rsa_chk.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266
  1. /*
  2. * Copyright 1999-2021 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. /*
  10. * RSA low level APIs are deprecated for public use, but still ok for
  11. * internal use.
  12. */
  13. #include "internal/deprecated.h"
  14. #include <openssl/bn.h>
  15. #include <openssl/err.h>
  16. #include "crypto/rsa.h"
  17. #include "rsa_local.h"
  18. #ifndef FIPS_MODULE
  19. static int rsa_validate_keypair_multiprime(const RSA *key, BN_GENCB *cb)
  20. {
  21. BIGNUM *i, *j, *k, *l, *m;
  22. BN_CTX *ctx;
  23. int ret = 1, ex_primes = 0, idx;
  24. RSA_PRIME_INFO *pinfo;
  25. if (key->p == NULL || key->q == NULL || key->n == NULL
  26. || key->e == NULL || key->d == NULL) {
  27. ERR_raise(ERR_LIB_RSA, RSA_R_VALUE_MISSING);
  28. return 0;
  29. }
  30. /* multi-prime? */
  31. if (key->version == RSA_ASN1_VERSION_MULTI) {
  32. ex_primes = sk_RSA_PRIME_INFO_num(key->prime_infos);
  33. if (ex_primes <= 0
  34. || (ex_primes + 2) > ossl_rsa_multip_cap(BN_num_bits(key->n))) {
  35. ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MULTI_PRIME_KEY);
  36. return 0;
  37. }
  38. }
  39. i = BN_new();
  40. j = BN_new();
  41. k = BN_new();
  42. l = BN_new();
  43. m = BN_new();
  44. ctx = BN_CTX_new_ex(key->libctx);
  45. if (i == NULL || j == NULL || k == NULL || l == NULL
  46. || m == NULL || ctx == NULL) {
  47. ret = -1;
  48. ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
  49. goto err;
  50. }
  51. if (BN_is_one(key->e)) {
  52. ret = 0;
  53. ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
  54. }
  55. if (!BN_is_odd(key->e)) {
  56. ret = 0;
  57. ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
  58. }
  59. /* p prime? */
  60. if (BN_check_prime(key->p, ctx, cb) != 1) {
  61. ret = 0;
  62. ERR_raise(ERR_LIB_RSA, RSA_R_P_NOT_PRIME);
  63. }
  64. /* q prime? */
  65. if (BN_check_prime(key->q, ctx, cb) != 1) {
  66. ret = 0;
  67. ERR_raise(ERR_LIB_RSA, RSA_R_Q_NOT_PRIME);
  68. }
  69. /* r_i prime? */
  70. for (idx = 0; idx < ex_primes; idx++) {
  71. pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
  72. if (BN_check_prime(pinfo->r, ctx, cb) != 1) {
  73. ret = 0;
  74. ERR_raise(ERR_LIB_RSA, RSA_R_MP_R_NOT_PRIME);
  75. }
  76. }
  77. /* n = p*q * r_3...r_i? */
  78. if (!BN_mul(i, key->p, key->q, ctx)) {
  79. ret = -1;
  80. goto err;
  81. }
  82. for (idx = 0; idx < ex_primes; idx++) {
  83. pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
  84. if (!BN_mul(i, i, pinfo->r, ctx)) {
  85. ret = -1;
  86. goto err;
  87. }
  88. }
  89. if (BN_cmp(i, key->n) != 0) {
  90. ret = 0;
  91. if (ex_primes)
  92. ERR_raise(ERR_LIB_RSA, RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES);
  93. else
  94. ERR_raise(ERR_LIB_RSA, RSA_R_N_DOES_NOT_EQUAL_P_Q);
  95. }
  96. /* d*e = 1 mod \lambda(n)? */
  97. if (!BN_sub(i, key->p, BN_value_one())) {
  98. ret = -1;
  99. goto err;
  100. }
  101. if (!BN_sub(j, key->q, BN_value_one())) {
  102. ret = -1;
  103. goto err;
  104. }
  105. /* now compute k = \lambda(n) = LCM(i, j, r_3 - 1...) */
  106. if (!BN_mul(l, i, j, ctx)) {
  107. ret = -1;
  108. goto err;
  109. }
  110. if (!BN_gcd(m, i, j, ctx)) {
  111. ret = -1;
  112. goto err;
  113. }
  114. for (idx = 0; idx < ex_primes; idx++) {
  115. pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
  116. if (!BN_sub(k, pinfo->r, BN_value_one())) {
  117. ret = -1;
  118. goto err;
  119. }
  120. if (!BN_mul(l, l, k, ctx)) {
  121. ret = -1;
  122. goto err;
  123. }
  124. if (!BN_gcd(m, m, k, ctx)) {
  125. ret = -1;
  126. goto err;
  127. }
  128. }
  129. if (!BN_div(k, NULL, l, m, ctx)) { /* remainder is 0 */
  130. ret = -1;
  131. goto err;
  132. }
  133. if (!BN_mod_mul(i, key->d, key->e, k, ctx)) {
  134. ret = -1;
  135. goto err;
  136. }
  137. if (!BN_is_one(i)) {
  138. ret = 0;
  139. ERR_raise(ERR_LIB_RSA, RSA_R_D_E_NOT_CONGRUENT_TO_1);
  140. }
  141. if (key->dmp1 != NULL && key->dmq1 != NULL && key->iqmp != NULL) {
  142. /* dmp1 = d mod (p-1)? */
  143. if (!BN_sub(i, key->p, BN_value_one())) {
  144. ret = -1;
  145. goto err;
  146. }
  147. if (!BN_mod(j, key->d, i, ctx)) {
  148. ret = -1;
  149. goto err;
  150. }
  151. if (BN_cmp(j, key->dmp1) != 0) {
  152. ret = 0;
  153. ERR_raise(ERR_LIB_RSA, RSA_R_DMP1_NOT_CONGRUENT_TO_D);
  154. }
  155. /* dmq1 = d mod (q-1)? */
  156. if (!BN_sub(i, key->q, BN_value_one())) {
  157. ret = -1;
  158. goto err;
  159. }
  160. if (!BN_mod(j, key->d, i, ctx)) {
  161. ret = -1;
  162. goto err;
  163. }
  164. if (BN_cmp(j, key->dmq1) != 0) {
  165. ret = 0;
  166. ERR_raise(ERR_LIB_RSA, RSA_R_DMQ1_NOT_CONGRUENT_TO_D);
  167. }
  168. /* iqmp = q^-1 mod p? */
  169. if (!BN_mod_inverse(i, key->q, key->p, ctx)) {
  170. ret = -1;
  171. goto err;
  172. }
  173. if (BN_cmp(i, key->iqmp) != 0) {
  174. ret = 0;
  175. ERR_raise(ERR_LIB_RSA, RSA_R_IQMP_NOT_INVERSE_OF_Q);
  176. }
  177. }
  178. for (idx = 0; idx < ex_primes; idx++) {
  179. pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
  180. /* d_i = d mod (r_i - 1)? */
  181. if (!BN_sub(i, pinfo->r, BN_value_one())) {
  182. ret = -1;
  183. goto err;
  184. }
  185. if (!BN_mod(j, key->d, i, ctx)) {
  186. ret = -1;
  187. goto err;
  188. }
  189. if (BN_cmp(j, pinfo->d) != 0) {
  190. ret = 0;
  191. ERR_raise(ERR_LIB_RSA, RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D);
  192. }
  193. /* t_i = R_i ^ -1 mod r_i ? */
  194. if (!BN_mod_inverse(i, pinfo->pp, pinfo->r, ctx)) {
  195. ret = -1;
  196. goto err;
  197. }
  198. if (BN_cmp(i, pinfo->t) != 0) {
  199. ret = 0;
  200. ERR_raise(ERR_LIB_RSA, RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R);
  201. }
  202. }
  203. err:
  204. BN_free(i);
  205. BN_free(j);
  206. BN_free(k);
  207. BN_free(l);
  208. BN_free(m);
  209. BN_CTX_free(ctx);
  210. return ret;
  211. }
  212. #endif /* FIPS_MODULE */
  213. int ossl_rsa_validate_public(const RSA *key)
  214. {
  215. return ossl_rsa_sp800_56b_check_public(key);
  216. }
  217. int ossl_rsa_validate_private(const RSA *key)
  218. {
  219. return ossl_rsa_sp800_56b_check_private(key);
  220. }
  221. int ossl_rsa_validate_pairwise(const RSA *key)
  222. {
  223. #ifdef FIPS_MODULE
  224. return ossl_rsa_sp800_56b_check_keypair(key, NULL, -1, RSA_bits(key));
  225. #else
  226. return rsa_validate_keypair_multiprime(key, NULL);
  227. #endif
  228. }
  229. int RSA_check_key(const RSA *key)
  230. {
  231. return RSA_check_key_ex(key, NULL);
  232. }
  233. int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
  234. {
  235. #ifdef FIPS_MODULE
  236. return ossl_rsa_validate_public(key)
  237. && ossl_rsa_validate_private(key)
  238. && ossl_rsa_validate_pairwise(key);
  239. #else
  240. return rsa_validate_keypair_multiprime(key, cb);
  241. #endif /* FIPS_MODULE */
  242. }