crypto/rsa/rsa_sp800_56b_check.c

   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  * √2/2 = 0.707106781186547524400 = 0.B504F333F9DE6484597D8
  79  * 0.B504F334 gives an approximation to 11 decimal places.
  80  * The range is then from
  81  *   0xB504F334_0000.......................000 to
  82  *   0xFFFFFFFF_FFFF.......................FFF
  83  */
  84 int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx)
  85 {
  86     int ret = 0;
  87     BIGNUM *tmp, *low;
  88
  89     nbits >>= 1;
  90
  91     /* Upper bound check */
  92     if (BN_num_bits(p) != nbits)
  93         return 0;
  94
  95     BN_CTX_start(ctx);
  96     tmp = BN_CTX_get(ctx);
  97     low = BN_CTX_get(ctx);
  98
  99     /* set low = (√2)(2^(nbits/2 - 1) */
 100     if (low == NULL || !BN_set_word(tmp, 0xB504F334))
 101         goto err;
 102
 103     if (nbits >= 32) {
 104         if (!BN_lshift(low, tmp, nbits - 32))
 105             goto err;
 106     } else if (!BN_rshift(low, tmp, 32 - nbits)) {
 107         goto err;
 108     }
 109     if (BN_cmp(p, low) < 0)
 110         goto err;
 111     ret = 1;
 112 err:
 113     BN_CTX_end(ctx);
 114     return ret;
 115 }
 116
 117 /*
 118  * Part of the RSA keypair test.
 119  * Check the prime factor (for either p or q)
 120  * i.e: p is prime AND GCD(p - 1, e) = 1
 121  *
 122  * See SP800-56Br1 6.4.1.2.3 Step 5 (a to d) & (e to h).
 123  */
 124 int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
 125 {
 126     int ret = 0;
 127     BIGNUM *p1 = NULL, *gcd = NULL;
 128
 129     /* (Steps 5 a-b) prime test */
 130     if (BN_check_prime(p, ctx, NULL) != 1
 131             /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
 132             || rsa_check_prime_factor_range(p, nbits, ctx) != 1)
 133         return 0;
 134
 135     BN_CTX_start(ctx);
 136     p1 = BN_CTX_get(ctx);
 137     gcd = BN_CTX_get(ctx);
 138     ret = (gcd != NULL)
 139           /* (Step 5d) GCD(p-1, e) = 1 */
 140           && (BN_copy(p1, p) != NULL)
 141           && BN_sub_word(p1, 1)
 142           && BN_gcd(gcd, p1, e, ctx)
 143           && BN_is_one(gcd);
 144
 145     BN_clear(p1);
 146     BN_CTX_end(ctx);
 147     return ret;
 148 }
 149
 150 /*
 151  * See SP800-56Br1 6.4.1.2.3 Part 6(a-b) Check the private exponent d
 152  * satisfies:
 153  *     (Step 6a) 2^(nBit/2) < d < LCM(p–1, q–1).
 154  *     (Step 6b) 1 = (d*e) mod LCM(p–1, q–1)
 155  */
 156 int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
 157 {
 158     int ret;
 159     BIGNUM *r, *p1, *q1, *lcm, *p1q1, *gcd;
 160
 161     /* (Step 6a) 2^(nbits/2) < d */
 162     if (BN_num_bits(rsa->d) <= (nbits >> 1))
 163         return 0;
 164
 165     BN_CTX_start(ctx);
 166     r = BN_CTX_get(ctx);
 167     p1 = BN_CTX_get(ctx);
 168     q1 = BN_CTX_get(ctx);
 169     lcm = BN_CTX_get(ctx);
 170     p1q1 = BN_CTX_get(ctx);
 171     gcd = BN_CTX_get(ctx);
 172     ret = (gcd != NULL
 173           /* LCM(p - 1, q - 1) */
 174           && (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) == 1)
 175           /* (Step 6a) d < LCM(p - 1, q - 1) */
 176           && (BN_cmp(rsa->d, lcm) < 0)
 177           /* (Step 6b) 1 = (e . d) mod LCM(p - 1, q - 1) */
 178           && BN_mod_mul(r, rsa->e, rsa->d, lcm, ctx)
 179           && BN_is_one(r));
 180
 181     BN_clear(p1);
 182     BN_clear(q1);
 183     BN_clear(lcm);
 184     BN_clear(gcd);
 185     BN_CTX_end(ctx);
 186     return ret;
 187 }
 188
 189 /* Check exponent is odd, and has a bitlen ranging from [17..256] */
 190 int rsa_check_public_exponent(const BIGNUM *e)
 191 {
 192     int bitlen = BN_num_bits(e);
 193
 194     return (BN_is_odd(e) &&  bitlen > 16 && bitlen < 257);
 195 }
 196
 197 /*
 198  * SP800-56Br1 6.4.1.2.1 (Step 5i): |p - q| > 2^(nbits/2 - 100)
 199  * i.e- numbits(p-q-1) > (nbits/2 -100)
 200  */
 201 int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
 202                            int nbits)
 203 {
 204     int bitlen = (nbits >> 1) - 100;
 205
 206     if (!BN_sub(diff, p, q))
 207         return -1;
 208     BN_set_negative(diff, 0);
 209
 210     if (BN_is_zero(diff))
 211         return 0;
 212
 213     if (!BN_sub_word(diff, 1))
 214         return -1;
 215     return (BN_num_bits(diff) > bitlen);
 216 }
 217
 218 /* return LCM(p-1, q-1) */
 219 int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
 220                 BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
 221                 BIGNUM *p1q1)
 222 {
 223     return BN_sub(p1, p, BN_value_one())    /* p-1 */
 224            && BN_sub(q1, q, BN_value_one()) /* q-1 */
 225            && BN_mul(p1q1, p1, q1, ctx)     /* (p-1)(q-1) */
 226            && BN_gcd(gcd, p1, q1, ctx)
 227            && BN_div(lcm, NULL, p1q1, gcd, ctx); /* LCM((p-1, q-1)) */
 228 }
 229
 230 /*
 231  * SP800-56Br1 6.4.2.2 Partial Public Key Validation for RSA refers to
 232  * SP800-89 5.3.3 (Explicit) Partial Public Key Validation for RSA
 233  * caveat is that the modulus must be as specified in SP800-56Br1
 234  */
 235 int rsa_sp800_56b_check_public(const RSA *rsa)
 236 {
 237     int ret = 0, nbits, status;
 238     BN_CTX *ctx = NULL;
 239     BIGNUM *gcd = NULL;
 240
 241     if (rsa->n == NULL || rsa->e == NULL)
 242         return 0;
 243
 244     /*
 245      * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1)
 246      * NOTE: changed to allow keys >= 2048
 247      */
 248     nbits = BN_num_bits(rsa->n);
 249     if (!rsa_sp800_56b_validate_strength(nbits, -1)) {
 250         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_KEY_LENGTH);
 251         return 0;
 252     }
 253     if (!BN_is_odd(rsa->n)) {
 254         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
 255         return 0;
 256     }
 257
 258     /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */
 259     if (!rsa_check_public_exponent(rsa->e)) {
 260         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC,
 261                RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
 262         return 0;
 263     }
 264
 265     ctx = BN_CTX_new();
 266     gcd = BN_new();
 267     if (ctx == NULL || gcd == NULL)
 268         goto err;
 269
 270     /* (Steps d-f):
 271      * The modulus is composite, but not a power of a prime.
 272      * The modulus has no factors smaller than 752.
 273      */
 274     if (!BN_gcd(gcd, rsa->n, bn_get0_small_factors(), ctx) || !BN_is_one(gcd)) {
 275         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
 276         goto err;
 277     }
 278
 279     ret = bn_miller_rabin_is_prime(rsa->n, 0, ctx, NULL, 1, &status);
 280     if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) {
 281         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
 282         ret = 0;
 283         goto err;
 284     }
 285
 286     ret = 1;
 287 err:
 288     BN_free(gcd);
 289     BN_CTX_free(ctx);
 290     return ret;
 291 }
 292
 293 /*
 294  * Perform validation of the RSA private key to check that 0 < D < N.
 295  */
 296 int rsa_sp800_56b_check_private(const RSA *rsa)
 297 {
 298     if (rsa->d == NULL || rsa->n == NULL)
 299         return 0;
 300     return BN_cmp(rsa->d, BN_value_one()) >= 0 && BN_cmp(rsa->d, rsa->n) < 0;
 301 }
 302
 303 /*
 304  * RSA key pair validation.
 305  *
 306  * SP800-56Br1.
 307  *    6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent"
 308  *    6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent"
 309  *
 310  * It uses:
 311  *     6.4.1.2.3 "rsakpv1 - crt"
 312  *     6.4.1.3.3 "rsakpv2 - crt"
 313  */
 314 int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
 315                                 int strength, int nbits)
 316 {
 317     int ret = 0;
 318     BN_CTX *ctx = NULL;
 319     BIGNUM *r = NULL;
 320
 321     if (rsa->p == NULL
 322             || rsa->q == NULL
 323             || rsa->e == NULL
 324             || rsa->d == NULL
 325             || rsa->n == NULL) {
 326         RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
 327         return 0;
 328     }
 329     /* (Step 1): Check Ranges */
 330     if (!rsa_sp800_56b_validate_strength(nbits, strength))
 331         return 0;
 332
 333     /* If the exponent is known */
 334     if (efixed != NULL) {
 335         /* (2): Check fixed exponent matches public exponent. */
 336         if (BN_cmp(efixed, rsa->e) != 0) {
 337             RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
 338             return 0;
 339         }
 340     }
 341     /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */
 342     if (!rsa_check_public_exponent(rsa->e)) {
 343         /* exponent out of range */
 344         RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR,
 345                RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
 346         return 0;
 347     }
 348     /* (Step 3.b): check the modulus */
 349     if (nbits != BN_num_bits(rsa->n)) {
 350         RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
 351         return 0;
 352     }
 353
 354     ctx = BN_CTX_new();
 355     if (ctx == NULL)
 356         return 0;
 357
 358     BN_CTX_start(ctx);
 359     r = BN_CTX_get(ctx);
 360     if (r == NULL || !BN_mul(r, rsa->p, rsa->q, ctx))
 361         goto err;
 362     /* (Step 4.c): Check n = pq */
 363     if (BN_cmp(rsa->n, r) != 0) {
 364         RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
 365         goto err;
 366     }
 367
 368     /* (Step 5): check prime factors p & q */
 369     ret = rsa_check_prime_factor(rsa->p, rsa->e, nbits, ctx)
 370           && rsa_check_prime_factor(rsa->q, rsa->e, nbits, ctx)
 371           && (rsa_check_pminusq_diff(r, rsa->p, rsa->q, nbits) > 0)
 372           /* (Step 6): Check the private exponent d */
 373           && rsa_check_private_exponent(rsa, nbits, ctx)
 374           /* 6.4.1.2.3 (Step 7): Check the CRT components */
 375           && rsa_check_crt_components(rsa, ctx);
 376     if (ret != 1)
 377         RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
 378
 379 err:
 380     BN_clear(r);
 381     BN_CTX_end(ctx);
 382     BN_CTX_free(ctx);
 383     return ret;
 384 }