static MPI
gen_prime( unsigned int nbits, int secret, int randomlevel )
{
unsigned nlimbs;
MPI prime, ptest, pminus1, val_2, val_3, result;
int i;
unsigned x, step;
int count1, count2;
int *mods;
if( 0 && DBG_CIPHER )
log_debug("generate a prime of %u bits ", nbits );
if (nbits < 16)
{
log_error (_("can't generate a prime with less than %d bits\n"), 16);
exit (2);
}
if( !no_of_small_prime_numbers ) {
for(i=0; small_prime_numbers[i]; i++ )
no_of_small_prime_numbers++;
}
mods = xmalloc( no_of_small_prime_numbers * sizeof *mods );
/* Make nbits fit into MPI implementation. */
nlimbs = mpi_nlimb_hint_from_nbits (nbits);
val_2 = mpi_alloc_set_ui( 2 );
val_3 = mpi_alloc_set_ui( 3);
prime = secret? mpi_alloc_secure( nlimbs ): mpi_alloc( nlimbs );
result = mpi_alloc_like( prime );
pminus1= mpi_alloc_like( prime );
ptest = mpi_alloc_like( prime );
count1 = count2 = 0;
for(;;) { /* try forvever */
int dotcount=0;
/* generate a random number */
{ char *p = get_random_bits( nbits, randomlevel, secret );
mpi_set_buffer( prime, p, (nbits+7)/8, 0 );
xfree(p);
}
/* Set high order bit to 1, set low order bit to 0.
If we are generating a secret prime we are most probably
doing that for RSA, to make sure that the modulus does have
the requested keysize we set the 2 high order bits */
mpi_set_highbit( prime, nbits-1 );
if (secret)
mpi_set_bit (prime, nbits-2);
mpi_set_bit( prime, 0 );
/* calculate all remainders */
for(i=0; (x = small_prime_numbers[i]); i++ )
mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
/* now try some primes starting with prime */
for(step=0; step < 20000; step += 2 ) {
/* check against all the small primes we have in mods */
count1++;
for(i=0; (x = small_prime_numbers[i]); i++ ) {
while( mods[i] + step >= x )
mods[i] -= x;
if( !(mods[i] + step) )
break;
}
if( x )
continue; /* found a multiple of an already known prime */
mpi_add_ui( ptest, prime, step );
/* do a faster Fermat test */
count2++;
mpi_sub_ui( pminus1, ptest, 1);
mpi_powm( result, val_2, pminus1, ptest );
if( !mpi_cmp_ui( result, 1 ) ) { /* not composite */
/* perform stronger tests */
if( is_prime(ptest, 5, &count2 ) ) {
if( !mpi_test_bit( ptest, nbits-1 ) ) {
progress('\n');
log_debug("overflow in prime generation\n");
break; /* step loop, continue with a new prime */
}
mpi_free(val_2);
mpi_free(val_3);
mpi_free(result);
mpi_free(pminus1);
mpi_free(prime);
xfree(mods);
return ptest;
}
}
if( ++dotcount == 10 ) {
progress('.');
dotcount = 0;
}
}
progress(':'); /* restart with a new random value */
}
}
