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