crypto/bn/bn_rsa_fips186_4.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 /*
  12  * According to NIST SP800-131A "Transitioning the use of cryptographic
  13  * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
  14  * allowed for signatures (Table 2) or key transport (Table 5). In the code
  15  * below any attempt to generate 1024 bit RSA keys will result in an error (Note
  16  * that digital signature verification can still use deprecated 1024 bit keys).
  17  *
  18  * Also see FIPS1402IG A.14
  19  * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
  20  * must be generated before the module generates the RSA primes p and q.
  21  * Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
  22  * 3072 bits only, the min/max total length of the auxiliary primes.
  23  * When implementing the RSA signature generation algorithm
  24  * with other approved RSA modulus sizes, the vendor shall use the limitations
  25  * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
  26  * FIPS 186-4 whose length does not exceed that of the implementation's RSA
  27  * modulus. In particular, when generating the primes for the 4096-bit RSA
  28  * modulus the limitations stated for the 3072-bit modulus shall apply.
  29  */
  30 #include <stdio.h>
  31 #include <openssl/bn.h>
  32 #include "bn_local.h"
  33 #include "crypto/bn.h"
  34
  35 /*
  36  * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
  37  *
  38  * Params:
  39  *     nbits The key size in bits.
  40  * Returns:
  41  *     The minimum size of the auxiliary primes or 0 if nbits is invalid.
  42  */
  43 static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
  44 {
  45     if (nbits >= 3072)
  46         return 171;
  47     if (nbits == 2048)
  48         return 141;
  49     return 0;
  50 }
  51
  52 /*
  53  * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
  54  * len(q1) + len(q2) for p,q Probable Primes".
  55  *
  56  * Params:
  57  *     nbits The key size in bits.
  58  * Returns:
  59  *     The maximum length or 0 if nbits is invalid.
  60  */
  61 static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
  62 {
  63     if (nbits >= 3072)
  64         return 1518;
  65     if (nbits == 2048)
  66         return 1007;
  67     return 0;
  68 }
  69
  70 /*
  71  * FIPS 186-4 Table C.3 for error probability of 2^-100
  72  * Minimum number of Miller Rabin Rounds for p1, p2, q1 & q2.
  73  *
  74  * Params:
  75  *     aux_prime_bits The auxiliary prime size in bits.
  76  * Returns:
  77  *     The minimum number of Miller Rabin Rounds for an auxiliary prime, or
  78  *     0 if aux_prime_bits is invalid.
  79  */
  80 static int bn_rsa_fips186_4_aux_prime_MR_min_checks(int aux_prime_bits)
  81 {
  82     if (aux_prime_bits > 170)
  83         return 27;
  84     if (aux_prime_bits > 140)
  85         return 32;
  86     return 0; /* Error case */
  87 }
  88
  89 /*
  90  * FIPS 186-4 Table C.3 for error probability of 2^-100
  91  * Minimum number of Miller Rabin Rounds for p, q.
  92  *
  93  * Params:
  94  *     nbits The key size in bits.
  95  * Returns:
  96  *     The minimum number of Miller Rabin Rounds required,
  97  *     or 0 if nbits is invalid.
  98  */
  99 int bn_rsa_fips186_4_prime_MR_min_checks(int nbits)
 100 {
 101     if (nbits >= 3072) /* > 170 */
 102         return 3;
 103     if (nbits == 2048) /* > 140 */
 104         return 4;
 105     return 0; /* Error case */
 106 }
 107
 108 /*
 109  * Find the first odd integer that is a probable prime.
 110  *
 111  * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
 112  *
 113  * Params:
 114  *     Xp1 The passed in starting point to find a probably prime.
 115  *     p1 The returned probable prime (first odd integer >= Xp1)
 116  *     ctx A BN_CTX object.
 117  *     cb An optional BIGNUM callback.
 118  * Returns: 1 on success otherwise it returns 0.
 119  */
 120 static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
 121                                                 BIGNUM *p1, BN_CTX *ctx,
 122                                                 BN_GENCB *cb)
 123 {
 124     int ret = 0;
 125     int i = 0;
 126     int checks = bn_rsa_fips186_4_aux_prime_MR_min_checks(BN_num_bits(Xp1));
 127
 128     if (checks == 0 || BN_copy(p1, Xp1) == NULL)
 129         return 0;
 130
 131     /* Find the first odd number >= Xp1 that is probably prime */
 132     for(;;) {
 133         i++;
 134         BN_GENCB_call(cb, 0, i);
 135         /* MR test with trial division */
 136         if (BN_is_prime_fasttest_ex(p1, checks, ctx, 1, cb))
 137             break;
 138         /* Get next odd number */
 139         if (!BN_add_word(p1, 2))
 140             goto err;
 141     }
 142     BN_GENCB_call(cb, 2, i);
 143     ret = 1;
 144 err:
 145     return ret;
 146 }
 147
 148 /*
 149  * Generate a probable prime (p or q).
 150  *
 151  * See FIPS 186-4 B.3.6 (Steps 4 & 5)
 152  *
 153  * Params:
 154  *     p The returned probable prime.
 155  *     Xpout An optionally returned random number used during generation of p.
 156  *     p1, p2 The returned auxiliary primes. If NULL they are not returned.
 157  *     Xp An optional passed in value (that is random number used during
 158  *        generation of p).
 159  *     Xp1, Xp2 Optional passed in values that are normally generated
 160  *              internally. Used to find p1, p2.
 161  *     nlen The bit length of the modulus (the key size).
 162  *     e The public exponent.
 163  *     ctx A BN_CTX object.
 164  *     cb An optional BIGNUM callback.
 165  * Returns: 1 on success otherwise it returns 0.
 166  */
 167 int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
 168                                      BIGNUM *p1, BIGNUM *p2,
 169                                      const BIGNUM *Xp, const BIGNUM *Xp1,
 170                                      const BIGNUM *Xp2, int nlen,
 171                                      const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
 172 {
 173     int ret = 0;
 174     BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
 175     int bitlen;
 176
 177     if (p == NULL || Xpout == NULL)
 178         return 0;
 179
 180     BN_CTX_start(ctx);
 181
 182     p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
 183     p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
 184     Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
 185     Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
 186     if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
 187         goto err;
 188
 189     bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
 190     if (bitlen == 0)
 191         goto err;
 192
 193     /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
 194     if (Xp1 == NULL) {
 195         /* Set the top and bottom bits to make it odd and the correct size */
 196         if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
 197                              ctx))
 198             goto err;
 199     }
 200     /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
 201     if (Xp2 == NULL) {
 202         /* Set the top and bottom bits to make it odd and the correct size */
 203         if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
 204                              ctx))
 205             goto err;
 206     }
 207
 208     /* (Steps 4.2/5.2) - find first auxiliary probable primes */
 209     if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
 210             || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
 211         goto err;
 212     /* (Table B.1) auxiliary prime Max length check */
 213     if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
 214             bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
 215         goto err;
 216     /* (Steps 4.3/5.3) - generate prime */
 217     if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
 218         goto err;
 219     ret = 1;
 220 err:
 221     /* Zeroize any internally generated values that are not returned */
 222     if (p1 == NULL)
 223         BN_clear(p1i);
 224     if (p2 == NULL)
 225         BN_clear(p2i);
 226     if (Xp1 == NULL)
 227         BN_clear(Xp1i);
 228     if (Xp2 == NULL)
 229         BN_clear(Xp2i);
 230     BN_CTX_end(ctx);
 231     return ret;
 232 }
 233
 234 /*
 235  * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
 236  * prime numbers and the Chinese Remainder Theorem.
 237  *
 238  * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
 239  * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
 240  *
 241  * Params:
 242  *     Y The returned prime factor (private_prime_factor) of the modulus n.
 243  *     X The returned random number used during generation of the prime factor.
 244  *     Xin An optional passed in value for X used for testing purposes.
 245  *     r1 An auxiliary prime.
 246  *     r2 An auxiliary prime.
 247  *     nlen The desired length of n (the RSA modulus).
 248  *     e The public exponent.
 249  *     ctx A BN_CTX object.
 250  *     cb An optional BIGNUM callback object.
 251  * Returns: 1 on success otherwise it returns 0.
 252  * Assumptions:
 253  *     Y, X, r1, r2, e are not NULL.
 254  */
 255 int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
 256                                   const BIGNUM *r1, const BIGNUM *r2, int nlen,
 257                                   const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
 258 {
 259     int ret = 0;
 260     int i, imax;
 261     int bits = nlen >> 1;
 262     int checks = bn_rsa_fips186_4_prime_MR_min_checks(nlen);
 263     BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
 264
 265     if (checks == 0)
 266         return 0;
 267     BN_CTX_start(ctx);
 268
 269     R = BN_CTX_get(ctx);
 270     tmp = BN_CTX_get(ctx);
 271     r1r2x2 = BN_CTX_get(ctx);
 272     y1 = BN_CTX_get(ctx);
 273     r1x2 = BN_CTX_get(ctx);
 274     if (r1x2 == NULL)
 275         goto err;
 276
 277     if (Xin != NULL && BN_copy(X, Xin) == NULL)
 278         goto err;
 279
 280     if (!(BN_lshift1(r1x2, r1)
 281             /* (Step 1) GCD(2r1, r2) = 1 */
 282             && BN_gcd(tmp, r1x2, r2, ctx)
 283             && BN_is_one(tmp)
 284             /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
 285             && BN_mod_inverse(R, r2, r1x2, ctx)
 286             && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
 287             && BN_mod_inverse(tmp, r1x2, r2, ctx)
 288             && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
 289             && BN_sub(R, R, tmp)
 290             /* Calculate 2r1r2 */
 291             && BN_mul(r1r2x2, r1x2, r2, ctx)))
 292         goto err;
 293     /* Make positive by adding the modulus */
 294     if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
 295         goto err;
 296
 297     imax = 5 * bits; /* max = 5/2 * nbits */
 298     for (;;) {
 299         if (Xin == NULL) {
 300             /*
 301              * (Step 3) Choose Random X such that
 302              *    sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1.
 303              *
 304              * For the lower bound:
 305              *   sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2)
 306              *   where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE...
 307              *   so largest number will have B5... as the top byte
 308              *   Setting the top 2 bits gives 0xC0.
 309              */
 310             if (!BN_priv_rand_ex(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY,
 311                                  ctx))
 312                 goto end;
 313         }
 314         /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
 315         if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
 316             goto err;
 317         /* (Step 5) */
 318         i = 0;
 319         for (;;) {
 320             /* (Step 6) */
 321             if (BN_num_bits(Y) > bits) {
 322                 if (Xin == NULL)
 323                     break; /* Randomly Generated X so Go back to Step 3 */
 324                 else
 325                     goto err; /* X is not random so it will always fail */
 326             }
 327             BN_GENCB_call(cb, 0, 2);
 328
 329             /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
 330             if (BN_copy(y1, Y) == NULL
 331                     || !BN_sub_word(y1, 1)
 332                     || !BN_gcd(tmp, y1, e, ctx))
 333                 goto err;
 334             if (BN_is_one(tmp)
 335                     && BN_is_prime_fasttest_ex(Y, checks, ctx, 1, cb))
 336                 goto end;
 337             /* (Step 8-10) */
 338             if (++i >= imax || !BN_add(Y, Y, r1r2x2))
 339                 goto err;
 340         }
 341     }
 342 end:
 343     ret = 1;
 344     BN_GENCB_call(cb, 3, 0);
 345 err:
 346     BN_clear(y1);
 347     BN_CTX_end(ctx);
 348     return ret;
 349 }