/src/dropbear/libtommath/bn_mp_dr_reduce.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_DR_REDUCE_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. |
7 | | * |
8 | | * Based on algorithm from the paper |
9 | | * |
10 | | * "Generating Efficient Primes for Discrete Log Cryptosystems" |
11 | | * Chae Hoon Lim, Pil Joong Lee, |
12 | | * POSTECH Information Research Laboratories |
13 | | * |
14 | | * The modulus must be of a special format [see manual] |
15 | | * |
16 | | * Has been modified to use algorithm 7.10 from the LTM book instead |
17 | | * |
18 | | * Input x must be in the range 0 <= x <= (n-1)**2 |
19 | | */ |
20 | | mp_err mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k) |
21 | 0 | { |
22 | 0 | mp_err err; |
23 | 0 | int i, m; |
24 | 0 | mp_word r; |
25 | 0 | mp_digit mu, *tmpx1, *tmpx2; |
26 | | |
27 | | /* m = digits in modulus */ |
28 | 0 | m = n->used; |
29 | | |
30 | | /* ensure that "x" has at least 2m digits */ |
31 | 0 | if (x->alloc < (m + m)) { |
32 | 0 | if ((err = mp_grow(x, m + m)) != MP_OKAY) { |
33 | 0 | return err; |
34 | 0 | } |
35 | 0 | } |
36 | | |
37 | | /* top of loop, this is where the code resumes if |
38 | | * another reduction pass is required. |
39 | | */ |
40 | 0 | top: |
41 | | /* aliases for digits */ |
42 | | /* alias for lower half of x */ |
43 | 0 | tmpx1 = x->dp; |
44 | | |
45 | | /* alias for upper half of x, or x/B**m */ |
46 | 0 | tmpx2 = x->dp + m; |
47 | | |
48 | | /* set carry to zero */ |
49 | 0 | mu = 0; |
50 | | |
51 | | /* compute (x mod B**m) + k * [x/B**m] inline and inplace */ |
52 | 0 | for (i = 0; i < m; i++) { |
53 | 0 | r = ((mp_word)*tmpx2++ * (mp_word)k) + *tmpx1 + mu; |
54 | 0 | *tmpx1++ = (mp_digit)(r & MP_MASK); |
55 | 0 | mu = (mp_digit)(r >> ((mp_word)MP_DIGIT_BIT)); |
56 | 0 | } |
57 | | |
58 | | /* set final carry */ |
59 | 0 | *tmpx1++ = mu; |
60 | | |
61 | | /* zero words above m */ |
62 | 0 | MP_ZERO_DIGITS(tmpx1, (x->used - m) - 1); |
63 | | |
64 | | /* clamp, sub and return */ |
65 | 0 | mp_clamp(x); |
66 | | |
67 | | /* if x >= n then subtract and reduce again |
68 | | * Each successive "recursion" makes the input smaller and smaller. |
69 | | */ |
70 | 0 | if (mp_cmp_mag(x, n) != MP_LT) { |
71 | 0 | if ((err = s_mp_sub(x, n, x)) != MP_OKAY) { |
72 | 0 | return err; |
73 | 0 | } |
74 | 0 | goto top; |
75 | 0 | } |
76 | 0 | return MP_OKAY; |
77 | 0 | } |
78 | | #endif |