os/ossrv/ssl/libcrypto/src/crypto/dsa/dsa_gen.c
author sl@SLION-WIN7.fritz.box
Fri, 15 Jun 2012 03:10:57 +0200
changeset 0 bde4ae8d615e
permissions -rw-r--r--
First public contribution.
sl@0
     1
/* crypto/dsa/dsa_gen.c */
sl@0
     2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
sl@0
     3
 * All rights reserved.
sl@0
     4
 *
sl@0
     5
 * This package is an SSL implementation written
sl@0
     6
 * by Eric Young (eay@cryptsoft.com).
sl@0
     7
 * The implementation was written so as to conform with Netscapes SSL.
sl@0
     8
 * 
sl@0
     9
 * This library is free for commercial and non-commercial use as long as
sl@0
    10
 * the following conditions are aheared to.  The following conditions
sl@0
    11
 * apply to all code found in this distribution, be it the RC4, RSA,
sl@0
    12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
sl@0
    13
 * included with this distribution is covered by the same copyright terms
sl@0
    14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
sl@0
    15
 * 
sl@0
    16
 * Copyright remains Eric Young's, and as such any Copyright notices in
sl@0
    17
 * the code are not to be removed.
sl@0
    18
 * If this package is used in a product, Eric Young should be given attribution
sl@0
    19
 * as the author of the parts of the library used.
sl@0
    20
 * This can be in the form of a textual message at program startup or
sl@0
    21
 * in documentation (online or textual) provided with the package.
sl@0
    22
 * 
sl@0
    23
 * Redistribution and use in source and binary forms, with or without
sl@0
    24
 * modification, are permitted provided that the following conditions
sl@0
    25
 * are met:
sl@0
    26
 * 1. Redistributions of source code must retain the copyright
sl@0
    27
 *    notice, this list of conditions and the following disclaimer.
sl@0
    28
 * 2. Redistributions in binary form must reproduce the above copyright
sl@0
    29
 *    notice, this list of conditions and the following disclaimer in the
sl@0
    30
 *    documentation and/or other materials provided with the distribution.
sl@0
    31
 * 3. All advertising materials mentioning features or use of this software
sl@0
    32
 *    must display the following acknowledgement:
sl@0
    33
 *    "This product includes cryptographic software written by
sl@0
    34
 *     Eric Young (eay@cryptsoft.com)"
sl@0
    35
 *    The word 'cryptographic' can be left out if the rouines from the library
sl@0
    36
 *    being used are not cryptographic related :-).
sl@0
    37
 * 4. If you include any Windows specific code (or a derivative thereof) from 
sl@0
    38
 *    the apps directory (application code) you must include an acknowledgement:
sl@0
    39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
sl@0
    40
 * 
sl@0
    41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
sl@0
    42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
sl@0
    43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
sl@0
    44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
sl@0
    45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
sl@0
    46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
sl@0
    47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
sl@0
    48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
sl@0
    49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
sl@0
    50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
sl@0
    51
 * SUCH DAMAGE.
sl@0
    52
 * 
sl@0
    53
 * The licence and distribution terms for any publically available version or
sl@0
    54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
sl@0
    55
 * copied and put under another distribution licence
sl@0
    56
 * [including the GNU Public Licence.]
sl@0
    57
 */
sl@0
    58
sl@0
    59
#undef GENUINE_DSA
sl@0
    60
sl@0
    61
#ifdef GENUINE_DSA
sl@0
    62
/* Parameter generation follows the original release of FIPS PUB 186,
sl@0
    63
 * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) */
sl@0
    64
#define HASH    EVP_sha()
sl@0
    65
#else
sl@0
    66
/* Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
sl@0
    67
 * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in
sl@0
    68
 * FIPS PUB 180-1) */
sl@0
    69
#define HASH    EVP_sha1()
sl@0
    70
#endif 
sl@0
    71
sl@0
    72
#include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
sl@0
    73
sl@0
    74
#ifndef OPENSSL_NO_SHA
sl@0
    75
sl@0
    76
#include <stdio.h>
sl@0
    77
#include <time.h>
sl@0
    78
