Mercurial > dropbear

comparison libtommath/bn_mp_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_REDUCE_C 2 #ifdef BN_MP_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 /* reduces x mod m, assumes 0 < x < m**2, mu is 15 /* reduces x mod m, assumes 0 < x < m**2, mu is
19 * precomputed via mp_reduce_setup. 16 * precomputed via mp_reduce_setup.
20 * From HAC pp.604 Algorithm 14.42 17 * From HAC pp.604 Algorithm 14.42
21 */ 18 */
22 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu) 19 int mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu)
23 { 20 {
24 mp_int q; 21 mp_int q;
25 int res, um = m->used; 22 int res, um = m->used;
26 23
27 /* q = x */ 24 /* q = x */
28 if ((res = mp_init_copy (&q, x)) != MP_OKAY) { 25 if ((res = mp_init_copy(&q, x)) != MP_OKAY) {
29 return res; 26 return res;
30 } 27 }
31 28
32 /* q1 = x / b**(k-1) */ 29 /* q1 = x / b**(k-1) */
33 mp_rshd (&q, um - 1); 30 mp_rshd(&q, um - 1);
34 31
35 /* according to HAC this optimization is ok */ 32 /* according to HAC this optimization is ok */
36 if (((mp_digit) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) { 33 if ((mp_digit)um > ((mp_digit)1 << (DIGIT_BIT - 1))) {
37 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) { 34 if ((res = mp_mul(&q, mu, &q)) != MP_OKAY) {
35 goto CLEANUP;
36 }
37 } else {
38 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
39 if ((res = s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) {
40 goto CLEANUP;
41 }
42 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
43 if ((res = fast_s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) {
44 goto CLEANUP;
45 }
46 #else
47 {
48 res = MP_VAL;
49 goto CLEANUP;
50 }
51 #endif
52 }
53
54 /* q3 = q2 / b**(k+1) */
55 mp_rshd(&q, um + 1);
56
57 /* x = x mod b**(k+1), quick (no division) */
58 if ((res = mp_mod_2d(x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
38 goto CLEANUP; 59 goto CLEANUP;
39 } 60 }
40 } else { 61
41 #ifdef BN_S_MP_MUL_HIGH_DIGS_C 62 /* q = q * m mod b**(k+1), quick (no division) */
42 if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { 63 if ((res = s_mp_mul_digs(&q, m, &q, um + 1)) != MP_OKAY) {
43 goto CLEANUP; 64 goto CLEANUP;
44 } 65 }
45 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C) 66
46 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { 67 /* x = x - q */
68 if ((res = mp_sub(x, &q, x)) != MP_OKAY) {
47 goto CLEANUP; 69 goto CLEANUP;
48 } 70 }
49 #else
50 {
51 res = MP_VAL;
52 goto CLEANUP;
53 }
54 #endif
55 }
56 71
57 /* q3 = q2 / b**(k+1) */ 72 /* If x < 0, add b**(k+1) to it */
58 mp_rshd (&q, um + 1); 73 if (mp_cmp_d(x, 0uL) == MP_LT) {
74 mp_set(&q, 1uL);
75 if ((res = mp_lshd(&q, um + 1)) != MP_OKAY)
76 goto CLEANUP;
77 if ((res = mp_add(x, &q, x)) != MP_OKAY)
78 goto CLEANUP;
79 }
59 80
60 /* x = x mod b**(k+1), quick (no division) */ 81 /* Back off if it's too big */
61 if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) { 82 while (mp_cmp(x, m) != MP_LT) {
62 goto CLEANUP; 83 if ((res = s_mp_sub(x, m, x)) != MP_OKAY) {
63 } 84 goto CLEANUP;
64 85 }
65 /* q = q * m mod b**(k+1), quick (no division) */ 86 }
66 if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) {
67 goto CLEANUP;
68 }
69
70 /* x = x - q */
71 if ((res = mp_sub (x, &q, x)) != MP_OKAY) {
72 goto CLEANUP;
73 }
74
75 /* If x < 0, add b**(k+1) to it */
76 if (mp_cmp_d (x, 0) == MP_LT) {
77 mp_set (&q, 1);
78 if ((res = mp_lshd (&q, um + 1)) != MP_OKAY)
79 goto CLEANUP;
80 if ((res = mp_add (x, &q, x)) != MP_OKAY)
81 goto CLEANUP;
82 }
83
84 /* Back off if it's too big */
85 while (mp_cmp (x, m) != MP_LT) {
86 if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
87 goto CLEANUP;
88 }
89 }
90 87
91 CLEANUP: 88 CLEANUP:
92 mp_clear (&q); 89 mp_clear(&q);
93 90
94 return res; 91 return res;
95 } 92 }
96 #endif 93 #endif
97 94
98 /* ref: $Format:%D$ */ 95 /* ref: HEAD -> master, tag: v1.1.0 */
99 /* git commit: $Format:%H$ */ 96 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
100 /* commit time: $Format:%ai$ */ 97 /* commit time: 2019-01-28 20:32:32 +0100 */