1 /*
2 * Generation of RSA keypairs.
3 */
4
5 /* nettle, low-level cryptographics library
6 *
7 * Copyright (C) 2002 Niels Möller
8 * Copyright (C) 2014 Red Hat
9 *
10 * The nettle library is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU Lesser General Public License as published by
12 * the Free Software Foundation; either version 2.1 of the License, or (at your
13 * option) any later version.
14 *
15 * The nettle library is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18 * License for more details.
19 *
20 * You should have received a copy of the GNU Lesser General Public License
21 * along with the nettle library; see the file COPYING.LIB. If not, write to
22 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
23 * MA 02111-1301, USA.
24 */
25
26 #if HAVE_CONFIG_H
27 #include "config.h"
28 #endif
29
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <string.h>
33
34 #include <nettle/rsa.h>
35 #include <dsa-fips.h>
36 #include <rsa-fips.h>
37
38 #include <nettle/bignum.h>
39
40 static int
rsa_provable_prime(mpz_t p,unsigned * prime_seed_length,void * prime_seed,unsigned bits,unsigned seed_length,const void * seed,mpz_t e,void * progress_ctx,nettle_progress_func * progress)41 rsa_provable_prime (mpz_t p,
42 unsigned *prime_seed_length, void *prime_seed,
43 unsigned bits,
44 unsigned seed_length, const void *seed,
45 mpz_t e,
46 void *progress_ctx, nettle_progress_func * progress)
47 {
48 mpz_t x, t, s, r1, r2, p0, sq;
49 int ret;
50 unsigned pcounter = 0;
51 unsigned iterations;
52 unsigned storage_length = 0, i;
53 uint8_t *storage = NULL;
54 uint8_t pseed[MAX_PVP_SEED_SIZE+1];
55 unsigned pseed_length = sizeof(pseed), tseed_length;
56 unsigned max = bits*5;
57
58 mpz_init(p0);
59 mpz_init(sq);
60 mpz_init(x);
61 mpz_init(t);
62 mpz_init(s);
63 mpz_init(r1);
64 mpz_init(r2);
65
66 /* p1 = p2 = 1 */
67
68 ret = st_provable_prime(p0, &pseed_length, pseed,
69 NULL, 1+div_ceil(bits,2), seed_length,
70 seed, progress_ctx, progress);
71 if (ret == 0) {
72 goto cleanup;
73 }
74
75 iterations = div_ceil(bits, DIGEST_SIZE*8);
76 mpz_set_ui(x, 0);
77
78 if (iterations > 0) {
79 storage_length = iterations * DIGEST_SIZE;
80 storage = malloc(storage_length);
81 if (storage == NULL) {
82 goto fail;
83 }
84
85 nettle_mpz_set_str_256_u(s, pseed_length, pseed);
86 for (i = 0; i < iterations; i++) {
87 tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
88 if (tseed_length > sizeof(pseed))
89 goto fail;
90 nettle_mpz_get_str_256(tseed_length, pseed, s);
91
92 hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
93 tseed_length, pseed);
94 mpz_add_ui(s, s, 1);
95 }
96
97 nettle_mpz_set_str_256_u(x, storage_length, storage);
98 }
99
100 /* x = sqrt(2)*2^(bits-1) + (x mod 2^(bits) - sqrt(2)*2(bits-1)) */
101
102 /* sq = sqrt(2)*2^(bits-1) */
103 mpz_set_ui(r1, 1);
104 mpz_mul_2exp(r1, r1, 2*bits-1);
105 mpz_sqrt(sq, r1);
106
107 /* r2 = 2^bits - sq */
108 mpz_set_ui(r2, 1);
109 mpz_mul_2exp(r2, r2, bits);
110 mpz_sub(r2, r2, sq);
111
112 /* x = sqrt(2)*2^(bits-1) + (x mod (2^L - sqrt(2)*2^(bits-1)) */
113 mpz_mod(x, x, r2);
114 mpz_add(x, x, sq);
115
116 /* y = p2 = p1 = 1 */
117
118 /* r1 = (2 y p0 p1) */
119 mpz_mul_2exp(r1, p0, 1);
120
121 /* r2 = 2 p0 p1 p2 (p2=y=1) */
122 mpz_set(r2, r1);
123
124 /* r1 = (2 y p0 p1) + x */
125 mpz_add(r1, r1, x);
126
127 /* t = ((2 y p0 p1) + x) / (2 p0 p1 p2) */
128 mpz_cdiv_q(t, r1, r2);
129
130 retry:
131 /* p = t p2 - y = t - 1 */
132 mpz_sub_ui(p, t, 1);
133
134 /* p = 2(tp2-y)p0p1 */
135 mpz_mul(p, p, p0);
136 mpz_mul_2exp(p, p, 1);
137
138 /* p = 2(tp2-y)p0p1 + 1*/
139 mpz_add_ui(p, p, 1);
140
141 mpz_set_ui(r2, 1);
142 mpz_mul_2exp(r2, r2, bits);
143
144 if (mpz_cmp(p, r2) > 0) {
145 /* t = (2 y p0 p1) + sqrt(2)*2^(bits-1) / (2p0p1p2) */
146 mpz_set(r1, p0);
147 /* r1 = (2 y p0 p1) */
148 mpz_mul_2exp(r1, r1, 1);
149
150 /* sq = sqrt(2)*2^(bits-1) */
151
152 /* r1 = (2 y p0 p1) + sq */
153 mpz_add(r1, r1, sq);
154
155 /* r2 = 2 p0 p1 p2 */
156 mpz_mul_2exp(r2, p0, 1);
157
158 /* t = ((2 y p0 p1) + sq) / (2 p0 p1 p2) */
159 mpz_cdiv_q(t, r1, r2);
160 }
161
162 pcounter++;
163
164 /* r2 = p - 1 */
165 mpz_sub_ui(r2, p, 1);
166
167 /* r1 = GCD(p1, e) */
168 mpz_gcd(r1, e, r2);
169
170 if (mpz_cmp_ui(r1, 1) == 0) {
171 mpz_set_ui(x, 0); /* a = 0 */
172 if (iterations > 0) {
173 for (i = 0; i < iterations; i++) {
174 tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
175 if (tseed_length > sizeof(pseed))
176 goto fail;
177 nettle_mpz_get_str_256(tseed_length, pseed, s);
178
179 hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
180 tseed_length, pseed);
181 mpz_add_ui(s, s, 1);
182 }
183
184 nettle_mpz_set_str_256_u(x, storage_length, storage);
185 }
186
187 /* a = 2 + a mod p-3 */
188 mpz_sub_ui(r1, p, 3); /* p is too large to worry about negatives */
189 mpz_mod(x, x, r1);
190 mpz_add_ui(x, x, 2);
191
192 /* z = a^(2(tp2-y)p1) mod p */
193
194 /* r1 = (tp2-y) */
195 mpz_sub_ui(r1, t, 1);
196 /* r1 = 2(tp2-y)p1 */
197 mpz_mul_2exp(r1, r1, 1);
198
199 /* z = r2 = a^r1 mod p */
200 mpz_powm(r2, x, r1, p);
201
202 mpz_sub_ui(r1, r2, 1);
203 mpz_gcd(x, r1, p);
204
205 if (mpz_cmp_ui(x, 1) == 0) {
206 mpz_powm(r1, r2, p0, p);
207 if (mpz_cmp_ui(r1, 1) == 0) {
208 if (prime_seed_length != NULL) {
209 tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
210 if (tseed_length > sizeof(pseed))
211 goto fail;
212
213 nettle_mpz_get_str_256(tseed_length, pseed, s);
214
215 if (*prime_seed_length < tseed_length) {
216 *prime_seed_length = tseed_length;
217 goto fail;
218 }
219 *prime_seed_length = tseed_length;
220 if (prime_seed != NULL)
221 memcpy(prime_seed, pseed, tseed_length);
222 }
223 ret = 1;
224 goto cleanup;
225 }
226 }
227 }
228
229 if (pcounter >= max) {
230 goto fail;
231 }
232
233 mpz_add_ui(t, t, 1);
234 goto retry;
235
236 fail:
237 ret = 0;
238 cleanup:
239 free(storage);
240 mpz_clear(p0);
241 mpz_clear(sq);
242 mpz_clear(r1);
243 mpz_clear(r2);
244 mpz_clear(x);
245 mpz_clear(t);
246 mpz_clear(s);
247
248 return ret;
249 }
250
251 /* This generates p,q params using the B.3.2.2 algorithm in FIPS 186-4.
252 *
253 * The hash function used is SHA384.
254 * The exponent e used is the value in pub->e.
255 */
256 int
_rsa_generate_fips186_4_keypair(struct rsa_public_key * pub,struct rsa_private_key * key,unsigned seed_length,uint8_t * seed,void * progress_ctx,nettle_progress_func * progress,unsigned n_size)257 _rsa_generate_fips186_4_keypair(struct rsa_public_key *pub,
258 struct rsa_private_key *key,
259 unsigned seed_length, uint8_t * seed,
260 void *progress_ctx,
261 nettle_progress_func * progress,
262 /* Desired size of modulo, in bits */
263 unsigned n_size)
264 {
265 mpz_t t, r, p1, q1, lcm;
266 int ret;
267 struct dss_params_validation_seeds cert;
268 unsigned l = n_size / 2;
269
270 FIPS_RULE(n_size == 2048 && seed_length != 14 * 2, 0, "seed length other than 28 bytes\n");
271 FIPS_RULE(n_size == 3072 && seed_length != 16 * 2, 0, "seed length other than 32 bytes\n");
272 FIPS_RULE(n_size != 2048 && n_size != 3072, 0, "unsupported size for modulus\n");
273
274 if (!mpz_tstbit(pub->e, 0)) {
275 _gnutls_debug_log("Unacceptable e (it is even)\n");
276 return 0;
277 }
278
279 if (mpz_cmp_ui(pub->e, 65536) <= 0) {
280 _gnutls_debug_log("Unacceptable e\n");
281 return 0;
282 }
283
284 mpz_init(p1);
285 mpz_init(q1);
286 mpz_init(lcm);
287 mpz_init(t);
288 mpz_init(r);
289
290 mpz_set_ui(t, 1);
291 mpz_mul_2exp(t, t, 256);
292
293 if (mpz_cmp(pub->e, t) >= 0) {
294 ret = 0;
295 goto cleanup;
296 }
297
298 cert.pseed_length = sizeof(cert.pseed);
299 ret = rsa_provable_prime(key->p, &cert.pseed_length, cert.pseed,
300 l, seed_length,
301 seed, pub->e, progress_ctx, progress);
302 if (ret == 0) {
303 goto cleanup;
304 }
305
306 mpz_set_ui(r, 1);
307 mpz_mul_2exp(r, r, (l) - 100);
308
309 do {
310 cert.qseed_length = sizeof(cert.qseed);
311 ret = rsa_provable_prime(key->q, &cert.qseed_length, cert.qseed,
312 l, cert.pseed_length, cert.pseed,
313 pub->e,
314 progress_ctx, progress);
315 if (ret == 0) {
316 goto cleanup;
317 }
318
319
320 cert.pseed_length = cert.qseed_length;
321 memcpy(cert.pseed, cert.qseed, cert.qseed_length);
322
323
324 if (mpz_cmp(key->p, key->q) > 0)
325 mpz_sub(t, key->p, key->q);
326 else
327 mpz_sub(t, key->q, key->p);
328 } while (mpz_cmp(t, r) <= 0);
329
330 memset(&cert, 0, sizeof(cert));
331
332 mpz_mul(pub->n, key->p, key->q);
333
334 if (mpz_sizeinbase(pub->n, 2) != n_size) {
335 ret = 0;
336 goto cleanup;
337 }
338
339 /* c = q^{-1} (mod p) */
340 if (mpz_invert(key->c, key->q, key->p) == 0) {
341 ret = 0;
342 goto cleanup;
343 }
344
345 mpz_sub_ui(p1, key->p, 1);
346 mpz_sub_ui(q1, key->q, 1);
347
348 mpz_lcm(lcm, p1, q1);
349
350 if (mpz_invert(key->d, pub->e, lcm) == 0) {
351 ret = 0;
352 goto cleanup;
353 }
354
355 /* check whether d > 2^(nlen/2) -- FIPS186-4 5.3.1 */
356 if (mpz_sizeinbase(key->d, 2) < n_size/2) {
357 ret = 0;
358 goto cleanup;
359 }
360
361 /* Done! Almost, we must compute the auxiliary private values. */
362 /* a = d % (p-1) */
363 mpz_fdiv_r(key->a, key->d, p1);
364
365 /* b = d % (q-1) */
366 mpz_fdiv_r(key->b, key->d, q1);
367
368 /* c was computed earlier */
369
370 pub->size = key->size = (n_size + 7) / 8;
371 if (pub->size < RSA_MINIMUM_N_OCTETS) {
372 ret = 0;
373 goto cleanup;
374 }
375
376 ret = 1;
377 cleanup:
378 mpz_clear(p1);
379 mpz_clear(q1);
380 mpz_clear(lcm);
381 mpz_clear(t);
382 mpz_clear(r);
383 return ret;
384 }
385
386 /* Not entirely accurate but a good precision
387 */
388 #define SEED_LENGTH(bits) (_gnutls_pk_bits_to_subgroup_bits(bits)/8)
389
390 /* This generates p,q params using the B.3.2.2 algorithm in FIPS 186-4.
391 *
392 * The hash function used is SHA384.
393 * The exponent e used is the value in pub->e.
394 */
395 int
rsa_generate_fips186_4_keypair(struct rsa_public_key * pub,struct rsa_private_key * key,void * random_ctx,nettle_random_func * random,void * progress_ctx,nettle_progress_func * progress,unsigned * rseed_size,void * rseed,unsigned n_size)396 rsa_generate_fips186_4_keypair(struct rsa_public_key *pub,
397 struct rsa_private_key *key,
398 void *random_ctx, nettle_random_func * random,
399 void *progress_ctx,
400 nettle_progress_func * progress,
401 unsigned *rseed_size,
402 void *rseed,
403 /* Desired size of modulo, in bits */
404 unsigned n_size)
405 {
406 uint8_t seed[128];
407 unsigned seed_length;
408 int ret;
409
410 FIPS_RULE(n_size != 2048 && n_size != 3072, 0, "size of prime of other than 2048 or 3072\n");
411
412 seed_length = SEED_LENGTH(n_size);
413 if (seed_length > sizeof(seed))
414 return 0;
415
416 random(random_ctx, seed_length, seed);
417
418 if (rseed && rseed_size) {
419 if (*rseed_size < seed_length) {
420 return 0;
421 }
422 memcpy(rseed, seed, seed_length);
423 *rseed_size = seed_length;
424 }
425
426 ret = _rsa_generate_fips186_4_keypair(pub, key, seed_length, seed,
427 progress_ctx, progress, n_size);
428 gnutls_memset(seed, 0, seed_length);
429 return ret;
430 }
431