#include "cryptlib.h"
sl@0
    79
#include <openssl/evp.h>
sl@0
    80
#include <openssl/bn.h>
sl@0
    81
#include <openssl/dsa.h>
sl@0
    82
#include <openssl/rand.h>
sl@0
    83
#include <openssl/sha.h>
sl@0
    84
sl@0
    85
static int dsa_builtin_paramgen(DSA *ret, int bits,
sl@0
    86
		unsigned char *seed_in, int seed_len,
sl@0
    87
		int *counter_ret, unsigned long *h_ret, BN_GENCB *cb);
sl@0
    88
sl@0
    89
EXPORT_C int DSA_generate_parameters_ex(DSA *ret, int bits,
sl@0
    90
		unsigned char *seed_in, int seed_len,
sl@0
    91
		int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
sl@0
    92
	{
sl@0
    93
	if(ret->meth->dsa_paramgen)
sl@0
    94
		return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
sl@0
    95
				counter_ret, h_ret, cb);
sl@0
    96
	return dsa_builtin_paramgen(ret, bits, seed_in, seed_len,
sl@0
    97
			counter_ret, h_ret, cb);
sl@0
    98
	}
sl@0
    99
sl@0
   100
static int dsa_builtin_paramgen(DSA *ret, int bits,
sl@0
   101
		unsigned char *seed_in, int seed_len,
sl@0
   102
		int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
sl@0
   103
	{
sl@0
   104
	int ok=0;
sl@0
   105
	unsigned char seed[SHA_DIGEST_LENGTH];
sl@0
   106
	unsigned char md[SHA_DIGEST_LENGTH];
sl@0
   107
	unsigned char buf[SHA_DIGEST_LENGTH],buf2[SHA_DIGEST_LENGTH];
sl@0
   108
	BIGNUM *r0,*W,*X,*c,*test;
sl@0
   109
	BIGNUM *g=NULL,*q=NULL,*p=NULL;
sl@0
   110
	BN_MONT_CTX *mont=NULL;
sl@0
   111
	int k,n=0,i,b,m=0;
sl@0
   112
	int counter=0;
sl@0
   113
	int r=0;
sl@0
   114
	BN_CTX *ctx=NULL;
sl@0
   115
	unsigned int h=2;
sl@0
   116
sl@0
   117
	if (bits < 512) bits=512;
sl@0
   118
	bits=(bits+63)/64*64;
sl@0
   119
sl@0
   120
	/* NB: seed_len == 0 is special case: copy generated seed to
sl@0
   121
 	 * seed_in if it is not NULL.
sl@0
   122
 	 */
sl@0
   123
	if (seed_len && (seed_len < 20))
sl@0
   124
		seed_in = NULL; /* seed buffer too small -- ignore */
sl@0
   125
	if (seed_len > 20) 
sl@0
   126
		seed_len = 20; /* App. 2.2 of FIPS PUB 186 allows larger SEED,
sl@0
   127
		                * but our internal buffers are restricted to 160 bits*/
sl@0
   128
	if ((seed_in != NULL) && (seed_len == 20))
sl@0
   129
		{
sl@0
   130
		memcpy(seed,seed_in,seed_len);
sl@0
   131
		/* set seed_in to NULL to avoid it being copied back */
sl@0
   132
		seed_in = NULL;
sl@0
   133
		}
sl@0
   134
sl@0
   135
	if ((ctx=BN_CTX_new()) == NULL) goto err;
sl@0
   136
sl@0
   137
	if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
sl@0
   138
sl@0
   139
	BN_CTX_start(ctx);
sl@0
   140
	r0 = BN_CTX_get(ctx);
sl@0
   141
	g = BN_CTX_get(ctx);
sl@0
   142
	W = BN_CTX_get(ctx);
sl@0
   143
	q = BN_CTX_get(ctx);
sl@0
   144
	X = BN_CTX_get(ctx);
sl@0
   145
	c = BN_CTX_get(ctx);
sl@0
   146
	p = BN_CTX_get(ctx);
sl@0
   147
	test = BN_CTX_get(ctx);
sl@0
   148
sl@0
   149
	if (!BN_lshift(test,BN_value_one(),bits-1))
sl@0
   150
		goto err;
sl@0
   151
sl@0
   152
	for (;;)
sl@0
   153
		{
sl@0
   154
		for (;;) /* find q */
sl@0
   155
			{
sl@0
   156
			int seed_is_random;
sl@0
   157
sl@0
   158
			/* step 1 */
sl@0
   159
			if(!BN_GENCB_call(cb, 0, m++))
sl@0
   160
				goto err;
sl@0
   161
sl@0
   162
			if (!seed_len)
sl@0
   163
				{
sl@0
   164
				RAND_pseudo_bytes(seed,SHA_DIGEST_LENGTH);
sl@0
   165
				seed_is_random = 1;
sl@0
   166
				}
sl@0
   167
			else
sl@0
   168
				{
sl@0
   169
				seed_is_random = 0;
sl@0
   170
				seed_len=0; /* use random seed if 'seed_in' turns out to be bad*/
sl@0
   171
				}
sl@0
   172
			memcpy(buf,seed,SHA_DIGEST_LENGTH);
sl@0
   173
			memcpy(buf2,seed,SHA_DIGEST_LENGTH);
sl@0
   174
			/* precompute "SEED + 1" for step 7: */
sl@0
   175
			for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
sl@0
   176
				{
sl@0
   177
				buf[i]++;
sl@0
   178
				if (buf[i] != 0) break;
sl@0
   179
				}
sl@0
   180
sl@0
   181
			/* step 2 */
sl@0
   182
			EVP_Digest(seed,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
sl@0
   183
			EVP_Digest(buf,SHA_DIGEST_LENGTH,buf2,NULL,HASH, NULL);
sl@0
   184
			for (i=0; i<SHA_DIGEST_LENGTH; i++)
sl@0
   185
				md[i]^=buf2[i];
sl@0
   186
sl@0
   187
			/* step 3 */
sl@0
   188
			md[0]|=0x80;
sl@0
   189
			md[SHA_DIGEST_LENGTH-1]|=0x01;
sl@0
   190
			if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,q)) goto err;
sl@0
   191
sl@0
   192
			/* step 4 */
sl@0
   193
			r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
sl@0
   194
					seed_is_random, cb);
sl@0
   195
			if (r > 0)
sl@0
   196
				break;
sl@0
   197
			if (r != 0)
sl@0
   198
				goto err;
sl@0
   199
sl@0
   200
			/* do a callback call */
sl@0
   201
			/* step 5 */
sl@0
   202
			}
sl@0
   203
sl@0
   204
		if(!BN_GENCB_call(cb, 2, 0)) goto err;
sl@0
   205
		if(!BN_GENCB_call(cb, 3, 0)) goto err;
sl@0
   206
sl@0
   207
		/* step 6 */
sl@0
   208
		counter=0;
sl@0
   209
		/* "offset = 2" */
sl@0
   210
sl@0
   211
		n=(bits-1)/160;
sl@0
   212
		b=(bits-1)-n*160;
sl@0
   213
sl@0
   214
		for (;;)
sl@0
   215
			{
sl@0
   216
			if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
sl@0
   217
				goto err;
sl@0
   218
sl@0
   219
			/* step 7 */
sl@0
   220
			BN_zero(W);
sl@0
   221
			/* now 'buf' contains "SEED + offset - 1" */
sl@0
   222
			for (k=0; k<=n; k++)
sl@0
   223
				{
sl@0
   224
				/* obtain "SEED + offset + k" by incrementing: */
sl@0
   225
				for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
sl@0
   226
					{
sl@0
   227
					buf[i]++;
sl@0
   228
					if (buf[i] != 0) break;
sl@0
   229
					}
sl@0
   230
sl@0
   231
				EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
sl@0
   232
sl@0
   233
				/* step 8 */
sl@0
   234
				if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))
sl@0
   235
					goto err;
sl@0
   236
				if (!BN_lshift(r0,r0,160*k)) goto err;
sl@0
   237
				if (!BN_add(W,W,r0)) goto err;
sl@0
   238
				}
