src/util/crypto_ksk.c

   1 /*
   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)
   5
   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.
  10
  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.
  15
  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.
  20
  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
  24      ordinary RSA keys!
  25 */
  26
  27
  28 /**
  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
  33  */
  34
  35 #include "platform.h"
  36 #include "gnunet_common.h"
  37 #include "gnunet_crypto_lib.h"
  38 #include "gnunet_os_lib.h"
  39 #include <gcrypt.h>
  40 #include <limits.h>
  41
  42 /**
  43  * Log an error message at log-level 'level' that indicates
  44  * a failure of the command 'cmd' with the message given
  45  * by gcry_strerror(rc).
  46  */
  47 #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);
  48
  49
  50 typedef struct
  51 {
  52   gcry_mpi_t n;                      /* public modulus */
  53   gcry_mpi_t e;                      /* public exponent */
  54   gcry_mpi_t d;                      /* exponent */
  55   gcry_mpi_t p;                      /* prime  p. */
  56   gcry_mpi_t q;                      /* prime  q. */
  57   gcry_mpi_t u;                      /* inverse of p mod q. */
  58 } KBlock_secret_key;
  59
  60 /**
  61  * The private information of an RSA key pair.
  62  * NOTE: this must match the definition in crypto_rsa.c
  63  */
  64 struct GNUNET_CRYPTO_RsaPrivateKey
  65 {
  66   gcry_sexp_t sexp;
  67 };
  68
  69
  70 static void
  71 mpz_randomize (gcry_mpi_t n, unsigned int nbits, GNUNET_HashCode * rnd)
  72 {
  73   GNUNET_HashCode hc;
  74   GNUNET_HashCode tmp;
  75   int bits_per_hc = sizeof (GNUNET_HashCode) * 8;
  76   int cnt;
  77   int i;
  78
  79   GNUNET_assert (nbits > 0);
  80   cnt = (nbits + bits_per_hc - 1) / bits_per_hc;
  81   gcry_mpi_set_ui (n, 0);
  82
  83   tmp = *rnd;
  84   for (i = 0; i < cnt; i++)
  85     {
  86       int j;
  87
  88       if (i > 0)
  89         GNUNET_CRYPTO_hash (&hc, sizeof (GNUNET_HashCode), &tmp);
  90       fprintf (stderr, "H: %s\n", GNUNET_h2s (&tmp));
  91
  92       for (j=0;j<sizeof(GNUNET_HashCode) / sizeof(uint32_t); j++)
  93         {
  94 #if HAVE_GCRY_MPI_LSHIFT
  95           gcry_mpi_lshift (n, n, sizeof(uint32_t)*8);
  96 #else
  97           gcry_mpi_mul_ui(n, n, 1 << (sizeof(uint32_t)*4));
  98           gcry_mpi_mul_ui(n, n, 1 << (sizeof(uint32_t)*4));
  99 #endif
 100           gcry_mpi_add_ui(n, n, ntohl (((uint32_t *) &tmp)[j]));
 101         }
 102       hc = tmp;
 103     }
 104   GNUNET_CRYPTO_hash (&hc, sizeof (GNUNET_HashCode), rnd);
 105   i = gcry_mpi_get_nbits (n);
 106   while (i > nbits)
 107     gcry_mpi_clear_bit (n, --i);
 108 }
 109
 110 static unsigned long
 111 mpz_trailing_zeroes (gcry_mpi_t n)
 112 {
 113   unsigned int idx, cnt;
 114
 115   cnt = gcry_mpi_get_nbits(n);
 116   for (idx = 0; idx < cnt; idx++)
 117     {
 118       if (gcry_mpi_test_bit(n, idx) == 0)
 119         return idx;
 120     }
 121
 122   return ULONG_MAX;
 123 }
 124
 125 static void
 126 mpz_tdiv_q_2exp (gcry_mpi_t q, gcry_mpi_t n, unsigned int b)
 127 {
 128   gcry_mpi_t u, d;
 129
 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);
 134 }
 135
 136 /**
 137  * Return true if n is probably a prime
 138  */
 139 static int
 140 is_prime (gcry_mpi_t n, int steps, GNUNET_HashCode * hc)
 141 {
 142   gcry_mpi_t x;
 143   gcry_mpi_t y;
 144   gcry_mpi_t z;
 145   gcry_mpi_t nminus1;
 146   gcry_mpi_t a2;
 147   gcry_mpi_t q;
 148   unsigned int i, j, k;
 149   int rc = 0;
 150   unsigned int nbits;
 151
 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);
 157
 158   nbits = gcry_mpi_get_nbits (n);
 159   gcry_mpi_sub_ui(nminus1, n, 1);
 160
 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);
 165
 166   for (i = 0; i < steps; i++)
 167     {
 168       if (!i)
 169         {
 170           gcry_mpi_set_ui (x, 2);
 171         }
 172       else
 173         {
 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);
 177         }
 178       gcry_mpi_powm (y, x, q, n);
 179       if (gcry_mpi_cmp_ui (y, 1) && gcry_mpi_cmp (y, nminus1))
 180         {
 181           for (j = 1; j < k && gcry_mpi_cmp (y, nminus1); j++)
 182             {
 183             gcry_mpi_powm (y, y, a2, n);
 184               if (!gcry_mpi_cmp_ui (y, 1))
 185                 goto leave;     /* Not a prime. */
 186             }
 187           if (gcry_mpi_cmp (y, nminus1))
 188             goto leave;         /* Not a prime. */
 189         }
 190     }
 191   rc = 1;                       /* May be a prime. */
 192
 193 leave:
 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);
 200
 201   return rc;
 202 }
 203
 204 static void
 205 gen_prime (gcry_mpi_t *ptest, unsigned int nbits, GNUNET_HashCode * hc)
 206 {
 207   /* Note: 2 is not included because it can be tested more easily by
 208      looking at bit 0. The last entry in this list is marked by a zero */
 209   static const uint16_t small_prime_numbers[] = {
 210     3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
 211     47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
 212     103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
 213     157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
 214     211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
 215     269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
 216     331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
 217     389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
 218     449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
 219     509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
 220     587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
 221     643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
 222     709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
 223     773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
 224     853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
 225     919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
 226     991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
 227     1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
 228     1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
 229     1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
 230     1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
 231     1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
 232     1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
 233     1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
 234     1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
 235     1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
 236     1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
 237     1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
 238     1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
 239     1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
 240     1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
 241     1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
 242     1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
 243     1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
 244     2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
 245     2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
 246     2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
 247     2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
 248     2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
 249     2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
 250     2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
 251     2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
 252     2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
 253     2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
 254     2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
 255     2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
 256     2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
 257     2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
 258     2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
 259     3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
 260     3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
 261     3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
 262     3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
 263     3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
 264     3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
 265     3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
 266     3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
 267     3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
 268     3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
 269     3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
 270     3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
 271     3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
 272     3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
 273     3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
 274     4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
 275     4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
 276     4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
 277     4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
 278     4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
 279     4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
 280     4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
 281     4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
 282     4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
 283     4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
 284     4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
 285     4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
 286     4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
 287     4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
 288     4957, 4967, 4969, 4973, 4987, 4993, 4999,
 289     0
 290   };
 291 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
 292   static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
 293
 294   gcry_mpi_t prime, pminus1, val_2, val_3, result;
 295   unsigned int i;
 296   unsigned int step;
 297   unsigned int mods[no_of_small_prime_numbers];
 298   gcry_mpi_t tmp;
 299   gcry_mpi_t sp;
 300
 301   GNUNET_assert (nbits >= 16);
 302
 303   /* Make nbits fit into mpz_t implementation. */
 304   val_2 = gcry_mpi_set_ui (NULL, 2);
 305   val_3 = gcry_mpi_set_ui (NULL, 3);
 306   prime = gcry_mpi_snew(0);
 307   result = gcry_mpi_new(0);
 308   pminus1 = gcry_mpi_new(0);
 309   *ptest = gcry_mpi_new(0);
 310   tmp = gcry_mpi_new (0);
 311   sp = gcry_mpi_new (0);
 312   while (1)
 313     {
 314       /* generate a random number */
 315       mpz_randomize (prime, nbits, hc);
 316       /* Set high order bit to 1, set low order bit to 1.  If we are
 317          generating a secret prime we are most probably doing that
 318          for RSA, to make sure that the modulus does have the
 319          requested key size we set the 2 high order bits. */
 320       gcry_mpi_set_bit (prime, nbits - 1);
 321       gcry_mpi_set_bit (prime, nbits - 2);
 322       gcry_mpi_set_bit (prime, 0);
 323
 324       /* Calculate all remainders. */
 325       for (i = 0; i < no_of_small_prime_numbers; i++)
 326         {
 327           size_t written;
 328
 329           gcry_mpi_set_ui(sp, small_prime_numbers[i]);
 330           gcry_mpi_div (NULL, tmp, prime, sp, -1);
 331           mods[i] = 0;
 332           written = sizeof (unsigned int);
 333           GNUNET_assert (0 ==
 334                          gcry_mpi_print (GCRYMPI_FMT_USG,
 335                                          (unsigned char*) &mods[i], written, &written,
 336                                          tmp));
 337         }
 338       /* Now try some primes starting with prime. */
 339       for (step = 0; step < 20000; step += 2)
 340         {
 341           /* Check against all the small primes we have in mods. */
 342           for (i = 0; i < no_of_small_prime_numbers; i++)
 343             {
 344               uint16_t x = small_prime_numbers[i];
 345               while (mods[i] + step >= x)
 346                 mods[i] -= x;
 347               if (!(mods[i] + step))
 348                 break;
 349             }
 350           if (i < no_of_small_prime_numbers)
 351             continue;           /* Found a multiple of an already known prime. */
 352
 353           gcry_mpi_add_ui (*ptest, prime, step);
 354           if (!gcry_mpi_test_bit (*ptest, nbits - 2))
 355             break;
 356
 357           /* Do a fast Fermat test now. */
 358           gcry_mpi_sub_ui (pminus1, *ptest, 1);
 359           gcry_mpi_powm (result, val_2, pminus1, *ptest);
 360           if ((!gcry_mpi_cmp_ui (result, 1)) && (is_prime (*ptest, 5, hc)))
 361             {
 362               /* Got it. */
 363               gcry_mpi_release (sp);
 364               gcry_mpi_release (tmp);
 365               gcry_mpi_release (val_2);
 366               gcry_mpi_release (val_3);
 367               gcry_mpi_release (result);
 368               gcry_mpi_release (pminus1);
 369               gcry_mpi_release (prime);
 370               return;
 371             }
 372         }
 373     }
 374 }
 375
 376 /**
 377  * Generate a key pair with a key of size NBITS.
 378  * @param sk where to store the key
 379  * @param nbits the number of bits to use
 380  * @param hc the HC to use for PRNG (modified!)
 381  */
 382 static void
 383 generate_kblock_key (KBlock_secret_key * sk,
 384                      unsigned int nbits, GNUNET_HashCode * hc)
 385 {
 386   gcry_mpi_t t1, t2;
 387   gcry_mpi_t phi;                    /* helper: (p-1)(q-1) */
 388   gcry_mpi_t g;
 389   gcry_mpi_t f;
 390
 391   /* make sure that nbits is even so that we generate p, q of equal size */
 392   if ((nbits & 1))
 393     nbits++;
 394
 395   sk->e = gcry_mpi_set_ui (NULL, 257);
 396   sk->n = gcry_mpi_new(0);
 397   sk->p = gcry_mpi_new(0);
 398   sk->q = gcry_mpi_new(0);
 399   sk->d = gcry_mpi_new(0);
 400   sk->u = gcry_mpi_new(0);
 401
 402   t1 = gcry_mpi_new(0);
 403   t2 = gcry_mpi_new(0);
 404   phi = gcry_mpi_new(0);
 405   g = gcry_mpi_new(0);
 406   f = gcry_mpi_new(0);
 407
 408   do
 409     {
 410       do
 411         {
 412           gcry_mpi_release (sk->p);
 413           gcry_mpi_release (sk->q);
 414           gen_prime (&sk->p, nbits / 2, hc);
 415           gen_prime (&sk->q, nbits / 2, hc);
 416
 417           if (gcry_mpi_cmp (sk->p, sk->q) > 0)       /* p shall be smaller than q (for calc of u) */
 418             gcry_mpi_swap (sk->p, sk->q);
 419           /* calculate the modulus */
 420           gcry_mpi_mul (sk->n, sk->p, sk->q);
 421         }
 422       while (gcry_mpi_get_nbits (sk->n) != nbits);
 423
 424       /* calculate Euler totient: phi = (p-1)(q-1) */
 425       gcry_mpi_sub_ui (t1, sk->p, 1);
 426       gcry_mpi_sub_ui (t2, sk->q, 1);
 427       gcry_mpi_mul (phi, t1, t2);
 428       gcry_mpi_gcd (g, t1, t2);
 429       gcry_mpi_div (f, NULL, phi, g, 0);
 430       while (0 == gcry_mpi_gcd (t1, sk->e, phi))
 431         {                       /* (while gcd is not 1) */
 432           gcry_mpi_add_ui (sk->e, sk->e, 2);
 433         }
 434
 435       /* calculate the secret key d = e^1 mod phi */
 436     }
 437   while ((0 == gcry_mpi_invm (sk->d, sk->e, f)) ||
 438          (0 == gcry_mpi_invm (sk->u, sk->p, sk->q)));
 439
 440   gcry_mpi_release (t1);
 441   gcry_mpi_release (t2);
 442   gcry_mpi_release (phi);
 443   gcry_mpi_release (f);
 444   gcry_mpi_release (g);
 445 }
 446
 447
 448 /**
 449  * Internal representation of the private key.
 450  */
 451 struct KskRsaPrivateKeyBinaryEncoded
 452 {
 453   /**
 454    * Total size of the structure, in bytes, in big-endian!
 455    */
 456   uint16_t len GNUNET_PACKED;
 457   uint16_t sizen GNUNET_PACKED; /*  in big-endian! */
 458   uint16_t sizee GNUNET_PACKED; /*  in big-endian! */
 459   uint16_t sized GNUNET_PACKED; /*  in big-endian! */
 460   uint16_t sizep GNUNET_PACKED; /*  in big-endian! */
 461   uint16_t sizeq GNUNET_PACKED; /*  in big-endian! */
 462   uint16_t sizedmp1 GNUNET_PACKED;      /*  in big-endian! */
 463   uint16_t sizedmq1 GNUNET_PACKED;      /*  in big-endian! */
 464   /* followed by the actual values */
 465 };
 466
 467
 468 /**
 469  * Deterministically (!) create a hostkey using only the
 470  * given HashCode as input to the PRNG.
 471  */
 472 static struct KskRsaPrivateKeyBinaryEncoded *
 473 makeKblockKeyInternal (const GNUNET_HashCode * hc)
 474 {
 475   KBlock_secret_key sk;
 476   GNUNET_HashCode hx;
 477   unsigned char *pbu[6];
 478   gcry_mpi_t *pkv[6];
 479   size_t sizes[6];
 480   struct KskRsaPrivateKeyBinaryEncoded *retval;
 481   int i;
 482   size_t size;
 483
 484   hx = *hc;
 485   generate_kblock_key (&sk, 1024,       /* at least 10x as fast than 2048 bits
 486                                            -- we simply cannot afford 2048 bits
 487                                            even on modern hardware, and especially
 488                                            not since clearly a dictionary attack
 489                                            will still be much cheaper
 490                                            than breaking a 1024 bit RSA key.
 491                                            If an adversary can spend the time to
 492                                            break a 1024 bit RSA key just to forge
 493                                            a signature -- SO BE IT. [ CG, 6/2005 ] */
 494                        &hx);
 495   pkv[0] = &sk.n;
 496   pkv[1] = &sk.e;
 497   pkv[2] = &sk.d;
 498   pkv[3] = &sk.p;
 499   pkv[4] = &sk.q;
 500   pkv[5] = &sk.u;
 501   size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
 502   for (i = 0; i < 6; i++)
 503     {
 504       gcry_mpi_aprint(GCRYMPI_FMT_STD, &pbu[i], &sizes[i], *pkv[i]);
 505       size += sizes[i];
 506     }
 507   GNUNET_assert (size < 65536);
 508   retval = GNUNET_malloc (size);
 509   retval->len = htons (size);
 510   i = 0;
 511   retval->sizen = htons (sizes[0]);
 512   memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
 513   i += sizes[0];
 514   retval->sizee = htons (sizes[1]);
 515   memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
 516   i += sizes[1];
 517   retval->sized = htons (sizes[2]);
 518   memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
 519   i += sizes[2];
 520   /* swap p and q! */
 521   retval->sizep = htons (sizes[4]);
 522   memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
 523   i += sizes[4];
 524   retval->sizeq = htons (sizes[3]);
 525   memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
 526   i += sizes[3];
 527   retval->sizedmp1 = htons (0);
 528   retval->sizedmq1 = htons (0);
 529   memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
 530   for (i = 0; i < 6; i++)
 531     {
 532       gcry_mpi_release (*pkv[i]);
 533       free (pbu[i]);
 534     }
 535   return retval;
 536 }
 537
 538
 539 /**
 540  * Decode the internal format into the format used
 541  * by libgcrypt.
 542  */
 543 static struct GNUNET_CRYPTO_RsaPrivateKey *
 544 ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
 545 {
 546   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 547   gcry_sexp_t res;
 548   gcry_mpi_t n, e, d, p, q, u;
 549   int rc;
 550   size_t size;
 551   int pos;
 552
 553   pos = 0;
 554   size = ntohs (encoding->sizen);
 555   rc = gcry_mpi_scan (&n,
 556                       GCRYMPI_FMT_USG,
 557                       &((const unsigned char *) (&encoding[1]))[pos],
 558                       size, &size);
 559   pos += ntohs (encoding->sizen);
 560   if (rc)
 561     {
 562       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 563       return NULL;
 564     }
 565   size = ntohs (encoding->sizee);
 566   rc = gcry_mpi_scan (&e,
 567                       GCRYMPI_FMT_USG,
 568                       &((const unsigned char *) (&encoding[1]))[pos],
 569                       size, &size);
 570   pos += ntohs (encoding->sizee);
 571   if (rc)
 572     {
 573       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 574       gcry_mpi_release (n);
 575       return NULL;
 576     }
 577   size = ntohs (encoding->sized);
 578   rc = gcry_mpi_scan (&d,
 579                       GCRYMPI_FMT_USG,
 580                       &((const unsigned char *) (&encoding[1]))[pos],
 581                       size, &size);
 582   pos += ntohs (encoding->sized);
 583   if (rc)
 584     {
 585       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 586       gcry_mpi_release (n);
 587       gcry_mpi_release (e);
 588       return NULL;
 589     }
 590   /* swap p and q! */
 591   size = ntohs (encoding->sizep);
 592   if (size > 0)
 593     {
 594       rc = gcry_mpi_scan (&q,
 595                           GCRYMPI_FMT_USG,
 596                           &((const unsigned char *) (&encoding[1]))[pos],
 597                           size, &size);
 598       pos += ntohs (encoding->sizep);
 599       if (rc)
 600         {
 601           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 602           gcry_mpi_release (n);
 603           gcry_mpi_release (e);
 604           gcry_mpi_release (d);
 605           return NULL;
 606         }
 607     }
 608   else
 609     q = NULL;
 610   size = ntohs (encoding->sizeq);
 611   if (size > 0)
 612     {
 613       rc = gcry_mpi_scan (&p,
 614                           GCRYMPI_FMT_USG,
 615                           &((const unsigned char *) (&encoding[1]))[pos],
 616                           size, &size);
 617       pos += ntohs (encoding->sizeq);
 618       if (rc)
 619         {
 620           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 621           gcry_mpi_release (n);
 622           gcry_mpi_release (e);
 623           gcry_mpi_release (d);
 624           if (q != NULL)
 625             gcry_mpi_release (q);
 626           return NULL;
 627         }
 628     }
 629   else
 630     p = NULL;
 631   pos += ntohs (encoding->sizedmp1);
 632   pos += ntohs (encoding->sizedmq1);
 633   size =
 634     ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
 635     pos;
 636   if (size > 0)
 637     {
 638       rc = gcry_mpi_scan (&u,
 639                           GCRYMPI_FMT_USG,
 640                           &((const unsigned char *) (&encoding[1]))[pos],
 641                           size, &size);
 642       if (rc)
 643         {
 644           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 645           gcry_mpi_release (n);
 646           gcry_mpi_release (e);
 647           gcry_mpi_release (d);
 648           if (p != NULL)
 649             gcry_mpi_release (p);
 650           if (q != NULL)
 651             gcry_mpi_release (q);
 652           return NULL;
 653         }
 654     }
 655   else
 656     u = NULL;
 657
 658   if ((p != NULL) && (q != NULL) && (u != NULL))
 659     {
 660       rc = gcry_sexp_build (&res, &size,        /* erroff */
 661                             "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
 662                             n, e, d, p, q, u);
 663     }
 664   else
 665     {
 666       if ((p != NULL) && (q != NULL))
 667         {
 668           rc = gcry_sexp_build (&res, &size,    /* erroff */
 669                                 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
 670                                 n, e, d, p, q);
 671         }
 672       else
 673         {
 674           rc = gcry_sexp_build (&res, &size,    /* erroff */
 675                                 "(private-key(rsa(n %m)(e %m)(d %m)))",
 676                                 n, e, d);
 677         }
 678     }
 679   gcry_mpi_release (n);
 680   gcry_mpi_release (e);
 681   gcry_mpi_release (d);
 682   if (p != NULL)
 683     gcry_mpi_release (p);
 684   if (q != NULL)
 685     gcry_mpi_release (q);
 686   if (u != NULL)
 687     gcry_mpi_release (u);
 688
 689   if (rc)
 690     LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
 691 #if EXTRA_CHECKS
 692   if (gcry_pk_testkey (res))
 693     {
 694       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
 695       return NULL;
 696     }
 697 #endif
 698   ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
 699   ret->sexp = res;
 700   return ret;
 701 }
 702
 703
 704 struct KBlockKeyCacheLine
 705 {
 706   GNUNET_HashCode hc;
 707   struct KskRsaPrivateKeyBinaryEncoded *pke;
 708 };
 709
 710 static struct KBlockKeyCacheLine **cache;
 711
 712 static unsigned int cacheSize;
 713
 714 /**
 715  * Deterministically (!) create a hostkey using only the
 716  * given HashCode as input to the PRNG.
 717  */
 718 struct GNUNET_CRYPTO_RsaPrivateKey *
 719 GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
 720 {
 721   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 722   struct KBlockKeyCacheLine *line;
 723   unsigned int i;
 724
 725   for (i = 0; i < cacheSize; i++)
 726     {
 727       if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
 728         {
 729           ret = ksk_decode_key (cache[i]->pke);
 730           return ret;
 731         }
 732     }
 733
 734   line = GNUNET_malloc (sizeof (struct KBlockKeyCacheLine));
 735   line->hc = *hc;
 736   line->pke = makeKblockKeyInternal (hc);
 737   GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
 738   cache[cacheSize - 1] = line;
 739   return ksk_decode_key (line->pke);
 740 }
 741
 742
 743 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
 744 {
 745   unsigned int i;
 746
 747   for (i = 0; i < cacheSize; i++)
 748     {
 749       GNUNET_free (cache[i]->pke);
 750       GNUNET_free (cache[i]);
 751     }
 752   GNUNET_array_grow (cache, cacheSize, 0);
 753 }
 754
 755
 756 /* end of crypto_ksk.c */