From ebb73b99a8ca14c45d64de2619ab0cf6b89b860e Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:40:50 -0400 Subject: Add BigInt functions for adding, subtracting and comparing with words Avoids needless allocations for expressions like x - 1 or y <= 4. --- src/lib/math/bigint/big_ops2.cpp | 64 ++++++++++++++++++++-------------- src/lib/math/bigint/big_ops3.cpp | 75 ++++++++++++++++++++++++++-------------- src/lib/math/bigint/bigint.cpp | 12 +++++++ src/lib/math/bigint/bigint.h | 42 ++++++++++++++++++++++ 4 files changed, 142 insertions(+), 51 deletions(-) diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp index 242635257..39f985566 100644 --- a/src/lib/math/bigint/big_ops2.cpp +++ b/src/lib/math/bigint/big_ops2.cpp @@ -12,32 +12,29 @@ namespace Botan { -/* -* Addition Operator -*/ -BigInt& BigInt::operator+=(const BigInt& y) +BigInt& BigInt::add(const word y[], size_t y_sw, Sign y_sign) { - const size_t x_sw = sig_words(), y_sw = y.sig_words(); + const size_t x_sw = sig_words(); - if(sign() == y.sign()) + if(sign() == y_sign) { const size_t reg_size = std::max(x_sw, y_sw) + 1; if(m_reg.size() < reg_size) grow_to(reg_size); - bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); + bigint_add2(mutable_data(), reg_size - 1, y, y_sw); } else { - const int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); + const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw); if(relative_size < 0) { const size_t reg_size = std::max(x_sw, y_sw); grow_to(reg_size); - bigint_sub2_rev(mutable_data(), y.data(), y_sw); - set_sign(y.sign()); + bigint_sub2_rev(mutable_data(), y, y_sw); + set_sign(y_sign); } else if(relative_size == 0) { @@ -46,37 +43,44 @@ BigInt& BigInt::operator+=(const BigInt& y) } else if(relative_size > 0) { - bigint_sub2(mutable_data(), x_sw, y.data(), y_sw); + bigint_sub2(mutable_data(), x_sw, y, y_sw); } } return (*this); } -/* -* Subtraction Operator -*/ -BigInt& BigInt::operator-=(const BigInt& y) +BigInt& BigInt::operator+=(const BigInt& y) + { + return add(y.data(), y.sig_words(), y.sign()); + } + +BigInt& BigInt::operator+=(word y) { - const size_t x_sw = sig_words(), y_sw = y.sig_words(); + return add(&y, 1, Positive); + } + +BigInt& BigInt::sub(const word y[], size_t y_sw, Sign y_sign) + { + const size_t x_sw = sig_words(); - int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); + int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw); const size_t reg_size = std::max(x_sw, y_sw) + 1; grow_to(reg_size); if(relative_size < 0) { - if(sign() == y.sign()) - bigint_sub2_rev(mutable_data(), y.data(), y_sw); + if(sign() == y_sign) + bigint_sub2_rev(mutable_data(), y, y_sw); else - bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); + bigint_add2(mutable_data(), reg_size - 1, y, y_sw); - set_sign(y.reverse_sign()); + set_sign(y_sign == Positive ? Negative : Positive); } else if(relative_size == 0) { - if(sign() == y.sign()) + if(sign() == y_sign) { clear(); set_sign(Positive); @@ -86,15 +90,25 @@ BigInt& BigInt::operator-=(const BigInt& y) } else if(relative_size > 0) { - if(sign() == y.sign()) - bigint_sub2(mutable_data(), x_sw, y.data(), y_sw); + if(sign() == y_sign) + bigint_sub2(mutable_data(), x_sw, y, y_sw); else - bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); + bigint_add2(mutable_data(), reg_size - 1, y, y_sw); } return (*this); } +BigInt& BigInt::operator-=(const BigInt& y) + { + return sub(y.data(), y.sig_words(), y.sign()); + } + +BigInt& BigInt::operator-=(word y) + { + return sub(&y, 1, Positive); + } + BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector& ws) { if(this->is_negative() || s.is_negative() || mod.is_negative()) diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp index ce9047b15..4f0ba5364 100644 --- a/src/lib/math/bigint/big_ops3.cpp +++ b/src/lib/math/bigint/big_ops3.cpp @@ -14,71 +14,94 @@ namespace Botan { -/* -* Addition Operator -*/ -BigInt operator+(const BigInt& x, const BigInt& y) +namespace { + +BigInt bigint_add(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign) { - const size_t x_sw = x.sig_words(), y_sw = y.sig_words(); + const size_t x_sw = x.sig_words(); BigInt z(x.sign(), std::max(x_sw, y_sw) + 1); - if(x.sign() == y.sign()) - bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); + if(x.sign() == y_sign) + bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw); else { - int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw); + int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw); if(relative_size < 0) { - bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw); - z.set_sign(y.sign()); + bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw); + z.set_sign(y_sign); } else if(relative_size == 0) z.set_sign(BigInt::Positive); else if(relative_size > 0) - bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); + bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw); } return z; } -/* -* Subtraction Operator -*/ -BigInt operator-(const BigInt& x, const BigInt& y) +BigInt bigint_sub(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign) { - const size_t x_sw = x.sig_words(), y_sw = y.sig_words(); + const size_t x_sw = x.sig_words(); - int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw); + int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw); BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1); if(relative_size < 0) { - if(x.sign() == y.sign()) - bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw); + if(x.sign() == y_sign) + bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw); else - bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); - z.set_sign(y.reverse_sign()); + bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw); + z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive); } else if(relative_size == 0) { - if(x.sign() != y.sign()) + if(x.sign() != y_sign) bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1); - z.set_sign(y.reverse_sign()); + z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive); } else if(relative_size > 0) { - if(x.sign() == y.sign()) - bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); + if(x.sign() == y_sign) + bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw); else - bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); + bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw); z.set_sign(x.sign()); } return z; } +} + +BigInt operator+(const BigInt& x, const BigInt& y) + { + return bigint_add(x, y.data(), y.sig_words(), y.sign()); + } + +BigInt operator+(const BigInt& x, word y) + { + return bigint_add(x, &y, 1, BigInt::Positive); + } + +BigInt operator+(word y, const BigInt& x) + { + return bigint_add(x, &y, 1, BigInt::Positive); + } + +BigInt operator-(const BigInt& x, const BigInt& y) + { + return bigint_sub(x, y.data(), y.sig_words(), y.sign()); + } + +BigInt operator-(const BigInt& x, word y) + { + return bigint_sub(x, &y, 1, BigInt::Positive); + } + /* * Multiplication Operator */ diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index 8874195af..39cff666c 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -113,6 +113,18 @@ BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit) randomize(rng, bits, set_high_bit); } +int32_t BigInt::cmp_word(word other) const + { + if(is_negative()) + return -1; // other is positive ... + + const size_t sw = this->sig_words(); + if(sw > 1) + return 1; // must be larger since other is just one word ... + + return bigint_cmp(this->data(), sw, &other, 1); + } + /* * Comparison Function */ diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index bb7a69541..33a1252ab 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -164,12 +164,24 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ BigInt& operator+=(const BigInt& y); + /** + * += operator + * @param y the word to add to this + */ + BigInt& operator+=(word y); + /** * -= operator * @param y the BigInt to subtract from this */ BigInt& operator-=(const BigInt& y); + /** + * -= operator + * @param y the word to subtract from this + */ + BigInt& operator-=(word y); + /** * *= operator * @param y the BigInt to multiply with this @@ -305,6 +317,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ int32_t cmp(const BigInt& n, bool check_signs = true) const; + /** + * Compare this to an integer + * @param n the value to compare with + * @result if (thisn) return 1, if both + * values are identical return 0 [like Perl's <=> operator] + */ + int32_t cmp_word(word n) const; + /** * Test if the integer has an even value * @result true if the integer is even, false otherwise @@ -700,6 +720,10 @@ class BOTAN_PUBLIC_API(2,0) BigInt final size_t idx); private: + + BigInt& add(const word y[], size_t y_words, Sign sign); + BigInt& sub(const word y[], size_t y_words, Sign sign); + secure_vector m_reg; Sign m_signedness = Positive; }; @@ -708,7 +732,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * Arithmetic Operators */ BigInt BOTAN_PUBLIC_API(2,0) operator+(const BigInt& x, const BigInt& y); +BigInt BOTAN_PUBLIC_API(2,7) operator+(const BigInt& x, word y); +BigInt BOTAN_PUBLIC_API(2,7) operator+(word x, const BigInt& y); + BigInt BOTAN_PUBLIC_API(2,0) operator-(const BigInt& x, const BigInt& y); +BigInt BOTAN_PUBLIC_API(2,7) operator-(const BigInt& x, word y); + BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y); BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d); BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m); @@ -732,6 +761,19 @@ inline bool operator<(const BigInt& a, const BigInt& b) inline bool operator>(const BigInt& a, const BigInt& b) { return (a.cmp(b) > 0); } +inline bool operator==(const BigInt& a, word b) + { return (a.cmp_word(b) == 0); } +inline bool operator!=(const BigInt& a, word b) + { return (a.cmp_word(b) != 0); } +inline bool operator<=(const BigInt& a, word b) + { return (a.cmp_word(b) <= 0); } +inline bool operator>=(const BigInt& a, word b) + { return (a.cmp_word(b) >= 0); } +inline bool operator<(const BigInt& a, word b) + { return (a.cmp_word(b) < 0); } +inline bool operator>(const BigInt& a, word b) + { return (a.cmp_word(b) > 0); } + /* * I/O Operators */ -- cgit v1.2.3 From a41779e3c2a9e90726f3ec45fb333af77128663f Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:42:15 -0400 Subject: Rewrite GCD in less branchy way, and use Montgomery in M-R test --- src/lib/math/numbertheory/numthry.cpp | 46 +++++++++++++++++++++++------------ 1 file changed, 30 insertions(+), 16 deletions(-) diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp index 8cc930175..10f44a1ee 100644 --- a/src/lib/math/numbertheory/numthry.cpp +++ b/src/lib/math/numbertheory/numthry.cpp @@ -8,9 +8,11 @@ #include #include #include +#include #include #include #include +#include #include namespace Botan { @@ -46,26 +48,32 @@ size_t low_zero_bits(const BigInt& n) */ BigInt gcd(const BigInt& a, const BigInt& b) { - if(a.is_zero() || b.is_zero()) return 0; - if(a == 1 || b == 1) return 1; + if(a.is_zero() || b.is_zero()) + return 0; + if(a == 1 || b == 1) + return 1; + + BigInt X[2] = { a, b }; + X[0].set_sign(BigInt::Positive); + X[1].set_sign(BigInt::Positive); - BigInt x = a, y = b; - x.set_sign(BigInt::Positive); - y.set_sign(BigInt::Positive); - size_t shift = std::min(low_zero_bits(x), low_zero_bits(y)); + const size_t shift = std::min(low_zero_bits(X[0]), low_zero_bits(X[1])); - x >>= shift; - y >>= shift; + X[0] >>= shift; + X[1] >>= shift; - while(x.is_nonzero()) + while(X[0].is_nonzero()) { - x >>= low_zero_bits(x); - y >>= low_zero_bits(y); - if(x >= y) { x -= y; x >>= 1; } - else { y -= x; y >>= 1; } + X[0] >>= low_zero_bits(X[0]); + X[1] >>= low_zero_bits(X[1]); + + const uint8_t sel = static_cast(X[0] >= X[1]); + + X[sel^1] -= X[sel]; + X[sel^1] >>= 1; } - return (y << shift); + return (X[1] << shift); } /* @@ -521,14 +529,20 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng, const BigInt n_minus_1 = n - 1; const size_t s = low_zero_bits(n_minus_1); + const BigInt nm1_s = n_minus_1 >> s; const Modular_Reducer mod_n(n); - const Fixed_Exponent_Power_Mod pow_mod(n_minus_1 >> s, n); + auto monty_n = std::make_shared(n, mod_n); + + const size_t powm_window = 4; for(size_t i = 0; i != test_iterations; ++i) { const BigInt a = BigInt::random_integer(rng, 2, n_minus_1); - BigInt y = pow_mod(a); + + auto powm_a_n = monty_precompute(monty_n, a, powm_window); + + BigInt y = monty_execute(*powm_a_n, nm1_s); if(mr_witness(std::move(y), mod_n, n_minus_1, s)) return false; -- cgit v1.2.3 From f5aa418e5d345f7054ebf2883fb880991eb7d1c0 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:44:13 -0400 Subject: Add a couple more GCD tests --- src/tests/data/bn/gcd.vec | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/src/tests/data/bn/gcd.vec b/src/tests/data/bn/gcd.vec index c7f630231..4378c9534 100644 --- a/src/tests/data/bn/gcd.vec +++ b/src/tests/data/bn/gcd.vec @@ -2,3 +2,11 @@ X = 259 Y = 4943984437 GCD = 259 + +X = 9298631792927489555577881706641 +Y = 536756618553495860610657489331151 +GCD = 1 + +X = 10022247630053045674847735694652 +Y = 25956 +GCD = 28 -- cgit v1.2.3 From e66b79e7ad1c99154069c4b94f59f4135b6bd986 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:44:25 -0400 Subject: Remove unused include --- src/lib/pubkey/dsa/dsa.cpp | 1 - 1 file changed, 1 deletion(-) diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp index a3a6b9a52..172804972 100644 --- a/src/lib/pubkey/dsa/dsa.cpp +++ b/src/lib/pubkey/dsa/dsa.cpp @@ -8,7 +8,6 @@ #include #include -#include #include #include #include -- cgit v1.2.3 From 178ddff62cc460be771018f48468e114b723da4e Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:52:03 -0400 Subject: 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. --- src/lib/math/numbertheory/make_prm.cpp | 32 +++++++++++++++++++++++++------- 1 file 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; -- cgit v1.2.3 From 0ccee221ca464320f1458aef82c90b1bea163649 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:57:20 -0400 Subject: Add a comment on side channels here --- src/lib/pubkey/rsa/rsa.cpp | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp index ca0f414f5..fdc5b63d0 100644 --- a/src/lib/pubkey/rsa/rsa.cpp +++ b/src/lib/pubkey/rsa/rsa.cpp @@ -141,18 +141,19 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng, m_e = exp; + const size_t p_bits = (bits + 1) / 2; + const size_t q_bits = bits - p_bits; + do { - 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); + // FIXME: lcm calls gcd which is not const time const BigInt phi_n = lcm(m_p - 1, m_q - 1); + // FIXME: this uses binary ext gcd because phi_n is even m_d = inverse_mod(m_e, phi_n); m_d1 = m_d % (m_p - 1); m_d2 = m_d % (m_q - 1); -- cgit v1.2.3 From b2b0ea31a5d3f8b697c3fcb19defbe0adc30aa80 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 13:04:53 -0400 Subject: Inline this operator+ [ci skip] --- src/lib/math/bigint/big_ops3.cpp | 5 ----- src/lib/math/bigint/bigint.h | 2 +- 2 files changed, 1 insertion(+), 6 deletions(-) diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp index 4f0ba5364..492a69ad0 100644 --- a/src/lib/math/bigint/big_ops3.cpp +++ b/src/lib/math/bigint/big_ops3.cpp @@ -87,11 +87,6 @@ BigInt operator+(const BigInt& x, word y) return bigint_add(x, &y, 1, BigInt::Positive); } -BigInt operator+(word y, const BigInt& x) - { - return bigint_add(x, &y, 1, BigInt::Positive); - } - BigInt operator-(const BigInt& x, const BigInt& y) { return bigint_sub(x, y.data(), y.sig_words(), y.sign()); diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index 33a1252ab..d5bd4ad4f 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -733,7 +733,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ BigInt BOTAN_PUBLIC_API(2,0) operator+(const BigInt& x, const BigInt& y); BigInt BOTAN_PUBLIC_API(2,7) operator+(const BigInt& x, word y); -BigInt BOTAN_PUBLIC_API(2,7) operator+(word x, const BigInt& y); +inline BigInt operator+(word x, const BigInt& y) { return y + x; } BigInt BOTAN_PUBLIC_API(2,0) operator-(const BigInt& x, const BigInt& y); BigInt BOTAN_PUBLIC_API(2,7) operator-(const BigInt& x, word y); -- cgit v1.2.3