sl@0
   239
sl@0
   240
			/* more of step 8 */
sl@0
   241
			if (!BN_mask_bits(W,bits-1)) goto err;
sl@0
   242
			if (!BN_copy(X,W)) goto err;
sl@0
   243
			if (!BN_add(X,X,test)) goto err;
sl@0
   244
sl@0
   245
			/* step 9 */
sl@0
   246
			if (!BN_lshift1(r0,q)) goto err;
sl@0
   247
			if (!BN_mod(c,X,r0,ctx)) goto err;
sl@0
   248
			if (!BN_sub(r0,c,BN_value_one())) goto err;
sl@0
   249
			if (!BN_sub(p,X,r0)) goto err;
sl@0
   250
sl@0
   251
			/* step 10 */
sl@0
   252
			if (BN_cmp(p,test) >= 0)
sl@0
   253
				{
sl@0
   254
				/* step 11 */
sl@0
   255
				r = BN_is_prime_fasttest_ex(p, DSS_prime_checks,
sl@0
   256
						ctx, 1, cb);
sl@0
   257
				if (r > 0)
sl@0
   258
						goto end; /* found it */
sl@0
   259
				if (r != 0)
sl@0
   260
					goto err;
sl@0
   261
				}
sl@0
   262
sl@0
   263
			/* step 13 */
