1 /*
2 * Copyright 1999-2017 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the OpenSSL license (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 #include <openssl/bn.h>
11 #include <openssl/err.h>
12 #include "rsa_local.h"
13
RSA_check_key(const RSA * key)14 int RSA_check_key(const RSA *key)
15 {
16 return RSA_check_key_ex(key, NULL);
17 }
18
RSA_check_key_ex(const RSA * key,BN_GENCB * cb)19 int RSA_check_key_ex(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
26 if (key->p == NULL || key->q == NULL || key->n == NULL
27 || key->e == NULL || key->d == NULL) {
28 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_VALUE_MISSING);
29 return 0;
30 }
31
32 /* multi-prime? */
33 if (key->version == RSA_ASN1_VERSION_MULTI) {
34 ex_primes = sk_RSA_PRIME_INFO_num(key->prime_infos);
35 if (ex_primes <= 0
36 || (ex_primes + 2) > rsa_multip_cap(BN_num_bits(key->n))) {
37 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_INVALID_MULTI_PRIME_KEY);
38 return 0;
39 }
40 }
41
42 i = BN_new();
43 j = BN_new();
44 k = BN_new();
45 l = BN_new();
46 m = BN_new();
47 ctx = BN_CTX_new();
48 if (i == NULL || j == NULL || k == NULL || l == NULL
49 || m == NULL || ctx == NULL) {
50 ret = -1;
51 RSAerr(RSA_F_RSA_CHECK_KEY_EX, ERR_R_MALLOC_FAILURE);
52 goto err;
53 }
54
55 if (BN_is_one(key->e)) {
56 ret = 0;
57 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_BAD_E_VALUE);
58 }
59 if (!BN_is_odd(key->e)) {
60 ret = 0;
61 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_BAD_E_VALUE);
62 }
63
64 /* p prime? */
65 if (BN_is_prime_ex(key->p, BN_prime_checks, NULL, cb) != 1) {
66 ret = 0;
67 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_P_NOT_PRIME);
68 }
69
70 /* q prime? */
71 if (BN_is_prime_ex(key->q, BN_prime_checks, NULL, cb) != 1) {
72 ret = 0;
73 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_Q_NOT_PRIME);
74 }
75
76 /* r_i prime? */
77 for (idx = 0; idx < ex_primes; idx++) {
78 pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
79 if (BN_is_prime_ex(pinfo->r, BN_prime_checks, NULL, cb) != 1) {
80 ret = 0;
81 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_R_NOT_PRIME);
82 }
83 }
84
85 /* n = p*q * r_3...r_i? */
86 if (!BN_mul(i, key->p, key->q, ctx)) {
87 ret = -1;
88 goto err;
89 }
90 for (idx = 0; idx < ex_primes; idx++) {
91 pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
92 if (!BN_mul(i, i, pinfo->r, ctx)) {
93 ret = -1;
94 goto err;
95 }
96 }
97 if (BN_cmp(i, key->n) != 0) {
98 ret = 0;
99 if (ex_primes)
100 RSAerr(RSA_F_RSA_CHECK_KEY_EX,
101 RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES);
102 else
103 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_N_DOES_NOT_EQUAL_P_Q);
104 }
105
106 /* d*e = 1 mod \lambda(n)? */
107 if (!BN_sub(i, key->p, BN_value_one())) {
108 ret = -1;
109 goto err;
110 }
111 if (!BN_sub(j, key->q, BN_value_one())) {
112 ret = -1;
113 goto err;
114 }
115
116 /* now compute k = \lambda(n) = LCM(i, j, r_3 - 1...) */
117 if (!BN_mul(l, i, j, ctx)) {
118 ret = -1;
119 goto err;
120 }
121 if (!BN_gcd(m, i, j, ctx)) {
122 ret = -1;
123 goto err;
124 }
125 for (idx = 0; idx < ex_primes; idx++) {
126 pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
127 if (!BN_sub(k, pinfo->r, BN_value_one())) {
128 ret = -1;
129 goto err;
130 }
131 if (!BN_mul(l, l, k, ctx)) {
132 ret = -1;
133 goto err;
134 }
135 if (!BN_gcd(m, m, k, ctx)) {
136 ret = -1;
137 goto err;
138 }
139 }
140 if (!BN_div(k, NULL, l, m, ctx)) { /* remainder is 0 */
141 ret = -1;
142 goto err;
143 }
144 if (!BN_mod_mul(i, key->d, key->e, k, ctx)) {
145 ret = -1;
146 goto err;
147 }
148
149 if (!BN_is_one(i)) {
150 ret = 0;
151 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_D_E_NOT_CONGRUENT_TO_1);
152 }
153
154 if (key->dmp1 != NULL && key->dmq1 != NULL && key->iqmp != NULL) {
155 /* dmp1 = d mod (p-1)? */
156 if (!BN_sub(i, key->p, 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->dmp1) != 0) {
165 ret = 0;
166 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_DMP1_NOT_CONGRUENT_TO_D);
167 }
168
169 /* dmq1 = d mod (q-1)? */
170 if (!BN_sub(i, key->q, BN_value_one())) {
171 ret = -1;
172 goto err;
173 }
174 if (!BN_mod(j, key->d, i, ctx)) {
175 ret = -1;
176 goto err;
177 }
178 if (BN_cmp(j, key->dmq1) != 0) {
179 ret = 0;
180 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_DMQ1_NOT_CONGRUENT_TO_D);
181 }
182
183 /* iqmp = q^-1 mod p? */
184 if (!BN_mod_inverse(i, key->q, key->p, ctx)) {
185 ret = -1;
186 goto err;
187 }
188 if (BN_cmp(i, key->iqmp) != 0) {
189 ret = 0;
190 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_IQMP_NOT_INVERSE_OF_Q);
191 }
192 }
193
194 for (idx = 0; idx < ex_primes; idx++) {
195 pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
196 /* d_i = d mod (r_i - 1)? */
197 if (!BN_sub(i, pinfo->r, BN_value_one())) {
198 ret = -1;
199 goto err;
200 }
201 if (!BN_mod(j, key->d, i, ctx)) {
202 ret = -1;
203 goto err;
204 }
205 if (BN_cmp(j, pinfo->d) != 0) {
206 ret = 0;
207 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D);
208 }
209 /* t_i = R_i ^ -1 mod r_i ? */
210 if (!BN_mod_inverse(i, pinfo->pp, pinfo->r, ctx)) {
211 ret = -1;
212 goto err;
213 }
214 if (BN_cmp(i, pinfo->t) != 0) {
215 ret = 0;
216 RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R);
217 }
218 }
219
220 err:
221 BN_free(i);
222 BN_free(j);
223 BN_free(k);
224 BN_free(l);
225 BN_free(m);
226 BN_CTX_free(ctx);
227 return ret;
228 }
229