aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/cli/speed.cpp24
-rw-r--r--src/lib/math/numbertheory/make_prm.cpp60
-rwxr-xr-xsrc/scripts/test_cli.py12
3 files changed, 52 insertions, 44 deletions
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 06c1e6ab9..e81ddd24b 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1598,26 +1598,37 @@ class Speed final : public Command
{
const size_t coprime = 65537; // simulates RSA key gen
- for(size_t bits : { 1024, 1536 })
+ for(size_t bits : { 256, 384, 512, 768, 1024, 1536 })
{
std::unique_ptr<Timer> genprime_timer = make_timer("random_prime " + std::to_string(bits));
+ std::unique_ptr<Timer> gensafe_timer = make_timer("random_safe_prime " + std::to_string(bits));
std::unique_ptr<Timer> is_prime_timer = make_timer("is_prime " + std::to_string(bits));
- while(genprime_timer->under(runtime) && is_prime_timer->under(runtime))
+ while(gensafe_timer->under(runtime))
{
const Botan::BigInt p = genprime_timer->run([&]
{
return Botan::random_prime(rng(), bits, coprime);
});
- const bool ok = is_prime_timer->run([&]
+ if(!is_prime_timer->run([&] { return Botan::is_prime(p, rng(), 64, true); }))
{
- return Botan::is_prime(p, rng(), 64, true);
+ error_output() << "Generated prime " << p << " which failed a primality test";
+ }
+
+ const Botan::BigInt sg = gensafe_timer->run([&]
+ {
+ return Botan::random_safe_prime(rng(), bits);
});
- if(!ok)
+ if(!is_prime_timer->run([&] { return Botan::is_prime(sg, rng(), 64, true); }))
{
- error_output() << "Generated prime " << p << " which failed a primality test";
+ error_output() << "Generated safe prime " << sg << " which failed a primality test";
+ }
+
+ if(!is_prime_timer->run([&] { return Botan::is_prime(sg / 2, rng(), 64, true); }))
+ {
+ error_output() << "Generated prime " << sg/2 << " which failed a primality test";
}
// Now test p+2, p+4, ... which may or may not be prime
@@ -1628,6 +1639,7 @@ class Speed final : public Command
}
record_result(genprime_timer);
+ record_result(gensafe_timer);
record_result(is_prime_timer);
}
}
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index 6c2c20718..404e30104 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -122,9 +122,9 @@ BigInt random_prime(RandomNumberGenerator& rng,
for(;;)
{
// This is slightly biased, but for small primes it does not seem to matter
- const uint8_t b0 = rng.next_byte();
- const uint8_t b1 = rng.next_byte();
- const size_t idx = make_uint16(b0, b1) % PRIME_TABLE_SIZE;
+ uint8_t b[4];
+ rng.randomize(b, 4);
+ const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
const uint16_t small_prime = PRIMES[idx];
if(high_bit(small_prime) == bits)
@@ -135,6 +135,8 @@ BigInt random_prime(RandomNumberGenerator& rng,
const size_t MAX_ATTEMPTS = 32*1024;
+ const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
+
while(true)
{
BigInt p(rng, bits);
@@ -161,16 +163,16 @@ BigInt random_prime(RandomNumberGenerator& rng,
Modular_Reducer mod_p(p);
- /*
- First do a single M-R iteration to quickly elimate most non-primes,
- before doing the coprimality check which is expensive
- */
- if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
- continue;
-
if(coprime > 1)
{
/*
+ First do a single M-R iteration to quickly elimate most non-primes,
+ before doing the coprimality check which is expensive
+ */
+ if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
+ continue;
+
+ /*
* Check if p - 1 and coprime are relatively prime, using gcd.
* The gcd computation is const-time
*/
@@ -181,9 +183,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
if(p.bits() > bits)
break;
- const size_t t = miller_rabin_test_iterations(bits, prob, true);
-
- if(is_miller_rabin_probable_prime(p, mod_p, rng, t) == false)
+ if(is_miller_rabin_probable_prime(p, mod_p, rng, mr_trials) == false)
continue;
if(prob > 32 && !is_lucas_probable_prime(p, mod_p))
@@ -213,19 +213,21 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
const size_t MAX_ATTEMPTS = 32*1024;
+ const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
+
while(true)
{
BigInt p(keygen_rng, bits);
- // Force lowest and two top bits on
+ // Force high two bits so multiplication always results in expected n bit integer
p.set_bit(bits - 1);
p.set_bit(bits - 2);
p.set_bit(0);
- Prime_Sieve sieve(p, bits);
-
const word step = 2;
+ Prime_Sieve sieve(p, bits);
+
for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
{
p += step;
@@ -239,8 +241,8 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
/*
* Do a single primality test first before checking coprimality, since
- * currently a single Miller-Rabin test is faster than computing modular
- * inverse, and this eliminates almost all wasted modular inverses.
+ * currently a single Miller-Rabin test is faster than computing gcd,
+ * and this eliminates almost all wasted gcd computations.
*/
if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)
continue;
@@ -254,9 +256,7 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
if(p.bits() > bits)
break;
- const size_t t = miller_rabin_test_iterations(bits, prob, true);
-
- if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, t) == true)
+ if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, mr_trials) == true)
return p;
}
}
@@ -271,25 +271,21 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
std::to_string(bits) + " bits");
+ const size_t error_bound = 128;
+
BigInt q, p;
for(;;)
{
/*
- Generate q == 2 (mod 3)
-
- Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
-
- Initially allow a very high error prob (1/2**8) to allow for fast checks,
- then if 2*q+1 turns out to be a prime go back and strongly check q.
+ Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
+ 2*q+1 == 3 (mod 3) and so certainly not prime.
*/
- q = random_prime(rng, bits - 1, 0, 2, 3, 8);
+ q = random_prime(rng, bits - 1, 0, 2, 3, error_bound);
p = (q << 1) + 1;
- if(is_prime(p, rng, 128, true))
+ if(is_prime(p, rng, error_bound, true))
{
- // We did only a weak check before, go back and verify q before returning
- if(is_prime(q, rng, 128, true))
- return p;
+ return p;
}
}
}
diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py
index cafab6a09..4e0f8ab83 100755
--- a/src/scripts/test_cli.py
+++ b/src/scripts/test_cli.py
@@ -269,12 +269,12 @@ def cli_argon2_tests(_tmp_dir):
def cli_gen_dl_group_tests(_tmp_dir):
pem = """-----BEGIN X9.42 DH PARAMETERS-----
-MIIBJAKBgwVcMHlFVo64S86Y5KrlClZrIibOQ6iKm8Ih3Eb53XoQiSc33GtilRmP
-f7qKIVI86meoJHVU7gtaJk82yAYk6BksmZn0eXvUU7zD8yF/yH3yym0SfI0eH1OC
-2+esfGblePpHCtt5uO56pzIqCIpOq+8gTG7JbFHJvTb8nwmAWFLZvjepAoGDBHOP
-e5A/RNyeXz+16+7Jjh4QOXWo/c6kM0WrIHgFbaIkupRndG5bcy8aCjsbgiIpeWy1
-aNDURFB3UR3q1Si0gA7cvirDOH7lnN3C9zeohq+VPy5L7S3gKLGB1HXY/r2qLKhM
-6ziphMYZxtr+XhsbxbA/+MuNoP/He+kwlGLtDKiBdF4CFjgPiPatvmWssQw2AuZ9
+MIIBJAKBgwTw7LQiLkXJsrgMVQxTPlWaQlYz/raZ+5RtIZe4YluQgRQGPFADLZ/t
+TOYzuIzZJFOcdKtEtrVkxZRGSkjZwKFKLUD6fzSjoC2M2EHktK/y5HsvxBxL4tKr
+q1ffbyPQi+iBLYTZAXygvxj2vWyrvA+/w4nbt1fStCHTDhWjLWqFpV9nAoGDAKzA
+HUu/IRl7OiUtW/dz36gzEJnaYtz4ZtJl0FG8RJiOe02lD8myqW2sVzYqMvKD0LGx
+x9fdSKC1G+aZ/NWtqrQjb66Daf7b0ddDx+bfWTWJ2dOtZd8IL2rmQQJm+JogDi9i
+huVYFicDNQGzi+nEKAzrZ1L/VxtiSiw/qw0IyOuVtz8CFjgPiPatvmWssQw2AuZ9
mFvAZ/8wal0=
-----END X9.42 DH PARAMETERS-----"""
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-25 05:46:02 +0000