Mercurial > dropbear

comparison libtommath/bn_mp_montgomery_reduce.c @ 1655:f52919ffd3b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents 8bba51a55704
children 1051e4eea25a
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_MP_MONTGOMERY_REDUCE_C 2 #ifdef BN_MP_MONTGOMERY_REDUCE_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 * 4 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
7 * 7 *
8 * The library was designed directly after the MPI library by 8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with 9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * SPDX-License-Identifier: Unlicense
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */ 13 */
17 14
18 /* computes xR**-1 == x (mod N) via Montgomery Reduction */ 15 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
19 int 16 int mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho)
20 mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
21 { 17 {
22 int ix, res, digs; 18 int ix, res, digs;
23 mp_digit mu; 19 mp_digit mu;
24 20
25 /* can the fast reduction [comba] method be used? 21 /* can the fast reduction [comba] method be used?
26 * 22 *
27 * Note that unlike in mul you're safely allowed *less* 23 * Note that unlike in mul you're safely allowed *less*
28 * than the available columns [255 per default] since carries 24 * than the available columns [255 per default] since carries
29 * are fixed up in the inner loop. 25 * are fixed up in the inner loop.
30 */ 26 */
31 digs = (n->used * 2) + 1; 27 digs = (n->used * 2) + 1;
32 if ((digs < MP_WARRAY) && 28 if ((digs < (int)MP_WARRAY) &&
33 (n->used < 29 (x->used <= (int)MP_WARRAY) &&
34 (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * DIGIT_BIT))))) { 30 (n->used <
35 return fast_mp_montgomery_reduce (x, n, rho); 31 (int)(1u << (((size_t)CHAR_BIT * sizeof(mp_word)) - (2u * (size_t)DIGIT_BIT))))) {
36 } 32 return fast_mp_montgomery_reduce(x, n, rho);
33 }
37 34
38 /* grow the input as required */ 35 /* grow the input as required */
39 if (x->alloc < digs) { 36 if (x->alloc < digs) {
40 if ((res = mp_grow (x, digs)) != MP_OKAY) { 37 if ((res = mp_grow(x, digs)) != MP_OKAY) {
41 return res; 38 return res;
42 } 39 }
43 } 40 }
44 x->used = digs; 41 x->used = digs;
45 42
46 for (ix = 0; ix < n->used; ix++) { 43 for (ix = 0; ix < n->used; ix++) {
47 /* mu = ai * rho mod b 44 /* mu = ai * rho mod b
48 * 45 *
49 * The value of rho must be precalculated via 46 * The value of rho must be precalculated via
50 * montgomery_setup() such that 47 * montgomery_setup() such that
51 * it equals -1/n0 mod b this allows the 48 * it equals -1/n0 mod b this allows the
52 * following inner loop to reduce the 49 * following inner loop to reduce the
53 * input one digit at a time 50 * input one digit at a time
54 */ 51 */
55 mu = (mp_digit) (((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK); 52 mu = (mp_digit)(((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK);
56 53
57 /* a = a + mu * m * b**i */ 54 /* a = a + mu * m * b**i */
58 { 55 {
59 int iy; 56 int iy;
60 mp_digit *tmpn, *tmpx, u; 57 mp_digit *tmpn, *tmpx, u;
61 mp_word r; 58 mp_word r;
62 59
63 /* alias for digits of the modulus */ 60 /* alias for digits of the modulus */
64 tmpn = n->dp; 61 tmpn = n->dp;
65 62
66 /* alias for the digits of x [the input] */ 63 /* alias for the digits of x [the input] */
67 tmpx = x->dp + ix; 64 tmpx = x->dp + ix;
68 65
69 /* set the carry to zero */ 66 /* set the carry to zero */
70 u = 0; 67 u = 0;
71 68
72 /* Multiply and add in place */ 69 /* Multiply and add in place */
73 for (iy = 0; iy < n->used; iy++) { 70 for (iy = 0; iy < n->used; iy++) {
74 /* compute product and sum */ 71 /* compute product and sum */
75 r = ((mp_word)mu * (mp_word)*tmpn++) + 72 r = ((mp_word)mu * (mp_word)*tmpn++) +
76 (mp_word) u + (mp_word) *tmpx; 73 (mp_word)u + (mp_word)*tmpx;
77 74
78 /* get carry */ 75 /* get carry */
79 u = (mp_digit)(r >> ((mp_word) DIGIT_BIT)); 76 u = (mp_digit)(r >> (mp_word)DIGIT_BIT);
80 77
81 /* fix digit */ 78 /* fix digit */
82 *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK)); 79 *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK);
83 } 80 }
84 /* At this point the ix'th digit of x should be zero */ 81 /* At this point the ix'th digit of x should be zero */
85 82
86 83
87 /* propagate carries upwards as required*/ 84 /* propagate carries upwards as required*/
88 while (u != 0) { 85 while (u != 0u) {
89 *tmpx += u; 86 *tmpx += u;
90 u = *tmpx >> DIGIT_BIT; 87 u = *tmpx >> DIGIT_BIT;
91 *tmpx++ &= MP_MASK; 88 *tmpx++ &= MP_MASK;
89 }
92 } 90 }
93 } 91 }
94 }
95 92
96 /* at this point the n.used'th least 93 /* at this point the n.used'th least
97 * significant digits of x are all zero 94 * significant digits of x are all zero
98 * which means we can shift x to the 95 * which means we can shift x to the
99 * right by n.used digits and the 96 * right by n.used digits and the
100 * residue is unchanged. 97 * residue is unchanged.
101 */ 98 */
102 99
103 /* x = x/b**n.used */ 100 /* x = x/b**n.used */
104 mp_clamp(x); 101 mp_clamp(x);
105 mp_rshd (x, n->used); 102 mp_rshd(x, n->used);
106 103
107 /* if x >= n then x = x - n */ 104 /* if x >= n then x = x - n */
108 if (mp_cmp_mag (x, n) != MP_LT) { 105 if (mp_cmp_mag(x, n) != MP_LT) {
109 return s_mp_sub (x, n, x); 106 return s_mp_sub(x, n, x);
110 } 107 }
111 108
112 return MP_OKAY; 109 return MP_OKAY;
113 } 110 }
114 #endif 111 #endif
115 112
116 /* ref: $Format:%D$ */ 113 /* ref: HEAD -> master, tag: v1.1.0 */
117 /* git commit: $Format:%H$ */ 114 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
118 /* commit time: $Format:%ai$ */ 115 /* commit time: 2019-01-28 20:32:32 +0100 */