dsa_gen.c@ 69890

Last change on this file since 69890 was 69890, checked in by vboxsync, 7 years ago
Added OpenSSL 1.1.0g with unneeded files removed, otherwise unmodified. bugref:8070: src/libs maintenance
Property svn:eol-style set to `native`
File size: 16.2 KB

Line
1	/*
2	* Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
3	*
4	* Licensed under the OpenSSL license (the "License"). You may not use
5	* this file except in compliance with the License. You can obtain a copy
6	* in the file LICENSE in the source distribution or at
7	* https://www.openssl.org/source/license.html
8	*/
9
10	/*
11	* Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
12	* also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
13	* 180-1)
14	*/
15	#define xxxHASH EVP_sha1()
16
17	#include <openssl/opensslconf.h>
18	#include <stdio.h>
19	#include "internal/cryptlib.h"
20	#include <openssl/evp.h>
21	#include <openssl/bn.h>
22	#include <openssl/rand.h>
23	#include <openssl/sha.h>
24	#include "dsa_locl.h"
25
26	int DSA_generate_parameters_ex(DSA *ret, int bits,
27	const unsigned char *seed_in, int seed_len,
28	int counter_ret, unsigned long h_ret,
29	BN_GENCB *cb)
30	{
31	if (ret->meth->dsa_paramgen)
32	return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
33	counter_ret, h_ret, cb);
34	else {
35	const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1();
36	size_t qbits = EVP_MD_size(evpmd) * 8;
37
38	return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
39	seed_in, seed_len, NULL, counter_ret,
40	h_ret, cb);
41	}
42	}
43
44	int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
45	const EVP_MD evpmd, const unsigned char seed_in,
46	size_t seed_len, unsigned char *seed_out,
47	int counter_ret, unsigned long h_ret, BN_GENCB *cb)
48	{
49	int ok = 0;
50	unsigned char seed[SHA256_DIGEST_LENGTH];
51	unsigned char md[SHA256_DIGEST_LENGTH];
52	unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
53	BIGNUM r0, W, X, c, *test;
54	BIGNUM g = NULL, q = NULL, *p = NULL;
55	BN_MONT_CTX *mont = NULL;
56	int i, k, n = 0, m = 0, qsize = qbits >> 3;
57	int counter = 0;
58	int r = 0;
59	BN_CTX *ctx = NULL;
60	unsigned int h = 2;
61
62	if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
63	qsize != SHA256_DIGEST_LENGTH)
64	/* invalid q size */
65	return 0;
66
67	if (evpmd == NULL)
68	/* use SHA1 as default */
69	evpmd = EVP_sha1();
70
71	if (bits < 512)
72	bits = 512;
73
74	bits = (bits + 63) / 64 * 64;
75
76	if (seed_in != NULL) {
77	if (seed_len < (size_t)qsize) {
78	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL);
79	return 0;
80	}
81	if (seed_len > (size_t)qsize) {
82	/* Only consume as much seed as is expected. */
83	seed_len = qsize;
84	}
85	memcpy(seed, seed_in, seed_len);
86	}
87
88	if ((mont = BN_MONT_CTX_new()) == NULL)
89	goto err;
90
91	if ((ctx = BN_CTX_new()) == NULL)
92	goto err;
93
94	BN_CTX_start(ctx);
95
96	r0 = BN_CTX_get(ctx);
97	g = BN_CTX_get(ctx);
98	W = BN_CTX_get(ctx);
99	q = BN_CTX_get(ctx);
100	X = BN_CTX_get(ctx);
101	c = BN_CTX_get(ctx);
102	p = BN_CTX_get(ctx);
103	test = BN_CTX_get(ctx);
104
105	if (test == NULL)
106	goto err;
107
108	if (!BN_lshift(test, BN_value_one(), bits - 1))
109	goto err;
110
111	for (;;) {
112	for (;;) { /* find q */
113	int use_random_seed = (seed_in == NULL);
114
115	/* step 1 */
116	if (!BN_GENCB_call(cb, 0, m++))
117	goto err;
118
119	if (use_random_seed) {
120	if (RAND_bytes(seed, qsize) <= 0)
121	goto err;
122	} else {
123	/* If we come back through, use random seed next time. */
124	seed_in = NULL;
125	}
126	memcpy(buf, seed, qsize);
127	memcpy(buf2, seed, qsize);
128	/* precompute "SEED + 1" for step 7: */
129	for (i = qsize - 1; i >= 0; i--) {
130	buf[i]++;
131	if (buf[i] != 0)
132	break;
133	}
134
135	/* step 2 */
136	if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
137	goto err;
138	if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
139	goto err;
140	for (i = 0; i < qsize; i++)
141	md[i] ^= buf2[i];
142
143	/* step 3 */
144	md[0] \|= 0x80;
145	md[qsize - 1] \|= 0x01;
146	if (!BN_bin2bn(md, qsize, q))
147	goto err;
148
149	/* step 4 */
150	r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
151	use_random_seed, cb);
152	if (r > 0)
153	break;
154	if (r != 0)
155	goto err;
156
157	/* do a callback call */
158	/* step 5 */
159	}
160
161	if (!BN_GENCB_call(cb, 2, 0))
162	goto err;
163	if (!BN_GENCB_call(cb, 3, 0))
164	goto err;
165
166	/* step 6 */
167	counter = 0;
168	/* "offset = 2" */
169
170	n = (bits - 1) / 160;
171
172	for (;;) {
173	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
174	goto err;
175
176	/* step 7 */
177	BN_zero(W);
178	/* now 'buf' contains "SEED + offset - 1" */
179	for (k = 0; k <= n; k++) {
180	/*
181	* obtain "SEED + offset + k" by incrementing:
182	*/
183	for (i = qsize - 1; i >= 0; i--) {
184	buf[i]++;
185	if (buf[i] != 0)
186	break;
187	}
188
189	if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
190	goto err;
191
192	/* step 8 */
193	if (!BN_bin2bn(md, qsize, r0))
194	goto err;
195	if (!BN_lshift(r0, r0, (qsize << 3) * k))
196	goto err;
197	if (!BN_add(W, W, r0))
198	goto err;
199	}
200
201	/* more of step 8 */
202	if (!BN_mask_bits(W, bits - 1))
203	goto err;
204	if (!BN_copy(X, W))
205	goto err;
206	if (!BN_add(X, X, test))
207	goto err;
208
209	/* step 9 */
210	if (!BN_lshift1(r0, q))
211	goto err;
212	if (!BN_mod(c, X, r0, ctx))
213	goto err;
214	if (!BN_sub(r0, c, BN_value_one()))
215	goto err;
216	if (!BN_sub(p, X, r0))
217	goto err;
218
219	/* step 10 */
220	if (BN_cmp(p, test) >= 0) {
221	/* step 11 */
222	r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
223	if (r > 0)
224	goto end; /* found it */
225	if (r != 0)
226	goto err;
227	}
228
229	/* step 13 */
230	counter++;
231	/* "offset = offset + n + 1" */
232
233	/* step 14 */
234	if (counter >= 4096)
235	break;
236	}
237	}
238	end:
239	if (!BN_GENCB_call(cb, 2, 1))
240	goto err;
241
242	/* We now need to generate g */
243	/* Set r0=(p-1)/q */
244	if (!BN_sub(test, p, BN_value_one()))
245	goto err;
246	if (!BN_div(r0, NULL, test, q, ctx))
247	goto err;
248
249	if (!BN_set_word(test, h))
250	goto err;
251	if (!BN_MONT_CTX_set(mont, p, ctx))
252	goto err;
253
254	for (;;) {
255	/* g=test^r0%p */
256	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
257	goto err;
258	if (!BN_is_one(g))
259	break;
260	if (!BN_add(test, test, BN_value_one()))
261	goto err;
262	h++;
263	}
264
265	if (!BN_GENCB_call(cb, 3, 1))
266	goto err;
267
268	ok = 1;
269	err:
270	if (ok) {
271	BN_free(ret->p);
272	BN_free(ret->q);
273	BN_free(ret->g);
274	ret->p = BN_dup(p);
275	ret->q = BN_dup(q);
276	ret->g = BN_dup(g);
277	if (ret->p == NULL \|\| ret->q == NULL \|\| ret->g == NULL) {
278	ok = 0;
279	goto err;
280	}
281	if (counter_ret != NULL)
282	*counter_ret = counter;
283	if (h_ret != NULL)
284	*h_ret = h;
285	if (seed_out)
286	memcpy(seed_out, seed, qsize);
287	}
288	if (ctx)
289	BN_CTX_end(ctx);
290	BN_CTX_free(ctx);
291	BN_MONT_CTX_free(mont);
292	return ok;
293	}
294
295	/*
296	* This is a parameter generation algorithm for the DSA2 algorithm as
297	* described in FIPS 186-3.
298	*/
299
300	int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
301	const EVP_MD evpmd, const unsigned char seed_in,
302	size_t seed_len, int idx, unsigned char *seed_out,
303	int counter_ret, unsigned long h_ret,
304	BN_GENCB *cb)
305	{
306	int ok = -1;
307	unsigned char seed = NULL, seed_tmp = NULL;
308	unsigned char md[EVP_MAX_MD_SIZE];
309	int mdsize;
310	BIGNUM r0, W, X, c, *test;
311	BIGNUM g = NULL, q = NULL, *p = NULL;
312	BN_MONT_CTX *mont = NULL;
313	int i, k, n = 0, m = 0, qsize = N >> 3;
314	int counter = 0;
315	int r = 0;
316	BN_CTX *ctx = NULL;
317	EVP_MD_CTX *mctx = EVP_MD_CTX_new();
318	unsigned int h = 2;
319
320	if (mctx == NULL)
321	goto err;
322
323	if (evpmd == NULL) {
324	if (N == 160)
325	evpmd = EVP_sha1();
326	else if (N == 224)
327	evpmd = EVP_sha224();
328	else
329	evpmd = EVP_sha256();
330	}
331
332	mdsize = EVP_MD_size(evpmd);
333	/* If unverifiable g generation only don't need seed */
334	if (!ret->p \|\| !ret->q \|\| idx >= 0) {
335	if (seed_len == 0)
336	seed_len = mdsize;
337
338	seed = OPENSSL_malloc(seed_len);
339
340	if (seed_out)
341	seed_tmp = seed_out;
342	else
343	seed_tmp = OPENSSL_malloc(seed_len);
344
345	if (seed == NULL \|\| seed_tmp == NULL)
346	goto err;
347
348	if (seed_in)
349	memcpy(seed, seed_in, seed_len);
350
351	}
352
353	if ((ctx = BN_CTX_new()) == NULL)
354	goto err;
355
356	if ((mont = BN_MONT_CTX_new()) == NULL)
357	goto err;
358
359	BN_CTX_start(ctx);
360	r0 = BN_CTX_get(ctx);
361	g = BN_CTX_get(ctx);
362	W = BN_CTX_get(ctx);
363	X = BN_CTX_get(ctx);
364	c = BN_CTX_get(ctx);
365	test = BN_CTX_get(ctx);
366	if (test == NULL)
367	goto err;
368
369	/* if p, q already supplied generate g only */
370	if (ret->p && ret->q) {
371	p = ret->p;
372	q = ret->q;
373	if (idx >= 0)
374	memcpy(seed_tmp, seed, seed_len);
375	goto g_only;
376	} else {
377	p = BN_CTX_get(ctx);
378	q = BN_CTX_get(ctx);
379	if (q == NULL)
380	goto err;
381	}
382
383	if (!BN_lshift(test, BN_value_one(), L - 1))
384	goto err;
385	for (;;) {
386	for (;;) { /* find q */
387	unsigned char *pmd;
388	/* step 1 */
389	if (!BN_GENCB_call(cb, 0, m++))
390	goto err;
391
392	if (!seed_in) {
393	if (RAND_bytes(seed, seed_len) <= 0)
394	goto err;
395	}
396	/* step 2 */
397	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
398	goto err;
399	/* Take least significant bits of md */
400	if (mdsize > qsize)
401	pmd = md + mdsize - qsize;
402	else
403	pmd = md;
404
405	if (mdsize < qsize)
406	memset(md + mdsize, 0, qsize - mdsize);
407
408	/* step 3 */
409	pmd[0] \|= 0x80;
410	pmd[qsize - 1] \|= 0x01;
411	if (!BN_bin2bn(pmd, qsize, q))
412	goto err;
413
414	/* step 4 */
415	r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
416	seed_in ? 1 : 0, cb);
417	if (r > 0)
418	break;
419	if (r != 0)
420	goto err;
421	/* Provided seed didn't produce a prime: error */
422	if (seed_in) {
423	ok = 0;
424	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
425	goto err;
426	}
427
428	/* do a callback call */
429	/* step 5 */
430	}
431	/* Copy seed to seed_out before we mess with it */
432	if (seed_out)
433	memcpy(seed_out, seed, seed_len);
434
435	if (!BN_GENCB_call(cb, 2, 0))
436	goto err;
437	if (!BN_GENCB_call(cb, 3, 0))
438	goto err;
439
440	/* step 6 */
441	counter = 0;
442	/* "offset = 1" */
443
444	n = (L - 1) / (mdsize << 3);
445
446	for (;;) {
447	if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
448	goto err;
449
450	/* step 7 */
451	BN_zero(W);
452	/* now 'buf' contains "SEED + offset - 1" */
453	for (k = 0; k <= n; k++) {
454	/*
455	* obtain "SEED + offset + k" by incrementing:
456	*/
457	for (i = seed_len - 1; i >= 0; i--) {
458	seed[i]++;
459	if (seed[i] != 0)
460	break;
461	}
462
463	if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
464	goto err;
465
466	/* step 8 */
467	if (!BN_bin2bn(md, mdsize, r0))
468	goto err;
469	if (!BN_lshift(r0, r0, (mdsize << 3) * k))
470	goto err;
471	if (!BN_add(W, W, r0))
472	goto err;
473	}
474
475	/* more of step 8 */
476	if (!BN_mask_bits(W, L - 1))
477	goto err;
478	if (!BN_copy(X, W))
479	goto err;
480	if (!BN_add(X, X, test))
481	goto err;
482
483	/* step 9 */
484	if (!BN_lshift1(r0, q))
485	goto err;
486	if (!BN_mod(c, X, r0, ctx))
487	goto err;
488	if (!BN_sub(r0, c, BN_value_one()))
489	goto err;
490	if (!BN_sub(p, X, r0))
491	goto err;
492
493	/* step 10 */
494	if (BN_cmp(p, test) >= 0) {
495	/* step 11 */
496	r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
497	if (r > 0)
498	goto end; /* found it */
499	if (r != 0)
500	goto err;
501	}
502
503	/* step 13 */
504	counter++;
505	/* "offset = offset + n + 1" */
506
507	/* step 14 */
508	if (counter >= (int)(4 * L))
509	break;
510	}
511	if (seed_in) {
512	ok = 0;
513	DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
514	goto err;
515	}
516	}
517	end:
518	if (!BN_GENCB_call(cb, 2, 1))
519	goto err;
520
521	g_only:
522
523	/* We now need to generate g */
524	/* Set r0=(p-1)/q */
525	if (!BN_sub(test, p, BN_value_one()))
526	goto err;
527	if (!BN_div(r0, NULL, test, q, ctx))
528	goto err;
529
530	if (idx < 0) {
531	if (!BN_set_word(test, h))
532	goto err;
533	} else
534	h = 1;
535	if (!BN_MONT_CTX_set(mont, p, ctx))
536	goto err;
537
538	for (;;) {
539	static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
540	if (idx >= 0) {
541	md[0] = idx & 0xff;
542	md[1] = (h >> 8) & 0xff;
543	md[2] = h & 0xff;
544	if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
545	goto err;
546	if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
547	goto err;
548	if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
549	goto err;
550	if (!EVP_DigestUpdate(mctx, md, 3))
551	goto err;
552	if (!EVP_DigestFinal_ex(mctx, md, NULL))
553	goto err;
554	if (!BN_bin2bn(md, mdsize, test))
555	goto err;
556	}
557	/* g=test^r0%p */
558	if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
559	goto err;
560	if (!BN_is_one(g))
561	break;
562	if (idx < 0 && !BN_add(test, test, BN_value_one()))
563	goto err;
564	h++;
565	if (idx >= 0 && h > 0xffff)
566	goto err;
567	}
568
569	if (!BN_GENCB_call(cb, 3, 1))
570	goto err;
571
572	ok = 1;
573	err:
574	if (ok == 1) {
575	if (p != ret->p) {
576	BN_free(ret->p);
577	ret->p = BN_dup(p);
578	}
579	if (q != ret->q) {
580	BN_free(ret->q);
581	ret->q = BN_dup(q);
582	}
583	BN_free(ret->g);
584	ret->g = BN_dup(g);
585	if (ret->p == NULL \|\| ret->q == NULL \|\| ret->g == NULL) {
586	ok = -1;
587	goto err;
588	}
589	if (counter_ret != NULL)
590	*counter_ret = counter;
591	if (h_ret != NULL)
592	*h_ret = h;
593	}
594	OPENSSL_free(seed);
595	if (seed_out != seed_tmp)
596	OPENSSL_free(seed_tmp);
597	if (ctx)
598	BN_CTX_end(ctx);
599	BN_CTX_free(ctx);
600	BN_MONT_CTX_free(mont);
601	EVP_MD_CTX_free(mctx);
602	return ok;
603	}

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

source: vbox/trunk/src/libs/openssl-1.1.0g/crypto/dsa/dsa_gen.c@ 69890

Download in other formats: