Mercurial > dropbear
comparison libtommath/bn_mp_dr_reduce.c @ 1655:f52919ffd3b1
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 */ |