diff options
| -rw-r--r-- | cipher/primegen.c | 71 | ||||
| -rw-r--r-- | configure.in | 2 | ||||
| -rw-r--r-- | mpi/mpi-div.c | 31 | ||||
| -rw-r--r-- | mpi/mpi-internal.h | 7 | ||||
| -rw-r--r-- | mpi/mpi-scan.c | 26 |
5 files changed, 116 insertions, 21 deletions
diff --git a/cipher/primegen.c b/cipher/primegen.c index 0173b3d0..d69f09ac 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -28,7 +28,7 @@ #include "cipher.h" static int no_of_small_prime_numbers; -static int rabin_miller( MPI n ); +static int is_not_prime( MPI n, unsigned nbits, int steps, int *count ); static MPI gen_prime( unsigned nbits, int mode ); @@ -50,7 +50,6 @@ generate_public_prime( unsigned nbits ) static MPI gen_prime( unsigned nbits, int secret ) { - unsigned nlimbs; MPI prime, val_2, val_3, result; int i; @@ -111,22 +110,9 @@ gen_prime( unsigned nbits, int secret ) continue; /* stepping (fermat test failed) */ if( DBG_CIPHER ) fputc('+', stderr); - /* and a second one */ - count2++; - mpi_powm( result, val_3, prime, prime ); - if( mpi_cmp_ui(result, 3) ) - continue; /* stepping (fermat test failed) */ - if( DBG_CIPHER ) - fputc('+', stderr); - /* perform Rabin-Miller tests */ - for(i=5; i > 0; i-- ) { - if( DBG_CIPHER ) - fputc('+', stderr); - if( rabin_miller(prime) ) - break; - } - if( !i ) { + /* perform stronger tests */ + if( !is_not_prime(prime, nbits, 5, &count2 ) ) { if( !mpi_test_bit( prime, nbits-1 ) ) { if( DBG_CIPHER ) { fputc('\n', stderr); @@ -136,7 +122,7 @@ gen_prime( unsigned nbits, int secret ) } if( DBG_CIPHER ) { fputc('\n', stderr); - log_debug("performed %u simple and %u Fermat/Rabin-Miller tests\n", + log_debug("performed %u simple and %u stronger tests\n", count1, count2 ); log_mpidump("found prime: ", prime ); } @@ -158,8 +144,53 @@ gen_prime( unsigned nbits, int secret ) * Return 1 if n is not a prime */ static int -rabin_miller( MPI n ) +is_not_prime( MPI n, unsigned nbits, int steps, int *count ) { - return 0; + MPI x = mpi_alloc( mpi_get_nlimbs( n ) ); + MPI y = mpi_alloc( mpi_get_nlimbs( n ) ); + MPI z = mpi_alloc( mpi_get_nlimbs( n ) ); + MPI nminus1 = mpi_alloc( mpi_get_nlimbs( n ) ); + MPI a2 = mpi_alloc_set_ui( 2 ); + MPI q; + unsigned i, j, k; + int rc = 1; + + mpi_sub_ui( nminus1, n, 1 ); + + /* find q and k, so that n = 1 + 2^k * q */ + q = mpi_copy( nminus1 ); + k = mpi_trailing_zeros( q ); + mpi_tdiv_q_2exp(q, q, k); + + for(i=0 ; i < steps; i++ ) { + ++*count; + do { + mpi_set_bytes( x, nbits, get_random_byte, 0 ); + } while( mpi_cmp( x, n ) < 0 && mpi_cmp_ui( x, 1 ) > 0 ); + mpi_powm( y, x, q, n); + if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) { + for( j=1; j < k; j++ ) { + mpi_powm(y, y, a2, n); + if( !mpi_cmp_ui( y, 1 ) ) + goto leave; /* not a prime */ + if( !mpi_cmp( y, nminus1 ) ) + break; /* may be a prime */ + } + if( j == k ) + goto leave; + } + if( DBG_CIPHER ) + fputc('+', stderr); + } + rc = 0; /* may be a prime */ + + leave: + mpi_free( x ); + mpi_free( y ); + mpi_free( z ); + mpi_free( nminus1 ); + mpi_free( q ); + + return rc; } diff --git a/configure.in b/configure.in index 2f77c068..4575bc88 100644 --- a/configure.in +++ b/configure.in @@ -18,8 +18,8 @@ AC_ARG_ENABLE(m-debug, [ --enable-m-debug Enable debugging of memory allocation]) if test "$enableval" = y || test "$enableval" = yes; then AC_DEFINE(M_DEBUG) - CFLAGS="-g" fi +CFLAGS="-g" dnl AC_CANONICAL_HOST diff --git a/mpi/mpi-div.c b/mpi/mpi-div.c index 2b39cb4c..52737574 100644 --- a/mpi/mpi-div.c +++ b/mpi/mpi-div.c @@ -278,6 +278,37 @@ mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den) mpi_free_limb_space(marker[--markidx]); } +void +mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count ) +{ + mpi_size_t usize, wsize; + mpi_size_t limb_cnt; + + usize = u->nlimbs; + limb_cnt = count / BITS_PER_MPI_LIMB; + wsize = usize - limb_cnt; + if( limb_cnt >= usize ) + w->nlimbs = 0; + else { + mpi_ptr_t wp; + mpi_ptr_t up; + + RESIZE_IF_NEEDED( w, wsize ); + wp = w->d; + up = u->d; + + count %= BITS_PER_MPI_LIMB; + if( count ) { + mpihelp_rshift( wp, up + limb_cnt, wsize, count ); + wsize -= !wp[wsize - 1]; + } + else { + MPN_COPY_INCR( wp, up + limb_cnt, wsize); + } + + w->nlimbs = wsize; + } +} /**************** * Check wether dividend is divisible by divisor diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h index 2748ddad..93ed688a 100644 --- a/mpi/mpi-internal.h +++ b/mpi/mpi-internal.h @@ -54,6 +54,13 @@ typedef int mpi_size_t; /* (must be a signed type) */ (d)[_i] = (s)[_i]; \ } while(0) +#define MPN_COPY_INCR( d, s, n) \ + do { \ + mpi_size_t _i; \ + for( _i = 0; _i < (n); _i++ ) \ + (d)[_i] = (d)[_i]; \ + } while (0) + #define MPN_COPY_DECR( d, s, n ) \ do { \ mpi_size_t _i; \ diff --git a/mpi/mpi-scan.c b/mpi/mpi-scan.c index 8626032a..b9745e1a 100644 --- a/mpi/mpi-scan.c +++ b/mpi/mpi-scan.c @@ -22,6 +22,7 @@ #include <stdio.h> #include <stdlib.h> #include "mpi-internal.h" +#include "longlong.h" /**************** * Scan through an mpi and return byte for byte. a -1 is returned to indicate @@ -86,3 +87,28 @@ mpi_putbyte( MPI a, unsigned index, int c ) abort(); /* index out of range */ } + +/**************** + * Count the number of zerobits at the low end of A + */ +unsigned +mpi_trailing_zeros( MPI a ) +{ + unsigned n, count = 0; + + for(n=0; n < a->nlimbs; n++ ) { + if( a->d[n] ) { + unsigned nn; + mpi_limb_t alimb = a->d[n]; + + count_trailing_zeros( nn, alimb ); + count += nn; + break; + } + count += BITS_PER_MPI_LIMB; + } + return count; + +} + + |