bn_rsa_fips186_4.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342
  1. /*
  2. * Copyright 2018-2020 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. * Also see FIPS1402IG A.14
  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, for RSA modulus lengths of 2048 and
  21. * 3072 bits only, the min/max total length of the auxiliary primes.
  22. * When implementing the RSA signature generation algorithm
  23. * with other approved RSA modulus sizes, the vendor shall use the limitations
  24. * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
  25. * FIPS 186-4 whose length does not exceed that of the implementation's RSA
  26. * modulus. In particular, when generating the primes for the 4096-bit RSA
  27. * modulus the limitations stated for the 3072-bit modulus shall apply.
  28. */
  29. #include <stdio.h>
  30. #include <openssl/bn.h>
  31. #include "bn_local.h"
  32. #include "crypto/bn.h"
  33. #include "internal/nelem.h"
  34. #if BN_BITS2 == 64
  35. # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
  36. #else
  37. # define BN_DEF(lo, hi) lo, hi
  38. #endif
  39. /* 1 / sqrt(2) * 2^256, rounded up */
  40. static const BN_ULONG inv_sqrt_2_val[] = {
  41. BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL),
  42. BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL)
  43. };
  44. const BIGNUM bn_inv_sqrt_2 = {
  45. (BN_ULONG *)inv_sqrt_2_val,
  46. OSSL_NELEM(inv_sqrt_2_val),
  47. OSSL_NELEM(inv_sqrt_2_val),
  48. 0,
  49. BN_FLG_STATIC_DATA
  50. };
  51. /*
  52. * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
  53. *
  54. * Params:
  55. * nbits The key size in bits.
  56. * Returns:
  57. * The minimum size of the auxiliary primes or 0 if nbits is invalid.
  58. */
  59. static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
  60. {
  61. if (nbits >= 3072)
  62. return 171;
  63. if (nbits == 2048)
  64. return 141;
  65. return 0;
  66. }
  67. /*
  68. * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
  69. * len(q1) + len(q2) for p,q Probable Primes".
  70. *
  71. * Params:
  72. * nbits The key size in bits.
  73. * Returns:
  74. * The maximum length or 0 if nbits is invalid.
  75. */
  76. static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
  77. {
  78. if (nbits >= 3072)
  79. return 1518;
  80. if (nbits == 2048)
  81. return 1007;
  82. return 0;
  83. }
  84. /*
  85. * Find the first odd integer that is a probable prime.
  86. *
  87. * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
  88. *
  89. * Params:
  90. * Xp1 The passed in starting point to find a probably prime.
  91. * p1 The returned probable prime (first odd integer >= Xp1)
  92. * ctx A BN_CTX object.
  93. * cb An optional BIGNUM callback.
  94. * Returns: 1 on success otherwise it returns 0.
  95. */
  96. static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
  97. BIGNUM *p1, BN_CTX *ctx,
  98. BN_GENCB *cb)
  99. {
  100. int ret = 0;
  101. int i = 0;
  102. if (BN_copy(p1, Xp1) == NULL)
  103. return 0;
  104. BN_set_flags(p1, BN_FLG_CONSTTIME);
  105. /* Find the first odd number >= Xp1 that is probably prime */
  106. for(;;) {
  107. i++;
  108. BN_GENCB_call(cb, 0, i);
  109. /* MR test with trial division */
  110. if (BN_check_prime(p1, ctx, cb))
  111. break;
  112. /* Get next odd number */
  113. if (!BN_add_word(p1, 2))
  114. goto err;
  115. }
  116. BN_GENCB_call(cb, 2, i);
  117. ret = 1;
  118. err:
  119. return ret;
  120. }
  121. /*
  122. * Generate a probable prime (p or q).
  123. *
  124. * See FIPS 186-4 B.3.6 (Steps 4 & 5)
  125. *
  126. * Params:
  127. * p The returned probable prime.
  128. * Xpout An optionally returned random number used during generation of p.
  129. * p1, p2 The returned auxiliary primes. If NULL they are not returned.
  130. * Xp An optional passed in value (that is random number used during
  131. * generation of p).
  132. * Xp1, Xp2 Optional passed in values that are normally generated
  133. * internally. Used to find p1, p2.
  134. * nlen The bit length of the modulus (the key size).
  135. * e The public exponent.
  136. * ctx A BN_CTX object.
  137. * cb An optional BIGNUM callback.
  138. * Returns: 1 on success otherwise it returns 0.
  139. */
  140. int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
  141. BIGNUM *p1, BIGNUM *p2,
  142. const BIGNUM *Xp, const BIGNUM *Xp1,
  143. const BIGNUM *Xp2, int nlen,
  144. const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
  145. {
  146. int ret = 0;
  147. BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
  148. int bitlen;
  149. if (p == NULL || Xpout == NULL)
  150. return 0;
  151. BN_CTX_start(ctx);
  152. p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
  153. p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
  154. Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
  155. Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
  156. if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
  157. goto err;
  158. bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
  159. if (bitlen == 0)
  160. goto err;
  161. /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
  162. if (Xp1 == NULL) {
  163. /* Set the top and bottom bits to make it odd and the correct size */
  164. if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
  165. ctx))
  166. goto err;
  167. }
  168. /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
  169. if (Xp2 == NULL) {
  170. /* Set the top and bottom bits to make it odd and the correct size */
  171. if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
  172. ctx))
  173. goto err;
  174. }
  175. /* (Steps 4.2/5.2) - find first auxiliary probable primes */
  176. if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
  177. || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
  178. goto err;
  179. /* (Table B.1) auxiliary prime Max length check */
  180. if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
  181. bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
  182. goto err;
  183. /* (Steps 4.3/5.3) - generate prime */
  184. if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
  185. goto err;
  186. ret = 1;
  187. err:
  188. /* Zeroize any internally generated values that are not returned */
  189. if (p1 == NULL)
  190. BN_clear(p1i);
  191. if (p2 == NULL)
  192. BN_clear(p2i);
  193. if (Xp1 == NULL)
  194. BN_clear(Xp1i);
  195. if (Xp2 == NULL)
  196. BN_clear(Xp2i);
  197. BN_CTX_end(ctx);
  198. return ret;
  199. }
  200. /*
  201. * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
  202. * prime numbers and the Chinese Remainder Theorem.
  203. *
  204. * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
  205. * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
  206. *
  207. * Params:
  208. * Y The returned prime factor (private_prime_factor) of the modulus n.
  209. * X The returned random number used during generation of the prime factor.
  210. * Xin An optional passed in value for X used for testing purposes.
  211. * r1 An auxiliary prime.
  212. * r2 An auxiliary prime.
  213. * nlen The desired length of n (the RSA modulus).
  214. * e The public exponent.
  215. * ctx A BN_CTX object.
  216. * cb An optional BIGNUM callback object.
  217. * Returns: 1 on success otherwise it returns 0.
  218. * Assumptions:
  219. * Y, X, r1, r2, e are not NULL.
  220. */
  221. int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
  222. const BIGNUM *r1, const BIGNUM *r2, int nlen,
  223. const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
  224. {
  225. int ret = 0;
  226. int i, imax;
  227. int bits = nlen >> 1;
  228. BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
  229. BIGNUM *base, *range;
  230. BN_CTX_start(ctx);
  231. base = BN_CTX_get(ctx);
  232. range = BN_CTX_get(ctx);
  233. R = BN_CTX_get(ctx);
  234. tmp = BN_CTX_get(ctx);
  235. r1r2x2 = BN_CTX_get(ctx);
  236. y1 = BN_CTX_get(ctx);
  237. r1x2 = BN_CTX_get(ctx);
  238. if (r1x2 == NULL)
  239. goto err;
  240. if (Xin != NULL && BN_copy(X, Xin) == NULL)
  241. goto err;
  242. /*
  243. * We need to generate a random number X in the range
  244. * 1/sqrt(2) * 2^(nlen/2) <= X < 2^(nlen/2).
  245. * We can rewrite that as:
  246. * base = 1/sqrt(2) * 2^(nlen/2)
  247. * range = ((2^(nlen/2))) - (1/sqrt(2) * 2^(nlen/2))
  248. * X = base + random(range)
  249. * We only have the first 256 bit of 1/sqrt(2)
  250. */
  251. if (Xin == NULL) {
  252. if (bits < BN_num_bits(&bn_inv_sqrt_2))
  253. goto err;
  254. if (!BN_lshift(base, &bn_inv_sqrt_2, bits - BN_num_bits(&bn_inv_sqrt_2))
  255. || !BN_lshift(range, BN_value_one(), bits)
  256. || !BN_sub(range, range, base))
  257. goto err;
  258. }
  259. if (!(BN_lshift1(r1x2, r1)
  260. /* (Step 1) GCD(2r1, r2) = 1 */
  261. && BN_gcd(tmp, r1x2, r2, ctx)
  262. && BN_is_one(tmp)
  263. /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
  264. && BN_mod_inverse(R, r2, r1x2, ctx)
  265. && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
  266. && BN_mod_inverse(tmp, r1x2, r2, ctx)
  267. && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
  268. && BN_sub(R, R, tmp)
  269. /* Calculate 2r1r2 */
  270. && BN_mul(r1r2x2, r1x2, r2, ctx)))
  271. goto err;
  272. /* Make positive by adding the modulus */
  273. if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
  274. goto err;
  275. imax = 5 * bits; /* max = 5/2 * nbits */
  276. for (;;) {
  277. if (Xin == NULL) {
  278. /*
  279. * (Step 3) Choose Random X such that
  280. * sqrt(2) * 2^(nlen/2-1) <= Random X <= (2^(nlen/2)) - 1.
  281. */
  282. if (!BN_priv_rand_range_ex(X, range, ctx) || !BN_add(X, X, base))
  283. goto end;
  284. }
  285. /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
  286. if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
  287. goto err;
  288. /* (Step 5) */
  289. i = 0;
  290. for (;;) {
  291. /* (Step 6) */
  292. if (BN_num_bits(Y) > bits) {
  293. if (Xin == NULL)
  294. break; /* Randomly Generated X so Go back to Step 3 */
  295. else
  296. goto err; /* X is not random so it will always fail */
  297. }
  298. BN_GENCB_call(cb, 0, 2);
  299. /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
  300. if (BN_copy(y1, Y) == NULL
  301. || !BN_sub_word(y1, 1)
  302. || !BN_gcd(tmp, y1, e, ctx))
  303. goto err;
  304. if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
  305. goto end;
  306. /* (Step 8-10) */
  307. if (++i >= imax || !BN_add(Y, Y, r1r2x2))
  308. goto err;
  309. }
  310. }
  311. end:
  312. ret = 1;
  313. BN_GENCB_call(cb, 3, 0);
  314. err:
  315. BN_clear(y1);
  316. BN_CTX_end(ctx);
  317. return ret;
  318. }