comparison libtommath/bn_mp_prime_next_prime.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 a36e545fb43d
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_MP_PRIME_NEXT_PRIME_C 2 #ifdef BN_MP_PRIME_NEXT_PRIME_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 /* finds the next prime after the number "a" using "t" trials 15 /* finds the next prime after the number "a" using "t" trials
19 * of Miller-Rabin. 16 * of Miller-Rabin.
20 * 17 *
24 { 21 {
25 int err, res = MP_NO, x, y; 22 int err, res = MP_NO, x, y;
26 mp_digit res_tab[PRIME_SIZE], step, kstep; 23 mp_digit res_tab[PRIME_SIZE], step, kstep;
27 mp_int b; 24 mp_int b;
28 25
29 /* ensure t is valid */
30 if ((t <= 0) || (t > PRIME_SIZE)) {
31 return MP_VAL;
32 }
33
34 /* force positive */ 26 /* force positive */
35 a->sign = MP_ZPOS; 27 a->sign = MP_ZPOS;
36 28
37 /* simple algo if a is less than the largest prime in the table */ 29 /* simple algo if a is less than the largest prime in the table */
38 if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) { 30 if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) {
39 /* find which prime it is bigger than */ 31 /* find which prime it is bigger than */
40 for (x = PRIME_SIZE - 2; x >= 0; x--) { 32 for (x = PRIME_SIZE - 2; x >= 0; x--) {
41 if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) { 33 if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) {
42 if (bbs_style == 1) { 34 if (bbs_style == 1) {
43 /* ok we found a prime smaller or 35 /* ok we found a prime smaller or
44 * equal [so the next is larger] 36 * equal [so the next is larger]
45 * 37 *
46 * however, the prime must be 38 * however, the prime must be
47 * congruent to 3 mod 4 39 * congruent to 3 mod 4
48 */ 40 */
49 if ((ltm_prime_tab[x + 1] & 3) != 3) { 41 if ((ltm_prime_tab[x + 1] & 3u) != 3u) {
50 /* scan upwards for a prime congruent to 3 mod 4 */ 42 /* scan upwards for a prime congruent to 3 mod 4 */
51 for (y = x + 1; y < PRIME_SIZE; y++) { 43 for (y = x + 1; y < PRIME_SIZE; y++) {
52 if ((ltm_prime_tab[y] & 3) == 3) { 44 if ((ltm_prime_tab[y] & 3u) == 3u) {
53 mp_set(a, ltm_prime_tab[y]); 45 mp_set(a, ltm_prime_tab[y]);
54 return MP_OKAY; 46 return MP_OKAY;
55 } 47 }
56 } 48 }
57 } 49 }
58 } else { 50 } else {
59 mp_set(a, ltm_prime_tab[x + 1]); 51 mp_set(a, ltm_prime_tab[x + 1]);
60 return MP_OKAY; 52 return MP_OKAY;
61 } 53 }
62 } 54 }
63 } 55 }
64 /* at this point a maybe 1 */ 56 /* at this point a maybe 1 */
65 if (mp_cmp_d(a, 1) == MP_EQ) { 57 if (mp_cmp_d(a, 1uL) == MP_EQ) {
66 mp_set(a, 2); 58 mp_set(a, 2uL);
67 return MP_OKAY; 59 return MP_OKAY;
68 } 60 }
69 /* fall through to the sieve */ 61 /* fall through to the sieve */
70 } 62 }
71 63
78 70
79 /* at this point we will use a combination of a sieve and Miller-Rabin */ 71 /* at this point we will use a combination of a sieve and Miller-Rabin */
80 72
81 if (bbs_style == 1) { 73 if (bbs_style == 1) {
82 /* if a mod 4 != 3 subtract the correct value to make it so */ 74 /* if a mod 4 != 3 subtract the correct value to make it so */
83 if ((a->dp[0] & 3) != 3) { 75 if ((a->dp[0] & 3u) != 3u) {
84 if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; }; 76 if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
77 return err;
78 };
85 } 79 }
86 } else { 80 } else {
87 if (mp_iseven(a) == MP_YES) { 81 if (mp_iseven(a) == MP_YES) {
88 /* force odd */ 82 /* force odd */
89 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { 83 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
90 return err; 84 return err;
91 } 85 }
92 } 86 }
93 } 87 }
94 88
114 /* increase step to next candidate */ 108 /* increase step to next candidate */
115 step += kstep; 109 step += kstep;
116 110
117 /* compute the new residue without using division */ 111 /* compute the new residue without using division */
118 for (x = 1; x < PRIME_SIZE; x++) { 112 for (x = 1; x < PRIME_SIZE; x++) {
119 /* add the step to each residue */ 113 /* add the step to each residue */
120 res_tab[x] += kstep; 114 res_tab[x] += kstep;
121 115
122 /* subtract the modulus [instead of using division] */ 116 /* subtract the modulus [instead of using division] */
123 if (res_tab[x] >= ltm_prime_tab[x]) { 117 if (res_tab[x] >= ltm_prime_tab[x]) {
124 res_tab[x] -= ltm_prime_tab[x]; 118 res_tab[x] -= ltm_prime_tab[x];
125 } 119 }
126 120
127 /* set flag if zero */ 121 /* set flag if zero */
128 if (res_tab[x] == 0) { 122 if (res_tab[x] == 0u) {
129 y = 1; 123 y = 1;
130 } 124 }
131 } 125 }
132 } while ((y == 1) && (step < ((((mp_digit)1) << DIGIT_BIT) - kstep))); 126 } while ((y == 1) && (step < (((mp_digit)1 << DIGIT_BIT) - kstep)));
133 127
134 /* add the step */ 128 /* add the step */
135 if ((err = mp_add_d(a, step, a)) != MP_OKAY) { 129 if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
136 goto LBL_ERR; 130 goto LBL_ERR;
137 } 131 }
138 132
139 /* if didn't pass sieve and step == MAX then skip test */ 133 /* if didn't pass sieve and step == MAX then skip test */
140 if ((y == 1) && (step >= ((((mp_digit)1) << DIGIT_BIT) - kstep))) { 134 if ((y == 1) && (step >= (((mp_digit)1 << DIGIT_BIT) - kstep))) {
141 continue; 135 continue;
142 } 136 }
143 137
144 /* is this prime? */ 138 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
145 for (x = 0; x < t; x++) { 139 goto LBL_ERR;
146 mp_set(&b, ltm_prime_tab[x]);
147 if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
148 goto LBL_ERR;
149 }
150 if (res == MP_NO) {
151 break;
152 }
153 } 140 }
154
155 if (res == MP_YES) { 141 if (res == MP_YES) {
156 break; 142 break;
157 } 143 }
158 } 144 }
159 145
163 return err; 149 return err;
164 } 150 }
165 151
166 #endif 152 #endif
167 153
168 /* ref: $Format:%D$ */ 154 /* ref: HEAD -> master, tag: v1.1.0 */
169 /* git commit: $Format:%H$ */ 155 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
170 /* commit time: $Format:%ai$ */ 156 /* commit time: 2019-01-28 20:32:32 +0100 */