Mercurial > dropbear

comparison libtommath/bn_mp_dr_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_DR_REDUCE_C 2 #ifdef BN_MP_DR_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 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. 15 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
19 * 16 *
20 * Based on algorithm from the paper 17 * Based on algorithm from the paper
27 * 24 *
28 * Has been modified to use algorithm 7.10 from the LTM book instead 25 * Has been modified to use algorithm 7.10 from the LTM book instead
29 * 26 *
30 * Input x must be in the range 0 <= x <= (n-1)**2 27 * Input x must be in the range 0 <= x <= (n-1)**2
31 */ 28 */
32 int 29 int mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k)
33 mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
34 { 30 {
35 int err, i, m; 31 int err, i, m;
36 mp_word r; 32 mp_word r;
37 mp_digit mu, *tmpx1, *tmpx2; 33 mp_digit mu, *tmpx1, *tmpx2;
38 34
39 /* m = digits in modulus */ 35 /* m = digits in modulus */
40 m = n->used; 36 m = n->used;
41 37
42 /* ensure that "x" has at least 2m digits */ 38 /* ensure that "x" has at least 2m digits */
43 if (x->alloc < (m + m)) { 39 if (x->alloc < (m + m)) {
44 if ((err = mp_grow (x, m + m)) != MP_OKAY) { 40 if ((err = mp_grow(x, m + m)) != MP_OKAY) {
45 return err; 41 return err;
46 } 42 }
47 } 43 }
48 44
49 /* top of loop, this is where the code resumes if 45 /* top of loop, this is where the code resumes if
50 * another reduction pass is required. 46 * another reduction pass is required.
51 */ 47 */
52 top: 48 top:
53 /* aliases for digits */ 49 /* aliases for digits */
54 /* alias for lower half of x */ 50 /* alias for lower half of x */
55 tmpx1 = x->dp; 51 tmpx1 = x->dp;
56 52
57 /* alias for upper half of x, or x/B**m */ 53 /* alias for upper half of x, or x/B**m */
58 tmpx2 = x->dp + m; 54 tmpx2 = x->dp + m;
59 55
60 /* set carry to zero */ 56 /* set carry to zero */
61 mu = 0; 57 mu = 0;
62 58
63 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */ 59 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
64 for (i = 0; i < m; i++) { 60 for (i = 0; i < m; i++) {
65 r = (((mp_word)*tmpx2++) * (mp_word)k) + *tmpx1 + mu; 61 r = ((mp_word)*tmpx2++ * (mp_word)k) + *tmpx1 + mu;
66 *tmpx1++ = (mp_digit)(r & MP_MASK); 62 *tmpx1++ = (mp_digit)(r & MP_MASK);
67 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT)); 63 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
68 } 64 }
69 65
70 /* set final carry */ 66 /* set final carry */
71 *tmpx1++ = mu; 67 *tmpx1++ = mu;
72 68
73 /* zero words above m */ 69 /* zero words above m */
74 for (i = m + 1; i < x->used; i++) { 70 for (i = m + 1; i < x->used; i++) {
75 *tmpx1++ = 0; 71 *tmpx1++ = 0;
76 } 72 }
77 73
78 /* clamp, sub and return */ 74 /* clamp, sub and return */
79 mp_clamp (x); 75 mp_clamp(x);
80 76
81 /* if x >= n then subtract and reduce again 77 /* if x >= n then subtract and reduce again
82 * Each successive "recursion" makes the input smaller and smaller. 78 * Each successive "recursion" makes the input smaller and smaller.
83 */ 79 */
84 if (mp_cmp_mag (x, n) != MP_LT) { 80 if (mp_cmp_mag(x, n) != MP_LT) {
85 if ((err = s_mp_sub(x, n, x)) != MP_OKAY) { 81 if ((err = s_mp_sub(x, n, x)) != MP_OKAY) {
86 return err; 82 return err;
87 } 83 }
88 goto top; 84 goto top;
89 } 85 }
90 return MP_OKAY; 86 return MP_OKAY;
91 } 87 }
92 #endif 88 #endif
93 89
94 /* ref: $Format:%D$ */ 90 /* ref: HEAD -> master, tag: v1.1.0 */
95 /* git commit: $Format:%H$ */ 91 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
96 /* commit time: $Format:%ai$ */ 92 /* commit time: 2019-01-28 20:32:32 +0100 */