#include "bn_lcl.h"
#include <openssl/rand.h>
-/* The quick seive algorithm approach to weeding out primes is
+/* The quick sieve algorithm approach to weeding out primes is
* Philip Zimmermann's, as implemented in PGP. I have had a read of
* his comments and implemented my own version.
*/
#include "bn_prime.h"
+/* number of Miller-Rabin iterations for an error rate of less than 2^-80
+ * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
+ * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
+ * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
+ * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
+#define BN_prime_checks_size(b) ((b) >= 1300 ? 2 : \
+ (b) >= 850 ? 3 : \
+ (b) >= 650 ? 4 : \
+ (b) >= 550 ? 5 : \
+ (b) >= 450 ? 6 : \
+ (b) >= 400 ? 7 : \
+ (b) >= 350 ? 8 : \
+ (b) >= 300 ? 9 : \
+ (b) >= 250 ? 12 : \
+ (b) >= 200 ? 15 : \
+ (b) >= 150 ? 18 : \
+ /* b >= 100 */ 27)
+
static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2,
BN_MONT_CTX *mont);
static int probable_prime(BIGNUM *rnd, int bits);
static int probable_prime_dh(BIGNUM *rnd, int bits,
BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
-static int probable_prime_dh_strong(BIGNUM *rnd, int bits,
+static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
-BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int strong, BIGNUM *add,
+
+BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, BIGNUM *add,
BIGNUM *rem, void (*callback)(int,int,void *), void *cb_arg)
{
BIGNUM *rnd=NULL;
BIGNUM t;
+ int found=0;
int i,j,c1=0;
BN_CTX *ctx;
+ int checks = BN_prime_checks_size(bits);
ctx=BN_CTX_new();
if (ctx == NULL) goto err;
}
else
{
- if (strong)
+ if (safe)
{
- if (!probable_prime_dh_strong(rnd,bits,add,rem,ctx))
+ if (!probable_prime_dh_safe(rnd,bits,add,rem,ctx))
goto err;
}
else
/* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */
if (callback != NULL) callback(0,c1++,cb_arg);
- if (!strong)
+ if (!safe)
{
- i=BN_is_prime(rnd,BN_prime_checks,callback,ctx,cb_arg);
+ i=BN_is_prime(rnd,checks,callback,ctx,cb_arg);
if (i == -1) goto err;
if (i == 0) goto loop;
}
else
{
- /* for a strong prime generation,
+ /* for "safe prime" generation,
* check that (p-1)/2 is prime.
* Since a prime is odd, We just
* need to divide by 2 */
if (!BN_rshift1(&t,rnd)) goto err;
- for (i=0; i<BN_prime_checks; i++)
+ for (i=0; i<checks; i++)
{
j=BN_is_prime(rnd,1,callback,ctx,cb_arg);
if (j == -1) goto err;
if (j == 0) goto loop;
if (callback != NULL) callback(2,c1-1,cb_arg);
- /* We have a strong prime test pass */
+ /* We have a safe prime test pass */
}
}
/* we have a prime :-) */
- ret=rnd;
+ found = 1;
err:
- if ((ret == NULL) && (rnd != NULL)) BN_free(rnd);
+ if (!found && (ret == NULL) && (rnd != NULL)) BN_free(rnd);
BN_free(&t);
if (ctx != NULL) BN_CTX_free(ctx);
- return(ret);
+ return(found ? rnd : NULL);
}
int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),
BN_CTX *ctx=NULL,*ctx2=NULL;
BN_MONT_CTX *mont=NULL;
+ if (checks == BN_prime_checks)
+ {
+ int bits = BN_num_bits(a);
+ checks = BN_prime_checks_size(bits);
+ }
+
if (!BN_is_odd(a))
return(0);
if (ctx_passed != NULL)
return(ret);
}
-#define RECP_MUL_MOD
-
static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2,
BN_MONT_CTX *mont)
{
return(ret);
}
-static int probable_prime_dh_strong(BIGNUM *p, int bits, BIGNUM *padd,
+static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd,
BIGNUM *rem, BN_CTX *ctx)
{
int i,ret=0;
}
#if 0
-static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx)
+
+#define RECP_MUL_MOD
+
+static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,
+ BN_CTX *unused, BN_MONT_CTX *unused2)
{
- int k,i,nb,ret= -1;
+ int k,i,ret= -1;
BIGNUM *d,*dd,*tmp;
- BIGNUM *d1,*d2,*x,*n1,*inv;
+ BIGNUM *d1,*d2,*x,*n1;
+ BN_RECP_CTX recp;
d1= &(ctx->bn[ctx->tos]);
d2= &(ctx->bn[ctx->tos+1]);
x= &(ctx->bn[ctx->tos+2]);
n1= &(ctx->bn[ctx->tos+3]);
- inv=&(ctx->bn[ctx->tos+4]);
- ctx->tos+=5;
+ ctx->tos+=4;
d=d1;
dd=d2;
/* i=BN_num_bits(n); */
#ifdef RECP_MUL_MOD
- nb=BN_reciprocal(inv,n,ctx); /**/
- if (nb == -1) goto err;
+ BN_RECP_CTX_init(&recp);
+ if (BN_RECP_CTX_set(&recp,n,ctx) <= 0) goto err;
#endif
for (i=k-1; i>=0; i--)
#ifndef RECP_MUL_MOD
if (!BN_mod_mul(dd,d,d,n,ctx)) goto err;
#else
- if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err;
+ if (!BN_mod_mul_reciprocal(dd,d,d,&recp,ctx)) goto err;
#endif
if ( BN_is_one(dd) &&
!BN_is_one(x) &&
#ifndef RECP_MUL_MOD
if (!BN_mod_mul(d,dd,a,n,ctx)) goto err;
#else
- if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err;
+ if (!BN_mod_mul_reciprocal(d,dd,a,&recp,ctx)) goto err;
#endif
}
else
else i=1;
ret=i;
err:
- ctx->tos-=5;
+ ctx->tos-=4;
+#ifdef RECP_MUL_MOD
+ BN_RECP_CTX_free(&recp);
+#endif
return(ret);
}
#endif