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 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
  43
  44 /**
  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).
  48  */
  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);
  50
  51
  52 typedef struct
  53 {
  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. */
  60 } KBlock_secret_key;
  61
  62 /**
  63  * The private information of an RSA key pair.
  64  * NOTE: this must match the definition in crypto_rsa.c
  65  */
  66 struct GNUNET_CRYPTO_RsaPrivateKey
  67 {
  68   gcry_sexp_t sexp;
  69 };
  70
  71
  72 static void
  73 mpz_randomize (gcry_mpi_t n, unsigned int nbits, GNUNET_HashCode * rnd)
  74 {
  75   GNUNET_HashCode hc;
  76   GNUNET_HashCode tmp;
  77   int bits_per_hc = sizeof (GNUNET_HashCode) * 8;
  78   int cnt;
  79   int i;
  80
  81   GNUNET_assert (nbits > 0);
  82   cnt = (nbits + bits_per_hc - 1) / bits_per_hc;
  83   gcry_mpi_set_ui (n, 0);
  84
  85   tmp = *rnd;
  86   for (i = 0; i < cnt; i++)
  87     {
  88       int j;
  89
  90       if (i > 0)
  91         GNUNET_CRYPTO_hash (&hc, sizeof (GNUNET_HashCode), &tmp);
  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 /**
 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.
 208  */
 209 static void
 210 adjust (unsigned char *buf, size_t size, size_t target)
 211 {
 212   if (size < target)
 213     {
 214       memmove (&buf[target - size], buf, size);
 215       memset (buf, 0, target - size);
 216     }
 217 }
 218
 219
 220 static void
 221 gen_prime (gcry_mpi_t * ptest, unsigned int nbits, GNUNET_HashCode * hc)
 222 {
 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,
 305     0
 306   };
 307 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
 308   static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
 309
 310   gcry_mpi_t prime, pminus1, val_2, val_3, result;
 311   unsigned int i;
 312   unsigned int step;
 313   unsigned int mods[no_of_small_prime_numbers];
 314   gcry_mpi_t tmp;
 315   gcry_mpi_t sp;
 316
 317   GNUNET_assert (nbits >= 16);
 318
 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);
 328   while (1)
 329     {
 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);
 339
 340       /* Calculate all remainders. */
 341       for (i = 0; i < no_of_small_prime_numbers; i++)
 342         {
 343           size_t written;
 344
 345           gcry_mpi_set_ui (sp, small_prime_numbers[i]);
 346           gcry_mpi_div (NULL, tmp, prime, sp, -1);
 347           mods[i] = 0;
 348           written = sizeof (unsigned int);
 349           GNUNET_assert (0 ==
 350                          gcry_mpi_print (GCRYMPI_FMT_USG,
 351                                          (unsigned char *) &mods[i], written,
 352                                          &written, tmp));
 353           adjust ((unsigned char *) &mods[i], written, sizeof (unsigned int));
 354           mods[i] = ntohl (mods[i]);
 355         }
 356       /* Now try some primes starting with prime. */
 357       for (step = 0; step < 20000; step += 2)
 358         {
 359           /* Check against all the small primes we have in mods. */
 360           for (i = 0; i < no_of_small_prime_numbers; i++)
 361             {
 362               uint16_t x = small_prime_numbers[i];
 363
 364               while (mods[i] + step >= x)
 365                 mods[i] -= x;
 366               if (!(mods[i] + step))
 367                 break;
 368             }
 369           if (i < no_of_small_prime_numbers)
 370             continue;           /* Found a multiple of an already known prime. */
 371
 372           gcry_mpi_add_ui (*ptest, prime, step);
 373           if (!gcry_mpi_test_bit (*ptest, nbits - 2))
 374             break;
 375
 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)))
 380             {
 381               /* Got it. */
 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);
 389               return;
 390             }
 391         }
 392     }
 393 }
 394
 395 /**
 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!)
 400  */
 401 static void
 402 generate_kblock_key (KBlock_secret_key * sk, unsigned int nbits,
 403                      GNUNET_HashCode * hc)
 404 {
 405   gcry_mpi_t t1, t2;
 406   gcry_mpi_t phi;               /* helper: (p-1)(q-1) */
 407   gcry_mpi_t g;
 408   gcry_mpi_t f;
 409
 410   /* make sure that nbits is even so that we generate p, q of equal size */
 411   if ((nbits & 1))
 412     nbits++;
 413
 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);
 420
 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);
 426
 427   do
 428     {
 429       do
 430         {
 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);
 435
 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);
 440         }
 441       while (gcry_mpi_get_nbits (sk->n) != nbits);
 442
 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);
 452         }
 453
 454       /* calculate the secret key d = e^1 mod phi */
 455     }
 456   while ((0 == gcry_mpi_invm (sk->d, sk->e, f)) ||
 457          (0 == gcry_mpi_invm (sk->u, sk->p, sk->q)));
 458
 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);
 464 }
 465
 466
 467 /**
 468  * Internal representation of the private key.
 469  */
 470 struct KskRsaPrivateKeyBinaryEncoded
 471 {
 472   /**
 473    * Total size of the structure, in bytes, in big-endian!
 474    */
 475   uint16_t len GNUNET_PACKED;
 476   uint16_t sizen GNUNET_PACKED; /*  in big-endian! */
 477   uint16_t sizee GNUNET_PACKED; /*  in big-endian! */
 478   uint16_t sized GNUNET_PACKED; /*  in big-endian! */
 479   uint16_t sizep GNUNET_PACKED; /*  in big-endian! */
 480   uint16_t sizeq GNUNET_PACKED; /*  in big-endian! */
 481   uint16_t sizedmp1 GNUNET_PACKED;      /*  in big-endian! */
 482   uint16_t sizedmq1 GNUNET_PACKED;      /*  in big-endian! */
 483   /* followed by the actual values */
 484 };
 485
 486
 487 /**
 488  * Deterministically (!) create a hostkey using only the
 489  * given HashCode as input to the PRNG.
 490  */
 491 static struct KskRsaPrivateKeyBinaryEncoded *
 492 makeKblockKeyInternal (const GNUNET_HashCode * hc)
 493 {
 494   KBlock_secret_key sk;
 495   GNUNET_HashCode hx;
 496   unsigned char *pbu[6];
 497   gcry_mpi_t *pkv[6];
 498   size_t sizes[6];
 499   struct KskRsaPrivateKeyBinaryEncoded *retval;
 500   int i;
 501   size_t size;
 502
 503   hx = *hc;
 504   generate_kblock_key (&sk, 1024,       /* at least 10x as fast than 2048 bits
 505                                          * -- we simply cannot afford 2048 bits
 506                                          * even on modern hardware, and especially
 507                                          * not since clearly a dictionary attack
 508                                          * will still be much cheaper
 509                                          * than breaking a 1024 bit RSA key.
 510                                          * If an adversary can spend the time to
 511                                          * break a 1024 bit RSA key just to forge
 512                                          * a signature -- SO BE IT. [ CG, 6/2005 ] */
 513                        &hx);
 514   pkv[0] = &sk.n;
 515   pkv[1] = &sk.e;
 516   pkv[2] = &sk.d;
 517   pkv[3] = &sk.p;
 518   pkv[4] = &sk.q;
 519   pkv[5] = &sk.u;
 520   size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
 521   for (i = 0; i < 6; i++)
 522     {
 523       gcry_mpi_aprint (GCRYMPI_FMT_STD, &pbu[i], &sizes[i], *pkv[i]);
 524       size += sizes[i];
 525     }
 526   GNUNET_assert (size < 65536);
 527   retval = GNUNET_malloc (size);
 528   retval->len = htons (size);
 529   i = 0;
 530   retval->sizen = htons (sizes[0]);
 531   memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
 532   i += sizes[0];
 533   retval->sizee = htons (sizes[1]);
 534   memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
 535   i += sizes[1];
 536   retval->sized = htons (sizes[2]);
 537   memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
 538   i += sizes[2];
 539   /* swap p and q! */
 540   retval->sizep = htons (sizes[4]);
 541   memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
 542   i += sizes[4];
 543   retval->sizeq = htons (sizes[3]);
 544   memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
 545   i += sizes[3];
 546   retval->sizedmp1 = htons (0);
 547   retval->sizedmq1 = htons (0);
 548   memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
 549   for (i = 0; i < 6; i++)
 550     {
 551       gcry_mpi_release (*pkv[i]);
 552       free (pbu[i]);
 553     }
 554   return retval;
 555 }
 556
 557
 558 /**
 559  * Decode the internal format into the format used
 560  * by libgcrypt.
 561  */
 562 static struct GNUNET_CRYPTO_RsaPrivateKey *
 563 ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
 564 {
 565   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 566   gcry_sexp_t res;
 567   gcry_mpi_t n, e, d, p, q, u;
 568   int rc;
 569   size_t size;
 570   int pos;
 571
 572   pos = 0;
 573   size = ntohs (encoding->sizen);
 574   rc = gcry_mpi_scan (&n, GCRYMPI_FMT_USG,
 575                       &((const unsigned char *) (&encoding[1]))[pos], size,
 576                       &size);
 577   pos += ntohs (encoding->sizen);
 578   if (rc)
 579     {
 580       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 581       return NULL;
 582     }
 583   size = ntohs (encoding->sizee);
 584   rc = gcry_mpi_scan (&e, GCRYMPI_FMT_USG,
 585                       &((const unsigned char *) (&encoding[1]))[pos], size,
 586                       &size);
 587   pos += ntohs (encoding->sizee);
 588   if (rc)
 589     {
 590       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 591       gcry_mpi_release (n);
 592       return NULL;
 593     }
 594   size = ntohs (encoding->sized);
 595   rc = gcry_mpi_scan (&d, GCRYMPI_FMT_USG,
 596                       &((const unsigned char *) (&encoding[1]))[pos], size,
 597                       &size);
 598   pos += ntohs (encoding->sized);
 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       return NULL;
 605     }
 606   /* swap p and q! */
 607   size = ntohs (encoding->sizep);
 608   if (size > 0)
 609     {
 610       rc = gcry_mpi_scan (&q, GCRYMPI_FMT_USG,
 611                           &((const unsigned char *) (&encoding[1]))[pos],
 612                           size, &size);
 613       pos += ntohs (encoding->sizep);
 614       if (rc)
 615         {
 616           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 617           gcry_mpi_release (n);
 618           gcry_mpi_release (e);
 619           gcry_mpi_release (d);
 620           return NULL;
 621         }
 622     }
 623   else
 624     q = NULL;
 625   size = ntohs (encoding->sizeq);
 626   if (size > 0)
 627     {
 628       rc = gcry_mpi_scan (&p, GCRYMPI_FMT_USG,
 629                           &((const unsigned char *) (&encoding[1]))[pos],
 630                           size, &size);
 631       pos += ntohs (encoding->sizeq);
 632       if (rc)
 633         {
 634           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 635           gcry_mpi_release (n);
 636           gcry_mpi_release (e);
 637           gcry_mpi_release (d);
 638           if (q != NULL)
 639             gcry_mpi_release (q);
 640           return NULL;
 641         }
 642     }
 643   else
 644     p = NULL;
 645   pos += ntohs (encoding->sizedmp1);
 646   pos += ntohs (encoding->sizedmq1);
 647   size =
 648     ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
 649     pos;
 650   if (size > 0)
 651     {
 652       rc = gcry_mpi_scan (&u, GCRYMPI_FMT_USG,
 653                           &((const unsigned char *) (&encoding[1]))[pos],
 654                           size, &size);
 655       if (rc)
 656         {
 657           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 658           gcry_mpi_release (n);
 659           gcry_mpi_release (e);
 660           gcry_mpi_release (d);
 661           if (p != NULL)
 662             gcry_mpi_release (p);
 663           if (q != NULL)
 664             gcry_mpi_release (q);
 665           return NULL;
 666         }
 667     }
 668   else
 669     u = NULL;
 670
 671   if ((p != NULL) && (q != NULL) && (u != NULL))
 672     {
 673       rc = gcry_sexp_build (&res, &size,        /* erroff */
 674                             "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
 675                             n, e, d, p, q, u);
 676     }
 677   else
 678     {
 679       if ((p != NULL) && (q != NULL))
 680         {
 681           rc = gcry_sexp_build (&res, &size,    /* erroff */
 682                                 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
 683                                 n, e, d, p, q);
 684         }
 685       else
 686         {
 687           rc = gcry_sexp_build (&res, &size,    /* erroff */
 688                                 "(private-key(rsa(n %m)(e %m)(d %m)))", n, e,
 689                                 d);
 690         }
 691     }
 692   gcry_mpi_release (n);
 693   gcry_mpi_release (e);
 694   gcry_mpi_release (d);
 695   if (p != NULL)
 696     gcry_mpi_release (p);
 697   if (q != NULL)
 698     gcry_mpi_release (q);
 699   if (u != NULL)
 700     gcry_mpi_release (u);
 701
 702   if (rc)
 703     LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
 704 #if EXTRA_CHECKS
 705   if (gcry_pk_testkey (res))
 706     {
 707       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
 708       return NULL;
 709     }
 710 #endif
 711   ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
 712   ret->sexp = res;
 713   return ret;
 714 }
 715
 716
 717 struct KBlockKeyCacheLine
 718 {
 719   GNUNET_HashCode hc;
 720   struct KskRsaPrivateKeyBinaryEncoded *pke;
 721 };
 722
 723 static struct KBlockKeyCacheLine **cache;
 724
 725 static unsigned int cacheSize;
 726
 727 /**
 728  * Deterministically (!) create a hostkey using only the
 729  * given HashCode as input to the PRNG.
 730  */
 731 struct GNUNET_CRYPTO_RsaPrivateKey *
 732 GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
 733 {
 734   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 735   struct KBlockKeyCacheLine *line;
 736   unsigned int i;
 737
 738   for (i = 0; i < cacheSize; i++)
 739     {
 740       if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
 741         {
 742           ret = ksk_decode_key (cache[i]->pke);
 743           return ret;
 744         }
 745     }
 746
 747   line = GNUNET_malloc (sizeof (struct KBlockKeyCacheLine));
 748   line->hc = *hc;
 749   line->pke = makeKblockKeyInternal (hc);
 750   GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
 751   cache[cacheSize - 1] = line;
 752   return ksk_decode_key (line->pke);
 753 }
 754
 755
 756 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
 757 {
 758   unsigned int i;
 759
 760   for (i = 0; i < cacheSize; i++)
 761     {
 762       GNUNET_free (cache[i]->pke);
 763       GNUNET_free (cache[i]);
 764     }
 765   GNUNET_array_grow (cache, cacheSize, 0);
 766 }
 767
 768
 769 /* end of crypto_ksk.c */