Coverage Report

Created: 2024-11-21 07:03

/src/boringssl/crypto/fipsmodule/bn/prime.c.inc
Line
Count
Source (jump to first uncovered line)
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
260
208
static int BN_prime_checks_for_size(int bits) {
261
208
  if (bits >= 3747) {
262
0
    return 3;
263
0
  }
264
208
  if (bits >= 1345) {
265
11
    return 4;
266
11
  }
267
197
  if (bits >= 476) {
268
19
    return 5;
269
19
  }
270
178
  if (bits >= 400) {
271
58
    return 6;
272
58
  }
273
120
  if (bits >= 347) {
274
0
    return 7;
275
0
  }
276
120
  if (bits >= 308) {
277
23
    return 8;
278
23
  }
279
97
  if (bits >= 55) {
280
91
    return 27;
281
91
  }
282
6
  return 34;
283
97
}
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.
288
2.54k
static size_t num_trial_division_primes(const BIGNUM *n) {
289
2.54k
  if (n->width * BN_BITS2 > 1024) {
290
0
    return OPENSSL_ARRAY_SIZE(kPrimes);
291
0
  }
292
2.54k
  return OPENSSL_ARRAY_SIZE(kPrimes) / 2;
293
2.54k
}
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
4.01k
#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
362
0
BN_GENCB *BN_GENCB_new(void) { return OPENSSL_zalloc(sizeof(BN_GENCB)); }
363
364
0
void BN_GENCB_free(BN_GENCB *callback) { OPENSSL_free(callback); }
365
366
void BN_GENCB_set(BN_GENCB *callback,
367
                  int (*f)(int event, int n, struct bn_gencb_st *),
368
0
                  void *arg) {
369
0
  callback->callback = f;
370
0
  callback->arg = arg;
371
0
}
372
373
6.36k
int BN_GENCB_call(BN_GENCB *callback, int event, int n) {
374
6.36k
  if (!callback) {
375
6.36k
    return 1;
376
6.36k
  }
377
378
0
  return callback->callback(event, n, callback);
379
6.36k
}
380
381
0
void *BN_GENCB_get_arg(const BN_GENCB *callback) { return callback->arg; }
382
383
int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
384
0
                         const BIGNUM *rem, BN_GENCB *cb) {
385
0
  BIGNUM *t;
386
0
  int found = 0;
387
0
  int i, j, c1 = 0;
388
0
  BN_CTX *ctx;
389
0
  int checks = BN_prime_checks_for_size(bits);
390
391
0
  if (bits < 2) {
392
    // There are no prime numbers this small.
393
0
    OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
394
0
    return 0;
395
0
  } else if (bits == 2 && safe) {
396
    // The smallest safe prime (7) is three bits.
397
0
    OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
398
0
    return 0;
399
0
  }
400
401
0
  ctx = BN_CTX_new();
402
0
  if (ctx == NULL) {
403
0
    goto err;
404
0
  }
405
0
  BN_CTX_start(ctx);
406
0
  t = BN_CTX_get(ctx);
407
0
  if (!t) {
408
0
    goto err;
409
0
  }
410
411
0
loop:
412
  // make a random number and set the top and bottom bits
413
0
  if (add == NULL) {
414
0
    if (!probable_prime(ret, bits)) {
415
0
      goto err;
416
0
    }
417
0
  } else {
418
0
    if (safe) {
419
0
      if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) {
420
0
        goto err;
421
0
      }
422
0
    } else {
423
0
      if (!probable_prime_dh(ret, bits, add, rem, ctx)) {
424
0
        goto err;
425
0
      }
426
0
    }
427
0
  }
428
429
0
  if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) {
430
    // aborted
431
0
    goto err;
432
0
  }
433
434
0
  if (!safe) {
435
0
    i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
436
0
    if (i == -1) {
437
0
      goto err;
438
0
    } else if (i == 0) {
439
0
      goto loop;
440
0
    }
441
0
  } else {
442
    // for "safe prime" generation, check that (p-1)/2 is prime. Since a prime
443
    // is odd, We just need to divide by 2
444
0
    if (!BN_rshift1(t, ret)) {
445
0
      goto err;
446
0
    }
447
448
    // Interleave |ret| and |t|'s primality tests to avoid paying the full
449
    // iteration count on |ret| only to quickly discover |t| is composite.
450
    //
451
    // TODO(davidben): This doesn't quite work because an iteration count of 1
452
    // still runs the blinding mechanism.
453
0
    for (i = 0; i < checks; i++) {
454
0
      j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL);
455
0
      if (j == -1) {
456
0
        goto err;
457
0
      } else if (j == 0) {
458
0
        goto loop;
459
0
      }
460
461
0
      j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL);
