]>
Commit | Line | Data |
---|---|---|
2039c421 | 1 | /* |
0d664759 | 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
0f113f3e | 3 | * |
2039c421 RS |
4 | * Licensed under the OpenSSL license (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy | |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
d02b48c6 RE |
8 | */ |
9 | ||
0f113f3e MC |
10 | /* |
11 | * NB: these functions have been "upgraded", the deprecated versions (which | |
12 | * are compatibility wrappers using these functions) are in rsa_depr.c. - | |
13 | * Geoff | |
e9224c71 GT |
14 | */ |
15 | ||
d02b48c6 RE |
16 | #include <stdio.h> |
17 | #include <time.h> | |
b39fc560 | 18 | #include "internal/cryptlib.h" |
ec577822 | 19 | #include <openssl/bn.h> |
9862e9aa | 20 | #include "rsa_locl.h" |
d02b48c6 | 21 | |
665d899f | 22 | static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value, |
0f113f3e | 23 | BN_GENCB *cb); |
2814c629 | 24 | |
0f113f3e MC |
25 | /* |
26 | * NB: this wrapper would normally be placed in rsa_lib.c and the static | |
27 | * implementation would probably be in rsa_eay.c. Nonetheless, is kept here | |
28 | * so that we don't introduce a new linker dependency. Eg. any application | |
29 | * that wasn't previously linking object code related to key-generation won't | |
30 | * have to now just because key-generation is part of RSA_METHOD. | |
31 | */ | |
bcfea9fb | 32 | int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) |
0f113f3e | 33 | { |
665d899f | 34 | if (rsa->meth->rsa_keygen != NULL) |
0f113f3e | 35 | return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); |
665d899f PY |
36 | |
37 | return RSA_generate_multi_prime_key(rsa, bits, RSA_DEFAULT_PRIME_NUM, | |
38 | e_value, cb); | |
0f113f3e MC |
39 | } |
40 | ||
665d899f PY |
41 | int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes, |
42 | BIGNUM *e_value, BN_GENCB *cb) | |
43 | { | |
44 | /* multi-prime is only supported with the builtin key generation */ | |
e44480cc | 45 | if (rsa->meth->rsa_multi_prime_keygen != NULL) { |
665d899f PY |
46 | return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes, |
47 | e_value, cb); | |
e44480cc AP |
48 | } else if (rsa->meth->rsa_keygen != NULL) { |
49 | /* | |
50 | * However, if rsa->meth implements only rsa_keygen, then we | |
51 | * have to honour it in 2-prime case and assume that it wouldn't | |
52 | * know what to do with multi-prime key generated by builtin | |
53 | * subroutine... | |
54 | */ | |
55 | if (primes == 2) | |
56 | return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); | |
57 | else | |
58 | return 0; | |
59 | } | |
60 | ||
665d899f PY |
61 | return rsa_builtin_keygen(rsa, bits, primes, e_value, cb); |
62 | } | |
63 | ||
64 | static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value, | |
0f113f3e MC |
65 | BN_GENCB *cb) |
66 | { | |
665d899f PY |
67 | BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime; |
68 | int ok = -1, n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0; | |
69 | int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0; | |
70 | RSA_PRIME_INFO *pinfo = NULL; | |
71 | STACK_OF(RSA_PRIME_INFO) *prime_infos = NULL; | |
0f113f3e | 72 | BN_CTX *ctx = NULL; |
665d899f | 73 | BN_ULONG bitst = 0; |
8db7946e | 74 | unsigned long error = 0; |
665d899f | 75 | |
cac19d19 | 76 | if (bits < RSA_MIN_MODULUS_BITS) { |
69795831 RS |
77 | ok = 0; /* we set our own err */ |
78 | RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_SIZE_TOO_SMALL); | |
79 | goto err; | |
80 | } | |
81 | ||
3bded9cd AP |
82 | if (primes < RSA_DEFAULT_PRIME_NUM || primes > rsa_multip_cap(bits)) { |
83 | ok = 0; /* we set our own err */ | |
665d899f PY |
84 | RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_PRIME_NUM_INVALID); |
85 | goto err; | |
86 | } | |
87 | ||
0f113f3e MC |
88 | ctx = BN_CTX_new(); |
89 | if (ctx == NULL) | |
90 | goto err; | |
91 | BN_CTX_start(ctx); | |
92 | r0 = BN_CTX_get(ctx); | |
93 | r1 = BN_CTX_get(ctx); | |
94 | r2 = BN_CTX_get(ctx); | |
665d899f PY |
95 | if (r2 == NULL) |
96 | goto err; | |
97 | ||
98 | /* divide bits into 'primes' pieces evenly */ | |
99 | quo = bits / primes; | |
100 | rmd = bits % primes; | |
101 | ||
665d899f PY |
102 | for (i = 0; i < primes; i++) |
103 | bitsr[i] = (i < rmd) ? quo + 1 : quo; | |
0f113f3e MC |
104 | |
105 | /* We need the RSA components non-NULL */ | |
106 | if (!rsa->n && ((rsa->n = BN_new()) == NULL)) | |
107 | goto err; | |
74924dcb | 108 | if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL)) |
0f113f3e MC |
109 | goto err; |
110 | if (!rsa->e && ((rsa->e = BN_new()) == NULL)) | |
111 | goto err; | |
74924dcb | 112 | if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL)) |
0f113f3e | 113 | goto err; |
74924dcb | 114 | if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL)) |
0f113f3e | 115 | goto err; |
74924dcb | 116 | if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL)) |
0f113f3e | 117 | goto err; |
74924dcb | 118 | if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL)) |
0f113f3e | 119 | goto err; |
74924dcb | 120 | if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL)) |
0f113f3e MC |
121 | goto err; |
122 | ||
665d899f PY |
123 | /* initialize multi-prime components */ |
124 | if (primes > RSA_DEFAULT_PRIME_NUM) { | |
125 | rsa->version = RSA_ASN1_VERSION_MULTI; | |
126 | prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, primes - 2); | |
127 | if (prime_infos == NULL) | |
128 | goto err; | |
129 | if (rsa->prime_infos != NULL) { | |
130 | /* could this happen? */ | |
131 | sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos, rsa_multip_info_free); | |
132 | } | |
133 | rsa->prime_infos = prime_infos; | |
134 | ||
135 | /* prime_info from 2 to |primes| -1 */ | |
136 | for (i = 2; i < primes; i++) { | |
137 | pinfo = rsa_multip_info_new(); | |
138 | if (pinfo == NULL) | |
139 | goto err; | |
140 | (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo); | |
141 | } | |
142 | } | |
143 | ||
78e09b53 RS |
144 | if (BN_copy(rsa->e, e_value) == NULL) |
145 | goto err; | |
0f113f3e | 146 | |
665d899f PY |
147 | /* generate p, q and other primes (if any) */ |
148 | for (i = 0; i < primes; i++) { | |
149 | adj = 0; | |
150 | retries = 0; | |
151 | ||
152 | if (i == 0) { | |
153 | prime = rsa->p; | |
154 | } else if (i == 1) { | |
155 | prime = rsa->q; | |
156 | } else { | |
157 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
158 | prime = pinfo->r; | |
159 | } | |
160 | ||
161 | for (;;) { | |
162 | redo: | |
163 | if (!BN_generate_prime_ex(prime, bitsr[i] + adj, 0, NULL, NULL, cb)) | |
164 | goto err; | |
165 | /* | |
166 | * prime should not be equal to p, q, r_3... | |
167 | * (those primes prior to this one) | |
168 | */ | |
169 | { | |
170 | int j; | |
171 | ||
172 | for (j = 0; j < i; j++) { | |
173 | BIGNUM *prev_prime; | |
174 | ||
175 | if (j == 0) | |
176 | prev_prime = rsa->p; | |
177 | else if (j == 1) | |
178 | prev_prime = rsa->q; | |
179 | else | |
180 | prev_prime = sk_RSA_PRIME_INFO_value(prime_infos, | |
181 | j - 2)->r; | |
182 | ||
183 | if (!BN_cmp(prime, prev_prime)) { | |
184 | goto redo; | |
185 | } | |
186 | } | |
187 | } | |
188 | if (!BN_sub(r2, prime, BN_value_one())) | |
189 | goto err; | |
8db7946e SW |
190 | ERR_set_mark(); |
191 | BN_set_flags(r2, BN_FLG_CONSTTIME); | |
192 | if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) { | |
193 | /* GCD == 1 since inverse exists */ | |
665d899f | 194 | break; |
8db7946e SW |
195 | } |
196 | error = ERR_peek_last_error(); | |
197 | if (ERR_GET_LIB(error) == ERR_LIB_BN | |
198 | && ERR_GET_REASON(error) == BN_R_NO_INVERSE) { | |
199 | /* GCD != 1 */ | |
200 | ERR_pop_to_mark(); | |
201 | } else { | |
202 | goto err; | |
203 | } | |
665d899f PY |
204 | if (!BN_GENCB_call(cb, 2, n++)) |
205 | goto err; | |
206 | } | |
207 | ||
208 | bitse += bitsr[i]; | |
209 | ||
210 | /* calculate n immediately to see if it's sufficient */ | |
211 | if (i == 1) { | |
212 | /* we get at least 2 primes */ | |
213 | if (!BN_mul(r1, rsa->p, rsa->q, ctx)) | |
214 | goto err; | |
215 | } else if (i != 0) { | |
216 | /* modulus n = p * q * r_3 * r_4 ... */ | |
217 | if (!BN_mul(r1, rsa->n, prime, ctx)) | |
218 | goto err; | |
219 | } else { | |
220 | /* i == 0, do nothing */ | |
221 | if (!BN_GENCB_call(cb, 3, i)) | |
222 | goto err; | |
223 | continue; | |
224 | } | |
225 | /* | |
226 | * if |r1|, product of factors so far, is not as long as expected | |
227 | * (by checking the first 4 bits are less than 0x9 or greater than | |
228 | * 0xF). If so, re-generate the last prime. | |
229 | * | |
230 | * NOTE: This actually can't happen in two-prime case, because of | |
231 | * the way factors are generated. | |
232 | * | |
233 | * Besides, another consideration is, for multi-prime case, even the | |
234 | * length modulus is as long as expected, the modulus could start at | |
235 | * 0x8, which could be utilized to distinguish a multi-prime private | |
236 | * key by using the modulus in a certificate. This is also covered | |
237 | * by checking the length should not be less than 0x9. | |
238 | */ | |
239 | if (!BN_rshift(r2, r1, bitse - 4)) | |
0f113f3e | 240 | goto err; |
665d899f PY |
241 | bitst = BN_get_word(r2); |
242 | ||
243 | if (bitst < 0x9 || bitst > 0xF) { | |
244 | /* | |
245 | * For keys with more than 4 primes, we attempt longer factor to | |
246 | * meet length requirement. | |
247 | * | |
248 | * Otherwise, we just re-generate the prime with the same length. | |
249 | * | |
250 | * This strategy has the following goals: | |
251 | * | |
252 | * 1. 1024-bit factors are effcient when using 3072 and 4096-bit key | |
253 | * 2. stay the same logic with normal 2-prime key | |
254 | */ | |
255 | bitse -= bitsr[i]; | |
256 | if (!BN_GENCB_call(cb, 2, n++)) | |
0f113f3e | 257 | goto err; |
665d899f PY |
258 | if (primes > 4) { |
259 | if (bitst < 0x9) | |
260 | adj++; | |
261 | else | |
262 | adj--; | |
263 | } else if (retries == 4) { | |
264 | /* | |
265 | * re-generate all primes from scratch, mainly used | |
266 | * in 4 prime case to avoid long loop. Max retry times | |
267 | * is set to 4. | |
268 | */ | |
269 | i = -1; | |
270 | bitse = 0; | |
271 | continue; | |
272 | } | |
273 | retries++; | |
274 | goto redo; | |
275 | } | |
276 | /* save product of primes for further use, for multi-prime only */ | |
277 | if (i > 1 && BN_copy(pinfo->pp, rsa->n) == NULL) | |
0f113f3e | 278 | goto err; |
665d899f | 279 | if (BN_copy(rsa->n, r1) == NULL) |
0f113f3e | 280 | goto err; |
665d899f | 281 | if (!BN_GENCB_call(cb, 3, i)) |
0f113f3e MC |
282 | goto err; |
283 | } | |
665d899f | 284 | |
0f113f3e MC |
285 | if (BN_cmp(rsa->p, rsa->q) < 0) { |
286 | tmp = rsa->p; | |
287 | rsa->p = rsa->q; | |
288 | rsa->q = tmp; | |
289 | } | |
290 | ||
0f113f3e | 291 | /* calculate d */ |
665d899f PY |
292 | |
293 | /* p - 1 */ | |
0f113f3e | 294 | if (!BN_sub(r1, rsa->p, BN_value_one())) |
665d899f PY |
295 | goto err; |
296 | /* q - 1 */ | |
0f113f3e | 297 | if (!BN_sub(r2, rsa->q, BN_value_one())) |
665d899f PY |
298 | goto err; |
299 | /* (p - 1)(q - 1) */ | |
0f113f3e | 300 | if (!BN_mul(r0, r1, r2, ctx)) |
665d899f PY |
301 | goto err; |
302 | /* multi-prime */ | |
303 | for (i = 2; i < primes; i++) { | |
304 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
305 | /* save r_i - 1 to pinfo->d temporarily */ | |
306 | if (!BN_sub(pinfo->d, pinfo->r, BN_value_one())) | |
307 | goto err; | |
308 | if (!BN_mul(r0, r0, pinfo->d, ctx)) | |
309 | goto err; | |
310 | } | |
311 | ||
fd7d2520 | 312 | { |
5584f65a MC |
313 | BIGNUM *pr0 = BN_new(); |
314 | ||
315 | if (pr0 == NULL) | |
316 | goto err; | |
665d899f | 317 | |
5584f65a | 318 | BN_with_flags(pr0, r0, BN_FLG_CONSTTIME); |
fd7d2520 | 319 | if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) { |
5584f65a | 320 | BN_free(pr0); |
fd7d2520 MC |
321 | goto err; /* d */ |
322 | } | |
5584f65a MC |
323 | /* We MUST free pr0 before any further use of r0 */ |
324 | BN_free(pr0); | |
fd7d2520 | 325 | } |
0f113f3e | 326 | |
fd7d2520 | 327 | { |
5584f65a MC |
328 | BIGNUM *d = BN_new(); |
329 | ||
330 | if (d == NULL) | |
331 | goto err; | |
665d899f | 332 | |
5584f65a | 333 | BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); |
0f113f3e | 334 | |
665d899f PY |
335 | /* calculate d mod (p-1) and d mod (q - 1) */ |
336 | if (!BN_mod(rsa->dmp1, d, r1, ctx) | |
fd7d2520 | 337 | || !BN_mod(rsa->dmq1, d, r2, ctx)) { |
5584f65a | 338 | BN_free(d); |
fd7d2520 MC |
339 | goto err; |
340 | } | |
665d899f PY |
341 | |
342 | /* calculate CRT exponents */ | |
343 | for (i = 2; i < primes; i++) { | |
344 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
345 | /* pinfo->d == r_i - 1 */ | |
346 | if (!BN_mod(pinfo->d, d, pinfo->d, ctx)) { | |
347 | BN_free(d); | |
348 | goto err; | |
349 | } | |
350 | } | |
351 | ||
5584f65a MC |
352 | /* We MUST free d before any further use of rsa->d */ |
353 | BN_free(d); | |
fd7d2520 MC |
354 | } |
355 | ||
356 | { | |
5584f65a MC |
357 | BIGNUM *p = BN_new(); |
358 | ||
359 | if (p == NULL) | |
360 | goto err; | |
361 | BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); | |
fd7d2520 MC |
362 | |
363 | /* calculate inverse of q mod p */ | |
fd7d2520 | 364 | if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) { |
5584f65a | 365 | BN_free(p); |
fd7d2520 MC |
366 | goto err; |
367 | } | |
665d899f PY |
368 | |
369 | /* calculate CRT coefficient for other primes */ | |
370 | for (i = 2; i < primes; i++) { | |
371 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
372 | BN_with_flags(p, pinfo->r, BN_FLG_CONSTTIME); | |
373 | if (!BN_mod_inverse(pinfo->t, pinfo->pp, p, ctx)) { | |
374 | BN_free(p); | |
375 | goto err; | |
376 | } | |
377 | } | |
378 | ||
5584f65a MC |
379 | /* We MUST free p before any further use of rsa->p */ |
380 | BN_free(p); | |
fd7d2520 | 381 | } |
0f113f3e MC |
382 | |
383 | ok = 1; | |
384 | err: | |
0f113f3e MC |
385 | if (ok == -1) { |
386 | RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN); | |
387 | ok = 0; | |
388 | } | |
23a1d5e9 | 389 | if (ctx != NULL) |
0f113f3e | 390 | BN_CTX_end(ctx); |
23a1d5e9 | 391 | BN_CTX_free(ctx); |
0f113f3e MC |
392 | return ok; |
393 | } |