rsa_sp800_56b_gen.c 13 KB

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