crypto/bn/bn_rsa_fips186_4.c

   1 /*
   2  * Copyright 2018-2021 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 /*
  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 #include "internal/nelem.h"
  35
  36 #if BN_BITS2 == 64
  37 # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
  38 #else
  39 # define BN_DEF(lo, hi) lo, hi
  40 #endif
  41
  42 /* 1 / sqrt(2) * 2^256, rounded up */
  43 static const BN_ULONG inv_sqrt_2_val[] = {
  44     BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL),
  45     BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL)
  46 };
  47
  48 const BIGNUM ossl_bn_inv_sqrt_2 = {
  49     (BN_ULONG *)inv_sqrt_2_val,
  50     OSSL_NELEM(inv_sqrt_2_val),
  51     OSSL_NELEM(inv_sqrt_2_val),
  52     0,
  53     BN_FLG_STATIC_DATA
  54 };
  55
  56 /*
  57  * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
  58  *
  59  * Params:
  60  *     nbits The key size in bits.
  61  * Returns:
  62  *     The minimum size of the auxiliary primes or 0 if nbits is invalid.
  63  */
  64 static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
  65 {
  66     if (nbits >= 3072)
  67         return 171;
  68     if (nbits >= 2048)
  69         return 141;
  70     return 0;
  71 }
  72
  73 /*
  74  * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
  75  * len(q1) + len(q2) for p,q Probable Primes".
  76  *
  77  * Params:
  78  *     nbits The key size in bits.
  79  * Returns:
  80  *     The maximum length or 0 if nbits is invalid.
  81  */
  82 static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
  83 {
  84     if (nbits >= 3072)
  85         return 1518;
  86     if (nbits >= 2048)
  87         return 1007;
  88     return 0;
  89 }
  90
  91 /*
  92  * Find the first odd integer that is a probable prime.
  93  *
  94  * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
  95  *
  96  * Params:
  97  *     Xp1 The passed in starting point to find a probably prime.
  98  *     p1 The returned probable prime (first odd integer >= Xp1)
  99  *     ctx A BN_CTX object.
 100  *     cb An optional BIGNUM callback.
 101  * Returns: 1 on success otherwise it returns 0.
 102  */
 103 static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
 104                                                 BIGNUM *p1, BN_CTX *ctx,
 105                                                 BN_GENCB *cb)
 106 {
 107     int ret = 0;
 108     int i = 0;
 109
 110     if (BN_copy(p1, Xp1) == NULL)
 111         return 0;
 112     BN_set_flags(p1, BN_FLG_CONSTTIME);
 113
 114     /* Find the first odd number >= Xp1 that is probably prime */
 115     for(;;) {
 116         i++;
 117         BN_GENCB_call(cb, 0, i);
 118         /* MR test with trial division */
 119         if (BN_check_prime(p1, ctx, cb))
 120             break;
 121         /* Get next odd number */
 122         if (!BN_add_word(p1, 2))
 123             goto err;
 124     }
 125     BN_GENCB_call(cb, 2, i);
 126     ret = 1;
 127 err:
 128     return ret;
 129 }
 130
 131 /*
 132  * Generate a probable prime (p or q).
 133  *
 134  * See FIPS 186-4 B.3.6 (Steps 4 & 5)
 135  *
 136  * Params:
 137  *     p The returned probable prime.
 138  *     Xpout An optionally returned random number used during generation of p.
 139  *     p1, p2 The returned auxiliary primes. If NULL they are not returned.
 140  *     Xp An optional passed in value (that is random number used during
 141  *        generation of p).
 142  *     Xp1, Xp2 Optional passed in values that are normally generated
 143  *              internally. Used to find p1, p2.
 144  *     nlen The bit length of the modulus (the key size).
 145  *     e The public exponent.
 146  *     ctx A BN_CTX object.
 147  *     cb An optional BIGNUM callback.
 148  * Returns: 1 on success otherwise it returns 0.
 149  */
 150 int ossl_bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
 151                                           BIGNUM *p1, BIGNUM *p2,
 152                                           const BIGNUM *Xp, const BIGNUM *Xp1,
 153                                           const BIGNUM *Xp2, int nlen,
 154                                           const BIGNUM *e, BN_CTX *ctx,
 155                                           BN_GENCB *cb)
 156 {
 157     int ret = 0;
 158     BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
 159     int bitlen;
 160
 161     if (p == NULL || Xpout == NULL)
 162         return 0;
 163
 164     BN_CTX_start(ctx);
 165
 166     p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
 167     p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
 168     Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
 169     Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
 170     if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
 171         goto err;
 172
 173     bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
 174     if (bitlen == 0)
 175         goto err;
 176
 177     /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
 178     if (Xp1 == NULL) {
 179         /* Set the top and bottom bits to make it odd and the correct size */
 180         if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
 181                              ctx))
 182             goto err;
 183     }
 184     /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
 185     if (Xp2 == NULL) {
 186         /* Set the top and bottom bits to make it odd and the correct size */
 187         if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
 188                              ctx))
 189             goto err;
 190     }
 191
 192     /* (Steps 4.2/5.2) - find first auxiliary probable primes */
 193     if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
 194             || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
 195         goto err;
 196     /* (Table B.1) auxiliary prime Max length check */
 197     if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
 198             bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
 199         goto err;
 200     /* (Steps 4.3/5.3) - generate prime */
 201     if (!ossl_bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e,
 202                                             ctx, cb))
 203         goto err;
 204     ret = 1;
 205 err:
 206     /* Zeroize any internally generated values that are not returned */
 207     if (p1 == NULL)
 208         BN_clear(p1i);
 209     if (p2 == NULL)
 210         BN_clear(p2i);
 211     if (Xp1 == NULL)
 212         BN_clear(Xp1i);
 213     if (Xp2 == NULL)
 214         BN_clear(Xp2i);
 215     BN_CTX_end(ctx);
 216     return ret;
 217 }
 218
 219 /*
 220  * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
 221  * prime numbers and the Chinese Remainder Theorem.
 222  *
 223  * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
 224  * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
 225  *
 226  * Params:
 227  *     Y The returned prime factor (private_prime_factor) of the modulus n.
 228  *     X The returned random number used during generation of the prime factor.
 229  *     Xin An optional passed in value for X used for testing purposes.
 230  *     r1 An auxiliary prime.
 231  *     r2 An auxiliary prime.
 232  *     nlen The desired length of n (the RSA modulus).
 233  *     e The public exponent.
 234  *     ctx A BN_CTX object.
 235  *     cb An optional BIGNUM callback object.
 236  * Returns: 1 on success otherwise it returns 0.
 237  * Assumptions:
 238  *     Y, X, r1, r2, e are not NULL.
 239  */
 240 int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
 241                                        const BIGNUM *r1, const BIGNUM *r2,
 242                                        int nlen, const BIGNUM *e, BN_CTX *ctx,
 243                                        BN_GENCB *cb)
 244 {
 245     int ret = 0;
 246     int i, imax;
 247     int bits = nlen >> 1;
 248     BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
 249     BIGNUM *base, *range;
 250
 251     BN_CTX_start(ctx);
 252
 253     base = BN_CTX_get(ctx);
 254     range = BN_CTX_get(ctx);
 255     R = BN_CTX_get(ctx);
 256     tmp = BN_CTX_get(ctx);
 257     r1r2x2 = BN_CTX_get(ctx);
 258     y1 = BN_CTX_get(ctx);
 259     r1x2 = BN_CTX_get(ctx);
 260     if (r1x2 == NULL)
 261         goto err;
 262
 263     if (Xin != NULL && BN_copy(X, Xin) == NULL)
 264         goto err;
 265
 266     /*
 267      * We need to generate a random number X in the range
 268      * 1/sqrt(2) * 2^(nlen/2) <= X < 2^(nlen/2).
 269      * We can rewrite that as:
 270      * base = 1/sqrt(2) * 2^(nlen/2)
 271      * range = ((2^(nlen/2))) - (1/sqrt(2) * 2^(nlen/2))
 272      * X = base + random(range)
 273      * We only have the first 256 bit of 1/sqrt(2)
 274      */
 275     if (Xin == NULL) {
 276         if (bits < BN_num_bits(&ossl_bn_inv_sqrt_2))
 277             goto err;
 278         if (!BN_lshift(base, &ossl_bn_inv_sqrt_2,
 279                        bits - BN_num_bits(&ossl_bn_inv_sqrt_2))
 280             || !BN_lshift(range, BN_value_one(), bits)
 281             || !BN_sub(range, range, base))
 282             goto err;
 283     }
 284
 285     if (!(BN_lshift1(r1x2, r1)
 286             /* (Step 1) GCD(2r1, r2) = 1 */
 287             && BN_gcd(tmp, r1x2, r2, ctx)
 288             && BN_is_one(tmp)
 289             /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
 290             && BN_mod_inverse(R, r2, r1x2, ctx)
 291             && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
 292             && BN_mod_inverse(tmp, r1x2, r2, ctx)
 293             && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
 294             && BN_sub(R, R, tmp)
 295             /* Calculate 2r1r2 */
 296             && BN_mul(r1r2x2, r1x2, r2, ctx)))
 297         goto err;
 298     /* Make positive by adding the modulus */
 299     if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
 300         goto err;
 301
 302     imax = 5 * bits; /* max = 5/2 * nbits */
 303     for (;;) {
 304         if (Xin == NULL) {
 305             /*
 306              * (Step 3) Choose Random X such that
 307              *    sqrt(2) * 2^(nlen/2-1) <= Random X <= (2^(nlen/2)) - 1.
 308              */
 309             if (!BN_priv_rand_range_ex(X, range, ctx) || !BN_add(X, X, base))
 310                 goto end;
 311         }
 312         /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
 313         if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
 314             goto err;
 315         /* (Step 5) */
 316         i = 0;
 317         for (;;) {
 318             /* (Step 6) */
 319             if (BN_num_bits(Y) > bits) {
 320                 if (Xin == NULL)
 321                     break; /* Randomly Generated X so Go back to Step 3 */
 322                 else
 323                     goto err; /* X is not random so it will always fail */
 324             }
 325             BN_GENCB_call(cb, 0, 2);
 326
 327             /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
 328             if (BN_copy(y1, Y) == NULL
 329                     || !BN_sub_word(y1, 1)
 330                     || !BN_gcd(tmp, y1, e, ctx))
 331                 goto err;
 332             if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
 333                 goto end;
 334             /* (Step 8-10) */
 335             if (++i >= imax || !BN_add(Y, Y, r1r2x2))
 336                 goto err;
 337         }
 338     }
 339 end:
 340     ret = 1;
 341     BN_GENCB_call(cb, 3, 0);
 342 err:
 343     BN_clear(y1);
 344     BN_CTX_end(ctx);
 345     return ret;
 346 }