diff options
author | Jack Lloyd <[email protected]> | 2018-04-26 11:52:03 -0400 |
---|---|---|
committer | Jack Lloyd <[email protected]> | 2018-04-26 11:52:03 -0400 |
commit | 178ddff62cc460be771018f48468e114b723da4e (patch) | |
tree | 2b222f50301e4bc9a1cf01792b1c64b175c2eddf /src/lib | |
parent | e66b79e7ad1c99154069c4b94f59f4135b6bd986 (diff) |
Correct handling of gcd(p - 1, e) in RSA keygen
We were calling inverse mod but because p - 1 > e the binary
extended euclidean algorithm was used instead of the const time
version.
Use the fact that e is odd (for RSA keys) to remove the factors of
2 from p - 1 and then check coprimality that way, since it allows
using our const time algo.
Diffstat (limited to 'src/lib')
-rw-r--r-- | src/lib/math/numbertheory/make_prm.cpp | 32 |
1 files changed, 25 insertions, 7 deletions
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp index 85089c9cb..1979fa550 100644 --- a/src/lib/math/numbertheory/make_prm.cpp +++ b/src/lib/math/numbertheory/make_prm.cpp @@ -182,8 +182,13 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng, 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"); + /* + * The restriction on coprime <= 64 bits is arbitrary but generally speaking + * very large RSA public exponents are a bad idea both for performance and due + * to attacks on small d. + */ + if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64) + throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer"); const size_t MAX_ATTEMPTS = 32*1024; @@ -218,13 +223,26 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng, continue; /* - * 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. + * Check if p - 1 and coprime are relatively prime by computing the inverse. + * + * We avoid gcd here because that algorithm is not constant time. + * Modular inverse is (for odd modulus anyway). + * + * We earlier verified that coprime argument is odd. Thus the factors of 2 + * in (p - 1) cannot possibly be factors in coprime, so remove them from p - 1. + * Using an odd modulus allows the const time algorithm to be used. + * + * This assumes coprime < p - 1 which is always true for RSA. */ - if(inverse_mod(p - 1, coprime).is_zero()) + BigInt p1 = p - 1; + p1 >>= low_zero_bits(p1); + if(inverse_mod(coprime, p1).is_zero()) + { + BOTAN_DEBUG_ASSERT(gcd(p1, coprime) > 1); continue; + } + + BOTAN_DEBUG_ASSERT(gcd(p1, coprime) == 1); if(p.bits() > bits) break; |