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, int bits,
- const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
{
case 1:
/* Deprecated-style callbacks */
+ if(!cb->cb.cb_1)
+ return 1;
cb->cb.cb_1(a, b, cb->arg);
return 1;
case 2:
int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
{
- BIGNUM t;
+ BIGNUM *t;
int found=0;
int i,j,c1=0;
BN_CTX *ctx;
int checks = BN_prime_checks_for_size(bits);
- BN_init(&t);
+ if (bits < 2)
+ {
+ /* There are no prime numbers this small. */
+ BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
+ return 0;
+ }
+ else if (bits == 2 && safe)
+ {
+ /* The smallest safe prime (7) is three bits. */
+ BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
+ return 0;
+ }
+
ctx=BN_CTX_new();
if (ctx == NULL) goto err;
+ BN_CTX_start(ctx);
+ t = BN_CTX_get(ctx);
+ if(!t) goto err;
loop:
/* make a random number and set the top and bottom bits */
if (add == NULL)
}
else
{
- if (!probable_prime_dh(ret,bits,add,rem,ctx))
+ if (!bn_probable_prime_dh(ret,bits,add,rem,ctx))
goto err;
}
}
* check that (p-1)/2 is prime.
* Since a prime is odd, We just
* need to divide by 2 */
- if (!BN_rshift1(&t,ret)) goto err;
+ if (!BN_rshift1(t,ret)) goto err;
for (i=0; i<checks; i++)
{
if (j == -1) goto err;
if (j == 0) goto loop;
- j=BN_is_prime_fasttest_ex(&t,1,ctx,0,cb);
+ j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);
if (j == -1) goto err;
if (j == 0) goto loop;
/* we have a prime :-) */
found = 1;
err:
- BN_free(&t);
- if (ctx != NULL) BN_CTX_free(ctx);
+ if (ctx != NULL)
+ {
+ BN_CTX_end(ctx);
+ BN_CTX_free(ctx);
+ }
+ bn_check_top(ret);
return found;
}
/* first look for small factors */
if (!BN_is_odd(a))
- return 0;
+ /* a is even => a is prime if and only if a == 2 */
+ return BN_is_word(a, 2);
if (do_trial_division)
{
for (i = 1; i < NUMPRIMES; i++)
return(ret);
}
+int bn_probable_prime_dh(BIGNUM *rnd, int bits,
+ const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
+ {
+ int i,ret=0;
+ BIGNUM *t1;
+
+ BN_CTX_start(ctx);
+ if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
+
+ if (!BN_rand(rnd,bits,0,1)) 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=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);
+ }
+
static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont)
{
}
/* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
* and it is neither -1 nor +1 -- so 'a' cannot be prime */
+ bn_check_top(w);
return 1;
}
static int probable_prime(BIGNUM *rnd, int bits)
{
int i;
- BN_ULONG mods[NUMPRIMES];
- BN_ULONG delta,d;
+ prime_t mods[NUMPRIMES];
+ BN_ULONG delta;
+ BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1];
+ char is_single_word = bits <= BN_BITS2;
again:
if (!BN_rand(rnd,bits,1,1)) return(0);
- /* we now have a random number 'rand' to test. */
+ /* we now have a random number 'rnd' to test. */
for (i=1; i<NUMPRIMES; i++)
- mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]);
+ mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]);
+ /* If bits is so small that it fits into a single word then we
+ * additionally don't want to exceed that many bits. */
+ if (is_single_word)
+ {
+ BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1;
+ if (size_limit < maxdelta)
+ maxdelta = size_limit;
+ }
delta=0;
- loop: for (i=1; i<NUMPRIMES; i++)
+loop:
+ if (is_single_word)
{
- /* check that rnd is not a prime and also
- * that gcd(rnd-1,primes) == 1 (except for 2) */
- if (((mods[i]+delta)%primes[i]) <= 1)
+ BN_ULONG rnd_word = BN_get_word(rnd);
+
+ /* In the case that the candidate prime is a single word then
+ * we check that:
+ * 1) It's greater than primes[i] because we shouldn't reject
+ * 3 as being a prime number because it's a multiple of
+ * three.
+ * 2) That it's not a multiple of a known prime. We don't
+ * check that rnd-1 is also coprime to all the known
+ * primes because there aren't many small primes where
+ * that's true. */
+ for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++)
{
- d=delta;
- delta+=2;
- /* perhaps need to check for overflow of
- * delta (but delta can be up to 2^32)
- * 21-May-98 eay - added overflow check */
- if (delta < d) goto again;
- goto loop;
+ if ((mods[i]+delta)%primes[i] == 0)
+ {
+ delta+=2;
+ if (delta > maxdelta) goto again;
+ goto loop;
+ }
}
}
- if (!BN_add_word(rnd,delta)) return(0);
- return(1);
- }
-
-static int probable_prime_dh(BIGNUM *rnd, int bits,
- const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
- {
- int i,ret=0;
- BIGNUM *t1;
-
- BN_CTX_start(ctx);
- if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
-
- if (!BN_rand(rnd,bits,0,1)) 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=1; i<NUMPRIMES; i++)
{
- /* check that rnd is a prime */
- if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
+ for (i=1; i<NUMPRIMES; i++)
{
- if (!BN_add(rnd,rnd,add)) goto err;
- goto loop;
+ /* check that rnd is not a prime and also
+ * that gcd(rnd-1,primes) == 1 (except for 2) */
+ if (((mods[i]+delta)%primes[i]) <= 1)
+ {
+ delta+=2;
+ if (delta > maxdelta) goto again;
+ goto loop;
+ }
}
}
- ret=1;
-err:
- BN_CTX_end(ctx);
- return(ret);
+ if (!BN_add_word(rnd,delta)) return(0);
+ if (BN_num_bits(rnd) != bits)
+ goto again;
+ bn_check_top(rnd);
+ return(1);
}
static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
if (!BN_lshift1(p,q)) goto err;
if (!BN_add_word(p,1)) goto err;
- loop: for (i=1; i<NUMPRIMES; i++)
+loop:
+ for (i=1; i<NUMPRIMES; i++)
{
/* check that p and q are prime */
/* check that for p and q
ret=1;
err:
BN_CTX_end(ctx);
+ bn_check_top(p);
return(ret);
}
projects / openssl.git / blobdiff