diff options
| -rw-r--r-- | PROJECTS | 2 | ||||
| -rw-r--r-- | THANKS | 2 | ||||
| -rw-r--r-- | cipher/ChangeLog | 7 | ||||
| -rw-r--r-- | cipher/primegen.c | 93 | ||||
| -rw-r--r-- | doc/FAQ | 3 | ||||
| -rw-r--r-- | doc/gpg.1pod | 2 | ||||
| -rw-r--r-- | include/mpi.h | 1 | ||||
| -rw-r--r-- | mpi/ChangeLog | 4 | ||||
| -rw-r--r-- | mpi/mpiutil.c | 30 |
9 files changed, 90 insertions, 54 deletions
@@ -26,8 +26,6 @@ * Split key support (n-out-of-m) - * Check Berkeley DB - it is in glibc - any licensing problems? - * add an option to re-create a public key from a secret key; we can do this in trustdb.c:verify_own_keys. (special tool?) @@ -67,7 +67,7 @@ QingLong qinglong@bolizm.ihep.su Ralph Gillen gillen@theochem.uni-duesseldorf.de Rat ratinox@peorth.gweep.net Reinhard Wobst R.Wobst@ifw-dresden.de -Rémi Guyomarch rguyomarch@ifn.fr +Rémi Guyomarch rguyom@mail.dotcom.fr Reuben Sumner rasumner@wisdom.weizmann.ac.il Roddy Strachan roddy@satlink.com.au Roland Rosenfeld roland@spinnaker.rhein.de diff --git a/cipher/ChangeLog b/cipher/ChangeLog index 52dd247de..34d30af24 100644 --- a/cipher/ChangeLog +++ b/cipher/ChangeLog @@ -1,3 +1,10 @@ +Tue May 4 15:47:53 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> + + * primegen.c (gen_prime): Readded the Fermat test. Fixed the bug + that we didn't correct for step when passing the prime to the + Rabin-Miller test which led to bad performance (Stefan Keller). + (check_prime): Add a first Fermat test. + Sun Apr 18 10:11:28 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> * cipher.c (cipher_setiv): Add ivlen arg, changed all callers. diff --git a/cipher/primegen.c b/cipher/primegen.c index c7b5b757d..9019e2839 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -34,7 +34,7 @@ static int no_of_small_prime_numbers; static MPI gen_prime( unsigned nbits, int mode, int randomlevel ); -static int check_prime( MPI prime ); +static int check_prime( MPI prime, MPI val_2 ); static int is_prime( MPI n, int steps, int *count ); static void m_out_of_n( char *array, int m, int n ); @@ -89,6 +89,7 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits, int count1, count2; unsigned nprime; unsigned req_qbits = qbits; /* the requested q bits size */ + MPI val_2 = mpi_alloc_set_ui( 2 ); /* find number of needed prime factors */ for(n=1; (pbits - qbits - 1) / n >= qbits; n++ ) @@ -186,7 +187,7 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits, } else count2 = 0; - } while( !(nprime == pbits && check_prime( prime )) ); + } while( !(nprime == pbits && check_prime( prime, val_2 )) ); if( DBG_CIPHER ) { putc('\n', stderr); @@ -261,6 +262,7 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits, mpi_free( pool[i] ); m_free( pool ); m_free(perms); + mpi_free(val_2); return prime; } @@ -270,7 +272,7 @@ static MPI gen_prime( unsigned nbits, int secret, int randomlevel ) { unsigned nlimbs; - MPI prime, val_2, val_3, result; + MPI prime, ptest, pminus1, val_2, val_3, result; int i; unsigned x, step; unsigned count1, count2; @@ -286,19 +288,17 @@ gen_prime( unsigned nbits, int secret, int randomlevel ) mods = m_alloc( no_of_small_prime_numbers * sizeof *mods ); /* make nbits fit into MPI implementation */ nlimbs = (nbits + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB; - val_2 = mpi_alloc( nlimbs ); - mpi_set_ui(val_2, 2); - val_3 = mpi_alloc( nlimbs ); - mpi_set_ui(val_3, 3); - result = mpi_alloc( nlimbs ); + 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; - /* enter (endless) loop */ - for(;;) { + for(;;) { /* try forvever */ int dotcount=0; /* generate a random number */ - /*mpi_set_bytes( prime, nbits, get_random_byte, randomlevel );*/ { char *p = get_random_bits( nbits, randomlevel, secret ); mpi_set_buffer( prime, p, (nbits+7)/8, 0 ); m_free(p); @@ -312,6 +312,7 @@ gen_prime( unsigned nbits, int secret, int randomlevel ) 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++; @@ -322,40 +323,31 @@ gen_prime( unsigned nbits, int secret, int randomlevel ) break; } if( x ) - continue; /* found a multiple of a already known prime */ + continue; /* found a multiple of an already known prime */ - mpi_add_ui( prime, prime, step ); + mpi_add_ui( ptest, prime, step ); - #if 0 - /* do a Fermat test */ + /* do a faster Fermat test */ count2++; - mpi_powm( result, val_2, prime, prime ); - if( mpi_cmp_ui(result, 2) ) - continue; /* stepping (fermat test failed) */ - fputc('+', stderr); - #endif - - /* perform stronger tests */ - if( is_prime(prime, 5, &count2 ) ) { - if( !mpi_test_bit( prime, nbits-1 ) ) { - if( 0 && DBG_CIPHER ) { + 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 ) ) { fputc('\n', stderr); log_debug("overflow in prime generation\n"); - break; /* step loop, cont with a new prime */ + break; /* step loop, continue with a new prime */ } - } - if( 0 && DBG_CIPHER ) { - log_debug("performed %u simple and %u stronger tests\n", - count1, count2 ); - log_mpidump("found prime: ", prime ); + mpi_free(val_2); + mpi_free(val_3); + mpi_free(result); + mpi_free(pminus1); + mpi_free(prime); + m_free(mods); + return ptest; } - - mpi_free(val_2); - mpi_free(val_3); - mpi_free(result); - m_free(mods); - return prime; } if( ++dotcount == 10 ) { fputc('.', stderr); @@ -370,7 +362,7 @@ gen_prime( unsigned nbits, int secret, int randomlevel ) * Returns: true if this may be a prime */ static int -check_prime( MPI prime ) +check_prime( MPI prime, MPI val_2 ) { int i; unsigned x; @@ -382,19 +374,20 @@ check_prime( MPI prime ) return 0; } - #if 0 - result = mpi_alloc( mpi_get_nlimbs(prime) ); - val_2 = mpi_alloc_set_ui( 2 ); - mpi_powm( result, val_2, prime, prime ); - if( mpi_cmp_ui(result, 2) ) { - mpi_free(result); - mpi_free(val_2); - return 0; + /* a quick fermat test */ + { + MPI result = mpi_alloc_like( prime ); + MPI pminus1 = mpi_alloc_like( prime ); + mpi_sub_ui( pminus1, prime, 1); + mpi_powm( result, val_2, pminus1, prime ); + mpi_free( pminus1 ); + if( mpi_cmp_ui( result, 1 ) ) { /* if composite */ + mpi_free( result ); + fputc('.', stderr); + return 0; + } + mpi_free( result ); } - mpi_free(result); - mpi_free(val_2); - fputc('+', stderr); - #endif /* perform stronger tests */ if( is_prime(prime, 5, &count ) ) @@ -81,7 +81,8 @@ signatures this is sufficient as the size of the hash is probably the weakest link if the keysize is larger than 1024 bits. Encryption keys may have greater sizes, - but you should than check the fingerprint of this key. + but you should than check the fingerprint of this key: + "gpg --fingerprint --fingerprint <user ID>". Q: Why are some signatures with an ELG-E key valid? A: These are ElGamal Key generated by GNUPG in v3 (rfc1991) diff --git a/doc/gpg.1pod b/doc/gpg.1pod index 9ec4d2ef4..9e8abc44b 100644 --- a/doc/gpg.1pod +++ b/doc/gpg.1pod @@ -93,6 +93,8 @@ B<--fingerprint> [I<names>] same output as B<list-keys> but with the additional output of a line with the fingerprint. May also be combined with B<--list-sigs> or B<--check-sigs>. + If this command is given twice, the fingerprints of all + secondary keys are listed too. B<--list-packets> List only the sequence of packets. This is mainly diff --git a/include/mpi.h b/include/mpi.h index ae32d1ba3..e845bec50 100644 --- a/include/mpi.h +++ b/include/mpi.h @@ -92,6 +92,7 @@ void *mpi_get_opaque( MPI a, int *len ); #define mpi_is_secure(a) ((a) && ((a)->flags&1)) void mpi_set_secure( MPI a ); void mpi_clear( MPI a ); +MPI mpi_alloc_like( MPI a ); void mpi_set( MPI w, MPI u); void mpi_set_ui( MPI w, ulong u); MPI mpi_alloc_set_ui( unsigned long u); diff --git a/mpi/ChangeLog b/mpi/ChangeLog index 7d66b809b..10e3bddd6 100644 --- a/mpi/ChangeLog +++ b/mpi/ChangeLog @@ -1,3 +1,7 @@ +Tue May 4 15:47:53 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> + + * mpiutil.c (mpi_alloc_like): New. + Mon Apr 26 17:48:15 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> * mpih-add.c, mpih-sub.c: Removed diff --git a/mpi/mpiutil.c b/mpi/mpiutil.c index 82ba87112..cbbe10d25 100644 --- a/mpi/mpiutil.c +++ b/mpi/mpiutil.c @@ -323,6 +323,36 @@ mpi_copy( MPI a ) } +/**************** + * This function allocates an MPI which is optimized to hold + * a value as large as the one given in the arhgument and allocates it + * with the same flags as A. + */ +MPI +mpi_alloc_like( MPI a ) +{ + MPI b; + + if( a && (a->flags & 4) ) { + void *p = m_is_secure(a->d)? m_alloc_secure( a->nbits ) + : m_alloc( a->nbits ); + memcpy( p, a->d, a->nbits ); + b = mpi_set_opaque( NULL, p, a->nbits ); + } + else if( a ) { + b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs ) + : mpi_alloc( a->nlimbs ); + b->nlimbs = 0; + b->sign = 0; + b->flags = a->flags; + b->nbits = 0; + } + else + b = NULL; + return b; +} + + void mpi_set( MPI w, MPI u) { |