2
0

bn_rsa_fips186_4.c 13 KB

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