diff options
author | Werner Koch <wk@gnupg.org> | 2011-02-04 20:21:45 +0100 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2011-02-04 20:21:45 +0100 |
commit | 4f048514ecae879fa4bb7b8522baf801229be522 (patch) | |
tree | d798c8527b68e83e4419c14d7c6dd47f2abdfd9e /cipher/primegen.c | |
parent | 9d00b28e0d04361fe9ccf02983bea781b5701c1d (diff) | |
download | libgcrypt-4f048514ecae879fa4bb7b8522baf801229be522.tar.gz |
Nuked almost all trailing whitespace.
Check and install the standard git pre-commit hook.
Diffstat (limited to 'cipher/primegen.c')
-rw-r--r-- | cipher/primegen.c | 187 |
1 files changed, 93 insertions, 94 deletions
diff --git a/cipher/primegen.c b/cipher/primegen.c index f0727754..edeb7c87 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -31,7 +31,7 @@ #include "cipher.h" #include "ath.h" -static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, +static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg); static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds, @@ -132,7 +132,7 @@ 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 { struct primepool_s *next; gcry_mpi_t prime; /* If this is NULL the entry is not used. */ @@ -163,7 +163,7 @@ save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel) /* 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) @@ -182,7 +182,7 @@ save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel) { /* Out of memory. Silently giving up. */ gcry_mpi_release (prime); - return; + return; } item->next = primepool; primepool = item; @@ -359,7 +359,7 @@ prime_generate_internal (int need_q_factor, 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); @@ -373,7 +373,7 @@ prime_generate_internal (int need_q_factor, /* 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 all factors + 2 for later usage. */ factors = gcry_calloc (n + 2, sizeof (*factors)); if (!factors) @@ -391,10 +391,10 @@ prime_generate_internal (int need_q_factor, } for (i=0; i < n; i++) pool_in_use[i] = -1; - + /* Make a pool of 3n+5 primes (this is an arbitrary value). We - require at least 30 primes for are useful selection process. - + require at least 30 primes for are useful selection process. + Fixme: We need to research the best formula for sizing the pool. */ m = n * 3 + 5; @@ -443,7 +443,7 @@ prime_generate_internal (int need_q_factor, is_locked = 1; for (i = 0; i < n; i++) { - perms[i] = 1; + 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 @@ -523,12 +523,12 @@ prime_generate_internal (int need_q_factor, gcry_free (perms); perms = NULL; progress ('!'); - goto next_try; + goto next_try; } } /* Generate next prime candidate: - p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. + p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. */ mpi_set (prime, q); mpi_mul_ui (prime, prime, 2); @@ -553,7 +553,7 @@ prime_generate_internal (int need_q_factor, } else count1 = 0; - + if (nprime > pbits) { if (++count2 > 20) @@ -624,14 +624,14 @@ prime_generate_internal (int need_q_factor, factors_new[i] = mpi_copy (factors[i]); } } - + 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 (need_q_factor) err = GPG_ERR_NOT_IMPLEMENTED; else @@ -662,7 +662,7 @@ prime_generate_internal (int need_q_factor, } if (DBG_CIPHER) progress('\n'); - } + } while (i < n + 2); mpi_free (factors[n+1]); @@ -671,7 +671,7 @@ prime_generate_internal (int need_q_factor, mpi_free (pmin1); } } - + if (! DBG_CIPHER) progress ('\n'); @@ -740,7 +740,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 == 1), &prime, pbits, qbits, g, ret_factors, GCRY_WEAK_RANDOM, 0, 0, NULL, NULL); @@ -750,7 +750,7 @@ _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits, static gcry_mpi_t -gen_prime (unsigned int nbits, int secret, int randomlevel, +gen_prime (unsigned int nbits, int secret, int randomlevel, int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg) { gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result; @@ -758,7 +758,7 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, unsigned int x, step; unsigned int count1, count2; int *mods; - + /* if ( DBG_CIPHER ) */ /* log_debug ("generate a prime of %u bits ", nbits ); */ @@ -777,10 +777,10 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, for (;;) { /* try forvever */ int dotcount=0; - + /* generate a random number */ gcry_mpi_randomize( prime, nbits, randomlevel ); - + /* Set high order bit to 1, set low order bit to 1. If we are generating a secret prime we are most probably doing that for RSA, to make sure that the modulus does have the @@ -789,17 +789,17 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, if (secret) mpi_set_bit (prime, nbits-2); mpi_set_bit(prime, 0); - + /* Calculate all remainders. */ 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 ) + for(step=0; step < 20000; step += 2 ) { /* Check against all the small primes we have in mods. */ count1++; - for (i=0; (x = small_prime_numbers[i]); i++ ) + for (i=0; (x = small_prime_numbers[i]); i++ ) { while ( mods[i] + step >= x ) mods[i] -= x; @@ -808,7 +808,7 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, } if ( x ) continue; /* Found a multiple of an already known prime. */ - + mpi_add_ui( ptest, prime, step ); /* Do a fast Fermat test now. */ @@ -816,7 +816,7 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, mpi_sub_ui( pminus1, ptest, 1); gcry_mpi_powm( result, val_2, pminus1, ptest ); if ( !mpi_cmp_ui( result, 1 ) ) - { + { /* Not composite, perform stronger tests */ if (is_prime(ptest, 5, &count2 )) { @@ -828,13 +828,13 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, } if (extra_check && extra_check (extra_check_arg, ptest)) - { + { /* The extra check told us that this prime is not of the caller's taste. */ progress ('/'); } else - { + { /* Got it. */ mpi_free(val_2); mpi_free(val_3); @@ -842,7 +842,7 @@ gen_prime (unsigned int nbits, int secret, int randomlevel, mpi_free(pminus1); mpi_free(prime); gcry_free(mods); - return ptest; + return ptest; } } } @@ -883,7 +883,7 @@ check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds, gcry_mpi_powm( result, val_2, pminus1, prime ); mpi_free( pminus1 ); if ( mpi_cmp_ui( result, 1 ) ) - { + { /* Is composite. */ mpi_free( result ); progress('.'); @@ -924,7 +924,7 @@ is_prime (gcry_mpi_t n, int steps, unsigned int *count) unsigned nbits = mpi_get_nbits( n ); if (steps < 5) /* Make sure that we do at least 5 rounds. */ - steps = 5; + steps = 5; mpi_sub_ui( nminus1, n, 1 ); @@ -996,7 +996,7 @@ is_prime (gcry_mpi_t n, int steps, unsigned int *count) 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. */ @@ -1010,7 +1010,7 @@ m_out_of_n ( char *array, int m, int n ) /* Need to handle this simple case separately. */ if( m == 1 ) - { + { for (i=0; i < n; i++ ) { if ( array[i] ) @@ -1060,7 +1060,7 @@ m_out_of_n ( char *array, int m, int n ) else k1 = k2 + 1; } - else + else { /* M is even. */ if( !array[n-1] ) @@ -1069,7 +1069,7 @@ m_out_of_n ( char *array, int m, int n ) k2 = k1 + 1; goto leave; } - + if( !(j1 & 1) ) { k1 = n - j1; @@ -1080,7 +1080,7 @@ m_out_of_n ( char *array, int m, int n ) } scan: jp = n - j1 - 1; - for (i=1; i <= jp; i++ ) + for (i=1; i <= jp; i++ ) { i1 = jp + 2 - i; if( array[i1-1] ) @@ -1128,7 +1128,7 @@ gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits, if (!prime) return gpg_error (GPG_ERR_INV_ARG); - *prime = NULL; + *prime = NULL; if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR) mode = 1; @@ -1156,7 +1156,7 @@ gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits, mpi_free (factors_generated[i]); gcry_free (factors_generated); } - err = GPG_ERR_GENERAL; + err = GPG_ERR_GENERAL; } } @@ -1207,29 +1207,29 @@ gcry_prime_group_generator (gcry_mpi_t *r_g, if (!factors || !r_g || !prime) return gpg_error (GPG_ERR_INV_ARG); - *r_g = NULL; + *r_g = NULL; for (n=0; factors[n]; n++) ; if (n < 2) return gpg_error (GPG_ERR_INV_ARG); - /* Extra sanity check - usually disabled. */ + /* Extra sanity check - usually disabled. */ /* mpi_set (tmp, factors[0]); */ /* for(i = 1; i < n; i++) */ /* mpi_mul (tmp, tmp, factors[i]); */ /* mpi_add_ui (tmp, tmp, 1); */ /* if (mpi_cmp (prime, tmp)) */ /* return gpg_error (GPG_ERR_INV_ARG); */ - - gcry_mpi_sub_ui (pmin1, prime, 1); - do + + gcry_mpi_sub_ui (pmin1, prime, 1); + do { if (first) first = 0; else gcry_mpi_add_ui (g, g, 1); - + if (DBG_CIPHER) { log_debug ("checking g:"); @@ -1238,7 +1238,7 @@ gcry_prime_group_generator (gcry_mpi_t *r_g, } else progress('^'); - + for (i = 0; i < n; i++) { mpi_fdiv_q (tmp, pmin1, factors[i]); @@ -1250,13 +1250,13 @@ gcry_prime_group_generator (gcry_mpi_t *r_g, progress('\n'); } while (i < n); - + gcry_mpi_release (tmp); - gcry_mpi_release (b); - gcry_mpi_release (pmin1); - *r_g = g; + gcry_mpi_release (b); + gcry_mpi_release (pmin1); + *r_g = g; - return 0; + return 0; } /* Convenience function to release the factors array. */ @@ -1266,7 +1266,7 @@ gcry_prime_release_factors (gcry_mpi_t *factors) if (factors) { int i; - + for (i=0; factors[i]; i++) mpi_free (factors[i]); gcry_free (factors); @@ -1279,11 +1279,11 @@ gcry_prime_release_factors (gcry_mpi_t *factors) static gcry_mpi_t find_x931_prime (const gcry_mpi_t pfirst) { - gcry_mpi_t val_2 = mpi_alloc_set_ui (2); + gcry_mpi_t val_2 = mpi_alloc_set_ui (2); gcry_mpi_t prime; - + prime = gcry_mpi_copy (pfirst); - /* If P is even add 1. */ + /* If P is even add 1. */ mpi_set_bit (prime, 0); /* We use 64 Rabin-Miller rounds which is better and thus @@ -1299,7 +1299,7 @@ find_x931_prime (const gcry_mpi_t pfirst) } -/* Generate a prime using the algorithm from X9.31 appendix B.4. +/* Generate a prime using the algorithm from X9.31 appendix B.4. This function requires that the provided public exponent E is odd. XP, XP1 and XP2 are the seed values. All values are mandatory. @@ -1308,7 +1308,7 @@ find_x931_prime (const gcry_mpi_t pfirst) internal values P1 and P2 are saved at these addresses. On error NULL is returned. */ gcry_mpi_t -_gcry_derive_x931_prime (const gcry_mpi_t xp, +_gcry_derive_x931_prime (const gcry_mpi_t xp, const gcry_mpi_t xp1, const gcry_mpi_t xp2, const gcry_mpi_t e, gcry_mpi_t *r_p1, gcry_mpi_t *r_p2) @@ -1327,20 +1327,20 @@ _gcry_derive_x931_prime (const gcry_mpi_t xp, { gcry_mpi_t r1, tmp; - + /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */ tmp = mpi_alloc_like (p1); mpi_invm (tmp, p2, p1); mpi_mul (tmp, tmp, p2); r1 = tmp; - + tmp = mpi_alloc_like (p2); mpi_invm (tmp, p1, p2); mpi_mul (tmp, tmp, p1); mpi_sub (r1, r1, tmp); /* Fixup a negative value. */ - if (mpi_is_neg (r1)) + if (mpi_is_neg (r1)) mpi_add (r1, r1, p1p2); /* yp0 = xp + (r1 - xp mod p1*p2) */ @@ -1350,7 +1350,7 @@ _gcry_derive_x931_prime (const gcry_mpi_t xp, mpi_free (r1); /* Fixup a negative value. */ - if (mpi_cmp (yp0, xp) < 0 ) + if (mpi_cmp (yp0, xp) < 0 ) mpi_add (yp0, yp0, p1p2); } @@ -1378,10 +1378,10 @@ _gcry_derive_x931_prime (const gcry_mpi_t xp, */ { - gcry_mpi_t val_2 = mpi_alloc_set_ui (2); + gcry_mpi_t val_2 = mpi_alloc_set_ui (2); gcry_mpi_t gcdtmp = mpi_alloc_like (yp0); int gcdres; - + mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body. */ mpi_sub_ui (yp0, yp0, 1); /* Ditto. */ for (;;) @@ -1453,7 +1453,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, ; /* No seed value given: We are asked to generate it. */ else if (!seed || seedlen < qbits/8) return GPG_ERR_INV_ARG; - + /* Allocate a buffer to later compute SEED+some_increment. */ seed_plus = gcry_malloc (seedlen < 20? 20:seedlen); if (!seed_plus) @@ -1468,7 +1468,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, value_w = gcry_mpi_new (pbits); value_x = gcry_mpi_new (pbits); - restart: + restart: /* Generate Q. */ for (;;) { @@ -1479,7 +1479,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, gcry_create_nonce (seed_help_buffer, seedlen); seed = seed_help_buffer; } - + /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits}) */ memcpy (seed_plus, seed, seedlen); for (i=seedlen-1; i >= 0; i--) @@ -1492,16 +1492,16 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); for (i=0; i < sizeof value_u; i++) value_u[i] ^= digest[i]; - + /* Step 3: Form q from U */ gcry_mpi_release (prime_q); prime_q = NULL; - ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, + ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, value_u, sizeof value_u, NULL)); if (ec) goto leave; mpi_set_highbit (prime_q, qbits-1 ); mpi_set_bit (prime_q, 0); - + /* Step 4: Test whether Q is prime using 64 round of Rabin-Miller. */ if (check_prime (prime_q, val_2, 64, NULL, NULL)) break; /* Yes, Q is prime. */ @@ -1509,7 +1509,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, /* Step 5. */ seed = NULL; /* Force a new seed at Step 1. */ } - + /* Step 6. Note that we do no use an explicit offset but increment SEED_PLUS accordingly. SEED_PLUS is currently SEED+1. */ counter = 0; @@ -1518,12 +1518,12 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, prime_p = gcry_mpi_new (pbits); for (;;) { - /* Step 7: For k = 0,...n let - V_k = sha1(seed+offset+k) mod 2^{qbits} - Step 8: W = V_0 + V_1*2^160 + - ... + /* Step 7: For k = 0,...n let + V_k = sha1(seed+offset+k) mod 2^{qbits} + Step 8: W = V_0 + V_1*2^160 + + ... + V_{n-1}*2^{(n-1)*160} - + (V_{n} mod 2^b)*2^{n*160} + + (V_{n} mod 2^b)*2^{n*160} */ mpi_set_ui (value_w, 0); for (value_k=0; value_k <= value_n; value_k++) @@ -1542,7 +1542,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, break; } gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); - + gcry_mpi_release (tmpval); tmpval = NULL; ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG, digest, sizeof digest, NULL)); @@ -1631,7 +1631,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, value is stored at R_COUNTER and the seed actually used for generation is stored at R_SEED and R_SEEDVALUE. The hash algorithm used is stored at R_HASHALGO. - + Note that this function is very similar to the fips186_2 code. Due to the minor differences, other buffer sizes and for documentarion, we use a separate function. @@ -1652,7 +1652,7 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, gcry_mpi_t tmpval = NULL; /* Helper variable. */ int hashalgo; /* The id of the Approved Hash Function. */ int i; - + unsigned char value_u[256/8]; int value_n, value_b, value_j; int counter; @@ -1690,10 +1690,10 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, ; /* No seed value given: We are asked to generate it. */ else if (!seed || seedlen < qbits/8) return GPG_ERR_INV_ARG; - + /* Allocate a buffer to later compute SEED+some_increment and a few helper variables. */ - seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer? + seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer? sizeof seed_help_buffer : seedlen); if (!seed_plus) { @@ -1709,7 +1709,7 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, /* Step 4: b = L - 1 - (n * outlen) */ value_b = pbits - 1 - (value_n * qbits); - restart: + restart: /* Generate Q. */ for (;;) { @@ -1721,7 +1721,7 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, gcry_create_nonce (seed_help_buffer, seedlen); seed = seed_help_buffer; } - + /* Step 6: U = hash(seed) */ gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen); @@ -1736,12 +1736,12 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, } } gcry_mpi_release (prime_q); prime_q = NULL; - ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, + ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, value_u, sizeof value_u, NULL)); if (ec) goto leave; mpi_set_highbit (prime_q, qbits-1 ); - + /* Step 8: Test whether Q is prime using 64 round of Rabin-Miller. According to table C.1 this is sufficient for all supported prime sizes (i.e. up 3072/256). */ @@ -1751,7 +1751,7 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, /* Step 8. */ seed = NULL; /* Force a new seed at Step 5. */ } - + /* Step 11. Note that we do no use an explicit offset but increment SEED_PLUS accordingly. */ memcpy (seed_plus, seed, seedlen); @@ -1761,12 +1761,12 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, prime_p = gcry_mpi_new (pbits); for (;;) { - /* Step 11.1: For j = 0,...n let - V_j = hash(seed+offset+j) - Step 11.2: W = V_0 + V_1*2^outlen + - ... + /* Step 11.1: For j = 0,...n let + V_j = hash(seed+offset+j) + Step 11.2: W = V_0 + V_1*2^outlen + + ... + V_{n-1}*2^{(n-1)*outlen} - + (V_{n} mod 2^b)*2^{n*outlen} + + (V_{n} mod 2^b)*2^{n*outlen} */ mpi_set_ui (value_w, 0); for (value_j=0; value_j <= value_n; value_j++) @@ -1783,7 +1783,7 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, break; } gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); - + gcry_mpi_release (tmpval); tmpval = NULL; ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG, digest, sizeof digest, NULL)); @@ -1813,7 +1813,7 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, if (mpi_get_nbits (prime_p) >= pbits-1 && check_prime (prime_p, val_2, 64, NULL, NULL) ) break; /* Yes, P is prime, continue with Step 15. */ - + /* Step 11.9: counter = counter + 1, offset = offset + n + 1. If counter >= 4L goto Step 5. */ counter++; @@ -1859,4 +1859,3 @@ _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, gcry_mpi_release (val_2); return ec; } - |