462
0
      if (j == -1) {
463
0
        goto err;
464
0
      } else if (j == 0) {
465
0
        goto loop;
466
0
      }
467
468
0
      if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i)) {
469
0
        goto err;
470
0
      }
471
      // We have a safe prime test pass
472
0
    }
473
0
  }
474
475
  // we have a prime :-)
476
0
  found = 1;
477
478
0
err:
479
0
  if (ctx != NULL) {
480
0
    BN_CTX_end(ctx);
481
0
    BN_CTX_free(ctx);
482
0
  }
483
484
0
  return found;
485
0
}
486
487
2.54k
static int bn_trial_division(uint16_t *out, const BIGNUM *bn) {
488
2.54k
  const size_t num_primes = num_trial_division_primes(bn);
489
215k
  for (size_t i = 1; i < num_primes; i++) {
490
    // During RSA key generation, |bn| may be secret, but only if |bn| was
491
    // prime, so it is safe to leak failed trial divisions.
492
215k
    if (constant_time_declassify_int(bn_mod_u16_consttime(bn, kPrimes[i]) ==
493
215k
                                     0)) {
494
2.20k
      *out = kPrimes[i];
495
2.20k
      return 1;
496
2.20k
    }
497
215k
  }
498
340
  return 0;
499
2.54k
}
500
501
0
int bn_odd_number_is_obviously_composite(const BIGNUM *bn) {
502
0
  uint16_t prime;
503
0
  return bn_trial_division(&prime, bn) && !BN_is_word(bn, prime);
504
0
}
505
506
int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin, const BN_MONT_CTX *mont,
507
548
                         BN_CTX *ctx) {
508
  // This function corresponds to steps 1 through 3 of FIPS 186-4, C.3.1.
509
548
  const BIGNUM *w = &mont->N;
510
  // Note we do not call |BN_CTX_start| in this function. We intentionally
511
  // allocate values in the containing scope so they outlive this function.
512
548
  miller_rabin->w1 = BN_CTX_get(ctx);
513
548
  miller_rabin->m = BN_CTX_get(ctx);
514
548
  miller_rabin->one_mont = BN_CTX_get(ctx);
515
548
  miller_rabin->w1_mont = BN_CTX_get(ctx);
516
548
  if (miller_rabin->w1 == NULL ||
517
548
      miller_rabin->m == NULL ||
518
548
      miller_rabin->one_mont == NULL ||
519
548
      miller_rabin->w1_mont == NULL) {
520
0
    return 0;
521
0
  }
522
523
  // See FIPS 186-4, C.3.1, steps 1 through 3.
524
548
  if (!bn_usub_consttime(miller_rabin->w1, w, BN_value_one())) {
525
0
    return 0;
526
0
  }
527
548
  miller_rabin->a = BN_count_low_zero_bits(miller_rabin->w1);
528
548
  if (!bn_rshift_secret_shift(miller_rabin->m, miller_rabin->w1,
529
548
                              miller_rabin->a, ctx)) {
530
0
    return 0;
531
0
  }
532
548
  miller_rabin->w_bits = BN_num_bits(w);
533
534
  // Precompute some values in Montgomery form.
535
548
  if (!bn_one_to_montgomery(miller_rabin->one_mont, mont, ctx) ||
536
      // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
537
      // with a subtraction. (|one_mont| cannot be zero.)
538
548
      !bn_usub_consttime(miller_rabin->w1_mont, w, miller_rabin->one_mont)) {
539
0
    return 0;
540
0
  }
541
542
548
  return 1;
543
548
}
544
545
int bn_miller_rabin_iteration(const BN_MILLER_RABIN *miller_rabin,
546
                              int *out_is_possibly_prime, const BIGNUM *b,
547
3.93k
                              const BN_MONT_CTX *mont, BN_CTX *ctx) {
548
  // This function corresponds to steps 4.3 through 4.5 of FIPS 186-4, C.3.1.
549
3.93k
  int ret = 0;
550
3.93k
  BN_CTX_start(ctx);
551
552
  // Step 4.3. We use Montgomery-encoding for better performance and to avoid
553
  // timing leaks.
554
3.93k
  const BIGNUM *w = &mont->N;
555
3.93k
  BIGNUM *z = BN_CTX_get(ctx);
556
3.93k
  if (z == NULL ||
557
3.93k
      !BN_mod_exp_mont_consttime(z, b, miller_rabin->m, w, ctx, mont) ||
558
3.93k
      !BN_to_montgomery(z, z, mont, ctx)) {
559
0
    goto err;
560
0
  }
561
562
  // is_possibly_prime is all ones if we have determined |b| is not a composite
563
  // witness for |w|. This is equivalent to going to step 4.7 in the original
564
  // algorithm. To avoid timing leaks, we run the algorithm to the end for prime
565
  // inputs.
566
3.93k
  crypto_word_t is_possibly_prime = 0;
567
568
  // Step 4.4. If z = 1 or z = w-1, b is not a composite witness and w is still
569
  // possibly prime.
570
3.93k
  is_possibly_prime = BN_equal_consttime(z, miller_rabin->one_mont) |
571
3.93k
                      BN_equal_consttime(z, miller_rabin->w1_mont);
572
3.93k
  is_possibly_prime = 0 - is_possibly_prime;  // Make it all zeros or all ones.
573
574
  // Step 4.5.
575
  //
576
  // To avoid leaking |a|, we run the loop to |w_bits| and mask off all
577
  // iterations once |j| = |a|.
578
821k
  for (int j = 1; j < miller_rabin->w_bits; j++) {
579
817k
    if (constant_time_declassify_w(constant_time_eq_int(j, miller_rabin->a) &
580
817k
                                   ~is_possibly_prime)) {
581
      // If the loop is done and we haven't seen z = 1 or z = w-1 yet, the
582
      // value is composite and we can break in variable time.
583
468
      break;
584
468
    }
585
586
    // Step 4.5.1.
587
817k
    if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
588
0
      goto err;
589
0
    }
590
591
    // Step 4.5.2. If z = w-1 and the loop is not done, this is not a composite
592
    // witness.
593
817k
    crypto_word_t z_is_w1_mont = BN_equal_consttime(z, miller_rabin->w1_mont);
594
817k
    z_is_w1_mont = 0 - z_is_w1_mont;    // Make it all zeros or all ones.
595
817k
    is_possibly_prime |= z_is_w1_mont;  // Go to step 4.7 if |z_is_w1_mont|.
596
597
    // Step 4.5.3. If z = 1 and the loop is not done, the previous value of z
598
    // was not -1. There are no non-trivial square roots of 1 modulo a prime, so
599
    // w is composite and we may exit in variable time.
600
817k
    if (constant_time_declassify_w(
601
817k
            BN_equal_consttime(z, miller_rabin->one_mont) &
602
817k
            ~is_possibly_prime)) {
603
0
      break;
604
0
    }
605
817k
  }
