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