From fd4a6e7d1e51ad53f70ae75317da36418cae6458 Mon Sep 17 00:00:00 2001 From: Kurt Roeckx Date: Wed, 23 Oct 2019 22:10:54 +0200 Subject: [PATCH] RSA generation: Use more bits of 1/sqrt(2) The old version always sets the top 2 bits, so the most significate byte of the primes was always >= 0xC0. We now use 256 bits to represent 1/sqrt(2) = 0x0.B504F333F9DE64845... Reviewed-by: Shane Lontis Reviewed-by: Richard Levitte GH: #10246 --- crypto/bn/bn_rsa_fips186_4.c | 53 ++++++++++++++++++++++++++------ crypto/rsa/rsa_sp800_56b_check.c | 27 ++++++++-------- include/crypto/bn.h | 3 ++ test/rsa_sp800_56b_test.c | 2 ++ 4 files changed, 64 insertions(+), 21 deletions(-) diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c index c31b43ba8f..492eb297c3 100644 --- a/crypto/bn/bn_rsa_fips186_4.c +++ b/crypto/bn/bn_rsa_fips186_4.c @@ -31,6 +31,27 @@ #include #include "bn_local.h" #include "crypto/bn.h" +#include "internal/nelem.h" + +#if BN_BITS2 == 64 +# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo +#else +# define BN_DEF(lo, hi) lo, hi +#endif + +/* 1 / sqrt(2) * 2^256, rounded up */ +static const BN_ULONG inv_sqrt_2_val[] = { + BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL), + BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL) +}; + +const BIGNUM bn_inv_sqrt_2 = { + (BN_ULONG *)inv_sqrt_2_val, + OSSL_NELEM(inv_sqrt_2_val), + OSSL_NELEM(inv_sqrt_2_val), + 0, + BN_FLG_STATIC_DATA +}; /* * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2". @@ -221,9 +242,12 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, int i, imax; int bits = nlen >> 1; BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2; + BIGNUM *base, *range; BN_CTX_start(ctx); + base = BN_CTX_get(ctx); + range = BN_CTX_get(ctx); R = BN_CTX_get(ctx); tmp = BN_CTX_get(ctx); r1r2x2 = BN_CTX_get(ctx); @@ -235,6 +259,24 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, if (Xin != NULL && BN_copy(X, Xin) == NULL) goto err; + /* + * We need to generate a random number X in the range + * 1/sqrt(2) * 2^(nlen/2) <= X < 2^(nlen/2). + * We can rewrite that as: + * base = 1/sqrt(2) * 2^(nlen/2) + * range = ((2^(nlen/2))) - (1/sqrt(2) * 2^(nlen/2)) + * X = base + random(range) + * We only have the first 256 bit of 1/sqrt(2) + */ + if (Xin == NULL) { + if (bits < BN_num_bits(&bn_inv_sqrt_2)) + goto err; + if (!BN_lshift(base, &bn_inv_sqrt_2, bits - BN_num_bits(&bn_inv_sqrt_2)) + || !BN_lshift(range, BN_value_one(), bits) + || !BN_sub(range, range, base)) + goto err; + } + if (!(BN_lshift1(r1x2, r1) /* (Step 1) GCD(2r1, r2) = 1 */ && BN_gcd(tmp, r1x2, r2, ctx) @@ -257,16 +299,9 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, if (Xin == NULL) { /* * (Step 3) Choose Random X such that - * sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1. - * - * For the lower bound: - * sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2) - * where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE... - * so largest number will have B5... as the top byte - * Setting the top 2 bits gives 0xC0. + * sqrt(2) * 2^(nlen/2-1) <= Random X <= (2^(nlen/2)) - 1. */ - if (!BN_priv_rand_ex(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY, - ctx)) + if (!BN_priv_rand_range_ex(X, range, ctx) || !BN_add(X, X, base)) goto end; } /* (Step 4) Y = X + ((R - X) mod 2r1r2) */ diff --git a/crypto/rsa/rsa_sp800_56b_check.c b/crypto/rsa/rsa_sp800_56b_check.c index d614504bc9..c4c0b6a95b 100644 --- a/crypto/rsa/rsa_sp800_56b_check.c +++ b/crypto/rsa/rsa_sp800_56b_check.c @@ -75,38 +75,41 @@ int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx) * See SP800-5bBr1 6.4.1.2.1 Part 5 (c) & (g) - used for both p and q. * * (√2)(2^(nbits/2 - 1) = (√2/2)(2^(nbits/2)) - * √2/2 = 0.707106781186547524400 = 0.B504F333F9DE6484597D8 - * 0.B504F334 gives an approximation to 11 decimal places. - * The range is then from - * 0xB504F334_0000.......................000 to - * 0xFFFFFFFF_FFFF.......................FFF */ int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx) { int ret = 0; - BIGNUM *tmp, *low; + BIGNUM *low; + int shift; nbits >>= 1; + shift = nbits - BN_num_bits(&bn_inv_sqrt_2); /* Upper bound check */ if (BN_num_bits(p) != nbits) return 0; BN_CTX_start(ctx); - tmp = BN_CTX_get(ctx); low = BN_CTX_get(ctx); + if (low == NULL) + goto err; /* set low = (√2)(2^(nbits/2 - 1) */ - if (low == NULL || !BN_set_word(tmp, 0xB504F334)) + if (!BN_copy(low, &bn_inv_sqrt_2)) goto err; - if (nbits >= 32) { - if (!BN_lshift(low, tmp, nbits - 32)) + if (shift >= 0) { + /* + * We don't have all the bits. bn_inv_sqrt_2 contains a rounded up + * value, so there is a very low probabilty that we'll reject a valid + * value. + */ + if (!BN_lshift(low, low, shift)) goto err; - } else if (!BN_rshift(low, tmp, 32 - nbits)) { + } else if (!BN_rshift(low, low, -shift)) { goto err; } - if (BN_cmp(p, low) < 0) + if (BN_cmp(p, low) <= 0) goto err; ret = 1; err: diff --git a/include/crypto/bn.h b/include/crypto/bn.h index 91c6cd5dcc..f2cb30de0a 100644 --- a/include/crypto/bn.h +++ b/include/crypto/bn.h @@ -111,4 +111,7 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb); OPENSSL_CTX *bn_get_lib_ctx(BN_CTX *ctx); + +extern const BIGNUM bn_inv_sqrt_2; + #endif diff --git a/test/rsa_sp800_56b_test.c b/test/rsa_sp800_56b_test.c index 1e6ea8d0b6..b928655794 100644 --- a/test/rsa_sp800_56b_test.c +++ b/test/rsa_sp800_56b_test.c @@ -223,6 +223,8 @@ static int test_check_prime_factor_range(void) && TEST_true(BN_set_word(p, 0x10)) && TEST_false(rsa_check_prime_factor_range(p, 8, ctx)) && TEST_true(BN_set_word(p, 0xB)) + && TEST_false(rsa_check_prime_factor_range(p, 8, ctx)) + && TEST_true(BN_set_word(p, 0xC)) && TEST_true(rsa_check_prime_factor_range(p, 8, ctx)) && TEST_true(BN_set_word(p, 0xF)) && TEST_true(rsa_check_prime_factor_range(p, 8, ctx)) -- 2.25.1