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