crypto/rsa/rsa_sp800_56b_gen.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 <openssl/core.h>
  14 #include "crypto/bn.h"
  15 #include "crypto/security_bits.h"
  16 #include "rsa_local.h"
  17
  18 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
  19 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
  20 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
  21
  22 /*
  23  * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
  24  * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
  25  * Primes".
  26  *
  27  * Params:
  28  *     rsa  Object used to store primes p & q.
  29  *     test Object used for CAVS testing only.that contains..
  30  *       p1, p2 The returned auxiliary primes for p.
  31  *              If NULL they are not returned.
  32  *       Xpout An optionally returned random number used during generation of p.
  33  *       Xp An optional passed in value (that is random number used during
  34  *          generation of p).
  35  *       Xp1, Xp2 Optionally passed in randomly generated numbers from which
  36  *                auxiliary primes p1 & p2 are calculated. If NULL these values
  37  *                are generated internally.
  38  *       q1, q2 The returned auxiliary primes for q.
  39  *              If NULL they are not returned.
  40  *       Xqout An optionally returned random number used during generation of q.
  41  *       Xq An optional passed in value (that is random number used during
  42  *          generation of q).
  43  *       Xq1, Xq2 Optionally passed in randomly generated numbers from which
  44  *                auxiliary primes q1 & q2 are calculated. If NULL these values
  45  *                are generated internally.
  46  *     nbits The key size in bits (The size of the modulus n).
  47  *     e The public exponent.
  48  *     ctx A BN_CTX object.
  49  *     cb An optional BIGNUM callback.
  50  * Returns: 1 if successful, or  0 otherwise.
  51  * Notes:
  52  *     p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
  53  *     Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
  54  *     (Required for CAVS testing).
  55  */
  56 int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test,
  57                                        int nbits, const BIGNUM *e, BN_CTX *ctx,
  58                                        BN_GENCB *cb)
  59 {
  60     int ret = 0, ok;
  61     /* Temp allocated BIGNUMS */
  62     BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
  63     /* Intermediate BIGNUMS that can be returned for testing */
  64     BIGNUM *p1 = NULL, *p2 = NULL;
  65     BIGNUM *q1 = NULL, *q2 = NULL;
  66     /* Intermediate BIGNUMS that can be input for testing */
  67     BIGNUM *Xpout = NULL, *Xqout = NULL;
  68     BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL;
  69     BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL;
  70
  71 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
  72     if (test != NULL) {
  73         Xp1 = test->Xp1;
  74         Xp2 = test->Xp2;
  75         Xq1 = test->Xq1;
  76         Xq2 = test->Xq2;
  77         Xp = test->Xp;
  78         Xq = test->Xq;
  79         p1 = test->p1;
  80         p2 = test->p2;
  81         q1 = test->q1;
  82         q2 = test->q2;
  83     }
  84 #endif
  85
  86     /* (Step 1) Check key length
  87      * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
  88      * Signature Generation and Key Agree/Transport.
  89      */
  90     if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
  91         ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
  92         return 0;
  93     }
  94
  95     if (!ossl_rsa_check_public_exponent(e)) {
  96         ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
  97         return 0;
  98     }
  99
 100     /* (Step 3) Determine strength and check rand generator strength is ok -
 101      * this step is redundant because the generator always returns a higher
 102      * strength than is required.
 103      */
 104
 105     BN_CTX_start(ctx);
 106     tmp = BN_CTX_get(ctx);
 107     Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx);
 108     Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
 109     if (tmp == NULL || Xpo == NULL || Xqo == NULL)
 110         goto err;
 111     BN_set_flags(Xpo, BN_FLG_CONSTTIME);
 112     BN_set_flags(Xqo, BN_FLG_CONSTTIME);
 113
 114     if (rsa->p == NULL)
 115         rsa->p = BN_secure_new();
 116     if (rsa->q == NULL)
 117         rsa->q = BN_secure_new();
 118     if (rsa->p == NULL || rsa->q == NULL)
 119         goto err;
 120     BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
 121     BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
 122
 123     /* (Step 4) Generate p, Xp */
 124     if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
 125                                           nbits, e, ctx, cb))
 126         goto err;
 127     for(;;) {
 128         /* (Step 5) Generate q, Xq*/
 129         if (!bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
 130                                               Xq2, nbits, e, ctx, cb))
 131             goto err;
 132
 133         /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
 134         ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
 135         if (ok < 0)
 136             goto err;
 137         if (ok == 0)
 138             continue;
 139
 140         /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
 141         ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
 142         if (ok < 0)
 143             goto err;
 144         if (ok == 0)
 145             continue;
 146         break; /* successfully finished */
 147     }
 148     rsa->dirty_cnt++;
 149     ret = 1;
 150 err:
 151     /* Zeroize any internally generated values that are not returned */
 152     if (Xpo != Xpout)
 153         BN_clear(Xpo);
 154     if (Xqo != Xqout)
 155         BN_clear(Xqo);
 156     BN_clear(tmp);
 157
 158     BN_CTX_end(ctx);
 159     return ret;
 160 }
 161
 162 /*
 163  * Validates the RSA key size based on the target strength.
 164  * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
 165  *
 166  * Params:
 167  *     nbits The key size in bits.
 168  *     strength The target strength in bits. -1 means the target
 169  *              strength is unknown.
 170  * Returns: 1 if the key size matches the target strength, or 0 otherwise.
 171  */
 172 int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength)
 173 {
 174     int s = (int)ifc_ffc_compute_security_bits(nbits);
 175 #ifdef FIPS_MODULE
 176     if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
 177             || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
 178         ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS);
 179         return 0;
 180     }
 181 #endif
 182     if (strength != -1 && s != strength) {
 183         ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH);
 184         return 0;
 185     }
 186     return 1;
 187 }
 188
 189 /*
 190  *
 191  * Using p & q, calculate other required parameters such as n, d.
 192  * as well as the CRT parameters dP, dQ, qInv.
 193  *
 194  * See SP800-56Br1
 195  *   6.3.1.1 rsakpg1 - basic (Steps 3-4)
 196  *   6.3.1.3 rsakpg1 - crt   (Step 5)
 197  *
 198  * Params:
 199  *     rsa An rsa object.
 200  *     nbits The key size.
 201  *     e The public exponent.
 202  *     ctx A BN_CTX object.
 203  * Notes:
 204  *   There is a small chance that the generated d will be too small.
 205  * Returns: -1 = error,
 206  *           0 = d is too small,
 207  *           1 = success.
 208  */
 209 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
 210                                              const BIGNUM *e, BN_CTX *ctx)
 211 {
 212     int ret = -1;
 213     BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
 214
 215     BN_CTX_start(ctx);
 216     p1 = BN_CTX_get(ctx);
 217     q1 = BN_CTX_get(ctx);
 218     lcm = BN_CTX_get(ctx);
 219     p1q1 = BN_CTX_get(ctx);
 220     gcd = BN_CTX_get(ctx);
 221     if (gcd == NULL)
 222         goto err;
 223
 224     BN_set_flags(p1, BN_FLG_CONSTTIME);
 225     BN_set_flags(q1, BN_FLG_CONSTTIME);
 226     BN_set_flags(lcm, BN_FLG_CONSTTIME);
 227     BN_set_flags(p1q1, BN_FLG_CONSTTIME);
 228     BN_set_flags(gcd, BN_FLG_CONSTTIME);
 229
 230     /* LCM((p-1, q-1)) */
 231     if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
 232         goto err;
 233
 234     /* copy e */
 235     BN_free(rsa->e);
 236     rsa->e = BN_dup(e);
 237     if (rsa->e == NULL)
 238         goto err;
 239
 240     BN_clear_free(rsa->d);
 241     /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
 242     rsa->d = BN_secure_new();
 243     if (rsa->d == NULL)
 244         goto err;
 245     BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
 246     if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
 247         goto err;
 248
 249     /* (Step 3) return an error if d is too small */
 250     if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
 251         ret = 0;
 252         goto err;
 253     }
 254
 255     /* (Step 4) n = pq */
 256     if (rsa->n == NULL)
 257         rsa->n = BN_new();
 258     if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
 259         goto err;
 260
 261     /* (Step 5a) dP = d mod (p-1) */
 262     if (rsa->dmp1 == NULL)
 263         rsa->dmp1 = BN_secure_new();
 264     if (rsa->dmp1 == NULL)
 265             goto err;
 266     BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
 267     if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
 268         goto err;
 269
 270     /* (Step 5b) dQ = d mod (q-1) */
 271     if (rsa->dmq1 == NULL)
 272         rsa->dmq1 = BN_secure_new();
 273     if (rsa->dmq1 == NULL)
 274             goto err;
 275     BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
 276     if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
 277         goto err;
 278
 279     /* (Step 5c) qInv = (inverse of q) mod p */
 280     BN_free(rsa->iqmp);
 281     rsa->iqmp = BN_secure_new();
 282     if (rsa->iqmp == NULL)
 283             goto err;
 284     BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
 285     if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
 286         goto err;
 287
 288     rsa->dirty_cnt++;
 289     ret = 1;
 290 err:
 291     if (ret != 1) {
 292         BN_free(rsa->e);
 293         rsa->e = NULL;
 294         BN_free(rsa->d);
 295         rsa->d = NULL;
 296         BN_free(rsa->n);
 297         rsa->n = NULL;
 298         BN_free(rsa->iqmp);
 299         rsa->iqmp = NULL;
 300         BN_free(rsa->dmq1);
 301         rsa->dmq1 = NULL;
 302         BN_free(rsa->dmp1);
 303         rsa->dmp1 = NULL;
 304     }
 305     BN_clear(p1);
 306     BN_clear(q1);
 307     BN_clear(lcm);
 308     BN_clear(p1q1);
 309     BN_clear(gcd);
 310
 311     BN_CTX_end(ctx);
 312     return ret;
 313 }
 314
 315 /*
 316  * Generate a SP800-56B RSA key.
 317  *
 318  * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
 319  *    6.3.1.1 rsakpg1 - basic
 320  *    6.3.1.3 rsakpg1 - crt
 321  *
 322  * See also FIPS 186-4 Section B.3.6
 323  * "Generation of Probable Primes with Conditions Based on Auxiliary
 324  * Probable Primes."
 325  *
 326  * Params:
 327  *     rsa The rsa object.
 328  *     nbits The intended key size in bits.
 329  *     efixed The public exponent. If NULL a default of 65537 is used.
 330  *     cb An optional BIGNUM callback.
 331  * Returns: 1 if successfully generated otherwise it returns 0.
 332  */
 333 int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
 334                                     BN_GENCB *cb)
 335 {
 336     int ret = 0;
 337     int ok;
 338     BN_CTX *ctx = NULL;
 339     BIGNUM *e = NULL;
 340     RSA_ACVP_TEST *info = NULL;
 341
 342 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
 343     info = rsa->acvp_test;
 344 #endif
 345
 346     /* (Steps 1a-1b) : Currently ignores the strength check */
 347     if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1))
 348         return 0;
 349
 350     ctx = BN_CTX_new_ex(rsa->libctx);
 351     if (ctx == NULL)
 352         return 0;
 353
 354     /* Set default if e is not passed in */
 355     if (efixed == NULL) {
 356         e = BN_new();
 357         if (e == NULL || !BN_set_word(e, 65537))
 358             goto err;
 359     } else {
 360         e = (BIGNUM *)efixed;
 361     }
 362     /* (Step 1c) fixed exponent is checked later .*/
 363
 364     for (;;) {
 365         /* (Step 2) Generate prime factors */
 366         if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb))
 367             goto err;
 368         /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
 369         ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
 370         if (ok < 0)
 371             goto err;
 372         if (ok > 0)
 373             break;
 374         /* Gets here if computed d is too small - so try again */
 375     }
 376
 377     /* (Step 6) Do pairwise test - optional validity test has been omitted */
 378     ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx);
 379 err:
 380     if (efixed == NULL)
 381         BN_free(e);
 382     BN_CTX_free(ctx);
 383     return ret;
 384 }
 385
 386 /*
 387  * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
 388  * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
 389  *
 390  * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
 391  */
 392 int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
 393 {
 394     int ret = 0;
 395     BIGNUM *k, *tmp;
 396
 397     BN_CTX_start(ctx);
 398     tmp = BN_CTX_get(ctx);
 399     k = BN_CTX_get(ctx);
 400     if (k == NULL)
 401         goto err;
 402     BN_set_flags(k, BN_FLG_CONSTTIME);
 403
 404     ret = (BN_set_word(k, 2)
 405           && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
 406           && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
 407           && BN_cmp(k, tmp) == 0);
 408     if (ret == 0)
 409         ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE);
 410 err:
 411     BN_CTX_end(ctx);
 412     return ret;
 413 }