rsa_sp800_56b_check.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391
  1. /*
  2. * Copyright 2018-2019 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 OpenSSL license (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 "crypto/bn.h"
  13. #include "rsa_local.h"
  14. /*
  15. * Part of the RSA keypair test.
  16. * Check the Chinese Remainder Theorem components are valid.
  17. *
  18. * See SP800-5bBr1
  19. * 6.4.1.2.3: rsakpv1-crt Step 7
  20. * 6.4.1.3.3: rsakpv2-crt Step 7
  21. */
  22. int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx)
  23. {
  24. int ret = 0;
  25. BIGNUM *r = NULL, *p1 = NULL, *q1 = NULL;
  26. /* check if only some of the crt components are set */
  27. if (rsa->dmp1 == NULL || rsa->dmq1 == NULL || rsa->iqmp == NULL) {
  28. if (rsa->dmp1 != NULL || rsa->dmq1 != NULL || rsa->iqmp != NULL)
  29. return 0;
  30. return 1; /* return ok if all components are NULL */
  31. }
  32. BN_CTX_start(ctx);
  33. r = BN_CTX_get(ctx);
  34. p1 = BN_CTX_get(ctx);
  35. q1 = BN_CTX_get(ctx);
  36. ret = (q1 != NULL)
  37. /* p1 = p -1 */
  38. && (BN_copy(p1, rsa->p) != NULL)
  39. && BN_sub_word(p1, 1)
  40. /* q1 = q - 1 */
  41. && (BN_copy(q1, rsa->q) != NULL)
  42. && BN_sub_word(q1, 1)
  43. /* (a) 1 < dP < (p – 1). */
  44. && (BN_cmp(rsa->dmp1, BN_value_one()) > 0)
  45. && (BN_cmp(rsa->dmp1, p1) < 0)
  46. /* (b) 1 < dQ < (q - 1). */
  47. && (BN_cmp(rsa->dmq1, BN_value_one()) > 0)
  48. && (BN_cmp(rsa->dmq1, q1) < 0)
  49. /* (c) 1 < qInv < p */
  50. && (BN_cmp(rsa->iqmp, BN_value_one()) > 0)
  51. && (BN_cmp(rsa->iqmp, rsa->p) < 0)
  52. /* (d) 1 = (dP . e) mod (p - 1)*/
  53. && BN_mod_mul(r, rsa->dmp1, rsa->e, p1, ctx)
  54. && BN_is_one(r)
  55. /* (e) 1 = (dQ . e) mod (q - 1) */
  56. && BN_mod_mul(r, rsa->dmq1, rsa->e, q1, ctx)
  57. && BN_is_one(r)
  58. /* (f) 1 = (qInv . q) mod p */
  59. && BN_mod_mul(r, rsa->iqmp, rsa->q, rsa->p, ctx)
  60. && BN_is_one(r);
  61. BN_clear(p1);
  62. BN_clear(q1);
  63. BN_CTX_end(ctx);
  64. return ret;
  65. }
  66. /*
  67. * Part of the RSA keypair test.
  68. * Check that (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2) - 1
  69. *
  70. * See SP800-5bBr1 6.4.1.2.1 Part 5 (c) & (g) - used for both p and q.
  71. *
  72. * (√2)(2^(nbits/2 - 1) = (√2/2)(2^(nbits/2))
  73. */
  74. int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx)
  75. {
  76. int ret = 0;
  77. BIGNUM *low;
  78. int shift;
  79. nbits >>= 1;
  80. shift = nbits - BN_num_bits(&bn_inv_sqrt_2);
  81. /* Upper bound check */
  82. if (BN_num_bits(p) != nbits)
  83. return 0;
  84. BN_CTX_start(ctx);
  85. low = BN_CTX_get(ctx);
  86. if (low == NULL)
  87. goto err;
  88. /* set low = (√2)(2^(nbits/2 - 1) */
  89. if (!BN_copy(low, &bn_inv_sqrt_2))
  90. goto err;
  91. if (shift >= 0) {
  92. /*
  93. * We don't have all the bits. bn_inv_sqrt_2 contains a rounded up
  94. * value, so there is a very low probability that we'll reject a valid
  95. * value.
  96. */
  97. if (!BN_lshift(low, low, shift))
  98. goto err;
  99. } else if (!BN_rshift(low, low, -shift)) {
  100. goto err;
  101. }
  102. if (BN_cmp(p, low) <= 0)
  103. goto err;
  104. ret = 1;
  105. err:
  106. BN_CTX_end(ctx);
  107. return ret;
  108. }
  109. /*
  110. * Part of the RSA keypair test.
  111. * Check the prime factor (for either p or q)
  112. * i.e: p is prime AND GCD(p - 1, e) = 1
  113. *
  114. * See SP800-56Br1 6.4.1.2.3 Step 5 (a to d) & (e to h).
  115. */
  116. int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
  117. {
  118. int ret = 0;
  119. BIGNUM *p1 = NULL, *gcd = NULL;
  120. /* (Steps 5 a-b) prime test */
  121. if (BN_check_prime(p, ctx, NULL) != 1
  122. /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
  123. || rsa_check_prime_factor_range(p, nbits, ctx) != 1)
  124. return 0;
  125. BN_CTX_start(ctx);
  126. p1 = BN_CTX_get(ctx);
  127. gcd = BN_CTX_get(ctx);
  128. ret = (gcd != NULL)
  129. /* (Step 5d) GCD(p-1, e) = 1 */
  130. && (BN_copy(p1, p) != NULL)
  131. && BN_sub_word(p1, 1)
  132. && BN_gcd(gcd, p1, e, ctx)
  133. && BN_is_one(gcd);
  134. BN_clear(p1);
  135. BN_CTX_end(ctx);
  136. return ret;
  137. }
  138. /*
  139. * See SP800-56Br1 6.4.1.2.3 Part 6(a-b) Check the private exponent d
  140. * satisfies:
  141. * (Step 6a) 2^(nBit/2) < d < LCM(p–1, q–1).
  142. * (Step 6b) 1 = (d*e) mod LCM(p–1, q–1)
  143. */
  144. int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
  145. {
  146. int ret;
  147. BIGNUM *r, *p1, *q1, *lcm, *p1q1, *gcd;
  148. /* (Step 6a) 2^(nbits/2) < d */
  149. if (BN_num_bits(rsa->d) <= (nbits >> 1))
  150. return 0;
  151. BN_CTX_start(ctx);
  152. r = BN_CTX_get(ctx);
  153. p1 = BN_CTX_get(ctx);
  154. q1 = BN_CTX_get(ctx);
  155. lcm = BN_CTX_get(ctx);
  156. p1q1 = BN_CTX_get(ctx);
  157. gcd = BN_CTX_get(ctx);
  158. ret = (gcd != NULL
  159. /* LCM(p - 1, q - 1) */
  160. && (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) == 1)
  161. /* (Step 6a) d < LCM(p - 1, q - 1) */
  162. && (BN_cmp(rsa->d, lcm) < 0)
  163. /* (Step 6b) 1 = (e . d) mod LCM(p - 1, q - 1) */
  164. && BN_mod_mul(r, rsa->e, rsa->d, lcm, ctx)
  165. && BN_is_one(r));
  166. BN_clear(p1);
  167. BN_clear(q1);
  168. BN_clear(lcm);
  169. BN_clear(gcd);
  170. BN_CTX_end(ctx);
  171. return ret;
  172. }
  173. /* Check exponent is odd, and has a bitlen ranging from [17..256] */
  174. int rsa_check_public_exponent(const BIGNUM *e)
  175. {
  176. int bitlen = BN_num_bits(e);
  177. return (BN_is_odd(e) && bitlen > 16 && bitlen < 257);
  178. }
  179. /*
  180. * SP800-56Br1 6.4.1.2.1 (Step 5i): |p - q| > 2^(nbits/2 - 100)
  181. * i.e- numbits(p-q-1) > (nbits/2 -100)
  182. */
  183. int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
  184. int nbits)
  185. {
  186. int bitlen = (nbits >> 1) - 100;
  187. if (!BN_sub(diff, p, q))
  188. return -1;
  189. BN_set_negative(diff, 0);
  190. if (BN_is_zero(diff))
  191. return 0;
  192. if (!BN_sub_word(diff, 1))
  193. return -1;
  194. return (BN_num_bits(diff) > bitlen);
  195. }
  196. /* return LCM(p-1, q-1) */
  197. int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
  198. BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
  199. BIGNUM *p1q1)
  200. {
  201. return BN_sub(p1, p, BN_value_one()) /* p-1 */
  202. && BN_sub(q1, q, BN_value_one()) /* q-1 */
  203. && BN_mul(p1q1, p1, q1, ctx) /* (p-1)(q-1) */
  204. && BN_gcd(gcd, p1, q1, ctx)
  205. && BN_div(lcm, NULL, p1q1, gcd, ctx); /* LCM((p-1, q-1)) */
  206. }
  207. /*
  208. * SP800-56Br1 6.4.2.2 Partial Public Key Validation for RSA refers to
  209. * SP800-89 5.3.3 (Explicit) Partial Public Key Validation for RSA
  210. * caveat is that the modulus must be as specified in SP800-56Br1
  211. */
  212. int rsa_sp800_56b_check_public(const RSA *rsa)
  213. {
  214. int ret = 0, status;
  215. #ifdef FIPS_MODE
  216. int nbits;
  217. #endif
  218. BN_CTX *ctx = NULL;
  219. BIGNUM *gcd = NULL;
  220. if (rsa->n == NULL || rsa->e == NULL)
  221. return 0;
  222. #ifdef FIPS_MODE
  223. /*
  224. * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1)
  225. * NOTE: changed to allow keys >= 2048
  226. */
  227. nbits = BN_num_bits(rsa->n);
  228. if (!rsa_sp800_56b_validate_strength(nbits, -1)) {
  229. RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_KEY_LENGTH);
  230. return 0;
  231. }
  232. #endif
  233. if (!BN_is_odd(rsa->n)) {
  234. RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
  235. return 0;
  236. }
  237. /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */
  238. if (!rsa_check_public_exponent(rsa->e)) {
  239. RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC,
  240. RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
  241. return 0;
  242. }
  243. ctx = BN_CTX_new();
  244. gcd = BN_new();
  245. if (ctx == NULL || gcd == NULL)
  246. goto err;
  247. /* (Steps d-f):
  248. * The modulus is composite, but not a power of a prime.
  249. * The modulus has no factors smaller than 752.
  250. */
  251. if (!BN_gcd(gcd, rsa->n, bn_get0_small_factors(), ctx) || !BN_is_one(gcd)) {
  252. RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
  253. goto err;
  254. }
  255. ret = bn_miller_rabin_is_prime(rsa->n, 0, ctx, NULL, 1, &status);
  256. if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) {
  257. RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
  258. ret = 0;
  259. goto err;
  260. }
  261. ret = 1;
  262. err:
  263. BN_free(gcd);
  264. BN_CTX_free(ctx);
  265. return ret;
  266. }
  267. /*
  268. * Perform validation of the RSA private key to check that 0 < D < N.
  269. */
  270. int rsa_sp800_56b_check_private(const RSA *rsa)
  271. {
  272. if (rsa->d == NULL || rsa->n == NULL)
  273. return 0;
  274. return BN_cmp(rsa->d, BN_value_one()) >= 0 && BN_cmp(rsa->d, rsa->n) < 0;
  275. }
  276. /*
  277. * RSA key pair validation.
  278. *
  279. * SP800-56Br1.
  280. * 6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent"
  281. * 6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent"
  282. *
  283. * It uses:
  284. * 6.4.1.2.3 "rsakpv1 - crt"
  285. * 6.4.1.3.3 "rsakpv2 - crt"
  286. */
  287. int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
  288. int strength, int nbits)
  289. {
  290. int ret = 0;
  291. BN_CTX *ctx = NULL;
  292. BIGNUM *r = NULL;
  293. if (rsa->p == NULL
  294. || rsa->q == NULL
  295. || rsa->e == NULL
  296. || rsa->d == NULL
  297. || rsa->n == NULL) {
  298. RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
  299. return 0;
  300. }
  301. /* (Step 1): Check Ranges */
  302. if (!rsa_sp800_56b_validate_strength(nbits, strength))
  303. return 0;
  304. /* If the exponent is known */
  305. if (efixed != NULL) {
  306. /* (2): Check fixed exponent matches public exponent. */
  307. if (BN_cmp(efixed, rsa->e) != 0) {
  308. RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
  309. return 0;
  310. }
  311. }
  312. /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */
  313. if (!rsa_check_public_exponent(rsa->e)) {
  314. /* exponent out of range */
  315. RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR,
  316. RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
  317. return 0;
  318. }
  319. /* (Step 3.b): check the modulus */
  320. if (nbits != BN_num_bits(rsa->n)) {
  321. RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
  322. return 0;
  323. }
  324. ctx = BN_CTX_new();
  325. if (ctx == NULL)
  326. return 0;
  327. BN_CTX_start(ctx);
  328. r = BN_CTX_get(ctx);
  329. if (r == NULL || !BN_mul(r, rsa->p, rsa->q, ctx))
  330. goto err;
  331. /* (Step 4.c): Check n = pq */
  332. if (BN_cmp(rsa->n, r) != 0) {
  333. RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
  334. goto err;
  335. }
  336. /* (Step 5): check prime factors p & q */
  337. ret = rsa_check_prime_factor(rsa->p, rsa->e, nbits, ctx)
  338. && rsa_check_prime_factor(rsa->q, rsa->e, nbits, ctx)
  339. && (rsa_check_pminusq_diff(r, rsa->p, rsa->q, nbits) > 0)
  340. /* (Step 6): Check the private exponent d */
  341. && rsa_check_private_exponent(rsa, nbits, ctx)
  342. /* 6.4.1.2.3 (Step 7): Check the CRT components */
  343. && rsa_check_crt_components(rsa, ctx);
  344. if (ret != 1)
  345. RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
  346. err:
  347. BN_clear(r);
  348. BN_CTX_end(ctx);
  349. BN_CTX_free(ctx);
  350. return ret;
  351. }