aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/math/numbertheory/dsa_gen.cpp4
-rw-r--r--src/lib/math/numbertheory/make_prm.cpp4
-rw-r--r--src/lib/math/numbertheory/numthry.cpp31
-rw-r--r--src/lib/math/numbertheory/numthry.h17
-rw-r--r--src/lib/pubkey/dl_group/dl_group.cpp9
-rw-r--r--src/lib/pubkey/if_algo/if_algo.cpp8
6 files changed, 57 insertions, 16 deletions
diff --git a/src/lib/math/numbertheory/dsa_gen.cpp b/src/lib/math/numbertheory/dsa_gen.cpp
index f14481f9c..796fb6ec2 100644
--- a/src/lib/math/numbertheory/dsa_gen.cpp
+++ b/src/lib/math/numbertheory/dsa_gen.cpp
@@ -82,7 +82,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
q.set_bit(qbits-1);
q.set_bit(0);
- if(!check_prime(q, rng))
+ if(!is_prime(q, rng))
return false;
const size_t n = (pbits-1) / (HASH_SIZE * 8),
@@ -106,7 +106,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
p = X - (X % (2*q) - 1);
- if(p.bits() == pbits && check_prime(p, rng))
+ if(p.bits() == pbits && is_prime(p, rng))
return true;
}
return false;
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index dc94420ab..2c8cd086d 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -75,7 +75,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
if(!passes_sieve || gcd(p - 1, coprime) != 1)
continue;
- if(check_prime(p, rng))
+ if(is_prime(p, rng, 64, true))
return p;
}
}
@@ -93,7 +93,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
BigInt p;
do
p = (random_prime(rng, bits - 1) << 1) + 1;
- while(!check_prime(p, rng));
+ while(!is_prime(p, rng, 64, true));
return p;
}
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 998b0b53b..ce25b5047 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -253,12 +253,39 @@ bool mr_witness(BigInt&& y,
return true; // fails Fermat test
}
+size_t mr_test_iterations(size_t n_bits, size_t prob, bool random)
+ {
+ const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
+
+ /*
+ * For randomly chosen numbers we can use the estimates from
+ * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf‎
+ *
+ * These values are derived from the inequality for p(k,t) given on
+ * the second page.
+ */
+ if(random && prob <= 80)
+ {
+ if(n_bits >= 1536)
+ return 2; // < 2^-89
+ if(n_bits >= 1024)
+ return 4; // < 2^-89
+ if(n_bits >= 512)
+ return 5; // < 2^-80
+ if(n_bits >= 256)
+ return 11; // < 2^-80
+ }
+
+ return base;
+ }
+
}
/*
* Test for primaility using Miller-Rabin
*/
-bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
+ size_t prob, bool is_random)
{
if(n == 2)
return true;
@@ -273,7 +300,7 @@ bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);
}
- const size_t test_iterations = 20;
+ const size_t test_iterations = mr_test_iterations(n.bits(), prob, is_random);
const BigInt n_minus_1 = n - 1;
const size_t s = low_zero_bits(n_minus_1);
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index cb73356b2..5499ff76f 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -126,9 +126,24 @@ size_t BOTAN_DLL low_zero_bits(const BigInt& x);
* Check for primality
* @param n a positive integer to test for primality
* @param rng a random number generator
+* @param prob chance of false positive is bounded by 1/2**prob
+* @param is_random true if n was randomly chosen by us
* @return true if all primality tests passed, otherwise false
*/
-bool BOTAN_DLL check_prime(const BigInt& n, RandomNumberGenerator& rng);
+bool BOTAN_DLL is_prime(const BigInt& n,
+ RandomNumberGenerator& rng,
+ size_t prob = 56,
+ bool is_random = false);
+
+inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+ { return is_prime(n, rng, 32); }
+
+inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+ { return is_prime(n, rng, 56); }
+
+inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+ { return is_prime(n, rng, 80); }
+
/**
* Randomly generate a prime
diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index 6fd1beeaa..13079a898 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -61,7 +61,7 @@ DL_Group::DL_Group(RandomNumberGenerator& rng,
q = random_prime(rng, qbits);
BigInt X;
- while(p.bits() != pbits || !check_prime(p, rng))
+ while(p.bits() != pbits || !is_prime(p, rng))
{
X.randomize(rng, pbits);
p = X - (X % (2*q) - 1);
@@ -159,12 +159,11 @@ bool DL_Group::verify_group(RandomNumberGenerator& rng,
if((q != 0) && ((p - 1) % q != 0))
return false;
- if(!strong)
- return true;
+ const size_t prob = (strong) ? 56 : 10;
- if(!check_prime(p, rng))
+ if(!is_prime(p, rng, prob))
return false;
- if((q > 0) && !check_prime(q, rng))
+ if((q > 0) && !is_prime(q, rng, prob))
return false;
return true;
}
diff --git a/src/lib/pubkey/if_algo/if_algo.cpp b/src/lib/pubkey/if_algo/if_algo.cpp
index f6aeb69db..339c4e317 100644
--- a/src/lib/pubkey/if_algo/if_algo.cpp
+++ b/src/lib/pubkey/if_algo/if_algo.cpp
@@ -130,12 +130,12 @@ bool IF_Scheme_PrivateKey::check_key(RandomNumberGenerator& rng,
if(n < 35 || n.is_even() || e < 2 || d < 2 || p < 3 || q < 3 || p*q != n)
return false;
- if(!strong)
- return true;
-
if(d1 != d % (p - 1) || d2 != d % (q - 1) || c != inverse_mod(q, p))
return false;
- if(!check_prime(p, rng) || !check_prime(q, rng))
+
+ const size_t prob = (strong) ? 56 : 12;
+
+ if(!is_prime(p, rng, prob) || !is_prime(q, rng, prob))
return false;
return true;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-23 16:00:00 +0000