7cf6241dee6126177f06d95806dfc366690ad2ff
[openssl.git] / crypto / rsa / rsa_sp800_56b_check.c
1 /*
2  * Copyright 2018-2020 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 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
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, status;
241 #ifdef FIPS_MODULE
242     int nbits;
243 #endif
244     BN_CTX *ctx = NULL;
245     BIGNUM *gcd = NULL;
246
247     if (rsa->n == NULL || rsa->e == NULL)
248         return 0;
249
250 #ifdef FIPS_MODULE
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     }
260 #endif
261     if (!BN_is_odd(rsa->n)) {
262         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
263         return 0;
264     }
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
272     ctx = BN_CTX_new_ex(rsa->libctx);
273     gcd = BN_new();
274     if (ctx == NULL || gcd == NULL)
275         goto err;
276
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
286     ret = bn_miller_rabin_is_prime(rsa->n, 0, ctx, NULL, 1, &status);
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
361     ctx = BN_CTX_new_ex(rsa->libctx);
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 }