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
11 #include <openssl/err.h>
12 #include <openssl/bn.h>
13 #include "internal/bn_int.h"
16 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
17 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
18 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
21 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
22 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
26 * rsa Object used to store primes p & q.
27 * p1, p2 The returned auxiliary primes for p. If NULL they are not returned.
28 * Xpout An optionally returned random number used during generation of p.
29 * Xp An optional passed in value (that is random number used during
31 * Xp1, Xp2 Optionally passed in randomly generated numbers from which
32 * auxiliary primes p1 & p2 are calculated. If NULL these values
33 * are generated internally.
34 * q1, q2 The returned auxiliary primes for q. If NULL they are not returned.
35 * Xqout An optionally returned random number used during generation of q.
36 * Xq An optional passed in value (that is random number used during
38 * Xq1, Xq2 Optionally passed in randomly generated numbers from which
39 * auxiliary primes q1 & q2 are calculated. If NULL these values
40 * are generated internally.
41 * nbits The key size in bits (The size of the modulus n).
42 * e The public exponent.
43 * ctx A BN_CTX object.
44 * cb An optional BIGNUM callback.
45 * Returns: 1 if successful, or 0 otherwise.
47 * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
48 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
49 * (Required for CAVS testing).
51 int rsa_fips186_4_gen_prob_primes(RSA
*rsa
, BIGNUM
*p1
, BIGNUM
*p2
,
52 BIGNUM
*Xpout
, const BIGNUM
*Xp
,
53 const BIGNUM
*Xp1
, const BIGNUM
*Xp2
,
54 BIGNUM
*q1
, BIGNUM
*q2
, BIGNUM
*Xqout
,
55 const BIGNUM
*Xq
, const BIGNUM
*Xq1
,
56 const BIGNUM
*Xq2
, int nbits
,
57 const BIGNUM
*e
, BN_CTX
*ctx
, BN_GENCB
*cb
)
60 BIGNUM
*Xpo
= NULL
, *Xqo
= NULL
, *tmp
= NULL
;
62 /* (Step 1) Check key length
63 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
64 * Signature Generation and Key Agree/Transport.
66 if (nbits
< RSA_FIPS1864_MIN_KEYGEN_KEYSIZE
) {
67 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES
, RSA_R_INVALID_KEY_LENGTH
);
71 if (!rsa_check_public_exponent(e
)) {
72 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES
,
73 RSA_R_PUB_EXPONENT_OUT_OF_RANGE
);
77 /* (Step 3) Determine strength and check rand generator strength is ok -
78 * this step is redundant because the generator always returns a higher
79 * strength than is required.
83 tmp
= BN_CTX_get(ctx
);
84 Xpo
= (Xpout
!= NULL
) ? Xpout
: BN_CTX_get(ctx
);
85 Xqo
= (Xqout
!= NULL
) ? Xqout
: BN_CTX_get(ctx
);
86 if (tmp
== NULL
|| Xpo
== NULL
|| Xqo
== NULL
)
90 rsa
->p
= BN_secure_new();
92 rsa
->q
= BN_secure_new();
93 if (rsa
->p
== NULL
|| rsa
->q
== NULL
)
96 /* (Step 4) Generate p, Xp */
97 if (!bn_rsa_fips186_4_gen_prob_primes(rsa
->p
, Xpo
, p1
, p2
, Xp
, Xp1
, Xp2
,
101 /* (Step 5) Generate q, Xq*/
102 if (!bn_rsa_fips186_4_gen_prob_primes(rsa
->q
, Xqo
, q1
, q2
, Xq
, Xq1
,
103 Xq2
, nbits
, e
, ctx
, cb
))
106 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
107 ok
= rsa_check_pminusq_diff(tmp
, Xpo
, Xqo
, nbits
);
113 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
114 ok
= rsa_check_pminusq_diff(tmp
, rsa
->p
, rsa
->q
, nbits
);
119 break; /* successfully finished */
123 /* Zeroize any internally generated values that are not returned */
135 * Validates the RSA key size based on the target strength.
136 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
139 * nbits The key size in bits.
140 * strength The target strength in bits. -1 means the target
141 * strength is unknown.
142 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
144 int rsa_sp800_56b_validate_strength(int nbits
, int strength
)
146 int s
= (int)rsa_compute_security_bits(nbits
);
148 if (s
< RSA_FIPS1864_MIN_KEYGEN_STRENGTH
149 || s
> RSA_FIPS1864_MAX_KEYGEN_STRENGTH
) {
150 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH
, RSA_R_INVALID_MODULUS
);
153 if (strength
!= -1 && s
!= strength
) {
154 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH
, RSA_R_INVALID_STRENGTH
);
162 * Using p & q, calculate other required parameters such as n, d.
163 * as well as the CRT parameters dP, dQ, qInv.
166 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
167 * 6.3.1.3 rsakpg1 - crt (Step 5)
171 * nbits The key size.
172 * e The public exponent.
173 * ctx A BN_CTX object.
175 * There is a small chance that the generated d will be too small.
176 * Returns: -1 = error,
177 * 0 = d is too small,
180 int rsa_sp800_56b_derive_params_from_pq(RSA
*rsa
, int nbits
,
181 const BIGNUM
*e
, BN_CTX
*ctx
)
184 BIGNUM
*p1
, *q1
, *lcm
, *p1q1
, *gcd
;
187 p1
= BN_CTX_get(ctx
);
188 q1
= BN_CTX_get(ctx
);
189 lcm
= BN_CTX_get(ctx
);
190 p1q1
= BN_CTX_get(ctx
);
191 gcd
= BN_CTX_get(ctx
);
195 /* LCM((p-1, q-1)) */
196 if (rsa_get_lcm(ctx
, rsa
->p
, rsa
->q
, lcm
, gcd
, p1
, q1
, p1q1
) != 1)
205 BN_clear_free(rsa
->d
);
206 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
207 rsa
->d
= BN_secure_new();
208 if (rsa
->d
== NULL
|| BN_mod_inverse(rsa
->d
, e
, lcm
, ctx
) == NULL
)
211 /* (Step 3) return an error if d is too small */
212 if (BN_num_bits(rsa
->d
) <= (nbits
>> 1)) {
217 /* (Step 4) n = pq */
220 if (rsa
->n
== NULL
|| !BN_mul(rsa
->n
, rsa
->p
, rsa
->q
, ctx
))
223 /* (Step 5a) dP = d mod (p-1) */
224 if (rsa
->dmp1
== NULL
)
225 rsa
->dmp1
= BN_new();
226 if (rsa
->dmp1
== NULL
|| !BN_mod(rsa
->dmp1
, rsa
->d
, p1
, ctx
))
229 /* (Step 5b) dQ = d mod (q-1) */
230 if (rsa
->dmq1
== NULL
)
231 rsa
->dmq1
= BN_secure_new();
232 if (rsa
->dmq1
== NULL
|| !BN_mod(rsa
->dmq1
, rsa
->d
, q1
, ctx
))
235 /* (Step 5c) qInv = (inverse of q) mod p */
237 rsa
->iqmp
= BN_secure_new();
238 if (rsa
->iqmp
== NULL
239 || BN_mod_inverse(rsa
->iqmp
, rsa
->q
, rsa
->p
, ctx
) == NULL
)
269 * Generate a SP800-56B RSA key.
271 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
272 * 6.3.1.1 rsakpg1 - basic
273 * 6.3.1.3 rsakpg1 - crt
275 * See also FIPS 186-4 Section B.3.6
276 * "Generation of Probable Primes with Conditions Based on Auxiliary
280 * rsa The rsa object.
281 * nbits The intended key size in bits.
282 * efixed The public exponent. If NULL a default of 65537 is used.
283 * cb An optional BIGNUM callback.
284 * Returns: 1 if successfully generated otherwise it returns 0.
286 int rsa_sp800_56b_generate_key(RSA
*rsa
, int nbits
, const BIGNUM
*efixed
,
294 /* (Steps 1a-1b) : Currently ignores the strength check */
295 if (!rsa_sp800_56b_validate_strength(nbits
, -1))
302 /* Set default if e is not passed in */
303 if (efixed
== NULL
) {
305 if (e
== NULL
|| !BN_set_word(e
, 65537))
308 e
= (BIGNUM
*)efixed
;
310 /* (Step 1c) fixed exponent is checked later . */
313 /* (Step 2) Generate prime factors */
314 if (!rsa_fips186_4_gen_prob_primes(rsa
, NULL
, NULL
, NULL
, NULL
, NULL
,
315 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
316 NULL
, nbits
, e
, ctx
, cb
))
318 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
319 ok
= rsa_sp800_56b_derive_params_from_pq(rsa
, nbits
, e
, ctx
);
324 /* Gets here if computed d is too small - so try again */
327 /* (Step 6) Do pairwise test - optional validity test has been omitted */
328 ret
= rsa_sp800_56b_pairwise_test(rsa
, ctx
);
337 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
338 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
340 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
342 int rsa_sp800_56b_pairwise_test(RSA
*rsa
, BN_CTX
*ctx
)
348 tmp
= BN_CTX_get(ctx
);
353 ret
= (BN_set_word(k
, 2)
354 && BN_mod_exp(tmp
, k
, rsa
->e
, rsa
->n
, ctx
)
355 && BN_mod_exp(tmp
, tmp
, rsa
->d
, rsa
->n
, ctx
)
356 && BN_cmp(k
, tmp
) == 0);
358 RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST
, RSA_R_PAIRWISE_TEST_FAILURE
);