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> |
13 | #include "crypto/bn.h" |
14 | #include "rsa_local.h" |
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)) |
78 | */ |
79 | int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx) |
80 | { |
81 | int ret = 0; |
82 | BIGNUM *low; |
83 | int shift; |
84 | |
85 | nbits >>= 1; |
86 | shift = nbits - BN_num_bits(&bn_inv_sqrt_2); |
87 | |
88 | /* Upper bound check */ |
89 | if (BN_num_bits(p) != nbits) |
90 | return 0; |
91 | |
92 | BN_CTX_start(ctx); |
93 | low = BN_CTX_get(ctx); |
94 | if (low == NULL) |
95 | goto err; |
96 | |
97 | /* set low = (√2)(2^(nbits/2 - 1) */ |
98 | if (!BN_copy(low, &bn_inv_sqrt_2)) |
99 | goto err; |
100 | |
101 | if (shift >= 0) { |
102 | /* |
103 | * We don't have all the bits. bn_inv_sqrt_2 contains a rounded up |
104 | * value, so there is a very low probability that we'll reject a valid |
105 | * value. |
106 | */ |
107 | if (!BN_lshift(low, low, shift)) |
108 | goto err; |
109 | } else if (!BN_rshift(low, low, -shift)) { |
110 | goto err; |
111 | } |
112 | if (BN_cmp(p, low) <= 0) |
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 | * |
125 | * See SP800-56Br1 6.4.1.2.3 Step 5 (a to d) & (e to h). |
126 | */ |
127 | int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx) |
128 | { |
129 | int ret = 0; |
130 | BIGNUM *p1 = NULL, *gcd = NULL; |
131 | |
132 | /* (Steps 5 a-b) prime test */ |
133 | if (BN_check_prime(p, ctx, NULL) != 1 |
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 | { |
240 | int ret = 0, nbits, status; |
241 | BN_CTX *ctx = NULL; |
242 | BIGNUM *gcd = NULL; |
243 | |
244 | if (rsa->n == NULL || rsa->e == NULL) |
245 | return 0; |
246 | |
247 | /* |
248 | * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1) |
249 | * NOTE: changed to allow keys >= 2048 |
250 | */ |
251 | nbits = BN_num_bits(rsa->n); |
252 | if (!rsa_sp800_56b_validate_strength(nbits, -1)) { |
253 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_KEY_LENGTH); |
254 | return 0; |
255 | } |
256 | if (!BN_is_odd(rsa->n)) { |
257 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS); |
258 | return 0; |
259 | } |
260 | |
261 | /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */ |
262 | if (!rsa_check_public_exponent(rsa->e)) { |
263 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, |
264 | RSA_R_PUB_EXPONENT_OUT_OF_RANGE); |
265 | return 0; |
266 | } |
267 | |
268 | ctx = BN_CTX_new(); |
269 | gcd = BN_new(); |
270 | if (ctx == NULL || gcd == NULL) |
271 | goto err; |
272 | |
273 | /* (Steps d-f): |
274 | * The modulus is composite, but not a power of a prime. |
275 | * The modulus has no factors smaller than 752. |
276 | */ |
277 | if (!BN_gcd(gcd, rsa->n, bn_get0_small_factors(), ctx) || !BN_is_one(gcd)) { |
278 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS); |
279 | goto err; |
280 | } |
281 | |
282 | ret = bn_miller_rabin_is_prime(rsa->n, 0, ctx, NULL, 1, &status); |
283 | if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) { |
284 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS); |
285 | ret = 0; |
286 | goto err; |
287 | } |
288 | |
289 | ret = 1; |
290 | err: |
291 | BN_free(gcd); |
292 | BN_CTX_free(ctx); |
293 | return ret; |
294 | } |
295 | |
296 | /* |
297 | * Perform validation of the RSA private key to check that 0 < D < N. |
298 | */ |
299 | int rsa_sp800_56b_check_private(const RSA *rsa) |
300 | { |
301 | if (rsa->d == NULL || rsa->n == NULL) |
302 | return 0; |
303 | return BN_cmp(rsa->d, BN_value_one()) >= 0 && BN_cmp(rsa->d, rsa->n) < 0; |
304 | } |
305 | |
306 | /* |
307 | * RSA key pair validation. |
308 | * |
309 | * SP800-56Br1. |
310 | * 6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent" |
311 | * 6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent" |
312 | * |
313 | * It uses: |
314 | * 6.4.1.2.3 "rsakpv1 - crt" |
315 | * 6.4.1.3.3 "rsakpv2 - crt" |
316 | */ |
317 | int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed, |
318 | int strength, int nbits) |
319 | { |
320 | int ret = 0; |
321 | BN_CTX *ctx = NULL; |
322 | BIGNUM *r = NULL; |
323 | |
324 | if (rsa->p == NULL |
325 | || rsa->q == NULL |
326 | || rsa->e == NULL |
327 | || rsa->d == NULL |
328 | || rsa->n == NULL) { |
329 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST); |
330 | return 0; |
331 | } |
332 | /* (Step 1): Check Ranges */ |
333 | if (!rsa_sp800_56b_validate_strength(nbits, strength)) |
334 | return 0; |
335 | |
336 | /* If the exponent is known */ |
337 | if (efixed != NULL) { |
338 | /* (2): Check fixed exponent matches public exponent. */ |
339 | if (BN_cmp(efixed, rsa->e) != 0) { |
340 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST); |
341 | return 0; |
342 | } |
343 | } |
344 | /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */ |
345 | if (!rsa_check_public_exponent(rsa->e)) { |
346 | /* exponent out of range */ |
347 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, |
348 | RSA_R_PUB_EXPONENT_OUT_OF_RANGE); |
349 | return 0; |
350 | } |
351 | /* (Step 3.b): check the modulus */ |
352 | if (nbits != BN_num_bits(rsa->n)) { |
353 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR); |
354 | return 0; |
355 | } |
356 | |
357 | ctx = BN_CTX_new(); |
358 | if (ctx == NULL) |
359 | return 0; |
360 | |
361 | BN_CTX_start(ctx); |
362 | r = BN_CTX_get(ctx); |
363 | if (r == NULL || !BN_mul(r, rsa->p, rsa->q, ctx)) |
364 | goto err; |
365 | /* (Step 4.c): Check n = pq */ |
366 | if (BN_cmp(rsa->n, r) != 0) { |
367 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST); |
368 | goto err; |
369 | } |
370 | |
371 | /* (Step 5): check prime factors p & q */ |
372 | ret = rsa_check_prime_factor(rsa->p, rsa->e, nbits, ctx) |
373 | && rsa_check_prime_factor(rsa->q, rsa->e, nbits, ctx) |
374 | && (rsa_check_pminusq_diff(r, rsa->p, rsa->q, nbits) > 0) |
375 | /* (Step 6): Check the private exponent d */ |
376 | && rsa_check_private_exponent(rsa, nbits, ctx) |
377 | /* 6.4.1.2.3 (Step 7): Check the CRT components */ |
378 | && rsa_check_crt_components(rsa, ctx); |
379 | if (ret != 1) |
380 | RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR); |
381 | |
382 | err: |
383 | BN_clear(r); |
384 | BN_CTX_end(ctx); |
385 | BN_CTX_free(ctx); |
386 | return ret; |
387 | } |
388 | |