rsa_sp800_56b_gen.c

Last change on this file was 108206, checked in by vboxsync, 3 months ago
openssl-3.3.2: Exported all files to OSE and removed .scm-settings bugref:10757
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 13.4 KB

Line
1	/*
2	* Copyright 2018-2024 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 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
9	*/
10
11	#include <openssl/err.h>
12	#include <openssl/bn.h>
13	#include <openssl/core.h>
14	#include <openssl/evp.h>
15	#include <openssl/rand.h>
16	#include "crypto/bn.h"
17	#include "crypto/security_bits.h"
18	#include "rsa_local.h"
19
20	#define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
21	#define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
22
23	/*
24	* Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
25	* "Generation of Probable Primes with Conditions Based on Auxiliary Probable
26	* Primes".
27	*
28	* Params:
29	* rsa Object used to store primes p & q.
30	* test Object used for CAVS testing only.that contains..
31	* p1, p2 The returned auxiliary primes for p.
32	* If NULL they are not returned.
33	* Xp An optional passed in value (that is random number used during
34	* generation of p).
35	* Xp1, Xp2 Optionally passed in randomly generated numbers from which
36	* auxiliary primes p1 & p2 are calculated. If NULL these values
37	* are generated internally.
38	* q1, q2 The returned auxiliary primes for q.
39	* If NULL they are not returned.
40	* Xq An optional passed in value (that is random number used during
41	* generation of q).
42	* Xq1, Xq2 Optionally passed in randomly generated numbers from which
43	* auxiliary primes q1 & q2 are calculated. If NULL these values
44	* are generated internally.
45	* nbits The key size in bits (The size of the modulus n).
46	* e The public exponent.
47	* ctx A BN_CTX object.
48	* cb An optional BIGNUM callback.
49	* Returns: 1 if successful, or 0 otherwise.
50	* Notes:
51	* p1, p2, q1, q2 are returned if they are not NULL.
52	* Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
53	* (Required for CAVS testing).
54	*/
55	int ossl_rsa_fips186_4_gen_prob_primes(RSA rsa, RSA_ACVP_TEST test,
56	int nbits, const BIGNUM e, BN_CTX ctx,
57	BN_GENCB *cb)
58	{
59	int ret = 0, ok;
60	/* Temp allocated BIGNUMS */
61	BIGNUM Xpo = NULL, Xqo = NULL, *tmp = NULL;
62	/* Intermediate BIGNUMS that can be returned for testing */
63	BIGNUM p1 = NULL, p2 = NULL;
64	BIGNUM q1 = NULL, q2 = NULL;
65	/* Intermediate BIGNUMS that can be input for testing */
66	BIGNUM Xp = NULL, Xp1 = NULL, *Xp2 = NULL;
67	BIGNUM Xq = NULL, Xq1 = NULL, *Xq2 = NULL;
68
69	#if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
70	if (test != NULL) {
71	Xp1 = test->Xp1;
72	Xp2 = test->Xp2;
73	Xq1 = test->Xq1;
74	Xq2 = test->Xq2;
75	Xp = test->Xp;
76	Xq = test->Xq;
77	p1 = test->p1;
78	p2 = test->p2;
79	q1 = test->q1;
80	q2 = test->q2;
81	}
82	#endif
83
84	/* (Step 1) Check key length
85	* NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
86	* Signature Generation and Key Agree/Transport.
87	*/
88	if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
89	ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
90	return 0;
91	}
92
93	if (!ossl_rsa_check_public_exponent(e)) {
94	ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
95	return 0;
96	}
97
98	/* (Step 3) Determine strength and check rand generator strength is ok -
99	* this step is redundant because the generator always returns a higher
100	* strength than is required.
101	*/
102
103	BN_CTX_start(ctx);
104	tmp = BN_CTX_get(ctx);
105	Xpo = BN_CTX_get(ctx);
106	Xqo = BN_CTX_get(ctx);
107	if (tmp == NULL \|\| Xpo == NULL \|\| Xqo == NULL)
108	goto err;
109	BN_set_flags(Xpo, BN_FLG_CONSTTIME);
110	BN_set_flags(Xqo, BN_FLG_CONSTTIME);
111
112	if (rsa->p == NULL)
113	rsa->p = BN_secure_new();
114	if (rsa->q == NULL)
115	rsa->q = BN_secure_new();
116	if (rsa->p == NULL \|\| rsa->q == NULL)
117	goto err;
118	BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
119	BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
120
121	/* (Step 4) Generate p, Xp */
122	if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
123	nbits, e, ctx, cb))
124	goto err;
125	for (;;) {
126	/* (Step 5) Generate q, Xq*/
127	if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
128	Xq2, nbits, e, ctx, cb))
129	goto err;
130
131	/* (Step 6) \|Xp - Xq\| > 2^(nbitlen/2 - 100) */
132	ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
133	if (ok < 0)
134	goto err;
135	if (ok == 0)
136	continue;
137
138	/* (Step 6) \|p - q\| > 2^(nbitlen/2 - 100) */
139	ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
140	if (ok < 0)
141	goto err;
142	if (ok == 0)
143	continue;
144	break; /* successfully finished */
145	}
146	rsa->dirty_cnt++;
147	ret = 1;
148	err:
149	/* Zeroize any internally generated values that are not returned */
150	if (Xpo != NULL)
151	BN_clear(Xpo);
152	if (Xqo != NULL)
153	BN_clear(Xqo);
154	BN_clear(tmp);
155
156	BN_CTX_end(ctx);
157	return ret;
158	}
159
160	/*
161	* Validates the RSA key size based on the target strength.
162	* See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
163	*
164	* Params:
165	* nbits The key size in bits.
166	* strength The target strength in bits. -1 means the target
167	* strength is unknown.
168	* Returns: 1 if the key size matches the target strength, or 0 otherwise.
169	*/
170	int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength)
171	{
172	int s = (int)ossl_ifc_ffc_compute_security_bits(nbits);
173
174	#ifdef FIPS_MODULE
175	if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) {
176	ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS);
177	return 0;
178	}
179	#endif
180	if (strength != -1 && s != strength) {
181	ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH);
182	return 0;
183	}
184	return 1;
185	}
186
187	/*
188	* Validate that the random bit generator is of sufficient strength to generate
189	* a key of the specified length.
190	*/
191	static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits)
192	{
193	if (rng == NULL)
194	return 0;
195	#ifdef FIPS_MODULE
196	/*
197	* This should become mainstream once similar tests are added to the other
198	* key generations and once there is a way to disable these checks.
199	*/
200	if (EVP_RAND_get_strength(rng) < ossl_ifc_ffc_compute_security_bits(nbits)) {
201	ERR_raise(ERR_LIB_RSA,
202	RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT);
203	return 0;
204	}
205	#endif
206	return 1;
207	}
208
209	/*
210	*
211	* Using p & q, calculate other required parameters such as n, d.
212	* as well as the CRT parameters dP, dQ, qInv.
213	*
214	* See SP800-56Br1
215	* 6.3.1.1 rsakpg1 - basic (Steps 3-4)
216	* 6.3.1.3 rsakpg1 - crt (Step 5)
217	*
218	* Params:
219	* rsa An rsa object.
220	* nbits The key size.
221	* e The public exponent.
222	* ctx A BN_CTX object.
223	* Notes:
224	* There is a small chance that the generated d will be too small.
225	* Returns: -1 = error,
226	* 0 = d is too small,
227	* 1 = success.
228	*
229	* SP800-56b key generation always passes a non NULL value for e.
230	* For other purposes, if e is NULL then it is assumed that e, n and d are
231	* already set in the RSA key and do not need to be recalculated.
232	*/
233	int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
234	const BIGNUM e, BN_CTX ctx)
235	{
236	int ret = -1;
237	BIGNUM p1, q1, lcm, p1q1, *gcd;
238	BN_CTX_start(ctx);
239	p1 = BN_CTX_get(ctx);
240	q1 = BN_CTX_get(ctx);
241	lcm = BN_CTX_get(ctx);
242	p1q1 = BN_CTX_get(ctx);
243	gcd = BN_CTX_get(ctx);
244	if (gcd == NULL)
245	goto err;
246
247	BN_set_flags(p1, BN_FLG_CONSTTIME);
248	BN_set_flags(q1, BN_FLG_CONSTTIME);
249	BN_set_flags(lcm, BN_FLG_CONSTTIME);
250	BN_set_flags(p1q1, BN_FLG_CONSTTIME);
251	BN_set_flags(gcd, BN_FLG_CONSTTIME);
252
253	/* LCM((p-1, q-1)) */
254	if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
255	goto err;
256
257	/*
258	* if e is provided as a parameter, don't recompute e, d or n
259	*/
260	if (e != NULL) {
261	/* copy e */
262	BN_free(rsa->e);
263	rsa->e = BN_dup(e);
264	if (rsa->e == NULL)
265	goto err;
266
267	BN_clear_free(rsa->d);
268	/* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
269	rsa->d = BN_secure_new();
270	if (rsa->d == NULL)
271	goto err;
272	BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
273	if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
274	goto err;
275
276	/* (Step 3) return an error if d is too small */
277	if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
278	ret = 0;
279	goto err;
280	}
281
282	/* (Step 4) n = pq */
283	if (rsa->n == NULL)
284	rsa->n = BN_new();
285	if (rsa->n == NULL \|\| !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
286	goto err;
287	}
288
289	/* (Step 5a) dP = d mod (p-1) */
290	if (rsa->dmp1 == NULL)
291	rsa->dmp1 = BN_secure_new();
292	if (rsa->dmp1 == NULL)
293	goto err;
294	BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
295	if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
296	goto err;
297
298	/* (Step 5b) dQ = d mod (q-1) */
299	if (rsa->dmq1 == NULL)
300	rsa->dmq1 = BN_secure_new();
301	if (rsa->dmq1 == NULL)
302	goto err;
303	BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
304	if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
305	goto err;
306
307	/* (Step 5c) qInv = (inverse of q) mod p */
308	BN_free(rsa->iqmp);
309	rsa->iqmp = BN_secure_new();
310	if (rsa->iqmp == NULL)
311	goto err;
312	BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
313	if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
314	goto err;
315
316	rsa->dirty_cnt++;
317	ret = 1;
318	err:
319	if (ret != 1) {
320	BN_free(rsa->e);
321	rsa->e = NULL;
322	BN_free(rsa->d);
323	rsa->d = NULL;
324	BN_free(rsa->n);
325	rsa->n = NULL;
326	BN_free(rsa->iqmp);
327	rsa->iqmp = NULL;
328	BN_free(rsa->dmq1);
329	rsa->dmq1 = NULL;
330	BN_free(rsa->dmp1);
331	rsa->dmp1 = NULL;
332	}
333	BN_clear(p1);
334	BN_clear(q1);
335	BN_clear(lcm);
336	BN_clear(p1q1);
337	BN_clear(gcd);
338
339	BN_CTX_end(ctx);
340	return ret;
341	}
342
343	/*
344	* Generate a SP800-56B RSA key.
345	*
346	* See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
347	* 6.3.1.1 rsakpg1 - basic
348	* 6.3.1.3 rsakpg1 - crt
349	*
350	* See also FIPS 186-4 Section B.3.6
351	* "Generation of Probable Primes with Conditions Based on Auxiliary
352	* Probable Primes."
353	*
354	* Params:
355	* rsa The rsa object.
356	* nbits The intended key size in bits.
357	* efixed The public exponent. If NULL a default of 65537 is used.
358	* cb An optional BIGNUM callback.
359	* Returns: 1 if successfully generated otherwise it returns 0.
360	*/
361	int ossl_rsa_sp800_56b_generate_key(RSA rsa, int nbits, const BIGNUM efixed,
362	BN_GENCB *cb)
363	{
364	int ret = 0;
365	int ok;
366	BN_CTX *ctx = NULL;
367	BIGNUM *e = NULL;
368	RSA_ACVP_TEST *info = NULL;
369	BIGNUM *tmp;
370
371	#if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
372	info = rsa->acvp_test;
373	#endif
374
375	/* (Steps 1a-1b) : Currently ignores the strength check */
376	if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1))
377	return 0;
378
379	/* Check that the RNG is capable of generating a key this large */
380	if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits))
381	return 0;
382
383	ctx = BN_CTX_new_ex(rsa->libctx);
384	if (ctx == NULL)
385	return 0;
386
387	/* Set default if e is not passed in */
388	if (efixed == NULL) {
389	e = BN_new();
390	if (e == NULL \|\| !BN_set_word(e, 65537))
391	goto err;
392	} else {
393	e = (BIGNUM *)efixed;
394	}
395	/* (Step 1c) fixed exponent is checked later .*/
396
397	for (;;) {
398	/* (Step 2) Generate prime factors */
399	if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb))
400	goto err;
401
402	/* p>q check and skipping in case of acvp test */
403	if (info == NULL && BN_cmp(rsa->p, rsa->q) < 0) {
404	tmp = rsa->p;
405	rsa->p = rsa->q;
406	rsa->q = tmp;
407	}
408
409	/* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
410	ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
411	if (ok < 0)
412	goto err;
413	if (ok > 0)
414	break;
415	/* Gets here if computed d is too small - so try again */
416	}
417
418	/* (Step 6) Do pairwise test - optional validity test has been omitted */
419	ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx);
420	err:
421	if (efixed == NULL)
422	BN_free(e);
423	BN_CTX_free(ctx);
424	return ret;
425	}
426
427	/*
428	* See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
429	* verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
430	*
431	* Returns 1 if the RSA key passes the pairwise test or 0 if it fails.
432	*/
433	int ossl_rsa_sp800_56b_pairwise_test(RSA rsa, BN_CTX ctx)
434	{
435	int ret = 0;
436	BIGNUM k, tmp;
437
438	BN_CTX_start(ctx);
439	tmp = BN_CTX_get(ctx);
440	k = BN_CTX_get(ctx);
441	if (k == NULL)
442	goto err;
443	BN_set_flags(k, BN_FLG_CONSTTIME);
444
445	ret = (BN_set_word(k, 2)
446	&& BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
447	&& BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
448	&& BN_cmp(k, tmp) == 0);
449	if (ret == 0)
450	ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE);
451	err:
452	BN_CTX_end(ctx);
453	return ret;
454	}

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/openssl-3.3.2/crypto/rsa/rsa_sp800_56b_gen.c

Download in other formats: