diff options
Diffstat (limited to 'cipher')
| -rw-r--r-- | cipher/ChangeLog | 8 | ||||
| -rw-r--r-- | cipher/dsa.c | 45 | ||||
| -rw-r--r-- | cipher/elgamal.c | 41 | ||||
| -rw-r--r-- | cipher/random.c | 52 | ||||
| -rw-r--r-- | cipher/random.h | 1 |
5 files changed, 119 insertions, 28 deletions
diff --git a/cipher/ChangeLog b/cipher/ChangeLog index 77a3e4b82..2ce644a43 100644 --- a/cipher/ChangeLog +++ b/cipher/ChangeLog @@ -1,3 +1,11 @@ +Fri Jul 2 11:45:54 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> + + + * dsa.c (gen_k): Changed algorithm to consume less random bytes + * elgamal.c (gen_k): Ditto. + + * random.c (random_dump_stats): New. + Thu Jul 1 12:47:31 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> diff --git a/cipher/dsa.c b/cipher/dsa.c index cbd90ac5f..9154f49d6 100644 --- a/cipher/dsa.c +++ b/cipher/dsa.c @@ -66,30 +66,49 @@ static MPI gen_k( MPI q ) { MPI k = mpi_alloc_secure( mpi_get_nlimbs(q) ); - unsigned nbits = mpi_get_nbits(q); + unsigned int nbits = mpi_get_nbits(q); + unsigned int nbytes = (nbits+7)/8; + char *rndbuf = NULL; if( DBG_CIPHER ) log_debug("choosing a random k "); for(;;) { if( DBG_CIPHER ) progress('.'); - { char *p = get_random_bits( nbits, 1, 1 ); - mpi_set_buffer( k, p, (nbits+7)/8, 0 ); - m_free(p); - /* make sure that the number is of the exact lenght */ - if( mpi_test_bit( k, nbits-1 ) ) - mpi_set_highbit( k, nbits-1 ); - else { - mpi_set_highbit( k, nbits-1 ); - mpi_clear_bit( k, nbits-1 ); - } + + if( !rndbuf || nbits < 32 ) { + m_free(rndbuf); + rndbuf = get_random_bits( nbits, 1, 1 ); + } + else { /* change only some of the higher bits */ + /* we could imporove this by directly requesting more memory + * at the first call to get_random_bits() and use this the here + * maybe it is easier to do this directly in random.c */ + char *pp = get_random_bits( 32, 1, 1 ); + memcpy( rndbuf,pp, 4 ); + m_free(pp); } - if( !(mpi_cmp( k, q ) < 0) ) /* check: k < q */ + mpi_set_buffer( k, rndbuf, nbytes, 0 ); + if( mpi_test_bit( k, nbits-1 ) ) + mpi_set_highbit( k, nbits-1 ); + else { + mpi_set_highbit( k, nbits-1 ); + mpi_clear_bit( k, nbits-1 ); + } + + if( !(mpi_cmp( k, q ) < 0) ) { /* check: k < q */ + if( DBG_CIPHER ) + progress('+'); continue; /* no */ - if( !(mpi_cmp_ui( k, 0 ) > 0) ) /* check: k > 0 */ + } + if( !(mpi_cmp_ui( k, 0 ) > 0) ) { /* check: k > 0 */ + if( DBG_CIPHER ) + progress('-'); continue; /* no */ + } break; /* okay */ } + m_free(rndbuf); if( DBG_CIPHER ) progress('\n'); diff --git a/cipher/elgamal.c b/cipher/elgamal.c index 0e6b992c0..4b9758628 100644 --- a/cipher/elgamal.c +++ b/cipher/elgamal.c @@ -108,7 +108,9 @@ gen_k( MPI p ) MPI k = mpi_alloc_secure( 0 ); MPI temp = mpi_alloc( mpi_get_nlimbs(p) ); MPI p_1 = mpi_copy(p); - unsigned nbits = mpi_get_nbits(p); + unsigned int nbits = mpi_get_nbits(p); + unsigned int nbytes = (nbits+7)/8; + char *rndbuf = NULL; if( DBG_CIPHER ) log_debug("choosing a random k "); @@ -116,9 +118,21 @@ gen_k( MPI p ) for(;;) { if( DBG_CIPHER ) progress('.'); - { char *pp = get_random_bits( nbits, 1, 1 ); - mpi_set_buffer( k, pp, (nbits+7)/8, 0 ); + if( !rndbuf || nbits < 32 ) { + m_free(rndbuf); + rndbuf = get_random_bits( nbits, 1, 1 ); + } + else { /* change only some of the higher bits */ + /* we could imporove this by directly requesting more memory + * at the first call to get_random_bits() and use this the here + * maybe it is easier to do this directly in random.c */ + char *pp = get_random_bits( 32, 1, 1 ); + memcpy( rndbuf,pp, 4 ); m_free(pp); + } + mpi_set_buffer( k, rndbuf, nbytes, 0 ); + + for(;;) { /* make sure that the number is of the exact lenght */ if( mpi_test_bit( k, nbits-1 ) ) mpi_set_highbit( k, nbits-1 ); @@ -126,14 +140,23 @@ gen_k( MPI p ) mpi_set_highbit( k, nbits-1 ); mpi_clear_bit( k, nbits-1 ); } + if( !(mpi_cmp( k, p_1 ) < 0) ) { /* check: k < (p-1) */ + if( DBG_CIPHER ) + progress('+'); + break; /* no */ + } + if( !(mpi_cmp_ui( k, 0 ) > 0) ) { /* check: k > 0 */ + if( DBG_CIPHER ) + progress('-'); + break; /* no */ + } + if( mpi_gcd( temp, k, p_1 ) ) + goto found; /* okay, k is relatively prime to (p-1) */ + mpi_add_ui( k, k, 1 ); } - if( !(mpi_cmp( k, p_1 ) < 0) ) /* check: k < (p-1) */ - continue; /* no */ - if( !(mpi_cmp_ui( k, 0 ) > 0) ) /* check: k > 0 */ - continue; /* no */ - if( mpi_gcd( temp, k, p_1 ) ) - break; /* okay, k is relatively prime to (p-1) */ } + found: + m_free(rndbuf); if( DBG_CIPHER ) progress('\n'); mpi_free(p_1); diff --git a/cipher/random.c b/cipher/random.c index 5fa45ea86..8ade26c11 100644 --- a/cipher/random.c +++ b/cipher/random.c @@ -104,6 +104,18 @@ static void read_random_source( int requester, size_t length, int level); static int gather_faked( void (*add)(const void*, size_t, int), int requester, size_t length, int level ); +static struct { + ulong mixrnd; + ulong mixkey; + ulong slowpolls; + ulong fastpolls; + ulong getbytes1; + ulong ngetbytes1; + ulong getbytes2; + ulong ngetbytes2; + ulong addbytes; + ulong naddbytes; +} rndstats; static void initialize(void) @@ -119,6 +131,19 @@ initialize(void) cipher_modules_constructor(); } + +void +random_dump_stats() +{ + fprintf(stderr, + "random usage: poolsize=%d mixed=%lu polls=%lu/%lu added=%lu/%lu\n" + " outmix=%lu getlvl1=%lu/%lu getlvl2=%lu/%lu\n", + POOLSIZE, rndstats.mixrnd, rndstats.slowpolls, rndstats.fastpolls, + rndstats.naddbytes, rndstats.addbytes, + rndstats.mixkey, rndstats.ngetbytes1, rndstats.getbytes1, + rndstats.ngetbytes2, rndstats.getbytes2 ); +} + void secure_random_alloc() { @@ -175,6 +200,15 @@ get_random_bits( size_t nbits, int level, int secure ) if( quick_test && level > 1 ) level = 1; MASK_LEVEL(level); + if( level == 1 ) { + rndstats.getbytes1 += nbytes; + rndstats.ngetbytes1++; + } + else if( level >= 2 ) { + rndstats.getbytes2 += nbytes; + rndstats.ngetbytes2++; + } + buf = secure && secure_alloc ? m_alloc_secure( nbytes ) : m_alloc( nbytes ); for( p = buf; nbytes > 0; ) { size_t n = nbytes > POOLSIZE? POOLSIZE : nbytes; @@ -265,21 +299,23 @@ read_pool( byte *buffer, size_t length, int level ) i < POOLWORDS; i++, dp++, sp++ ) *dp = *sp + ADD_VALUE; /* must mix both pools */ - mix_pool(rndpool); - mix_pool(keypool); + mix_pool(rndpool); rndstats.mixrnd++; + mix_pool(keypool); rndstats.mixkey++; memcpy( buffer, keypool, length ); } else { /* mix the pool (if add_randomness() didn't it) */ - if( !just_mixed ) + if( !just_mixed ) { mix_pool(rndpool); + rndstats.mixrnd++; + } /* create a new pool */ for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool; i < POOLWORDS; i++, dp++, sp++ ) *dp = *sp + ADD_VALUE; /* and mix both pools */ - mix_pool(rndpool); - mix_pool(keypool); + mix_pool(rndpool); rndstats.mixrnd++; + mix_pool(keypool); rndstats.mixkey++; /* read the required data * we use a readpoiter to read from a different postion each * time */ @@ -308,13 +344,15 @@ add_randomness( const void *buffer, size_t length, int source ) if( !is_initialized ) initialize(); + rndstats.addbytes += length; + rndstats.naddbytes++; while( length-- ) { rndpool[pool_writepos++] = *p++; if( pool_writepos >= POOLSIZE ) { if( source > 1 ) pool_filled = 1; pool_writepos = 0; - mix_pool(rndpool); + mix_pool(rndpool); rndstats.mixrnd++; just_mixed = !length; } } @@ -325,6 +363,7 @@ add_randomness( const void *buffer, size_t length, int source ) static void random_poll() { + rndstats.slowpolls++; read_random_source( 2, POOLSIZE/5, 1 ); } @@ -335,6 +374,7 @@ fast_random_poll() static void (*fnc)( void (*)(const void*, size_t, int), int) = NULL; static int initialized = 0; + rndstats.fastpolls++; if( !initialized ) { if( !is_initialized ) initialize(); diff --git a/cipher/random.h b/cipher/random.h index 4b1d56d57..64ffdb5e6 100644 --- a/cipher/random.h +++ b/cipher/random.h @@ -23,6 +23,7 @@ #include "types.h" /*-- random.c --*/ +void random_dump_stats(void); void secure_random_alloc(void); int quick_random_gen( int onoff ); int random_is_faked(void); |