1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
56 */
57 /* ====================================================================
58 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
59 *
60 * Redistribution and use in source and binary forms, with or without
61 * modification, are permitted provided that the following conditions
62 * are met:
63 *
64 * 1. Redistributions of source code must retain the above copyright
65 * notice, this list of conditions and the following disclaimer.
66 *
67 * 2. Redistributions in binary form must reproduce the above copyright
68 * notice, this list of conditions and the following disclaimer in
69 * the documentation and/or other materials provided with the
70 * distribution.
71 *
72 * 3. All advertising materials mentioning features or use of this
73 * software must display the following acknowledgment:
74 * "This product includes software developed by the OpenSSL Project
75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
76 *
77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
78 * endorse or promote products derived from this software without
79 * prior written permission. For written permission, please contact
80 * openssl-core@openssl.org.
81 *
82 * 5. Products derived from this software may not be called "OpenSSL"
83 * nor may "OpenSSL" appear in their names without prior written
84 * permission of the OpenSSL Project.
85 *
86 * 6. Redistributions of any form whatsoever must retain the following
87 * acknowledgment:
88 * "This product includes software developed by the OpenSSL Project
89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
90 *
91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
102 * OF THE POSSIBILITY OF SUCH DAMAGE.
103 * ====================================================================
104 *
105 * This product includes cryptographic software written by Eric Young
106 * (eay@cryptsoft.com). This product includes software written by Tim
107 * Hudson (tjh@cryptsoft.com). */
108
109 #include <openssl/bn.h>
110
111 #include <openssl/err.h>
112 #include <openssl/mem.h>
113
114 #include "internal.h"
115 #include "../../internal.h"
116
117
118 // kPrimes contains the first 1024 primes.
119 static const uint16_t kPrimes[] = {
120 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
121 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
122 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
123 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
124 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
125 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
126 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433,
127 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
128 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
129 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
130 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
131 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827,
132 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
133 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
134 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
135 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
136 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
137 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
138 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439,
139 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
140 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601,
141 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
142 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783,
143 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
144 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
145 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
146 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,
147 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
148 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347,
149 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
150 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543,
151 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
152 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713,
153 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
154 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
155 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
156 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119,
157 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
158 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323,
159 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
160 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527,
161 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
162 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697,
163 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
164 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
165 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
166 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093,
167 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
168 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283,
169 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
170 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513,
171 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
172 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721,
173 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
174 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
175 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
176 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113,
177 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
178 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351,
179 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
180 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531,
181 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
182 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743,
183 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
184 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
185 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
186 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173,
187 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
188 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359,
189 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
190 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581,
191 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
192 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803,
193 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
194 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
195 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
196 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229,
197 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
198 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487,
199 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
200 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669,
201 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
202 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879,
203 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
204 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
205 8117, 8123, 8147, 8161,
206 };
207
208 // BN_prime_checks_for_size returns the number of Miller-Rabin iterations
209 // necessary for generating a 'bits'-bit candidate prime.
210 //
211 //
212 // This table is generated using the algorithm of FIPS PUB 186-4
213 // Digital Signature Standard (DSS), section F.1, page 117.
214 // (https://doi.org/10.6028/NIST.FIPS.186-4)
215 // The following magma script was used to generate the output:
216 // securitybits:=125;
217 // k:=1024;
218 // for t:=1 to 65 do
219 // for M:=3 to Floor(2*Sqrt(k-1)-1) do
220 // S:=0;
221 // // Sum over m
222 // for m:=3 to M do
223 // s:=0;
224 // // Sum over j
225 // for j:=2 to m do
226 // s+:=(RealField(32)!2)^-(j+(k-1)/j);
227 // end for;
228 // S+:=2^(m-(m-1)*t)*s;
229 // end for;
230 // A:=2^(k-2-M*t);
231 // B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S;
232 // pkt:=2.00743*Log(2)*k*2^-k*(A+B);
233 // seclevel:=Floor(-Log(2,pkt));
234 // if seclevel ge securitybits then
235 // printf "k: %5o, security: %o bits (t: %o, M: %o)\n",k,seclevel,t,M;
236 // break;
237 // end if;
238 // end for;
239 // if seclevel ge securitybits then break; end if;
240 // end for;
241 //
242 // It can be run online at: http://magma.maths.usyd.edu.au/calc
243 // And will output:
244 // k: 1024, security: 129 bits (t: 6, M: 23)
245 // k is the number of bits of the prime, securitybits is the level we want to
246 // reach.
247 // prime length | RSA key size | # MR tests | security level
248 // -------------+--------------|------------+---------------
249 // (b) >= 6394 | >= 12788 | 3 | 256 bit
250 // (b) >= 3747 | >= 7494 | 3 | 192 bit
251 // (b) >= 1345 | >= 2690 | 4 | 128 bit
252 // (b) >= 1080 | >= 2160 | 5 | 128 bit
253 // (b) >= 852 | >= 1704 | 5 | 112 bit
254 // (b) >= 476 | >= 952 | 5 | 80 bit
255 // (b) >= 400 | >= 800 | 6 | 80 bit
256 // (b) >= 347 | >= 694 | 7 | 80 bit
257 // (b) >= 308 | >= 616 | 8 | 80 bit
258 // (b) >= 55 | >= 110 | 27 | 64 bit
259 // (b) >= 6 | >= 12 | 34 | 64 bit
BN_prime_checks_for_size(int bits)260 static int BN_prime_checks_for_size(int bits) {
261 if (bits >= 3747) {
262 return 3;
263 }
264 if (bits >= 1345) {
265 return 4;
266 }
267 if (bits >= 476) {
268 return 5;
269 }
270 if (bits >= 400) {
271 return 6;
272 }
273 if (bits >= 347) {
274 return 7;
275 }
276 if (bits >= 308) {
277 return 8;
278 }
279 if (bits >= 55) {
280 return 27;
281 }
282 return 34;
283 }
284
285 // num_trial_division_primes returns the number of primes to try with trial
286 // division before using more expensive checks. For larger numbers, the value
287 // of excluding a candidate with trial division is larger.
num_trial_division_primes(const BIGNUM * n)288 static size_t num_trial_division_primes(const BIGNUM *n) {
289 if (n->width * BN_BITS2 > 1024) {
290 return OPENSSL_ARRAY_SIZE(kPrimes);
291 }
292 return OPENSSL_ARRAY_SIZE(kPrimes) / 2;
293 }
294
295 // BN_PRIME_CHECKS_BLINDED is the iteration count for blinding the constant-time
296 // primality test. See |BN_primality_test| for details. This number is selected
297 // so that, for a candidate N-bit RSA prime, picking |BN_PRIME_CHECKS_BLINDED|
298 // random N-bit numbers will have at least |BN_prime_checks_for_size(N)| values
299 // in range with high probability.
300 //
301 // The following Python script computes the blinding factor needed for the
302 // corresponding iteration count.
303 /*
304 import math
305
306 # We choose candidate RSA primes between sqrt(2)/2 * 2^N and 2^N and select
307 # witnesses by generating random N-bit numbers. Thus the probability of
308 # selecting one in range is at least sqrt(2)/2.
309 p = math.sqrt(2) / 2
310
311 # Target around 2^-8 probability of the blinding being insufficient given that
312 # key generation is a one-time, noisy operation.
313 epsilon = 2**-8
314
315 def choose(a, b):
316 r = 1
317 for i in xrange(b):
318 r *= a - i
319 r /= (i + 1)
320 return r
321
322 def failure_rate(min_uniform, iterations):
323 """ Returns the probability that, for |iterations| candidate witnesses, fewer
324 than |min_uniform| of them will be uniform. """
325 prob = 0.0
326 for i in xrange(min_uniform):
327 prob += (choose(iterations, i) *
328 p**i * (1-p)**(iterations - i))
329 return prob
330
331 for min_uniform in (3, 4, 5, 6, 8, 13, 19, 28):
332 # Find the smallest number of iterations under the target failure rate.
333 iterations = min_uniform
334 while True:
335 prob = failure_rate(min_uniform, iterations)
336 if prob < epsilon:
337 print min_uniform, iterations, prob
338 break
339 iterations += 1
340
341 Output:
342 3 9 0.00368894873911
343 4 11 0.00363319494662
344 5 13 0.00336215573898
345 6 15 0.00300145783158
346 8 19 0.00225214119331
347 13 27 0.00385610026955
348 19 38 0.0021410539126
349 28 52 0.00325405801769
350
351 16 iterations suffices for 400-bit primes and larger (6 uniform samples needed),
352 which is already well below the minimum acceptable key size for RSA.
353 */
354 #define BN_PRIME_CHECKS_BLINDED 16
355
356 static int probable_prime(BIGNUM *rnd, int bits);
357 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
358 const BIGNUM *rem, BN_CTX *ctx);
359 static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add,
360 const BIGNUM *rem, BN_CTX *ctx);
361
BN_GENCB_new(void)362 BN_GENCB *BN_GENCB_new(void) {
363 BN_GENCB *callback = OPENSSL_malloc(sizeof(BN_GENCB));
364 if (callback == NULL) {
365 return NULL;
366 }
367 OPENSSL_memset(callback, 0, sizeof(BN_GENCB));
368 return callback;
369 }
370
BN_GENCB_free(BN_GENCB * callback)371 void BN_GENCB_free(BN_GENCB *callback) { OPENSSL_free(callback); }
372
BN_GENCB_set(BN_GENCB * callback,int (* f)(int event,int n,struct bn_gencb_st *),void * arg)373 void BN_GENCB_set(BN_GENCB *callback,
374 int (*f)(int event, int n, struct bn_gencb_st *),
375 void *arg) {
376 callback->callback = f;
377 callback->arg = arg;
378 }
379
BN_GENCB_call(BN_GENCB * callback,int event,int n)380 int BN_GENCB_call(BN_GENCB *callback, int event, int n) {
381 if (!callback) {
382 return 1;
383 }
384
385 return callback->callback(event, n, callback);
386 }
387
BN_GENCB_get_arg(const BN_GENCB * callback)388 void *BN_GENCB_get_arg(const BN_GENCB *callback) { return callback->arg; }
389
BN_generate_prime_ex(BIGNUM * ret,int bits,int safe,const BIGNUM * add,const BIGNUM * rem,BN_GENCB * cb)390 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
391 const BIGNUM *rem, BN_GENCB *cb) {
392 BIGNUM *t;
393 int found = 0;
394 int i, j, c1 = 0;
395 BN_CTX *ctx;
396 int checks = BN_prime_checks_for_size(bits);
397
398 if (bits < 2) {
399 // There are no prime numbers this small.
400 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
401 return 0;
402 } else if (bits == 2 && safe) {
403 // The smallest safe prime (7) is three bits.
404 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
405 return 0;
406 }
407
408 ctx = BN_CTX_new();
409 if (ctx == NULL) {
410 goto err;
411 }
412 BN_CTX_start(ctx);
413 t = BN_CTX_get(ctx);
414 if (!t) {
415 goto err;
416 }
417
418 loop:
419 // make a random number and set the top and bottom bits
420 if (add == NULL) {
421 if (!probable_prime(ret, bits)) {
422 goto err;
423 }
424 } else {
425 if (safe) {
426 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) {
427 goto err;
428 }
429 } else {
430 if (!probable_prime_dh(ret, bits, add, rem, ctx)) {
431 goto err;
432 }
433 }
434 }
435
436 if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) {
437 // aborted
438 goto err;
439 }
440
441 if (!safe) {
442 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
443 if (i == -1) {
444 goto err;
445 } else if (i == 0) {
446 goto loop;
447 }
448 } else {
449 // for "safe prime" generation, check that (p-1)/2 is prime. Since a prime
450 // is odd, We just need to divide by 2
451 if (!BN_rshift1(t, ret)) {
452 goto err;
453 }
454
455 // Interleave |ret| and |t|'s primality tests to avoid paying the full
456 // iteration count on |ret| only to quickly discover |t| is composite.
457 //
458 // TODO(davidben): This doesn't quite work because an iteration count of 1
459 // still runs the blinding mechanism.
460 for (i = 0; i < checks; i++) {
461 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL);
462 if (j == -1) {
463 goto err;
464 } else if (j == 0) {
465 goto loop;
466 }
467
468 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL);
469 if (j == -1) {
470 goto err;
471 } else if (j == 0) {
472 goto loop;
473 }
474
475 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i)) {
476 goto err;
477 }
478 // We have a safe prime test pass
479 }
480 }
481
482 // we have a prime :-)
483 found = 1;
484
485 err:
486 if (ctx != NULL) {
487 BN_CTX_end(ctx);
488 BN_CTX_free(ctx);
489 }
490
491 return found;
492 }
493
bn_trial_division(uint16_t * out,const BIGNUM * bn)494 static int bn_trial_division(uint16_t *out, const BIGNUM *bn) {
495 const size_t num_primes = num_trial_division_primes(bn);
496 for (size_t i = 1; i < num_primes; i++) {
497 if (bn_mod_u16_consttime(bn, kPrimes[i]) == 0) {
498 *out = kPrimes[i];
499 return 1;
500 }
501 }
502 return 0;
503 }
504
bn_odd_number_is_obviously_composite(const BIGNUM * bn)505 int bn_odd_number_is_obviously_composite(const BIGNUM *bn) {
506 uint16_t prime;
507 return bn_trial_division(&prime, bn) && !BN_is_word(bn, prime);
508 }
509
bn_miller_rabin_init(BN_MILLER_RABIN * miller_rabin,const BN_MONT_CTX * mont,BN_CTX * ctx)510 int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin, const BN_MONT_CTX *mont,
511 BN_CTX *ctx) {
512 // This function corresponds to steps 1 through 3 of FIPS 186-4, C.3.1.
513 const BIGNUM *w = &mont->N;
514 // Note we do not call |BN_CTX_start| in this function. We intentionally
515 // allocate values in the containing scope so they outlive this function.
516 miller_rabin->w1 = BN_CTX_get(ctx);
517 miller_rabin->m = BN_CTX_get(ctx);
518 miller_rabin->one_mont = BN_CTX_get(ctx);
519 miller_rabin->w1_mont = BN_CTX_get(ctx);
520 if (miller_rabin->w1 == NULL ||
521 miller_rabin->m == NULL ||
522 miller_rabin->one_mont == NULL ||
523 miller_rabin->w1_mont == NULL) {
524 return 0;
525 }
526
527 // See FIPS 186-4, C.3.1, steps 1 through 3.
528 if (!bn_usub_consttime(miller_rabin->w1, w, BN_value_one())) {
529 return 0;
530 }
531 miller_rabin->a = BN_count_low_zero_bits(miller_rabin->w1);
532 if (!bn_rshift_secret_shift(miller_rabin->m, miller_rabin->w1,
533 miller_rabin->a, ctx)) {
534 return 0;
535 }
536 miller_rabin->w_bits = BN_num_bits(w);
537
538 // Precompute some values in Montgomery form.
539 if (!bn_one_to_montgomery(miller_rabin->one_mont, mont, ctx) ||
540 // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
541 // with a subtraction. (|one_mont| cannot be zero.)
542 !bn_usub_consttime(miller_rabin->w1_mont, w, miller_rabin->one_mont)) {
543 return 0;
544 }
545
546 return 1;
547 }
548
bn_miller_rabin_iteration(const BN_MILLER_RABIN * miller_rabin,int * out_is_possibly_prime,const BIGNUM * b,const BN_MONT_CTX * mont,BN_CTX * ctx)549 int bn_miller_rabin_iteration(const BN_MILLER_RABIN *miller_rabin,
550 int *out_is_possibly_prime, const BIGNUM *b,
551 const BN_MONT_CTX *mont, BN_CTX *ctx) {
552 // This function corresponds to steps 4.3 through 4.5 of FIPS 186-4, C.3.1.
553 int ret = 0;
554 BN_CTX_start(ctx);
555
556 // Step 4.3. We use Montgomery-encoding for better performance and to avoid
557 // timing leaks.
558 const BIGNUM *w = &mont->N;
559 BIGNUM *z = BN_CTX_get(ctx);
560 if (z == NULL ||
561 !BN_mod_exp_mont_consttime(z, b, miller_rabin->m, w, ctx, mont) ||
562 !BN_to_montgomery(z, z, mont, ctx)) {
563 goto err;
564 }
565
566 // is_possibly_prime is all ones if we have determined |b| is not a composite
567 // witness for |w|. This is equivalent to going to step 4.7 in the original
568 // algorithm. To avoid timing leaks, we run the algorithm to the end for prime
569 // inputs.
570 crypto_word_t is_possibly_prime = 0;
571
572 // Step 4.4. If z = 1 or z = w-1, b is not a composite witness and w is still
573 // possibly prime.
574 is_possibly_prime = BN_equal_consttime(z, miller_rabin->one_mont) |
575 BN_equal_consttime(z, miller_rabin->w1_mont);
576 is_possibly_prime = 0 - is_possibly_prime; // Make it all zeros or all ones.
577
578 // Step 4.5.
579 //
580 // To avoid leaking |a|, we run the loop to |w_bits| and mask off all
581 // iterations once |j| = |a|.
582 for (int j = 1; j < miller_rabin->w_bits; j++) {
583 if (constant_time_eq_int(j, miller_rabin->a) & ~is_possibly_prime) {
584 // If the loop is done and we haven't seen z = 1 or z = w-1 yet, the
585 // value is composite and we can break in variable time.
586 break;
587 }
588
589 // Step 4.5.1.
590 if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
591 goto err;
592 }
593
594 // Step 4.5.2. If z = w-1 and the loop is not done, this is not a composite
595 // witness.
596 crypto_word_t z_is_w1_mont = BN_equal_consttime(z, miller_rabin->w1_mont);
597 z_is_w1_mont = 0 - z_is_w1_mont; // Make it all zeros or all ones.
598 is_possibly_prime |= z_is_w1_mont; // Go to step 4.7 if |z_is_w1_mont|.
599
600 // Step 4.5.3. If z = 1 and the loop is not done, the previous value of z
601 // was not -1. There are no non-trivial square roots of 1 modulo a prime, so
602 // w is composite and we may exit in variable time.
603 if (BN_equal_consttime(z, miller_rabin->one_mont) & ~is_possibly_prime) {
604 break;
605 }
606 }
607
608 *out_is_possibly_prime = is_possibly_prime & 1;
609 ret = 1;
610
611 err:
612 BN_CTX_end(ctx);
613 return ret;
614 }
615
BN_primality_test(int * out_is_probably_prime,const BIGNUM * w,int checks,BN_CTX * ctx,int do_trial_division,BN_GENCB * cb)616 int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w, int checks,
617 BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) {
618 // This function's secrecy and performance requirements come from RSA key
619 // generation. We generate RSA keys by selecting two large, secret primes with
620 // rejection sampling.
621 //
622 // We thus treat |w| as secret if turns out to be a large prime. However, if
623 // |w| is composite, we treat this and |w| itself as public. (Conversely, if
624 // |w| is prime, that it is prime is public. Only the value is secret.) This
625 // is fine for RSA key generation, but note it is important that we use
626 // rejection sampling, with each candidate prime chosen independently. This
627 // would not work for, e.g., an algorithm which looked for primes in
628 // consecutive integers. These assumptions allow us to discard composites
629 // quickly. We additionally treat |w| as public when it is a small prime to
630 // simplify trial decryption and some edge cases.
631 //
632 // One RSA key generation will call this function on exactly two primes and
633 // many more composites. The overall cost is a combination of several factors:
634 //
635 // 1. Checking if |w| is divisible by a small prime is much faster than
636 // learning it is composite by Miller-Rabin (see below for details on that
637 // cost). Trial division by p saves 1/p of Miller-Rabin calls, so this is
638 // worthwhile until p exceeds the ratio of the two costs.
639 //
640 // 2. For a random (i.e. non-adversarial) candidate large prime and candidate
641 // witness, the probability of false witness is very low. (This is why FIPS
642 // 186-4 only requires a few iterations.) Thus composites not discarded by
643 // trial decryption, in practice, cost one Miller-Rabin iteration. Only the
644 // two actual primes cost the full iteration count.
645 //
646 // 3. A Miller-Rabin iteration is a modular exponentiation plus |a| additional
647 // modular squares, where |a| is the number of factors of two in |w-1|. |a|
648 // is likely small (the distribution falls exponentially), but it is also
649 // potentially secret, so we loop up to its log(w) upper bound when |w| is
650 // prime. When |w| is composite, we break early, so only two calls pay this
651 // cost. (Note that all calls pay the modular exponentiation which is,
652 // itself, log(w) modular multiplications and squares.)
653 //
654 // 4. While there are only two prime calls, they multiplicatively pay the full
655 // costs of (2) and (3).
656 //
657 // 5. After the primes are chosen, RSA keys derive some values from the
658 // primes, but this cost is negligible in comparison.
659
660 *out_is_probably_prime = 0;
661
662 if (BN_cmp(w, BN_value_one()) <= 0) {
663 return 1;
664 }
665
666 if (!BN_is_odd(w)) {
667 // The only even prime is two.
668 *out_is_probably_prime = BN_is_word(w, 2);
669 return 1;
670 }
671
672 // Miller-Rabin does not work for three.
673 if (BN_is_word(w, 3)) {
674 *out_is_probably_prime = 1;
675 return 1;
676 }
677
678 if (do_trial_division) {
679 // Perform additional trial division checks to discard small primes.
680 uint16_t prime;
681 if (bn_trial_division(&prime, w)) {
682 *out_is_probably_prime = BN_is_word(w, prime);
683 return 1;
684 }
685 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, -1)) {
686 return 0;
687 }
688 }
689
690 if (checks == BN_prime_checks_for_generation) {
691 checks = BN_prime_checks_for_size(BN_num_bits(w));
692 }
693
694 BN_CTX *new_ctx = NULL;
695 if (ctx == NULL) {
696 new_ctx = BN_CTX_new();
697 if (new_ctx == NULL) {
698 return 0;
699 }
700 ctx = new_ctx;
701 }
702
703 // See C.3.1 from FIPS 186-4.
704 int ret = 0;
705 BN_CTX_start(ctx);
706 BIGNUM *b = BN_CTX_get(ctx);
707 BN_MONT_CTX *mont = BN_MONT_CTX_new_consttime(w, ctx);
708 BN_MILLER_RABIN miller_rabin;
709 if (b == NULL || mont == NULL ||
710 // Steps 1-3.
711 !bn_miller_rabin_init(&miller_rabin, mont, ctx)) {
712 goto err;
713 }
714
715 // The following loop performs in inner iteration of the Miller-Rabin
716 // Primality test (Step 4).
717 //
718 // The algorithm as specified in FIPS 186-4 leaks information on |w|, the RSA
719 // private key. Instead, we run through each iteration unconditionally,
720 // performing modular multiplications, masking off any effects to behave
721 // equivalently to the specified algorithm.
722 //
723 // We also blind the number of values of |b| we try. Steps 4.1–4.2 say to
724 // discard out-of-range values. To avoid leaking information on |w|, we use
725 // |bn_rand_secret_range| which, rather than discarding bad values, adjusts
726 // them to be in range. Though not uniformly selected, these adjusted values
727 // are still usable as Miller-Rabin checks.
728 //
729 // Miller-Rabin is already probabilistic, so we could reach the desired
730 // confidence levels by just suitably increasing the iteration count. However,
731 // to align with FIPS 186-4, we use a more pessimal analysis: we do not count
732 // the non-uniform values towards the iteration count. As a result, this
733 // function is more complex and has more timing risk than necessary.
734 //
735 // We count both total iterations and uniform ones and iterate until we've
736 // reached at least |BN_PRIME_CHECKS_BLINDED| and |iterations|, respectively.
737 // If the latter is large enough, it will be the limiting factor with high
738 // probability and we won't leak information.
739 //
740 // Note this blinding does not impact most calls when picking primes because
741 // composites are rejected early. Only the two secret primes see extra work.
742
743 crypto_word_t uniform_iterations = 0;
744 // Using |constant_time_lt_w| seems to prevent the compiler from optimizing
745 // this into two jumps.
746 for (int i = 1; (i <= BN_PRIME_CHECKS_BLINDED) |
747 constant_time_lt_w(uniform_iterations, checks);
748 i++) {
749 // Step 4.1-4.2
750 int is_uniform;
751 if (!bn_rand_secret_range(b, &is_uniform, 2, miller_rabin.w1)) {
752 goto err;
753 }
754 uniform_iterations += is_uniform;
755
756 // Steps 4.3-4.5
757 int is_possibly_prime = 0;
758 if (!bn_miller_rabin_iteration(&miller_rabin, &is_possibly_prime, b, mont,
759 ctx)) {
760 goto err;
761 }
762
763 if (!is_possibly_prime) {
764 // Step 4.6. We did not see z = w-1 before z = 1, so w must be composite.
765 *out_is_probably_prime = 0;
766 ret = 1;
767 goto err;
768 }
769
770 // Step 4.7
771 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i - 1)) {
772 goto err;
773 }
774 }
775
776 assert(uniform_iterations >= (crypto_word_t)checks);
777 *out_is_probably_prime = 1;
778 ret = 1;
779
780 err:
781 BN_MONT_CTX_free(mont);
782 BN_CTX_end(ctx);
783 BN_CTX_free(new_ctx);
784 return ret;
785 }
786
BN_is_prime_ex(const BIGNUM * candidate,int checks,BN_CTX * ctx,BN_GENCB * cb)787 int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx,
788 BN_GENCB *cb) {
789 return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
790 }
791
BN_is_prime_fasttest_ex(const BIGNUM * a,int checks,BN_CTX * ctx,int do_trial_division,BN_GENCB * cb)792 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx,
793 int do_trial_division, BN_GENCB *cb) {
794 int is_probably_prime;
795 if (!BN_primality_test(&is_probably_prime, a, checks, ctx, do_trial_division,
796 cb)) {
797 return -1;
798 }
799 return is_probably_prime;
800 }
801
BN_enhanced_miller_rabin_primality_test(enum bn_primality_result_t * out_result,const BIGNUM * w,int checks,BN_CTX * ctx,BN_GENCB * cb)802 int BN_enhanced_miller_rabin_primality_test(
803 enum bn_primality_result_t *out_result, const BIGNUM *w, int checks,
804 BN_CTX *ctx, BN_GENCB *cb) {
805 // Enhanced Miller-Rabin is only valid on odd integers greater than 3.
806 if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) {
807 OPENSSL_PUT_ERROR(BN, BN_R_INVALID_INPUT);
808 return 0;
809 }
810
811 if (checks == BN_prime_checks_for_generation) {
812 checks = BN_prime_checks_for_size(BN_num_bits(w));
813 }
814
815 int ret = 0;
816 BN_MONT_CTX *mont = NULL;
817
818 BN_CTX_start(ctx);
819
820 BIGNUM *w1 = BN_CTX_get(ctx);
821 if (w1 == NULL ||
822 !BN_copy(w1, w) ||
823 !BN_sub_word(w1, 1)) {
824 goto err;
825 }
826
827 // Write w1 as m*2^a (Steps 1 and 2).
828 int a = 0;
829 while (!BN_is_bit_set(w1, a)) {
830 a++;
831 }
832 BIGNUM *m = BN_CTX_get(ctx);
833 if (m == NULL ||
834 !BN_rshift(m, w1, a)) {
835 goto err;
836 }
837
838 BIGNUM *b = BN_CTX_get(ctx);
839 BIGNUM *g = BN_CTX_get(ctx);
840 BIGNUM *z = BN_CTX_get(ctx);
841 BIGNUM *x = BN_CTX_get(ctx);
842 BIGNUM *x1 = BN_CTX_get(ctx);
843 if (b == NULL ||
844 g == NULL ||
845 z == NULL ||
846 x == NULL ||
847 x1 == NULL) {
848 goto err;
849 }
850
851 // Montgomery setup for computations mod w
852 mont = BN_MONT_CTX_new_for_modulus(w, ctx);
853 if (mont == NULL) {
854 goto err;
855 }
856
857 // The following loop performs in inner iteration of the Enhanced Miller-Rabin
858 // Primality test (Step 4).
859 for (int i = 1; i <= checks; i++) {
860 // Step 4.1-4.2
861 if (!BN_rand_range_ex(b, 2, w1)) {
862 goto err;
863 }
864
865 // Step 4.3-4.4
866 if (!BN_gcd(g, b, w, ctx)) {
867 goto err;
868 }
869 if (BN_cmp_word(g, 1) > 0) {
870 *out_result = bn_composite;
871 ret = 1;
872 goto err;
873 }
874
875 // Step 4.5
876 if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) {
877 goto err;
878 }
879
880 // Step 4.6
881 if (BN_is_one(z) || BN_cmp(z, w1) == 0) {
882 goto loop;
883 }
884
885 // Step 4.7
886 for (int j = 1; j < a; j++) {
887 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
888 goto err;
889 }
890 if (BN_cmp(z, w1) == 0) {
891 goto loop;
892 }
893 if (BN_is_one(z)) {
894 goto composite;
895 }
896 }
897
898 // Step 4.8-4.9
899 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
900 goto err;
901 }
902
903 // Step 4.10-4.11
904 if (!BN_is_one(z) && !BN_copy(x, z)) {
905 goto err;
906 }
907
908 composite:
909 // Step 4.12-4.14
910 if (!BN_copy(x1, x) ||
911 !BN_sub_word(x1, 1) ||
912 !BN_gcd(g, x1, w, ctx)) {
913 goto err;
914 }
915 if (BN_cmp_word(g, 1) > 0) {
916 *out_result = bn_composite;
917 } else {
918 *out_result = bn_non_prime_power_composite;
919 }
920
921 ret = 1;
922 goto err;
923
924 loop:
925 // Step 4.15
926 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i - 1)) {
927 goto err;
928 }
929 }
930
931 *out_result = bn_probably_prime;
932 ret = 1;
933
934 err:
935 BN_MONT_CTX_free(mont);
936 BN_CTX_end(ctx);
937
938 return ret;
939 }
940
probable_prime(BIGNUM * rnd,int bits)941 static int probable_prime(BIGNUM *rnd, int bits) {
942 do {
943 if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) {
944 return 0;
945 }
946 } while (bn_odd_number_is_obviously_composite(rnd));
947 return 1;
948 }
949
probable_prime_dh(BIGNUM * rnd,int bits,const BIGNUM * add,const BIGNUM * rem,BN_CTX * ctx)950 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
951 const BIGNUM *rem, BN_CTX *ctx) {
952 int ret = 0;
953 BIGNUM *t1;
954
955 BN_CTX_start(ctx);
956 if ((t1 = BN_CTX_get(ctx)) == NULL) {
957 goto err;
958 }
959
960 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
961 goto err;
962 }
963
964 // we need ((rnd-rem) % add) == 0
965
966 if (!BN_mod(t1, rnd, add, ctx)) {
967 goto err;
968 }
969 if (!BN_sub(rnd, rnd, t1)) {
970 goto err;
971 }
972 if (rem == NULL) {
973 if (!BN_add_word(rnd, 1)) {
974 goto err;
975 }
976 } else {
977 if (!BN_add(rnd, rnd, rem)) {
978 goto err;
979 }
980 }
981 // we now have a random number 'rand' to test.
982
983 const size_t num_primes = num_trial_division_primes(rnd);
984 loop:
985 for (size_t i = 1; i < num_primes; i++) {
986 // check that rnd is a prime
987 if (bn_mod_u16_consttime(rnd, kPrimes[i]) <= 1) {
988 if (!BN_add(rnd, rnd, add)) {
989 goto err;
990 }
991 goto loop;
992 }
993 }
994
995 ret = 1;
996
997 err:
998 BN_CTX_end(ctx);
999 return ret;
1000 }
1001
probable_prime_dh_safe(BIGNUM * p,int bits,const BIGNUM * padd,const BIGNUM * rem,BN_CTX * ctx)1002 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
1003 const BIGNUM *rem, BN_CTX *ctx) {
1004 int ret = 0;
1005 BIGNUM *t1, *qadd, *q;
1006
1007 bits--;
1008 BN_CTX_start(ctx);
1009 t1 = BN_CTX_get(ctx);
1010 q = BN_CTX_get(ctx);
1011 qadd = BN_CTX_get(ctx);
1012 if (qadd == NULL) {
1013 goto err;
1014 }
1015
1016 if (!BN_rshift1(qadd, padd)) {
1017 goto err;
1018 }
1019
1020 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
1021 goto err;
1022 }
1023
1024 // we need ((rnd-rem) % add) == 0
1025 if (!BN_mod(t1, q, qadd, ctx)) {
1026 goto err;
1027 }
1028
1029 if (!BN_sub(q, q, t1)) {
1030 goto err;
1031 }
1032
1033 if (rem == NULL) {
1034 if (!BN_add_word(q, 1)) {
1035 goto err;
1036 }
1037 } else {
1038 if (!BN_rshift1(t1, rem)) {
1039 goto err;
1040 }
1041 if (!BN_add(q, q, t1)) {
1042 goto err;
1043 }
1044 }
1045
1046 // we now have a random number 'rand' to test.
1047 if (!BN_lshift1(p, q)) {
1048 goto err;
1049 }
1050 if (!BN_add_word(p, 1)) {
1051 goto err;
1052 }
1053
1054 const size_t num_primes = num_trial_division_primes(p);
1055 loop:
1056 for (size_t i = 1; i < num_primes; i++) {
1057 // check that p and q are prime
1058 // check that for p and q
1059 // gcd(p-1,primes) == 1 (except for 2)
1060 if (bn_mod_u16_consttime(p, kPrimes[i]) == 0 ||
1061 bn_mod_u16_consttime(q, kPrimes[i]) == 0) {
1062 if (!BN_add(p, p, padd)) {
1063 goto err;
1064 }
1065 if (!BN_add(q, q, qadd)) {
1066 goto err;
1067 }
1068 goto loop;
1069 }
1070 }
1071
1072 ret = 1;
1073
1074 err:
1075 BN_CTX_end(ctx);
1076 return ret;
1077 }
1078