2 * Copyright 2018-2020 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
5 * Licensed under the Apache License 2.0 (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
11 #include <openssl/err.h>
12 #include <openssl/bn.h>
13 #include "crypto/bn.h"
14 #include "rsa_local.h"
17 * Part of the RSA keypair test.
18 * Check the Chinese Remainder Theorem components are valid.
21 * 6.4.1.2.3: rsakpv1-crt Step 7
22 * 6.4.1.3.3: rsakpv2-crt Step 7
24 int rsa_check_crt_components(const RSA
*rsa
, BN_CTX
*ctx
)
27 BIGNUM
*r
= NULL
, *p1
= NULL
, *q1
= NULL
;
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
)
33 return 1; /* return ok if all components are NULL */
41 BN_set_flags(r
, BN_FLG_CONSTTIME
);
42 BN_set_flags(p1
, BN_FLG_CONSTTIME
);
43 BN_set_flags(q1
, BN_FLG_CONSTTIME
);
50 && (BN_copy(p1
, rsa
->p
) != NULL
)
53 && (BN_copy(q1
, rsa
->q
) != NULL
)
55 /* (a) 1 < dP < (p – 1). */
56 && (BN_cmp(rsa
->dmp1
, BN_value_one()) > 0)
57 && (BN_cmp(rsa
->dmp1
, p1
) < 0)
58 /* (b) 1 < dQ < (q - 1). */
59 && (BN_cmp(rsa
->dmq1
, BN_value_one()) > 0)
60 && (BN_cmp(rsa
->dmq1
, q1
) < 0)
61 /* (c) 1 < qInv < p */
62 && (BN_cmp(rsa
->iqmp
, BN_value_one()) > 0)
63 && (BN_cmp(rsa
->iqmp
, rsa
->p
) < 0)
64 /* (d) 1 = (dP . e) mod (p - 1)*/
65 && BN_mod_mul(r
, rsa
->dmp1
, rsa
->e
, p1
, ctx
)
67 /* (e) 1 = (dQ . e) mod (q - 1) */
68 && BN_mod_mul(r
, rsa
->dmq1
, rsa
->e
, q1
, ctx
)
70 /* (f) 1 = (qInv . q) mod p */
71 && BN_mod_mul(r
, rsa
->iqmp
, rsa
->q
, rsa
->p
, ctx
)
81 * Part of the RSA keypair test.
82 * Check that (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2) - 1
84 * See SP800-5bBr1 6.4.1.2.1 Part 5 (c) & (g) - used for both p and q.
86 * (√2)(2^(nbits/2 - 1) = (√2/2)(2^(nbits/2))
88 int rsa_check_prime_factor_range(const BIGNUM
*p
, int nbits
, BN_CTX
*ctx
)
95 shift
= nbits
- BN_num_bits(&bn_inv_sqrt_2
);
97 /* Upper bound check */
98 if (BN_num_bits(p
) != nbits
)
102 low
= BN_CTX_get(ctx
);
106 /* set low = (√2)(2^(nbits/2 - 1) */
107 if (!BN_copy(low
, &bn_inv_sqrt_2
))
112 * We don't have all the bits. bn_inv_sqrt_2 contains a rounded up
113 * value, so there is a very low probability that we'll reject a valid
116 if (!BN_lshift(low
, low
, shift
))
118 } else if (!BN_rshift(low
, low
, -shift
)) {
121 if (BN_cmp(p
, low
) <= 0)
130 * Part of the RSA keypair test.
131 * Check the prime factor (for either p or q)
132 * i.e: p is prime AND GCD(p - 1, e) = 1
134 * See SP800-56Br1 6.4.1.2.3 Step 5 (a to d) & (e to h).
136 int rsa_check_prime_factor(BIGNUM
*p
, BIGNUM
*e
, int nbits
, BN_CTX
*ctx
)
139 BIGNUM
*p1
= NULL
, *gcd
= NULL
;
141 /* (Steps 5 a-b) prime test */
142 if (BN_check_prime(p
, ctx
, NULL
) != 1
143 /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
144 || rsa_check_prime_factor_range(p
, nbits
, ctx
) != 1)
148 p1
= BN_CTX_get(ctx
);
149 gcd
= BN_CTX_get(ctx
);
151 BN_set_flags(p1
, BN_FLG_CONSTTIME
);
152 BN_set_flags(gcd
, BN_FLG_CONSTTIME
);
158 /* (Step 5d) GCD(p-1, e) = 1 */
159 && (BN_copy(p1
, p
) != NULL
)
160 && BN_sub_word(p1
, 1)
161 && BN_gcd(gcd
, p1
, e
, ctx
)
170 * See SP800-56Br1 6.4.1.2.3 Part 6(a-b) Check the private exponent d
172 * (Step 6a) 2^(nBit/2) < d < LCM(p–1, q–1).
173 * (Step 6b) 1 = (d*e) mod LCM(p–1, q–1)
175 int rsa_check_private_exponent(const RSA
*rsa
, int nbits
, BN_CTX
*ctx
)
178 BIGNUM
*r
, *p1
, *q1
, *lcm
, *p1q1
, *gcd
;
180 /* (Step 6a) 2^(nbits/2) < d */
181 if (BN_num_bits(rsa
->d
) <= (nbits
>> 1))
186 p1
= BN_CTX_get(ctx
);
187 q1
= BN_CTX_get(ctx
);
188 lcm
= BN_CTX_get(ctx
);
189 p1q1
= BN_CTX_get(ctx
);
190 gcd
= BN_CTX_get(ctx
);
192 BN_set_flags(r
, BN_FLG_CONSTTIME
);
193 BN_set_flags(p1
, BN_FLG_CONSTTIME
);
194 BN_set_flags(q1
, BN_FLG_CONSTTIME
);
195 BN_set_flags(lcm
, BN_FLG_CONSTTIME
);
196 BN_set_flags(p1q1
, BN_FLG_CONSTTIME
);
197 BN_set_flags(gcd
, BN_FLG_CONSTTIME
);
203 /* LCM(p - 1, q - 1) */
204 && (rsa_get_lcm(ctx
, rsa
->p
, rsa
->q
, lcm
, gcd
, p1
, q1
, p1q1
) == 1)
205 /* (Step 6a) d < LCM(p - 1, q - 1) */
206 && (BN_cmp(rsa
->d
, lcm
) < 0)
207 /* (Step 6b) 1 = (e . d) mod LCM(p - 1, q - 1) */
208 && BN_mod_mul(r
, rsa
->e
, rsa
->d
, lcm
, ctx
)
221 static int bn_is_three(const BIGNUM
*bn
)
223 BIGNUM
*num
= BN_dup(bn
);
224 int ret
= (num
!= NULL
&& BN_sub_word(num
, 3) && BN_is_zero(num
));
229 #endif /* FIPS_MODULE */
231 /* Check exponent is odd, and has a bitlen ranging from [17..256] */
232 int rsa_check_public_exponent(const BIGNUM
*e
)
236 /* For legacy purposes RSA_3 is allowed in non fips mode */
240 #endif /* FIPS_MODULE */
242 bitlen
= BN_num_bits(e
);
243 return (BN_is_odd(e
) && bitlen
> 16 && bitlen
< 257);
247 * SP800-56Br1 6.4.1.2.1 (Step 5i): |p - q| > 2^(nbits/2 - 100)
248 * i.e- numbits(p-q-1) > (nbits/2 -100)
250 int rsa_check_pminusq_diff(BIGNUM
*diff
, const BIGNUM
*p
, const BIGNUM
*q
,
253 int bitlen
= (nbits
>> 1) - 100;
255 if (!BN_sub(diff
, p
, q
))
257 BN_set_negative(diff
, 0);
259 if (BN_is_zero(diff
))
262 if (!BN_sub_word(diff
, 1))
264 return (BN_num_bits(diff
) > bitlen
);
268 * return LCM(p-1, q-1)
270 * Caller should ensure that lcm, gcd, p1, q1, p1q1 are flagged with
273 int rsa_get_lcm(BN_CTX
*ctx
, const BIGNUM
*p
, const BIGNUM
*q
,
274 BIGNUM
*lcm
, BIGNUM
*gcd
, BIGNUM
*p1
, BIGNUM
*q1
,
277 return BN_sub(p1
, p
, BN_value_one()) /* p-1 */
278 && BN_sub(q1
, q
, BN_value_one()) /* q-1 */
279 && BN_mul(p1q1
, p1
, q1
, ctx
) /* (p-1)(q-1) */
280 && BN_gcd(gcd
, p1
, q1
, ctx
)
281 && BN_div(lcm
, NULL
, p1q1
, gcd
, ctx
); /* LCM((p-1, q-1)) */
285 * SP800-56Br1 6.4.2.2 Partial Public Key Validation for RSA refers to
286 * SP800-89 5.3.3 (Explicit) Partial Public Key Validation for RSA
287 * caveat is that the modulus must be as specified in SP800-56Br1
289 int rsa_sp800_56b_check_public(const RSA
*rsa
)
298 if (rsa
->n
== NULL
|| rsa
->e
== NULL
)
303 * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1)
304 * NOTE: changed to allow keys >= 2048
306 nbits
= BN_num_bits(rsa
->n
);
307 if (!rsa_sp800_56b_validate_strength(nbits
, -1)) {
308 RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC
, RSA_R_INVALID_KEY_LENGTH
);
312 if (!BN_is_odd(rsa
->n
)) {
313 RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC
, RSA_R_INVALID_MODULUS
);
316 /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */
317 if (!rsa_check_public_exponent(rsa
->e
)) {
318 RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC
,
319 RSA_R_PUB_EXPONENT_OUT_OF_RANGE
);
323 ctx
= BN_CTX_new_ex(rsa
->libctx
);
325 if (ctx
== NULL
|| gcd
== NULL
)
329 * The modulus is composite, but not a power of a prime.
330 * The modulus has no factors smaller than 752.
332 if (!BN_gcd(gcd
, rsa
->n
, bn_get0_small_factors(), ctx
) || !BN_is_one(gcd
)) {
333 RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC
, RSA_R_INVALID_MODULUS
);
337 ret
= bn_miller_rabin_is_prime(rsa
->n
, 0, ctx
, NULL
, 1, &status
);
338 if (ret
!= 1 || status
!= BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
) {
339 RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC
, RSA_R_INVALID_MODULUS
);
352 * Perform validation of the RSA private key to check that 0 < D < N.
354 int rsa_sp800_56b_check_private(const RSA
*rsa
)
356 if (rsa
->d
== NULL
|| rsa
->n
== NULL
)
358 return BN_cmp(rsa
->d
, BN_value_one()) >= 0 && BN_cmp(rsa
->d
, rsa
->n
) < 0;
362 * RSA key pair validation.
365 * 6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent"
366 * 6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent"
369 * 6.4.1.2.3 "rsakpv1 - crt"
370 * 6.4.1.3.3 "rsakpv2 - crt"
372 int rsa_sp800_56b_check_keypair(const RSA
*rsa
, const BIGNUM
*efixed
,
373 int strength
, int nbits
)
384 RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR
, RSA_R_INVALID_REQUEST
);
387 /* (Step 1): Check Ranges */
388 if (!rsa_sp800_56b_validate_strength(nbits
, strength
))
391 /* If the exponent is known */
392 if (efixed
!= NULL
) {
393 /* (2): Check fixed exponent matches public exponent. */
394 if (BN_cmp(efixed
, rsa
->e
) != 0) {
395 RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR
, RSA_R_INVALID_REQUEST
);
399 /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */
400 if (!rsa_check_public_exponent(rsa
->e
)) {
401 /* exponent out of range */
402 RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR
,
403 RSA_R_PUB_EXPONENT_OUT_OF_RANGE
);
406 /* (Step 3.b): check the modulus */
407 if (nbits
!= BN_num_bits(rsa
->n
)) {
408 RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR
, RSA_R_INVALID_KEYPAIR
);
412 ctx
= BN_CTX_new_ex(rsa
->libctx
);
418 if (r
== NULL
|| !BN_mul(r
, rsa
->p
, rsa
->q
, ctx
))
420 /* (Step 4.c): Check n = pq */
421 if (BN_cmp(rsa
->n
, r
) != 0) {
422 RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR
, RSA_R_INVALID_REQUEST
);
426 /* (Step 5): check prime factors p & q */
427 ret
= rsa_check_prime_factor(rsa
->p
, rsa
->e
, nbits
, ctx
)
428 && rsa_check_prime_factor(rsa
->q
, rsa
->e
, nbits
, ctx
)
429 && (rsa_check_pminusq_diff(r
, rsa
->p
, rsa
->q
, nbits
) > 0)
430 /* (Step 6): Check the private exponent d */
431 && rsa_check_private_exponent(rsa
, nbits
, ctx
)
432 /* 6.4.1.2.3 (Step 7): Check the CRT components */
433 && rsa_check_crt_components(rsa
, ctx
);
435 RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR
, RSA_R_INVALID_KEYPAIR
);