aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/math/numbertheory/make_prm.cpp157
-rw-r--r--src/lib/math/numbertheory/numthry.cpp40
-rw-r--r--src/lib/math/numbertheory/numthry.h17
-rw-r--r--src/lib/pubkey/rsa/rsa.cpp8
4 files changed, 179 insertions, 43 deletions
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index bd0ae8e92..85089c9cb 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -12,6 +12,61 @@
namespace Botan {
+namespace {
+
+class Prime_Sieve
+ {
+ public:
+ Prime_Sieve(const BigInt& init_value) : m_sieve(PRIME_TABLE_SIZE)
+ {
+ for(size_t i = 0; i != m_sieve.size(); ++i)
+ m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]);
+ }
+
+ void step(word increment)
+ {
+ for(size_t i = 0; i != m_sieve.size(); ++i)
+ {
+ m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i];
+ }
+ }
+
+ bool passes(bool check_2p1 = false) const
+ {
+ for(size_t i = 0; i != m_sieve.size(); ++i)
+ {
+ /*
+ In this case, p is a multiple of PRIMES[i]
+ */
+ if(m_sieve[i] == 0)
+ return false;
+
+ if(check_2p1)
+ {
+ /*
+ In this case, 2*p+1 will be a multiple of PRIMES[i]
+
+ So if potentially generating a safe prime, we want to
+ avoid this value because 2*p+1 will certainly not be prime.
+
+ See "Safe Prime Generation with a Combined Sieve" M. Wiener
+ https://eprint.iacr.org/2003/186.pdf
+ */
+ if(m_sieve[i] == (PRIMES[i] - 1) / 2)
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ private:
+ std::vector<uint16_t> m_sieve;
+ };
+
+}
+
+
/*
* Generate a random prime
*/
@@ -64,7 +119,6 @@ BigInt random_prime(RandomNumberGenerator& rng,
}
}
- secure_vector<uint16_t> sieve(PRIME_TABLE_SIZE);
const size_t MAX_ATTEMPTS = 32*1024;
while(true)
@@ -79,8 +133,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
// Force p to be equal to equiv mod modulo
p += (modulo - (p % modulo)) + equiv;
- for(size_t i = 0; i != sieve.size(); ++i)
- sieve[i] = static_cast<uint16_t>(p % PRIMES[i]);
+ Prime_Sieve sieve(p);
size_t counter = 0;
while(true)
@@ -94,46 +147,89 @@ BigInt random_prime(RandomNumberGenerator& rng,
p += modulo;
- if(p.bits() > bits)
- break;
+ sieve.step(modulo);
- // Now that p is updated, update the sieve
- for(size_t i = 0; i != sieve.size(); ++i)
- {
- sieve[i] = (sieve[i] + modulo) % PRIMES[i];
- }
+ if(sieve.passes(true) == false)
+ continue;
- bool passes_sieve = true;
- for(size_t i = 0; passes_sieve && (i != sieve.size()); ++i)
+ if(coprime > 1)
{
/*
- In this case, p is a multiple of PRIMES[i]
+ * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The
+ * gcd algorithm is not constant time, but modular inverse is (for
+ * odd modulus anyway). This avoids a side channel attack against RSA
+ * key generation, though RSA keygen should be using generate_rsa_prime.
*/
- if(sieve[i] == 0)
- passes_sieve = false;
+ if(inverse_mod(p - 1, coprime).is_zero())
+ continue;
+ }
- /*
- In this case, 2*p+1 will be a multiple of PRIMES[i]
+ if(p.bits() > bits)
+ break;
- So if generating a safe prime, we want to avoid this value
- because 2*p+1 will not be useful. Since the check is cheap to
- do and doesn't seem to affect the overall distribution of the
- generated primes overmuch it's used in all cases.
+ if(is_prime(p, rng, prob, true))
+ return p;
+ }
+ }
+ }
- See "Safe Prime Generation with a Combined Sieve" M. Wiener
- https://eprint.iacr.org/2003/186.pdf
- */
- if(sieve[i] == (PRIMES[i] - 1) / 2)
- passes_sieve = false;
+BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
+ RandomNumberGenerator& prime_test_rng,
+ size_t bits,
+ const BigInt& coprime,
+ size_t prob)
+ {
+ if(bits < 512)
+ throw Invalid_Argument("generate_rsa_prime bits too small");
+
+ if(coprime <= 1 || coprime.is_even())
+ throw Invalid_Argument("generate_rsa_prime coprime must be odd positive integer");
+
+ const size_t MAX_ATTEMPTS = 32*1024;
+
+ while(true)
+ {
+ BigInt p(keygen_rng, bits);
+
+ // Force lowest and two top bits on
+ p.set_bit(bits - 1);
+ p.set_bit(bits - 2);
+ p.set_bit(0);
+
+ Prime_Sieve sieve(p);
+
+ const word step = 2;
+
+ size_t counter = 0;
+ while(true)
+ {
+ ++counter;
+
+ if(counter > MAX_ATTEMPTS)
+ {
+ break; // don't try forever, choose a new starting point
}
- if(!passes_sieve)
+ p += step;
+
+ sieve.step(step);
+
+ if(sieve.passes() == false)
continue;
- if(coprime > 0 && gcd(p - 1, coprime) != 1)
+ /*
+ * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The
+ * gcd algorithm is not constant time, but modular inverse is (for
+ * odd modulus anyway). This avoids a side channel attack against RSA
+ * key generation.
+ */
+ if(inverse_mod(p - 1, coprime).is_zero())
continue;
- if(is_prime(p, rng, prob, true))
+ if(p.bits() > bits)
+ break;
+
+ if(is_prime(p, prime_test_rng, prob, true))
return p;
}
}
@@ -156,7 +252,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
*/
- q = random_prime(rng, bits - 1, 1, 2, 3, 8);
+ q = random_prime(rng, bits - 1, 0, 2, 3, 8);
p = (q << 1) + 1;
if(is_prime(p, rng, 128, true))
@@ -165,7 +261,6 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
if(is_prime(q, rng, 128, true))
return p;
}
-
}
}
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 76d7936bc..8cc930175 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -453,22 +453,44 @@ 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
/*
+ * If the candidate prime was maliciously constructed, we can't rely
+ * on arguments based on p being random.
+ */
+ if(random == false)
+ return base;
+
+ /*
* 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(random)
{
- 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
+ if(prob <= 80)
+ {
+ if(n_bits >= 1536)
+ return 2; // < 2^-89
+ if(n_bits >= 1024)
+ return 3; // < 2^-89
+ if(n_bits >= 512)
+ return 5; // < 2^-80
+ if(n_bits >= 256)
+ return 11; // < 2^-80
+ }
+
+ if(prob <= 128)
+ {
+ if(n_bits >= 1536)
+ return 4; // < 2^-133
+ if(n_bits >= 1024)
+ return 6; // < 2^-133
+ if(n_bits >= 512)
+ return 12; // < 2^-129
+ if(n_bits >= 256)
+ return 28; // < 2^-128
+ }
}
return base;
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index 61da93bcd..7097979bd 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -189,7 +189,7 @@ inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
/**
-* Randomly generate a prime
+* Randomly generate a prime suitable for discrete logarithm parameters
* @param rng a random number generator
* @param bits how large the resulting prime should be in bits
* @param coprime a positive integer that (prime - 1) should be coprime to
@@ -207,6 +207,21 @@ BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng,
size_t prob = 128);
/**
+* Generate a prime suitable for RSA p/q
+* @param keygen_rng a random number generator
+* @param prime_test_rng a random number generator
+* @param bits how large the resulting prime should be in bits (must be >= 512)
+* @param coprime a positive integer that (prime - 1) should be coprime to
+* @param prob use test so false positive is bounded by 1/2**prob
+* @return random prime with the specified criteria
+*/
+BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng,
+ RandomNumberGenerator& prime_test_rng,
+ size_t bits,
+ const BigInt& coprime,
+ size_t prob = 128);
+
+/**
* Return a 'safe' prime, of the form p=2*q+1 with q prime
* @param rng a random number generator
* @param bits is how long the resulting prime should be
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index df639be58..ca0f414f5 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -143,9 +143,13 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
do
{
- m_p = random_prime(rng, (bits + 1) / 2, m_e);
- m_q = random_prime(rng, bits - m_p.bits(), m_e);
+ const size_t p_bits = (bits + 1) / 2;
+ const size_t q_bits = bits - p_bits;
+
+ m_p = generate_rsa_prime(rng, rng, p_bits, m_e);
+ m_q = generate_rsa_prime(rng, rng, q_bits, m_e);
m_n = m_p * m_q;
+
} while(m_n.bits() != bits);
const BigInt phi_n = lcm(m_p - 1, m_q - 1);
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-20 01:55:37 +0000