2 * Copyright 2018-2020 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
5 * Licensed under the Apache License 2.0 (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 "crypto/bn.h"
14 #include "crypto/security_bits.h"
15 #include "rsa_local.h"
17 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
18 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
19 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
22 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
23 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
27 * rsa Object used to store primes p & q.
28 * p1, p2 The returned auxiliary primes for p. If NULL they are not returned.
29 * Xpout An optionally returned random number used during generation of p.
30 * Xp An optional passed in value (that is random number used during
32 * Xp1, Xp2 Optionally passed in randomly generated numbers from which
33 * auxiliary primes p1 & p2 are calculated. If NULL these values
34 * are generated internally.
35 * q1, q2 The returned auxiliary primes for q. If NULL they are not returned.
36 * Xqout An optionally returned random number used during generation of q.
37 * Xq An optional passed in value (that is random number used during
39 * Xq1, Xq2 Optionally passed in randomly generated numbers from which
40 * auxiliary primes q1 & q2 are calculated. If NULL these values
41 * are generated internally.
42 * nbits The key size in bits (The size of the modulus n).
43 * e The public exponent.
44 * ctx A BN_CTX object.
45 * cb An optional BIGNUM callback.
46 * Returns: 1 if successful, or 0 otherwise.
48 * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
49 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
50 * (Required for CAVS testing).
52 int rsa_fips186_4_gen_prob_primes(RSA *rsa, BIGNUM *p1, BIGNUM *p2,
53 BIGNUM *Xpout, const BIGNUM *Xp,
54 const BIGNUM *Xp1, const BIGNUM *Xp2,
55 BIGNUM *q1, BIGNUM *q2, BIGNUM *Xqout,
56 const BIGNUM *Xq, const BIGNUM *Xq1,
57 const BIGNUM *Xq2, int nbits,
58 const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
61 BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
63 /* (Step 1) Check key length
64 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
65 * Signature Generation and Key Agree/Transport.
67 if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
68 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES, RSA_R_KEY_SIZE_TOO_SMALL);
72 if (!rsa_check_public_exponent(e)) {
73 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES,
74 RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
78 /* (Step 3) Determine strength and check rand generator strength is ok -
79 * this step is redundant because the generator always returns a higher
80 * strength than is required.
84 tmp = BN_CTX_get(ctx);
85 Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx);
86 Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
87 if (tmp == NULL || Xpo == NULL || Xqo == NULL)
91 rsa->p = BN_secure_new();
93 rsa->q = BN_secure_new();
94 if (rsa->p == NULL || rsa->q == NULL)
97 /* (Step 4) Generate p, Xp */
98 if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
102 /* (Step 5) Generate q, Xq*/
103 if (!bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
104 Xq2, nbits, e, ctx, cb))
107 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
108 ok = rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
114 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
115 ok = rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
120 break; /* successfully finished */
125 /* Zeroize any internally generated values that are not returned */
137 * Validates the RSA key size based on the target strength.
138 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
141 * nbits The key size in bits.
142 * strength The target strength in bits. -1 means the target
143 * strength is unknown.
144 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
146 int rsa_sp800_56b_validate_strength(int nbits, int strength)
148 int s = (int)ifc_ffc_compute_security_bits(nbits);
150 if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
151 || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
152 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_MODULUS);
156 if (strength != -1 && s != strength) {
157 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_STRENGTH);
165 * Using p & q, calculate other required parameters such as n, d.
166 * as well as the CRT parameters dP, dQ, qInv.
169 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
170 * 6.3.1.3 rsakpg1 - crt (Step 5)
174 * nbits The key size.
175 * e The public exponent.
176 * ctx A BN_CTX object.
178 * There is a small chance that the generated d will be too small.
179 * Returns: -1 = error,
180 * 0 = d is too small,
183 int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
184 const BIGNUM *e, BN_CTX *ctx)
187 BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
190 p1 = BN_CTX_get(ctx);
191 q1 = BN_CTX_get(ctx);
192 lcm = BN_CTX_get(ctx);
193 p1q1 = BN_CTX_get(ctx);
194 gcd = BN_CTX_get(ctx);
198 /* LCM((p-1, q-1)) */
199 if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
208 BN_clear_free(rsa->d);
209 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
210 rsa->d = BN_secure_new();
211 if (rsa->d == NULL || BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
214 /* (Step 3) return an error if d is too small */
215 if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
220 /* (Step 4) n = pq */
223 if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
226 /* (Step 5a) dP = d mod (p-1) */
227 if (rsa->dmp1 == NULL)
228 rsa->dmp1 = BN_new();
229 if (rsa->dmp1 == NULL || !BN_mod(rsa->dmp1, rsa->d, p1, ctx))
232 /* (Step 5b) dQ = d mod (q-1) */
233 if (rsa->dmq1 == NULL)
234 rsa->dmq1 = BN_secure_new();
235 if (rsa->dmq1 == NULL || !BN_mod(rsa->dmq1, rsa->d, q1, ctx))
238 /* (Step 5c) qInv = (inverse of q) mod p */
240 rsa->iqmp = BN_secure_new();
241 if (rsa->iqmp == NULL
242 || BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
273 * Generate a SP800-56B RSA key.
275 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
276 * 6.3.1.1 rsakpg1 - basic
277 * 6.3.1.3 rsakpg1 - crt
279 * See also FIPS 186-4 Section B.3.6
280 * "Generation of Probable Primes with Conditions Based on Auxiliary
284 * rsa The rsa object.
285 * nbits The intended key size in bits.
286 * efixed The public exponent. If NULL a default of 65537 is used.
287 * cb An optional BIGNUM callback.
288 * Returns: 1 if successfully generated otherwise it returns 0.
290 int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
298 /* (Steps 1a-1b) : Currently ignores the strength check */
299 if (!rsa_sp800_56b_validate_strength(nbits, -1))
302 ctx = BN_CTX_new_ex(rsa->libctx);
306 /* Set default if e is not passed in */
307 if (efixed == NULL) {
309 if (e == NULL || !BN_set_word(e, 65537))
312 e = (BIGNUM *)efixed;
314 /* (Step 1c) fixed exponent is checked later . */
317 /* (Step 2) Generate prime factors */
318 if (!rsa_fips186_4_gen_prob_primes(rsa, NULL, NULL, NULL, NULL, NULL,
319 NULL, NULL, NULL, NULL, NULL, NULL,
320 NULL, nbits, e, ctx, cb))
322 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
323 ok = rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
328 /* Gets here if computed d is too small - so try again */
331 /* (Step 6) Do pairwise test - optional validity test has been omitted */
332 ret = rsa_sp800_56b_pairwise_test(rsa, ctx);
341 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
342 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
344 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
346 int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
352 tmp = BN_CTX_get(ctx);
357 ret = (BN_set_word(k, 2)
358 && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
359 && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
360 && BN_cmp(k, tmp) == 0);
362 RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST, RSA_R_PAIRWISE_TEST_FAILURE);