606
607
3.93k
  *out_is_possibly_prime = constant_time_declassify_w(is_possibly_prime) & 1;
608
3.93k
  ret = 1;
609
610
3.93k
err:
611
3.93k
  BN_CTX_end(ctx);
612
3.93k
  return ret;
613
3.93k
}
614
615
int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w, int checks,
616
2.81k
                      BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) {
617
  // This function's secrecy and performance requirements come from RSA key
618
  // generation. We generate RSA keys by selecting two large, secret primes with
619
  // rejection sampling.
620
  //
621
  // We thus treat |w| as secret if turns out to be a large prime. However, if
622
  // |w| is composite, we treat this and |w| itself as public. (Conversely, if
623
  // |w| is prime, that it is prime is public. Only the value is secret.) This
624
  // is fine for RSA key generation, but note it is important that we use
625
  // rejection sampling, with each candidate prime chosen independently. This
626
  // would not work for, e.g., an algorithm which looked for primes in
627
  // consecutive integers. These assumptions allow us to discard composites
628
  // quickly. We additionally treat |w| as public when it is a small prime to
629
  // simplify trial decryption and some edge cases.
630
  //
631
  // One RSA key generation will call this function on exactly two primes and
632
  // many more composites. The overall cost is a combination of several factors:
633
  //
634
  // 1. Checking if |w| is divisible by a small prime is much faster than
635
  //    learning it is composite by Miller-Rabin (see below for details on that
636
  //    cost). Trial division by p saves 1/p of Miller-Rabin calls, so this is
637
  //    worthwhile until p exceeds the ratio of the two costs.
638
  //
639
  // 2. For a random (i.e. non-adversarial) candidate large prime and candidate
640
  //    witness, the probability of false witness is very low. (This is why FIPS
641
  //    186-4 only requires a few iterations.) Thus composites not discarded by
642
  //    trial decryption, in practice, cost one Miller-Rabin iteration. Only the
643
  //    two actual primes cost the full iteration count.
644
  //
645
  // 3. A Miller-Rabin iteration is a modular exponentiation plus |a| additional
646
  //    modular squares, where |a| is the number of factors of two in |w-1|. |a|
647
  //    is likely small (the distribution falls exponentially), but it is also
648
  //    potentially secret, so we loop up to its log(w) upper bound when |w| is
649
  //    prime. When |w| is composite, we break early, so only two calls pay this
650
  //    cost. (Note that all calls pay the modular exponentiation which is,
651
  //    itself, log(w) modular multiplications and squares.)
652
  //
653
  // 4. While there are only two prime calls, they multiplicatively pay the full
654
  //    costs of (2) and (3).
655
  //
656
  // 5. After the primes are chosen, RSA keys derive some values from the
657
  //    primes, but this cost is negligible in comparison.
658
659
2.81k
  *out_is_probably_prime = 0;
660
661
2.81k
  if (BN_cmp(w, BN_value_one()) <= 0) {
662
21
    return 1;
663
21
  }
664
665
2.78k
  if (!BN_is_odd(w)) {
666
    // The only even prime is two.
667
36
    *out_is_probably_prime = BN_is_word(w, 2);
668
36
    return 1;
669
36
  }
670
671
  // Miller-Rabin does not work for three.
672
2.75k
  if (BN_is_word(w, 3)) {
673
0
    *out_is_probably_prime = 1;
674
0
    return 1;
675
0
  }
676
677
2.75k
  if (do_trial_division) {
678
    // Perform additional trial division checks to discard small primes.
679
2.54k
    uint16_t prime;
680
2.54k
    if (bn_trial_division(&prime, w)) {
681
2.20k
      *out_is_probably_prime = BN_is_word(w, prime);
682
2.20k
      return 1;
683
2.20k
    }
684
340
    if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, -1)) {
685
0
      return 0;
686
0
    }
