#include "gnunet_common.h"
#include "gnunet_crypto_lib.h"
#include "gnunet_os_lib.h"
-#include <gmp.h>
#include <gcrypt.h>
+#include <limits.h>
+
+#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
/**
* Log an error message at log-level 'level' that indicates
* a failure of the command 'cmd' with the message given
* by gcry_strerror(rc).
*/
-#define LOG_GCRY(level, cmd, rc) do { GNUNET_log(level, _("`%s' failed at %s:%d with error: %s\n"), cmd, __FILE__, __LINE__, gcry_strerror(rc)); } while(0);
+#define LOG_GCRY(level, cmd, rc) do { LOG(level, _("`%s' failed at %s:%d with error: %s\n"), cmd, __FILE__, __LINE__, gcry_strerror(rc)); } while(0);
typedef struct
{
- mpz_t n; /* public modulus */
- mpz_t e; /* public exponent */
- mpz_t d; /* exponent */
- mpz_t p; /* prime p. */
- mpz_t q; /* prime q. */
- mpz_t u; /* inverse of p mod q. */
+ 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. */
} KBlock_secret_key;
/**
};
-/* 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 uint16_t 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 void
+mpz_randomize (gcry_mpi_t n, unsigned int nbits, GNUNET_HashCode * rnd)
+{
+ GNUNET_HashCode hc;
+ GNUNET_HashCode tmp;
+ int bits_per_hc = sizeof (GNUNET_HashCode) * 8;
+ int cnt;
+ int i;
-#define DIM(v) (sizeof(v)/sizeof((v)[0]))
-static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
+ GNUNET_assert (nbits > 0);
+ cnt = (nbits + bits_per_hc - 1) / bits_per_hc;
+ gcry_mpi_set_ui (n, 0);
+ tmp = *rnd;
+ for (i = 0; i < cnt; i++)
+ {
+ int j;
- static unsigned int
- get_nbits (mpz_t a)
-{
- return mpz_sizeinbase (a, 2);
+ if (i > 0)
+ GNUNET_CRYPTO_hash (&hc, sizeof (GNUNET_HashCode), &tmp);
+ for (j = 0; j < sizeof (GNUNET_HashCode) / sizeof (uint32_t); j++)
+ {
+#if HAVE_GCRY_MPI_LSHIFT
+ gcry_mpi_lshift (n, n, sizeof (uint32_t) * 8);
+#else
+ gcry_mpi_mul_ui (n, n, 1 << (sizeof (uint32_t) * 4));
+ gcry_mpi_mul_ui (n, n, 1 << (sizeof (uint32_t) * 4));
+#endif
+ gcry_mpi_add_ui (n, n, ntohl (((uint32_t *) & tmp)[j]));
+ }
+ hc = tmp;
+ }
+ GNUNET_CRYPTO_hash (&hc, sizeof (GNUNET_HashCode), rnd);
+ i = gcry_mpi_get_nbits (n);
+ while (i > nbits)
+ gcry_mpi_clear_bit (n, --i);
}
-/**
- * Count the number of zerobits at the low end of A
- */
-static unsigned int
-get_trailing_zeros (mpz_t a)
+static unsigned long
+mpz_trailing_zeroes (gcry_mpi_t n)
{
- unsigned int count = 0;
- unsigned int nbits = get_nbits (a);
-
- while ((mpz_tstbit (a, count)) && (count < nbits))
- count++;
- return count;
-}
+ unsigned int idx, cnt;
-/**
- * Set bit N of A. and clear all bits above
- */
-static void
-set_highbit (mpz_t a, unsigned int n)
-{
- unsigned int nbits;
+ cnt = gcry_mpi_get_nbits (n);
+ for (idx = 0; idx < cnt; idx++)
+ {
+ if (gcry_mpi_test_bit (n, idx) == 0)
+ return idx;
+ }
- nbits = get_nbits (a);
- while (nbits > n)
- mpz_clrbit (a, nbits--);
- mpz_setbit (a, n);
+ return ULONG_MAX;
}
static void
-mpz_randomize (mpz_t n, unsigned int nbits, GNUNET_HashCode * rnd)
+mpz_tdiv_q_2exp (gcry_mpi_t q, gcry_mpi_t n, unsigned int b)
{
- GNUNET_HashCode *tmp;
- int cnt;
- int i;
+ gcry_mpi_t u, d;
- cnt = (nbits / sizeof (GNUNET_HashCode) / 8) + 1;
- tmp = GNUNET_malloc (sizeof (GNUNET_HashCode) * cnt);
-
- tmp[0] = *rnd;
- for (i = 0; i < cnt - 1; i++)
- {
- GNUNET_CRYPTO_hash (&tmp[i], sizeof (GNUNET_HashCode), &tmp[i + 1]);
- }
- *rnd = tmp[cnt - 1];
- mpz_import (n, cnt * sizeof (GNUNET_HashCode) / sizeof (unsigned int),
- 1, sizeof (unsigned int), 1, 0, tmp);
- GNUNET_free (tmp);
- i = get_nbits (n);
- while (i > nbits)
- mpz_clrbit (n, i--);
+ u = gcry_mpi_set_ui (NULL, 1);
+ d = gcry_mpi_new (0);
+ gcry_mpi_mul_2exp (d, u, b);
+ gcry_mpi_div (q, NULL, n, d, 0);
}
/**
* Return true if n is probably a prime
*/
static int
-is_prime (mpz_t n, int steps, GNUNET_HashCode * hc)
+is_prime (gcry_mpi_t n, int steps, GNUNET_HashCode * hc)
{
- mpz_t x;
- mpz_t y;
- mpz_t z;
- mpz_t nminus1;
- mpz_t a2;
- mpz_t q;
+ gcry_mpi_t x;
+ gcry_mpi_t y;
+ gcry_mpi_t z;
+ gcry_mpi_t nminus1;
+ gcry_mpi_t a2;
+ gcry_mpi_t q;
unsigned int i, j, k;
int rc = 0;
unsigned int nbits;
- mpz_init (x);
- mpz_init (y);
- mpz_init (z);
- mpz_init (nminus1);
- mpz_init_set_ui (a2, 2);
- nbits = get_nbits (n);
- mpz_sub_ui (nminus1, n, 1);
+ x = gcry_mpi_new (0);
+ y = gcry_mpi_new (0);
+ z = gcry_mpi_new (0);
+ nminus1 = gcry_mpi_new (0);
+ a2 = gcry_mpi_set_ui (NULL, 2);
+
+ nbits = gcry_mpi_get_nbits (n);
+ gcry_mpi_sub_ui (nminus1, n, 1);
/* Find q and k, so that n = 1 + 2^k * q . */
- mpz_init_set (q, nminus1);
- k = get_trailing_zeros (q);
+ q = gcry_mpi_set (NULL, nminus1);
+ k = mpz_trailing_zeroes (q);
mpz_tdiv_q_2exp (q, q, k);
for (i = 0; i < steps; i++)
+ {
+ if (!i)
+ {
+ gcry_mpi_set_ui (x, 2);
+ }
+ else
{
- if (!i)
- {
- mpz_set_ui (x, 2);
- }
- else
- {
- mpz_randomize (x, nbits, hc);
-
- /* Make sure that the number is smaller than the prime and
- keep the randomness of the high bit. */
- if (mpz_tstbit (x, nbits - 2))
- {
- set_highbit (x, nbits - 2); /* Clear all higher bits. */
- }
- else
- {
- set_highbit (x, nbits - 2);
- mpz_clrbit (x, nbits - 2);
- }
- GNUNET_assert (mpz_cmp (x, nminus1) < 0 && mpz_cmp_ui (x, 1) > 0);
- }
- mpz_powm (y, x, q, n);
- if (mpz_cmp_ui (y, 1) && mpz_cmp (y, nminus1))
- {
- for (j = 1; j < k && mpz_cmp (y, nminus1); j++)
- {
- mpz_powm (y, y, a2, n);
- if (!mpz_cmp_ui (y, 1))
- goto leave; /* Not a prime. */
- }
- if (mpz_cmp (y, nminus1))
- goto leave; /* Not a prime. */
- }
+ mpz_randomize (x, nbits - 1, hc);
+ GNUNET_assert (gcry_mpi_cmp (x, nminus1) < 0);
+ GNUNET_assert (gcry_mpi_cmp_ui (x, 1) > 0);
}
+ gcry_mpi_powm (y, x, q, n);
+ if (gcry_mpi_cmp_ui (y, 1) && gcry_mpi_cmp (y, nminus1))
+ {
+ for (j = 1; j < k && gcry_mpi_cmp (y, nminus1); j++)
+ {
+ gcry_mpi_powm (y, y, a2, n);
+ if (!gcry_mpi_cmp_ui (y, 1))
+ goto leave; /* Not a prime. */
+ }
+ if (gcry_mpi_cmp (y, nminus1))
+ goto leave; /* Not a prime. */
+ }
+ }
rc = 1; /* May be a prime. */
leave:
- mpz_clear (x);
- mpz_clear (y);
- mpz_clear (z);
- mpz_clear (nminus1);
- mpz_clear (q);
- mpz_clear (a2);
+ gcry_mpi_release (x);
+ gcry_mpi_release (y);
+ gcry_mpi_release (z);
+ gcry_mpi_release (nminus1);
+ gcry_mpi_release (q);
+ gcry_mpi_release (a2);
return rc;
}
+/**
+ * If target != size, move target bytes to the
+ * end of the size-sized buffer and zero out the
+ * first target-size bytes.
+ */
static void
-gen_prime (mpz_t ptest, unsigned int nbits, GNUNET_HashCode * hc)
+adjust (unsigned char *buf, size_t size, size_t target)
{
- mpz_t prime, pminus1, val_2, val_3, result;
- int i;
- unsigned x, step;
- int *mods;
- mpz_t tmp;
+ if (size < target)
+ {
+ memmove (&buf[target - size], buf, size);
+ memset (buf, 0, target - size);
+ }
+}
+
+
+static void
+gen_prime (gcry_mpi_t * ptest, unsigned int nbits, GNUNET_HashCode * hc)
+{
+ /* 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 const uint16_t 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
+ };
+#define DIM(v) (sizeof(v)/sizeof((v)[0]))
+ static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
+
+ gcry_mpi_t prime, pminus1, val_2, val_3, result;
+ unsigned int i;
+ unsigned int step;
+ unsigned int mods[no_of_small_prime_numbers];
+ gcry_mpi_t tmp;
+ gcry_mpi_t sp;
GNUNET_assert (nbits >= 16);
- mods = GNUNET_malloc (no_of_small_prime_numbers * sizeof (*mods));
/* Make nbits fit into mpz_t implementation. */
- mpz_init_set_ui (val_2, 2);
- mpz_init_set_ui (val_3, 3);
- mpz_init (prime);
- mpz_init (result);
- mpz_init (pminus1);
- mpz_init (ptest);
+ val_2 = gcry_mpi_set_ui (NULL, 2);
+ val_3 = gcry_mpi_set_ui (NULL, 3);
+ prime = gcry_mpi_snew (0);
+ result = gcry_mpi_new (0);
+ pminus1 = gcry_mpi_new (0);
+ *ptest = gcry_mpi_new (0);
+ tmp = gcry_mpi_new (0);
+ sp = gcry_mpi_new (0);
while (1)
+ {
+ /* generate a random number */
+ mpz_randomize (prime, nbits, hc);
+ /* 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. */
+ gcry_mpi_set_bit (prime, nbits - 1);
+ gcry_mpi_set_bit (prime, nbits - 2);
+ gcry_mpi_set_bit (prime, 0);
+
+ /* Calculate all remainders. */
+ for (i = 0; i < no_of_small_prime_numbers; i++)
{
- /* generate a random number */
- mpz_randomize (prime, nbits, hc);
- /* 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. */
- set_highbit (prime, nbits - 1);
- mpz_setbit (prime, nbits - 2);
- mpz_setbit (prime, 0);
-
- /* Calculate all remainders. */
- mpz_init (tmp);
- for (i = 0; (x = small_prime_numbers[i]); i++)
- mods[i] = mpz_fdiv_r_ui (tmp, prime, x);
- mpz_clear (tmp);
- /* Now try some primes starting with prime. */
- for (step = 0; step < 20000; step += 2)
- {
- /* Check against all the small primes we have in mods. */
- 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. */
-
- mpz_add_ui (ptest, prime, step);
- if (!mpz_tstbit (ptest, nbits - 2))
- break;
-
- /* Do a fast Fermat test now. */
- mpz_sub_ui (pminus1, ptest, 1);
- mpz_powm (result, val_2, pminus1, ptest);
- if ((!mpz_cmp_ui (result, 1)) && (is_prime (ptest, 5, hc)))
- {
- /* Got it. */
- mpz_clear (val_2);
- mpz_clear (val_3);
- mpz_clear (result);
- mpz_clear (pminus1);
- mpz_clear (prime);
- GNUNET_free (mods);
- return;
- }
- }
+ size_t written;
+
+ gcry_mpi_set_ui (sp, small_prime_numbers[i]);
+ gcry_mpi_div (NULL, tmp, prime, sp, -1);
+ mods[i] = 0;
+ written = sizeof (unsigned int);
+ GNUNET_assert (0 ==
+ gcry_mpi_print (GCRYMPI_FMT_USG,
+ (unsigned char *) &mods[i], written,
+ &written, tmp));
+ adjust ((unsigned char *) &mods[i], written, sizeof (unsigned int));
+ mods[i] = ntohl (mods[i]);
}
-}
-
-/**
- * Find the greatest common divisor G of A and B.
- * Return: 1 if this 1, 0 in all other cases
- */
-static int
-test_gcd (mpz_t g, mpz_t xa, mpz_t xb)
-{
- mpz_t a, b;
-
- mpz_init_set (a, xa);
- mpz_init_set (b, xb);
-
- /* TAOCP Vol II, 4.5.2, Algorithm A */
- while (mpz_cmp_ui (b, 0))
+ /* Now try some primes starting with prime. */
+ for (step = 0; step < 20000; step += 2)
{
- mpz_fdiv_r (g, a, b); /* g used as temorary variable */
- mpz_set (a, b);
- mpz_set (b, g);
+ /* Check against all the small primes we have in mods. */
+ for (i = 0; i < no_of_small_prime_numbers; i++)
+ {
+ uint16_t x = small_prime_numbers[i];
+
+ while (mods[i] + step >= x)
+ mods[i] -= x;
+ if (!(mods[i] + step))
+ break;
+ }
+ if (i < no_of_small_prime_numbers)
+ continue; /* Found a multiple of an already known prime. */
+
+ gcry_mpi_add_ui (*ptest, prime, step);
+ if (!gcry_mpi_test_bit (*ptest, nbits - 2))
+ break;
+
+ /* Do a fast Fermat test now. */
+ gcry_mpi_sub_ui (pminus1, *ptest, 1);
+ gcry_mpi_powm (result, val_2, pminus1, *ptest);
+ if ((!gcry_mpi_cmp_ui (result, 1)) && (is_prime (*ptest, 5, hc)))
+ {
+ /* Got it. */
+ gcry_mpi_release (sp);
+ gcry_mpi_release (tmp);
+ gcry_mpi_release (val_2);
+ gcry_mpi_release (val_3);
+ gcry_mpi_release (result);
+ gcry_mpi_release (pminus1);
+ gcry_mpi_release (prime);
+ return;
+ }
}
- mpz_set (g, a);
-
- mpz_clear (a);
- mpz_clear (b);
- return (0 == mpz_cmp_ui (g, 1));
+ }
}
/**
* @param hc the HC to use for PRNG (modified!)
*/
static void
-generate_kblock_key (KBlock_secret_key * sk,
- unsigned int nbits, GNUNET_HashCode * hc)
+generate_kblock_key (KBlock_secret_key *sk, unsigned int nbits,
+ GNUNET_HashCode * hc)
{
- mpz_t t1, t2;
- mpz_t phi; /* helper: (p-1)(q-1) */
- mpz_t g;
- mpz_t f;
+ gcry_mpi_t t1, t2;
+ gcry_mpi_t phi; /* helper: (p-1)(q-1) */
+ gcry_mpi_t g;
+ gcry_mpi_t f;
/* make sure that nbits is even so that we generate p, q of equal size */
if ((nbits & 1))
nbits++;
- mpz_init_set_ui (sk->e, 257);
- mpz_init (sk->n);
- mpz_init (sk->p);
- mpz_init (sk->q);
- mpz_init (sk->d);
- mpz_init (sk->u);
+ sk->e = gcry_mpi_set_ui (NULL, 257);
+ sk->n = gcry_mpi_new (0);
+ sk->p = gcry_mpi_new (0);
+ sk->q = gcry_mpi_new (0);
+ sk->d = gcry_mpi_new (0);
+ sk->u = gcry_mpi_new (0);
- mpz_init (t1);
- mpz_init (t2);
- mpz_init (phi);
- mpz_init (g);
- mpz_init (f);
+ t1 = gcry_mpi_new (0);
+ t2 = gcry_mpi_new (0);
+ phi = gcry_mpi_new (0);
+ g = gcry_mpi_new (0);
+ f = gcry_mpi_new (0);
do
+ {
+ do
{
- do
- {
- mpz_clear (sk->p);
- mpz_clear (sk->q);
- gen_prime (sk->p, nbits / 2, hc);
- gen_prime (sk->q, nbits / 2, hc);
-
- if (mpz_cmp (sk->p, sk->q) > 0) /* p shall be smaller than q (for calc of u) */
- mpz_swap (sk->p, sk->q);
- /* calculate the modulus */
- mpz_mul (sk->n, sk->p, sk->q);
- }
- while (get_nbits (sk->n) != nbits);
-
- /* calculate Euler totient: phi = (p-1)(q-1) */
- mpz_sub_ui (t1, sk->p, 1);
- mpz_sub_ui (t2, sk->q, 1);
- mpz_mul (phi, t1, t2);
- mpz_gcd (g, t1, t2);
- mpz_fdiv_q (f, phi, g);
-
- while (0 == test_gcd (t1, sk->e, phi))
- { /* (while gcd is not 1) */
- mpz_add_ui (sk->e, sk->e, 2);
- }
-
- /* calculate the secret key d = e^1 mod phi */
+ gcry_mpi_release (sk->p);
+ gcry_mpi_release (sk->q);
+ gen_prime (&sk->p, nbits / 2, hc);
+ gen_prime (&sk->q, nbits / 2, hc);
+
+ if (gcry_mpi_cmp (sk->p, sk->q) > 0) /* p shall be smaller than q (for calc of u) */
+ gcry_mpi_swap (sk->p, sk->q);
+ /* calculate the modulus */
+ gcry_mpi_mul (sk->n, sk->p, sk->q);
}
- while ((0 == mpz_invert (sk->d, sk->e, f)) ||
- (0 == mpz_invert (sk->u, sk->p, sk->q)));
-
- mpz_clear (t1);
- mpz_clear (t2);
- mpz_clear (phi);
- mpz_clear (f);
- mpz_clear (g);
+ while (gcry_mpi_get_nbits (sk->n) != nbits);
+
+ /* calculate Euler totient: phi = (p-1)(q-1) */
+ gcry_mpi_sub_ui (t1, sk->p, 1);
+ gcry_mpi_sub_ui (t2, sk->q, 1);
+ gcry_mpi_mul (phi, t1, t2);
+ gcry_mpi_gcd (g, t1, t2);
+ gcry_mpi_div (f, NULL, phi, g, 0);
+ while (0 == gcry_mpi_gcd (t1, sk->e, phi))
+ { /* (while gcd is not 1) */
+ gcry_mpi_add_ui (sk->e, sk->e, 2);
+ }
+
+ /* calculate the secret key d = e^1 mod phi */
+ }
+ while ((0 == gcry_mpi_invm (sk->d, sk->e, f)) ||
+ (0 == gcry_mpi_invm (sk->u, sk->p, sk->q)));
+
+ gcry_mpi_release (t1);
+ gcry_mpi_release (t2);
+ gcry_mpi_release (phi);
+ gcry_mpi_release (f);
+ gcry_mpi_release (g);
}
+GNUNET_NETWORK_STRUCT_BEGIN
/**
* Internal representation of the private key.
uint16_t sizedmq1 GNUNET_PACKED; /* in big-endian! */
/* followed by the actual values */
};
-
+GNUNET_NETWORK_STRUCT_END
/**
* Deterministically (!) create a hostkey using only the
{
KBlock_secret_key sk;
GNUNET_HashCode hx;
- void *pbu[6];
- mpz_t *pkv[6];
+ unsigned char *pbu[6];
+ gcry_mpi_t *pkv[6];
size_t sizes[6];
struct KskRsaPrivateKeyBinaryEncoded *retval;
int i;
hx = *hc;
generate_kblock_key (&sk, 1024, /* at least 10x as fast than 2048 bits
- -- we simply cannot afford 2048 bits
- even on modern hardware, and especially
- not since clearly a dictionary attack
- will still be much cheaper
- than breaking a 1024 bit RSA key.
- If an adversary can spend the time to
- break a 1024 bit RSA key just to forge
- a signature -- SO BE IT. [ CG, 6/2005 ] */
+ * -- we simply cannot afford 2048 bits
+ * even on modern hardware, and especially
+ * not since clearly a dictionary attack
+ * will still be much cheaper
+ * than breaking a 1024 bit RSA key.
+ * If an adversary can spend the time to
+ * break a 1024 bit RSA key just to forge
+ * a signature -- SO BE IT. [ CG, 6/2005 ] */
&hx);
pkv[0] = &sk.n;
pkv[1] = &sk.e;
pkv[5] = &sk.u;
size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
for (i = 0; i < 6; i++)
- {
- pbu[i] = mpz_export (NULL, &sizes[i], 1, /* most significant word first */
- 1, /* unit is bytes */
- 1, /* big endian */
- 0, /* nails */
- *pkv[i]);
- size += sizes[i];
- }
+ {
+ gcry_mpi_aprint (GCRYMPI_FMT_STD, &pbu[i], &sizes[i], *pkv[i]);
+ size += sizes[i];
+ }
GNUNET_assert (size < 65536);
retval = GNUNET_malloc (size);
retval->len = htons (size);
retval->sizedmq1 = htons (0);
memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
for (i = 0; i < 6; i++)
- {
- mpz_clear (*pkv[i]);
- free (pbu[i]);
- }
+ {
+ gcry_mpi_release (*pkv[i]);
+ free (pbu[i]);
+ }
return retval;
}
/**
- * Decode the internal format into the format used
- * by libgcrypt.
+ * Entry in the KSK cache.
*/
-static struct GNUNET_CRYPTO_RsaPrivateKey *
-ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
+struct KBlockKeyCacheLine
{
- struct GNUNET_CRYPTO_RsaPrivateKey *ret;
- gcry_sexp_t res;
- gcry_mpi_t n, e, d, p, q, u;
- int rc;
- size_t size;
- int pos;
-
- pos = 0;
- size = ntohs (encoding->sizen);
- rc = gcry_mpi_scan (&n,
- GCRYMPI_FMT_USG,
- &((const unsigned char *) (&encoding[1]))[pos],
- size, &size);
- pos += ntohs (encoding->sizen);
- if (rc)
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
- return NULL;
- }
- size = ntohs (encoding->sizee);
- rc = gcry_mpi_scan (&e,
- GCRYMPI_FMT_USG,
- &((const unsigned char *) (&encoding[1]))[pos],
- size, &size);
- pos += ntohs (encoding->sizee);
- if (rc)
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
- gcry_mpi_release (n);
- return NULL;
- }
- size = ntohs (encoding->sized);
- rc = gcry_mpi_scan (&d,
- GCRYMPI_FMT_USG,
- &((const unsigned char *) (&encoding[1]))[pos],
- size, &size);
- pos += ntohs (encoding->sized);
- if (rc)
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
- gcry_mpi_release (n);
- gcry_mpi_release (e);
- return NULL;
- }
- /* swap p and q! */
- size = ntohs (encoding->sizep);
- if (size > 0)
- {
- rc = gcry_mpi_scan (&q,
- GCRYMPI_FMT_USG,
- &((const unsigned char *) (&encoding[1]))[pos],
- size, &size);
- pos += ntohs (encoding->sizep);
- if (rc)
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
- gcry_mpi_release (n);
- gcry_mpi_release (e);
- gcry_mpi_release (d);
- return NULL;
- }
- }
- else
- q = NULL;
- size = ntohs (encoding->sizeq);
- if (size > 0)
- {
- rc = gcry_mpi_scan (&p,
- GCRYMPI_FMT_USG,
- &((const unsigned char *) (&encoding[1]))[pos],
- size, &size);
- pos += ntohs (encoding->sizeq);
- if (rc)
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
- gcry_mpi_release (n);
- gcry_mpi_release (e);
- gcry_mpi_release (d);
- if (q != NULL)
- gcry_mpi_release (q);
- return NULL;
- }
- }
- else
- p = NULL;
- pos += ntohs (encoding->sizedmp1);
- pos += ntohs (encoding->sizedmq1);
- size =
- ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
- pos;
- if (size > 0)
- {
- rc = gcry_mpi_scan (&u,
- GCRYMPI_FMT_USG,
- &((const unsigned char *) (&encoding[1]))[pos],
- size, &size);
- if (rc)
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
- gcry_mpi_release (n);
- gcry_mpi_release (e);
- gcry_mpi_release (d);
- if (p != NULL)
- gcry_mpi_release (p);
- if (q != NULL)
- gcry_mpi_release (q);
- return NULL;
- }
- }
- else
- u = NULL;
-
- if ((p != NULL) && (q != NULL) && (u != NULL))
- {
- rc = gcry_sexp_build (&res, &size, /* erroff */
- "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
- n, e, d, p, q, u);
- }
- else
- {
- if ((p != NULL) && (q != NULL))
- {
- rc = gcry_sexp_build (&res, &size, /* erroff */
- "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
- n, e, d, p, q);
- }
- else
- {
- rc = gcry_sexp_build (&res, &size, /* erroff */
- "(private-key(rsa(n %m)(e %m)(d %m)))",
- n, e, d);
- }
- }
- gcry_mpi_release (n);
- gcry_mpi_release (e);
- gcry_mpi_release (d);
- if (p != NULL)
- gcry_mpi_release (p);
- if (q != NULL)
- gcry_mpi_release (q);
- if (u != NULL)
- gcry_mpi_release (u);
-
- if (rc)
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
-#if EXTRA_CHECKS
- if (gcry_pk_testkey (res))
- {
- LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
- return NULL;
- }
-#endif
- ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
- ret->sexp = res;
- return ret;
-}
+ /**
+ * Hash from which the key was generated.
+ */
+ GNUNET_HashCode hc;
+ /**
+ * The encoded key.
+ */
+ struct KskRsaPrivateKeyBinaryEncoded *pke;
+};
+/**
+ * Cached KSK keys so that we don't have to recompute them
+ * all the time.
+ */
+static struct KBlockKeyCacheLine **cache;
-typedef struct
-{
- GNUNET_HashCode hc;
- struct KskRsaPrivateKeyBinaryEncoded *pke;
-} KBlockKeyCacheLine;
-static KBlockKeyCacheLine **cache;
+/**
+ * Size of the 'cache' array.
+ */
static unsigned int cacheSize;
+
/**
* Deterministically (!) create a hostkey using only the
* given HashCode as input to the PRNG.
+ *
+ * @param hc hash code to generate the key from
+ * @return corresponding private key; must not be freed!
*/
struct GNUNET_CRYPTO_RsaPrivateKey *
GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
{
- struct GNUNET_CRYPTO_RsaPrivateKey *ret;
- KBlockKeyCacheLine *line;
- int i;
-
- for (i = 0; i < cacheSize; i++)
- {
- if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
- {
- ret = ksk_decode_key (cache[i]->pke);
- return ret;
- }
- }
-
- line = GNUNET_malloc (sizeof (KBlockKeyCacheLine));
+ struct KBlockKeyCacheLine *line;
+ unsigned int i;
+
+ for (i = 0; i < cacheSize; i++)
+ if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
+ return GNUNET_CRYPTO_rsa_decode_key ((const char*) cache[i]->pke,
+ ntohs (cache[i]->pke->len));
+ line = GNUNET_malloc (sizeof (struct KBlockKeyCacheLine));
line->hc = *hc;
line->pke = makeKblockKeyInternal (hc);
GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
cache[cacheSize - 1] = line;
- return ksk_decode_key (line->pke);
+ return GNUNET_CRYPTO_rsa_decode_key ((const char*) line->pke,
+ ntohs (line->pke->len));
}
-/* Used to register a progress callback. This needs to be called
- before any threads are created. */
-void
-_gcry_register_random_progress (void (*cb)(void *,const char*,int,int,int),
- void *cb_data );
-
-
/**
- * Function called by libgcrypt whenever we are
- * blocked gathering entropy.
+ * Destructor that frees the KSK cache.
*/
-static void
-entropy_generator (void *cls,
- const char *what,
- int printchar,
- int current,
- int total)
-{
- static pid_t genproc;
- if (0 != strcmp (what, "need_entropy"))
- return;
- if (current == total)
- {
- if (genproc != 0)
- {
- PLIBC_KILL(genproc, SIGKILL);
- GNUNET_break (GNUNET_OK == GNUNET_OS_process_wait (genproc));
- genproc = 0;
- }
- return;
- }
- genproc = GNUNET_OS_start_process ("find",
- "find",
- "-type",
- "s",
- "-fprint",
- "/dev/null",
- NULL);
-
-
-}
-
-
-void __attribute__ ((constructor)) GNUNET_CRYPTO_ksk_init ()
-{
- gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
- if (!gcry_check_version (GCRYPT_VERSION))
- {
- fprintf (stderr,
- _
- ("libgcrypt has not the expected version (version %s is required).\n"),
- GCRYPT_VERSION);
- abort ();
- }
-#ifdef gcry_fast_random_poll
- gcry_fast_random_poll ();
-#endif
- _gcry_register_random_progress (&entropy_generator, NULL);
-}
-
void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
{
- int i;
+ unsigned int i;
for (i = 0; i < cacheSize; i++)
- {
- GNUNET_free (cache[i]->pke);
- GNUNET_free (cache[i]);
- }
+ {
+ GNUNET_free (cache[i]->pke);
+ GNUNET_free (cache[i]);
+ }
GNUNET_array_grow (cache, cacheSize, 0);
- _gcry_register_random_progress (NULL, NULL);
}
-/* end of kblockkey.c */
+
+/* end of crypto_ksk.c */
projects / oweals / gnunet.git / blobdiff