diff options
author | Werner Koch <wk@gnupg.org> | 2006-10-25 18:28:49 +0000 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2006-10-25 18:28:49 +0000 |
commit | f7aa7a5f4bd9bf008c4134d4417823aa06c10a23 (patch) | |
tree | 21a7f802f5eac330727e5c9e8d26e9c1dd1f64b2 /cipher/primegen.c | |
parent | ba6bb0aa867715a7a713d1c706ae5433fa831b00 (diff) | |
download | libgcrypt-f7aa7a5f4bd9bf008c4134d4417823aa06c10a23.tar.gz |
See ChangeLog. There are still problems in ac.c.
Diffstat (limited to 'cipher/primegen.c')
-rw-r--r-- | cipher/primegen.c | 336 |
1 files changed, 284 insertions, 52 deletions
diff --git a/cipher/primegen.c b/cipher/primegen.c index 924e1fab..17c65d7d 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -17,11 +17,6 @@ * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - * - * *********************************************************************** - * The algorithm used to generate practically save primes is due to - * Lim and Lee as described in the CRYPTO '97 proceedings (ISBN3540633847) - * page 260. */ #include <config.h> @@ -35,6 +30,7 @@ #include "g10lib.h" #include "mpi.h" #include "cipher.h" +#include "ath.h" static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, int (*extra_check)(void *, gcry_mpi_t), @@ -133,6 +129,96 @@ static ushort small_prime_numbers[] = { }; static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1; + + +/* An object and a list to build up a global pool of primes. See + save_pool_prime and get_pool_prime. */ +struct primepool_s +{ + struct primepool_s *next; + gcry_mpi_t prime; /* If this is NULL the entry is not used. */ + unsigned int nbits; + gcry_random_level_t randomlevel; +}; +struct primepool_s *primepool; +/* Mutex used to protect access to the primepool. */ +static ath_mutex_t primepool_lock = ATH_MUTEX_INITIALIZER; + + + +/* Save PRIME which has been generated at RANDOMLEVEL for later + use. Needs to be called while primepool_lock is being hold. Note + that PRIME should be considered released after calling this + function. */ +static void +save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel) +{ + struct primepool_s *item, *item2; + size_t n; + + for (n=0, item = primepool; item; item = item->next, n++) + if (!item->prime) + break; + if (!item && n > 100) + { + /* Remove some of the entries. Our strategy is removing + the last third from the list. */ + int i; + + for (i=0, item2 = primepool; item2; item2 = item2->next) + { + if (i >= n/3*2) + { + gcry_mpi_release (item2->prime); + item2->prime = NULL; + if (!item) + item = item2; + } + } + } + if (!item) + { + item = gcry_calloc (1, sizeof *item); + if (!item) + { + /* Out of memory. Silently giving up. */ + gcry_mpi_release (prime); + return; + } + item->next = primepool; + primepool = item; + } + item->prime = prime; + item->nbits = mpi_get_nbits (prime); + item->randomlevel = randomlevel; +} + + +/* Return a prime for the prime pool or NULL if none has been found. + The prime needs to match NBITS and randomlevel. This function needs + to be called why the primepool_look is being hold. */ +static gcry_mpi_t +get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel) +{ + struct primepool_s *item; + + for (item = primepool; item; item = item->next) + if (item->prime + && item->nbits == nbits && item->randomlevel == randomlevel) + { + gcry_mpi_t prime = item->prime; + item->prime = NULL; + assert (nbits == mpi_get_nbits (prime)); + return prime; + } + return NULL; +} + + + + + + void _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int), void *cb_data ) @@ -178,18 +264,30 @@ _gcry_generate_public_prime( unsigned int nbits, } -/**************** - * We do not need to use the strongest RNG because we gain no extra - * security from it - The prime number is public and we could also - * offer the factors for those who are willing to check that it is - * indeed a strong prime. With ALL_FACTORS set to true all afcors of - * prime-1 are returned in FACTORS. - * - * mode 0: Standard - * 1: Make sure that at least one factor is of size qbits. +/* Core prime generation function. The algorithm used to generate + practically save primes is due to Lim and Lee as described in the + CRYPTO '97 proceedings (ISBN3540633847) page 260. + + NEED_Q_FACTOR: If true make sure that at least one factor is of + size qbits. This is for example required for DSA. + PRIME_GENERATED: Adresss of a variable where the resulting prime + number will be stored. + PBITS: Requested size of the prime number. At least 48. + QBITS: One factor of the prime needs to be of this size. Maybe 0 + if this is not required. See also MODE. + G: If not NULL an MPI which will receive a generator for the prime + for use with Elgamal. + RET_FACTORS: if not NULL, an array with all factors are stored at + that address. + ALL_FACTORS: If set to true all factors of prime-1 are returned. + RANDOMLEVEL: How strong should the random numers be. + FLAGS: Prime generation bit flags. Currently supported: + GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret. + CB_FUNC, CB_ARG: Callback to be used for extra checks. + */ static gcry_err_code_t -prime_generate_internal (int mode, +prime_generate_internal (int need_q_factor, gcry_mpi_t *prime_generated, unsigned int pbits, unsigned int qbits, gcry_mpi_t g, gcry_mpi_t **ret_factors, @@ -201,7 +299,9 @@ prime_generate_internal (int mode, gcry_mpi_t *factors_new = NULL; /* Factors to return to the caller. */ gcry_mpi_t *factors = NULL; /* Current factors. */ + gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */ gcry_mpi_t *pool = NULL; /* Pool of primes. */ + int *pool_in_use = NULL; /* Array with currently used POOL elements. */ 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. */ @@ -212,6 +312,7 @@ prime_generate_internal (int mode, unsigned int nprime = 0; /* Bits of PRIME. */ unsigned int req_qbits; /* The original QBITS value. */ gcry_mpi_t val_2; /* For check_prime(). */ + int is_locked = 0; /* Flag to help unlocking the primepool. */ unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET); unsigned int count1 = 0, count2 = 0; unsigned int i = 0, j = 0; @@ -219,28 +320,33 @@ prime_generate_internal (int mode, if (pbits < 48) return GPG_ERR_INV_ARG; + /* We won't use a too strong random elvel for the pooled subprimes. */ + poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM? + GCRY_STRONG_RANDOM : randomlevel); + + /* If QBITS is not given, assume a reasonable value. */ if (!qbits) qbits = pbits / 3; req_qbits = qbits; - /* Find number of needed prime factors. */ + /* Find number of needed prime factors N. */ for (n = 1; (pbits - qbits - 1) / n >= qbits; n++) ; n--; val_2 = mpi_alloc_set_ui (2); - if ((! n) || ((mode == 1) && (n < 2))) + if ((! n) || ((need_q_factor) && (n < 2))) { err = GPG_ERR_INV_ARG; goto leave; } - if (mode == 1) + if (need_q_factor) { - n--; + n--; /* Need one factor less because we want a specific Q-FACTOR. */ fbits = (pbits - 2 * req_qbits -1) / n; qbits = pbits - req_qbits - n * fbits; } @@ -254,28 +360,45 @@ prime_generate_internal (int mode, log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n", pbits, req_qbits, qbits, fbits, n); + /* Allocate an integer to old the new prime. */ prime = gcry_mpi_new (pbits); /* Generate first prime factor. */ q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); - - if (mode == 1) + + /* Generate a specific Q-Factor if requested. */ + if (need_q_factor) q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL); - /* Allocate an array to hold the factors + 2 for later usage. */ + /* Allocate an array to hold all factors + 2 for later usage. */ factors = gcry_calloc (n + 2, sizeof (*factors)); if (!factors) { err = gpg_err_code_from_errno (errno); goto leave; } + + /* Allocate an array to track pool usage. */ + pool_in_use = gcry_malloc (n * sizeof *pool_in_use); + if (!pool_in_use) + { + err = gpg_err_code_from_errno (errno); + goto leave; + } + for (i=0; i < n; i++) + pool_in_use[i] = -1; - /* Make a pool of 3n+5 primes (this is an arbitrary value). */ + /* Make a pool of 3n+5 primes (this is an arbitrary value). We + require at least 30 primes for are useful selection process. + + FIXME: We need to do some reseacrh on the best formula for sizing + the pool. + */ m = n * 3 + 5; - if (mode == 1) /* Need some more (for e.g. DSA). */ + if (need_q_factor) /* Need some more in this case. */ m += 5; - if (m < 25) - m = 25; + if (m < 30) + m = 30; pool = gcry_calloc (m , sizeof (*pool)); if (! pool) { @@ -283,14 +406,19 @@ prime_generate_internal (int mode, goto leave; } - /* Permutate over the pool of primes. */ + /* Permutate over the pool of primes until we find a prime of the + requested length. */ do { next_try: - if (! perms) + for (i=0; i < n; i++) + pool_in_use[i] = -1; + + if (!perms) { - /* Allocate new primes. */ - for(i = 0; i < m; i++) + /* Allocate new primes. This is done right at the beginning + of the loop and if we have later run out of primes. */ + for (i = 0; i < m; i++) { mpi_free (pool[i]); pool[i] = NULL; @@ -298,44 +426,110 @@ prime_generate_internal (int mode, /* Init m_out_of_n(). */ perms = gcry_calloc (1, m); - if (! perms) + if (!perms) { err = gpg_err_code_from_errno (errno); goto leave; } - for(i = 0; i < n; i++) + + if (ath_mutex_lock (&primepool_lock)) + { + err = GPG_ERR_INTERNAL; + goto leave; + } + is_locked = 1; + for (i = 0; i < n; i++) { - perms[i] = 1; - pool[i] = gen_prime (fbits, is_secret, - randomlevel, NULL, NULL); + perms[i] = 1; + /* At a maximum we use strong random for the factors. + This saves us a lot of entropy. Given that Q and + possible Q-factor are also used in the final prime + this should be acceptable. We also don't allocate in + secure memory to save on that scare resource too. If + Q has been allocated in secure memory, the final + prime will be saved there anyway. This is because + our MPI routines take care of that. GnuPG has worked + this way ever since. */ + pool[i] = NULL; + if (is_locked) + { + pool[i] = get_pool_prime (fbits, poolrandomlevel); + if (!pool[i]) + { + if (ath_mutex_unlock (&primepool_lock)) + { + err = GPG_ERR_INTERNAL; + goto leave; + } + is_locked = 0; + } + } + if (!pool[i]) + pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL); + pool_in_use[i] = i; factors[i] = pool[i]; } + if (is_locked && ath_mutex_unlock (&primepool_lock)) + { + err = GPG_ERR_INTERNAL; + goto leave; + } + is_locked = 0; } else { + /* Get next permutation. */ m_out_of_n ( (char*)perms, n, m); + if (ath_mutex_lock (&primepool_lock)) + { + err = GPG_ERR_INTERNAL; + goto leave; + } + is_locked = 1; for (i = j = 0; (i < m) && (j < n); i++) if (perms[i]) { - if(! pool[i]) - pool[i] = gen_prime (fbits, 0, 1, NULL, NULL); + /* If the subprime has not yet beed generated do it now. */ + if (!pool[i] && is_locked) + { + pool[i] = get_pool_prime (fbits, poolrandomlevel); + if (!pool[i]) + { + if (ath_mutex_unlock (&primepool_lock)) + { + err = GPG_ERR_INTERNAL; + goto leave; + } + is_locked = 0; + } + } + if (!pool[i]) + pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL); + pool_in_use[j] = i; factors[j++] = pool[i]; } + if (is_locked && ath_mutex_unlock (&primepool_lock)) + { + err = GPG_ERR_INTERNAL; + goto leave; + } + is_locked = 0; if (i == n) { + /* Ran out of permutations: Allocate new primes. */ gcry_free (perms); perms = NULL; progress ('!'); - goto next_try; /* Allocate new primes. */ + goto next_try; } } /* 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) + if (need_q_factor) mpi_mul (prime, prime, q_factor); for(i = 0; i < n; i++) mpi_mul (prime, prime, factors[i]); @@ -350,7 +544,7 @@ prime_generate_internal (int mode, qbits++; progress('>'); mpi_free (q); - q = gen_prime (qbits, 0, 0, NULL, NULL); + q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); goto next_try; } } @@ -365,7 +559,7 @@ prime_generate_internal (int mode, qbits--; progress('<'); mpi_free (q); - q = gen_prime (qbits, 0, 0, NULL, NULL); + q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); goto next_try; } } @@ -380,13 +574,13 @@ prime_generate_internal (int mode, progress ('\n'); log_mpidump ("prime : ", prime); log_mpidump ("factor q: ", q); - if (mode == 1) + if (need_q_factor) 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) + if (need_q_factor) 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])); @@ -408,7 +602,7 @@ prime_generate_internal (int mode, i = 0; factors_new[i++] = gcry_mpi_set_ui (NULL, 2); factors_new[i++] = mpi_copy (q); - if (mode == 1) + if (need_q_factor) factors_new[i++] = mpi_copy (q_factor); for(j=0; j < n; j++) factors_new[i++] = mpi_copy (factors[j]); @@ -416,7 +610,7 @@ prime_generate_internal (int mode, else { i = 0; - if (mode == 1) + if (need_q_factor) { factors_new[i++] = mpi_copy (q_factor); for (; i <= n; i++) @@ -435,7 +629,7 @@ prime_generate_internal (int mode, gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime)); gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime)); - if (mode == 1) + if (need_q_factor) err = GPG_ERR_NOT_IMPLEMENTED; else { @@ -482,10 +676,29 @@ prime_generate_internal (int mode, leave: if (pool) { + is_locked = !ath_mutex_lock (&primepool_lock); for(i = 0; i < m; i++) - mpi_free (pool[i]); + { + if (pool[i]) + { + for (j=0; j < n; j++) + if (pool_in_use[j] == i) + break; + if (j == n && is_locked) + { + /* This pooled subprime has not been used. */ + save_pool_prime (pool[i], poolrandomlevel); + } + else + mpi_free (pool[i]); + } + } + if (is_locked && ath_mutex_unlock (&primepool_lock)) + err = GPG_ERR_INTERNAL; + is_locked = 0; gcry_free (pool); } + gcry_free (pool_in_use); if (factors) gcry_free (factors); /* Factors are shallow copies. */ if (perms) @@ -515,6 +728,8 @@ prime_generate_internal (int mode, return err; } + + gcry_mpi_t _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits, gcry_mpi_t g, gcry_mpi_t **ret_factors) @@ -522,7 +737,7 @@ _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits, gcry_err_code_t err = GPG_ERR_NO_ERROR; gcry_mpi_t prime = NULL; - err = prime_generate_internal (mode, &prime, pbits, qbits, g, + err = prime_generate_internal ((mode == 1), &prime, pbits, qbits, g, ret_factors, GCRY_WEAK_RANDOM, 0, 0, NULL, NULL); @@ -765,6 +980,21 @@ is_prime (gcry_mpi_t n, int steps, unsigned int *count) } +/* Given ARRAY of size N with M elements set to true produce a + modified array with the next permutation of M elements. Note, that + ARRAY is used in a one-bit-per-byte approach. To detected the last + permutation it is useful to intialize the array with the first M + element set to true and use this test: + m_out_of_n (array, m, n); + for (i = j = 0; i < n && j < m; i++) + if (array[i]) + j++; + if (j == m) + goto ready; + + This code is based on the algorithm 452 from the "Collected + Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang. +*/ static void m_out_of_n ( char *array, int m, int n ) { @@ -773,12 +1003,12 @@ m_out_of_n ( char *array, int m, int n ) if( !m || m >= n ) return; + /* Need to handle this simple case separately. */ if( m == 1 ) { - /* Special case. */ for (i=0; i < n; i++ ) { - if( array[i] ) + if ( array[i] ) { array[i++] = 0; if( i >= n ) @@ -790,6 +1020,7 @@ m_out_of_n ( char *array, int m, int n ) BUG(); } + for (j=1; j < n; j++ ) { if ( array[n-1] == array[n-j-1]) @@ -866,6 +1097,7 @@ m_out_of_n ( char *array, int m, int n ) k2 = n + 1 - m; } leave: + /* Now complement the two selected bits. */ array[k1-1] = !array[k1-1]; array[k2-1] = !array[k2-1]; } @@ -897,7 +1129,7 @@ gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits, mode = 1; /* Generate. */ - err = prime_generate_internal (mode, &prime_generated, prime_bits, + err = prime_generate_internal ((mode==1), &prime_generated, prime_bits, factor_bits, NULL, factors? &factors_generated : NULL, random_level, flags, 1, |