2 * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
5 * Licensed under the OpenSSL license (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
12 * According to NIST SP800-131A "Transitioning the use of cryptographic
13 * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
14 * allowed for signatures (Table 2) or key transport (Table 5). In the code
15 * below any attempt to generate 1024 bit RSA keys will result in an error (Note
16 * that digital signature verification can still use deprecated 1024 bit keys).
18 * Also see FIPS1402IG A.14
19 * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
20 * must be generated before the module generates the RSA primes p and q.
21 * Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
22 * 3072 bits only, the min/max total length of the auxiliary primes.
23 * When implementing the RSA signature generation algorithm
24 * with other approved RSA modulus sizes, the vendor shall use the limitations
25 * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
26 * FIPS 186-4 whose length does not exceed that of the implementation's RSA
27 * modulus. In particular, when generating the primes for the 4096-bit RSA
28 * modulus the limitations stated for the 3072-bit modulus shall apply.
31 #include <openssl/bn.h>
33 #include "crypto/bn.h"
36 * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
39 * nbits The key size in bits.
41 * The minimum size of the auxiliary primes or 0 if nbits is invalid.
43 static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
53 * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
54 * len(q1) + len(q2) for p,q Probable Primes".
57 * nbits The key size in bits.
59 * The maximum length or 0 if nbits is invalid.
61 static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
71 * Find the first odd integer that is a probable prime.
73 * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
76 * Xp1 The passed in starting point to find a probably prime.
77 * p1 The returned probable prime (first odd integer >= Xp1)
78 * ctx A BN_CTX object.
79 * cb An optional BIGNUM callback.
80 * Returns: 1 on success otherwise it returns 0.
82 static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
83 BIGNUM *p1, BN_CTX *ctx,
89 if (BN_copy(p1, Xp1) == NULL)
92 /* Find the first odd number >= Xp1 that is probably prime */
95 BN_GENCB_call(cb, 0, i);
96 /* MR test with trial division */
97 if (BN_check_prime(p1, ctx, cb))
99 /* Get next odd number */
100 if (!BN_add_word(p1, 2))
103 BN_GENCB_call(cb, 2, i);
110 * Generate a probable prime (p or q).
112 * See FIPS 186-4 B.3.6 (Steps 4 & 5)
115 * p The returned probable prime.
116 * Xpout An optionally returned random number used during generation of p.
117 * p1, p2 The returned auxiliary primes. If NULL they are not returned.
118 * Xp An optional passed in value (that is random number used during
120 * Xp1, Xp2 Optional passed in values that are normally generated
121 * internally. Used to find p1, p2.
122 * nlen The bit length of the modulus (the key size).
123 * e The public exponent.
124 * ctx A BN_CTX object.
125 * cb An optional BIGNUM callback.
126 * Returns: 1 on success otherwise it returns 0.
128 int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
129 BIGNUM *p1, BIGNUM *p2,
130 const BIGNUM *Xp, const BIGNUM *Xp1,
131 const BIGNUM *Xp2, int nlen,
132 const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
135 BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
138 if (p == NULL || Xpout == NULL)
143 p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
144 p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
145 Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
146 Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
147 if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
150 bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
154 /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
156 /* Set the top and bottom bits to make it odd and the correct size */
157 if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
161 /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
163 /* Set the top and bottom bits to make it odd and the correct size */
164 if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
169 /* (Steps 4.2/5.2) - find first auxiliary probable primes */
170 if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
171 || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
173 /* (Table B.1) auxiliary prime Max length check */
174 if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
175 bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
177 /* (Steps 4.3/5.3) - generate prime */
178 if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
182 /* Zeroize any internally generated values that are not returned */
196 * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
197 * prime numbers and the Chinese Remainder Theorem.
199 * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
200 * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
203 * Y The returned prime factor (private_prime_factor) of the modulus n.
204 * X The returned random number used during generation of the prime factor.
205 * Xin An optional passed in value for X used for testing purposes.
206 * r1 An auxiliary prime.
207 * r2 An auxiliary prime.
208 * nlen The desired length of n (the RSA modulus).
209 * e The public exponent.
210 * ctx A BN_CTX object.
211 * cb An optional BIGNUM callback object.
212 * Returns: 1 on success otherwise it returns 0.
214 * Y, X, r1, r2, e are not NULL.
216 int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
217 const BIGNUM *r1, const BIGNUM *r2, int nlen,
218 const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
222 int bits = nlen >> 1;
223 BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
228 tmp = BN_CTX_get(ctx);
229 r1r2x2 = BN_CTX_get(ctx);
230 y1 = BN_CTX_get(ctx);
231 r1x2 = BN_CTX_get(ctx);
235 if (Xin != NULL && BN_copy(X, Xin) == NULL)
238 if (!(BN_lshift1(r1x2, r1)
239 /* (Step 1) GCD(2r1, r2) = 1 */
240 && BN_gcd(tmp, r1x2, r2, ctx)
242 /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
243 && BN_mod_inverse(R, r2, r1x2, ctx)
244 && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
245 && BN_mod_inverse(tmp, r1x2, r2, ctx)
246 && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
248 /* Calculate 2r1r2 */
249 && BN_mul(r1r2x2, r1x2, r2, ctx)))
251 /* Make positive by adding the modulus */
252 if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
255 imax = 5 * bits; /* max = 5/2 * nbits */
259 * (Step 3) Choose Random X such that
260 * sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1.
262 * For the lower bound:
263 * sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2)
264 * where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE...
265 * so largest number will have B5... as the top byte
266 * Setting the top 2 bits gives 0xC0.
268 if (!BN_priv_rand_ex(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY,
272 /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
273 if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
279 if (BN_num_bits(Y) > bits) {
281 break; /* Randomly Generated X so Go back to Step 3 */
283 goto err; /* X is not random so it will always fail */
285 BN_GENCB_call(cb, 0, 2);
287 /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
288 if (BN_copy(y1, Y) == NULL
289 || !BN_sub_word(y1, 1)
290 || !BN_gcd(tmp, y1, e, ctx))
292 if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
295 if (++i >= imax || !BN_add(Y, Y, r1r2x2))
301 BN_GENCB_call(cb, 3, 0);