/src/dropbear/libtommath/bn_mp_montgomery_reduce.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_MONTGOMERY_REDUCE_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* computes xR**-1 == x (mod N) via Montgomery Reduction */ |
7 | | mp_err mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho) |
8 | 1.21M | { |
9 | 1.21M | int ix, digs; |
10 | 1.21M | mp_err err; |
11 | 1.21M | mp_digit mu; |
12 | | |
13 | | /* can the fast reduction [comba] method be used? |
14 | | * |
15 | | * Note that unlike in mul you're safely allowed *less* |
16 | | * than the available columns [255 per default] since carries |
17 | | * are fixed up in the inner loop. |
18 | | */ |
19 | 1.21M | digs = (n->used * 2) + 1; |
20 | 1.21M | if ((digs < MP_WARRAY) && |
21 | 1.21M | (x->used <= MP_WARRAY) && |
22 | 1.21M | (n->used < MP_MAXFAST)) { |
23 | 1.21M | return s_mp_montgomery_reduce_fast(x, n, rho); |
24 | 1.21M | } |
25 | | |
26 | | /* grow the input as required */ |
27 | 0 | if (x->alloc < digs) { |
28 | 0 | if ((err = mp_grow(x, digs)) != MP_OKAY) { |
29 | 0 | return err; |
30 | 0 | } |
31 | 0 | } |
32 | 0 | x->used = digs; |
33 | |
|
34 | 0 | for (ix = 0; ix < n->used; ix++) { |
35 | | /* mu = ai * rho mod b |
36 | | * |
37 | | * The value of rho must be precalculated via |
38 | | * montgomery_setup() such that |
39 | | * it equals -1/n0 mod b this allows the |
40 | | * following inner loop to reduce the |
41 | | * input one digit at a time |
42 | | */ |
43 | 0 | mu = (mp_digit)(((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK); |
44 | | |
45 | | /* a = a + mu * m * b**i */ |
46 | 0 | { |
47 | 0 | int iy; |
48 | 0 | mp_digit *tmpn, *tmpx, u; |
49 | 0 | mp_word r; |
50 | | |
51 | | /* alias for digits of the modulus */ |
52 | 0 | tmpn = n->dp; |
53 | | |
54 | | /* alias for the digits of x [the input] */ |
55 | 0 | tmpx = x->dp + ix; |
56 | | |
57 | | /* set the carry to zero */ |
58 | 0 | u = 0; |
59 | | |
60 | | /* Multiply and add in place */ |
61 | 0 | for (iy = 0; iy < n->used; iy++) { |
62 | | /* compute product and sum */ |
63 | 0 | r = ((mp_word)mu * (mp_word)*tmpn++) + |
64 | 0 | (mp_word)u + (mp_word)*tmpx; |
65 | | |
66 | | /* get carry */ |
67 | 0 | u = (mp_digit)(r >> (mp_word)MP_DIGIT_BIT); |
68 | | |
69 | | /* fix digit */ |
70 | 0 | *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK); |
71 | 0 | } |
72 | | /* At this point the ix'th digit of x should be zero */ |
73 | | |
74 | | |
75 | | /* propagate carries upwards as required*/ |
76 | 0 | while (u != 0u) { |
77 | 0 | *tmpx += u; |
78 | 0 | u = *tmpx >> MP_DIGIT_BIT; |
79 | 0 | *tmpx++ &= MP_MASK; |
80 | 0 | } |
81 | 0 | } |
82 | 0 | } |
83 | | |
84 | | /* at this point the n.used'th least |
85 | | * significant digits of x are all zero |
86 | | * which means we can shift x to the |
87 | | * right by n.used digits and the |
88 | | * residue is unchanged. |
89 | | */ |
90 | | |
91 | | /* x = x/b**n.used */ |
92 | 0 | mp_clamp(x); |
93 | 0 | mp_rshd(x, n->used); |
94 | | |
95 | | /* if x >= n then x = x - n */ |
96 | 0 | if (mp_cmp_mag(x, n) != MP_LT) { |
97 | 0 | return s_mp_sub(x, n, x); |
98 | 0 | } |
99 | | |
100 | 0 | return MP_OKAY; |
101 | 0 | } |
102 | | #endif |