sl@0
   264
			counter++;
sl@0
   265
			/* "offset = offset + n + 1" */
sl@0
   266
sl@0
   267
			/* step 14 */
sl@0
   268
			if (counter >= 4096) break;
sl@0
   269
			}
sl@0
   270
		}
sl@0
   271
end:
sl@0
   272
	if(!BN_GENCB_call(cb, 2, 1))
sl@0
   273
		goto err;
sl@0
   274
sl@0
   275
	/* We now need to generate g */
sl@0
   276
	/* Set r0=(p-1)/q */
sl@0
   277
	if (!BN_sub(test,p,BN_value_one())) goto err;
sl@0
   278
	if (!BN_div(r0,NULL,test,q,ctx)) goto err;
sl@0
   279
sl@0
   280
	if (!BN_set_word(test,h)) goto err;
sl@0
   281
	if (!BN_MONT_CTX_set(mont,p,ctx)) goto err;
sl@0
   282
sl@0
   283
	for (;;)
sl@0
   284
		{
sl@0
   285
		/* g=test^r0%p */
sl@0
   286
		if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err;
sl@0
   287
		if (!BN_is_one(g)) break;
sl@0
   288
		if (!BN_add(test,test,BN_value_one())) goto err;
sl@0
   289
		h++;
sl@0
   290
		}
sl@0
   291
sl@0
   292
	if(!BN_GENCB_call(cb, 3, 1))
sl@0
   293
		goto err;
sl@0
   294
sl@0
   295
	ok=1;
sl@0
   296
err:
sl@0
   297
	if (ok)
sl@0
   298
		{
sl@0
   299
		if(ret->p) BN_free(ret->p);
sl@0
   300
		if(ret->q) BN_free(ret->q);
sl@0
   301
		if(ret->g) BN_free(ret->g);
sl@0
   302
		ret->p=BN_dup(p);
sl@0
   303
		ret->q=BN_dup(q);
sl@0
   304
		ret->g=BN_dup(g);
sl@0
   305
		if (ret->p == NULL || ret->q == NULL || ret->g == NULL)
sl@0
   306
			{
sl@0
   307
			ok=0;
sl@0
   308
			goto err;
sl@0
   309
			}
sl@0
   310
		if (seed_in != NULL) memcpy(seed_in,seed,20);
sl@0
   311
		if (counter_ret != NULL) *counter_ret=counter;
sl@0
   312
		if (h_ret != NULL) *h_ret=h;
sl@0
   313
		}
sl@0
   314
	if(ctx)
sl@0
   315
		{
sl@0
   316
		BN_CTX_end(ctx);
sl@0
   317
		BN_CTX_free(ctx);
sl@0
   318
		}
sl@0
   319
	if (mont != NULL) BN_MONT_CTX_free(mont);
sl@0
   320
	return ok;
sl@0
   321
	}
sl@0
   322
#endif