1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ssl/libcrypto/src/crypto/dsa/dsa_gen.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,322 @@
1.4 +/* crypto/dsa/dsa_gen.c */
1.5 +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
1.6 + * All rights reserved.
1.7 + *
1.8 + * This package is an SSL implementation written
1.9 + * by Eric Young (eay@cryptsoft.com).
1.10 + * The implementation was written so as to conform with Netscapes SSL.
1.11 + *
1.12 + * This library is free for commercial and non-commercial use as long as
1.13 + * the following conditions are aheared to. The following conditions
1.14 + * apply to all code found in this distribution, be it the RC4, RSA,
1.15 + * lhash, DES, etc., code; not just the SSL code. The SSL documentation
1.16 + * included with this distribution is covered by the same copyright terms
1.17 + * except that the holder is Tim Hudson (tjh@cryptsoft.com).
1.18 + *
1.19 + * Copyright remains Eric Young's, and as such any Copyright notices in
1.20 + * the code are not to be removed.
1.21 + * If this package is used in a product, Eric Young should be given attribution
1.22 + * as the author of the parts of the library used.
1.23 + * This can be in the form of a textual message at program startup or
1.24 + * in documentation (online or textual) provided with the package.
1.25 + *
1.26 + * Redistribution and use in source and binary forms, with or without
1.27 + * modification, are permitted provided that the following conditions
1.28 + * are met:
1.29 + * 1. Redistributions of source code must retain the copyright
1.30 + * notice, this list of conditions and the following disclaimer.
1.31 + * 2. Redistributions in binary form must reproduce the above copyright
1.32 + * notice, this list of conditions and the following disclaimer in the
1.33 + * documentation and/or other materials provided with the distribution.
1.34 + * 3. All advertising materials mentioning features or use of this software
1.35 + * must display the following acknowledgement:
1.36 + * "This product includes cryptographic software written by
1.37 + * Eric Young (eay@cryptsoft.com)"
1.38 + * The word 'cryptographic' can be left out if the rouines from the library
1.39 + * being used are not cryptographic related :-).
1.40 + * 4. If you include any Windows specific code (or a derivative thereof) from
1.41 + * the apps directory (application code) you must include an acknowledgement:
1.42 + * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
1.43 + *
1.44 + * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
1.45 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.46 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.47 + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
1.48 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.49 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.50 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.51 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.52 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.53 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.54 + * SUCH DAMAGE.
1.55 + *
1.56 + * The licence and distribution terms for any publically available version or
1.57 + * derivative of this code cannot be changed. i.e. this code cannot simply be
1.58 + * copied and put under another distribution licence
1.59 + * [including the GNU Public Licence.]
1.60 + */
1.61 +
1.62 +#undef GENUINE_DSA
1.63 +
1.64 +#ifdef GENUINE_DSA
1.65 +/* Parameter generation follows the original release of FIPS PUB 186,
1.66 + * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) */
1.67 +#define HASH EVP_sha()
1.68 +#else
1.69 +/* Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
1.70 + * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in
1.71 + * FIPS PUB 180-1) */
1.72 +#define HASH EVP_sha1()
1.73 +#endif
1.74 +
1.75 +#include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
1.76 +
1.77 +#ifndef OPENSSL_NO_SHA
1.78 +
1.79 +#include <stdio.h>
1.80 +#include <time.h>
1.81 +#include "cryptlib.h"
1.82 +#include <openssl/evp.h>
1.83 +#include <openssl/bn.h>
1.84 +#include <openssl/dsa.h>
1.85 +#include <openssl/rand.h>
1.86 +#include <openssl/sha.h>
1.87 +
1.88 +static int dsa_builtin_paramgen(DSA *ret, int bits,
1.89 + unsigned char *seed_in, int seed_len,
1.90 + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb);
1.91 +
1.92 +EXPORT_C int DSA_generate_parameters_ex(DSA *ret, int bits,
1.93 + unsigned char *seed_in, int seed_len,
1.94 + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
1.95 + {
1.96 + if(ret->meth->dsa_paramgen)
1.97 + return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
1.98 + counter_ret, h_ret, cb);
1.99 + return dsa_builtin_paramgen(ret, bits, seed_in, seed_len,
1.100 + counter_ret, h_ret, cb);
1.101 + }
1.102 +
1.103 +static int dsa_builtin_paramgen(DSA *ret, int bits,
1.104 + unsigned char *seed_in, int seed_len,
1.105 + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
1.106 + {
1.107 + int ok=0;
1.108 + unsigned char seed[SHA_DIGEST_LENGTH];
1.109 + unsigned char md[SHA_DIGEST_LENGTH];
1.110 + unsigned char buf[SHA_DIGEST_LENGTH],buf2[SHA_DIGEST_LENGTH];
1.111 + BIGNUM *r0,*W,*X,*c,*test;
1.112 + BIGNUM *g=NULL,*q=NULL,*p=NULL;
1.113 + BN_MONT_CTX *mont=NULL;
1.114 + int k,n=0,i,b,m=0;
1.115 + int counter=0;
1.116 + int r=0;
1.117 + BN_CTX *ctx=NULL;
1.118 + unsigned int h=2;
1.119 +
1.120 + if (bits < 512) bits=512;
1.121 + bits=(bits+63)/64*64;
1.122 +
1.123 + /* NB: seed_len == 0 is special case: copy generated seed to
1.124 + * seed_in if it is not NULL.
1.125 + */
1.126 + if (seed_len && (seed_len < 20))
1.127 + seed_in = NULL; /* seed buffer too small -- ignore */
1.128 + if (seed_len > 20)
1.129 + seed_len = 20; /* App. 2.2 of FIPS PUB 186 allows larger SEED,
1.130 + * but our internal buffers are restricted to 160 bits*/
1.131 + if ((seed_in != NULL) && (seed_len == 20))
1.132 + {
1.133 + memcpy(seed,seed_in,seed_len);
1.134 + /* set seed_in to NULL to avoid it being copied back */
1.135 + seed_in = NULL;
1.136 + }
1.137 +
1.138 + if ((ctx=BN_CTX_new()) == NULL) goto err;
1.139 +
1.140 + if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
1.141 +
1.142 + BN_CTX_start(ctx);
1.143 + r0 = BN_CTX_get(ctx);
1.144 + g = BN_CTX_get(ctx);
1.145 + W = BN_CTX_get(ctx);
1.146 + q = BN_CTX_get(ctx);
1.147 + X = BN_CTX_get(ctx);
1.148 + c = BN_CTX_get(ctx);
1.149 + p = BN_CTX_get(ctx);
1.150 + test = BN_CTX_get(ctx);
1.151 +
1.152 + if (!BN_lshift(test,BN_value_one(),bits-1))
1.153 + goto err;
1.154 +
1.155 + for (;;)
1.156 + {
1.157 + for (;;) /* find q */
1.158 + {
1.159 + int seed_is_random;
1.160 +
1.161 + /* step 1 */
1.162 + if(!BN_GENCB_call(cb, 0, m++))
1.163 + goto err;
1.164 +
1.165 + if (!seed_len)
1.166 + {
1.167 + RAND_pseudo_bytes(seed,SHA_DIGEST_LENGTH);
1.168 + seed_is_random = 1;
1.169 + }
1.170 + else
1.171 + {
1.172 + seed_is_random = 0;
1.173 + seed_len=0; /* use random seed if 'seed_in' turns out to be bad*/
1.174 + }
1.175 + memcpy(buf,seed,SHA_DIGEST_LENGTH);
1.176 + memcpy(buf2,seed,SHA_DIGEST_LENGTH);
1.177 + /* precompute "SEED + 1" for step 7: */
1.178 + for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
1.179 + {
1.180 + buf[i]++;
1.181 + if (buf[i] != 0) break;
1.182 + }
1.183 +
1.184 + /* step 2 */
1.185 + EVP_Digest(seed,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
1.186 + EVP_Digest(buf,SHA_DIGEST_LENGTH,buf2,NULL,HASH, NULL);
1.187 + for (i=0; i<SHA_DIGEST_LENGTH; i++)
1.188 + md[i]^=buf2[i];
1.189 +
1.190 + /* step 3 */
1.191 + md[0]|=0x80;
1.192 + md[SHA_DIGEST_LENGTH-1]|=0x01;
1.193 + if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,q)) goto err;
1.194 +
1.195 + /* step 4 */
1.196 + r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
1.197 + seed_is_random, cb);
1.198 + if (r > 0)
1.199 + break;
1.200 + if (r != 0)
1.201 + goto err;
1.202 +
1.203 + /* do a callback call */
1.204 + /* step 5 */
1.205 + }
1.206 +
1.207 + if(!BN_GENCB_call(cb, 2, 0)) goto err;
1.208 + if(!BN_GENCB_call(cb, 3, 0)) goto err;
1.209 +
1.210 + /* step 6 */
1.211 + counter=0;
1.212 + /* "offset = 2" */
1.213 +
1.214 + n=(bits-1)/160;
1.215 + b=(bits-1)-n*160;
1.216 +
1.217 + for (;;)
1.218 + {
1.219 + if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
1.220 + goto err;
1.221 +
1.222 + /* step 7 */
1.223 + BN_zero(W);
1.224 + /* now 'buf' contains "SEED + offset - 1" */
1.225 + for (k=0; k<=n; k++)
1.226 + {
1.227 + /* obtain "SEED + offset + k" by incrementing: */
1.228 + for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
1.229 + {
1.230 + buf[i]++;
1.231 + if (buf[i] != 0) break;
1.232 + }
1.233 +
1.234 + EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
1.235 +
1.236 + /* step 8 */
1.237 + if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))
1.238 + goto err;
1.239 + if (!BN_lshift(r0,r0,160*k)) goto err;
1.240 + if (!BN_add(W,W,r0)) goto err;
1.241 + }
1.242 +
1.243 + /* more of step 8 */
1.244 + if (!BN_mask_bits(W,bits-1)) goto err;
1.245 + if (!BN_copy(X,W)) goto err;
1.246 + if (!BN_add(X,X,test)) goto err;
1.247 +
1.248 + /* step 9 */
1.249 + if (!BN_lshift1(r0,q)) goto err;
1.250 + if (!BN_mod(c,X,r0,ctx)) goto err;
1.251 + if (!BN_sub(r0,c,BN_value_one())) goto err;
1.252 + if (!BN_sub(p,X,r0)) goto err;
1.253 +
1.254 + /* step 10 */
1.255 + if (BN_cmp(p,test) >= 0)
1.256 + {
1.257 + /* step 11 */
1.258 + r = BN_is_prime_fasttest_ex(p, DSS_prime_checks,
1.259 + ctx, 1, cb);
1.260 + if (r > 0)
1.261 + goto end; /* found it */
1.262 + if (r != 0)
1.263 + goto err;
1.264 + }
1.265 +
1.266 + /* step 13 */
1.267 + counter++;
1.268 + /* "offset = offset + n + 1" */
1.269 +
1.270 + /* step 14 */
1.271 + if (counter >= 4096) break;
1.272 + }
1.273 + }
1.274 +end:
1.275 + if(!BN_GENCB_call(cb, 2, 1))
1.276 + goto err;
1.277 +
1.278 + /* We now need to generate g */
1.279 + /* Set r0=(p-1)/q */
1.280 + if (!BN_sub(test,p,BN_value_one())) goto err;
1.281 + if (!BN_div(r0,NULL,test,q,ctx)) goto err;
1.282 +
1.283 + if (!BN_set_word(test,h)) goto err;
1.284 + if (!BN_MONT_CTX_set(mont,p,ctx)) goto err;
1.285 +
1.286 + for (;;)
1.287 + {
1.288 + /* g=test^r0%p */
1.289 + if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err;
1.290 + if (!BN_is_one(g)) break;
1.291 + if (!BN_add(test,test,BN_value_one())) goto err;
1.292 + h++;
1.293 + }
1.294 +
1.295 + if(!BN_GENCB_call(cb, 3, 1))
1.296 + goto err;
1.297 +
1.298 + ok=1;
1.299 +err:
1.300 + if (ok)
1.301 + {
1.302 + if(ret->p) BN_free(ret->p);
1.303 + if(ret->q) BN_free(ret->q);
1.304 + if(ret->g) BN_free(ret->g);
1.305 + ret->p=BN_dup(p);
1.306 + ret->q=BN_dup(q);
1.307 + ret->g=BN_dup(g);
1.308 + if (ret->p == NULL || ret->q == NULL || ret->g == NULL)
1.309 + {
1.310 + ok=0;
1.311 + goto err;
1.312 + }
1.313 + if (seed_in != NULL) memcpy(seed_in,seed,20);
1.314 + if (counter_ret != NULL) *counter_ret=counter;
1.315 + if (h_ret != NULL) *h_ret=h;
1.316 + }
1.317 + if(ctx)
1.318 + {
1.319 + BN_CTX_end(ctx);
1.320 + BN_CTX_free(ctx);
1.321 + }
1.322 + if (mont != NULL) BN_MONT_CTX_free(mont);
1.323 + return ok;
1.324 + }
1.325 +#endif