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 <shane.lontis@oracle.com>
Reviewed-by: Richard Levitte <levitte@openssl.org>
GH: #10246

1 files changed, 15 insertions, 12 deletions

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: