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