diff --git a/cipher/primegen.c b/cipher/primegen.c index 3ed432bf..cccda84e 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -1,1851 +1,1872 @@ /* primegen.c - prime number generator * Copyright (C) 1998, 2000, 2001, 2002, 2003 * 2004, 2008 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser general Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * 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 */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" 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, gcry_prime_check_func_t cb_func, void *cb_arg ); static int is_prime (gcry_mpi_t n, int steps, unsigned int *count); static void m_out_of_n( char *array, int m, int n ); static void (*progress_cb) (void *,const char*,int,int, int ); static void *progress_cb_data; /* Note: 2 is not included because it can be tested more easily by looking at bit 0. The last entry in this list is marked by a zero */ static ushort small_prime_numbers[] = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 0 }; 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. */ GPGRT_LOCK_DEFINE (primepool_lock); gcry_err_code_t _gcry_primegen_init (void) { /* This function was formerly used to initialize the primepool Mutex. This has been replace by a static initialization. */ return 0; } /* 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 = xtrycalloc (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 with 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; gcry_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 ) { progress_cb = cb; progress_cb_data = cb_data; } static void progress( int c ) { if ( progress_cb ) progress_cb ( progress_cb_data, "primegen", c, 0, 0 ); } /**************** * Generate a prime number (stored in secure memory) */ gcry_mpi_t _gcry_generate_secret_prime (unsigned int nbits, gcry_random_level_t random_level, int (*extra_check)(void*, gcry_mpi_t), void *extra_check_arg) { gcry_mpi_t prime; prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg); progress('\n'); return prime; } /* Generate a prime number which may be public, i.e. not allocated in secure memory. */ gcry_mpi_t _gcry_generate_public_prime (unsigned int nbits, gcry_random_level_t random_level, int (*extra_check)(void*, gcry_mpi_t), void *extra_check_arg) { gcry_mpi_t prime; prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg); progress('\n'); return prime; } /* 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 need_q_factor, gcry_mpi_t *prime_generated, unsigned int pbits, unsigned int qbits, gcry_mpi_t g, gcry_mpi_t **ret_factors, gcry_random_level_t randomlevel, unsigned int flags, int all_factors, gcry_prime_check_func_t cb_func, void *cb_arg) { gcry_err_code_t err = 0; 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. */ 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 = NULL; /* Prime candidate. */ 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; 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 N. */ for (n = 1; (pbits - qbits - 1) / n >= qbits; n++) ; n--; val_2 = mpi_alloc_set_ui (2); if ((! n) || ((need_q_factor) && (n < 2))) { err = GPG_ERR_INV_ARG; goto leave; } if (need_q_factor) { 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; } 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); /* Allocate an integer to old the new prime. */ prime = mpi_new (pbits); /* Generate first prime factor. */ q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); /* 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 = xtrycalloc (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 = xtrymalloc (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). We 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; if (need_q_factor) /* Need some more in this case. */ m += 5; if (m < 30) m = 30; pool = xtrycalloc (m , sizeof (*pool)); if (! pool) { err = gpg_err_code_from_errno (errno); goto leave; } /* Permutate over the pool of primes until we find a prime of the requested length. */ do { next_try: for (i=0; i < n; i++) pool_in_use[i] = -1; if (!perms) { /* 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; } /* Init m_out_of_n(). */ perms = xtrycalloc (1, m); if (!perms) { err = gpg_err_code_from_errno (errno); goto leave; } err = gpgrt_lock_lock (&primepool_lock); if (err) goto leave; is_locked = 1; for (i = 0; i < n; i++) { 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]) { err = gpgrt_lock_unlock (&primepool_lock); if (err) 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 && (err = gpgrt_lock_unlock (&primepool_lock))) goto leave; is_locked = 0; } else { /* Get next permutation. */ m_out_of_n ( (char*)perms, n, m); if ((err = gpgrt_lock_lock (&primepool_lock))) goto leave; is_locked = 1; for (i = j = 0; (i < m) && (j < n); i++) if (perms[i]) { /* 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 ((err = gpgrt_lock_unlock (&primepool_lock))) 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 && (err = gpgrt_lock_unlock (&primepool_lock))) goto leave; is_locked = 0; if (i == n) { /* Ran out of permutations: Allocate new primes. */ xfree (perms); perms = NULL; progress ('!'); 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 (need_q_factor) 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, is_secret, randomlevel, NULL, NULL); goto next_try; } } else count1 = 0; if (nprime > pbits) { if (++count2 > 20) { count2 = 0; qbits--; progress('<'); mpi_free (q); q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); goto next_try; } } else count2 = 0; } while (! ((nprime == pbits) && check_prime (prime, val_2, 5, cb_func, cb_arg))); if (DBG_CIPHER) { progress ('\n'); log_mpidump ("prime ", prime); log_mpidump ("factor q", q); 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 (need_q_factor) log_printf (", q0=%u", mpi_get_nbits (q_factor)); for (i = 0; i < n; i++) log_printf (", p%d=%u", i, mpi_get_nbits (factors[i])); log_printf ("\n"); } if (ret_factors) { /* Caller wants the factors. */ factors_new = xtrycalloc (n + 4, sizeof (*factors_new)); if (! factors_new) { err = gpg_err_code_from_errno (errno); goto leave; } if (all_factors) { i = 0; factors_new[i++] = mpi_set_ui (NULL, 2); factors_new[i++] = mpi_copy (q); if (need_q_factor) factors_new[i++] = mpi_copy (q_factor); for(j=0; j < n; j++) factors_new[i++] = mpi_copy (factors[j]); } else { i = 0; if (need_q_factor) { 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 (g && need_q_factor) err = GPG_ERR_NOT_IMPLEMENTED; else 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)); 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_printmpi ("checking g", g); 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. */ 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 (! DBG_CIPHER) progress ('\n'); leave: if (pool) { is_locked = !gpgrt_lock_lock (&primepool_lock); for(i = 0; i < m; 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) err = gpgrt_lock_unlock (&primepool_lock); is_locked = 0; xfree (pool); } xfree (pool_in_use); if (factors) xfree (factors); /* Factors are shallow copies. */ if (perms) xfree (perms); mpi_free (val_2); mpi_free (q); mpi_free (q_factor); 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]); xfree (factors_new); } mpi_free (prime); } return err; } /* Generate a prime used for discrete logarithm algorithms; i.e. this prime will be public and no strong random is required. On success R_PRIME receives a new MPI with the prime. On error R_PRIME is set to NULL and an error code is returned. If RET_FACTORS is not NULL it is set to an allocated array of factors on success or to NULL on error. */ gcry_err_code_t _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits, gcry_mpi_t g, gcry_mpi_t *r_prime, gcry_mpi_t **ret_factors) { *r_prime = NULL; if (ret_factors) *ret_factors = NULL; return prime_generate_internal ((mode == 1), r_prime, pbits, qbits, g, ret_factors, GCRY_WEAK_RANDOM, 0, 0, NULL, NULL); } static gcry_mpi_t 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; int i; unsigned int x, step; unsigned int count1, count2; int *mods; /* if ( DBG_CIPHER ) */ /* log_debug ("generate a prime of %u bits ", nbits ); */ if (nbits < 16) log_fatal ("can't generate a prime with less than %d bits\n", 16); mods = xmalloc (no_of_small_prime_numbers * sizeof *mods); /* Make nbits fit into gcry_mpi_t implementation. */ val_2 = mpi_alloc_set_ui( 2 ); val_3 = mpi_alloc_set_ui( 3); prime = secret? mpi_snew (nbits): mpi_new (nbits); result = mpi_alloc_like( prime ); pminus1= mpi_alloc_like( prime ); ptest = mpi_alloc_like( prime ); count1 = count2 = 0; 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 requested key size we set the 2 high order bits. */ mpi_set_highbit (prime, nbits-1); 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 ) { /* Check against all the small primes we have in mods. */ count1++; for (i=0; (x = small_prime_numbers[i]); i++ ) { while ( mods[i] + step >= x ) mods[i] -= x; if ( !(mods[i] + step) ) break; } if ( x ) continue; /* Found a multiple of an already known prime. */ mpi_add_ui( ptest, prime, step ); /* Do a fast Fermat test now. */ count2++; mpi_sub_ui( pminus1, ptest, 1); mpi_powm( result, val_2, pminus1, ptest ); if ( !mpi_cmp_ui( result, 1 ) ) { /* Not composite, perform stronger tests */ if (is_prime(ptest, 5, &count2 )) { if (!mpi_test_bit( ptest, nbits-1-secret )) { progress('\n'); log_debug ("overflow in prime generation\n"); break; /* Stop loop, continue with a new prime. */ } 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); mpi_free(result); mpi_free(pminus1); mpi_free(prime); xfree(mods); return ptest; } } } if (++dotcount == 10 ) { progress('.'); dotcount = 0; } } progress(':'); /* restart with a new random value */ } } /**************** * Returns: true if this may be a prime * RM_ROUNDS gives the number of Rabin-Miller tests to run. */ static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds, gcry_prime_check_func_t cb_func, void *cb_arg) { int i; unsigned int x; unsigned int count=0; /* Check against small primes. */ for (i=0; (x = small_prime_numbers[i]); i++ ) { if ( mpi_divisible_ui( prime, x ) ) return !mpi_cmp_ui (prime, x); } /* A quick Fermat test. */ { gcry_mpi_t result = mpi_alloc_like( prime ); gcry_mpi_t pminus1 = mpi_alloc_like( prime ); mpi_sub_ui( pminus1, prime, 1); mpi_powm( result, val_2, pminus1, prime ); mpi_free( pminus1 ); if ( mpi_cmp_ui( result, 1 ) ) { /* Is composite. */ mpi_free( result ); progress('.'); return 0; } mpi_free( result ); } if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime)) { /* Perform stronger tests. */ if ( is_prime( prime, rm_rounds, &count ) ) { if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime)) return 1; /* Probably a prime. */ } } progress('.'); return 0; } /* * Return true if n is probably a prime */ static int is_prime (gcry_mpi_t n, int steps, unsigned int *count) { gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t a2 = mpi_alloc_set_ui( 2 ); gcry_mpi_t q; unsigned i, j, k; int rc = 0; unsigned nbits = mpi_get_nbits( n ); if (steps < 5) /* Make sure that we do at least 5 rounds. */ steps = 5; mpi_sub_ui( nminus1, n, 1 ); /* Find q and k, so that n = 1 + 2^k * q . */ q = mpi_copy ( nminus1 ); k = mpi_trailing_zeros ( q ); mpi_tdiv_q_2exp (q, q, k); for (i=0 ; i < steps; i++ ) { ++*count; if( !i ) { mpi_set_ui( x, 2 ); } else { _gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM ); /* Make sure that the number is smaller than the prime and keep the randomness of the high bit. */ if ( mpi_test_bit ( x, nbits-2) ) { mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */ } else { mpi_set_highbit( x, nbits-2 ); mpi_clear_bit( x, nbits-2 ); } gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0); } mpi_powm ( y, x, q, n); if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) { for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ ) { mpi_powm(y, y, a2, n); if( !mpi_cmp_ui( y, 1 ) ) goto leave; /* Not a prime. */ } if (mpi_cmp( y, nminus1 ) ) goto leave; /* Not a prime. */ } progress('+'); } rc = 1; /* May be a prime. */ leave: mpi_free( x ); mpi_free( y ); mpi_free( z ); mpi_free( nminus1 ); mpi_free( q ); mpi_free( a2 ); return rc; } /* 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 initialize 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 ) { int i=0, i1=0, j=0, jp=0, j1=0, k1=0, k2=0; if( !m || m >= n ) return; /* Need to handle this simple case separately. */ if( m == 1 ) { for (i=0; i < n; i++ ) { if ( array[i] ) { array[i++] = 0; if( i >= n ) i = 0; array[i] = 1; return; } } BUG(); } for (j=1; j < n; j++ ) { if ( array[n-1] == array[n-j-1]) continue; j1 = j; break; } if ( (m & 1) ) { /* M is odd. */ if( array[n-1] ) { if( j1 & 1 ) { k1 = n - j1; k2 = k1+2; if( k2 > n ) k2 = n; goto leave; } goto scan; } k2 = n - j1 - 1; if( k2 == 0 ) { k1 = i; k2 = n - j1; } else if( array[k2] && array[k2-1] ) k1 = n; else k1 = k2 + 1; } else { /* M is even. */ if( !array[n-1] ) { k1 = n - j1; k2 = k1 + 1; goto leave; } if( !(j1 & 1) ) { k1 = n - j1; k2 = k1+2; if( k2 > n ) k2 = n; goto leave; } scan: jp = n - j1 - 1; for (i=1; i <= jp; i++ ) { i1 = jp + 2 - i; if( array[i1-1] ) { if( array[i1-2] ) { k1 = i1 - 1; k2 = n - j1; } else { k1 = i1 - 1; k2 = n + 1 - j1; } goto leave; } } k1 = 1; k2 = n + 1 - m; } leave: /* Now complement the two selected bits. */ array[k1-1] = !array[k1-1]; 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_err_code_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 rc = 0; gcry_mpi_t *factors_generated = NULL; gcry_mpi_t prime_generated = NULL; unsigned int mode = 0; if (!prime) return GPG_ERR_INV_ARG; *prime = NULL; if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR) mode = 1; /* Generate. */ rc = prime_generate_internal ((mode==1), &prime_generated, prime_bits, factor_bits, NULL, factors? &factors_generated : NULL, random_level, flags, 1, cb_func, cb_arg); if (!rc && cb_func) { /* Additional check. */ if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated)) { /* Failed, deallocate resources. */ unsigned int i; mpi_free (prime_generated); if (factors) { for (i = 0; factors_generated[i]; i++) mpi_free (factors_generated[i]); xfree (factors_generated); } rc = GPG_ERR_GENERAL; } } if (!rc) { if (factors) *factors = factors_generated; *prime = prime_generated; } return rc; } /* Check whether the number X is prime. */ gcry_err_code_t _gcry_prime_check (gcry_mpi_t x, unsigned int flags) { (void)flags; switch (mpi_cmp_ui (x, 2)) { case 0: return 0; /* 2 is a prime */ case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes. */ } /* We use 64 rounds because the prime we are going to test is not guaranteed to be a random one. */ if (check_prime (x, mpi_const (MPI_C_TWO), 64, NULL, NULL)) return 0; return GPG_ERR_NO_PRIME; } + +/* Check whether the number X is prime according to FIPS 186-4 table C.2. */ +gcry_err_code_t +_gcry_fips186_4_prime_check (gcry_mpi_t x, unsigned int bits) +{ + gcry_err_code_t ec = GPG_ERR_NO_ERROR; + + switch (mpi_cmp_ui (x, 2)) + { + case 0: return ec; /* 2 is a prime */ + case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes. */ + } + + /* We use 5 or 4 rounds as specified in table C.2 */ + if (! check_prime (x, mpi_const (MPI_C_TWO), bits > 1024 ? 4 : 5, NULL, NULL)) + ec = GPG_ERR_NO_PRIME; + + return ec; +} + + /* Find a generator for PRIME where the factorization of (prime-1) is in the NULL terminated array FACTORS. Return the generator as a newly allocated MPI in R_G. If START_G is not NULL, use this as s atart for the search. Returns 0 on success.*/ gcry_err_code_t _gcry_prime_group_generator (gcry_mpi_t *r_g, gcry_mpi_t prime, gcry_mpi_t *factors, gcry_mpi_t start_g) { gcry_mpi_t tmp, b, pmin1, g; int first, i, n; if (!r_g) return GPG_ERR_INV_ARG; *r_g = NULL; if (!factors || !prime) return GPG_ERR_INV_ARG; for (n=0; factors[n]; n++) ; if (n < 2) return GPG_ERR_INV_ARG; tmp = mpi_new (0); b = mpi_new (0); pmin1 = mpi_new (0); g = start_g? mpi_copy (start_g) : mpi_set_ui (NULL, 3); /* 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); */ mpi_sub_ui (pmin1, prime, 1); first = 1; do { if (first) first = 0; else mpi_add_ui (g, g, 1); if (DBG_CIPHER) log_printmpi ("checking g", g); else progress('^'); for (i = 0; i < n; i++) { mpi_fdiv_q (tmp, pmin1, factors[i]); mpi_powm (b, g, tmp, prime); if (! mpi_cmp_ui (b, 1)) break; } if (DBG_CIPHER) progress('\n'); } while (i < n); _gcry_mpi_release (tmp); _gcry_mpi_release (b); _gcry_mpi_release (pmin1); *r_g = g; return 0; } /* Convenience function to release the factors array. */ void _gcry_prime_release_factors (gcry_mpi_t *factors) { if (factors) { int i; for (i=0; factors[i]; i++) mpi_free (factors[i]); xfree (factors); } } /* Helper for _gcry_derive_x931_prime. */ 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 prime; prime = mpi_copy (pfirst); /* If P is even add 1. */ mpi_set_bit (prime, 0); /* We use 64 Rabin-Miller rounds which is better and thus sufficient. We do not have a Lucas test implementaion thus we can't do it in the X9.31 preferred way of running a few Rabin-Miller followed by one Lucas test. */ while ( !check_prime (prime, val_2, 64, NULL, NULL) ) mpi_add_ui (prime, prime, 2); mpi_free (val_2); return prime; } /* 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. On success the prime is returned. If R_P1 or R_P2 are given the 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, 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) { gcry_mpi_t p1, p2, p1p2, yp0; if (!xp || !xp1 || !xp2) return NULL; if (!e || !mpi_test_bit (e, 0)) return NULL; /* We support only odd values for E. */ p1 = find_x931_prime (xp1); p2 = find_x931_prime (xp2); p1p2 = mpi_alloc_like (xp); mpi_mul (p1p2, p1, p2); { 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_has_sign (r1)) mpi_add (r1, r1, p1p2); /* yp0 = xp + (r1 - xp mod p1*p2) */ yp0 = tmp; tmp = NULL; mpi_subm (yp0, r1, xp, p1p2); mpi_add (yp0, yp0, xp); mpi_free (r1); /* Fixup a negative value. */ if (mpi_cmp (yp0, xp) < 0 ) mpi_add (yp0, yp0, p1p2); } /* yp0 is now the first integer greater than xp with p1 being a large prime factor of yp0-1 and p2 a large prime factor of yp0+1. */ /* Note that the first example from X9.31 (D.1.1) which uses (Xq1 #1A5CF72EE770DE50CB09ACCEA9#) (Xq2 #134E4CAA16D2350A21D775C404#) (Xq #CC1092495D867E64065DEE3E7955F2EBC7D47A2D 7C9953388F97DDDC3E1CA19C35CA659EDC2FC325 6D29C2627479C086A699A49C4C9CEE7EF7BD1B34 321DE34A#)))) returns an yp0 of #CC1092495D867E64065DEE3E7955F2EBC7D47A2D 7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3 BF20CB896EE37E098A906313271422162CB6C642 75C1201F# and not #CC1092495D867E64065DEE3E7955F2EBC7D47A2D 7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6 C88FE299D52D78BE405A97E01FD71DD7819ECB91 FA85A076# as stated in the standard. This seems to be a bug in X9.31. */ { 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 (;;) { gcdres = mpi_gcd (gcdtmp, e, yp0); mpi_add_ui (yp0, yp0, 1); if (!gcdres) progress ('/'); /* gcd (e, yp0-1) != 1 */ else if (check_prime (yp0, val_2, 64, NULL, NULL)) break; /* Found. */ /* We add p1p2-1 because yp0 is incremented after the gcd test. */ mpi_add (yp0, yp0, p1p2); } mpi_free (gcdtmp); mpi_free (val_2); } mpi_free (p1p2); progress('\n'); if (r_p1) *r_p1 = p1; else mpi_free (p1); if (r_p2) *r_p2 = p2; else mpi_free (p2); return yp0; } /* Generate the two prime used for DSA using the algorithm specified in FIPS 186-2. PBITS is the desired length of the prime P and a QBITS the length of the prime Q. If SEED is not supplied and SEEDLEN is 0 the function generates an appropriate SEED. On success the generated primes are stored at R_Q and R_P, the counter value is stored at R_COUNTER and the seed actually used for generation is stored at R_SEED and R_SEEDVALUE. */ gpg_err_code_t _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, const void *seed, size_t seedlen, gcry_mpi_t *r_q, gcry_mpi_t *r_p, int *r_counter, void **r_seed, size_t *r_seedlen) { gpg_err_code_t ec; unsigned char seed_help_buffer[160/8]; /* Used to hold a generated SEED. */ unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */ unsigned char digest[160/8]; /* Helper buffer for SHA-1 digest. */ gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */ gcry_mpi_t tmpval = NULL; /* Helper variable. */ int i; unsigned char value_u[160/8]; int value_n, value_b, value_k; int counter; gcry_mpi_t value_w = NULL; gcry_mpi_t value_x = NULL; gcry_mpi_t prime_q = NULL; gcry_mpi_t prime_p = NULL; /* FIPS 186-2 allows only for 1024/160 bit. */ if (pbits != 1024 || qbits != 160) return GPG_ERR_INV_KEYLEN; if (!seed && !seedlen) ; /* 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 = xtrymalloc (seedlen < 20? 20:seedlen); if (!seed_plus) { ec = gpg_err_code_from_syserror (); goto leave; } val_2 = mpi_alloc_set_ui (2); value_n = (pbits - 1) / qbits; value_b = (pbits - 1) - value_n * qbits; value_w = mpi_new (pbits); value_x = mpi_new (pbits); restart: /* Generate Q. */ for (;;) { /* Step 1: Generate a (new) seed unless one has been supplied. */ if (!seed) { seedlen = sizeof seed_help_buffer; _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--) { seed_plus[i]++; if (seed_plus[i]) break; } _gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen); _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 = _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. */ /* 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; /* Generate P. */ prime_p = 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 + ... + V_{n-1}*2^{(n-1)*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++) { /* There is no need to have an explicit offset variable: In the first round we shall have an offset of 2, this is achieved by using SEED_PLUS which is already at SEED+1, thus we just need to increment it once again. The requirement for the next round is to update offset by N, which we implictly did at the end of this loop, and then to add one; this one is the same as in the first round. */ for (i=seedlen-1; i >= 0; i--) { seed_plus[i]++; if (seed_plus[i]) break; } _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); _gcry_mpi_release (tmpval); tmpval = NULL; ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG, digest, sizeof digest, NULL); if (ec) goto leave; if (value_k == value_n) mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */ mpi_lshift (tmpval, tmpval, value_k*qbits); mpi_add (value_w, value_w, tmpval); } /* Step 8 continued: X = W + 2^{L-1} */ mpi_set_ui (value_x, 0); mpi_set_highbit (value_x, pbits-1); mpi_add (value_x, value_x, value_w); /* Step 9: c = X mod 2q, p = X - (c - 1) */ mpi_mul_2exp (tmpval, prime_q, 1); mpi_mod (tmpval, value_x, tmpval); mpi_sub_ui (tmpval, tmpval, 1); mpi_sub (prime_p, value_x, tmpval); /* Step 10: If p < 2^{L-1} skip the primality test. */ /* Step 11 and 12: Primality test. */ 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 13: counter = counter + 1, offset = offset + n + 1. */ counter++; /* Step 14: If counter >= 2^12 goto Step 1. */ if (counter >= 4096) goto restart; } /* Step 15: Save p, q, counter and seed. */ /* log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */ /* mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */ /* log_printhex("fips186-2 seed:", seed, seedlen); */ /* log_mpidump ("fips186-2 prime p", prime_p); */ /* log_mpidump ("fips186-2 prime q", prime_q); */ if (r_q) { *r_q = prime_q; prime_q = NULL; } if (r_p) { *r_p = prime_p; prime_p = NULL; } if (r_counter) *r_counter = counter; if (r_seed && r_seedlen) { memcpy (seed_plus, seed, seedlen); *r_seed = seed_plus; seed_plus = NULL; *r_seedlen = seedlen; } leave: _gcry_mpi_release (tmpval); _gcry_mpi_release (value_x); _gcry_mpi_release (value_w); _gcry_mpi_release (prime_p); _gcry_mpi_release (prime_q); xfree (seed_plus); _gcry_mpi_release (val_2); return ec; } /* WARNING: The code below has not yet been tested! * * Generate the two prime used for DSA using the algorithm specified * in FIPS 186-3, A.1.1.2. PBITS is the desired length of the prime P * and a QBITS the length of the prime Q. If SEED is not supplied and * SEEDLEN is 0 the function generates an appropriate SEED. On * success the generated primes are stored at R_Q and R_P, the counter * 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. */ gpg_err_code_t _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, const void *seed, size_t seedlen, gcry_mpi_t *r_q, gcry_mpi_t *r_p, int *r_counter, void **r_seed, size_t *r_seedlen, int *r_hashalgo) { gpg_err_code_t ec; unsigned char seed_help_buffer[256/8]; /* Used to hold a generated SEED. */ unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */ unsigned char digest[256/8]; /* Helper buffer for SHA-2 digest. */ gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */ 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; gcry_mpi_t value_w = NULL; gcry_mpi_t value_x = NULL; gcry_mpi_t prime_q = NULL; gcry_mpi_t prime_p = NULL; gcry_assert (sizeof seed_help_buffer == sizeof digest && sizeof seed_help_buffer == sizeof value_u); /* Step 1: Check the requested prime lengths. */ /* Note that due to the size of our buffers QBITS is limited to 256. */ if (pbits == 2048 && qbits == 224) hashalgo = GCRY_MD_SHA224; else if (pbits == 2048 && qbits == 256) hashalgo = GCRY_MD_SHA256; else if (pbits == 3072 && qbits == 256) hashalgo = GCRY_MD_SHA256; else return GPG_ERR_INV_KEYLEN; /* Also check that the hash algorithm is available. */ ec = _gcry_md_test_algo (hashalgo); if (ec) return ec; gcry_assert (qbits/8 <= sizeof digest); gcry_assert (_gcry_md_get_algo_dlen (hashalgo) == qbits/8); /* Step 2: Check seedlen. */ if (!seed && !seedlen) ; /* 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 = xtrymalloc (seedlen < sizeof seed_help_buffer? sizeof seed_help_buffer : seedlen); if (!seed_plus) { ec = gpg_err_code_from_syserror (); goto leave; } val_2 = mpi_alloc_set_ui (2); value_w = mpi_new (pbits); value_x = mpi_new (pbits); /* Step 3: n = \lceil L / outlen \rceil - 1 */ value_n = (pbits + qbits - 1) / qbits - 1; /* Step 4: b = L - 1 - (n * outlen) */ value_b = pbits - 1 - (value_n * qbits); restart: /* Generate Q. */ for (;;) { /* Step 5: Generate a (new) seed unless one has been supplied. */ if (!seed) { seedlen = qbits/8; gcry_assert (seedlen <= sizeof seed_help_buffer); _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); /* Step 7: q = 2^{N-1} + U + 1 - (U mod 2) */ if ( !(value_u[qbits/8-1] & 0x01) ) { for (i=qbits/8-1; i >= 0; i--) { value_u[i]++; if (value_u[i]) break; } } _gcry_mpi_release (prime_q); prime_q = NULL; ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, value_u, qbits/8, 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). */ if (check_prime (prime_q, val_2, 64, NULL, NULL)) break; /* Yes, Q is prime. */ /* 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); counter = 0; /* Generate P. */ prime_p = 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 + ... + V_{n-1}*2^{(n-1)*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++) { /* There is no need to have an explicit offset variable: In the first round we shall have an offset of 1 and a j of 0. This is achieved by incrementing SEED_PLUS here. For the next round offset is implicitly updated by using SEED_PLUS again. */ for (i=seedlen-1; i >= 0; i--) { seed_plus[i]++; if (seed_plus[i]) break; } _gcry_md_hash_buffer (hashalgo, digest, seed_plus, seedlen); _gcry_mpi_release (tmpval); tmpval = NULL; ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG, digest, qbits/8, NULL); if (ec) goto leave; if (value_j == value_n) mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */ mpi_lshift (tmpval, tmpval, value_j*qbits); mpi_add (value_w, value_w, tmpval); } /* Step 11.3: X = W + 2^{L-1} */ mpi_set_ui (value_x, 0); mpi_set_highbit (value_x, pbits-1); mpi_add (value_x, value_x, value_w); /* Step 11.4: c = X mod 2q */ mpi_mul_2exp (tmpval, prime_q, 1); mpi_mod (tmpval, value_x, tmpval); /* Step 11.5: p = X - (c - 1) */ mpi_sub_ui (tmpval, tmpval, 1); mpi_sub (prime_p, value_x, tmpval); /* Step 11.6: If p < 2^{L-1} skip the primality test. */ /* Step 11.7 and 11.8: Primality test. */ 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++; if (counter >= 4*pbits) goto restart; } /* Step 12: Save p, q, counter and seed. */ /* log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n", */ /* mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */ /* log_printhex ("fips186-3 seed", seed, seedlen); */ /* log_printmpi ("fips186-3 p", prime_p); */ /* log_printmpi ("fips186-3 q", prime_q); */ if (r_q) { *r_q = prime_q; prime_q = NULL; } if (r_p) { *r_p = prime_p; prime_p = NULL; } if (r_counter) *r_counter = counter; if (r_seed && r_seedlen) { memcpy (seed_plus, seed, seedlen); *r_seed = seed_plus; seed_plus = NULL; *r_seedlen = seedlen; } if (r_hashalgo) *r_hashalgo = hashalgo; leave: _gcry_mpi_release (tmpval); _gcry_mpi_release (value_x); _gcry_mpi_release (value_w); _gcry_mpi_release (prime_p); _gcry_mpi_release (prime_q); xfree (seed_plus); _gcry_mpi_release (val_2); return ec; } diff --git a/cipher/rsa.c b/cipher/rsa.c index 787b14a1..cb3c464a 100644 --- a/cipher/rsa.c +++ b/cipher/rsa.c @@ -1,1694 +1,1986 @@ /* rsa.c - RSA implementation * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn) * Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ /* This code uses an algorithm protected by U.S. Patent #4,405,829 which expired on September 20, 2000. The patent holder placed that patent into the public domain on Sep 6th, 2000. */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "pubkey-internal.h" typedef struct { gcry_mpi_t n; /* modulus */ gcry_mpi_t e; /* exponent */ } RSA_public_key; typedef struct { gcry_mpi_t n; /* public modulus */ gcry_mpi_t e; /* public exponent */ gcry_mpi_t d; /* exponent */ gcry_mpi_t p; /* prime p. */ gcry_mpi_t q; /* prime q. */ gcry_mpi_t u; /* inverse of p mod q. */ } RSA_secret_key; static const char *rsa_names[] = { "rsa", "openpgp-rsa", "oid.1.2.840.113549.1.1.1", NULL, }; /* A sample 2048 bit RSA key used for the selftests. */ static const char sample_secret_key[] = " (private-key" " (rsa" " (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC" " 7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8" " 7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C" " 958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917" " DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613" " 6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C" " 42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918" " 664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)" " (e #010001#)" " (d #07EF82500C403899934FE993AC5A36F14FF2DF38CF1EF315F205EE4C83EDAA19" " 8890FC23DE9AA933CAFB37B6A8A8DBA675411958337287310D3FF2F1DDC0CB93" " 7E70F57F75F833C021852B631D2B9A520E4431A03C5C3FCB5742DCD841D9FB12" " 771AA1620DCEC3F1583426066ED9DC3F7028C5B59202C88FDF20396E2FA0EC4F" " 5A22D9008F3043673931BC14A5046D6327398327900867E39CC61B2D1AFE2F48" " EC8E1E3861C68D257D7425F4E6F99ABD77D61F10CA100EFC14389071831B33DD" " 69CC8EABEF860D1DC2AAA84ABEAE5DFC91BC124DAF0F4C8EF5BBEA436751DE84" " 3A8063E827A024466F44C28614F93B0732A100D4A0D86D532FE1E22C7725E401#)" " (p #00C29D438F115825779631CD665A5739367F3E128ADC29766483A46CA80897E0" " 79B32881860B8F9A6A04C2614A904F6F2578DAE13EA67CD60AE3D0AA00A1FF9B" " 441485E44B2DC3D0B60260FBFE073B5AC72FAF67964DE15C8212C389D20DB9CF" " 54AF6AEF5C4196EAA56495DD30CF709F499D5AB30CA35E086C2A1589D6283F1783#)" " (q #00D1984135231CB243FE959C0CBEF551EDD986AD7BEDF71EDF447BE3DA27AF46" " 79C974A6FA69E4D52FE796650623DE70622862713932AA2FD9F2EC856EAEAA77" " 88B4EA6084DC81C902F014829B18EA8B2666EC41586818E0589E18876065F97E" " 8D22CE2DA53A05951EC132DCEF41E70A9C35F4ACC268FFAC2ADF54FA1DA110B919#)" " (u #67CF0FD7635205DD80FA814EE9E9C267C17376BF3209FB5D1BC42890D2822A04" " 479DAF4D5B6ED69D0F8D1AF94164D07F8CD52ECEFE880641FA0F41DDAB1785E4" " A37A32F997A516480B4CD4F6482B9466A1765093ED95023CA32D5EDC1E34CEE9" " AF595BC51FE43C4BF810FA225AF697FB473B83815966188A4312C048B885E3F7#)))"; /* A sample 2048 bit RSA key used for the selftests (public only). */ static const char sample_public_key[] = " (public-key" " (rsa" " (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC" " 7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8" " 7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C" " 958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917" " DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613" " 6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C" " 42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918" " 664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)" " (e #010001#)))"; static int test_keys (RSA_secret_key *sk, unsigned nbits); static int check_secret_key (RSA_secret_key *sk); static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey); static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey); static unsigned int rsa_get_nbits (gcry_sexp_t parms); /* Check that a freshly generated key actually works. Returns 0 on success. */ static int test_keys (RSA_secret_key *sk, unsigned int nbits) { int result = -1; /* Default to failure. */ RSA_public_key pk; gcry_mpi_t plaintext = mpi_new (nbits); gcry_mpi_t ciphertext = mpi_new (nbits); gcry_mpi_t decr_plaintext = mpi_new (nbits); gcry_mpi_t signature = mpi_new (nbits); /* Put the relevant parameters into a public key structure. */ pk.n = sk->n; pk.e = sk->e; /* Create a random plaintext. */ _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM); /* Encrypt using the public key. */ public (ciphertext, plaintext, &pk); /* Check that the cipher text does not match the plaintext. */ if (!mpi_cmp (ciphertext, plaintext)) goto leave; /* Ciphertext is identical to the plaintext. */ /* Decrypt using the secret key. */ secret (decr_plaintext, ciphertext, sk); /* Check that the decrypted plaintext matches the original plaintext. */ if (mpi_cmp (decr_plaintext, plaintext)) goto leave; /* Plaintext does not match. */ /* Create another random plaintext as data for signature checking. */ _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM); /* Use the RSA secret function to create a signature of the plaintext. */ secret (signature, plaintext, sk); /* Use the RSA public function to verify this signature. */ public (decr_plaintext, signature, &pk); if (mpi_cmp (decr_plaintext, plaintext)) goto leave; /* Signature does not match. */ /* Modify the signature and check that the signing fails. */ mpi_add_ui (signature, signature, 1); public (decr_plaintext, signature, &pk); if (!mpi_cmp (decr_plaintext, plaintext)) goto leave; /* Signature matches but should not. */ result = 0; /* All tests succeeded. */ leave: _gcry_mpi_release (signature); _gcry_mpi_release (decr_plaintext); _gcry_mpi_release (ciphertext); _gcry_mpi_release (plaintext); return result; } /* Callback used by the prime generation to test whether the exponent is suitable. Returns 0 if the test has been passed. */ static int check_exponent (void *arg, gcry_mpi_t a) { gcry_mpi_t e = arg; gcry_mpi_t tmp; int result; mpi_sub_ui (a, a, 1); tmp = _gcry_mpi_alloc_like (a); result = !mpi_gcd(tmp, e, a); /* GCD is not 1. */ _gcry_mpi_release (tmp); mpi_add_ui (a, a, 1); return result; } /**************** * Generate a key pair with a key of size NBITS. * USE_E = 0 let Libcgrypt decide what exponent to use. * = 1 request the use of a "secure" exponent; this is required by some * specification to be 65537. * > 2 Use this public exponent. If the given exponent * is not odd one is internally added to it. * TRANSIENT_KEY: If true, generate the primes using the standard RNG. * Returns: 2 structures filled with all needed values */ static gpg_err_code_t generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, int transient_key) { gcry_mpi_t p, q; /* the two primes */ gcry_mpi_t d; /* the private key */ gcry_mpi_t u; gcry_mpi_t t1, t2; gcry_mpi_t n; /* the public key */ gcry_mpi_t e; /* the exponent */ gcry_mpi_t phi; /* helper: (p-1)(q-1) */ gcry_mpi_t g; gcry_mpi_t f; gcry_random_level_t random_level; if (fips_mode ()) { if (nbits < 1024) return GPG_ERR_INV_VALUE; if (transient_key) return GPG_ERR_INV_VALUE; } /* The random quality depends on the transient_key flag. */ random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM; /* Make sure that nbits is even so that we generate p, q of equal size. */ if ( (nbits&1) ) nbits++; if (use_e == 1) /* Alias for a secure value */ use_e = 65537; /* as demanded by Sphinx. */ /* Public exponent: In general we use 41 as this is quite fast and more secure than the commonly used 17. Benchmarking the RSA verify function with a 1024 bit key yields (2001-11-08): e=17 0.54 ms e=41 0.75 ms e=257 0.95 ms e=65537 1.80 ms */ e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB ); if (!use_e) mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */ else { use_e |= 1; /* make sure this is odd */ mpi_set_ui (e, use_e); } n = mpi_new (nbits); p = q = NULL; do { /* select two (very secret) primes */ if (p) _gcry_mpi_release (p); if (q) _gcry_mpi_release (q); if (use_e) { /* Do an extra test to ensure that the given exponent is suitable. */ p = _gcry_generate_secret_prime (nbits/2, random_level, check_exponent, e); q = _gcry_generate_secret_prime (nbits/2, random_level, check_exponent, e); } else { /* We check the exponent later. */ p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL); q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL); } if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/ mpi_swap(p,q); /* calculate the modulus */ mpi_mul( n, p, q ); } while ( mpi_get_nbits(n) != nbits ); /* calculate Euler totient: phi = (p-1)(q-1) */ t1 = mpi_alloc_secure( mpi_get_nlimbs(p) ); t2 = mpi_alloc_secure( mpi_get_nlimbs(p) ); phi = mpi_snew ( nbits ); g = mpi_snew ( nbits ); f = mpi_snew ( nbits ); mpi_sub_ui( t1, p, 1 ); mpi_sub_ui( t2, q, 1 ); mpi_mul( phi, t1, t2 ); mpi_gcd (g, t1, t2); mpi_fdiv_q(f, phi, g); while (!mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */ { if (use_e) BUG (); /* The prime generator already made sure that we never can get to here. */ mpi_add_ui (e, e, 2); } /* calculate the secret key d = e^1 mod phi */ d = mpi_snew ( nbits ); mpi_invm (d, e, f ); /* calculate the inverse of p and q (used for chinese remainder theorem)*/ u = mpi_snew ( nbits ); mpi_invm(u, p, q ); if( DBG_CIPHER ) { log_mpidump(" p= ", p ); log_mpidump(" q= ", q ); log_mpidump("phi= ", phi ); log_mpidump(" g= ", g ); log_mpidump(" f= ", f ); log_mpidump(" n= ", n ); log_mpidump(" e= ", e ); log_mpidump(" d= ", d ); log_mpidump(" u= ", u ); } _gcry_mpi_release (t1); _gcry_mpi_release (t2); _gcry_mpi_release (phi); _gcry_mpi_release (f); _gcry_mpi_release (g); sk->n = n; sk->e = e; sk->p = p; sk->q = q; sk->d = d; sk->u = u; /* Now we can test our keys. */ if (test_keys (sk, nbits - 64)) { _gcry_mpi_release (sk->n); sk->n = NULL; _gcry_mpi_release (sk->e); sk->e = NULL; _gcry_mpi_release (sk->p); sk->p = NULL; _gcry_mpi_release (sk->q); sk->q = NULL; _gcry_mpi_release (sk->d); sk->d = NULL; _gcry_mpi_release (sk->u); sk->u = NULL; fips_signal_error ("self-test after key generation failed"); return GPG_ERR_SELFTEST_FAILED; } return 0; } +/**************** + * Generate a key pair with a key of size NBITS. + * USE_E = 0 let Libcgrypt decide what exponent to use. + * = 1 request the use of a "secure" exponent; this is required by some + * specification to be 65537. + * > 2 Use this public exponent. If the given exponent + * is not odd one is internally added to it. + * TESTPARMS: If set, do not generate but test whether the p,q is probably prime + * Returns key with zeroes to not break code calling this function. + * TRANSIENT_KEY: If true, generate the primes using the standard RNG. + * Returns: 2 structures filled with all needed values + */ +static gpg_err_code_t +generate_fips (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, + gcry_sexp_t testparms, int transient_key) +{ + gcry_mpi_t p, q; /* the two primes */ + gcry_mpi_t d; /* the private key */ + gcry_mpi_t u; + gcry_mpi_t p1, q1; + gcry_mpi_t n; /* the public key */ + gcry_mpi_t e; /* the exponent */ + gcry_mpi_t g; + gcry_mpi_t minp; + gcry_mpi_t diff, mindiff; + gcry_random_level_t random_level; + unsigned int pbits = nbits/2; + unsigned int i; + int pqswitch; + gpg_err_code_t ec = GPG_ERR_NO_PRIME; + + if (nbits < 1024 || (nbits & 0x1FF)) + return GPG_ERR_INV_VALUE; + if (_gcry_enforced_fips_mode() && nbits != 2048 && nbits != 3072) + return GPG_ERR_INV_VALUE; + + /* The random quality depends on the transient_key flag. */ + random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM; + + if (testparms) + { + /* Parameters to derive the key are given. */ + /* Note that we explicitly need to setup the values of tbl + because some compilers (e.g. OpenWatcom, IRIX) don't allow to + initialize a structure with automatic variables. */ + struct { const char *name; gcry_mpi_t *value; } tbl[] = { + { "e" }, + { "p" }, + { "q" }, + { NULL } + }; + int idx; + gcry_sexp_t oneparm; + + tbl[0].value = &e; + tbl[1].value = &p; + tbl[2].value = &q; + + for (idx=0; tbl[idx].name; idx++) + { + oneparm = sexp_find_token (testparms, tbl[idx].name, 0); + if (oneparm) + { + *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG); + sexp_release (oneparm); + } + } + for (idx=0; tbl[idx].name; idx++) + if (!*tbl[idx].value) + break; + if (tbl[idx].name) + { + /* At least one parameter is missing. */ + for (idx=0; tbl[idx].name; idx++) + _gcry_mpi_release (*tbl[idx].value); + return GPG_ERR_MISSING_VALUE; + } + } + else + { + if (use_e < 65537) + use_e = 65537; /* This is the smallest value allowed by FIPS */ + + e = mpi_alloc ((32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB); + + use_e |= 1; /* make sure this is odd */ + mpi_set_ui (e, use_e); + + p = mpi_snew (pbits); + q = mpi_snew (pbits); + } + + n = mpi_new (nbits); + d = mpi_snew (nbits); + u = mpi_snew (nbits); + + /* prepare approximate minimum p and q */ + minp = mpi_new (pbits); + mpi_set_ui (minp, 0xB504F334); + mpi_lshift (minp, minp, pbits - 32); + + /* prepare minimum p and q difference */ + diff = mpi_new (pbits); + mindiff = mpi_new (pbits - 99); + mpi_set_ui (mindiff, 1); + mpi_lshift (mindiff, mindiff, pbits - 100); + + p1 = mpi_snew (pbits); + q1 = mpi_snew (pbits); + g = mpi_snew (pbits); + + retry: + /* generate p and q */ + for (i = 0; i < 5 * pbits; i++) + { + ploop: + if (!testparms) + { + _gcry_mpi_randomize (p, pbits, random_level); + } + if (mpi_cmp (p, minp) < 0) + { + if (testparms) + goto err; + goto ploop; + } + + mpi_sub_ui (p1, p, 1); + if (mpi_gcd (g, p1, e)) + { + if (_gcry_fips186_4_prime_check (p, pbits) != GPG_ERR_NO_ERROR) + { + /* not a prime */ + if (testparms) + goto err; + } + else + break; + } + else if (testparms) + goto err; + } + if (i >= 5 * pbits) + goto err; + + for (i = 0; i < 5 * pbits; i++) + { + qloop: + if (!testparms) + { + _gcry_mpi_randomize (q, pbits, random_level); + } + if (mpi_cmp (q, minp) < 0) + { + if (testparms) + goto err; + goto qloop; + } + if (mpi_cmp (p, q) > 0) + { + pqswitch = 1; + mpi_sub (diff, p, q); + } + else + { + pqswitch = 0; + mpi_sub (diff, q, p); + } + if (mpi_cmp (diff, mindiff) < 0) + { + if (testparms) + goto err; + goto qloop; + } + + mpi_sub_ui (q1, q, 1); + if (mpi_gcd (g, q1, e)) + { + if (_gcry_fips186_4_prime_check (q, pbits) != GPG_ERR_NO_ERROR) + { + /* not a prime */ + if (testparms) + goto err; + } + else + break; + } + else if (testparms) + goto err; + } + if (i >= 5 * pbits) + goto err; + + if (testparms) + { + mpi_clear (p); + mpi_clear (q); + } + else + { + gcry_mpi_t f; + + if (pqswitch) + { + gcry_mpi_t tmp; + + tmp = p; + p = q; + q = tmp; + } + + f = mpi_snew (nbits); + + /* calculate the modulus */ + mpi_mul (n, p, q); + + /* calculate the secret key d = e^1 mod phi */ + mpi_gcd (g, p1, q1); + mpi_fdiv_q (f, p1, g); + mpi_mul (f, f, q1); + + mpi_invm (d, e, f); + + _gcry_mpi_release (f); + + if (mpi_get_nbits (d) < pbits) + goto retry; + + /* calculate the inverse of p and q (used for chinese remainder theorem)*/ + mpi_invm (u, p, q ); + } + + ec = 0; + + if (DBG_CIPHER) + { + log_mpidump(" p= ", p ); + log_mpidump(" q= ", q ); + log_mpidump(" n= ", n ); + log_mpidump(" e= ", e ); + log_mpidump(" d= ", d ); + log_mpidump(" u= ", u ); + } + + err: + + _gcry_mpi_release (p1); + _gcry_mpi_release (q1); + _gcry_mpi_release (g); + _gcry_mpi_release (minp); + _gcry_mpi_release (mindiff); + _gcry_mpi_release (diff); + + sk->n = n; + sk->e = e; + sk->p = p; + sk->q = q; + sk->d = d; + sk->u = u; + + /* Now we can test our keys. */ + if (ec || (!testparms && test_keys (sk, nbits - 64))) + { + _gcry_mpi_release (sk->n); sk->n = NULL; + _gcry_mpi_release (sk->e); sk->e = NULL; + _gcry_mpi_release (sk->p); sk->p = NULL; + _gcry_mpi_release (sk->q); sk->q = NULL; + _gcry_mpi_release (sk->d); sk->d = NULL; + _gcry_mpi_release (sk->u); sk->u = NULL; + if (!ec) + { + fips_signal_error ("self-test after key generation failed"); + return GPG_ERR_SELFTEST_FAILED; + } + } + + return ec; +} + + /* Helper for generate_x931. */ static gcry_mpi_t gen_x931_parm_xp (unsigned int nbits) { gcry_mpi_t xp; xp = mpi_snew (nbits); _gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM); /* The requirement for Xp is: sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1 We set the two high order bits to 1 to satisfy the lower bound. By using mpi_set_highbit we make sure that the upper bound is satisfied as well. */ mpi_set_highbit (xp, nbits-1); mpi_set_bit (xp, nbits-2); gcry_assert ( mpi_get_nbits (xp) == nbits ); return xp; } /* Helper for generate_x931. */ static gcry_mpi_t gen_x931_parm_xi (void) { gcry_mpi_t xi; xi = mpi_snew (101); _gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM); mpi_set_highbit (xi, 100); gcry_assert ( mpi_get_nbits (xi) == 101 ); return xi; } /* Variant of the standard key generation code using the algorithm from X9.31. Using this algorithm has the advantage that the generation can be made deterministic which is required for CAVS testing. */ static gpg_err_code_t generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value, gcry_sexp_t deriveparms, int *swapped) { gcry_mpi_t p, q; /* The two primes. */ gcry_mpi_t e; /* The public exponent. */ gcry_mpi_t n; /* The public key. */ gcry_mpi_t d; /* The private key */ gcry_mpi_t u; /* The inverse of p and q. */ gcry_mpi_t pm1; /* p - 1 */ gcry_mpi_t qm1; /* q - 1 */ gcry_mpi_t phi; /* Euler totient. */ gcry_mpi_t f, g; /* Helper. */ *swapped = 0; if (e_value == 1) /* Alias for a secure value. */ e_value = 65537; /* Point 1 of section 4.1: k = 1024 + 256s with S >= 0 */ if (nbits < 1024 || (nbits % 256)) return GPG_ERR_INV_VALUE; /* Point 2: 2 <= bitlength(e) < 2^{k-2} Note that we do not need to check the upper bound because we use an unsigned long for E and thus there is no way for E to reach that limit. */ if (e_value < 3) return GPG_ERR_INV_VALUE; /* Our implementaion requires E to be odd. */ if (!(e_value & 1)) return GPG_ERR_INV_VALUE; /* Point 3: e > 0 or e 0 if it is to be randomly generated. We support only a fixed E and thus there is no need for an extra test. */ /* Compute or extract the derive parameters. */ { gcry_mpi_t xp1 = NULL; gcry_mpi_t xp2 = NULL; gcry_mpi_t xp = NULL; gcry_mpi_t xq1 = NULL; gcry_mpi_t xq2 = NULL; gcry_mpi_t xq = NULL; gcry_mpi_t tmpval; if (!deriveparms) { /* Not given: Generate them. */ xp = gen_x931_parm_xp (nbits/2); /* Make sure that |xp - xq| > 2^{nbits - 100} holds. */ tmpval = mpi_snew (nbits/2); do { _gcry_mpi_release (xq); xq = gen_x931_parm_xp (nbits/2); mpi_sub (tmpval, xp, xq); } while (mpi_get_nbits (tmpval) <= (nbits/2 - 100)); _gcry_mpi_release (tmpval); xp1 = gen_x931_parm_xi (); xp2 = gen_x931_parm_xi (); xq1 = gen_x931_parm_xi (); xq2 = gen_x931_parm_xi (); } else { /* Parameters to derive the key are given. */ /* Note that we explicitly need to setup the values of tbl because some compilers (e.g. OpenWatcom, IRIX) don't allow to initialize a structure with automatic variables. */ struct { const char *name; gcry_mpi_t *value; } tbl[] = { { "Xp1" }, { "Xp2" }, { "Xp" }, { "Xq1" }, { "Xq2" }, { "Xq" }, { NULL } }; int idx; gcry_sexp_t oneparm; tbl[0].value = &xp1; tbl[1].value = &xp2; tbl[2].value = &xp; tbl[3].value = &xq1; tbl[4].value = &xq2; tbl[5].value = &xq; for (idx=0; tbl[idx].name; idx++) { oneparm = sexp_find_token (deriveparms, tbl[idx].name, 0); if (oneparm) { *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG); sexp_release (oneparm); } } for (idx=0; tbl[idx].name; idx++) if (!*tbl[idx].value) break; if (tbl[idx].name) { /* At least one parameter is missing. */ for (idx=0; tbl[idx].name; idx++) _gcry_mpi_release (*tbl[idx].value); return GPG_ERR_MISSING_VALUE; } } e = mpi_alloc_set_ui (e_value); /* Find two prime numbers. */ p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL); q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL); _gcry_mpi_release (xp); xp = NULL; _gcry_mpi_release (xp1); xp1 = NULL; _gcry_mpi_release (xp2); xp2 = NULL; _gcry_mpi_release (xq); xq = NULL; _gcry_mpi_release (xq1); xq1 = NULL; _gcry_mpi_release (xq2); xq2 = NULL; if (!p || !q) { _gcry_mpi_release (p); _gcry_mpi_release (q); _gcry_mpi_release (e); return GPG_ERR_NO_PRIME; } } /* Compute the public modulus. We make sure that p is smaller than q to allow the use of the CRT. */ if (mpi_cmp (p, q) > 0 ) { mpi_swap (p, q); *swapped = 1; } n = mpi_new (nbits); mpi_mul (n, p, q); /* Compute the Euler totient: phi = (p-1)(q-1) */ pm1 = mpi_snew (nbits/2); qm1 = mpi_snew (nbits/2); phi = mpi_snew (nbits); mpi_sub_ui (pm1, p, 1); mpi_sub_ui (qm1, q, 1); mpi_mul (phi, pm1, qm1); g = mpi_snew (nbits); gcry_assert (mpi_gcd (g, e, phi)); /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */ mpi_gcd (g, pm1, qm1); f = pm1; pm1 = NULL; _gcry_mpi_release (qm1); qm1 = NULL; mpi_fdiv_q (f, phi, g); _gcry_mpi_release (phi); phi = NULL; d = g; g = NULL; /* Compute the secret key: d = e^{-1} mod lcm(p-1,q-1) */ mpi_invm (d, e, f); /* Compute the inverse of p and q. */ u = f; f = NULL; mpi_invm (u, p, q ); if( DBG_CIPHER ) { if (*swapped) log_debug ("p and q are swapped\n"); log_mpidump(" p", p ); log_mpidump(" q", q ); log_mpidump(" n", n ); log_mpidump(" e", e ); log_mpidump(" d", d ); log_mpidump(" u", u ); } sk->n = n; sk->e = e; sk->p = p; sk->q = q; sk->d = d; sk->u = u; /* Now we can test our keys. */ if (test_keys (sk, nbits - 64)) { _gcry_mpi_release (sk->n); sk->n = NULL; _gcry_mpi_release (sk->e); sk->e = NULL; _gcry_mpi_release (sk->p); sk->p = NULL; _gcry_mpi_release (sk->q); sk->q = NULL; _gcry_mpi_release (sk->d); sk->d = NULL; _gcry_mpi_release (sk->u); sk->u = NULL; fips_signal_error ("self-test after key generation failed"); return GPG_ERR_SELFTEST_FAILED; } return 0; } /**************** * Test whether the secret key is valid. * Returns: true if this is a valid key. */ static int check_secret_key( RSA_secret_key *sk ) { int rc; gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 ); mpi_mul(temp, sk->p, sk->q ); rc = mpi_cmp( temp, sk->n ); mpi_free(temp); return !rc; } /**************** * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT. * * c = m^e mod n * * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY. */ static void public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey ) { if( output == input ) /* powm doesn't like output and input the same */ { gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 ); mpi_powm( x, input, pkey->e, pkey->n ); mpi_set(output, x); mpi_free(x); } else mpi_powm( output, input, pkey->e, pkey->n ); } #if 0 static void stronger_key_check ( RSA_secret_key *skey ) { gcry_mpi_t t = mpi_alloc_secure ( 0 ); gcry_mpi_t t1 = mpi_alloc_secure ( 0 ); gcry_mpi_t t2 = mpi_alloc_secure ( 0 ); gcry_mpi_t phi = mpi_alloc_secure ( 0 ); /* check that n == p * q */ mpi_mul( t, skey->p, skey->q); if (mpi_cmp( t, skey->n) ) log_info ( "RSA Oops: n != p * q\n" ); /* check that p is less than q */ if( mpi_cmp( skey->p, skey->q ) > 0 ) { log_info ("RSA Oops: p >= q - fixed\n"); _gcry_mpi_swap ( skey->p, skey->q); } /* check that e divides neither p-1 nor q-1 */ mpi_sub_ui(t, skey->p, 1 ); mpi_fdiv_r(t, t, skey->e ); if ( !mpi_cmp_ui( t, 0) ) log_info ( "RSA Oops: e divides p-1\n" ); mpi_sub_ui(t, skey->q, 1 ); mpi_fdiv_r(t, t, skey->e ); if ( !mpi_cmp_ui( t, 0) ) log_info ( "RSA Oops: e divides q-1\n" ); /* check that d is correct */ mpi_sub_ui( t1, skey->p, 1 ); mpi_sub_ui( t2, skey->q, 1 ); mpi_mul( phi, t1, t2 ); gcry_mpi_gcd(t, t1, t2); mpi_fdiv_q(t, phi, t); mpi_invm(t, skey->e, t ); if ( mpi_cmp(t, skey->d ) ) { log_info ( "RSA Oops: d is wrong - fixed\n"); mpi_set (skey->d, t); log_printmpi (" fixed d", skey->d); } /* check for correctness of u */ mpi_invm(t, skey->p, skey->q ); if ( mpi_cmp(t, skey->u ) ) { log_info ( "RSA Oops: u is wrong - fixed\n"); mpi_set (skey->u, t); log_printmpi (" fixed u", skey->u); } log_info ( "RSA secret key check finished\n"); mpi_free (t); mpi_free (t1); mpi_free (t2); mpi_free (phi); } #endif /**************** * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT. * * m = c^d mod n * * Or faster: * * m1 = c ^ (d mod (p-1)) mod p * m2 = c ^ (d mod (q-1)) mod q * h = u * (m2 - m1) mod q * m = m1 + h * p * * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY. */ static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey ) { /* Remove superfluous leading zeroes from INPUT. */ mpi_normalize (input); if (!skey->p || !skey->q || !skey->u) { mpi_powm (output, input, skey->d, skey->n); } else { gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); gcry_mpi_t h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); /* m1 = c ^ (d mod (p-1)) mod p */ mpi_sub_ui( h, skey->p, 1 ); mpi_fdiv_r( h, skey->d, h ); mpi_powm( m1, input, h, skey->p ); /* m2 = c ^ (d mod (q-1)) mod q */ mpi_sub_ui( h, skey->q, 1 ); mpi_fdiv_r( h, skey->d, h ); mpi_powm( m2, input, h, skey->q ); /* h = u * ( m2 - m1 ) mod q */ mpi_sub( h, m2, m1 ); if ( mpi_has_sign ( h ) ) mpi_add ( h, h, skey->q ); mpi_mulm( h, skey->u, h, skey->q ); /* m = m1 + h * p */ mpi_mul ( h, h, skey->p ); mpi_add ( output, m1, h ); mpi_free ( h ); mpi_free ( m1 ); mpi_free ( m2 ); } } /********************************************* ************** interface ****************** *********************************************/ static gcry_err_code_t rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) { gpg_err_code_t ec; unsigned int nbits; unsigned long evalue; RSA_secret_key sk; gcry_sexp_t deriveparms; int flags = 0; gcry_sexp_t l1; gcry_sexp_t swap_info = NULL; memset (&sk, 0, sizeof sk); ec = _gcry_pk_util_get_nbits (genparms, &nbits); if (ec) return ec; ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue); if (ec) return ec; /* Parse the optional flags list. */ l1 = sexp_find_token (genparms, "flags", 0); if (l1) { ec = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); sexp_release (l1); if (ec) return ec; } deriveparms = (genparms? sexp_find_token (genparms, "derive-parms", 0) : NULL); if (!deriveparms) { /* Parse the optional "use-x931" flag. */ l1 = sexp_find_token (genparms, "use-x931", 0); if (l1) { flags |= PUBKEY_FLAG_USE_X931; sexp_release (l1); } } - if (deriveparms || (flags & PUBKEY_FLAG_USE_X931) || fips_mode ()) + if (deriveparms || (flags & PUBKEY_FLAG_USE_X931)) { int swapped; ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped); sexp_release (deriveparms); if (!ec && swapped) ec = sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1); } else { /* Parse the optional "transient-key" flag. */ if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY)) { l1 = sexp_find_token (genparms, "transient-key", 0); if (l1) { flags |= PUBKEY_FLAG_TRANSIENT_KEY; sexp_release (l1); } } + deriveparms = (genparms? sexp_find_token (genparms, "test-parms", 0) + /**/ : NULL); + /* Generate. */ - ec = generate_std (&sk, nbits, evalue, - !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); + if (deriveparms || fips_mode()) + { + ec = generate_fips (&sk, nbits, evalue, deriveparms, + !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); + } + else + { + ec = generate_std (&sk, nbits, evalue, + !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); + } + sexp_release (deriveparms); } if (!ec) { ec = sexp_build (r_skey, NULL, "(key-data" " (public-key" " (rsa(n%m)(e%m)))" " (private-key" " (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))" " %S)", sk.n, sk.e, sk.n, sk.e, sk.d, sk.p, sk.q, sk.u, swap_info); } mpi_free (sk.n); mpi_free (sk.e); mpi_free (sk.p); mpi_free (sk.q); mpi_free (sk.d); mpi_free (sk.u); sexp_release (swap_info); return ec; } static gcry_err_code_t rsa_check_secret_key (gcry_sexp_t keyparms) { gcry_err_code_t rc; RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL}; /* To check the key we need the optional parameters. */ rc = sexp_extract_param (keyparms, NULL, "nedpqu", &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u, NULL); if (rc) goto leave; if (!check_secret_key (&sk)) rc = GPG_ERR_BAD_SECKEY; leave: _gcry_mpi_release (sk.n); _gcry_mpi_release (sk.e); _gcry_mpi_release (sk.d); _gcry_mpi_release (sk.p); _gcry_mpi_release (sk.q); _gcry_mpi_release (sk.u); if (DBG_CIPHER) log_debug ("rsa_testkey => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_mpi_t data = NULL; RSA_public_key pk = {NULL, NULL}; gcry_mpi_t ciph = NULL; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_mpidump ("rsa_encrypt data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_mpidump ("rsa_encrypt n", pk.n); log_mpidump ("rsa_encrypt e", pk.e); } /* Do RSA computation and build result. */ ciph = mpi_new (0); public (ciph, data, &pk); if (DBG_CIPHER) log_mpidump ("rsa_encrypt res", ciph); if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN)) { /* We need to make sure to return the correct length to avoid problems with missing leading zeroes. */ unsigned char *em; size_t emlen = (mpi_get_nbits (pk.n)+7)/8; rc = _gcry_mpi_to_octet_string (&em, NULL, ciph, emlen); if (!rc) { rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%b)))", (int)emlen, em); xfree (em); } } else rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%m)))", ciph); leave: _gcry_mpi_release (ciph); _gcry_mpi_release (pk.n); _gcry_mpi_release (pk.e); _gcry_mpi_release (data); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_encrypt => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gpg_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; gcry_mpi_t data = NULL; RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL}; gcry_mpi_t plain = NULL; gcry_mpi_t r = NULL; /* Random number needed for blinding. */ gcry_mpi_t ri = NULL; /* Modular multiplicative inverse of r. */ gcry_mpi_t bldata = NULL;/* Blinded data to decrypt. */ unsigned char *unpad = NULL; size_t unpadlen = 0; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_preparse_encval (s_data, rsa_names, &l1, &ctx); if (rc) goto leave; rc = sexp_extract_param (l1, NULL, "a", &data, NULL); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_decrypt data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?", &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("rsa_decrypt n", sk.n); log_printmpi ("rsa_decrypt e", sk.e); if (!fips_mode ()) { log_printmpi ("rsa_decrypt d", sk.d); log_printmpi ("rsa_decrypt p", sk.p); log_printmpi ("rsa_decrypt q", sk.q); log_printmpi ("rsa_decrypt u", sk.u); } } /* Better make sure that there are no superfluous leading zeroes in the input and it has not been "padded" using multiples of N. This mitigates side-channel attacks (CVE-2013-4576). */ mpi_normalize (data); mpi_fdiv_r (data, data, sk.n); /* Allocate MPI for the plaintext. */ plain = mpi_snew (ctx.nbits); /* We use blinding by default to mitigate timing attacks which can be practically mounted over the network as shown by Brumley and Boney in 2003. */ if (!(ctx.flags & PUBKEY_FLAG_NO_BLINDING)) { /* First, we need a random number r between 0 and n - 1, which is relatively prime to n (i.e. it is neither p nor q). The random number needs to be only unpredictable, thus we employ the gcry_create_nonce function by using GCRY_WEAK_RANDOM with gcry_mpi_randomize. */ r = mpi_snew (ctx.nbits); ri = mpi_snew (ctx.nbits); bldata = mpi_snew (ctx.nbits); do { _gcry_mpi_randomize (r, ctx.nbits, GCRY_WEAK_RANDOM); mpi_mod (r, r, sk.n); } while (!mpi_invm (ri, r, sk.n)); /* Do blinding. We calculate: y = (x * r^e) mod n, where r is the random number, e is the public exponent, x is the non-blinded data and n is the RSA modulus. */ mpi_powm (bldata, r, sk.e, sk.n); mpi_mulm (bldata, bldata, data, sk.n); /* Perform decryption. */ secret (plain, bldata, &sk); _gcry_mpi_release (bldata); bldata = NULL; /* Undo blinding. Here we calculate: y = (x * r^-1) mod n, where x is the blinded decrypted data, ri is the modular multiplicative inverse of r and n is the RSA modulus. */ mpi_mulm (plain, plain, ri, sk.n); _gcry_mpi_release (r); r = NULL; _gcry_mpi_release (ri); ri = NULL; } else secret (plain, data, &sk); if (DBG_CIPHER) log_printmpi ("rsa_decrypt res", plain); /* Reverse the encoding and build the s-expression. */ switch (ctx.encoding) { case PUBKEY_ENC_PKCS1: rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain); mpi_free (plain); plain = NULL; if (!rc) rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad); break; case PUBKEY_ENC_OAEP: rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen, ctx.nbits, ctx.hash_algo, plain, ctx.label, ctx.labellen); mpi_free (plain); plain = NULL; if (!rc) rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad); break; default: /* Raw format. For backward compatibility we need to assume a signed mpi by using the sexp format string "%m". */ rc = sexp_build (r_plain, NULL, (ctx.flags & PUBKEY_FLAG_LEGACYRESULT) ? "%m":"(value %m)", plain); break; } leave: xfree (unpad); _gcry_mpi_release (plain); _gcry_mpi_release (sk.n); _gcry_mpi_release (sk.e); _gcry_mpi_release (sk.d); _gcry_mpi_release (sk.p); _gcry_mpi_release (sk.q); _gcry_mpi_release (sk.u); _gcry_mpi_release (data); _gcry_mpi_release (r); _gcry_mpi_release (ri); _gcry_mpi_release (bldata); sexp_release (l1); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_decrypt => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gpg_err_code_t rc; struct pk_encoding_ctx ctx; gcry_mpi_t data = NULL; RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL}; RSA_public_key pk; gcry_mpi_t sig = NULL; gcry_mpi_t result = NULL; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_sign data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?", &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("rsa_sign n", sk.n); log_printmpi ("rsa_sign e", sk.e); if (!fips_mode ()) { log_printmpi ("rsa_sign d", sk.d); log_printmpi ("rsa_sign p", sk.p); log_printmpi ("rsa_sign q", sk.q); log_printmpi ("rsa_sign u", sk.u); } } /* Do RSA computation. */ sig = mpi_new (0); secret (sig, data, &sk); if (DBG_CIPHER) log_printmpi ("rsa_sign res", sig); /* Check that the created signature is good. This detects a failure of the CRT algorithm (Lenstra's attack on RSA's use of the CRT). */ result = mpi_new (0); pk.n = sk.n; pk.e = sk.e; public (result, sig, &pk); if (mpi_cmp (result, data)) { rc = GPG_ERR_BAD_SIGNATURE; goto leave; } /* Convert the result. */ if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN)) { /* We need to make sure to return the correct length to avoid problems with missing leading zeroes. */ unsigned char *em; size_t emlen = (mpi_get_nbits (sk.n)+7)/8; rc = _gcry_mpi_to_octet_string (&em, NULL, sig, emlen); if (!rc) { rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%b)))", (int)emlen, em); xfree (em); } } else rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%M)))", sig); leave: _gcry_mpi_release (result); _gcry_mpi_release (sig); _gcry_mpi_release (sk.n); _gcry_mpi_release (sk.e); _gcry_mpi_release (sk.d); _gcry_mpi_release (sk.p); _gcry_mpi_release (sk.q); _gcry_mpi_release (sk.u); _gcry_mpi_release (data); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_sign => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; gcry_mpi_t sig = NULL; gcry_mpi_t data = NULL; RSA_public_key pk = { NULL, NULL }; gcry_mpi_t result = NULL; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_verify data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the signature value. */ rc = _gcry_pk_util_preparse_sigval (s_sig, rsa_names, &l1, NULL); if (rc) goto leave; rc = sexp_extract_param (l1, NULL, "s", &sig, NULL); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_verify sig", sig); /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("rsa_verify n", pk.n); log_printmpi ("rsa_verify e", pk.e); } /* Do RSA computation and compare. */ result = mpi_new (0); public (result, sig, &pk); if (DBG_CIPHER) log_printmpi ("rsa_verify cmp", result); if (ctx.verify_cmp) rc = ctx.verify_cmp (&ctx, result); else rc = mpi_cmp (result, data) ? GPG_ERR_BAD_SIGNATURE : 0; leave: _gcry_mpi_release (result); _gcry_mpi_release (pk.n); _gcry_mpi_release (pk.e); _gcry_mpi_release (data); _gcry_mpi_release (sig); sexp_release (l1); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_verify => %s\n", rc?gpg_strerror (rc):"Good"); return rc; } /* Return the number of bits for the key described by PARMS. On error * 0 is returned. The format of PARMS starts with the algorithm name; * for example: * * (rsa * (n ) * (e )) * * More parameters may be given but we only need N here. */ static unsigned int rsa_get_nbits (gcry_sexp_t parms) { gcry_sexp_t l1; gcry_mpi_t n; unsigned int nbits; l1 = sexp_find_token (parms, "n", 1); if (!l1) return 0; /* Parameter N not found. */ n = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG); sexp_release (l1); nbits = n? mpi_get_nbits (n) : 0; _gcry_mpi_release (n); return nbits; } /* Compute a keygrip. MD is the hash context which we are going to update. KEYPARAM is an S-expression with the key parameters, this is usually a public key but may also be a secret key. An example of such an S-expression is: (rsa (n #00B...#) (e #010001#)) PKCS-15 says that for RSA only the modulus should be hashed - however, it is not clear whether this is meant to use the raw bytes (assuming this is an unsigned integer) or whether the DER required 0 should be prefixed. We hash the raw bytes. */ static gpg_err_code_t compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam) { gcry_sexp_t l1; const char *data; size_t datalen; l1 = sexp_find_token (keyparam, "n", 1); if (!l1) return GPG_ERR_NO_OBJ; data = sexp_nth_data (l1, 1, &datalen); if (!data) { sexp_release (l1); return GPG_ERR_NO_OBJ; } _gcry_md_write (md, data, datalen); sexp_release (l1); return 0; } /* Self-test section. */ static const char * selftest_sign_2048 (gcry_sexp_t pkey, gcry_sexp_t skey) { static const char sample_data[] = "(data (flags pkcs1)" " (hash sha256 #11223344556677889900aabbccddeeff" /**/ "102030405060708090a0b0c0d0f01121#))"; static const char sample_data_bad[] = "(data (flags pkcs1)" " (hash sha256 #11223344556677889900aabbccddeeff" /**/ "802030405060708090a0b0c0d0f01121#))"; const char *errtxt = NULL; gcry_error_t err; gcry_sexp_t data = NULL; gcry_sexp_t data_bad = NULL; gcry_sexp_t sig = NULL; /* raw signature data reference */ const char ref_data[] = "6252a19a11e1d5155ed9376036277193d644fa239397fff03e9b92d6f86415d6" "d30da9273775f290e580d038295ff8ff89522becccfa6ae870bf76b76df402a8" "54f69347e3db3de8e1e7d4dada281ec556810c7a8ecd0b5f51f9b1c0e7aa7557" "61aa2b8ba5f811304acc6af0eca41fe49baf33bf34eddaf44e21e036ac7f0b68" "03cdef1c60021fb7b5b97ebacdd88ab755ce29af568dbc5728cc6e6eff42618d" "62a0386ca8beed46402bdeeef29b6a3feded906bace411a06a39192bf516ae10" "67e4320fa8ea113968525f4574d022a3ceeaafdc41079efe1f22cc94bf59d8d3" "328085da9674857db56de5978a62394aab48aa3b72e23a1b16260cfd9daafe65"; gcry_mpi_t ref_mpi = NULL; gcry_mpi_t sig_mpi = NULL; err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data)); if (!err) err = sexp_sscan (&data_bad, NULL, sample_data_bad, strlen (sample_data_bad)); if (err) { errtxt = "converting data failed"; goto leave; } err = _gcry_pk_sign (&sig, data, skey); if (err) { errtxt = "signing failed"; goto leave; } err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL); if (err) { errtxt = "converting ref_data to mpi failed"; goto leave; } err = _gcry_sexp_extract_param(sig, "sig-val!rsa", "s", &sig_mpi, NULL); if (err) { errtxt = "extracting signature data failed"; goto leave; } if (mpi_cmp (sig_mpi, ref_mpi)) { errtxt = "signature does not match reference data"; goto leave; } err = _gcry_pk_verify (sig, data, pkey); if (err) { errtxt = "verify failed"; goto leave; } err = _gcry_pk_verify (sig, data_bad, pkey); if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE) { errtxt = "bad signature not detected"; goto leave; } leave: sexp_release (sig); sexp_release (data_bad); sexp_release (data); _gcry_mpi_release (ref_mpi); _gcry_mpi_release (sig_mpi); return errtxt; } /* Given an S-expression ENCR_DATA of the form: (enc-val (rsa (a a-value))) as returned by gcry_pk_decrypt, return the the A-VALUE. On error, return NULL. */ static gcry_mpi_t extract_a_from_sexp (gcry_sexp_t encr_data) { gcry_sexp_t l1, l2, l3; gcry_mpi_t a_value; l1 = sexp_find_token (encr_data, "enc-val", 0); if (!l1) return NULL; l2 = sexp_find_token (l1, "rsa", 0); sexp_release (l1); if (!l2) return NULL; l3 = sexp_find_token (l2, "a", 0); sexp_release (l2); if (!l3) return NULL; a_value = sexp_nth_mpi (l3, 1, 0); sexp_release (l3); return a_value; } static const char * selftest_encr_2048 (gcry_sexp_t pkey, gcry_sexp_t skey) { const char *errtxt = NULL; gcry_error_t err; static const char plaintext[] = "Jim quickly realized that the beautiful gowns are expensive."; gcry_sexp_t plain = NULL; gcry_sexp_t encr = NULL; gcry_mpi_t ciphertext = NULL; gcry_sexp_t decr = NULL; char *decr_plaintext = NULL; gcry_sexp_t tmplist = NULL; /* expected result of encrypting the plaintext with sample_secret_key */ static const char ref_data[] = "18022e2593a402a737caaa93b4c7e750e20ca265452980e1d6b7710fbd3e" "7dce72be5c2110fb47691cb38f42170ee3b4a37f2498d4a51567d762585e" "4cb81d04fbc7df4144f8e5eac2d4b8688521b64011f11d7ad53f4c874004" "819856f2e2a6f83d1c9c4e73ac26089789c14482b0b8d44139133c88c4a5" "2dba9dd6d6ffc622666b7d129168333d999706af30a2d7d272db7734e5ed" "fb8c64ea3018af3ad20f4a013a5060cb0f5e72753967bebe294280a6ed0d" "dbd3c4f11d0a8696e9d32a0dc03deb0b5e49b2cbd1503392642d4e1211f3" "e8e2ee38abaa3671ccd57fcde8ca76e85fd2cb77c35706a970a213a27352" "cec92a9604d543ddb5fc478ff50e0622"; gcry_mpi_t ref_mpi = NULL; /* Put the plaintext into an S-expression. */ err = sexp_build (&plain, NULL, "(data (flags raw) (value %s))", plaintext); if (err) { errtxt = "converting data failed"; goto leave; } /* Encrypt. */ err = _gcry_pk_encrypt (&encr, plain, pkey); if (err) { errtxt = "encrypt failed"; goto leave; } err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL); if (err) { errtxt = "converting encrydata to mpi failed"; goto leave; } /* Extraxt the ciphertext from the returned S-expression. */ /*sexp_dump (encr);*/ ciphertext = extract_a_from_sexp (encr); if (!ciphertext) { errtxt = "gcry_pk_decrypt returned garbage"; goto leave; } /* Check that the ciphertext does no match the plaintext. */ /* _gcry_log_printmpi ("plaintext", plaintext); */ /* _gcry_log_printmpi ("ciphertxt", ciphertext); */ if (mpi_cmp (ref_mpi, ciphertext)) { errtxt = "ciphertext doesn't match reference data"; goto leave; } /* Decrypt. */ err = _gcry_pk_decrypt (&decr, encr, skey); if (err) { errtxt = "decrypt failed"; goto leave; } /* Extract the decrypted data from the S-expression. Note that the output of gcry_pk_decrypt depends on whether a flags lists occurs in its input data. Because we passed the output of gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value won't be there as of today. To be prepared for future changes we take care of it anyway. */ tmplist = sexp_find_token (decr, "value", 0); if (tmplist) decr_plaintext = sexp_nth_string (tmplist, 1); else decr_plaintext = sexp_nth_string (decr, 0); if (!decr_plaintext) { errtxt = "decrypt returned no plaintext"; goto leave; } /* Check that the decrypted plaintext matches the original plaintext. */ if (strcmp (plaintext, decr_plaintext)) { errtxt = "mismatch"; goto leave; } leave: sexp_release (tmplist); xfree (decr_plaintext); sexp_release (decr); _gcry_mpi_release (ciphertext); _gcry_mpi_release (ref_mpi); sexp_release (encr); sexp_release (plain); return errtxt; } static gpg_err_code_t selftests_rsa (selftest_report_func_t report) { const char *what; const char *errtxt; gcry_error_t err; gcry_sexp_t skey = NULL; gcry_sexp_t pkey = NULL; /* Convert the S-expressions into the internal representation. */ what = "convert"; err = sexp_sscan (&skey, NULL, sample_secret_key, strlen (sample_secret_key)); if (!err) err = sexp_sscan (&pkey, NULL, sample_public_key, strlen (sample_public_key)); if (err) { errtxt = _gcry_strerror (err); goto failed; } what = "key consistency"; err = _gcry_pk_testkey (skey); if (err) { errtxt = _gcry_strerror (err); goto failed; } what = "sign"; errtxt = selftest_sign_2048 (pkey, skey); if (errtxt) goto failed; what = "encrypt"; errtxt = selftest_encr_2048 (pkey, skey); if (errtxt) goto failed; sexp_release (pkey); sexp_release (skey); return 0; /* Succeeded. */ failed: sexp_release (pkey); sexp_release (skey); if (report) report ("pubkey", GCRY_PK_RSA, what, errtxt); return GPG_ERR_SELFTEST_FAILED; } /* Run a full self-test for ALGO and return 0 on success. */ static gpg_err_code_t run_selftests (int algo, int extended, selftest_report_func_t report) { gpg_err_code_t ec; (void)extended; switch (algo) { case GCRY_PK_RSA: ec = selftests_rsa (report); break; default: ec = GPG_ERR_PUBKEY_ALGO; break; } return ec; } gcry_pk_spec_t _gcry_pubkey_spec_rsa = { GCRY_PK_RSA, { 0, 1 }, (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR), "RSA", rsa_names, "ne", "nedpqu", "a", "s", "n", rsa_generate, rsa_check_secret_key, rsa_encrypt, rsa_decrypt, rsa_sign, rsa_verify, rsa_get_nbits, run_selftests, compute_keygrip }; diff --git a/src/g10lib.h b/src/g10lib.h index 1070d9e9..170ffa16 100644 --- a/src/g10lib.h +++ b/src/g10lib.h @@ -1,442 +1,445 @@ /* g10lib.h - Internal definitions for libgcrypt * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005 * 2007, 2011 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser general Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ /* This header is to be used inside of libgcrypt in place of gcrypt.h. This way we can better distinguish between internal and external usage of gcrypt.h. */ #ifndef G10LIB_H #define G10LIB_H 1 #ifdef _GCRYPT_H #error gcrypt.h already included #endif #ifndef _GCRYPT_IN_LIBGCRYPT #error something is wrong with config.h #endif #include #include #include "visibility.h" #include "types.h" /* Attribute handling macros. */ #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 5 ) #define JNLIB_GCC_M_FUNCTION 1 #define JNLIB_GCC_A_NR __attribute__ ((noreturn)) #define JNLIB_GCC_A_PRINTF( f, a ) __attribute__ ((format (printf,f,a))) #define JNLIB_GCC_A_NR_PRINTF( f, a ) \ __attribute__ ((noreturn, format (printf,f,a))) #define GCC_ATTR_NORETURN __attribute__ ((__noreturn__)) #else #define JNLIB_GCC_A_NR #define JNLIB_GCC_A_PRINTF( f, a ) #define JNLIB_GCC_A_NR_PRINTF( f, a ) #define GCC_ATTR_NORETURN #endif #if __GNUC__ >= 3 /* According to glibc this attribute is available since 2.8 however we better play safe and use it only with gcc 3 or newer. */ #define GCC_ATTR_FORMAT_ARG(a) __attribute__ ((format_arg (a))) #else #define GCC_ATTR_FORMAT_ARG(a) #endif /* I am not sure since when the unused attribute is really supported. In any case it it only needed for gcc versions which print a warning. Thus let us require gcc >= 3.5. */ #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 5 ) #define GCC_ATTR_UNUSED __attribute__ ((unused)) #else #define GCC_ATTR_UNUSED #endif /* Gettext macros. */ #define _(a) _gcry_gettext(a) #define N_(a) (a) /* Some handy macros */ #ifndef STR #define STR(v) #v #endif #define STR2(v) STR(v) #define DIM(v) (sizeof(v)/sizeof((v)[0])) #define DIMof(type,member) DIM(((type *)0)->member) /*-- src/global.c -*/ int _gcry_global_is_operational (void); gcry_err_code_t _gcry_vcontrol (enum gcry_ctl_cmds cmd, va_list arg_ptr); void _gcry_check_heap (const void *a); int _gcry_get_debug_flag (unsigned int mask); /* Malloc functions and common wrapper macros. */ void *_gcry_malloc (size_t n) _GCRY_GCC_ATTR_MALLOC; void *_gcry_calloc (size_t n, size_t m) _GCRY_GCC_ATTR_MALLOC; void *_gcry_malloc_secure (size_t n) _GCRY_GCC_ATTR_MALLOC; void *_gcry_calloc_secure (size_t n, size_t m) _GCRY_GCC_ATTR_MALLOC; void *_gcry_realloc (void *a, size_t n); char *_gcry_strdup (const char *string) _GCRY_GCC_ATTR_MALLOC; void *_gcry_xmalloc (size_t n) _GCRY_GCC_ATTR_MALLOC; void *_gcry_xcalloc (size_t n, size_t m) _GCRY_GCC_ATTR_MALLOC; void *_gcry_xmalloc_secure (size_t n) _GCRY_GCC_ATTR_MALLOC; void *_gcry_xcalloc_secure (size_t n, size_t m) _GCRY_GCC_ATTR_MALLOC; void *_gcry_xrealloc (void *a, size_t n); char *_gcry_xstrdup (const char * a) _GCRY_GCC_ATTR_MALLOC; void _gcry_free (void *a); int _gcry_is_secure (const void *a) _GCRY_GCC_ATTR_PURE; #define xtrymalloc(a) _gcry_malloc ((a)) #define xtrycalloc(a,b) _gcry_calloc ((a),(b)) #define xtrymalloc_secure(a) _gcry_malloc_secure ((a)) #define xtrycalloc_secure(a,b) _gcry_calloc_secure ((a),(b)) #define xtryrealloc(a,b) _gcry_realloc ((a),(b)) #define xtrystrdup(a) _gcry_strdup ((a)) #define xmalloc(a) _gcry_xmalloc ((a)) #define xcalloc(a,b) _gcry_xcalloc ((a),(b)) #define xmalloc_secure(a) _gcry_xmalloc_secure ((a)) #define xcalloc_secure(a,b) _gcry_xcalloc_secure ((a),(b)) #define xrealloc(a,b) _gcry_xrealloc ((a),(b)) #define xstrdup(a) _gcry_xstrdup ((a)) #define xfree(a) _gcry_free ((a)) /*-- src/misc.c --*/ #if defined(JNLIB_GCC_M_FUNCTION) || __STDC_VERSION__ >= 199901L void _gcry_bug (const char *file, int line, const char *func) GCC_ATTR_NORETURN; void _gcry_assert_failed (const char *expr, const char *file, int line, const char *func) GCC_ATTR_NORETURN; #else void _gcry_bug (const char *file, int line); void _gcry_assert_failed (const char *expr, const char *file, int line); #endif void _gcry_divide_by_zero (void) JNLIB_GCC_A_NR; const char *_gcry_gettext (const char *key) GCC_ATTR_FORMAT_ARG(1); void _gcry_fatal_error(int rc, const char *text ) JNLIB_GCC_A_NR; void _gcry_logv (int level, const char *fmt, va_list arg_ptr) JNLIB_GCC_A_PRINTF(2,0); void _gcry_log( int level, const char *fmt, ... ) JNLIB_GCC_A_PRINTF(2,3); void _gcry_log_bug( const char *fmt, ... ) JNLIB_GCC_A_NR_PRINTF(1,2); void _gcry_log_fatal( const char *fmt, ... ) JNLIB_GCC_A_NR_PRINTF(1,2); void _gcry_log_error( const char *fmt, ... ) JNLIB_GCC_A_PRINTF(1,2); void _gcry_log_info( const char *fmt, ... ) JNLIB_GCC_A_PRINTF(1,2); int _gcry_log_info_with_dummy_fp (FILE *fp, const char *fmt, ... ) JNLIB_GCC_A_PRINTF(2,3); void _gcry_log_debug( const char *fmt, ... ) JNLIB_GCC_A_PRINTF(1,2); void _gcry_log_printf ( const char *fmt, ... ) JNLIB_GCC_A_PRINTF(1,2); void _gcry_log_printhex (const char *text, const void *buffer, size_t length); void _gcry_log_printmpi (const char *text, gcry_mpi_t mpi); void _gcry_log_printsxp (const char *text, gcry_sexp_t sexp); void _gcry_set_log_verbosity( int level ); int _gcry_log_verbosity( int level ); #ifdef JNLIB_GCC_M_FUNCTION #define BUG() _gcry_bug( __FILE__ , __LINE__, __FUNCTION__ ) #define gcry_assert(expr) ((expr)? (void)0 \ : _gcry_assert_failed (STR(expr), __FILE__, __LINE__, __FUNCTION__)) #elif __STDC_VERSION__ >= 199901L #define BUG() _gcry_bug( __FILE__ , __LINE__, __func__ ) #define gcry_assert(expr) ((expr)? (void)0 \ : _gcry_assert_failed (STR(expr), __FILE__, __LINE__, __func__)) #else #define BUG() _gcry_bug( __FILE__ , __LINE__ ) #define gcry_assert(expr) ((expr)? (void)0 \ : _gcry_assert_failed (STR(expr), __FILE__, __LINE__)) #endif #define log_bug _gcry_log_bug #define log_fatal _gcry_log_fatal #define log_error _gcry_log_error #define log_info _gcry_log_info #define log_debug _gcry_log_debug #define log_printf _gcry_log_printf #define log_printhex _gcry_log_printhex #define log_printmpi _gcry_log_printmpi #define log_printsxp _gcry_log_printsxp /* Compatibility macro. */ #define log_mpidump _gcry_log_printmpi /* Tokeninze STRING and return a malloced array. */ char **_gcry_strtokenize (const char *string, const char *delim); /*-- src/hwfeatures.c --*/ #define HWF_PADLOCK_RNG (1 << 0) #define HWF_PADLOCK_AES (1 << 1) #define HWF_PADLOCK_SHA (1 << 2) #define HWF_PADLOCK_MMUL (1 << 3) #define HWF_INTEL_CPU (1 << 4) #define HWF_INTEL_FAST_SHLD (1 << 5) #define HWF_INTEL_BMI2 (1 << 6) #define HWF_INTEL_SSSE3 (1 << 7) #define HWF_INTEL_SSE4_1 (1 << 8) #define HWF_INTEL_PCLMUL (1 << 9) #define HWF_INTEL_AESNI (1 << 10) #define HWF_INTEL_RDRAND (1 << 11) #define HWF_INTEL_AVX (1 << 12) #define HWF_INTEL_AVX2 (1 << 13) #define HWF_ARM_NEON (1 << 14) gpg_err_code_t _gcry_disable_hw_feature (const char *name); void _gcry_detect_hw_features (void); unsigned int _gcry_get_hw_features (void); const char *_gcry_enum_hw_features (int idx, unsigned int *r_feature); /*-- mpi/mpiutil.c --*/ const char *_gcry_mpi_get_hw_config (void); /*-- cipher/pubkey.c --*/ /* FIXME: shouldn't this go into mpi.h? */ #ifndef mpi_powm #define mpi_powm(w,b,e,m) gcry_mpi_powm( (w), (b), (e), (m) ) #endif /*-- primegen.c --*/ gcry_err_code_t _gcry_primegen_init (void); gcry_mpi_t _gcry_generate_secret_prime (unsigned int nbits, gcry_random_level_t random_level, int (*extra_check)(void*, gcry_mpi_t), void *extra_check_arg); gcry_mpi_t _gcry_generate_public_prime (unsigned int nbits, gcry_random_level_t random_level, int (*extra_check)(void*, gcry_mpi_t), void *extra_check_arg); gcry_err_code_t _gcry_generate_elg_prime (int mode, unsigned int pbits, unsigned int qbits, gcry_mpi_t g, gcry_mpi_t *r_prime, gcry_mpi_t **factors); gcry_mpi_t _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); gpg_err_code_t _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, const void *seed, size_t seedlen, gcry_mpi_t *r_q, gcry_mpi_t *r_p, int *r_counter, void **r_seed, size_t *r_seedlen); gpg_err_code_t _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, const void *seed, size_t seedlen, gcry_mpi_t *r_q, gcry_mpi_t *r_p, int *r_counter, void **r_seed, size_t *r_seedlen, int *r_hashalgo); +gpg_err_code_t _gcry_fips186_4_prime_check (const gcry_mpi_t x, + unsigned int bits); + /* Replacements of missing functions (missing-string.c). */ #ifndef HAVE_STPCPY char *stpcpy (char *a, const char *b); #endif #ifndef HAVE_STRCASECMP int strcasecmp (const char *a, const char *b) _GCRY_GCC_ATTR_PURE; #endif #include "../compat/libcompat.h" /* Macros used to rename missing functions. */ #ifndef HAVE_STRTOUL #define strtoul(a,b,c) ((unsigned long)strtol((a),(b),(c))) #endif #ifndef HAVE_MEMMOVE #define memmove(d, s, n) bcopy((s), (d), (n)) #endif #ifndef HAVE_STRICMP #define stricmp(a,b) strcasecmp( (a), (b) ) #endif #ifndef HAVE_ATEXIT #define atexit(a) (on_exit((a),0)) #endif #ifndef HAVE_RAISE #define raise(a) kill(getpid(), (a)) #endif /* Stack burning. */ #ifdef HAVE_GCC_ASM_VOLATILE_MEMORY #define __gcry_burn_stack_dummy() asm volatile ("":::"memory") #else void __gcry_burn_stack_dummy (void); #endif void __gcry_burn_stack (unsigned int bytes); #define _gcry_burn_stack(bytes) \ do { __gcry_burn_stack (bytes); \ __gcry_burn_stack_dummy (); } while(0) /* To avoid that a compiler optimizes certain memset calls away, these macros may be used instead. */ #define wipememory2(_ptr,_set,_len) do { \ volatile char *_vptr=(volatile char *)(_ptr); \ size_t _vlen=(_len); \ unsigned char _vset=(_set); \ fast_wipememory2(_vptr,_vset,_vlen); \ while(_vlen) { *_vptr=(_vset); _vptr++; _vlen--; } \ } while(0) #define wipememory(_ptr,_len) wipememory2(_ptr,0,_len) #define FASTWIPE_T u64 #define FASTWIPE_MULT (U64_C(0x0101010101010101)) /* Following architectures can handle unaligned accesses fast. */ #if defined(HAVE_GCC_ATTRIBUTE_PACKED) && \ defined(HAVE_GCC_ATTRIBUTE_ALIGNED) && \ (defined(__i386__) || defined(__x86_64__) || \ defined(__powerpc__) || defined(__powerpc64__) || \ (defined(__arm__) && defined(__ARM_FEATURE_UNALIGNED)) || \ defined(__aarch64__)) #define fast_wipememory2_unaligned_head(_ptr,_set,_len) /*do nothing*/ typedef struct fast_wipememory_s { FASTWIPE_T a; } __attribute__((packed, aligned(1))) fast_wipememory_t; #else #define fast_wipememory2_unaligned_head(_vptr,_vset,_vlen) do { \ while((size_t)(_vptr)&(sizeof(FASTWIPE_T)-1) && _vlen) \ { *_vptr=(_vset); _vptr++; _vlen--; } \ } while(0) typedef struct fast_wipememory_s { FASTWIPE_T a; } fast_wipememory_t; #endif /* fast_wipememory2 may leave tail bytes unhandled, in which case tail bytes are handled by wipememory2. */ #define fast_wipememory2(_vptr,_vset,_vlen) do { \ FASTWIPE_T _vset_long = _vset; \ fast_wipememory2_unaligned_head(_vptr,_vset,_vlen); \ if (_vlen < sizeof(FASTWIPE_T)) \ break; \ _vset_long *= FASTWIPE_MULT; \ do { \ volatile fast_wipememory_t *_vptr_long = \ (volatile void *)_vptr; \ _vptr_long->a = _vset_long; \ _vlen -= sizeof(FASTWIPE_T); \ _vptr += sizeof(FASTWIPE_T); \ } while (_vlen >= sizeof(FASTWIPE_T)); \ } while (0) /* Digit predicates. */ #define digitp(p) (*(p) >= '0' && *(p) <= '9') #define octdigitp(p) (*(p) >= '0' && *(p) <= '7') #define alphap(a) ( (*(a) >= 'A' && *(a) <= 'Z') \ || (*(a) >= 'a' && *(a) <= 'z')) #define hexdigitp(a) (digitp (a) \ || (*(a) >= 'A' && *(a) <= 'F') \ || (*(a) >= 'a' && *(a) <= 'f')) /* Init functions. */ gcry_err_code_t _gcry_cipher_init (void); gcry_err_code_t _gcry_md_init (void); gcry_err_code_t _gcry_mac_init (void); gcry_err_code_t _gcry_pk_init (void); gcry_err_code_t _gcry_secmem_module_init (void); gcry_err_code_t _gcry_mpi_init (void); /* Memory management. */ #define GCRY_ALLOC_FLAG_SECURE (1 << 0) /*-- sexp.c --*/ gcry_err_code_t _gcry_sexp_vbuild (gcry_sexp_t *retsexp, size_t *erroff, const char *format, va_list arg_ptr); char *_gcry_sexp_nth_string (const gcry_sexp_t list, int number); gpg_err_code_t _gcry_sexp_vextract_param (gcry_sexp_t sexp, const char *path, const char *list, va_list arg_ptr); /*-- fips.c --*/ void _gcry_initialize_fips_mode (int force); int _gcry_fips_mode (void); #define fips_mode() _gcry_fips_mode () int _gcry_enforced_fips_mode (void); void _gcry_set_enforced_fips_mode (void); void _gcry_inactivate_fips_mode (const char *text); int _gcry_is_fips_mode_inactive (void); void _gcry_fips_signal_error (const char *srcfile, int srcline, const char *srcfunc, int is_fatal, const char *description); #ifdef JNLIB_GCC_M_FUNCTION # define fips_signal_error(a) \ _gcry_fips_signal_error (__FILE__, __LINE__, __FUNCTION__, 0, (a)) # define fips_signal_fatal_error(a) \ _gcry_fips_signal_error (__FILE__, __LINE__, __FUNCTION__, 1, (a)) #else # define fips_signal_error(a) \ _gcry_fips_signal_error (__FILE__, __LINE__, NULL, 0, (a)) # define fips_signal_fatal_error(a) \ _gcry_fips_signal_error (__FILE__, __LINE__, NULL, 1, (a)) #endif int _gcry_fips_is_operational (void); #define fips_is_operational() (_gcry_global_is_operational ()) #define fips_not_operational() (GPG_ERR_NOT_OPERATIONAL) int _gcry_fips_test_operational (void); int _gcry_fips_test_error_or_operational (void); gpg_err_code_t _gcry_fips_run_selftests (int extended); void _gcry_fips_noreturn (void); #define fips_noreturn() (_gcry_fips_noreturn ()) #endif /* G10LIB_H */ diff --git a/tests/keygen.c b/tests/keygen.c index dcb59e48..4bcea20d 100644 --- a/tests/keygen.c +++ b/tests/keygen.c @@ -1,753 +1,775 @@ /* keygen.c - key generation regression tests * Copyright (C) 2003, 2005, 2012 Free Software Foundation, Inc. * Copyright (C) 2013, 2015 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ #ifdef HAVE_CONFIG_H #include #endif #include #include #include #include #include "../src/gcrypt-int.h" #define PGM "keygen" #define xmalloc(a) gcry_xmalloc ((a)) #define xcalloc(a,b) gcry_xcalloc ((a),(b)) #define xstrdup(a) gcry_xstrdup ((a)) #define xfree(a) gcry_free ((a)) #define pass() do { ; } while (0) static int verbose; static int debug; static int error_count; static int in_fips_mode; static void die (const char *format, ...) { va_list arg_ptr ; fflush (stdout); fprintf (stderr, "%s: ", PGM); va_start( arg_ptr, format ) ; vfprintf (stderr, format, arg_ptr ); va_end(arg_ptr); if (*format && format[strlen(format)-1] != '\n') putc ('\n', stderr); exit (1); } static void fail (const char *format, ...) { va_list arg_ptr; fflush (stdout); fprintf (stderr, "%s: ", PGM); /* if (wherestr) */ /* fprintf (stderr, "%s: ", wherestr); */ va_start (arg_ptr, format); vfprintf (stderr, format, arg_ptr); va_end (arg_ptr); if (*format && format[strlen(format)-1] != '\n') putc ('\n', stderr); error_count++; if (error_count >= 50) die ("stopped after 50 errors."); } static void show (const char *format, ...) { va_list arg_ptr; fprintf (stderr, "%s: ", PGM); va_start (arg_ptr, format); vfprintf (stderr, format, arg_ptr); if (*format && format[strlen(format)-1] != '\n') putc ('\n', stderr); va_end (arg_ptr); } /* static void */ /* show_note (const char *format, ...) */ /* { */ /* va_list arg_ptr; */ /* if (!verbose && getenv ("srcdir")) */ /* fputs (" ", stderr); /\* To align above "PASS: ". *\/ */ /* else */ /* fprintf (stderr, "%s: ", PGM); */ /* va_start (arg_ptr, format); */ /* vfprintf (stderr, format, arg_ptr); */ /* if (*format && format[strlen(format)-1] != '\n') */ /* putc ('\n', stderr); */ /* va_end (arg_ptr); */ /* } */ static void show_sexp (const char *prefix, gcry_sexp_t a) { char *buf; size_t size; fprintf (stderr, "%s: ", PGM); if (prefix) fputs (prefix, stderr); size = gcry_sexp_sprint (a, GCRYSEXP_FMT_ADVANCED, NULL, 0); buf = xmalloc (size); gcry_sexp_sprint (a, GCRYSEXP_FMT_ADVANCED, buf, size); fprintf (stderr, "%.*s", (int)size, buf); gcry_free (buf); } static void show_mpi (const char *prefix, gcry_mpi_t a) { char *buf; void *bufaddr = &buf; gcry_error_t rc; fprintf (stderr, "%s: ", PGM); if (prefix) fputs (prefix, stderr); rc = gcry_mpi_aprint (GCRYMPI_FMT_HEX, bufaddr, NULL, a); if (rc) fprintf (stderr, "[error printing number: %s]\n", gpg_strerror (rc)); else { fprintf (stderr, "%s\n", buf); gcry_free (buf); } } static void check_generated_rsa_key (gcry_sexp_t key, unsigned long expected_e) { gcry_sexp_t skey, pkey, list; pkey = gcry_sexp_find_token (key, "public-key", 0); if (!pkey) fail ("public part missing in return value\n"); else { gcry_mpi_t e = NULL; list = gcry_sexp_find_token (pkey, "e", 0); if (!list || !(e=gcry_sexp_nth_mpi (list, 1, 0)) ) fail ("public exponent not found\n"); else if (!expected_e) { if (verbose) show_mpi ("public exponent: ", e); } else if ( gcry_mpi_cmp_ui (e, expected_e)) { show_mpi ("public exponent: ", e); fail ("public exponent is not %lu\n", expected_e); } gcry_sexp_release (list); gcry_mpi_release (e); gcry_sexp_release (pkey); } skey = gcry_sexp_find_token (key, "private-key", 0); if (!skey) fail ("private part missing in return value\n"); else { int rc = gcry_pk_testkey (skey); if (rc) fail ("gcry_pk_testkey failed: %s\n", gpg_strerror (rc)); gcry_sexp_release (skey); } } static void check_rsa_keys (void) { gcry_sexp_t keyparm, key; int rc; if (verbose) show ("creating 2048 bit RSA key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (rsa\n" " (nbits 4:2048)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating RSA key: %s\n", gpg_strerror (rc)); if (verbose) show ("creating 1024 bit RSA key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (rsa\n" " (nbits 4:1024)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc && !in_fips_mode) fail ("error generating RSA key: %s\n", gpg_strerror (rc)); else if (!rc && in_fips_mode) fail ("generating 1024 bit RSA key must not work!"); if (!rc) { if (verbose > 1) show_sexp ("1024 bit RSA key:\n", key); check_generated_rsa_key (key, 65537); } gcry_sexp_release (key); + if (verbose) + show ("creating 1024 bit RSA key with e=65539\n"); + rc = gcry_sexp_new (&keyparm, + "(genkey\n" + " (rsa\n" + " (nbits 4:1024)\n" + " (rsa-use-e 5:65539)\n" + " ))", 0, 1); + if (rc) + die ("error creating S-expression: %s\n", gpg_strerror (rc)); + rc = gcry_pk_genkey (&key, keyparm); + gcry_sexp_release (keyparm); + if (rc && !in_fips_mode) + fail ("error generating RSA key: %s\n", gpg_strerror (rc)); + else if (!rc && in_fips_mode) + fail ("generating RSA key must not work!"); + + if (!rc) + check_generated_rsa_key (key, 65539); + gcry_sexp_release (key); + + if (verbose) show ("creating 512 bit RSA key with e=257\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (rsa\n" " (nbits 3:512)\n" " (rsa-use-e 3:257)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc && !in_fips_mode) fail ("error generating RSA key: %s\n", gpg_strerror (rc)); else if (!rc && in_fips_mode) fail ("generating 512 bit RSA key must not work!"); if (!rc) check_generated_rsa_key (key, 257); gcry_sexp_release (key); if (verbose) show ("creating 512 bit RSA key with default e\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (rsa\n" " (nbits 3:512)\n" " (rsa-use-e 1:0)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc && !in_fips_mode) fail ("error generating RSA key: %s\n", gpg_strerror (rc)); else if (!rc && in_fips_mode) fail ("generating 512 bit RSA key must not work!"); if (!rc) check_generated_rsa_key (key, 0); /* We don't expect a constant exponent. */ gcry_sexp_release (key); } static void check_elg_keys (void) { gcry_sexp_t keyparm, key; int rc; if (verbose) show ("creating 1024 bit Elgamal key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (elg\n" " (nbits 4:1024)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating Elgamal key: %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("1024 bit Elgamal key:\n", key); gcry_sexp_release (key); } static void check_dsa_keys (void) { gcry_sexp_t keyparm, key; int rc; int i; /* Check that DSA generation works and that it can grok the qbits argument. */ if (verbose) show ("creating 5 1024 bit DSA keys\n"); for (i=0; i < 5; i++) { rc = gcry_sexp_new (&keyparm, "(genkey\n" " (dsa\n" " (nbits 4:1024)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc && !in_fips_mode) die ("error generating DSA key: %s\n", gpg_strerror (rc)); else if (!rc && in_fips_mode) die ("generating 1024 bit DSA key must not work!"); if (!i && verbose > 1) show_sexp ("1024 bit DSA key:\n", key); gcry_sexp_release (key); } if (verbose) show ("creating 1536 bit DSA key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (dsa\n" " (nbits 4:1536)\n" " (qbits 3:224)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc && !in_fips_mode) die ("error generating DSA key: %s\n", gpg_strerror (rc)); else if (!rc && in_fips_mode) die ("generating 1536 bit DSA key must not work!"); if (verbose > 1) show_sexp ("1536 bit DSA key:\n", key); gcry_sexp_release (key); if (verbose) show ("creating 3072 bit DSA key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (dsa\n" " (nbits 4:3072)\n" " (qbits 3:256)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating DSA key: %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("3072 bit DSA key:\n", key); gcry_sexp_release (key); if (verbose) show ("creating 2048/256 bit DSA key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (dsa\n" " (nbits 4:2048)\n" " (qbits 3:256)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating DSA key: %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("2048 bit DSA key:\n", key); gcry_sexp_release (key); if (verbose) show ("creating 2048/224 bit DSA key\n"); rc = gcry_sexp_new (&keyparm, "(genkey\n" " (dsa\n" " (nbits 4:2048)\n" " (qbits 3:224)\n" " ))", 0, 1); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating DSA key: %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("2048 bit DSA key:\n", key); gcry_sexp_release (key); } static void check_generated_ecc_key (gcry_sexp_t key) { gcry_sexp_t skey, pkey; pkey = gcry_sexp_find_token (key, "public-key", 0); if (!pkey) fail ("public part missing in return value\n"); else { /* Fixme: Check more stuff. */ gcry_sexp_release (pkey); } skey = gcry_sexp_find_token (key, "private-key", 0); if (!skey) fail ("private part missing in return value\n"); else { int rc = gcry_pk_testkey (skey); if (rc) fail ("gcry_pk_testkey failed: %s\n", gpg_strerror (rc)); gcry_sexp_release (skey); } /* Finally check that gcry_pk_testkey also works on the entire S-expression. */ { int rc = gcry_pk_testkey (key); if (rc) fail ("gcry_pk_testkey failed on key pair: %s\n", gpg_strerror (rc)); } } static void check_ecc_keys (void) { const char *curves[] = { "NIST P-521", "NIST P-384", "NIST P-256", "Ed25519", NULL }; int testno; gcry_sexp_t keyparm, key; int rc; for (testno=0; curves[testno]; testno++) { if (verbose) show ("creating ECC key using curve %s\n", curves[testno]); if (!strcmp (curves[testno], "Ed25519")) { /* Ed25519 isn't allowed in fips mode */ if (in_fips_mode) continue; rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve %s)(flags param eddsa)))", curves[testno]); } else rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve %s)(flags param)))", curves[testno]); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve %s: %s\n", curves[testno], gpg_strerror (rc)); if (verbose > 1) show_sexp ("ECC key:\n", key); check_generated_ecc_key (key); gcry_sexp_release (key); } if (verbose) show ("creating ECC key using curve Ed25519 for ECDSA\n"); rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve Ed25519)))"); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve Ed25519 for ECDSA: %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("ECC key:\n", key); check_generated_ecc_key (key); gcry_sexp_release (key); if (verbose) show ("creating ECC key using curve Ed25519 for ECDSA (nocomp)\n"); rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve Ed25519)(flags nocomp)))"); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve Ed25519 for ECDSA" " (nocomp): %s\n", gpg_strerror (rc)); if (verbose) show ("creating ECC key using curve NIST P-384 for ECDSA\n"); /* Must be specified as nistp384 (one word), because ecc_generate * uses _gcry_sexp_nth_string which takes the first word of the name * and thus libgcrypt can't find it later in its curves table. */ rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve nistp384)))"); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve NIST P-384 for ECDSA: %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("ECC key:\n", key); check_generated_ecc_key (key); gcry_sexp_release (key); if (verbose) show ("creating ECC key using curve NIST P-384 for ECDSA (nocomp)\n"); rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve nistp384)(flags nocomp)))"); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve NIST P-384 for ECDSA" " (nocomp): %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("ECC key:\n", key); check_generated_ecc_key (key); gcry_sexp_release (key); if (verbose) show ("creating ECC key using curve Ed25519 for ECDSA (transient-key)\n"); rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve Ed25519)(flags transient-key)))"); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve Ed25519 for ECDSA" " (transient-key): %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("ECC key:\n", key); check_generated_ecc_key (key); gcry_sexp_release (key); if (verbose) show ("creating ECC key using curve Ed25519 for ECDSA " "(transient-key no-keytest)\n"); rc = gcry_sexp_build (&keyparm, NULL, "(genkey(ecc(curve Ed25519)" "(flags transient-key no-keytest)))"); if (rc) die ("error creating S-expression: %s\n", gpg_strerror (rc)); rc = gcry_pk_genkey (&key, keyparm); gcry_sexp_release (keyparm); if (rc) die ("error generating ECC key using curve Ed25519 for ECDSA" " (transient-key no-keytest): %s\n", gpg_strerror (rc)); if (verbose > 1) show_sexp ("ECC key:\n", key); check_generated_ecc_key (key); gcry_sexp_release (key); } static void check_nonce (void) { char a[32], b[32]; int i,j; int oops=0; if (verbose) show ("checking gcry_create_nonce\n"); gcry_create_nonce (a, sizeof a); for (i=0; i < 10; i++) { gcry_create_nonce (b, sizeof b); if (!memcmp (a, b, sizeof a)) die ("identical nonce found\n"); } for (i=0; i < 10; i++) { gcry_create_nonce (a, sizeof a); if (!memcmp (a, b, sizeof a)) die ("identical nonce found\n"); } again: for (i=1,j=0; i < sizeof a; i++) if (a[0] == a[i]) j++; if (j+1 == sizeof (a)) { if (oops) die ("impossible nonce found\n"); oops++; gcry_create_nonce (a, sizeof a); goto again; } } static void progress_cb (void *cb_data, const char *what, int printchar, int current, int total) { (void)cb_data; (void)what; (void)current; (void)total; if (printchar == '\n') fputs ( "", stdout); else putchar (printchar); fflush (stdout); } static void usage (int mode) { fputs ("usage: " PGM " [options] [{rsa|elg|dsa|ecc|nonce}]\n" "Options:\n" " --verbose be verbose\n" " --debug flyswatter\n" " --progress print progress indicators\n", mode? stderr : stdout); if (mode) exit (1); } int main (int argc, char **argv) { int last_argc = -1; int with_progress = 0; if (argc) { argc--; argv++; } while (argc && last_argc != argc ) { last_argc = argc; if (!strcmp (*argv, "--")) { argc--; argv++; break; } else if (!strcmp (*argv, "--help")) { usage (0); exit (0); } else if (!strcmp (*argv, "--verbose")) { verbose++; argc--; argv++; } else if (!strcmp (*argv, "--debug")) { verbose += 2; debug++; argc--; argv++; } else if (!strcmp (*argv, "--progress")) { argc--; argv++; with_progress = 1; } else if (!strncmp (*argv, "--", 2)) die ("unknown option '%s'", *argv); else break; } if (!gcry_check_version (GCRYPT_VERSION)) die ("version mismatch\n"); gcry_control (GCRYCTL_DISABLE_SECMEM, 0); gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0); if (debug) gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u , 0); /* No valuable keys are create, so we can speed up our RNG. */ gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0); if (with_progress) gcry_set_progress_handler (progress_cb, NULL); if ( gcry_fips_mode_active () ) in_fips_mode = 1; if (!argc) { check_rsa_keys (); check_elg_keys (); check_dsa_keys (); check_ecc_keys (); check_nonce (); } else { for (; argc; argc--, argv++) if (!strcmp (*argv, "rsa")) check_rsa_keys (); else if (!strcmp (*argv, "elg")) check_elg_keys (); else if (!strcmp (*argv, "dsa")) check_dsa_keys (); else if (!strcmp (*argv, "ecc")) check_ecc_keys (); else if (!strcmp (*argv, "nonce")) check_nonce (); else usage (1); } return error_count? 1:0; }