diff options
author | Felix Laurie von Massenbach <felix@erbridge.co.uk> | 2014-05-27 00:37:03 +0100 |
---|---|---|
committer | Ben Laurie <ben@links.org> | 2014-06-01 15:31:26 +0100 |
commit | b0513819e043b13692c9e923adf5aafa26cddec0 (patch) | |
tree | 2d84e04d840d932c7858e5de5df10c6db6e55010 /crypto/bn | |
parent | b359642ffd0ae9dff8e1eb7d871356c99b093f57 (diff) | |
download | openssl-b0513819e043b13692c9e923adf5aafa26cddec0.tar.gz |
Add a method to generate a prime that is guaranteed not to be divisible by 3 or 5.
Possibly some reduction in bias, but no speed gains.
Diffstat (limited to 'crypto/bn')
-rw-r--r-- | crypto/bn/bn_lcl.h | 2 | ||||
-rw-r--r-- | crypto/bn/bn_prime.c | 84 |
2 files changed, 57 insertions, 29 deletions
diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h index 40ef22b73f..fc54dcecdc 100644 --- a/crypto/bn/bn_lcl.h +++ b/crypto/bn/bn_lcl.h @@ -536,6 +536,8 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, int bn_probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); +int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); #ifdef __cplusplus } diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index ac6ae30fa2..b303a48726 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -129,9 +129,13 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); static int probable_prime(BIGNUM *rnd, int bits); +static int probable_prime_dh(BIGNUM *rnd, const BIGNUM *add, + const BIGNUM *rem, BN_CTX *ctx, int first_prime_index); static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); +static int prime_offsets[8] = { 7, 11, 13, 17, 19, 23, 29, 31 }; + int BN_GENCB_call(BN_GENCB *cb, int a, int b) { /* No callback means continue */ @@ -363,40 +367,25 @@ err: int bn_probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) { - int i,ret=0; - BIGNUM *t1; + if (!BN_rand(rnd, bits, 0, 1)) return(0); - BN_CTX_start(ctx); - if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; - - if (!BN_rand(rnd,bits,0,1)) goto err; + return(probable_prime_dh(rnd, add, rem, ctx, 1)); + } - /* we need ((rnd-rem) % add) == 0 */ +int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) + { + BIGNUM *offset_index = BN_new(); - if (!BN_mod(t1,rnd,add,ctx)) goto err; - if (!BN_sub(rnd,rnd,t1)) goto err; - if (rem == NULL) - { if (!BN_add_word(rnd,1)) goto err; } - else - { if (!BN_add(rnd,rnd,rem)) goto err; } + if (!BN_rand(rnd, bits, 0, 1)) return(0); + if (!BN_rand(offset_index, 3, -1, -1)) return(0); - /* we now have a random number 'rand' to test. */ + BN_mul_word(rnd, 30); + BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]); + + BN_free(offset_index); -loop: - for (i=1; i<NUMPRIMES; i++) - { - /* check that rnd is a prime */ - if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1) - { - if (!BN_add(rnd,rnd,add)) goto err; - goto loop; - } - } - ret=1; -err: - BN_CTX_end(ctx); - bn_check_top(rnd); - return(ret); + return(probable_prime_dh(rnd, add, rem, ctx, 3)); } static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, @@ -491,6 +480,43 @@ loop: return(1); } +static int probable_prime_dh(BIGNUM *rnd, const BIGNUM *add, + const BIGNUM *rem, BN_CTX *ctx, int first_prime_index) + { + int i,ret=0; + BIGNUM *t1; + + BN_CTX_start(ctx); + if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; + + /* we need ((rnd-rem) % add) == 0 */ + + if (!BN_mod(t1,rnd,add,ctx)) goto err; + if (!BN_sub(rnd,rnd,t1)) goto err; + if (rem == NULL) + { if (!BN_add_word(rnd,1)) goto err; } + else + { if (!BN_add(rnd,rnd,rem)) goto err; } + + /* we now have a random number 'rand' to test. */ + +loop: + for (i=first_prime_index; i<NUMPRIMES; i++) + { + /* check that rnd is a prime */ + if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1) + { + if (!BN_add(rnd,rnd,add)) goto err; + goto loop; + } + } + ret=1; +err: + BN_CTX_end(ctx); + bn_check_top(rnd); + return(ret); + } + static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, const BIGNUM *rem, BN_CTX *ctx) { |