687
340
  }
688
689
548
  if (checks == BN_prime_checks_for_generation) {
690
208
    checks = BN_prime_checks_for_size(BN_num_bits(w));
691
208
  }
692
693
548
  BN_CTX *new_ctx = NULL;
694
548
  if (ctx == NULL) {
695
208
    new_ctx = BN_CTX_new();
696
208
    if (new_ctx == NULL) {
697
0
      return 0;
698
0
    }
699
208
    ctx = new_ctx;
700
208
  }
701
702
  // See C.3.1 from FIPS 186-4.
703
548
  int ret = 0;
704
548
  BN_CTX_start(ctx);
705
548
  BIGNUM *b = BN_CTX_get(ctx);
706
548
  BN_MONT_CTX *mont = BN_MONT_CTX_new_consttime(w, ctx);
707
548
  BN_MILLER_RABIN miller_rabin;
708
548
  if (b == NULL || mont == NULL ||
709
      // Steps 1-3.
710
548
      !bn_miller_rabin_init(&miller_rabin, mont, ctx)) {
711
0
    goto err;
712
0
  }
713
714
  // The following loop performs in inner iteration of the Miller-Rabin
715
  // Primality test (Step 4).
716
  //
717
  // The algorithm as specified in FIPS 186-4 leaks information on |w|, the RSA
718
  // private key. Instead, we run through each iteration unconditionally,
719
  // performing modular multiplications, masking off any effects to behave
720
  // equivalently to the specified algorithm.
721
  //
722
  // We also blind the number of values of |b| we try. Steps 4.1–4.2 say to
