2 This file is part of GNUnet.
3 Copyright (C) 1994, 1996, 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
4 Copyright (C) 2004, 2005, 2006 Christian Grothoff (and other contributing authors)
6 GNUnet is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published
8 by the Free Software Foundation; either version 2, or (at your
9 option) any later version.
11 GNUnet is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNUnet; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.
21 Note: This code is based on code from libgcrypt
22 The code was adapted for GNUnet to support RSA-key generation
23 based on weak, pseudo-random keys. Do NOT use to generate
29 * @file util/crypto_ksk.c
30 * @brief implementation of RSA-Key generation for KBlocks
31 * (do NOT use for pseudonyms or hostkeys!)
32 * @author Christian Grothoff
36 #include "gnunet_common.h"
37 #include "gnunet_crypto_lib.h"
38 #include "gnunet_os_lib.h"
42 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
45 * Log an error message at log-level 'level' that indicates
46 * a failure of the command 'cmd' with the message given
47 * by gcry_strerror(rc).
49 #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);
54 gcry_mpi_t n; /* public modulus */
55 gcry_mpi_t e; /* public exponent */
56 gcry_mpi_t d; /* exponent */
57 gcry_mpi_t p; /* prime p. */
58 gcry_mpi_t q; /* prime q. */
59 gcry_mpi_t u; /* inverse of p mod q. */
63 * The private information of an RSA key pair.
64 * NOTE: this must match the definition in crypto_rsa.c
66 struct GNUNET_CRYPTO_RsaPrivateKey
73 mpz_randomize (gcry_mpi_t n, unsigned int nbits, struct GNUNET_HashCode * rnd)
75 struct GNUNET_HashCode hc;
76 struct GNUNET_HashCode tmp;
77 int bits_per_hc = sizeof (struct GNUNET_HashCode) * 8;
81 GNUNET_assert (nbits > 0);
82 cnt = (nbits + bits_per_hc - 1) / bits_per_hc;
83 gcry_mpi_set_ui (n, 0);
86 for (i = 0; i < cnt; i++)
91 GNUNET_CRYPTO_hash (&hc, sizeof (struct GNUNET_HashCode), &tmp);
92 for (j = 0; j < sizeof (struct GNUNET_HashCode) / sizeof (uint32_t); j++)
94 #if HAVE_GCRY_MPI_LSHIFT
95 gcry_mpi_lshift (n, n, sizeof (uint32_t) * 8);
97 gcry_mpi_mul_ui (n, n, 1 << (sizeof (uint32_t) * 4));
98 gcry_mpi_mul_ui (n, n, 1 << (sizeof (uint32_t) * 4));
100 gcry_mpi_add_ui (n, n, ntohl (((uint32_t *) & tmp)[j]));
104 GNUNET_CRYPTO_hash (&hc, sizeof (struct GNUNET_HashCode), rnd);
105 i = gcry_mpi_get_nbits (n);
107 gcry_mpi_clear_bit (n, --i);
111 mpz_trailing_zeroes (gcry_mpi_t n)
113 unsigned int idx, cnt;
115 cnt = gcry_mpi_get_nbits (n);
116 for (idx = 0; idx < cnt; idx++)
118 if (gcry_mpi_test_bit (n, idx) == 0)
126 mpz_tdiv_q_2exp (gcry_mpi_t q, gcry_mpi_t n, unsigned int b)
130 u = gcry_mpi_set_ui (NULL, 1);
131 d = gcry_mpi_new (0);
132 gcry_mpi_mul_2exp (d, u, b);
133 gcry_mpi_div (q, NULL, n, d, 0);
137 * Return true if n is probably a prime
140 is_prime (gcry_mpi_t n, int steps, struct GNUNET_HashCode * hc)
148 unsigned int i, j, k;
152 x = gcry_mpi_new (0);
153 y = gcry_mpi_new (0);
154 z = gcry_mpi_new (0);
155 nminus1 = gcry_mpi_new (0);
156 a2 = gcry_mpi_set_ui (NULL, 2);
158 nbits = gcry_mpi_get_nbits (n);
159 gcry_mpi_sub_ui (nminus1, n, 1);
161 /* Find q and k, so that n = 1 + 2^k * q . */
162 q = gcry_mpi_set (NULL, nminus1);
163 k = mpz_trailing_zeroes (q);
164 mpz_tdiv_q_2exp (q, q, k);
166 for (i = 0; i < steps; i++)
170 gcry_mpi_set_ui (x, 2);
174 mpz_randomize (x, nbits - 1, hc);
175 GNUNET_assert (gcry_mpi_cmp (x, nminus1) < 0);
176 GNUNET_assert (gcry_mpi_cmp_ui (x, 1) > 0);
178 gcry_mpi_powm (y, x, q, n);
179 if (gcry_mpi_cmp_ui (y, 1) && gcry_mpi_cmp (y, nminus1))
181 for (j = 1; j < k && gcry_mpi_cmp (y, nminus1); j++)
183 gcry_mpi_powm (y, y, a2, n);
184 if (!gcry_mpi_cmp_ui (y, 1))
185 goto leave; /* Not a prime. */
187 if (gcry_mpi_cmp (y, nminus1))
188 goto leave; /* Not a prime. */
191 rc = 1; /* May be a prime. */
194 gcry_mpi_release (x);
195 gcry_mpi_release (y);
196 gcry_mpi_release (z);
197 gcry_mpi_release (nminus1);
198 gcry_mpi_release (q);
199 gcry_mpi_release (a2);
205 * If target != size, move target bytes to the
206 * end of the size-sized buffer and zero out the
207 * first target-size bytes.
210 adjust (unsigned char *buf, size_t size, size_t target)
214 memmove (&buf[target - size], buf, size);
215 memset (buf, 0, target - size);
221 gen_prime (gcry_mpi_t * ptest, unsigned int nbits, struct GNUNET_HashCode * hc)
223 /* Note: 2 is not included because it can be tested more easily by
224 * looking at bit 0. The last entry in this list is marked by a zero */
225 static const uint16_t small_prime_numbers[] = {
226 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
227 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
228 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
229 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
230 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
231 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
232 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
233 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
234 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
235 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
236 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
237 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
238 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
239 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
240 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
241 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
242 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
243 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
244 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
245 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
246 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
247 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
248 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
249 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
250 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
251 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
252 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
253 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
254 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
255 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
256 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
257 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
258 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
259 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
260 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
261 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
262 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
263 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
264 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
265 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
266 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
267 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
268 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
269 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
270 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
271 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
272 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
273 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
274 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
275 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
276 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
277 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
278 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
279 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
280 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
281 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
282 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
283 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
284 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
285 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
286 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
287 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
288 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
289 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
290 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
291 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
292 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
293 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
294 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
295 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
296 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
297 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
298 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
299 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
300 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
301 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
302 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
303 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
304 4957, 4967, 4969, 4973, 4987, 4993, 4999,
307 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
308 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
310 gcry_mpi_t prime, pminus1, val_2, val_3, result;
313 unsigned int mods[no_of_small_prime_numbers];
317 GNUNET_assert (nbits >= 16);
319 /* Make nbits fit into mpz_t implementation. */
320 val_2 = gcry_mpi_set_ui (NULL, 2);
321 val_3 = gcry_mpi_set_ui (NULL, 3);
322 prime = gcry_mpi_snew (0);
323 result = gcry_mpi_new (0);
324 pminus1 = gcry_mpi_new (0);
325 *ptest = gcry_mpi_new (0);
326 tmp = gcry_mpi_new (0);
327 sp = gcry_mpi_new (0);
330 /* generate a random number */
331 mpz_randomize (prime, nbits, hc);
332 /* Set high order bit to 1, set low order bit to 1. If we are
333 * generating a secret prime we are most probably doing that
334 * for RSA, to make sure that the modulus does have the
335 * requested key size we set the 2 high order bits. */
336 gcry_mpi_set_bit (prime, nbits - 1);
337 gcry_mpi_set_bit (prime, nbits - 2);
338 gcry_mpi_set_bit (prime, 0);
340 /* Calculate all remainders. */
341 for (i = 0; i < no_of_small_prime_numbers; i++)
345 gcry_mpi_set_ui (sp, small_prime_numbers[i]);
346 gcry_mpi_div (NULL, tmp, prime, sp, -1);
348 written = sizeof (unsigned int);
350 gcry_mpi_print (GCRYMPI_FMT_USG,
351 (unsigned char *) &mods[i], written,
353 adjust ((unsigned char *) &mods[i], written, sizeof (unsigned int));
354 mods[i] = ntohl (mods[i]);
356 /* Now try some primes starting with prime. */
357 for (step = 0; step < 20000; step += 2)
359 /* Check against all the small primes we have in mods. */
360 for (i = 0; i < no_of_small_prime_numbers; i++)
362 uint16_t x = small_prime_numbers[i];
364 while (mods[i] + step >= x)
366 if (!(mods[i] + step))
369 if (i < no_of_small_prime_numbers)
370 continue; /* Found a multiple of an already known prime. */
372 gcry_mpi_add_ui (*ptest, prime, step);
373 if (!gcry_mpi_test_bit (*ptest, nbits - 2))
376 /* Do a fast Fermat test now. */
377 gcry_mpi_sub_ui (pminus1, *ptest, 1);
378 gcry_mpi_powm (result, val_2, pminus1, *ptest);
379 if ((!gcry_mpi_cmp_ui (result, 1)) && (is_prime (*ptest, 5, hc)))
382 gcry_mpi_release (sp);
383 gcry_mpi_release (tmp);
384 gcry_mpi_release (val_2);
385 gcry_mpi_release (val_3);
386 gcry_mpi_release (result);
387 gcry_mpi_release (pminus1);
388 gcry_mpi_release (prime);
396 * Generate a key pair with a key of size NBITS.
397 * @param sk where to store the key
398 * @param nbits the number of bits to use
399 * @param hc the HC to use for PRNG (modified!)
402 generate_kblock_key (KBlock_secret_key *sk, unsigned int nbits,
403 struct GNUNET_HashCode * hc)
406 gcry_mpi_t phi; /* helper: (p-1)(q-1) */
410 /* make sure that nbits is even so that we generate p, q of equal size */
414 sk->e = gcry_mpi_set_ui (NULL, 257);
415 sk->n = gcry_mpi_new (0);
416 sk->p = gcry_mpi_new (0);
417 sk->q = gcry_mpi_new (0);
418 sk->d = gcry_mpi_new (0);
419 sk->u = gcry_mpi_new (0);
421 t1 = gcry_mpi_new (0);
422 t2 = gcry_mpi_new (0);
423 phi = gcry_mpi_new (0);
424 g = gcry_mpi_new (0);
425 f = gcry_mpi_new (0);
431 gcry_mpi_release (sk->p);
432 gcry_mpi_release (sk->q);
433 gen_prime (&sk->p, nbits / 2, hc);
434 gen_prime (&sk->q, nbits / 2, hc);
436 if (gcry_mpi_cmp (sk->p, sk->q) > 0) /* p shall be smaller than q (for calc of u) */
437 gcry_mpi_swap (sk->p, sk->q);
438 /* calculate the modulus */
439 gcry_mpi_mul (sk->n, sk->p, sk->q);
441 while (gcry_mpi_get_nbits (sk->n) != nbits);
443 /* calculate Euler totient: phi = (p-1)(q-1) */
444 gcry_mpi_sub_ui (t1, sk->p, 1);
445 gcry_mpi_sub_ui (t2, sk->q, 1);
446 gcry_mpi_mul (phi, t1, t2);
447 gcry_mpi_gcd (g, t1, t2);
448 gcry_mpi_div (f, NULL, phi, g, 0);
449 while (0 == gcry_mpi_gcd (t1, sk->e, phi))
450 { /* (while gcd is not 1) */
451 gcry_mpi_add_ui (sk->e, sk->e, 2);
454 /* calculate the secret key d = e^1 mod phi */
456 while ((0 == gcry_mpi_invm (sk->d, sk->e, f)) ||
457 (0 == gcry_mpi_invm (sk->u, sk->p, sk->q)));
459 gcry_mpi_release (t1);
460 gcry_mpi_release (t2);
461 gcry_mpi_release (phi);
462 gcry_mpi_release (f);
463 gcry_mpi_release (g);
466 GNUNET_NETWORK_STRUCT_BEGIN
469 * Internal representation of the private key.
471 struct KskRsaPrivateKeyBinaryEncoded
474 * Total size of the structure, in bytes, in big-endian!
476 uint16_t len GNUNET_PACKED;
477 uint16_t sizen GNUNET_PACKED; /* in big-endian! */
478 uint16_t sizee GNUNET_PACKED; /* in big-endian! */
479 uint16_t sized GNUNET_PACKED; /* in big-endian! */
480 uint16_t sizep GNUNET_PACKED; /* in big-endian! */
481 uint16_t sizeq GNUNET_PACKED; /* in big-endian! */
482 uint16_t sizedmp1 GNUNET_PACKED; /* in big-endian! */
483 uint16_t sizedmq1 GNUNET_PACKED; /* in big-endian! */
484 /* followed by the actual values */
486 GNUNET_NETWORK_STRUCT_END
489 * Deterministically (!) create a hostkey using only the
490 * given HashCode as input to the PRNG.
492 static struct KskRsaPrivateKeyBinaryEncoded *
493 makeKblockKeyInternal (const struct GNUNET_HashCode * hc)
495 KBlock_secret_key sk;
496 struct GNUNET_HashCode hx;
497 unsigned char *pbu[6];
500 struct KskRsaPrivateKeyBinaryEncoded *retval;
505 generate_kblock_key (&sk, 1024, /* at least 10x as fast than 2048 bits
506 * -- we simply cannot afford 2048 bits
507 * even on modern hardware, and especially
508 * not since clearly a dictionary attack
509 * will still be much cheaper
510 * than breaking a 1024 bit RSA key.
511 * If an adversary can spend the time to
512 * break a 1024 bit RSA key just to forge
513 * a signature -- SO BE IT. [ CG, 6/2005 ] */
521 size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
522 for (i = 0; i < 6; i++)
524 gcry_mpi_aprint (GCRYMPI_FMT_STD, &pbu[i], &sizes[i], *pkv[i]);
527 GNUNET_assert (size < 65536);
528 retval = GNUNET_malloc (size);
529 retval->len = htons (size);
531 retval->sizen = htons (sizes[0]);
532 memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
534 retval->sizee = htons (sizes[1]);
535 memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
537 retval->sized = htons (sizes[2]);
538 memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
541 retval->sizep = htons (sizes[4]);
542 memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
544 retval->sizeq = htons (sizes[3]);
545 memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
547 retval->sizedmp1 = htons (0);
548 retval->sizedmq1 = htons (0);
549 memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
550 for (i = 0; i < 6; i++)
552 gcry_mpi_release (*pkv[i]);
560 * Entry in the KSK cache.
562 struct KBlockKeyCacheLine
565 * Hash from which the key was generated.
567 struct GNUNET_HashCode hc;
572 struct KskRsaPrivateKeyBinaryEncoded *pke;
577 * Cached KSK keys so that we don't have to recompute them
580 static struct KBlockKeyCacheLine **cache;
584 * Size of the 'cache' array.
586 static unsigned int cacheSize;
590 * Deterministically (!) create a hostkey using only the
591 * given HashCode as input to the PRNG.
593 * @param hc hash code to generate the key from
594 * @return corresponding private key; must not be freed!
596 struct GNUNET_CRYPTO_RsaPrivateKey *
597 GNUNET_CRYPTO_rsa_key_create_from_hash (const struct GNUNET_HashCode * hc)
599 struct KBlockKeyCacheLine *line;
602 for (i = 0; i < cacheSize; i++)
603 if (0 == memcmp (hc, &cache[i]->hc, sizeof (struct GNUNET_HashCode)))
604 return GNUNET_CRYPTO_rsa_decode_key ((const char*) cache[i]->pke,
605 ntohs (cache[i]->pke->len));
606 line = GNUNET_malloc (sizeof (struct KBlockKeyCacheLine));
608 line->pke = makeKblockKeyInternal (hc);
609 GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
610 cache[cacheSize - 1] = line;
611 return GNUNET_CRYPTO_rsa_decode_key ((const char*) line->pke,
612 ntohs (line->pke->len));
617 * Destructor that frees the KSK cache.
619 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
623 for (i = 0; i < cacheSize; i++)
625 GNUNET_free (cache[i]->pke);
626 GNUNET_free (cache[i]);
628 GNUNET_array_grow (cache, cacheSize, 0);
632 /* end of crypto_ksk.c */