removed old leak detective
[strongswan.git] / src / scepclient / rsakey.c
1 /**
2 * @file rsakey.c
3 * @brief Functions for RSA key generation
4 */
5
6 /*
7 * Copyright (C) 1999, 2000, 2001 Henry Spencer.
8 * Copyright (C) 2005 Jan Hutter, Martin Willi
9 * Hochschule fuer Technik Rapperswil
10 *
11 * This program is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by the
13 * Free Software Foundation; either version 2 of the License, or (at your
14 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
15 *
16 * This program is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 * for more details.
20 *
21 * $Id: rsakey.c,v 1.5 2006/01/04 21:16:30 as Exp $
22 */
23
24
25 #include <stdlib.h>
26 #include <sys/types.h>
27 #include <sys/stat.h>
28 #include <fcntl.h>
29 #include <unistd.h>
30 #include <assert.h>
31 #include <gmp.h>
32
33 #include <freeswan.h>
34
35 #include "../pluto/constants.h"
36 #include "../pluto/defs.h"
37 #include "../pluto/mp_defs.h"
38 #include "../pluto/log.h"
39 #include "../pluto/asn1.h"
40 #include "../pluto/pkcs1.h"
41
42 #include "rsakey.h"
43
44 /* Number of times the probabilistic primality test is applied */
45 #define PRIMECHECK_ROUNDS 30
46
47 /* Public exponent used for signature key generation */
48 #define PUBLIC_EXPONENT 0x10001
49
50 #ifndef DEV_RANDOM
51 #define DEV_RANDOM "/dev/random"
52 #endif
53
54
55 /**
56 * @brief Reads a specific number of bytes from a given device/file
57 *
58 * @param[in] nbytes number of bytes to read from random device
59 * @param[out] buf pointer to buffer where to write the data in.
60 * size of buffer has to be at least nbytes.
61 * @return TRUE, if succeeded, FALSE otherwise
62 */
63
64 static bool
65 get_true_random_bytes(size_t nbytes, char *buf)
66 {
67 size_t ndone;
68 size_t got;
69 char *device = DEV_RANDOM;
70
71 int dev = open(DEV_RANDOM, 0);
72
73 if (dev < 0)
74 {
75 fprintf(stderr, "could not open random device %s", device);
76 return FALSE;
77 }
78
79 DBG(DBG_CONTROL,
80 DBG_log("getting %d bytes from %s...", (int) nbytes, device)
81 )
82
83 ndone = 0;
84 while (ndone < nbytes)
85 {
86 got = read(dev, buf + ndone, nbytes - ndone);
87 if (got < 0)
88 {
89 fprintf(stderr, "read error on %s", device);
90 return FALSE;
91 }
92 if (got == 0)
93 {
94 fprintf(stderr, "eof on %s", device);
95 return FALSE;
96 }
97 ndone += got;
98 }
99 close(dev);
100 return TRUE;
101 }
102
103 /**
104 * @brief initialize an mpz_t to a random number, specified bit count
105 *
106 * Converting the random value in a value of type mpz_t is done
107 * by creating a hexbuffer.
108 * Converting via hex is a bit weird, but it's the best route GMP gives us.
109 * Note that highmost and lowmost bits are forced on -- highmost to give a
110 * number of exactly the specified length, lowmost so it is an odd number.
111 *
112 * @param[out] var uninitialized mpz_t to store th random number in
113 * @param[in] nbits length of var in bits (known to be a multiple of BITS_PER_BYTE)
114 * @return TRUE on success, FALSE otherwise
115 */
116 static bool
117 init_random(mpz_t var, int nbits)
118 {
119 size_t nbytes = (size_t)(nbits/BITS_PER_BYTE);
120 char random_buf[RSA_MAX_OCTETS/2];
121
122 assert(nbytes <= sizeof(random_buf));
123
124 if (!get_true_random_bytes(nbytes, random_buf))
125 return FALSE;
126
127 random_buf[0] |= 01 << (BITS_PER_BYTE-1); /* force high bit on */
128 random_buf[nbytes-1] |= 01; /* force low bit on */
129 n_to_mpz(var, random_buf, nbytes);
130 return TRUE;
131 }
132
133 /**
134 * @brief initialize an mpz_t to a random prime of specified size
135 *
136 * Efficiency tweak: we reject candidates that are 1 higher than a multiple
137 * of e, since they will make the internal modulus not relatively prime to e.
138 *
139 * @param[out] var mpz_t variable to initialize
140 * @param[in] nbits length of given prime in bits (known to be a multiple of BITS_PER_BYTE)
141 * @param[in] eval E-Value, 0 means don't bother w. tweak
142 * @return 1 on success, 0 otherwise
143 */
144 static bool
145 init_prime(mpz_t var, int nbits, int eval)
146 {
147 unsigned long tries;
148 size_t len;
149
150 /* get a random value of nbits length */
151 if (!init_random(var, nbits))
152 return FALSE;
153
154 /* check if odd number */
155 assert(mpz_fdiv_ui(var, 2) == 1);
156 DBG(DBG_CONTROLMORE,
157 DBG_log("looking for a prime starting there (can take a while)...")
158 )
159
160 tries = 1;
161 while (mpz_fdiv_ui(var, eval) == 1
162 || !mpz_probab_prime_p(var, PRIMECHECK_ROUNDS))
163 {
164 /* not a prime, increase by 2 */
165 mpz_add_ui(var, var, 2);
166 tries++;
167 }
168
169 len = mpz_sizeinbase(var, 2);
170
171 /* check bit length of primee */
172 assert(len == (size_t)nbits || len == (size_t)(nbits+1));
173
174 if (len == (size_t)(nbits+1))
175 {
176 DBG(DBG_CONTROLMORE,
177 DBG_log("carry out occurred (!), retrying...")
178 )
179 mpz_clear(var);
180 /* recursive call */
181 return init_prime(var, nbits, eval);
182 }
183 DBG(DBG_CONTROLMORE,
184 DBG_log("found it after %lu tries.",tries)
185 )
186 return TRUE;
187 }
188
189 /**
190 * @brief Generate a RSA key usable for encryption
191 *
192 * Generate an RSA key usable for encryption. All the
193 * values of the RSA key are filled into mpz_t parameters.
194 * These mpz_t parameters must not be initialized and have
195 * to be cleared with mpz_clear after using.
196 *
197 * @param[in] nbits size of rsa key in bits
198 * @return RSA_public_key_t containing the generated RSA key
199 */
200 err_t
201 generate_rsa_private_key(int nbits, RSA_private_key_t *key)
202 {
203 mpz_t p, q, n, e, d, exp1, exp2, coeff;
204 mpz_t m, q1, t; /* temporary variables*/
205
206 DBG(DBG_CONTROL,
207 DBG_log("generating %d bit RSA key:", nbits)
208 )
209
210 if (nbits <= 0)
211 return "negative rsa key length!";
212
213 /* Get values of primes p and q */
214 DBG(DBG_CONTROLMORE,
215 DBG_log("initialize prime p")
216 )
217 if (!init_prime(p, nbits/2, PUBLIC_EXPONENT))
218 return "could not generate prime p";
219
220 DBG(DBG_CONTROLMORE,
221 DBG_log("initialize prime q")
222 )
223 if (!init_prime(q, nbits/2, PUBLIC_EXPONENT))
224 return "could not generate prime q";
225
226 mpz_init(t);
227
228 /* Swapping primes so p is larger then q */
229 if (mpz_cmp(p, q) < 0)
230 {
231 DBG(DBG_CONTROLMORE,
232 DBG_log("swapping primes so p is the larger...")
233 );
234 mpz_set(t, p);
235 mpz_set(p, q);
236 mpz_set(q, t);
237 }
238
239 DBG(DBG_CONTROLMORE,
240 DBG_log("computing modulus...")
241 )
242 mpz_init(n);
243 /* n = p*q */
244 mpz_mul(n, p, q);
245
246 /* Assign e the value of defined PUBLIC_EXPONENT */
247 mpz_init_set_ui(e, PUBLIC_EXPONENT);
248
249 DBG(DBG_CONTROLMORE,
250 DBG_log("computing lcm(p-1, q-1)...")
251 )
252 /* m = p */
253 mpz_init_set(m, p);
254 /* m = m-1 */
255 mpz_sub_ui(m, m, 1);
256 /* q1 = q */
257 mpz_init_set(q1, q);
258 /* q1 = q1-1 */
259 mpz_sub_ui(q1, q1, 1);
260 /* t = gcd(p-1, q-1) */
261 mpz_gcd(t, m, q1);
262 /* m = (p-1)*(q-1) */
263 mpz_mul(m, m, q1);
264 /* m = m / t */
265 mpz_divexact(m, m, t);
266 /* t = gcd(m, e) (greatest common divisor) */
267 mpz_gcd(t, m, e);
268 /* m and e relatively prime */
269 assert(mpz_cmp_ui(t, 1) == 0);
270
271 /* decryption key */
272 DBG(DBG_CONTROLMORE,
273 DBG_log("computing d...")
274 )
275 mpz_init(d);
276 /* e has an inverse mod m */
277 assert(mpz_invert(d, e, m));
278
279 /* make sure d is positive */
280 if (mpz_cmp_ui(d, 0) < 0)
281 mpz_add(d, d, m);
282
283 /* d has to be positive */
284 assert(mpz_cmp(d, m) < 0);
285
286 /* the speedup hacks */
287 DBG(DBG_CONTROLMORE,
288 DBG_log("computing exp1, exp1, coeff...")
289 )
290 mpz_init(exp1);
291 /* t = p-1 */
292 mpz_sub_ui(t, p, 1);
293 /* exp1 = d mod p-1 */
294 mpz_mod(exp1, d, t);
295
296 mpz_init(exp2);
297 /* t = q-1 */
298 mpz_sub_ui(t, q, 1);
299 /* exp2 = d mod q-1 */
300 mpz_mod(exp2, d, t);
301
302 mpz_init(coeff);
303 /* coeff = q^-1 mod p */
304 mpz_invert(coeff, q, p);
305
306 /* make sure coeff is positive */
307 if (mpz_cmp_ui(coeff, 0) < 0)
308 mpz_add(coeff, coeff, p);
309
310 /* coeff has to be positive */
311 assert(mpz_cmp(coeff, p) < 0);
312
313 /* Clear temporary variables */
314 mpz_clear(q1);
315 mpz_clear(m);
316 mpz_clear(t);
317
318 /* form FreeS/WAN keyid */
319 {
320 size_t e_len = (mpz_sizeinbase(e,2)+BITS_PER_BYTE-1)/BITS_PER_BYTE;
321 size_t n_len = (mpz_sizeinbase(n,2)+BITS_PER_BYTE-1)/BITS_PER_BYTE;
322 chunk_t e_ch = mpz_to_n(e, e_len);
323 chunk_t n_ch = mpz_to_n(n, n_len);
324 form_keyid(e_ch, n_ch, key->pub.keyid, &key->pub.k);
325 freeanychunk(e_ch);
326 freeanychunk(n_ch);
327 }
328 /* fill in the elements of the RSA private key */
329 key->p = *p;
330 key->q = *q;
331 key->pub.n = *n;
332 key->pub.e = *e;
333 key->d = *d;
334 key->dP = *exp1;
335 key->dQ = *exp2;
336 key->qInv = *coeff;
337
338 DBG(DBG_CONTROL,
339 DBG_log("RSA key *%s generated with %d bits", key->pub.keyid
340 , (int)mpz_sizeinbase(n,2))
341 )
342
343 #ifdef DEBUG
344 DBG(DBG_PRIVATE,
345 RSA_show_private_key(key)
346 )
347 #endif
348 return NULL;
349 }