diff options
-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 | ||||
-rw-r--r-- | mpi/ChangeLog | 6 | ||||
-rw-r--r-- | mpi/mpi-bit.c | 48 | ||||
-rw-r--r-- | mpi/mpi-internal.h | 5 | ||||
-rw-r--r-- | mpi/mpi-mpow.c | 141 | ||||
-rw-r--r-- | mpi/mpi-mul.c | 1 |
10 files changed, 300 insertions, 48 deletions
diff --git a/cipher/ChangeLog b/cipher/ChangeLog index 77a3e4b8..2ce644a4 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 cbd90ac5..9154f49d 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 0e6b992c..4b975862 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 5fa45ea8..8ade26c1 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 4b1d56d5..64ffdb5e 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); diff --git a/mpi/ChangeLog b/mpi/ChangeLog index 959f3b48..1951dd3a 100644 --- a/mpi/ChangeLog +++ b/mpi/ChangeLog @@ -1,3 +1,9 @@ +Fri Jul 2 11:45:54 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> + + + * mpi-bit.c (mpi_lshift_limbs,mpi_rshift_limbs): New. + * mpi-mpow.c (barrett_mulm): New but diabled. + Tue Jun 1 16:01:46 CEST 1999 Werner Koch <wk@isil.d.shuttle.de> * config.links (i[56]86*-*-freebsdelf*): New. diff --git a/mpi/mpi-bit.c b/mpi/mpi-bit.c index 00aa5d08..f1eff863 100644 --- a/mpi/mpi-bit.c +++ b/mpi/mpi-bit.c @@ -212,3 +212,51 @@ mpi_rshift( MPI x, MPI a, unsigned n ) x->nlimbs = xsize; } + +/**************** + * Shift A by COUNT limbs to the left + * This is used only within the MPI library + */ +void +mpi_lshift_limbs( MPI a, unsigned int count ) +{ + mpi_ptr_t ap = a->d; + int n = a->nlimbs; + int i; + + if( !count || !n ) + return; + + RESIZE_IF_NEEDED( a, n+count ); + + for( i = n-1; i >= 0; i-- ) + ap[i+count] = ap[i]; + for(i=0; i < count; i++ ) + ap[i] = 0; + a->nlimbs += count; +} + + +/**************** + * Shift A by COUNT limbs to the right + * This is used only within the MPI library + */ +void +mpi_rshift_limbs( MPI a, unsigned int count ) +{ + mpi_ptr_t ap = a->d; + mpi_size_t n = a->nlimbs; + unsigned int i; + + if( count >= n ) { + a->nlimbs = 0; + return; + } + + for( i = 0; i < n - count; i++ ) + ap[i] = ap[i+count]; + ap[i] = 0; + a->nlimbs -= count; +} + + diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h index f73efb76..035d33cb 100644 --- a/mpi/mpi-internal.h +++ b/mpi/mpi-internal.h @@ -161,6 +161,11 @@ typedef int mpi_size_t; /* (must be a signed type) */ #endif void mpi_assign_limb_space( MPI a, mpi_ptr_t ap, unsigned nlimbs ); +/*-- mpi-bit.c --*/ +void mpi_rshift_limbs( MPI a, unsigned int count ); +void mpi_lshift_limbs( MPI a, unsigned int count ); + + /*-- mpihelp-add.c --*/ mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, mpi_limb_t s2_limb ); diff --git a/mpi/mpi-mpow.c b/mpi/mpi-mpow.c index 689a7600..a8c561dd 100644 --- a/mpi/mpi-mpow.c +++ b/mpi/mpi-mpow.c @@ -1,5 +1,5 @@ /* mpi-mpow.c - MPI functions - * Copyright (C) 1998 Free Software Foundation, Inc. + * Copyright (C) 1998, 1999 Free Software Foundation, Inc. * * This file is part of GnuPG. * @@ -25,6 +25,22 @@ #include "longlong.h" #include <assert.h> +/* Barrett is slower than the classical way. It can be tweaked by + * using partial multiplications + */ +/*#define USE_BARRETT*/ + + + +#ifdef USE_BARRETT +static void barrett_mulm( MPI w, MPI u, MPI v, MPI m, MPI y, int k, MPI r1, MPI r2 ); +static MPI init_barrett( MPI m, int *k, MPI *r1, MPI *r2 ); +static int calc_barrett( MPI r, MPI x, MPI m, MPI y, int k, MPI r1, MPI r2 ); +#else +#define barrett_mulm( w, u, v, m, y, k, r1, r2 ) mpi_mulm( (w), (u), (v), (m) ) +#endif + + static int build_index( MPI *exparray, int k, int i, int t ) { @@ -52,6 +68,10 @@ mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m) int i, j, idx; MPI *G; /* table with precomputed values of size 2^k */ MPI tmp; + #ifdef USE_BARRETT + MPI barrett_y, barrett_r1, barrett_r2; + int barrett_k; + #endif for(k=0; basearray[k]; k++ ) ; @@ -68,27 +88,15 @@ mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m) assert( k < 10 ); G = m_alloc_clear( (1<<k) * sizeof *G ); - #if 0 - /* do the precomputation */ - G[0] = mpi_alloc_set_ui( 1 ); - for(i=1; i < (1<<k); i++ ) { - for(j=0; j < k; j++ ) { - if( (i & (1<<j) ) ) { - if( !G[i] ) - G[i] = mpi_copy( basearray[j] ); - else - mpi_mulm( G[i], G[i], basearray[j], m ); - } - } - if( !G[i] ) - G[i] = mpi_alloc(0); - } + #ifdef USE_BARRETT + barrett_y = init_barrett( m, &barrett_k, &barrett_r1, &barrett_r2 ); #endif /* and calculate */ tmp = mpi_alloc( mpi_get_nlimbs(m)+1 ); mpi_set_ui( res, 1 ); for(i = 1; i <= t; i++ ) { - mpi_mulm(tmp, res, res, m ); + barrett_mulm(tmp, res, res, m, barrett_y, barrett_k, + barrett_r1, barrett_r2 ); idx = build_index( exparray, k, i, t ); assert( idx >= 0 && idx < (1<<k) ); if( !G[idx] ) { @@ -100,20 +108,115 @@ mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m) if( !G[idx] ) G[idx] = mpi_copy( basearray[j] ); else - mpi_mulm( G[idx], G[idx], basearray[j], m ); + barrett_mulm( G[idx], G[idx], basearray[j], + m, barrett_y, barrett_k, barrett_r1, barrett_r2 ); } } if( !G[idx] ) G[idx] = mpi_alloc(0); } } - mpi_mulm(res, tmp, G[idx], m ); + barrett_mulm(res, tmp, G[idx], m, barrett_y, barrett_k, barrett_r1, barrett_r2 ); } /* cleanup */ mpi_free(tmp); + #ifdef USE_BARRETT + mpi_free(barrett_y); + mpi_free(barrett_r1); + mpi_free(barrett_r2); + #endif for(i=0; i < (1<<k); i++ ) mpi_free(G[i]); m_free(G); } + + +#ifdef USE_BARRETT +static void +barrett_mulm( MPI w, MPI u, MPI v, MPI m, MPI y, int k, MPI r1, MPI r2 ) +{ + mpi_mul(w, u, v); + if( calc_barrett( w, w, m, y, k, r1, r2 ) ) + mpi_fdiv_r( w, w, m ); +} + +/**************** + * Barrett precalculation: y = floor(b^(2k) / m) + */ +static MPI +init_barrett( MPI m, int *k, MPI *r1, MPI *r2 ) +{ + MPI tmp; + + mpi_normalize( m ); + *k = mpi_get_nlimbs( m ); + tmp = mpi_alloc( *k + 1 ); + mpi_set_ui( tmp, 1 ); + mpi_lshift_limbs( tmp, 2 * *k ); + mpi_fdiv_q( tmp, tmp, m ); + *r1 = mpi_alloc( 2* *k + 1 ); + *r2 = mpi_alloc( 2* *k + 1 ); + return tmp; +} + +/**************** + * Barrett reduction: We assume that these conditions are met: + * Given x =(x_2k-1 ...x_0)_b + * m =(m_k-1 ....m_0)_b with m_k-1 != 0 + * Output r = x mod m + * Before using this function init_barret must be used to calucalte y and k. + * Returns: false = no error + * true = can't perform barret reduction + */ +static int +calc_barrett( MPI r, MPI x, MPI m, MPI y, int k, MPI r1, MPI r2 ) +{ + int xx = k > 3 ? k-3:0; + + mpi_normalize( x ); + if( mpi_get_nlimbs(x) > 2*k ) + return 1; /* can't do it */ + + /* 1. q1 = floor( x / b^k-1) + * q2 = q1 * y + * q3 = floor( q2 / b^k+1 ) + * Actually, we don't need qx, we can work direct on r2 + */ + mpi_set( r2, x ); + mpi_rshift_limbs( r2, k-1 ); + mpi_mul( r2, r2, y ); + mpi_rshift_limbs( r2, k+1 ); + + /* 2. r1 = x mod b^k+1 + * r2 = q3 * m mod b^k+1 + * r = r1 - r2 + * 3. if r < 0 then r = r + b^k+1 + */ + mpi_set( r1, x ); + if( r1->nlimbs > k+1 ) /* quick modulo operation */ + r1->nlimbs = k+1; + mpi_mul( r2, r2, m ); + if( r2->nlimbs > k+1 ) /* quick modulo operation */ + r2->nlimbs = k+1; + mpi_sub( r, r1, r2 ); + + if( mpi_is_neg( r ) ) { + MPI tmp; + + tmp = mpi_alloc( k + 2 ); + mpi_set_ui( tmp, 1 ); + mpi_lshift_limbs( tmp, k+1 ); + mpi_add( r, r, tmp ); + mpi_free(tmp); + } + + /* 4. while r >= m do r = r - m */ + while( mpi_cmp( r, m ) >= 0 ) + mpi_sub( r, r, m ); + + return 0; +} +#endif /* USE_BARRETT */ + diff --git a/mpi/mpi-mul.c b/mpi/mpi-mul.c index f8382492..df8eb258 100644 --- a/mpi/mpi-mul.c +++ b/mpi/mpi-mul.c @@ -189,7 +189,6 @@ mpi_mul( MPI w, MPI u, MPI v) } - void mpi_mulm( MPI w, MPI u, MPI v, MPI m) { |