1 /* 2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. 3 * 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 8 */ 9 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 14 */ 15 16 #include <stdio.h> 17 #include <time.h> 18 #include "internal/cryptlib.h" 19 #include <openssl/bn.h> 20 #include "rsa_locl.h" 21 22 static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value, 23 BN_GENCB *cb); 24 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 */ 32 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) 33 { 34 if (rsa->meth->rsa_keygen != NULL) 35 return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); 36 37 return RSA_generate_multi_prime_key(rsa, bits, RSA_DEFAULT_PRIME_NUM, 38 e_value, cb); 39 } 40 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 */ 45 if (rsa->meth->rsa_multi_prime_keygen != NULL) { 46 return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes, 47 e_value, cb); 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 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, 65 BN_GENCB *cb) 66 { 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; 72 BN_CTX *ctx = NULL; 73 BN_ULONG bitst = 0; 74 unsigned long error = 0; 75 76 if (bits < RSA_MIN_MODULUS_BITS) { 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 82 if (primes < RSA_DEFAULT_PRIME_NUM || primes > rsa_multip_cap(bits)) { 83 ok = 0; /* we set our own err */ 84 RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_PRIME_NUM_INVALID); 85 goto err; 86 } 87 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); 95 if (r2 == NULL) 96 goto err; 97 98 /* divide bits into 'primes' pieces evenly */ 99 quo = bits / primes; 100 rmd = bits % primes; 101 102 for (i = 0; i < primes; i++) 103 bitsr[i] = (i < rmd) ? quo + 1 : quo; 104 105 /* We need the RSA components non-NULL */ 106 if (!rsa->n && ((rsa->n = BN_new()) == NULL)) 107 goto err; 108 if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL)) 109 goto err; 110 if (!rsa->e && ((rsa->e = BN_new()) == NULL)) 111 goto err; 112 if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL)) 113 goto err; 114 if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL)) 115 goto err; 116 if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL)) 117 goto err; 118 if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL)) 119 goto err; 120 if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL)) 121 goto err; 122 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 144 if (BN_copy(rsa->e, e_value) == NULL) 145 goto err; 146 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 BN_set_flags(prime, BN_FLG_CONSTTIME); 161 162 for (;;) { 163 redo: 164 if (!BN_generate_prime_ex(prime, bitsr[i] + adj, 0, NULL, NULL, cb)) 165 goto err; 166 /* 167 * prime should not be equal to p, q, r_3... 168 * (those primes prior to this one) 169 */ 170 { 171 int j; 172 173 for (j = 0; j < i; j++) { 174 BIGNUM *prev_prime; 175 176 if (j == 0) 177 prev_prime = rsa->p; 178 else if (j == 1) 179 prev_prime = rsa->q; 180 else 181 prev_prime = sk_RSA_PRIME_INFO_value(prime_infos, 182 j - 2)->r; 183 184 if (!BN_cmp(prime, prev_prime)) { 185 goto redo; 186 } 187 } 188 } 189 if (!BN_sub(r2, prime, BN_value_one())) 190 goto err; 191 ERR_set_mark(); 192 BN_set_flags(r2, BN_FLG_CONSTTIME); 193 if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) { 194 /* GCD == 1 since inverse exists */ 195 break; 196 } 197 error = ERR_peek_last_error(); 198 if (ERR_GET_LIB(error) == ERR_LIB_BN 199 && ERR_GET_REASON(error) == BN_R_NO_INVERSE) { 200 /* GCD != 1 */ 201 ERR_pop_to_mark(); 202 } else { 203 goto err; 204 } 205 if (!BN_GENCB_call(cb, 2, n++)) 206 goto err; 207 } 208 209 bitse += bitsr[i]; 210 211 /* calculate n immediately to see if it's sufficient */ 212 if (i == 1) { 213 /* we get at least 2 primes */ 214 if (!BN_mul(r1, rsa->p, rsa->q, ctx)) 215 goto err; 216 } else if (i != 0) { 217 /* modulus n = p * q * r_3 * r_4 ... */ 218 if (!BN_mul(r1, rsa->n, prime, ctx)) 219 goto err; 220 } else { 221 /* i == 0, do nothing */ 222 if (!BN_GENCB_call(cb, 3, i)) 223 goto err; 224 continue; 225 } 226 /* 227 * if |r1|, product of factors so far, is not as long as expected 228 * (by checking the first 4 bits are less than 0x9 or greater than 229 * 0xF). If so, re-generate the last prime. 230 * 231 * NOTE: This actually can't happen in two-prime case, because of 232 * the way factors are generated. 233 * 234 * Besides, another consideration is, for multi-prime case, even the 235 * length modulus is as long as expected, the modulus could start at 236 * 0x8, which could be utilized to distinguish a multi-prime private 237 * key by using the modulus in a certificate. This is also covered 238 * by checking the length should not be less than 0x9. 239 */ 240 if (!BN_rshift(r2, r1, bitse - 4)) 241 goto err; 242 bitst = BN_get_word(r2); 243 244 if (bitst < 0x9 || bitst > 0xF) { 245 /* 246 * For keys with more than 4 primes, we attempt longer factor to 247 * meet length requirement. 248 * 249 * Otherwise, we just re-generate the prime with the same length. 250 * 251 * This strategy has the following goals: 252 * 253 * 1. 1024-bit factors are effcient when using 3072 and 4096-bit key 254 * 2. stay the same logic with normal 2-prime key 255 */ 256 bitse -= bitsr[i]; 257 if (!BN_GENCB_call(cb, 2, n++)) 258 goto err; 259 if (primes > 4) { 260 if (bitst < 0x9) 261 adj++; 262 else 263 adj--; 264 } else if (retries == 4) { 265 /* 266 * re-generate all primes from scratch, mainly used 267 * in 4 prime case to avoid long loop. Max retry times 268 * is set to 4. 269 */ 270 i = -1; 271 bitse = 0; 272 continue; 273 } 274 retries++; 275 goto redo; 276 } 277 /* save product of primes for further use, for multi-prime only */ 278 if (i > 1 && BN_copy(pinfo->pp, rsa->n) == NULL) 279 goto err; 280 if (BN_copy(rsa->n, r1) == NULL) 281 goto err; 282 if (!BN_GENCB_call(cb, 3, i)) 283 goto err; 284 } 285 286 if (BN_cmp(rsa->p, rsa->q) < 0) { 287 tmp = rsa->p; 288 rsa->p = rsa->q; 289 rsa->q = tmp; 290 } 291 292 /* calculate d */ 293 294 /* p - 1 */ 295 if (!BN_sub(r1, rsa->p, BN_value_one())) 296 goto err; 297 /* q - 1 */ 298 if (!BN_sub(r2, rsa->q, BN_value_one())) 299 goto err; 300 /* (p - 1)(q - 1) */ 301 if (!BN_mul(r0, r1, r2, ctx)) 302 goto err; 303 /* multi-prime */ 304 for (i = 2; i < primes; i++) { 305 pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); 306 /* save r_i - 1 to pinfo->d temporarily */ 307 if (!BN_sub(pinfo->d, pinfo->r, BN_value_one())) 308 goto err; 309 if (!BN_mul(r0, r0, pinfo->d, ctx)) 310 goto err; 311 } 312 313 { 314 BIGNUM *pr0 = BN_new(); 315 316 if (pr0 == NULL) 317 goto err; 318 319 BN_with_flags(pr0, r0, BN_FLG_CONSTTIME); 320 if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) { 321 BN_free(pr0); 322 goto err; /* d */ 323 } 324 /* We MUST free pr0 before any further use of r0 */ 325 BN_free(pr0); 326 } 327 328 { 329 BIGNUM *d = BN_new(); 330 331 if (d == NULL) 332 goto err; 333 334 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 335 336 /* calculate d mod (p-1) and d mod (q - 1) */ 337 if (!BN_mod(rsa->dmp1, d, r1, ctx) 338 || !BN_mod(rsa->dmq1, d, r2, ctx)) { 339 BN_free(d); 340 goto err; 341 } 342 343 /* calculate CRT exponents */ 344 for (i = 2; i < primes; i++) { 345 pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); 346 /* pinfo->d == r_i - 1 */ 347 if (!BN_mod(pinfo->d, d, pinfo->d, ctx)) { 348 BN_free(d); 349 goto err; 350 } 351 } 352 353 /* We MUST free d before any further use of rsa->d */ 354 BN_free(d); 355 } 356 357 { 358 BIGNUM *p = BN_new(); 359 360 if (p == NULL) 361 goto err; 362 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); 363 364 /* calculate inverse of q mod p */ 365 if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) { 366 BN_free(p); 367 goto err; 368 } 369 370 /* calculate CRT coefficient for other primes */ 371 for (i = 2; i < primes; i++) { 372 pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); 373 BN_with_flags(p, pinfo->r, BN_FLG_CONSTTIME); 374 if (!BN_mod_inverse(pinfo->t, pinfo->pp, p, ctx)) { 375 BN_free(p); 376 goto err; 377 } 378 } 379 380 /* We MUST free p before any further use of rsa->p */ 381 BN_free(p); 382 } 383 384 ok = 1; 385 err: 386 if (ok == -1) { 387 RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN); 388 ok = 0; 389 } 390 if (ctx != NULL) 391 BN_CTX_end(ctx); 392 BN_CTX_free(ctx); 393 return ok; 394 } 395