From 3dd9b31dc4fc935543d4142dfdd9a88e3ef6dcd8 Mon Sep 17 00:00:00 2001 From: "Dr. Stephen Henson" Date: Mon, 31 Jan 2011 19:44:09 +0000 Subject: Provisional, experimental support for DSA2 parameter generation algorithm. Not properly integrated or tested yet. --- crypto/dsa/dsa.h | 3 + crypto/dsa/dsa_err.c | 3 + crypto/dsa/dsa_gen.c | 268 +++++++++++++++++++++++++++++++++++++++++++++++++- crypto/dsa/dsa_locl.h | 5 + 4 files changed, 277 insertions(+), 2 deletions(-) (limited to 'crypto/dsa') diff --git a/crypto/dsa/dsa.h b/crypto/dsa/dsa.h index d232f67fdb..06a7b1431d 100644 --- a/crypto/dsa/dsa.h +++ b/crypto/dsa/dsa.h @@ -296,6 +296,7 @@ void ERR_load_DSA_strings(void); #define DSA_F_DSAPARAMS_PRINT_FP 101 #define DSA_F_DSA_BUILTIN_KEYGEN 124 #define DSA_F_DSA_BUILTIN_PARAMGEN 125 +#define DSA_F_DSA_BUILTIN_PARAMGEN2 126 #define DSA_F_DSA_DO_SIGN 112 #define DSA_F_DSA_DO_VERIFY 113 #define DSA_F_DSA_NEW_METHOD 103 @@ -323,12 +324,14 @@ void ERR_load_DSA_strings(void); #define DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE 100 #define DSA_R_DECODE_ERROR 104 #define DSA_R_INVALID_DIGEST_TYPE 106 +#define DSA_R_INVALID_PARAMETERS 112 #define DSA_R_KEY_SIZE_TOO_SMALL 111 #define DSA_R_MISSING_PARAMETERS 101 #define DSA_R_MODULUS_TOO_LARGE 103 #define DSA_R_NEED_NEW_SETUP_VALUES 110 #define DSA_R_NO_PARAMETERS_SET 107 #define DSA_R_PARAMETER_ENCODING_ERROR 105 +#define DSA_R_Q_NOT_PRIME 113 #ifdef __cplusplus } diff --git a/crypto/dsa/dsa_err.c b/crypto/dsa/dsa_err.c index 3241e57a8e..a46fade4c6 100644 --- a/crypto/dsa/dsa_err.c +++ b/crypto/dsa/dsa_err.c @@ -76,6 +76,7 @@ static ERR_STRING_DATA DSA_str_functs[]= {ERR_FUNC(DSA_F_DSAPARAMS_PRINT_FP), "DSAparams_print_fp"}, {ERR_FUNC(DSA_F_DSA_BUILTIN_KEYGEN), "DSA_BUILTIN_KEYGEN"}, {ERR_FUNC(DSA_F_DSA_BUILTIN_PARAMGEN), "DSA_BUILTIN_PARAMGEN"}, +{ERR_FUNC(DSA_F_DSA_BUILTIN_PARAMGEN2), "DSA_BUILTIN_PARAMGEN2"}, {ERR_FUNC(DSA_F_DSA_DO_SIGN), "DSA_do_sign"}, {ERR_FUNC(DSA_F_DSA_DO_VERIFY), "DSA_do_verify"}, {ERR_FUNC(DSA_F_DSA_NEW_METHOD), "DSA_new_method"}, @@ -106,12 +107,14 @@ static ERR_STRING_DATA DSA_str_reasons[]= {ERR_REASON(DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE),"data too large for key size"}, {ERR_REASON(DSA_R_DECODE_ERROR) ,"decode error"}, {ERR_REASON(DSA_R_INVALID_DIGEST_TYPE) ,"invalid digest type"}, +{ERR_REASON(DSA_R_INVALID_PARAMETERS) ,"invalid parameters"}, {ERR_REASON(DSA_R_KEY_SIZE_TOO_SMALL) ,"key size too small"}, {ERR_REASON(DSA_R_MISSING_PARAMETERS) ,"missing parameters"}, {ERR_REASON(DSA_R_MODULUS_TOO_LARGE) ,"modulus too large"}, {ERR_REASON(DSA_R_NEED_NEW_SETUP_VALUES) ,"need new setup values"}, {ERR_REASON(DSA_R_NO_PARAMETERS_SET) ,"no parameters set"}, {ERR_REASON(DSA_R_PARAMETER_ENCODING_ERROR),"parameter encoding error"}, +{ERR_REASON(DSA_R_Q_NOT_PRIME) ,"q not prime"}, {0,NULL} }; diff --git a/crypto/dsa/dsa_gen.c b/crypto/dsa/dsa_gen.c index d5a41c249a..7f8ee8f727 100644 --- a/crypto/dsa/dsa_gen.c +++ b/crypto/dsa/dsa_gen.c @@ -136,8 +136,7 @@ int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, #ifdef OPENSSL_FIPS if(FIPS_selftest_failed()) { - FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN, - FIPS_R_FIPS_SELFTEST_FAILED); + FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN, FIPS_R_FIPS_SELFTEST_FAILED); goto err; } @@ -369,4 +368,269 @@ err: if (mont != NULL) BN_MONT_CTX_free(mont); return ok; } + +/* Permissible parameter values for (L,N): see FIPS186-3 4.2 */ + +static int dsa2_check_params(size_t L, size_t N) + { + if (L == 1024 && N == 160) + return 1; + if (L == 2048 && N == 224) + return 1; + if (L == 2048 && N == 256) + return 1; + if (L == 3072 && N == 256) + return 1; + return 0; + } + +/* This is a parameter generation algorithm for the DSA2 algorithm as + * described in FIPS 186-3. + */ + +int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, + const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, + unsigned char *seed_out, + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) + { + int ok=-1; + unsigned char *seed = NULL; + unsigned char md[EVP_MAX_MD_SIZE]; + int mdsize; + BIGNUM *r0,*W,*X,*c,*test; + BIGNUM *g=NULL,*q=NULL,*p=NULL; + BN_MONT_CTX *mont=NULL; + int i, k, n=0, m=0, qsize = N >> 3; + int counter=0; + int r=0; + BN_CTX *ctx=NULL; + unsigned int h=2; + +#ifdef OPENSSL_FIPS + if(FIPS_selftest_failed()) + { + FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN2, + FIPS_R_FIPS_SELFTEST_FAILED); + goto err; + } +#endif + if (!dsa2_check_params(L, N)) + { + DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); + ok = 0; + goto err; + } + + if (evpmd == NULL) + { + if (N == 160) + evpmd = EVP_sha1(); + else if (N == 224) + evpmd = EVP_sha224(); + else + evpmd = EVP_sha256(); + } + + mdsize = M_EVP_MD_size(evpmd); + + if (seed_len == 0) + seed_len = mdsize; + + seed = OPENSSL_malloc(seed_len); + + if (!seed) + goto err; + + if (seed_in) + memcpy(seed, seed_in, seed_len); + + if ((ctx=BN_CTX_new()) == NULL) + goto err; + + if ((mont=BN_MONT_CTX_new()) == NULL) + goto err; + + BN_CTX_start(ctx); + r0 = BN_CTX_get(ctx); + g = BN_CTX_get(ctx); + W = BN_CTX_get(ctx); + q = BN_CTX_get(ctx); + X = BN_CTX_get(ctx); + c = BN_CTX_get(ctx); + p = BN_CTX_get(ctx); + test = BN_CTX_get(ctx); + + if (!BN_lshift(test,BN_value_one(),L-1)) + goto err; + for (;;) + { + for (;;) /* find q */ + { + unsigned char *pmd; + /* step 1 */ + if(!BN_GENCB_call(cb, 0, m++)) + goto err; + + if (!seed_in) + RAND_pseudo_bytes(seed, qsize); + /* step 2 */ + if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) + goto err; + /* Take least significant bits of md */ + if (mdsize > qsize) + pmd = md + mdsize - qsize; + else + pmd = md; + + if (mdsize < qsize) + memset(md + mdsize, 0, qsize - mdsize); + + /* step 3 */ + pmd[0] |= 0x80; + pmd[qsize-1] |= 0x01; + if (!BN_bin2bn(pmd, qsize, q)) + goto err; + + /* step 4 */ + r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, + seed_in ? 1 : 0, cb); + if (r > 0) + break; + if (r != 0) + goto err; + /* Provided seed didn't produce a prime: error */ + if (seed_in) + { + ok = 0; + DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME); + goto err; + } + + /* do a callback call */ + /* step 5 */ + } + + if(!BN_GENCB_call(cb, 2, 0)) goto err; + if(!BN_GENCB_call(cb, 3, 0)) goto err; + + /* step 6 */ + counter=0; + /* "offset = 1" */ + + n=(L-1)/(mdsize << 3); + + for (;;) + { + if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) + goto err; + + /* step 7 */ + BN_zero(W); + /* now 'buf' contains "SEED + offset - 1" */ + for (k=0; k<=n; k++) + { + /* obtain "SEED + offset + k" by incrementing: */ + for (i = seed_len-1; i >= 0; i--) + { + seed[i]++; + if (seed[i] != 0) + break; + } + + if (!EVP_Digest(seed, seed_len, md ,NULL, evpmd, + NULL)) + goto err; + + /* step 8 */ + if (!BN_bin2bn(md, mdsize, r0)) + goto err; + if (!BN_lshift(r0,r0,(mdsize << 3)*k)) goto err; + if (!BN_add(W,W,r0)) goto err; + } + + /* more of step 8 */ + if (!BN_mask_bits(W,L-1)) goto err; + if (!BN_copy(X,W)) goto err; + if (!BN_add(X,X,test)) goto err; + + /* step 9 */ + if (!BN_lshift1(r0,q)) goto err; + if (!BN_mod(c,X,r0,ctx)) goto err; + if (!BN_sub(r0,c,BN_value_one())) goto err; + if (!BN_sub(p,X,r0)) goto err; + + /* step 10 */ + if (BN_cmp(p,test) >= 0) + { + /* step 11 */ + r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, + ctx, 1, cb); + if (r > 0) + goto end; /* found it */ + if (r != 0) + goto err; + } + + /* step 13 */ + counter++; + /* "offset = offset + n + 1" */ + + /* step 14 */ + if (counter >= 4096) break; + } + } +end: + if(!BN_GENCB_call(cb, 2, 1)) + goto err; + + /* We now need to generate g */ + /* Set r0=(p-1)/q */ + if (!BN_sub(test,p,BN_value_one())) goto err; + if (!BN_div(r0,NULL,test,q,ctx)) goto err; + + if (!BN_set_word(test,h)) goto err; + if (!BN_MONT_CTX_set(mont,p,ctx)) goto err; + + for (;;) + { + /* g=test^r0%p */ + if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err; + if (!BN_is_one(g)) break; + if (!BN_add(test,test,BN_value_one())) goto err; + h++; + } + + if(!BN_GENCB_call(cb, 3, 1)) + goto err; + + ok=1; +err: + if (ok) + { + if(ret->p) BN_free(ret->p); + if(ret->q) BN_free(ret->q); + if(ret->g) BN_free(ret->g); + ret->p=BN_dup(p); + ret->q=BN_dup(q); + ret->g=BN_dup(g); + if (ret->p == NULL || ret->q == NULL || ret->g == NULL) + { + ok=-1; + goto err; + } + if (counter_ret != NULL) *counter_ret=counter; + if (h_ret != NULL) *h_ret=h; + if (seed_out) + memcpy(seed_out, seed, seed_len); + } + if (seed) + OPENSSL_free(seed); + if(ctx) + { + BN_CTX_end(ctx); + BN_CTX_free(ctx); + } + if (mont != NULL) BN_MONT_CTX_free(mont); + return ok; + } #endif diff --git a/crypto/dsa/dsa_locl.h b/crypto/dsa/dsa_locl.h index 21e2e45242..4e07c7cbab 100644 --- a/crypto/dsa/dsa_locl.h +++ b/crypto/dsa/dsa_locl.h @@ -58,3 +58,8 @@ int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, unsigned char *seed_out, int *counter_ret, unsigned long *h_ret, BN_GENCB *cb); + +int dsa_builtin_paramgen2(DSA *ret, size_t bits, size_t qbits, + const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, + unsigned char *seed_out, + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb); -- cgit v1.2.3