723
  // discard out-of-range values. To avoid leaking information on |w|, we use
724
  // |bn_rand_secret_range| which, rather than discarding bad values, adjusts
725
  // them to be in range. Though not uniformly selected, these adjusted values
726
  // are still usable as Miller-Rabin checks.
727
  //
728
  // Miller-Rabin is already probabilistic, so we could reach the desired
729
  // confidence levels by just suitably increasing the iteration count. However,
730
  // to align with FIPS 186-4, we use a more pessimal analysis: we do not count
731
  // the non-uniform values towards the iteration count. As a result, this
732
  // function is more complex and has more timing risk than necessary.
733
  //
734
  // We count both total iterations and uniform ones and iterate until we've
735
  // reached at least |BN_PRIME_CHECKS_BLINDED| and |iterations|, respectively.
736
  // If the latter is large enough, it will be the limiting factor with high
737
  // probability and we won't leak information.
738
  //
739
  // Note this blinding does not impact most calls when picking primes because
740
  // composites are rejected early. Only the two secret primes see extra work.
741
742
548
  crypto_word_t uniform_iterations = 0;
743
  // Using |constant_time_lt_w| seems to prevent the compiler from optimizing
744
  // this into two jumps.
745
4.01k
  for (int i = 1; constant_time_declassify_w(
746
4.01k
           (i <= BN_PRIME_CHECKS_BLINDED) |
747
4.01k
           constant_time_lt_w(uniform_iterations, checks));
748
3.93k
       i++) {
749
    // Step 4.1-4.2
750
3.93k
    int is_uniform;
751
3.93k
    if (!bn_rand_secret_range(b, &is_uniform, 2, miller_rabin.w1)) {
752
0
        goto err;
753
0
    }
754
3.93k
    uniform_iterations += is_uniform;
755
756
    // Steps 4.3-4.5
757
3.93k
    int is_possibly_prime = 0;
758
3.93k
    if (!bn_miller_rabin_iteration(&miller_rabin, &is_possibly_prime, b, mont,
759
3.93k
                                   ctx)) {
760
0
      goto err;
761
0
    }
762
763
3.93k
    if (!is_possibly_prime) {
764
      // Step 4.6. We did not see z = w-1 before z = 1, so w must be composite.
765
468
      *out_is_probably_prime = 0;
766
468
      ret = 1;
767
468
      goto err;
768
468
    }
769
770
    // Step 4.7
771
3.46k
    if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i - 1)) {
772
0
      goto err;
773
0
    }
774
3.46k
  }
775
776
80
  declassify_assert(uniform_iterations >= (crypto_word_t)checks);
777
80
  *out_is_probably_prime = 1;
778
80
  ret = 1;
779
780
548
err:
781
548
  BN_MONT_CTX_free(mont);
782
548
  BN_CTX_end(ctx);
783
548
  BN_CTX_free(new_ctx);
784
548
  return ret;
785
80
}
786
787
int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx,
788
265
                   BN_GENCB *cb) {
789
265
  return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
790
265
}
791
792
int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx,
793
2.81k
                            int do_trial_division, BN_GENCB *cb) {
794
2.81k
  int is_probably_prime;
795
2.81k
  if (!BN_primality_test(&is_probably_prime, a, checks, ctx, do_trial_division,
796
2.81k
                         cb)) {
797
0
    return -1;
798
0
  }
799
2.81k
  return is_probably_prime;
800
2.81k
}
801
802
int BN_enhanced_miller_rabin_primality_test(
803
    enum bn_primality_result_t *out_result, const BIGNUM *w, int checks,
804
0
    BN_CTX *ctx, BN_GENCB *cb) {
805
  // Enhanced Miller-Rabin is only valid on odd integers greater than 3.
806
0
  if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) {
807
0
    OPENSSL_PUT_ERROR(BN, BN_R_INVALID_INPUT);
808
0
    return 0;
809
0
  }
810
811
0
  if (checks == BN_prime_checks_for_generation) {
812
0
    checks = BN_prime_checks_for_size(BN_num_bits(w));
813
0
  }
814
815
0
  int ret = 0;
816
0
  BN_MONT_CTX *mont = NULL;
817
818
0
  BN_CTX_start(ctx);
