LibCrypto: Fix random number generation

2 files changed, 21 insertions, 16 deletions

diff --git a/Libraries/LibCrypto/NumberTheory/ModularFunctions.h b/Libraries/LibCrypto/NumberTheory/ModularFunctions.h
index afd97a107c..9b1ef1a1fd 100644
--- a/Libraries/LibCrypto/NumberTheory/ModularFunctions.h
+++ b/Libraries/LibCrypto/NumberTheory/ModularFunctions.h
@@ -306,20 +306,25 @@ static bool MR_primality_test(UnsignedBigInteger n, const Vector<UnsignedBigInte
     return true;
 }
 
-static UnsignedBigInteger random_number(const UnsignedBigInteger& min, const UnsignedBigInteger& max)
+static UnsignedBigInteger random_number(const UnsignedBigInteger& min, const UnsignedBigInteger& max_excluded)
 {
-    ASSERT(min < max);
-    auto range = max.minus(min);
+    ASSERT(min < max_excluded);
+    auto range = max_excluded.minus(min);
     UnsignedBigInteger base;
-    auto size = range.trimmed_length() * sizeof(u32);
+    auto size = range.trimmed_length() * sizeof(u32) + 2;
+    // "+2" is intentional (see below).
     u8 buf[size];
     AK::fill_with_random(buf, size);
-    Vector<u32> vec;
-    for (size_t i = 0; i < size / sizeof(u32); ++i) {
-        vec.append(*(u32*)buf + i);
-    }
-    UnsignedBigInteger offset { move(vec) };
-    return offset.plus(min);
+    UnsignedBigInteger random { buf, size };
+    // At this point, `random` is a large number, in the range [0, 256^size).
+    // To get down to the actual range, we could just compute random % range.
+    // This introduces "modulo bias". However, since we added 2 to `size`,
+    // we know that the generated range is at least 65536 times as large as the
+    // required range! This means that the modulo bias is only 0.0015%, if all
+    // inputs are chosen adversarially. Let's hope this is good enough.
+    auto divmod = random.divided_by(range);
+    // The proper way to fix this is to restart if `divmod.quotient` is maximal.
+    return divmod.remainder.plus(min);
 }
 
 static bool is_probably_prime(const UnsignedBigInteger& p)
diff --git a/Userland/test-crypto.cpp b/Userland/test-crypto.cpp
index 1ea3875781..bcf3afc36e 100644
--- a/Userland/test-crypto.cpp
+++ b/Userland/test-crypto.cpp
@@ -1419,11 +1419,11 @@ static void hmac_sha512_test_process()
 
 static int rsa_tests()
 {
-    (void)rsa_test_encrypt;
-    (void)rsa_test_der_parse;
+    rsa_test_encrypt();
+    rsa_test_der_parse();
     bigint_test_number_theory();
-    (void)rsa_test_encrypt_decrypt;
-    (void)rsa_emsa_pss_test_create;
+    rsa_test_encrypt_decrypt();
+    rsa_emsa_pss_test_create();
     return g_some_test_failed ? 1 : 0;
 }
 
@@ -1559,10 +1559,10 @@ static void bigint_test_number_theory()
         for (auto test_case : primality_tests) {
             I_TEST((Number Theory | Random numbers));
             auto actual_result = Crypto::NumberTheory::random_number(test_case.min, test_case.max);
-            if (actual_result < the_min) {
+            if (actual_result < test_case.min) {
                 FAIL(Too small);
                 printf("The generated number %s is smaller than the requested minimum %s. (max = %s)\n", actual_result.to_base10().characters(), test_case.min.to_base10().characters(), test_case.max.to_base10().characters());
-            } else if (!(actual_result < the_max)) {
+            } else if (!(actual_result < test_case.max)) {
                 FAIL(Too large);
                 printf("The generated number %s is larger-or-equal to the requested maximum %s. (min = %s)\n", actual_result.to_base10().characters(), test_case.max.to_base10().characters(), test_case.min.to_base10().characters());
             } else {