diff options
author | Moritz Schulte <mo@g10code.com> | 2003-09-02 00:42:41 +0000 |
---|---|---|
committer | Moritz Schulte <mo@g10code.com> | 2003-09-02 00:42:41 +0000 |
commit | e567fa59ec8fe54ef43783178af5b2b5e7bc4eef (patch) | |
tree | 37b5c420b9042492d8ff08bb888185c7444528f5 /cipher | |
parent | 5dc9baf75b3170fe9db9bb4fd78947c26f11fb51 (diff) | |
download | libgcrypt-e567fa59ec8fe54ef43783178af5b2b5e7bc4eef.tar.gz |
2003-09-02 Moritz Schulte <mo@g10code.com>
* primegen.c (gcry_prime_check, gcry_prime_generate): New
functions.
(prime_generate_internal): New function, based on
_gcry_generate_elg_prime.
(_gcry_generate_elg_prime): Rewritten as a wrapper for
prime_generate_internal.
Diffstat (limited to 'cipher')
-rw-r--r-- | cipher/ChangeLog | 9 | ||||
-rw-r--r-- | cipher/primegen.c | 528 |
2 files changed, 365 insertions, 172 deletions
diff --git a/cipher/ChangeLog b/cipher/ChangeLog index 5cdcd9ae..4c2d9bc7 100644 --- a/cipher/ChangeLog +++ b/cipher/ChangeLog @@ -1,3 +1,12 @@ +2003-09-02 Moritz Schulte <mo@g10code.com> + + * primegen.c (gcry_prime_check, gcry_prime_generate): New + functions. + (prime_generate_internal): New function, based on + _gcry_generate_elg_prime. + (_gcry_generate_elg_prime): Rewritten as a wrapper for + prime_generate_internal. + 2003-08-28 Werner Koch <wk@gnupg.org> * pubkey.c (gcry_pk_encrypt): Don't include the flags list in the diff --git a/cipher/primegen.c b/cipher/primegen.c index 9575532d..e74eed93 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -24,10 +24,12 @@ */ #include <config.h> + #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> + #include "g10lib.h" #include "mpi.h" #include "cipher.h" @@ -180,205 +182,318 @@ _gcry_generate_public_prime( unsigned int nbits, * mode 0: Standard * 1: Make sure that at least one factor is of size qbits. */ -gcry_mpi_t -_gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits, - gcry_mpi_t g, gcry_mpi_t **ret_factors ) +static gcry_err_code_t +prime_generate_internal (int mode, + gcry_mpi_t *prime_generated, unsigned int pbits, + unsigned int qbits, gcry_mpi_t g, + gcry_mpi_t **ret_factors, + gcry_random_level_t random, unsigned int flags) { - int n; /* number of factors */ - int m; /* number of primes in pool */ - unsigned fbits; /* length of prime factors */ - gcry_mpi_t *factors; /* current factors */ - gcry_mpi_t *pool; /* pool of primes */ - gcry_mpi_t q; /* first prime factor (variable)*/ - gcry_mpi_t prime; /* prime test value */ - gcry_mpi_t q_factor; /* used for mode 1 */ - byte *perms = NULL; - int i, j; - int count1, count2; - unsigned nprime; - unsigned req_qbits = qbits; /* the requested q bits size */ - gcry_mpi_t val_2 = mpi_alloc_set_ui( 2 ); - - /* find number of needed prime factors */ - for(n=1; (pbits - qbits - 1) / n >= qbits; n++ ) - ; - n--; - if( !n || (mode==1 && n < 2) ) - log_fatal("can't gen prime with pbits=%u qbits=%u\n", pbits, qbits ); - if( mode == 1 ) { - n--; - fbits = (pbits - 2*req_qbits -1) / n; - qbits = pbits - req_qbits - n*fbits; - } - else { - fbits = (pbits - req_qbits -1) / n; - qbits = pbits - n*fbits; + gcry_err_code_t err = GPG_ERR_NO_ERROR; + gcry_mpi_t *factors_new = NULL; /* Factors to return to the + caller. */ + gcry_mpi_t *factors = NULL; /* Current factors. */ + gcry_mpi_t *pool = NULL; /* Pool of primes. */ + unsigned char *perms = NULL; /* Permutations of POOL. */ + gcry_mpi_t q_factor = NULL; /* Used if QBITS is non-zero. */ + unsigned int fbits = 0; /* Length of prime factors. */ + unsigned int n = 0; /* Number of factors. */ + unsigned int m = 0; /* Number of primes in pool. */ + gcry_mpi_t q = NULL; /* First prime factor. */ + gcry_mpi_t prime; /* Prime candidate. */ + unsigned int nprime = 0; /* Bits of PRIME. */ + unsigned int req_qbits = qbits; /* The original QBITS value. */ + gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* For check_prime(). */ + unsigned int is_secret = flags & GCRY_PRIME_FLAG_SECRET; + unsigned int count1 = 0, count2 = 0; + unsigned int i = 0, j = 0; + + /* Find number of needed prime factors. */ + for (n = 1; (pbits - qbits - 1) / n >= qbits; n++); + n--; + + if ((! n) || ((mode == 1) && (n < 2))) + err = GPG_ERR_INV_ARG; + + if (! err) + { + if (mode == 1) + { + n--; + fbits = (pbits - 2 * req_qbits -1) / n; + qbits = pbits - req_qbits - n * fbits; + } + else + { + fbits = (pbits - req_qbits -1) / n; + qbits = pbits - n * fbits; + } + + if (DBG_CIPHER) + log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n", + pbits, req_qbits, qbits, fbits, n); + + prime = gcry_mpi_new (pbits); + + /* Generate first prime factor. */ + q = gen_prime (qbits, is_secret, random, NULL, NULL); + + if (mode == 1) + q_factor = gen_prime (req_qbits, is_secret, random, NULL, NULL); + + /* Allocate an array to hold the factors + 2 for later + usage. */ + factors = gcry_calloc (n + 2, sizeof (*factors)); + if (! factors) + err = GPG_ERR_INTERNAL; /* FIXME. */ } - if( DBG_CIPHER ) - log_debug("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n", - pbits, req_qbits, qbits, fbits, n ); - prime = gcry_mpi_new ( pbits ); - q = gen_prime( qbits, 0, 0, NULL, NULL ); - q_factor = mode==1? gen_prime( req_qbits, 0, 0, NULL, NULL ) : NULL; - - /* allocate an array to hold the factors + 2 for later usage */ - factors = gcry_xcalloc( n+2, sizeof *factors ); - - /* make a pool of 3n+5 primes (this is an arbitrary value) */ - m = n*3+5; - if( mode == 1 ) - m += 5; /* need some more for DSA */ - if( m < 25 ) + + if (! err) + { + /* Make a pool of 3n+5 primes (this is an arbitrary value). */ + + m = n * 3 + 5; + if (mode == 1) + /* Need some more (for e.g. DSA). */ + m += 5; + if (m < 25) m = 25; - pool = gcry_xcalloc( m , sizeof *pool ); + pool = gcry_calloc (m , sizeof (*pool)); + if (! pool) + err = GPG_ERR_INTERNAL; + } - /* permutate over the pool of primes */ - count1=count2=0; - do { + if (! err) + /* Permutate over the pool of primes. */ + do + { next_try: - if( !perms ) { - /* allocate new primes */ - for(i=0; i < m; i++ ) { - mpi_free(pool[i]); + if (! perms) + { + /* Allocate new primes. */ + for(i = 0; i < m; i++) + { + mpi_free (pool[i]); pool[i] = NULL; - } - /* init m_out_of_n() */ - perms = gcry_xcalloc( 1, m ); - for(i=0; i < n; i++ ) { - perms[i] = 1; - pool[i] = gen_prime( fbits, 0, 1, NULL, NULL ); - factors[i] = pool[i]; - } - } - else { - m_out_of_n( perms, n, m ); - for(i=j=0; i < m && j < n ; i++ ) - if( perms[i] ) { - if( !pool[i] ) - pool[i] = gen_prime( fbits, 0, 1, NULL, NULL ); - factors[j++] = pool[i]; + } + + /* Init m_out_of_n(). */ + perms = gcry_calloc (1, m); + if (! perms) + err = GPG_ERR_INTERNAL; /* FIXME. */ + else + { + for(i = 0; i < n; i++) + { + perms[i] = 1; + pool[i] = gen_prime (fbits, is_secret, random, NULL, NULL); + factors[i] = pool[i]; + } + } + + if (err) + break; + } + else + { + m_out_of_n (perms, n, m); + for(i = j = 0; (i < m) && (j < n); i++) + if (perms[i]) + { + if(! pool[i]) + pool[i] = gen_prime (fbits, 0, 1, NULL, NULL); + factors[j++] = pool[i]; } - if( i == n ) { - gcry_free(perms); perms = NULL; + if (i == n) + { + gcry_free(perms); + perms = NULL; progress('!'); - goto next_try; /* allocate new primes */ - } - } - - mpi_set( prime, q ); - mpi_mul_ui( prime, prime, 2 ); - if( mode == 1 ) - mpi_mul( prime, prime, q_factor ); - for(i=0; i < n; i++ ) - mpi_mul( prime, prime, factors[i] ); - mpi_add_ui( prime, prime, 1 ); - nprime = mpi_get_nbits(prime); - if( nprime < pbits ) { - if( ++count1 > 20 ) { + goto next_try; /* Allocate new primes. */ + } + } + + /* Generate next prime candidate: + + p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. */ + + mpi_set (prime, q); + mpi_mul_ui (prime, prime, 2); + if (mode == 1) + mpi_mul (prime, prime, q_factor); + for(i = 0; i < n; i++) + mpi_mul (prime, prime, factors[i]); + mpi_add_ui (prime, prime, 1); + nprime = mpi_get_nbits (prime); + + if (nprime < pbits) + { + if (++count1 > 20) + { count1 = 0; qbits++; progress('>'); - mpi_free (q); - q = gen_prime( qbits, 0, 0, NULL, NULL ); + mpi_free (q); + q = gen_prime (qbits, 0, 0, NULL, NULL); goto next_try; - } - } + } + } else - count1 = 0; - if( nprime > pbits ) { - if( ++count2 > 20 ) { + count1 = 0; + + if (nprime > pbits) + { + if (++count2 > 20) + { count2 = 0; qbits--; progress('<'); - mpi_free (q); - q = gen_prime( qbits, 0, 0, NULL, NULL ); + mpi_free (q); + q = gen_prime (qbits, 0, 0, NULL, NULL); goto next_try; - } - } + } + } else - count2 = 0; - } while( !(nprime == pbits && check_prime( prime, val_2 )) ); - - if( DBG_CIPHER ) { - progress('\n'); - log_mpidump( "prime : ", prime ); - log_mpidump( "factor q: ", q ); - if( mode == 1 ) - log_mpidump( "factor q0: ", q_factor ); - for(i=0; i < n; i++ ) - log_mpidump( "factor pi: ", factors[i] ); - log_debug("bit sizes: prime=%u, q=%u", mpi_get_nbits(prime), mpi_get_nbits(q) ); - if( mode == 1 ) - log_debug (", q0=%u", mpi_get_nbits(q_factor) ); - for(i=0; i < n; i++ ) - log_debug (", p%d=%u", i, mpi_get_nbits(factors[i]) ); + count2 = 0; + } + while (! ((nprime == pbits) && check_prime (prime, val_2))); + + if (! err) + if (DBG_CIPHER) + { + progress ('\n'); + log_mpidump ("prime : ", prime); + log_mpidump ("factor q: ", q); + if (mode == 1) + log_mpidump ("factor q0: ", q_factor); + for(i = 0; i < n; i++) + log_mpidump ("factor pi: ", factors[i]); + log_debug ("bit sizes: prime=%u, q=%u", + mpi_get_nbits (prime), mpi_get_nbits (q)); + if (mode == 1) + log_debug (", q0=%u", mpi_get_nbits (q_factor)); + for (i = 0; i < n; i++) + log_debug (", p%d=%u", i, mpi_get_nbits (factors[i])); progress('\n'); - } + } + + if (! err) + if (ret_factors) + { + /* Caller wants the factors. */ + factors_new = gcry_calloc (n + 2, sizeof (*factors_new)); + if (! factors_new) + err = GPG_ERR_INTERNAL; /* FIXME. */ + else + { + i = 0; + if (mode == 1) + { + (factors_new)[i++] = mpi_copy (q_factor); + for(; i <= n; i++) + (factors_new)[i] = mpi_copy (factors[i]); + } + else + for(; i < n; i++ ) + (factors_new)[i] = mpi_copy (factors[i]); + } + } + + if (! err) + if (g) + { + /* Create a generator (start with 3). */ + gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime)); + gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime)); + gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime)); + + if (mode == 1) + err = GPG_ERR_NOT_IMPLEMENTED; + else + { + factors[n] = q; + factors[n + 1] = mpi_alloc_set_ui (2); + mpi_sub_ui (pmin1, prime, 1); + mpi_set_ui (g, 2); + do + { + mpi_add_ui (g, g, 1); + if (DBG_CIPHER) + { + log_debug ("checking g:"); + gcry_mpi_dump (g); + log_debug ("\n"); + } + else + progress('^'); + for (i = 0; i < n + 2; i++) + { + mpi_fdiv_q (tmp, pmin1, factors[i]); + /* No mpi_pow(), but it is okay to use this with mod + prime. */ + gcry_mpi_powm (b, g, tmp, prime); + if (! mpi_cmp_ui (b, 1)) + break; + } + if (DBG_CIPHER) + progress('\n'); + } while (i < n + 2); + mpi_free (factors[n+1]); + mpi_free (tmp); + mpi_free (b); + mpi_free (pmin1); + } + } + + if (! err) + if (! DBG_CIPHER) + progress ('\n'); - if( ret_factors ) { /* caller wants the factors */ - *ret_factors = gcry_xcalloc( n+2 , sizeof **ret_factors); - i = 0; - if( mode == 1 ) { - (*ret_factors)[i++] = mpi_copy( q_factor ); - for(; i <= n; i++ ) - (*ret_factors)[i] = mpi_copy( factors[i] ); - } - else { - for(; i < n; i++ ) - (*ret_factors)[i] = mpi_copy( factors[i] ); - } + if (pool) + { + for(i = 0; i < m; i++) + mpi_free (pool[i]); + gcry_free (pool); } + if (factors) + gcry_free (factors); /* Factors are shallow copies. */ + if (perms) + gcry_free (perms); - if( g ) { /* create a generator (start with 3)*/ - gcry_mpi_t tmp = mpi_alloc( mpi_get_nlimbs(prime) ); - gcry_mpi_t b = mpi_alloc( mpi_get_nlimbs(prime) ); - gcry_mpi_t pmin1 = mpi_alloc( mpi_get_nlimbs(prime) ); - - if( mode == 1 ) - BUG(); /* not yet implemented */ - factors[n] = q; - factors[n+1] = mpi_alloc_set_ui(2); - mpi_sub_ui( pmin1, prime, 1 ); - mpi_set_ui(g,2); - do { - mpi_add_ui(g, g, 1); - if( DBG_CIPHER ) { - log_debug ("checking g:"); - gcry_mpi_dump (g); - log_debug ("\n"); - } - else - progress('^'); - for(i=0; i < n+2; i++ ) { - /*fputc('~', stderr);*/ - mpi_fdiv_q(tmp, pmin1, factors[i] ); - /* (no mpi_pow(), but it is okay to use this with mod prime) */ - gcry_mpi_powm(b, g, tmp, prime ); - if( !mpi_cmp_ui(b, 1) ) - break; - } - if( DBG_CIPHER ) - progress('\n'); - } while( i < n+2 ); - mpi_free(factors[n+1]); - mpi_free(tmp); - mpi_free(b); - mpi_free(pmin1); + mpi_free (val_2); + mpi_free (q); + + if (! err) + { + *prime_generated = prime; + if (ret_factors) + *ret_factors = factors_new; + } + else + { + if (factors_new) + { + for (i = 0; factors_new[i]; i++) + mpi_free (factors_new[i]); + gcry_free (factors_new); + } } - if( !DBG_CIPHER ) - progress('\n'); - gcry_free( factors ); /* (factors are shallow copies) */ - for(i=0; i < m; i++ ) - mpi_free( pool[i] ); - gcry_free( pool ); - gcry_free(perms); - mpi_free(val_2); - mpi_free (q); - return prime; + return err; } +gcry_mpi_t +_gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits, + gcry_mpi_t g, gcry_mpi_t **ret_factors) +{ + gcry_err_code_t err = GPG_ERR_NO_ERROR; + gcry_mpi_t prime = NULL; + + err = prime_generate_internal (mode, &prime, pbits, qbits, g, + ret_factors, GCRY_WEAK_RANDOM, 0); + return prime; +} static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, @@ -673,3 +788,72 @@ m_out_of_n( char *array, int m, int n ) array[k2-1] = !array[k2-1]; } + +/* Generate a new prime number of PRIME_BITS bits and store it in + PRIME. If FACTOR_BITS is non-zero, one of the prime factors of + (prime - 1) / 2 must be FACTOR_BITS bits long. If FACTORS is + non-zero, allocate a new, NULL-terminated array holding the prime + factors and store it in FACTORS. FLAGS might be used to influence + the prime number generation process. */ +gcry_error_t +gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits, + unsigned int factor_bits, gcry_mpi_t **factors, + gcry_prime_check_func_t cb_func, void *cb_arg, + gcry_random_level_t random_level, + unsigned int flags) +{ + gcry_err_code_t err = GPG_ERR_NO_ERROR; + gcry_mpi_t *factors_generated = NULL; + gcry_mpi_t prime_generated = NULL; + unsigned int mode = 0; + + if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR) + mode = 1; + + /* Generate. */ + err = prime_generate_internal (mode, &prime_generated, prime_bits, + factor_bits, NULL, &factors_generated, + random_level, flags); + + if (! err) + if (cb_func) + { + /* Additional check */ + if (! (*cb_func) (cb_arg, 0, prime_generated)) + { + /* Failed, deallocate resources. */ + + unsigned int i; + + mpi_free (prime_generated); + for (i = 0; factors_generated[i]; i++) + mpi_free (factors_generated[i]); + gcry_free (factors_generated); + err = GPG_ERR_INTERNAL; /* FIXME. */ + } + } + + if (! err) + { + /* Done. */ + *prime = prime_generated; + *factors = factors_generated; + } + + return gcry_error (err); +} + +/* Check wether the number X is prime. */ +gcry_error_t +gcry_prime_check (gcry_mpi_t x, unsigned int flags) +{ + gcry_err_code_t err = GPG_ERR_NO_ERROR; + gcry_mpi_t test_value = mpi_alloc_set_ui (2); /* ? */ + + if (! check_prime (x, test_value)) + err = GPG_ERR_NO_PRIME; + + mpi_free (test_value); + + return gcry_error (err); +} |