1 /* 2 * Copyright 2018-2023 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved. 4 * 5 * Licensed under the Apache License 2.0 (the "License"). You may not use 6 * this file except in compliance with the License. You can obtain a copy 7 * in the file LICENSE in the source distribution or at 8 * https://www.openssl.org/source/license.html 9 */ 10 11 #include <openssl/err.h> 12 #include <openssl/bn.h> 13 #include <openssl/core.h> 14 #include <openssl/evp.h> 15 #include <openssl/rand.h> 16 #include "crypto/bn.h" 17 #include "crypto/security_bits.h" 18 #include "rsa_local.h" 19 20 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048 21 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112 22 23 /* 24 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6 25 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable 26 * Primes". 27 * 28 * Params: 29 * rsa Object used to store primes p & q. 30 * test Object used for CAVS testing only.that contains.. 31 * p1, p2 The returned auxiliary primes for p. 32 * If NULL they are not returned. 33 * Xpout An optionally returned random number used during generation of p. 34 * Xp An optional passed in value (that is random number used during 35 * generation of p). 36 * Xp1, Xp2 Optionally passed in randomly generated numbers from which 37 * auxiliary primes p1 & p2 are calculated. If NULL these values 38 * are generated internally. 39 * q1, q2 The returned auxiliary primes for q. 40 * If NULL they are not returned. 41 * Xqout An optionally returned random number used during generation of q. 42 * Xq An optional passed in value (that is random number used during 43 * generation of q). 44 * Xq1, Xq2 Optionally passed in randomly generated numbers from which 45 * auxiliary primes q1 & q2 are calculated. If NULL these values 46 * are generated internally. 47 * nbits The key size in bits (The size of the modulus n). 48 * e The public exponent. 49 * ctx A BN_CTX object. 50 * cb An optional BIGNUM callback. 51 * Returns: 1 if successful, or 0 otherwise. 52 * Notes: 53 * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL. 54 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in. 55 * (Required for CAVS testing). 56 */ 57 int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, 58 int nbits, const BIGNUM *e, BN_CTX *ctx, 59 BN_GENCB *cb) 60 { 61 int ret = 0, ok; 62 /* Temp allocated BIGNUMS */ 63 BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL; 64 /* Intermediate BIGNUMS that can be returned for testing */ 65 BIGNUM *p1 = NULL, *p2 = NULL; 66 BIGNUM *q1 = NULL, *q2 = NULL; 67 /* Intermediate BIGNUMS that can be input for testing */ 68 BIGNUM *Xpout = NULL, *Xqout = NULL; 69 BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL; 70 BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL; 71 72 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) 73 if (test != NULL) { 74 Xp1 = test->Xp1; 75 Xp2 = test->Xp2; 76 Xq1 = test->Xq1; 77 Xq2 = test->Xq2; 78 Xp = test->Xp; 79 Xq = test->Xq; 80 p1 = test->p1; 81 p2 = test->p2; 82 q1 = test->q1; 83 q2 = test->q2; 84 } 85 #endif 86 87 /* (Step 1) Check key length 88 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA 89 * Signature Generation and Key Agree/Transport. 90 */ 91 if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) { 92 ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL); 93 return 0; 94 } 95 96 if (!ossl_rsa_check_public_exponent(e)) { 97 ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE); 98 return 0; 99 } 100 101 /* (Step 3) Determine strength and check rand generator strength is ok - 102 * this step is redundant because the generator always returns a higher 103 * strength than is required. 104 */ 105 106 BN_CTX_start(ctx); 107 tmp = BN_CTX_get(ctx); 108 Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx); 109 Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx); 110 if (tmp == NULL || Xpo == NULL || Xqo == NULL) 111 goto err; 112 BN_set_flags(Xpo, BN_FLG_CONSTTIME); 113 BN_set_flags(Xqo, BN_FLG_CONSTTIME); 114 115 if (rsa->p == NULL) 116 rsa->p = BN_secure_new(); 117 if (rsa->q == NULL) 118 rsa->q = BN_secure_new(); 119 if (rsa->p == NULL || rsa->q == NULL) 120 goto err; 121 BN_set_flags(rsa->p, BN_FLG_CONSTTIME); 122 BN_set_flags(rsa->q, BN_FLG_CONSTTIME); 123 124 /* (Step 4) Generate p, Xp */ 125 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2, 126 nbits, e, ctx, cb)) 127 goto err; 128 for(;;) { 129 /* (Step 5) Generate q, Xq*/ 130 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1, 131 Xq2, nbits, e, ctx, cb)) 132 goto err; 133 134 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */ 135 ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits); 136 if (ok < 0) 137 goto err; 138 if (ok == 0) 139 continue; 140 141 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */ 142 ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits); 143 if (ok < 0) 144 goto err; 145 if (ok == 0) 146 continue; 147 break; /* successfully finished */ 148 } 149 rsa->dirty_cnt++; 150 ret = 1; 151 err: 152 /* Zeroize any internally generated values that are not returned */ 153 if (Xpo != Xpout) 154 BN_clear(Xpo); 155 if (Xqo != Xqout) 156 BN_clear(Xqo); 157 BN_clear(tmp); 158 159 BN_CTX_end(ctx); 160 return ret; 161 } 162 163 /* 164 * Validates the RSA key size based on the target strength. 165 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b) 166 * 167 * Params: 168 * nbits The key size in bits. 169 * strength The target strength in bits. -1 means the target 170 * strength is unknown. 171 * Returns: 1 if the key size matches the target strength, or 0 otherwise. 172 */ 173 int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength) 174 { 175 int s = (int)ossl_ifc_ffc_compute_security_bits(nbits); 176 177 #ifdef FIPS_MODULE 178 if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) { 179 ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS); 180 return 0; 181 } 182 #endif 183 if (strength != -1 && s != strength) { 184 ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH); 185 return 0; 186 } 187 return 1; 188 } 189 190 /* 191 * Validate that the random bit generator is of sufficient strength to generate 192 * a key of the specified length. 193 */ 194 static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits) 195 { 196 if (rng == NULL) 197 return 0; 198 #ifdef FIPS_MODULE 199 /* 200 * This should become mainstream once similar tests are added to the other 201 * key generations and once there is a way to disable these checks. 202 */ 203 if (EVP_RAND_get_strength(rng) < ossl_ifc_ffc_compute_security_bits(nbits)) { 204 ERR_raise(ERR_LIB_RSA, 205 RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT); 206 return 0; 207 } 208 #endif 209 return 1; 210 } 211 212 /* 213 * 214 * Using p & q, calculate other required parameters such as n, d. 215 * as well as the CRT parameters dP, dQ, qInv. 216 * 217 * See SP800-56Br1 218 * 6.3.1.1 rsakpg1 - basic (Steps 3-4) 219 * 6.3.1.3 rsakpg1 - crt (Step 5) 220 * 221 * Params: 222 * rsa An rsa object. 223 * nbits The key size. 224 * e The public exponent. 225 * ctx A BN_CTX object. 226 * Notes: 227 * There is a small chance that the generated d will be too small. 228 * Returns: -1 = error, 229 * 0 = d is too small, 230 * 1 = success. 231 */ 232 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits, 233 const BIGNUM *e, BN_CTX *ctx) 234 { 235 int ret = -1; 236 BIGNUM *p1, *q1, *lcm, *p1q1, *gcd; 237 238 BN_CTX_start(ctx); 239 p1 = BN_CTX_get(ctx); 240 q1 = BN_CTX_get(ctx); 241 lcm = BN_CTX_get(ctx); 242 p1q1 = BN_CTX_get(ctx); 243 gcd = BN_CTX_get(ctx); 244 if (gcd == NULL) 245 goto err; 246 247 BN_set_flags(p1, BN_FLG_CONSTTIME); 248 BN_set_flags(q1, BN_FLG_CONSTTIME); 249 BN_set_flags(lcm, BN_FLG_CONSTTIME); 250 BN_set_flags(p1q1, BN_FLG_CONSTTIME); 251 BN_set_flags(gcd, BN_FLG_CONSTTIME); 252 253 /* LCM((p-1, q-1)) */ 254 if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1) 255 goto err; 256 257 /* copy e */ 258 BN_free(rsa->e); 259 rsa->e = BN_dup(e); 260 if (rsa->e == NULL) 261 goto err; 262 263 BN_clear_free(rsa->d); 264 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */ 265 rsa->d = BN_secure_new(); 266 if (rsa->d == NULL) 267 goto err; 268 BN_set_flags(rsa->d, BN_FLG_CONSTTIME); 269 if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL) 270 goto err; 271 272 /* (Step 3) return an error if d is too small */ 273 if (BN_num_bits(rsa->d) <= (nbits >> 1)) { 274 ret = 0; 275 goto err; 276 } 277 278 /* (Step 4) n = pq */ 279 if (rsa->n == NULL) 280 rsa->n = BN_new(); 281 if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) 282 goto err; 283 284 /* (Step 5a) dP = d mod (p-1) */ 285 if (rsa->dmp1 == NULL) 286 rsa->dmp1 = BN_secure_new(); 287 if (rsa->dmp1 == NULL) 288 goto err; 289 BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME); 290 if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx)) 291 goto err; 292 293 /* (Step 5b) dQ = d mod (q-1) */ 294 if (rsa->dmq1 == NULL) 295 rsa->dmq1 = BN_secure_new(); 296 if (rsa->dmq1 == NULL) 297 goto err; 298 BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME); 299 if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx)) 300 goto err; 301 302 /* (Step 5c) qInv = (inverse of q) mod p */ 303 BN_free(rsa->iqmp); 304 rsa->iqmp = BN_secure_new(); 305 if (rsa->iqmp == NULL) 306 goto err; 307 BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME); 308 if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL) 309 goto err; 310 311 rsa->dirty_cnt++; 312 ret = 1; 313 err: 314 if (ret != 1) { 315 BN_free(rsa->e); 316 rsa->e = NULL; 317 BN_free(rsa->d); 318 rsa->d = NULL; 319 BN_free(rsa->n); 320 rsa->n = NULL; 321 BN_free(rsa->iqmp); 322 rsa->iqmp = NULL; 323 BN_free(rsa->dmq1); 324 rsa->dmq1 = NULL; 325 BN_free(rsa->dmp1); 326 rsa->dmp1 = NULL; 327 } 328 BN_clear(p1); 329 BN_clear(q1); 330 BN_clear(lcm); 331 BN_clear(p1q1); 332 BN_clear(gcd); 333 334 BN_CTX_end(ctx); 335 return ret; 336 } 337 338 /* 339 * Generate a SP800-56B RSA key. 340 * 341 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent" 342 * 6.3.1.1 rsakpg1 - basic 343 * 6.3.1.3 rsakpg1 - crt 344 * 345 * See also FIPS 186-4 Section B.3.6 346 * "Generation of Probable Primes with Conditions Based on Auxiliary 347 * Probable Primes." 348 * 349 * Params: 350 * rsa The rsa object. 351 * nbits The intended key size in bits. 352 * efixed The public exponent. If NULL a default of 65537 is used. 353 * cb An optional BIGNUM callback. 354 * Returns: 1 if successfully generated otherwise it returns 0. 355 */ 356 int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed, 357 BN_GENCB *cb) 358 { 359 int ret = 0; 360 int ok; 361 BN_CTX *ctx = NULL; 362 BIGNUM *e = NULL; 363 RSA_ACVP_TEST *info = NULL; 364 BIGNUM *tmp; 365 366 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) 367 info = rsa->acvp_test; 368 #endif 369 370 /* (Steps 1a-1b) : Currently ignores the strength check */ 371 if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1)) 372 return 0; 373 374 /* Check that the RNG is capable of generating a key this large */ 375 if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits)) 376 return 0; 377 378 ctx = BN_CTX_new_ex(rsa->libctx); 379 if (ctx == NULL) 380 return 0; 381 382 /* Set default if e is not passed in */ 383 if (efixed == NULL) { 384 e = BN_new(); 385 if (e == NULL || !BN_set_word(e, 65537)) 386 goto err; 387 } else { 388 e = (BIGNUM *)efixed; 389 } 390 /* (Step 1c) fixed exponent is checked later .*/ 391 392 for (;;) { 393 /* (Step 2) Generate prime factors */ 394 if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb)) 395 goto err; 396 397 /* p>q check and skipping in case of acvp test */ 398 if (info == NULL && BN_cmp(rsa->p, rsa->q) < 0) { 399 tmp = rsa->p; 400 rsa->p = rsa->q; 401 rsa->q = tmp; 402 } 403 404 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */ 405 ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx); 406 if (ok < 0) 407 goto err; 408 if (ok > 0) 409 break; 410 /* Gets here if computed d is too small - so try again */ 411 } 412 413 /* (Step 6) Do pairwise test - optional validity test has been omitted */ 414 ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx); 415 err: 416 if (efixed == NULL) 417 BN_free(e); 418 BN_CTX_free(ctx); 419 return ret; 420 } 421 422 /* 423 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by 424 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1. 425 * 426 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails. 427 */ 428 int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx) 429 { 430 int ret = 0; 431 BIGNUM *k, *tmp; 432 433 BN_CTX_start(ctx); 434 tmp = BN_CTX_get(ctx); 435 k = BN_CTX_get(ctx); 436 if (k == NULL) 437 goto err; 438 BN_set_flags(k, BN_FLG_CONSTTIME); 439 440 ret = (BN_set_word(k, 2) 441 && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx) 442 && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx) 443 && BN_cmp(k, tmp) == 0); 444 if (ret == 0) 445 ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE); 446 err: 447 BN_CTX_end(ctx); 448 return ret; 449 } 450