819
820
0
  BIGNUM *w1 = BN_CTX_get(ctx);
821
0
  if (w1 == NULL ||
822
0
      !BN_copy(w1, w) ||
823
0
      !BN_sub_word(w1, 1)) {
824
0
    goto err;
825
0
  }
826
827
  // Write w1 as m*2^a (Steps 1 and 2).
828
0
  int a = 0;
829
0
  while (!BN_is_bit_set(w1, a)) {
830
0
    a++;
831
0
  }
832
0
  BIGNUM *m = BN_CTX_get(ctx);
833
0
  if (m == NULL ||
834
0
      !BN_rshift(m, w1, a)) {
835
0
    goto err;
836
0
  }
837
838
0
  BIGNUM *b = BN_CTX_get(ctx);
839
0
  BIGNUM *g = BN_CTX_get(ctx);
840
0
  BIGNUM *z = BN_CTX_get(ctx);
841
0
  BIGNUM *x = BN_CTX_get(ctx);
842
0
  BIGNUM *x1 = BN_CTX_get(ctx);
843
0
  if (b == NULL ||
844
0
      g == NULL ||
845
0
      z == NULL ||
846
0
      x == NULL ||
847
0
      x1 == NULL) {
848
0
    goto err;
849
0
  }
850
851
  // Montgomery setup for computations mod w
852
0
  mont = BN_MONT_CTX_new_for_modulus(w, ctx);
853
0
  if (mont == NULL) {
854
0
    goto err;
855
0
  }
856
857
  // The following loop performs in inner iteration of the Enhanced Miller-Rabin
858
  // Primality test (Step 4).
859
0
  for (int i = 1; i <= checks; i++) {
860
    // Step 4.1-4.2
861
0
    if (!BN_rand_range_ex(b, 2, w1)) {
862
0
      goto err;
863
0
    }
864
865
    // Step 4.3-4.4
866
0
    if (!BN_gcd(g, b, w, ctx)) {
867
0
      goto err;
868
0
    }
869
0
    if (BN_cmp_word(g, 1) > 0) {
870
0
      *out_result = bn_composite;
871
0
      ret = 1;
872
0
      goto err;
873
0
    }
874
875
    // Step 4.5
876
0
    if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) {
877
0
      goto err;
878
0
    }
879
880
    // Step 4.6
881
0
    if (BN_is_one(z) || BN_cmp(z, w1) == 0) {
882
0
      goto loop;
883
0
    }
884
885
    // Step 4.7
886
0
    for (int j = 1; j < a; j++) {
887
0
      if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
888
0
        goto err;
889
0
      }
890
0
      if (BN_cmp(z, w1) == 0) {
891
0
        goto loop;
892
0
      }
893
0
      if (BN_is_one(z)) {
894
0
        goto composite;
895
0
      }
896
0
    }
897
898
    // Step 4.8-4.9
899
0
    if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
900
0
      goto err;
901
0
    }
902
903
    // Step 4.10-4.11
904
0
    if (!BN_is_one(z) && !BN_copy(x, z)) {
905
0
      goto err;
906
0
    }
907
908
0
 composite:
909
    // Step 4.12-4.14
910
0
    if (!BN_copy(x1, x) ||
911
0
        !BN_sub_word(x1, 1) ||
912
0
        !BN_gcd(g, x1, w, ctx)) {
913
0
      goto err;
914
0
    }
915
0
    if (BN_cmp_word(g, 1) > 0) {
916
0
      *out_result = bn_composite;
917
0
    } else {
918
0
      *out_result = bn_non_prime_power_composite;
919
0
    }
920
921
0
    ret = 1;
922
0
    goto err;
923
924
0
 loop:
925
    // Step 4.15
926
0
    if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i - 1)) {
927
0
      goto err;
928
0
    }
929
0
  }
930
931
0
  *out_result = bn_probably_prime;
932
0
  ret = 1;
933
934
0
err:
935
0
  BN_MONT_CTX_free(mont);
936
0
  BN_CTX_end(ctx);
937
938
0
  return ret;
939
0
}
940
941
0
static int probable_prime(BIGNUM *rnd, int bits) {
942
0
  do {
943
0
    if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) {
944
0
      return 0;
945
0
    }
946
0
  } while (bn_odd_number_is_obviously_composite(rnd));
