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 | */ |
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) |
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; |
123 | err: |
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 | */ |
145 | int 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 | */ |
181 | int 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; |
245 | err: |
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 | */ |
288 | int 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); |
331 | err: |
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 | */ |
344 | int 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); |
361 | err: |
362 | BN_CTX_end(ctx); |
363 | return ret; |
364 | } |
365 | |