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