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