Mercurial > dropbear

comparison libtommath/bn_mp_montgomery_reduce.c @ 1739:13d834efc376 fuzz

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1562:768ebf737aa0 1739:13d834efc376
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 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17 5
18 /* computes xR**-1 == x (mod N) via Montgomery Reduction */ 6 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
19 int 7 mp_err 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 { 8 {
22 int ix, res, digs; 9 int ix, digs;
23 mp_digit mu; 10 mp_err err;
11 mp_digit mu;
24 12
25 /* can the fast reduction [comba] method be used? 13 /* can the fast reduction [comba] method be used?
26 * 14 *
27 * Note that unlike in mul you're safely allowed *less* 15 * Note that unlike in mul you're safely allowed *less*
28 * than the available columns [255 per default] since carries 16 * than the available columns [255 per default] since carries
29 * are fixed up in the inner loop. 17 * are fixed up in the inner loop.
30 */ 18 */
31 digs = (n->used * 2) + 1; 19 digs = (n->used * 2) + 1;
32 if ((digs < MP_WARRAY) && 20 if ((digs < MP_WARRAY) &&
33 (n->used < 21 (x->used <= MP_WARRAY) &&
34 (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * DIGIT_BIT))))) { 22 (n->used < MP_MAXFAST)) {
35 return fast_mp_montgomery_reduce (x, n, rho); 23 return s_mp_montgomery_reduce_fast(x, n, rho);
36 } 24 }
37 25
38 /* grow the input as required */ 26 /* grow the input as required */
39 if (x->alloc < digs) { 27 if (x->alloc < digs) {
40 if ((res = mp_grow (x, digs)) != MP_OKAY) { 28 if ((err = mp_grow(x, digs)) != MP_OKAY) {
41 return res; 29 return err;
42 } 30 }
43 } 31 }
44 x->used = digs; 32 x->used = digs;
45 33
46 for (ix = 0; ix < n->used; ix++) { 34 for (ix = 0; ix < n->used; ix++) {
47 /* mu = ai * rho mod b 35 /* mu = ai * rho mod b
48 * 36 *
49 * The value of rho must be precalculated via 37 * The value of rho must be precalculated via
50 * montgomery_setup() such that 38 * montgomery_setup() such that
51 * it equals -1/n0 mod b this allows the 39 * it equals -1/n0 mod b this allows the
52 * following inner loop to reduce the 40 * following inner loop to reduce the
53 * input one digit at a time 41 * input one digit at a time
54 */ 42 */
55 mu = (mp_digit) (((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK); 43 mu = (mp_digit)(((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK);
56 44
57 /* a = a + mu * m * b**i */ 45 /* a = a + mu * m * b**i */
58 { 46 {
59 int iy; 47 int iy;
60 mp_digit *tmpn, *tmpx, u; 48 mp_digit *tmpn, *tmpx, u;
61 mp_word r; 49 mp_word r;
62 50
63 /* alias for digits of the modulus */ 51 /* alias for digits of the modulus */
64 tmpn = n->dp; 52 tmpn = n->dp;
65 53
66 /* alias for the digits of x [the input] */ 54 /* alias for the digits of x [the input] */
67 tmpx = x->dp + ix; 55 tmpx = x->dp + ix;
68 56
69 /* set the carry to zero */ 57 /* set the carry to zero */
70 u = 0; 58 u = 0;
71 59
72 /* Multiply and add in place */ 60 /* Multiply and add in place */
73 for (iy = 0; iy < n->used; iy++) { 61 for (iy = 0; iy < n->used; iy++) {
74 /* compute product and sum */ 62 /* compute product and sum */
75 r = ((mp_word)mu * (mp_word)*tmpn++) + 63 r = ((mp_word)mu * (mp_word)*tmpn++) +
76 (mp_word) u + (mp_word) *tmpx; 64 (mp_word)u + (mp_word)*tmpx;
77 65
78 /* get carry */ 66 /* get carry */
79 u = (mp_digit)(r >> ((mp_word) DIGIT_BIT)); 67 u = (mp_digit)(r >> (mp_word)MP_DIGIT_BIT);
80 68
81 /* fix digit */ 69 /* fix digit */
82 *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK)); 70 *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK);
83 } 71 }
84 /* At this point the ix'th digit of x should be zero */ 72 /* At this point the ix'th digit of x should be zero */
85 73
86 74
87 /* propagate carries upwards as required*/ 75 /* propagate carries upwards as required*/
88 while (u != 0) { 76 while (u != 0u) {
89 *tmpx += u; 77 *tmpx += u;
90 u = *tmpx >> DIGIT_BIT; 78 u = *tmpx >> MP_DIGIT_BIT;
91 *tmpx++ &= MP_MASK; 79 *tmpx++ &= MP_MASK;
80 }
92 } 81 }
93 } 82 }
94 }
95 83
96 /* at this point the n.used'th least 84 /* at this point the n.used'th least
97 * significant digits of x are all zero 85 * significant digits of x are all zero
98 * which means we can shift x to the 86 * which means we can shift x to the
99 * right by n.used digits and the 87 * right by n.used digits and the
100 * residue is unchanged. 88 * residue is unchanged.
101 */ 89 */
102 90
103 /* x = x/b**n.used */ 91 /* x = x/b**n.used */
104 mp_clamp(x); 92 mp_clamp(x);
105 mp_rshd (x, n->used); 93 mp_rshd(x, n->used);
106 94
107 /* if x >= n then x = x - n */ 95 /* if x >= n then x = x - n */
108 if (mp_cmp_mag (x, n) != MP_LT) { 96 if (mp_cmp_mag(x, n) != MP_LT) {
109 return s_mp_sub (x, n, x); 97 return s_mp_sub(x, n, x);
110 } 98 }
111 99
112 return MP_OKAY; 100 return MP_OKAY;
113 } 101 }
114 #endif 102 #endif
115
116 /* ref: $Format:%D$ */
117 /* git commit: $Format:%H$ */
118 /* commit time: $Format:%ai$ */