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 */
24int 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 */
79int 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;
115err:
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 */
127int 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 */
159int 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] */
193int 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 */
204int 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) */
222int 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 */
238int 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;
290err:
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 */
299int 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 */
317int 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
382err:
383 BN_clear(r);
384 BN_CTX_end(ctx);
385 BN_CTX_free(ctx);
386 return ret;
387}
388