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/* 12 * According to NIST SP800-131A "Transitioning the use of cryptographic 13 * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer 14 * allowed for signatures (Table 2) or key transport (Table 5). In the code 15 * below any attempt to generate 1024 bit RSA keys will result in an error (Note 16 * that digital signature verification can still use deprecated 1024 bit keys). 17 * 18 * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that 19 * must be generated before the module generates the RSA primes p and q. 20 * Table B.1 in FIPS 186-4 specifies RSA modulus lengths of 2048 and 21 * 3072 bits only, the min/max total length of the auxiliary primes. 22 * FIPS 186-5 Table A.1 includes an additional entry for 4096 which has been 23 * included here. 24 */ 25#include <stdio.h> 26#include <openssl/bn.h> 27#include "bn_local.h" 28#include "crypto/bn.h" 29#include "internal/nelem.h" 30 31#if BN_BITS2 == 64 32# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo 33#else 34# define BN_DEF(lo, hi) lo, hi 35#endif 36 37/* 1 / sqrt(2) * 2^256, rounded up */ 38static const BN_ULONG inv_sqrt_2_val[] = { 39 BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL), 40 BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL) 41}; 42 43const BIGNUM ossl_bn_inv_sqrt_2 = { 44 (BN_ULONG *)inv_sqrt_2_val, 45 OSSL_NELEM(inv_sqrt_2_val), 46 OSSL_NELEM(inv_sqrt_2_val), 47 0, 48 BN_FLG_STATIC_DATA 49}; 50 51/* 52 * FIPS 186-5 Table A.1. "Min length of auxiliary primes p1, p2, q1, q2". 53 * (FIPS 186-5 has an entry for >= 4096 bits). 54 * 55 * Params: 56 * nbits The key size in bits. 57 * Returns: 58 * The minimum size of the auxiliary primes or 0 if nbits is invalid. 59 */ 60static int bn_rsa_fips186_5_aux_prime_min_size(int nbits) 61{ 62 if (nbits >= 4096) 63 return 201; 64 if (nbits >= 3072) 65 return 171; 66 if (nbits >= 2048) 67 return 141; 68 return 0; 69} 70 71/* 72 * FIPS 186-5 Table A.1 "Max of len(p1) + len(p2) and 73 * len(q1) + len(q2) for p,q Probable Primes". 74 * (FIPS 186-5 has an entry for >= 4096 bits). 75 * Params: 76 * nbits The key size in bits. 77 * Returns: 78 * The maximum length or 0 if nbits is invalid. 79 */ 80static int bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(int nbits) 81{ 82 if (nbits >= 4096) 83 return 2030; 84 if (nbits >= 3072) 85 return 1518; 86 if (nbits >= 2048) 87 return 1007; 88 return 0; 89} 90 91/* 92 * Find the first odd integer that is a probable prime. 93 * 94 * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2). 95 * 96 * Params: 97 * Xp1 The passed in starting point to find a probably prime. 98 * p1 The returned probable prime (first odd integer >= Xp1) 99 * ctx A BN_CTX object. 100 * cb An optional BIGNUM callback. 101 * Returns: 1 on success otherwise it returns 0. 102 */ 103static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1, 104 BIGNUM *p1, BN_CTX *ctx, 105 BN_GENCB *cb) 106{ 107 int ret = 0; 108 int i = 0; 109 int tmp = 0; 110 111 if (BN_copy(p1, Xp1) == NULL) 112 return 0; 113 BN_set_flags(p1, BN_FLG_CONSTTIME); 114 115 /* Find the first odd number >= Xp1 that is probably prime */ 116 for(;;) { 117 i++; 118 BN_GENCB_call(cb, 0, i); 119 /* MR test with trial division */ 120 tmp = BN_check_prime(p1, ctx, cb); 121 if (tmp > 0) 122 break; 123 if (tmp < 0) 124 goto err; 125 /* Get next odd number */ 126 if (!BN_add_word(p1, 2)) 127 goto err; 128 } 129 BN_GENCB_call(cb, 2, i); 130 ret = 1; 131err: 132 return ret; 133} 134 135/* 136 * Generate a probable prime (p or q). 137 * 138 * See FIPS 186-4 B.3.6 (Steps 4 & 5) 139 * 140 * Params: 141 * p The returned probable prime. 142 * Xpout An optionally returned random number used during generation of p. 143 * p1, p2 The returned auxiliary primes. If NULL they are not returned. 144 * Xp An optional passed in value (that is random number used during 145 * generation of p). 146 * Xp1, Xp2 Optional passed in values that are normally generated 147 * internally. Used to find p1, p2. 148 * nlen The bit length of the modulus (the key size). 149 * e The public exponent. 150 * ctx A BN_CTX object. 151 * cb An optional BIGNUM callback. 152 * Returns: 1 on success otherwise it returns 0. 153 */ 154int ossl_bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout, 155 BIGNUM *p1, BIGNUM *p2, 156 const BIGNUM *Xp, const BIGNUM *Xp1, 157 const BIGNUM *Xp2, int nlen, 158 const BIGNUM *e, BN_CTX *ctx, 159 BN_GENCB *cb) 160{ 161 int ret = 0; 162 BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL; 163 int bitlen; 164 165 if (p == NULL || Xpout == NULL) 166 return 0; 167 168 BN_CTX_start(ctx); 169 170 p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx); 171 p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx); 172 Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx); 173 Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx); 174 if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL) 175 goto err; 176 177 bitlen = bn_rsa_fips186_5_aux_prime_min_size(nlen); 178 if (bitlen == 0) 179 goto err; 180 181 /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */ 182 if (Xp1 == NULL) { 183 /* Set the top and bottom bits to make it odd and the correct size */ 184 if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, 185 0, ctx)) 186 goto err; 187 } 188 /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */ 189 if (Xp2 == NULL) { 190 /* Set the top and bottom bits to make it odd and the correct size */ 191 if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, 192 0, ctx)) 193 goto err; 194 } 195 196 /* (Steps 4.2/5.2) - find first auxiliary probable primes */ 197 if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb) 198 || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb)) 199 goto err; 200 /* (Table B.1) auxiliary prime Max length check */ 201 if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >= 202 bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(nlen)) 203 goto err; 204 /* (Steps 4.3/5.3) - generate prime */ 205 if (!ossl_bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, 206 ctx, cb)) 207 goto err; 208 ret = 1; 209err: 210 /* Zeroize any internally generated values that are not returned */ 211 if (p1 == NULL) 212 BN_clear(p1i); 213 if (p2 == NULL) 214 BN_clear(p2i); 215 if (Xp1 == NULL) 216 BN_clear(Xp1i); 217 if (Xp2 == NULL) 218 BN_clear(Xp2i); 219 BN_CTX_end(ctx); 220 return ret; 221} 222 223/* 224 * Constructs a probable prime (a candidate for p or q) using 2 auxiliary 225 * prime numbers and the Chinese Remainder Theorem. 226 * 227 * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary 228 * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q. 229 * 230 * Params: 231 * Y The returned prime factor (private_prime_factor) of the modulus n. 232 * X The returned random number used during generation of the prime factor. 233 * Xin An optional passed in value for X used for testing purposes. 234 * r1 An auxiliary prime. 235 * r2 An auxiliary prime. 236 * nlen The desired length of n (the RSA modulus). 237 * e The public exponent. 238 * ctx A BN_CTX object. 239 * cb An optional BIGNUM callback object. 240 * Returns: 1 on success otherwise it returns 0. 241 * Assumptions: 242 * Y, X, r1, r2, e are not NULL. 243 */ 244int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, 245 const BIGNUM *r1, const BIGNUM *r2, 246 int nlen, const BIGNUM *e, BN_CTX *ctx, 247 BN_GENCB *cb) 248{ 249 int ret = 0; 250 int i, imax; 251 int bits = nlen >> 1; 252 BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2; 253 BIGNUM *base, *range; 254 255 BN_CTX_start(ctx); 256 257 base = BN_CTX_get(ctx); 258 range = BN_CTX_get(ctx); 259 R = BN_CTX_get(ctx); 260 tmp = BN_CTX_get(ctx); 261 r1r2x2 = BN_CTX_get(ctx); 262 y1 = BN_CTX_get(ctx); 263 r1x2 = BN_CTX_get(ctx); 264 if (r1x2 == NULL) 265 goto err; 266 267 if (Xin != NULL && BN_copy(X, Xin) == NULL) 268 goto err; 269 270 /* 271 * We need to generate a random number X in the range 272 * 1/sqrt(2) * 2^(nlen/2) <= X < 2^(nlen/2). 273 * We can rewrite that as: 274 * base = 1/sqrt(2) * 2^(nlen/2) 275 * range = ((2^(nlen/2))) - (1/sqrt(2) * 2^(nlen/2)) 276 * X = base + random(range) 277 * We only have the first 256 bit of 1/sqrt(2) 278 */ 279 if (Xin == NULL) { 280 if (bits < BN_num_bits(&ossl_bn_inv_sqrt_2)) 281 goto err; 282 if (!BN_lshift(base, &ossl_bn_inv_sqrt_2, 283 bits - BN_num_bits(&ossl_bn_inv_sqrt_2)) 284 || !BN_lshift(range, BN_value_one(), bits) 285 || !BN_sub(range, range, base)) 286 goto err; 287 } 288 289 if (!(BN_lshift1(r1x2, r1) 290 /* (Step 1) GCD(2r1, r2) = 1 */ 291 && BN_gcd(tmp, r1x2, r2, ctx) 292 && BN_is_one(tmp) 293 /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */ 294 && BN_mod_inverse(R, r2, r1x2, ctx) 295 && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */ 296 && BN_mod_inverse(tmp, r1x2, r2, ctx) 297 && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */ 298 && BN_sub(R, R, tmp) 299 /* Calculate 2r1r2 */ 300 && BN_mul(r1r2x2, r1x2, r2, ctx))) 301 goto err; 302 /* Make positive by adding the modulus */ 303 if (BN_is_negative(R) && !BN_add(R, R, r1r2x2)) 304 goto err; 305 306 /* 307 * In FIPS 186-4 imax was set to 5 * nlen/2. 308 * Analysis by Allen Roginsky (See https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf 309 * page 68) indicates this has a 1 in 2 million chance of failure. 310 * The number has been updated to 20 * nlen/2 as used in 311 * FIPS186-5 Appendix B.9 Step 9. 312 */ 313 imax = 20 * bits; /* max = 20/2 * nbits */ 314 for (;;) { 315 if (Xin == NULL) { 316 /* 317 * (Step 3) Choose Random X such that 318 * sqrt(2) * 2^(nlen/2-1) <= Random X <= (2^(nlen/2)) - 1. 319 */ 320 if (!BN_priv_rand_range_ex(X, range, 0, ctx) || !BN_add(X, X, base)) 321 goto err; 322 } 323 /* (Step 4) Y = X + ((R - X) mod 2r1r2) */ 324 if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X)) 325 goto err; 326 /* (Step 5) */ 327 i = 0; 328 for (;;) { 329 /* (Step 6) */ 330 if (BN_num_bits(Y) > bits) { 331 if (Xin == NULL) 332 break; /* Randomly Generated X so Go back to Step 3 */ 333 else 334 goto err; /* X is not random so it will always fail */ 335 } 336 BN_GENCB_call(cb, 0, 2); 337 338 /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */ 339 if (BN_copy(y1, Y) == NULL 340 || !BN_sub_word(y1, 1) 341 || !BN_gcd(tmp, y1, e, ctx)) 342 goto err; 343 if (BN_is_one(tmp)) { 344 int rv = BN_check_prime(Y, ctx, cb); 345 346 if (rv > 0) 347 goto end; 348 if (rv < 0) 349 goto err; 350 } 351 /* (Step 8-10) */ 352 if (++i >= imax) { 353 ERR_raise(ERR_LIB_BN, BN_R_NO_PRIME_CANDIDATE); 354 goto err; 355 } 356 if (!BN_add(Y, Y, r1r2x2)) 357 goto err; 358 } 359 } 360end: 361 ret = 1; 362 BN_GENCB_call(cb, 3, 0); 363err: 364 BN_clear(y1); 365 BN_CTX_end(ctx); 366 return ret; 367} 368