1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
|
/*
* Copyright 2018-2021 The OpenSSL Project Authors. All Rights Reserved.
* Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
*
* Licensed under the Apache License 2.0 (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
* in the file LICENSE in the source distribution or at
* https://www.openssl.org/source/license.html
*/
/*
* According to NIST SP800-131A "Transitioning the use of cryptographic
* algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
* allowed for signatures (Table 2) or key transport (Table 5). In the code
* below any attempt to generate 1024 bit RSA keys will result in an error (Note
* that digital signature verification can still use deprecated 1024 bit keys).
*
* FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
* must be generated before the module generates the RSA primes p and q.
* Table B.1 in FIPS 186-4 specifies RSA modulus lengths of 2048 and
* 3072 bits only, the min/max total length of the auxiliary primes.
* FIPS 186-5 Table A.1 includes an additional entry for 4096 which has been
* included here.
*/
#include <stdio.h>
#include <openssl/bn.h>
#include "bn_local.h"
#include "crypto/bn.h"
#include "internal/nelem.h"
#if BN_BITS2 == 64
# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
#else
# define BN_DEF(lo, hi) lo, hi
#endif
/* 1 / sqrt(2) * 2^256, rounded up */
static const BN_ULONG inv_sqrt_2_val[] = {
BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL),
BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL)
};
const BIGNUM ossl_bn_inv_sqrt_2 = {
(BN_ULONG *)inv_sqrt_2_val,
OSSL_NELEM(inv_sqrt_2_val),
OSSL_NELEM(inv_sqrt_2_val),
0,
BN_FLG_STATIC_DATA
};
/*
* Refer to FIPS 186-5 Table B.1 for minimum rounds of Miller Rabin
* required for generation of RSA aux primes (p1, p2, q1 and q2).
*/
static int bn_rsa_fips186_5_aux_prime_MR_rounds(int nbits)
{
if (nbits >= 4096)
return 44;
if (nbits >= 3072)
return 41;
if (nbits >= 2048)
return 38;
return 0; /* Error */
}
/*
* Refer to FIPS 186-5 Table B.1 for minimum rounds of Miller Rabin
* required for generation of RSA primes (p and q)
*/
static int bn_rsa_fips186_5_prime_MR_rounds(int nbits)
{
if (nbits >= 3072)
return 4;
if (nbits >= 2048)
return 5;
return 0; /* Error */
}
/*
* FIPS 186-5 Table A.1. "Min length of auxiliary primes p1, p2, q1, q2".
* (FIPS 186-5 has an entry for >= 4096 bits).
*
* Params:
* nbits The key size in bits.
* Returns:
* The minimum size of the auxiliary primes or 0 if nbits is invalid.
*/
static int bn_rsa_fips186_5_aux_prime_min_size(int nbits)
{
if (nbits >= 4096)
return 201;
if (nbits >= 3072)
return 171;
if (nbits >= 2048)
return 141;
return 0;
}
/*
* FIPS 186-5 Table A.1 "Max of len(p1) + len(p2) and
* len(q1) + len(q2) for p,q Probable Primes".
* (FIPS 186-5 has an entry for >= 4096 bits).
* Params:
* nbits The key size in bits.
* Returns:
* The maximum length or 0 if nbits is invalid.
*/
static int bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(int nbits)
{
if (nbits >= 4096)
return 2030;
if (nbits >= 3072)
return 1518;
if (nbits >= 2048)
return 1007;
return 0;
}
/*
* Find the first odd integer that is a probable prime.
*
* See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
*
* Params:
* Xp1 The passed in starting point to find a probably prime.
* p1 The returned probable prime (first odd integer >= Xp1)
* ctx A BN_CTX object.
* rounds The number of Miller Rabin rounds
* cb An optional BIGNUM callback.
* Returns: 1 on success otherwise it returns 0.
*/
static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
BIGNUM *p1, BN_CTX *ctx,
int rounds,
BN_GENCB *cb)
{
int ret = 0;
int i = 0;
int tmp = 0;
if (BN_copy(p1, Xp1) == NULL)
return 0;
BN_set_flags(p1, BN_FLG_CONSTTIME);
/* Find the first odd number >= Xp1 that is probably prime */
for (;;) {
i++;
BN_GENCB_call(cb, 0, i);
/* MR test with trial division */
tmp = ossl_bn_check_generated_prime(p1, rounds, ctx, cb);
if (tmp > 0)
break;
if (tmp < 0)
goto err;
/* Get next odd number */
if (!BN_add_word(p1, 2))
goto err;
}
BN_GENCB_call(cb, 2, i);
ret = 1;
err:
return ret;
}
/*
* Generate a probable prime (p or q).
*
* See FIPS 186-4 B.3.6 (Steps 4 & 5)
*
* Params:
* p The returned probable prime.
* Xpout An optionally returned random number used during generation of p.
* p1, p2 The returned auxiliary primes. If NULL they are not returned.
* Xp An optional passed in value (that is random number used during
* generation of p).
* Xp1, Xp2 Optional passed in values that are normally generated
* internally. Used to find p1, p2.
* nlen The bit length of the modulus (the key size).
* e The public exponent.
* ctx A BN_CTX object.
* cb An optional BIGNUM callback.
* Returns: 1 on success otherwise it returns 0.
*/
int ossl_bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
BIGNUM *p1, BIGNUM *p2,
const BIGNUM *Xp, const BIGNUM *Xp1,
const BIGNUM *Xp2, int nlen,
const BIGNUM *e, BN_CTX *ctx,
BN_GENCB *cb)
{
int ret = 0;
BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
int bitlen, rounds;
if (p == NULL || Xpout == NULL)
return 0;
BN_CTX_start(ctx);
p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
goto err;
bitlen = bn_rsa_fips186_5_aux_prime_min_size(nlen);
if (bitlen == 0)
goto err;
rounds = bn_rsa_fips186_5_aux_prime_MR_rounds(nlen);
/* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
if (Xp1 == NULL) {
/* Set the top and bottom bits to make it odd and the correct size */
if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
0, ctx))
goto err;
}
/* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
if (Xp2 == NULL) {
/* Set the top and bottom bits to make it odd and the correct size */
if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
0, ctx))
goto err;
}
/* (Steps 4.2/5.2) - find first auxiliary probable primes */
if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, rounds, cb)
|| !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, rounds, cb))
goto err;
/* (Table B.1) auxiliary prime Max length check */
if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(nlen))
goto err;
/* (Steps 4.3/5.3) - generate prime */
if (!ossl_bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e,
ctx, cb))
goto err;
ret = 1;
err:
/* Zeroize any internally generated values that are not returned */
if (p1 == NULL)
BN_clear(p1i);
if (p2 == NULL)
BN_clear(p2i);
if (Xp1 == NULL)
BN_clear(Xp1i);
if (Xp2 == NULL)
BN_clear(Xp2i);
BN_CTX_end(ctx);
return ret;
}
/*
* Constructs a probable prime (a candidate for p or q) using 2 auxiliary
* prime numbers and the Chinese Remainder Theorem.
*
* See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
* Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
*
* Params:
* Y The returned prime factor (private_prime_factor) of the modulus n.
* X The returned random number used during generation of the prime factor.
* Xin An optional passed in value for X used for testing purposes.
* r1 An auxiliary prime.
* r2 An auxiliary prime.
* nlen The desired length of n (the RSA modulus).
* e The public exponent.
* ctx A BN_CTX object.
* cb An optional BIGNUM callback object.
* Returns: 1 on success otherwise it returns 0.
* Assumptions:
* Y, X, r1, r2, e are not NULL.
*/
int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
const BIGNUM *r1, const BIGNUM *r2,
int nlen, const BIGNUM *e,
BN_CTX *ctx, BN_GENCB *cb)
{
int ret = 0;
int i, imax, rounds;
int bits = nlen >>
|