Line data Source code
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
41 14 : 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 14 : mpz_t x, t, s, r1, r2, p0, sq;
49 14 : int ret;
50 14 : unsigned pcounter = 0;
51 14 : unsigned iterations;
52 14 : unsigned storage_length = 0, i;
53 14 : uint8_t *storage = NULL;
54 14 : uint8_t pseed[MAX_PVP_SEED_SIZE+1];
55 14 : unsigned pseed_length = sizeof(pseed), tseed_length;
56 14 : unsigned max = bits*5;
57 :
58 14 : mpz_init(p0);
59 14 : mpz_init(sq);
60 14 : mpz_init(x);
61 14 : mpz_init(t);
62 14 : mpz_init(s);
63 14 : mpz_init(r1);
64 14 : mpz_init(r2);
65 :
66 : /* p1 = p2 = 1 */
67 :
68 28 : ret = st_provable_prime(p0, &pseed_length, pseed,
69 14 : NULL, 1+div_ceil(bits,2), seed_length,
70 : seed, progress_ctx, progress);
71 14 : if (ret == 0) {
72 0 : goto cleanup;
73 : }
74 :
75 14 : iterations = div_ceil(bits, DIGEST_SIZE*8);
76 14 : mpz_set_ui(x, 0);
77 :
78 14 : if (iterations > 0) {
79 14 : storage_length = iterations * DIGEST_SIZE;
80 14 : storage = malloc(storage_length);
81 14 : if (storage == NULL) {
82 0 : goto fail;
83 : }
84 :
85 14 : nettle_mpz_set_str_256_u(s, pseed_length, pseed);
86 74 : for (i = 0; i < iterations; i++) {
87 46 : tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
88 46 : if (tseed_length > sizeof(pseed))
89 0 : goto fail;
90 46 : nettle_mpz_get_str_256(tseed_length, pseed, s);
91 :
92 46 : hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
93 : tseed_length, pseed);
94 46 : mpz_add_ui(s, s, 1);
95 : }
96 :
97 14 : 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 14 : mpz_set_ui(r1, 1);
104 14 : mpz_mul_2exp(r1, r1, 2*bits-1);
105 14 : mpz_sqrt(sq, r1);
106 :
107 : /* r2 = 2^bits - sq */
108 14 : mpz_set_ui(r2, 1);
109 14 : mpz_mul_2exp(r2, r2, bits);
110 14 : mpz_sub(r2, r2, sq);
111 :
112 : /* x = sqrt(2)*2^(bits-1) + (x mod (2^L - sqrt(2)*2^(bits-1)) */
113 14 : mpz_mod(x, x, r2);
114 14 : mpz_add(x, x, sq);
115 :
116 : /* y = p2 = p1 = 1 */
117 :
118 : /* r1 = (2 y p0 p1) */
119 14 : mpz_mul_2exp(r1, p0, 1);
120 :
121 : /* r2 = 2 p0 p1 p2 (p2=y=1) */
122 14 : mpz_set(r2, r1);
123 :
124 : /* r1 = (2 y p0 p1) + x */
125 14 : mpz_add(r1, r1, x);
126 :
127 : /* t = ((2 y p0 p1) + x) / (2 p0 p1 p2) */
128 14 : mpz_cdiv_q(t, r1, r2);
129 :
130 5265 : retry:
131 : /* p = t p2 - y = t - 1 */
132 5265 : mpz_sub_ui(p, t, 1);
133 :
134 : /* p = 2(tp2-y)p0p1 */
135 5265 : mpz_mul(p, p, p0);
136 5265 : mpz_mul_2exp(p, p, 1);
137 :
138 : /* p = 2(tp2-y)p0p1 + 1*/
139 5265 : mpz_add_ui(p, p, 1);
140 :
141 5265 : mpz_set_ui(r2, 1);
142 5265 : mpz_mul_2exp(r2, r2, bits);
143 :
144 5265 : if (mpz_cmp(p, r2) > 0) {
145 : /* t = (2 y p0 p1) + sqrt(2)*2^(bits-1) / (2p0p1p2) */
146 0 : mpz_set(r1, p0);
147 : /* r1 = (2 y p0 p1) */
148 0 : mpz_mul_2exp(r1, r1, 1);
149 :
150 : /* sq = sqrt(2)*2^(bits-1) */
151 :
152 : /* r1 = (2 y p0 p1) + sq */
153 0 : mpz_add(r1, r1, sq);
154 :
155 : /* r2 = 2 p0 p1 p2 */
156 0 : mpz_mul_2exp(r2, p0, 1);
157 :
158 : /* t = ((2 y p0 p1) + sq) / (2 p0 p1 p2) */
159 0 : mpz_cdiv_q(t, r1, r2);
160 : }
161 :
162 5265 : pcounter++;
163 :
164 : /* r2 = p - 1 */
165 5265 : mpz_sub_ui(r2, p, 1);
166 :
167 : /* r1 = GCD(p1, e) */
168 5265 : mpz_gcd(r1, e, r2);
169 :
170 5265 : if (mpz_cmp_ui(r1, 1) == 0) {
171 5265 : mpz_set_ui(x, 0); /* a = 0 */
172 5265 : if (iterations > 0) {
173 22564 : for (i = 0; i < iterations; i++) {
174 17299 : tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
175 17299 : if (tseed_length > sizeof(pseed))
176 0 : goto fail;
177 17299 : nettle_mpz_get_str_256(tseed_length, pseed, s);
178 :
179 17299 : hash(&storage[(iterations - i - 1) * DIGEST_SIZE],
180 : tseed_length, pseed);
181 17299 : mpz_add_ui(s, s, 1);
182 : }
183 :
184 5265 : nettle_mpz_set_str_256_u(x, storage_length, storage);
185 : }
186 :
187 : /* a = 2 + a mod p-3 */
188 5265 : mpz_sub_ui(r1, p, 3); /* p is too large to worry about negatives */
189 5265 : mpz_mod(x, x, r1);
190 5265 : mpz_add_ui(x, x, 2);
191 :
192 : /* z = a^(2(tp2-y)p1) mod p */
193 :
194 : /* r1 = (tp2-y) */
195 5265 : mpz_sub_ui(r1, t, 1);
196 : /* r1 = 2(tp2-y)p1 */
197 5265 : mpz_mul_2exp(r1, r1, 1);
198 :
199 : /* z = r2 = a^r1 mod p */
200 5265 : mpz_powm(r2, x, r1, p);
201 :
202 5265 : mpz_sub_ui(r1, r2, 1);
203 5265 : mpz_gcd(x, r1, p);
204 :
205 5265 : if (mpz_cmp_ui(x, 1) == 0) {
206 2832 : mpz_powm(r1, r2, p0, p);
207 2832 : if (mpz_cmp_ui(r1, 1) == 0) {
208 14 : if (prime_seed_length != NULL) {
209 14 : tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
210 14 : if (tseed_length > sizeof(pseed))
211 0 : goto fail;
212 :
213 14 : nettle_mpz_get_str_256(tseed_length, pseed, s);
214 :
215 14 : if (*prime_seed_length < tseed_length) {
216 0 : *prime_seed_length = tseed_length;
217 0 : goto fail;
218 : }
219 14 : *prime_seed_length = tseed_length;
220 14 : if (prime_seed != NULL)
221 14 : memcpy(prime_seed, pseed, tseed_length);
222 : }
223 14 : ret = 1;
224 14 : goto cleanup;
225 : }
226 : }
227 : }
228 :
229 5251 : if (pcounter >= max) {
230 0 : goto fail;
231 : }
232 :
233 5251 : mpz_add_ui(t, t, 1);
234 5251 : goto retry;
235 :
236 : fail:
237 : ret = 0;
238 14 : cleanup:
239 14 : free(storage);
240 14 : mpz_clear(p0);
241 14 : mpz_clear(sq);
242 14 : mpz_clear(r1);
243 14 : mpz_clear(r2);
244 14 : mpz_clear(x);
245 14 : mpz_clear(t);
246 14 : mpz_clear(s);
247 :
248 14 : 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
257 7 : _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 7 : mpz_t t, r, p1, q1, lcm;
266 7 : int ret;
267 7 : struct dss_params_validation_seeds cert;
268 7 : unsigned l = n_size / 2;
269 :
270 7 : FIPS_RULE(n_size == 2048 && seed_length != 14 * 2, 0, "seed length other than 28 bytes\n");
271 7 : FIPS_RULE(n_size == 3072 && seed_length != 16 * 2, 0, "seed length other than 32 bytes\n");
272 7 : FIPS_RULE(n_size != 2048 && n_size != 3072, 0, "unsupported size for modulus\n");
273 :
274 7 : if (!mpz_tstbit(pub->e, 0)) {
275 0 : _gnutls_debug_log("Unacceptable e (it is even)\n");
276 0 : return 0;
277 : }
278 :
279 7 : if (mpz_cmp_ui(pub->e, 65536) <= 0) {
280 0 : _gnutls_debug_log("Unacceptable e\n");
281 0 : return 0;
282 : }
283 :
284 7 : mpz_init(p1);
285 7 : mpz_init(q1);
286 7 : mpz_init(lcm);
287 7 : mpz_init(t);
288 7 : mpz_init(r);
289 :
290 7 : mpz_set_ui(t, 1);
291 7 : mpz_mul_2exp(t, t, 256);
292 :
293 7 : if (mpz_cmp(pub->e, t) >= 0) {
294 0 : ret = 0;
295 0 : goto cleanup;
296 : }
297 :
298 7 : cert.pseed_length = sizeof(cert.pseed);
299 7 : ret = rsa_provable_prime(key->p, &cert.pseed_length, cert.pseed,
300 : l, seed_length,
301 : seed, pub->e, progress_ctx, progress);
302 7 : if (ret == 0) {
303 0 : goto cleanup;
304 : }
305 :
306 7 : mpz_set_ui(r, 1);
307 7 : mpz_mul_2exp(r, r, (l) - 100);
308 :
309 7 : do {
310 7 : cert.qseed_length = sizeof(cert.qseed);
311 7 : 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 7 : if (ret == 0) {
316 0 : goto cleanup;
317 : }
318 :
319 :
320 7 : cert.pseed_length = cert.qseed_length;
321 7 : memcpy(cert.pseed, cert.qseed, cert.qseed_length);
322 :
323 :
324 7 : if (mpz_cmp(key->p, key->q) > 0)
325 2 : mpz_sub(t, key->p, key->q);
326 : else
327 5 : mpz_sub(t, key->q, key->p);
328 7 : } while (mpz_cmp(t, r) <= 0);
329 :
330 7 : memset(&cert, 0, sizeof(cert));
331 :
332 7 : mpz_mul(pub->n, key->p, key->q);
333 :
334 7 : if (mpz_sizeinbase(pub->n, 2) != n_size) {
335 0 : ret = 0;
336 0 : goto cleanup;
337 : }
338 :
339 : /* c = q^{-1} (mod p) */
340 7 : if (mpz_invert(key->c, key->q, key->p) == 0) {
341 0 : ret = 0;
342 0 : goto cleanup;
343 : }
344 :
345 7 : mpz_sub_ui(p1, key->p, 1);
346 7 : mpz_sub_ui(q1, key->q, 1);
347 :
348 7 : mpz_lcm(lcm, p1, q1);
349 :
350 7 : if (mpz_invert(key->d, pub->e, lcm) == 0) {
351 0 : ret = 0;
352 0 : goto cleanup;
353 : }
354 :
355 : /* check whether d > 2^(nlen/2) -- FIPS186-4 5.3.1 */
356 7 : if (mpz_sizeinbase(key->d, 2) < n_size/2) {
357 0 : ret = 0;
358 0 : goto cleanup;
359 : }
360 :
361 : /* Done! Almost, we must compute the auxiliary private values. */
362 : /* a = d % (p-1) */
363 7 : mpz_fdiv_r(key->a, key->d, p1);
364 :
365 : /* b = d % (q-1) */
366 7 : mpz_fdiv_r(key->b, key->d, q1);
367 :
368 : /* c was computed earlier */
369 :
370 7 : pub->size = key->size = (n_size + 7) / 8;
371 7 : if (pub->size < RSA_MINIMUM_N_OCTETS) {
372 0 : ret = 0;
373 0 : goto cleanup;
374 : }
375 :
376 : ret = 1;
377 7 : cleanup:
378 7 : mpz_clear(p1);
379 7 : mpz_clear(q1);
380 7 : mpz_clear(lcm);
381 7 : mpz_clear(t);
382 7 : mpz_clear(r);
383 7 : 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
396 0 : 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 0 : uint8_t seed[128];
407 0 : unsigned seed_length;
408 0 : int ret;
409 :
410 0 : FIPS_RULE(n_size != 2048 && n_size != 3072, 0, "size of prime of other than 2048 or 3072\n");
411 :
412 0 : seed_length = SEED_LENGTH(n_size);
413 0 : if (seed_length > sizeof(seed))
414 : return 0;
415 :
416 0 : random(random_ctx, seed_length, seed);
417 :
418 0 : if (rseed && rseed_size) {
419 0 : if (*rseed_size < seed_length) {
420 : return 0;
421 : }
422 0 : memcpy(rseed, seed, seed_length);
423 0 : *rseed_size = seed_length;
424 : }
425 :
426 0 : ret = _rsa_generate_fips186_4_keypair(pub, key, seed_length, seed,
427 : progress_ctx, progress, n_size);
428 0 : gnutls_memset(seed, 0, seed_length);
429 0 : return ret;
430 : }
|