947
0
  return 1;
948
0
}
949
950
static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
951
0
                             const BIGNUM *rem, BN_CTX *ctx) {
952
0
  int ret = 0;
953
0
  BIGNUM *t1;
954
955
0
  BN_CTX_start(ctx);
956
0
  if ((t1 = BN_CTX_get(ctx)) == NULL) {
957
0
    goto err;
958
0
  }
959
960
0
  if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
961
0
    goto err;
962
0
  }
963
964
  // we need ((rnd-rem) % add) == 0
965
966
0
  if (!BN_mod(t1, rnd, add, ctx)) {
967
0
    goto err;
968
0
  }
969
0
  if (!BN_sub(rnd, rnd, t1)) {
970
0
    goto err;
971
0
  }
972
0
  if (rem == NULL) {
973
0
    if (!BN_add_word(rnd, 1)) {
974
0
      goto err;
975
0
    }
976
0
  } else {
977
0
    if (!BN_add(rnd, rnd, rem)) {
978
0
      goto err;
979
0
    }
980
0
  }
981
  // we now have a random number 'rand' to test.
982
983
0
  const size_t num_primes = num_trial_division_primes(rnd);
984
0
loop:
985
0
  for (size_t i = 1; i < num_primes; i++) {
986
    // check that rnd is a prime
987
0
    if (bn_mod_u16_consttime(rnd, kPrimes[i]) <= 1) {
988
0
      if (!BN_add(rnd, rnd, add)) {
989
0
        goto err;
990
0
      }
991
0
      goto loop;
992
0
    }
993
0
  }
994
995
0
  ret = 1;
996
997
0
err:
998
0
  BN_CTX_end(ctx);
999
0
  return ret;
1000
0
}
1001
1002
static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
1003
0
                                  const BIGNUM *rem, BN_CTX *ctx) {
1004
0
  int ret = 0;
1005
0
  BIGNUM *t1, *qadd, *q;
1006
1007
0
  bits--;
1008
0
  BN_CTX_start(ctx);
1009
0
  t1 = BN_CTX_get(ctx);
1010
0
  q = BN_CTX_get(ctx);
1011
0
  qadd = BN_CTX_get(ctx);
1012
0
  if (qadd == NULL) {
1013
0
    goto err;
1014
0
  }
1015
1016
0
  if (!BN_rshift1(qadd, padd)) {
1017
0
    goto err;
1018
0
  }
1019
1020
0
  if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
1021
0
    goto err;
1022
0
  }
1023
1024
  // we need ((rnd-rem) % add) == 0
1025
0
  if (!BN_mod(t1, q, qadd, ctx)) {
1026
0
    goto err;
1027
0
  }
1028
1029
0
  if (!BN_sub(q, q, t1)) {
1030
0
    goto err;
1031
0
  }
1032
1033
0
  if (rem == NULL) {
1034
0
    if (!BN_add_word(q, 1)) {
1035
0
      goto err;
1036
0
    }
1037
0
  } else {
1038
0
    if (!BN_rshift1(t1, rem)) {
1039
0
      goto err;
1040
0
    }
1041
0
    if (!BN_add(q, q, t1)) {
1042
0
      goto err;
1043
0
    }
1044
0
  }
1045
1046
  // we now have a random number 'rand' to test.
1047
0
  if (!BN_lshift1(p, q)) {
1048
0
    goto err;
1049
0
  }
1050
0
  if (!BN_add_word(p, 1)) {
1051
0
    goto err;
1052
0
  }
1053
1054
0
  const size_t num_primes = num_trial_division_primes(p);
1055
0
loop:
1056
0
  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
0
    if (bn_mod_u16_consttime(p, kPrimes[i]) == 0 ||
1061
0
        bn_mod_u16_consttime(q, kPrimes[i]) == 0) {
1062
0
      if (!BN_add(p, p, padd)) {
1063
0
        goto err;
1064
0
      }
1065
0
      if (!BN_add(q, q, qadd)) {
1066
0
        goto err;
1067
0
      }
1068
0
      goto loop;
1069
0
    }
1070
0
  }
1071
1072
0
  ret = 1;
1073
1074
0
err:
1075
0
  BN_CTX_end(ctx);
1076
0
  return ret;
1077
0
}