aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/math')
-rw-r--r--src/lib/math/bigint/bigint.h2
-rw-r--r--src/lib/math/ec_gfp/point_gfp.cpp3
-rw-r--r--src/lib/math/numbertheory/numthry.cpp189
-rw-r--r--src/lib/math/numbertheory/numthry.h34
4 files changed, 42 insertions, 186 deletions
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index a1164bf92..0d9b43357 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -430,7 +430,7 @@ class BOTAN_DLL BigInt
* @param rng a random number generator
* @param min the minimum value
* @param max the maximum value
- * @return random integer between min and max
+ * @return random integer in [min,max)
*/
static BigInt random_integer(RandomNumberGenerator& rng,
const BigInt& min,
diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp
index 9cd5a2aaf..cf3a204d6 100644
--- a/src/lib/math/ec_gfp/point_gfp.cpp
+++ b/src/lib/math/ec_gfp/point_gfp.cpp
@@ -196,7 +196,8 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
monty_sqr(z4, monty_sqr(coord_z));
monty_mult(a_z4, curve.get_a_r(), z4);
- M = 3 * monty_sqr(coord_x);
+ M = monty_sqr(coord_x);
+ M *= 3;
M += a_z4;
while(M >= p)
M -= p;
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 5946aa994..998b0b53b 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -13,128 +13,6 @@
namespace Botan {
-namespace {
-
-/*
-* Miller-Rabin Primality Tester
-*/
-class MillerRabin_Test
- {
- public:
- bool is_witness(const BigInt& nonce);
- MillerRabin_Test(const BigInt& num);
- private:
- BigInt n, r, n_minus_1;
- size_t s;
- Fixed_Exponent_Power_Mod pow_mod;
- Modular_Reducer reducer;
- };
-
-/*
-* Miller-Rabin Test, as described in Handbook of Applied Cryptography
-* section 4.24
-*/
-bool MillerRabin_Test::is_witness(const BigInt& a)
- {
- if(a < 2 || a >= n_minus_1)
- throw Invalid_Argument("Bad size for nonce in Miller-Rabin test");
-
- BigInt y = pow_mod(a);
- if(y == 1 || y == n_minus_1)
- return false;
-
- for(size_t i = 1; i != s; ++i)
- {
- y = reducer.square(y);
-
- if(y == 1) // found a non-trivial square root
- return true;
-
- if(y == n_minus_1) // -1, trivial square root, so give up
- return false;
- }
-
- return true; // fails Fermat test
- }
-
-/*
-* Miller-Rabin Constructor
-*/
-MillerRabin_Test::MillerRabin_Test(const BigInt& num)
- {
- if(num.is_even() || num < 3)
- throw Invalid_Argument("MillerRabin_Test: Invalid number for testing");
-
- n = num;
- n_minus_1 = n - 1;
- s = low_zero_bits(n_minus_1);
- r = n_minus_1 >> s;
-
- pow_mod = Fixed_Exponent_Power_Mod(r, n);
- reducer = Modular_Reducer(n);
- }
-
-/*
-* Miller-Rabin Iterations
-*/
-size_t miller_rabin_test_iterations(size_t bits, size_t level)
- {
- struct mapping { size_t bits; size_t verify_iter; size_t check_iter; };
-
- const mapping tests[] = {
- { 50, 55, 25 },
- { 100, 38, 22 },
- { 160, 32, 18 },
- { 163, 31, 17 },
- { 168, 30, 16 },
- { 177, 29, 16 },
- { 181, 28, 15 },
- { 185, 27, 15 },
- { 190, 26, 15 },
- { 195, 25, 14 },
- { 201, 24, 14 },
- { 208, 23, 14 },
- { 215, 22, 13 },
- { 222, 21, 13 },
- { 231, 20, 13 },
- { 241, 19, 12 },
- { 252, 18, 12 },
- { 264, 17, 12 },
- { 278, 16, 11 },
- { 294, 15, 10 },
- { 313, 14, 9 },
- { 334, 13, 8 },
- { 360, 12, 8 },
- { 392, 11, 7 },
- { 430, 10, 7 },
- { 479, 9, 6 },
- { 542, 8, 6 },
- { 626, 7, 5 },
- { 746, 6, 4 },
- { 926, 5, 3 },
- { 1232, 4, 2 },
- { 1853, 3, 2 },
- { 0, 0, 0 }
- };
-
- for(size_t i = 0; tests[i].bits; ++i)
- {
- if(bits <= tests[i].bits)
- {
- if(level >= 2)
- return tests[i].verify_iter;
- else if(level == 1)
- return tests[i].check_iter;
- else if(level == 0)
- return std::max<size_t>(tests[i].check_iter / 4, 1);
- }
- }
-
- return level > 0 ? 2 : 1; // for large inputs
- }
-
-}
-
/*
* Return the number of 0 bits at the end of n
*/
@@ -352,12 +230,35 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
return pow_mod.execute();
}
+namespace {
+
+bool mr_witness(BigInt&& y,
+ const Modular_Reducer& reducer_n,
+ const BigInt& n_minus_1, size_t s)
+ {
+ if(y == 1 || y == n_minus_1)
+ return false;
+
+ for(size_t i = 1; i != s; ++i)
+ {
+ y = reducer_n.square(y);
+
+ if(y == 1) // found a non-trivial square root
+ return true;
+
+ if(y == n_minus_1) // -1, trivial square root, so give up
+ return false;
+ }
+
+ return true; // fails Fermat test
+ }
+
+}
+
/*
* Test for primaility using Miller-Rabin
*/
-bool primality_test(const BigInt& n,
- RandomNumberGenerator& rng,
- size_t level)
+bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
{
if(n == 2)
return true;
@@ -367,40 +268,26 @@ bool primality_test(const BigInt& n,
// Fast path testing for small numbers (<= 65521)
if(n <= PRIMES[PRIME_TABLE_SIZE-1])
{
- const word num = n.word_at(0);
+ const u16bit num = n.word_at(0);
- for(size_t i = 0; PRIMES[i]; ++i)
- {
- if(num == PRIMES[i])
- return true;
- if(num < PRIMES[i])
- return false;
- }
-
- return false;
+ return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);
}
- if(level > 2)
- level = 2;
-
- const size_t PREF_NONCE_BITS = 192;
+ const size_t test_iterations = 20;
- const size_t NONCE_BITS = std::min(n.bits() - 2, PREF_NONCE_BITS);
+ const BigInt n_minus_1 = n - 1;
+ const size_t s = low_zero_bits(n_minus_1);
- MillerRabin_Test mr(n);
+ Fixed_Exponent_Power_Mod pow_mod(n_minus_1 >> s, n);
+ Modular_Reducer reducer(n);
- if(mr.is_witness(2))
- return false;
-
- const size_t tests = miller_rabin_test_iterations(n.bits(), level);
-
- for(size_t i = 0; i != tests; ++i)
+ for(size_t i = 0; i != test_iterations; ++i)
{
- BigInt nonce;
- while(nonce < 2 || nonce >= (n-1))
- nonce.randomize(rng, NONCE_BITS);
+ const BigInt a = BigInt::random_integer(rng, 2, n_minus_1);
+
+ BigInt y = pow_mod(a);
- if(mr.is_witness(nonce))
+ if(mr_witness(std::move(y), reducer, n_minus_1, s))
return false;
}
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index a34d855b2..cb73356b2 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -123,44 +123,12 @@ word BOTAN_DLL monty_inverse(word input);
size_t BOTAN_DLL low_zero_bits(const BigInt& x);
/**
-* Primality Testing
-* @param n a positive integer to test for primality
-* @param rng a random number generator
-* @param level how hard to test
-* @return true if all primality tests passed, otherwise false
-*/
-bool BOTAN_DLL primality_test(const BigInt& n,
- RandomNumberGenerator& rng,
- size_t level = 1);
-
-/**
-* Quickly check for primality
-* @param n a positive integer to test for primality
-* @param rng a random number generator
-* @return true if all primality tests passed, otherwise false
-*/
-inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
- { return primality_test(n, rng, 0); }
-
-/**
* Check for primality
* @param n a positive integer to test for primality
* @param rng a random number generator
* @return true if all primality tests passed, otherwise false
*/
-inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
- { return primality_test(n, rng, 1); }
-
-/**
-* Verify primality - this function is slow but useful if you want to
-* ensure that a possibly malicious entity did not provide you with
-* something that 'looks like' a prime
-* @param n a positive integer to test for primality
-* @param rng a random number generator
-* @return true if all primality tests passed, otherwise false
-*/
-inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
- { return primality_test(n, rng, 2); }
+bool BOTAN_DLL check_prime(const BigInt& n, RandomNumberGenerator& rng);
/**
* Randomly generate a prime
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 08:17:50 +0000