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 /**
 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, &written,
 352                                          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               while (mods[i] + step >= x)
 364                 mods[i] -= x;
 365               if (!(mods[i] + step))
 366                 break;
 367             }
 368           if (i < no_of_small_prime_numbers)
 369             continue;           /* Found a multiple of an already known prime. */
 370
 371           gcry_mpi_add_ui (*ptest, prime, step);
 372           if (!gcry_mpi_test_bit (*ptest, nbits - 2))
 373             break;
 374
 375           /* Do a fast Fermat test now. */
 376           gcry_mpi_sub_ui (pminus1, *ptest, 1);
 377           gcry_mpi_powm (result, val_2, pminus1, *ptest);
 378           if ((!gcry_mpi_cmp_ui (result, 1)) && (is_prime (*ptest, 5, hc)))
 379             {
 380               /* Got it. */
 381               gcry_mpi_release (sp);
 382               gcry_mpi_release (tmp);
 383               gcry_mpi_release (val_2);
 384               gcry_mpi_release (val_3);
 385               gcry_mpi_release (result);
 386               gcry_mpi_release (pminus1);
 387               gcry_mpi_release (prime);
 388               return;
 389             }
 390         }
 391     }
 392 }
 393
 394 /**
 395  * Generate a key pair with a key of size NBITS.
 396  * @param sk where to store the key
 397  * @param nbits the number of bits to use
 398  * @param hc the HC to use for PRNG (modified!)
 399  */
 400 static void
 401 generate_kblock_key (KBlock_secret_key * sk,
 402                      unsigned int nbits, GNUNET_HashCode * hc)
 403 {
 404   gcry_mpi_t t1, t2;
 405   gcry_mpi_t phi;                    /* helper: (p-1)(q-1) */
 406   gcry_mpi_t g;
 407   gcry_mpi_t f;
 408
 409   /* make sure that nbits is even so that we generate p, q of equal size */
 410   if ((nbits & 1))
 411     nbits++;
 412
 413   sk->e = gcry_mpi_set_ui (NULL, 257);
 414   sk->n = gcry_mpi_new(0);
 415   sk->p = gcry_mpi_new(0);
 416   sk->q = gcry_mpi_new(0);
 417   sk->d = gcry_mpi_new(0);
 418   sk->u = gcry_mpi_new(0);
 419
 420   t1 = gcry_mpi_new(0);
 421   t2 = gcry_mpi_new(0);
 422   phi = gcry_mpi_new(0);
 423   g = gcry_mpi_new(0);
 424   f = gcry_mpi_new(0);
 425
 426   do
 427     {
 428       do
 429         {
 430           gcry_mpi_release (sk->p);
 431           gcry_mpi_release (sk->q);
 432           gen_prime (&sk->p, nbits / 2, hc);
 433           gen_prime (&sk->q, nbits / 2, hc);
 434
 435           if (gcry_mpi_cmp (sk->p, sk->q) > 0)       /* p shall be smaller than q (for calc of u) */
 436             gcry_mpi_swap (sk->p, sk->q);
 437           /* calculate the modulus */
 438           gcry_mpi_mul (sk->n, sk->p, sk->q);
 439         }
 440       while (gcry_mpi_get_nbits (sk->n) != nbits);
 441
 442       /* calculate Euler totient: phi = (p-1)(q-1) */
 443       gcry_mpi_sub_ui (t1, sk->p, 1);
 444       gcry_mpi_sub_ui (t2, sk->q, 1);
 445       gcry_mpi_mul (phi, t1, t2);
 446       gcry_mpi_gcd (g, t1, t2);
 447       gcry_mpi_div (f, NULL, phi, g, 0);
 448       while (0 == gcry_mpi_gcd (t1, sk->e, phi))
 449         {                       /* (while gcd is not 1) */
 450           gcry_mpi_add_ui (sk->e, sk->e, 2);
 451         }
 452
 453       /* calculate the secret key d = e^1 mod phi */
 454     }
 455   while ((0 == gcry_mpi_invm (sk->d, sk->e, f)) ||
 456          (0 == gcry_mpi_invm (sk->u, sk->p, sk->q)));
 457
 458   gcry_mpi_release (t1);
 459   gcry_mpi_release (t2);
 460   gcry_mpi_release (phi);
 461   gcry_mpi_release (f);
 462   gcry_mpi_release (g);
 463 }
 464
 465
 466 /**
 467  * Internal representation of the private key.
 468  */
 469 struct KskRsaPrivateKeyBinaryEncoded
 470 {
 471   /**
 472    * Total size of the structure, in bytes, in big-endian!
 473    */
 474   uint16_t len GNUNET_PACKED;
 475   uint16_t sizen GNUNET_PACKED; /*  in big-endian! */
 476   uint16_t sizee GNUNET_PACKED; /*  in big-endian! */
 477   uint16_t sized GNUNET_PACKED; /*  in big-endian! */
 478   uint16_t sizep GNUNET_PACKED; /*  in big-endian! */
 479   uint16_t sizeq GNUNET_PACKED; /*  in big-endian! */
 480   uint16_t sizedmp1 GNUNET_PACKED;      /*  in big-endian! */
 481   uint16_t sizedmq1 GNUNET_PACKED;      /*  in big-endian! */
 482   /* followed by the actual values */
 483 };
 484
 485
 486 /**
 487  * Deterministically (!) create a hostkey using only the
 488  * given HashCode as input to the PRNG.
 489  */
 490 static struct KskRsaPrivateKeyBinaryEncoded *
 491 makeKblockKeyInternal (const GNUNET_HashCode * hc)
 492 {
 493   KBlock_secret_key sk;
 494   GNUNET_HashCode hx;
 495   unsigned char *pbu[6];
 496   gcry_mpi_t *pkv[6];
 497   size_t sizes[6];
 498   struct KskRsaPrivateKeyBinaryEncoded *retval;
 499   int i;
 500   size_t size;
 501
 502   hx = *hc;
 503   generate_kblock_key (&sk, 1024,       /* at least 10x as fast than 2048 bits
 504                                            -- we simply cannot afford 2048 bits
 505                                            even on modern hardware, and especially
 506                                            not since clearly a dictionary attack
 507                                            will still be much cheaper
 508                                            than breaking a 1024 bit RSA key.
 509                                            If an adversary can spend the time to
 510                                            break a 1024 bit RSA key just to forge
 511                                            a signature -- SO BE IT. [ CG, 6/2005 ] */
 512                        &hx);
 513   pkv[0] = &sk.n;
 514   pkv[1] = &sk.e;
 515   pkv[2] = &sk.d;
 516   pkv[3] = &sk.p;
 517   pkv[4] = &sk.q;
 518   pkv[5] = &sk.u;
 519   size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
 520   for (i = 0; i < 6; i++)
 521     {
 522       gcry_mpi_aprint(GCRYMPI_FMT_STD, &pbu[i], &sizes[i], *pkv[i]);
 523       size += sizes[i];
 524     }
 525   GNUNET_assert (size < 65536);
 526   retval = GNUNET_malloc (size);
 527   retval->len = htons (size);
 528   i = 0;
 529   retval->sizen = htons (sizes[0]);
 530   memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
 531   i += sizes[0];
 532   retval->sizee = htons (sizes[1]);
 533   memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
 534   i += sizes[1];
 535   retval->sized = htons (sizes[2]);
 536   memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
 537   i += sizes[2];
 538   /* swap p and q! */
 539   retval->sizep = htons (sizes[4]);
 540   memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
 541   i += sizes[4];
 542   retval->sizeq = htons (sizes[3]);
 543   memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
 544   i += sizes[3];
 545   retval->sizedmp1 = htons (0);
 546   retval->sizedmq1 = htons (0);
 547   memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
 548   for (i = 0; i < 6; i++)
 549     {
 550       gcry_mpi_release (*pkv[i]);
 551       free (pbu[i]);
 552     }
 553   return retval;
 554 }
 555
 556
 557 /**
 558  * Decode the internal format into the format used
 559  * by libgcrypt.
 560  */
 561 static struct GNUNET_CRYPTO_RsaPrivateKey *
 562 ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
 563 {
 564   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 565   gcry_sexp_t res;
 566   gcry_mpi_t n, e, d, p, q, u;
 567   int rc;
 568   size_t size;
 569   int pos;
 570
 571   pos = 0;
 572   size = ntohs (encoding->sizen);
 573   rc = gcry_mpi_scan (&n,
 574                       GCRYMPI_FMT_USG,
 575                       &((const unsigned char *) (&encoding[1]))[pos],
 576                       size, &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,
 585                       GCRYMPI_FMT_USG,
 586                       &((const unsigned char *) (&encoding[1]))[pos],
 587                       size, &size);
 588   pos += ntohs (encoding->sizee);
 589   if (rc)
 590     {
 591       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 592       gcry_mpi_release (n);
 593       return NULL;
 594     }
 595   size = ntohs (encoding->sized);
 596   rc = gcry_mpi_scan (&d,
 597                       GCRYMPI_FMT_USG,
 598                       &((const unsigned char *) (&encoding[1]))[pos],
 599                       size, &size);
 600   pos += ntohs (encoding->sized);
 601   if (rc)
 602     {
 603       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 604       gcry_mpi_release (n);
 605       gcry_mpi_release (e);
 606       return NULL;
 607     }
 608   /* swap p and q! */
 609   size = ntohs (encoding->sizep);
 610   if (size > 0)
 611     {
 612       rc = gcry_mpi_scan (&q,
 613                           GCRYMPI_FMT_USG,
 614                           &((const unsigned char *) (&encoding[1]))[pos],
 615                           size, &size);
 616       pos += ntohs (encoding->sizep);
 617       if (rc)
 618         {
 619           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 620           gcry_mpi_release (n);
 621           gcry_mpi_release (e);
 622           gcry_mpi_release (d);
 623           return NULL;
 624         }
 625     }
 626   else
 627     q = NULL;
 628   size = ntohs (encoding->sizeq);
 629   if (size > 0)
 630     {
 631       rc = gcry_mpi_scan (&p,
 632                           GCRYMPI_FMT_USG,
 633                           &((const unsigned char *) (&encoding[1]))[pos],
 634                           size, &size);
 635       pos += ntohs (encoding->sizeq);
 636       if (rc)
 637         {
 638           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 639           gcry_mpi_release (n);
 640           gcry_mpi_release (e);
 641           gcry_mpi_release (d);
 642           if (q != NULL)
 643             gcry_mpi_release (q);
 644           return NULL;
 645         }
 646     }
 647   else
 648     p = NULL;
 649   pos += ntohs (encoding->sizedmp1);
 650   pos += ntohs (encoding->sizedmq1);
 651   size =
 652     ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
 653     pos;
 654   if (size > 0)
 655     {
 656       rc = gcry_mpi_scan (&u,
 657                           GCRYMPI_FMT_USG,
 658                           &((const unsigned char *) (&encoding[1]))[pos],
 659                           size, &size);
 660       if (rc)
 661         {
 662           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 663           gcry_mpi_release (n);
 664           gcry_mpi_release (e);
 665           gcry_mpi_release (d);
 666           if (p != NULL)
 667             gcry_mpi_release (p);
 668           if (q != NULL)
 669             gcry_mpi_release (q);
 670           return NULL;
 671         }
 672     }
 673   else
 674     u = NULL;
 675
 676   if ((p != NULL) && (q != NULL) && (u != NULL))
 677     {
 678       rc = gcry_sexp_build (&res, &size,        /* erroff */
 679                             "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
 680                             n, e, d, p, q, u);
 681     }
 682   else
 683     {
 684       if ((p != NULL) && (q != NULL))
 685         {
 686           rc = gcry_sexp_build (&res, &size,    /* erroff */
 687                                 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
 688                                 n, e, d, p, q);
 689         }
 690       else
 691         {
 692           rc = gcry_sexp_build (&res, &size,    /* erroff */
 693                                 "(private-key(rsa(n %m)(e %m)(d %m)))",
 694                                 n, e, d);
 695         }
 696     }
 697   gcry_mpi_release (n);
 698   gcry_mpi_release (e);
 699   gcry_mpi_release (d);
 700   if (p != NULL)
 701     gcry_mpi_release (p);
 702   if (q != NULL)
 703     gcry_mpi_release (q);
 704   if (u != NULL)
 705     gcry_mpi_release (u);
 706
 707   if (rc)
 708     LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
 709 #if EXTRA_CHECKS
 710   if (gcry_pk_testkey (res))
 711     {
 712       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
 713       return NULL;
 714     }
 715 #endif
 716   ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
 717   ret->sexp = res;
 718   return ret;
 719 }
 720
 721
 722 struct KBlockKeyCacheLine
 723 {
 724   GNUNET_HashCode hc;
 725   struct KskRsaPrivateKeyBinaryEncoded *pke;
 726 };
 727
 728 static struct KBlockKeyCacheLine **cache;
 729
 730 static unsigned int cacheSize;
 731
 732 /**
 733  * Deterministically (!) create a hostkey using only the
 734  * given HashCode as input to the PRNG.
 735  */
 736 struct GNUNET_CRYPTO_RsaPrivateKey *
 737 GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
 738 {
 739   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 740   struct KBlockKeyCacheLine *line;
 741   unsigned int i;
 742
 743   for (i = 0; i < cacheSize; i++)
 744     {
 745       if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
 746         {
 747           ret = ksk_decode_key (cache[i]->pke);
 748           return ret;
 749         }
 750     }
 751
 752   line = GNUNET_malloc (sizeof (struct KBlockKeyCacheLine));
 753   line->hc = *hc;
 754   line->pke = makeKblockKeyInternal (hc);
 755   GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
 756   cache[cacheSize - 1] = line;
 757   return ksk_decode_key (line->pke);
 758 }
 759
 760
 761 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
 762 {
 763   unsigned int i;
 764
 765   for (i = 0; i < cacheSize; i++)
 766     {
 767       GNUNET_free (cache[i]->pke);
 768       GNUNET_free (cache[i]);
 769     }
 770   GNUNET_array_grow (cache, cacheSize, 0);
 771 }
 772
 773
 774 /* end of crypto_ksk.c */