1/*
2 * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
4 *
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
9 */
10
11#include <openssl/err.h>
12#include <openssl/bn.h>
13#include "crypto/bn.h"
14#include "rsa_local.h"
15
16#define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
17#define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
18#define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
19
20/*
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
23 * Primes".
24 *
25 * Params:
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
30 * generation of p).
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
37 * generation of q).
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.
46 * Notes:
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).
50 */
51int 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)
58{
59 int ret = 0, ok;
60 BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
61
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.
65 */
66 if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
67 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES, RSA_R_INVALID_KEY_LENGTH);
68 return 0;
69 }
70
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);
74 return 0;
75 }
76
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.
80 */
81
82 BN_CTX_start(ctx);
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)
87 goto err;
88
89 if (rsa->p == NULL)
90 rsa->p = BN_secure_new();
91 if (rsa->q == NULL)
92 rsa->q = BN_secure_new();
93 if (rsa->p == NULL || rsa->q == NULL)
94 goto err;
95
96 /* (Step 4) Generate p, Xp */
97 if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
98 nbits, e, ctx, cb))
99 goto err;
100 for(;;) {
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))
104 goto err;
105
106 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
107 ok = rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
108 if (ok < 0)
109 goto err;
110 if (ok == 0)
111 continue;
112
113 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
114 ok = rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
115 if (ok < 0)
116 goto err;
117 if (ok == 0)
118 continue;
119 break; /* successfully finished */
120 }
121 rsa->dirty_cnt++;
122 ret = 1;
123err:
124 /* Zeroize any internally generated values that are not returned */
125 if (Xpo != Xpout)
126 BN_clear(Xpo);
127 if (Xqo != Xqout)
128 BN_clear(Xqo);
129 BN_clear(tmp);
130
131 BN_CTX_end(ctx);
132 return ret;
133}
134
135/*
136 * Validates the RSA key size based on the target strength.
137 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
138 *
139 * Params:
140 * nbits The key size in bits.
141 * strength The target strength in bits. -1 means the target
142 * strength is unknown.
143 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
144 */
145int rsa_sp800_56b_validate_strength(int nbits, int strength)
146{
147 int s = (int)rsa_compute_security_bits(nbits);
148
149 if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
150 || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
151 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_MODULUS);
152 return 0;
153 }
154 if (strength != -1 && s != strength) {
155 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_STRENGTH);
156 return 0;
157 }
158 return 1;
159}
160
161/*
162 *
163 * Using p & q, calculate other required parameters such as n, d.
164 * as well as the CRT parameters dP, dQ, qInv.
165 *
166 * See SP800-56Br1
167 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
168 * 6.3.1.3 rsakpg1 - crt (Step 5)
169 *
170 * Params:
171 * rsa An rsa object.
172 * nbits The key size.
173 * e The public exponent.
174 * ctx A BN_CTX object.
175 * Notes:
176 * There is a small chance that the generated d will be too small.
177 * Returns: -1 = error,
178 * 0 = d is too small,
179 * 1 = success.
180 */
181int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
182 const BIGNUM *e, BN_CTX *ctx)
183{
184 int ret = -1;
185 BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
186
187 BN_CTX_start(ctx);
188 p1 = BN_CTX_get(ctx);
189 q1 = BN_CTX_get(ctx);
190 lcm = BN_CTX_get(ctx);
191 p1q1 = BN_CTX_get(ctx);
192 gcd = BN_CTX_get(ctx);
193 if (gcd == NULL)
194 goto err;
195
196 /* LCM((p-1, q-1)) */
197 if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
198 goto err;
199
200 /* copy e */
201 BN_free(rsa->e);
202 rsa->e = BN_dup(e);
203 if (rsa->e == NULL)
204 goto err;
205
206 BN_clear_free(rsa->d);
207 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
208 rsa->d = BN_secure_new();
209 if (rsa->d == NULL || BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
210 goto err;
211
212 /* (Step 3) return an error if d is too small */
213 if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
214 ret = 0;
215 goto err;
216 }
217
218 /* (Step 4) n = pq */
219 if (rsa->n == NULL)
220 rsa->n = BN_new();
221 if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
222 goto err;
223
224 /* (Step 5a) dP = d mod (p-1) */
225 if (rsa->dmp1 == NULL)
226 rsa->dmp1 = BN_new();
227 if (rsa->dmp1 == NULL || !BN_mod(rsa->dmp1, rsa->d, p1, ctx))
228 goto err;
229
230 /* (Step 5b) dQ = d mod (q-1) */
231 if (rsa->dmq1 == NULL)
232 rsa->dmq1 = BN_secure_new();
233 if (rsa->dmq1 == NULL || !BN_mod(rsa->dmq1, rsa->d, q1, ctx))
234 goto err;
235
236 /* (Step 5c) qInv = (inverse of q) mod p */
237 BN_free(rsa->iqmp);
238 rsa->iqmp = BN_secure_new();
239 if (rsa->iqmp == NULL
240 || BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
241 goto err;
242
243 rsa->dirty_cnt++;
244 ret = 1;
245err:
246 if (ret != 1) {
247 BN_free(rsa->e);
248 rsa->e = NULL;
249 BN_free(rsa->d);
250 rsa->d = NULL;
251 BN_free(rsa->n);
252 rsa->n = NULL;
253 BN_free(rsa->iqmp);
254 rsa->iqmp = NULL;
255 BN_free(rsa->dmq1);
256 rsa->dmq1 = NULL;
257 BN_free(rsa->dmp1);
258 rsa->dmp1 = NULL;
259 }
260 BN_clear(p1);
261 BN_clear(q1);
262 BN_clear(lcm);
263 BN_clear(p1q1);
264 BN_clear(gcd);
265
266 BN_CTX_end(ctx);
267 return ret;
268}
269
270/*
271 * Generate a SP800-56B RSA key.
272 *
273 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
274 * 6.3.1.1 rsakpg1 - basic
275 * 6.3.1.3 rsakpg1 - crt
276 *
277 * See also FIPS 186-4 Section B.3.6
278 * "Generation of Probable Primes with Conditions Based on Auxiliary
279 * Probable Primes."
280 *
281 * Params:
282 * rsa The rsa object.
283 * nbits The intended key size in bits.
284 * efixed The public exponent. If NULL a default of 65537 is used.
285 * cb An optional BIGNUM callback.
286 * Returns: 1 if successfully generated otherwise it returns 0.
287 */
288int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
289 BN_GENCB *cb)
290{
291 int ret = 0;
292 int ok;
293 BN_CTX *ctx = NULL;
294 BIGNUM *e = NULL;
295
296 /* (Steps 1a-1b) : Currently ignores the strength check */
297 if (!rsa_sp800_56b_validate_strength(nbits, -1))
298 return 0;
299
300 ctx = BN_CTX_new();
301 if (ctx == NULL)
302 return 0;
303
304 /* Set default if e is not passed in */
305 if (efixed == NULL) {
306 e = BN_new();
307 if (e == NULL || !BN_set_word(e, 65537))
308 goto err;
309 } else {
310 e = (BIGNUM *)efixed;
311 }
312 /* (Step 1c) fixed exponent is checked later . */
313
314 for (;;) {
315 /* (Step 2) Generate prime factors */
316 if (!rsa_fips186_4_gen_prob_primes(rsa, NULL, NULL, NULL, NULL, NULL,
317 NULL, NULL, NULL, NULL, NULL, NULL,
318 NULL, nbits, e, ctx, cb))
319 goto err;
320 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
321 ok = rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
322 if (ok < 0)
323 goto err;
324 if (ok > 0)
325 break;
326 /* Gets here if computed d is too small - so try again */
327 }
328
329 /* (Step 6) Do pairwise test - optional validity test has been omitted */
330 ret = rsa_sp800_56b_pairwise_test(rsa, ctx);
331err:
332 if (efixed == NULL)
333 BN_free(e);
334 BN_CTX_free(ctx);
335 return ret;
336}
337
338/*
339 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
340 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
341 *
342 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
343 */
344int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
345{
346 int ret = 0;
347 BIGNUM *k, *tmp;
348
349 BN_CTX_start(ctx);
350 tmp = BN_CTX_get(ctx);
351 k = BN_CTX_get(ctx);
352 if (k == NULL)
353 goto err;
354
355 ret = (BN_set_word(k, 2)
356 && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
357 && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
358 && BN_cmp(k, tmp) == 0);
359 if (ret == 0)
360 RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST, RSA_R_PAIRWISE_TEST_FAILURE);
361err:
362 BN_CTX_end(ctx);
363 return ret;
364}
365