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