diff options
Diffstat (limited to 'src/lib')
51 files changed, 1553 insertions, 742 deletions
diff --git a/src/lib/asn1/asn1_time.cpp b/src/lib/asn1/asn1_time.cpp index e64fd57c7..863a064f0 100644 --- a/src/lib/asn1/asn1_time.cpp +++ b/src/lib/asn1/asn1_time.cpp @@ -213,7 +213,7 @@ void X509_Time::set_to(const std::string& t_spec, ASN1_Tag spec_tag) } if(!passes_sanity_check()) - throw Invalid_Argument("Time did not pass sanity check: " + t_spec); + throw Invalid_Argument("Time " + t_spec + " does not seem to be valid"); } /* @@ -221,13 +221,26 @@ void X509_Time::set_to(const std::string& t_spec, ASN1_Tag spec_tag) */ bool X509_Time::passes_sanity_check() const { - if(m_year < 1950 || m_year > 2100) + if(m_year < 1950 || m_year > 2200) return false; if(m_month == 0 || m_month > 12) return false; - if(m_day == 0 || m_day > 31) + + const uint32_t days_in_month[12] = { 31, 28+1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; + + if(m_day == 0 || m_day > days_in_month[m_month-1]) return false; - if(m_hour >= 24 || m_minute > 60 || m_second > 60) + + if(m_month == 2 && m_day == 29) + { + if(m_year % 4 != 0) + return false; // not a leap year + + if(m_year % 100 == 0 && m_year % 400 != 0) + return false; + } + + if(m_hour >= 24 || m_minute >= 60 || m_second > 60) return false; if (m_tag == UTC_TIME) diff --git a/src/lib/asn1/asn1_time.h b/src/lib/asn1/asn1_time.h index 73bf2747f..717c58a7d 100644 --- a/src/lib/asn1/asn1_time.h +++ b/src/lib/asn1/asn1_time.h @@ -72,6 +72,8 @@ bool BOTAN_PUBLIC_API(2,0) operator>=(const X509_Time&, const X509_Time&); bool BOTAN_PUBLIC_API(2,0) operator<(const X509_Time&, const X509_Time&); bool BOTAN_PUBLIC_API(2,0) operator>(const X509_Time&, const X509_Time&); +typedef X509_Time ASN1_Time; + } #endif diff --git a/src/lib/asn1/oid_maps.cpp b/src/lib/asn1/oid_maps.cpp index d0d961e27..e9c671d16 100644 --- a/src/lib/asn1/oid_maps.cpp +++ b/src/lib/asn1/oid_maps.cpp @@ -1,7 +1,7 @@ /* * OID maps * -* This file was automatically generated by ./src/scripts/oids.py on 2018-02-07 +* This file was automatically generated by ./src/scripts/oids.py on 2018-05-02 * * All manual edits to this file will be lost. Edit the script * then regenerate this source file. @@ -114,6 +114,7 @@ std::unordered_map<std::string, std::string> OIDS::load_oid2str_map() { "1.3.36.3.3.2.8.1.1.7", "brainpool256r1" }, { "1.3.36.3.3.2.8.1.1.9", "brainpool320r1" }, { "1.3.6.1.4.1.11591.12.2", "Tiger(24,3)" }, + { "1.3.6.1.4.1.11591.15.1", "OpenPGP.Ed25519" }, { "1.3.6.1.4.1.25258.1.3", "McEliece" }, { "1.3.6.1.4.1.25258.1.5", "XMSS" }, { "1.3.6.1.4.1.25258.1.6.1", "GOST-34.10/EMSA1(SHA-256)" }, @@ -128,6 +129,7 @@ std::unordered_map<std::string, std::string> OIDS::load_oid2str_map() { "1.3.6.1.4.1.25258.3.2.5", "Twofish/OCB" }, { "1.3.6.1.4.1.25258.3.3", "Twofish/CBC" }, { "1.3.6.1.4.1.3029.1.2.1", "ElGamal" }, + { "1.3.6.1.4.1.3029.1.5.1", "OpenPGP.Curve25519" }, { "1.3.6.1.4.1.311.20.2.2", "Microsoft SmartcardLogon" }, { "1.3.6.1.4.1.8301.3.1.2.9.0.38", "secp521r1" }, { "1.3.6.1.5.5.7.1.1", "PKIX.AuthorityInformationAccess" }, @@ -290,6 +292,8 @@ std::unordered_map<std::string, OID> OIDS::load_str2oid_map() { "MGF1", OID({1,2,840,113549,1,1,8}) }, { "McEliece", OID({1,3,6,1,4,1,25258,1,3}) }, { "Microsoft SmartcardLogon", OID({1,3,6,1,4,1,311,20,2,2}) }, + { "OpenPGP.Curve25519", OID({1,3,6,1,4,1,3029,1,5,1}) }, + { "OpenPGP.Ed25519", OID({1,3,6,1,4,1,11591,15,1}) }, { "PBE-PKCS5v20", OID({1,2,840,113549,1,5,13}) }, { "PKCS5.PBKDF2", OID({1,2,840,113549,1,5,12}) }, { "PKCS9.ChallengePassword", OID({1,2,840,113549,1,9,7}) }, diff --git a/src/lib/entropy/dev_random/dev_random.cpp b/src/lib/entropy/dev_random/dev_random.cpp index f37831d2e..56552228a 100644 --- a/src/lib/entropy/dev_random/dev_random.cpp +++ b/src/lib/entropy/dev_random/dev_random.cpp @@ -12,6 +12,7 @@ #include <sys/select.h> #include <sys/stat.h> #include <unistd.h> +#include <errno.h> #include <fcntl.h> namespace Botan { diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp index 212a44fa0..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) { - const size_t x_sw = sig_words(), y_sw = y.sig_words(); + return add(y.data(), y.sig_words(), y.sign()); + } - int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); +BigInt& BigInt::operator+=(word y) + { + 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, 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,10 +90,69 @@ 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<word>& ws) + { + if(this->is_negative() || s.is_negative() || mod.is_negative()) + throw Invalid_Argument("BigInt::mod_add expects all arguments are positive"); + + // TODO add optimized version of this + *this += s; + this->reduce_below(mod, ws); + + return (*this); + } + +BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) + { + if(this->is_negative() || s.is_negative() || mod.is_negative()) + throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive"); + + const size_t t_sw = sig_words(); + const size_t s_sw = s.sig_words(); + const size_t mod_sw = mod.sig_words(); + + if(t_sw > mod_sw || s_sw > mod_sw) + throw Invalid_Argument("BigInt::mod_sub args larger than modulus"); + + int32_t relative_size = bigint_cmp(data(), t_sw, s.data(), s_sw); + + if(relative_size >= 0) + { + // this >= s in which case just subtract + bigint_sub2(mutable_data(), t_sw, s.data(), s_sw); + } + else + { + // Otherwise we must sub s and then add p (or add (p - s) as here) + + ws.resize(mod_sw + 1); + + bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), s_sw); + + if(m_reg.size() < mod_sw) + grow_to(mod_sw); + + word carry = bigint_add2_nc(mutable_data(), m_reg.size(), ws.data(), mod_sw); + BOTAN_ASSERT_NOMSG(carry == 0); } return (*this); diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp index ce9047b15..492a69ad0 100644 --- a/src/lib/math/bigint/big_ops3.cpp +++ b/src/lib/math/bigint/big_ops3.cpp @@ -14,71 +14,89 @@ 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-(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 fd967e66e..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 */ @@ -335,6 +347,18 @@ void BigInt::shrink_to_fit(size_t min_size) m_reg.resize(words); } +#if defined(BOTAN_HAS_VALGRIND) +void BigInt::const_time_poison() const + { + CT::poison(m_reg.data(), m_reg.size()); + } + +void BigInt::const_time_unpoison() const + { + CT::unpoison(m_reg.data(), m_reg.size()); + } +#endif + void BigInt::const_time_lookup(secure_vector<word>& output, const std::vector<BigInt>& vec, size_t idx) diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index 44177de96..d5bd4ad4f 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -165,12 +165,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 */ @@ -266,6 +278,22 @@ class BOTAN_PUBLIC_API(2,0) BigInt final BigInt& rev_sub(const word y[], size_t y_size, secure_vector<word>& ws); /** + * Set *this to (*this + y) % mod + * @param y the BigInt to add - assumed y >= 0 and y < mod + * @param mod the positive modulus + * @param ws a temp workspace + */ + BigInt& mod_add(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); + + /** + * Set *this to (*this - y) % mod + * @param y the BigInt to subtract - assumed y >= 0 and y < mod + * @param mod the positive modulus + * @param ws a temp workspace + */ + BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); + + /** * Return *this below mod * * Assumes that *this is (if anything) only slightly larger than @@ -290,6 +318,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 (this<n) return -1, if (this>n) 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 */ @@ -565,6 +601,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ void encode_words(word out[], size_t size) const; +#if defined(BOTAN_HAS_VALGRIND) + void const_time_poison() const; + void const_time_unpoison() const; +#else + void const_time_poison() const {} + void const_time_unpoison() const {} +#endif + /** * @param rng a random number generator * @param min the minimum value @@ -676,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<word> m_reg; Sign m_signedness = Positive; }; @@ -684,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); +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); + 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); @@ -708,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 */ diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp index 52ad3a4d4..b1add33a4 100644 --- a/src/lib/math/mp/mp_core.cpp +++ b/src/lib/math/mp/mp_core.cpp @@ -157,8 +157,7 @@ word bigint_add3_nc(word z[], const word x[], size_t x_size, */ void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size) { - if(bigint_add2_nc(x, x_size, y, y_size)) - x[x_size] += 1; + x[x_size] += bigint_add2_nc(x, x_size, y, y_size); } /* @@ -212,6 +211,20 @@ void bigint_sub2_rev(word x[], const word y[], size_t y_size) BOTAN_ASSERT(!borrow, "y must be greater than x"); } +int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t sz) + { + word borrow = bigint_sub3(z, x, sz, y, sz); + + CT::unpoison(borrow); + if(borrow) + { + bigint_sub3(z, y, sz, x, sz); + return -1; + } + + return 1; + } + /* * Three Operand Subtraction */ @@ -396,7 +409,7 @@ void bigint_shr2(word y[], const word x[], size_t x_size, * Compare two MP integers */ int32_t bigint_cmp(const word x[], size_t x_size, - const word y[], size_t y_size) + const word y[], size_t y_size) { if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); } diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index a2c39bafa..1fae33987 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -95,6 +95,15 @@ word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size); +/** +* Return abs(x-y), ie if x >= y, then compute z = x - y +* Otherwise compute z = y - x +* No borrow is possible since the result is always >= 0 +* +* Returns 1 if x >= y or -1 if x < y +*/ +int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t size); + /* * Shift Operations */ @@ -134,10 +143,10 @@ void bigint_monty_redc(word z[], size_t ws_size); /** -* Compare x and y +* Compare x and y returning early */ int32_t bigint_cmp(const word x[], size_t x_size, - const word y[], size_t y_size); + const word y[], size_t y_size); /** * Compute ((n1<<bits) + n0) / d diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp index 7322b1c4b..220bd8f9e 100644 --- a/src/lib/math/mp/mp_karat.cpp +++ b/src/lib/math/mp/mp_karat.cpp @@ -101,8 +101,8 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N, word* z0 = z; word* z1 = z + N; - const int32_t cmp0 = bigint_cmp(x0, N2, x1, N2); - const int32_t cmp1 = bigint_cmp(y1, N2, y0, N2); + word* ws0 = workspace; + word* ws1 = workspace + N; clear_mem(workspace, 2*N); @@ -115,34 +115,29 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N, * subtractions and recursively multiply to avoid the timing channel. */ - //if(cmp0 && cmp1) - { - if(cmp0 > 0) - bigint_sub3(z0, x0, N2, x1, N2); - else - bigint_sub3(z0, x1, N2, x0, N2); + // First compute (X_lo - X_hi)*(Y_hi - Y_lo) + const int32_t cmp0 = bigint_sub_abs(z0, x0, x1, N2); + const int32_t cmp1 = bigint_sub_abs(z1, y1, y0, N2); - if(cmp1 > 0) - bigint_sub3(z1, y1, N2, y0, N2); - else - bigint_sub3(z1, y0, N2, y1, N2); + karatsuba_mul(ws0, z0, z1, N2, ws1); + const bool is_negative = cmp0 != cmp1; - karatsuba_mul(workspace, z0, z1, N2, workspace+N); - } + // Compute X_lo * Y_lo + karatsuba_mul(z0, x0, y0, N2, ws1); - karatsuba_mul(z0, x0, y0, N2, workspace+N); - karatsuba_mul(z1, x1, y1, N2, workspace+N); + // Compute X_hi * Y_hi + karatsuba_mul(z1, x1, y1, N2, ws1); - const word ws_carry = bigint_add3_nc(workspace + N, z0, N, z1, N); - word z_carry = bigint_add2_nc(z + N2, N, workspace + N, N); + const word ws_carry = bigint_add3_nc(ws1, z0, N, z1, N); + word z_carry = bigint_add2_nc(z + N2, N, ws1, N); z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1); bigint_add2_nc(z + N + N2, N2, &z_carry, 1); - if((cmp0 == cmp1) || (cmp0 == 0) || (cmp1 == 0)) - bigint_add2(z + N2, 2*N-N2, workspace, N); + if(is_negative) + bigint_sub2(z + N2, 2*N-N2, ws0, N); else - bigint_sub2(z + N2, 2*N-N2, workspace, N); + bigint_add2_nc(z + N2, 2*N-N2, ws0, N); } /* @@ -169,37 +164,30 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[]) word* z0 = z; word* z1 = z + N; - const int32_t cmp = bigint_cmp(x0, N2, x1, N2); + word* ws0 = workspace; + word* ws1 = workspace + N; clear_mem(workspace, 2*N); // See comment in karatsuba_mul + bigint_sub_abs(z0, x0, x1, N2); + karatsuba_sqr(ws0, z0, N2, ws1); - //if(cmp) - { - if(cmp > 0) - bigint_sub3(z0, x0, N2, x1, N2); - else - bigint_sub3(z0, x1, N2, x0, N2); - - karatsuba_sqr(workspace, z0, N2, workspace+N); - } - - karatsuba_sqr(z0, x0, N2, workspace+N); - karatsuba_sqr(z1, x1, N2, workspace+N); + karatsuba_sqr(z0, x0, N2, ws1); + karatsuba_sqr(z1, x1, N2, ws1); - const word ws_carry = bigint_add3_nc(workspace + N, z0, N, z1, N); - word z_carry = bigint_add2_nc(z + N2, N, workspace + N, N); + const word ws_carry = bigint_add3_nc(ws1, z0, N, z1, N); + word z_carry = bigint_add2_nc(z + N2, N, ws1, N); z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1); bigint_add2_nc(z + N + N2, N2, &z_carry, 1); /* - * This is only actually required if cmp is != 0, however - * if cmp==0 then workspace[0:N] == 0 and avoiding the jump - * hides a timing channel. + * This is only actually required if cmp (result of bigint_sub_abs) is != 0, + * however if cmp==0 then ws0[0:N] == 0 and avoiding the jump hides a + * timing channel. */ - bigint_sub2(z + N2, 2*N-N2, workspace, N); + bigint_sub2(z + N2, 2*N-N2, ws0, N); } /* diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp index bd0ae8e92..1979fa550 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,107 @@ 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"); + + /* + * 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; + + 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 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. + */ + BigInt p1 = p - 1; + p1 >>= low_zero_bits(p1); + if(inverse_mod(coprime, p1).is_zero()) + { + BOTAN_DEBUG_ASSERT(gcd(p1, coprime) > 1); continue; + } - if(is_prime(p, rng, prob, true)) + BOTAN_DEBUG_ASSERT(gcd(p1, coprime) == 1); + + if(p.bits() > bits) + break; + + if(is_prime(p, prime_test_rng, prob, true)) return p; } } @@ -156,7 +270,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 +279,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/monty.cpp b/src/lib/math/numbertheory/monty.cpp index 33d15de5b..b33fdf34c 100644 --- a/src/lib/math/numbertheory/monty.cpp +++ b/src/lib/math/numbertheory/monty.cpp @@ -136,6 +136,32 @@ void Montgomery_Params::mul_by(BigInt& x, copy_mem(x.mutable_data(), z_data, output_size); } +void Montgomery_Params::mul_by(BigInt& x, + const BigInt& y, + secure_vector<word>& ws) const + { + const size_t output_size = 2*m_p_words + 2; + + if(ws.size() < 2*output_size) + ws.resize(2*output_size); + + word* z_data = &ws[0]; + word* ws_data = &ws[output_size]; + + bigint_mul(z_data, output_size, + x.data(), x.size(), x.sig_words(), + y.data(), y.size(), y.sig_words(), + ws_data, output_size); + + bigint_monty_redc(z_data, + m_p.data(), m_p_words, m_p_dash, + ws_data, output_size); + + if(x.size() < output_size) + x.grow_to(output_size); + copy_mem(x.mutable_data(), z_data, output_size); + } + BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const { const size_t output_size = 2*m_p_words + 2; @@ -281,17 +307,25 @@ Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) { - m_v += other.m_v; secure_vector<word> ws; - m_v.reduce_below(m_params->p(), ws); + return this->add(other, ws); + } + +Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) + { + m_v.mod_add(other.m_v, m_params->p(), ws); return (*this); } Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) { - m_v -= other.m_v; - if(m_v.is_negative()) - m_v += m_params->p(); + secure_vector<word> ws; + return this->sub(other, ws); + } + +Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) + { + m_v.mod_sub(other.m_v, m_params->p(), ws); return (*this); } @@ -310,7 +344,7 @@ Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) { - m_v = m_params->mul(m_v, other.m_v, ws); + m_params->mul_by(m_v, other.m_v, ws); return (*this); } @@ -318,7 +352,6 @@ Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, secure_vector<word>& ws) { m_params->mul_by(m_v, other, ws); - //m_v = m_params->mul(m_v, other, ws); return (*this); } diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h index 9f369f1a5..7586b634f 100644 --- a/src/lib/math/numbertheory/monty.h +++ b/src/lib/math/numbertheory/monty.h @@ -18,7 +18,7 @@ class Montgomery_Params; /** * The Montgomery representation of an integer */ -class Montgomery_Int final +class BOTAN_UNSTABLE_API Montgomery_Int final { public: /** @@ -75,6 +75,12 @@ class Montgomery_Int final Montgomery_Int& operator*=(const secure_vector<word>& other); + Montgomery_Int& add(const Montgomery_Int& other, + secure_vector<word>& ws); + + Montgomery_Int& sub(const Montgomery_Int& other, + secure_vector<word>& ws); + Montgomery_Int mul(const Montgomery_Int& other, secure_vector<word>& ws) const; @@ -100,6 +106,9 @@ class Montgomery_Int final Montgomery_Int& mul_by_8(secure_vector<word>& ws); + void const_time_poison() const { m_v.const_time_poison(); } + void const_time_unpoison() const { return m_v.const_time_unpoison(); } + private: std::shared_ptr<const Montgomery_Params> m_params; BigInt m_v; @@ -108,7 +117,7 @@ class Montgomery_Int final /** * Parameters for Montgomery Reduction */ -class Montgomery_Params final +class BOTAN_UNSTABLE_API Montgomery_Params final { public: /** @@ -147,6 +156,9 @@ class Montgomery_Params final const secure_vector<word>& y, secure_vector<word>& ws) const; + void mul_by(BigInt& x, const BigInt& y, + secure_vector<word>& ws) const; + BigInt sqr(const BigInt& x, secure_vector<word>& ws) const; diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp index 4bf281fa9..b32a7ab4c 100644 --- a/src/lib/math/numbertheory/monty_exp.cpp +++ b/src/lib/math/numbertheory/monty_exp.cpp @@ -20,7 +20,8 @@ class Montgomery_Exponentation_State public: Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params, const BigInt& g, - size_t window_bits); + size_t window_bits, + bool const_time); BigInt exponentiation(const BigInt& k) const; @@ -29,13 +30,16 @@ class Montgomery_Exponentation_State std::shared_ptr<const Montgomery_Params> m_params; std::vector<Montgomery_Int> m_g; size_t m_window_bits; + bool m_const_time; }; Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params, const BigInt& g, - size_t window_bits) : + size_t window_bits, + bool const_time) : m_params(params), - m_window_bits(window_bits == 0 ? 4 : window_bits) + m_window_bits(window_bits == 0 ? 4 : window_bits), + m_const_time(const_time) { if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ... throw Invalid_Argument("Invalid window bits for Montgomery exponentiation"); @@ -59,6 +63,8 @@ Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<c for(size_t i = 0; i != window_size; ++i) { m_g[i].fix_size(); + if(const_time) + m_g[i].const_time_poison(); } } @@ -91,6 +97,7 @@ void const_time_lookup(secure_vector<word>& output, BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) const { const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits; + CT::unpoison(exp_nibbles); Montgomery_Int x(m_params, m_params->R1(), false); @@ -111,11 +118,14 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) cons x.mul_by(e_bits, ws); } + x.const_time_unpoison(); return x.value(); } BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const { + BOTAN_ASSERT_NOMSG(m_const_time == false); + const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits; Montgomery_Int x(m_params, m_params->R1(), false); @@ -135,15 +145,17 @@ BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scal x.mul_by(m_g[nibble], ws); } + x.const_time_unpoison(); return x.value(); } std::shared_ptr<const Montgomery_Exponentation_State> monty_precompute(std::shared_ptr<const Montgomery_Params> params, const BigInt& g, - size_t window_bits) + size_t window_bits, + bool const_time) { - return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits); + return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time); } BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state, diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h index 6eeb88e7f..61da258cc 100644 --- a/src/lib/math/numbertheory/monty_exp.h +++ b/src/lib/math/numbertheory/monty_exp.h @@ -24,7 +24,8 @@ class Montgomery_Exponentation_State; std::shared_ptr<const Montgomery_Exponentation_State> monty_precompute(std::shared_ptr<const Montgomery_Params> params_p, const BigInt& g, - size_t window_bits); + size_t window_bits, + bool const_time = true); /* * Return g^x mod p diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp index f2782038b..33e77562e 100644 --- a/src/lib/math/numbertheory/nistp_redc.cpp +++ b/src/lib/math/numbertheory/nistp_redc.cpp @@ -98,20 +98,13 @@ inline uint32_t get_uint32_t(const BigInt& x, size_t i) #endif } -/** -* Treating this MPI as a sequence of 32-bit words in big-endian -* order, set word i to the value x -*/ -template<typename T> -inline void set_uint32_t(BigInt& x, size_t i, T v_in) +inline void set_words(BigInt& x, size_t i, uint32_t R0, uint32_t R1) { - const uint32_t v = static_cast<uint32_t>(v_in); #if (BOTAN_MP_WORD_BITS == 32) - x.set_word_at(i, v); + x.set_word_at(i, R0); + x.set_word_at(i+1, R1); #elif (BOTAN_MP_WORD_BITS == 64) - const word shift_32 = (i % 2) * 32; - const word w = (x.word_at(i/2) & (static_cast<word>(0xFFFFFFFF) << (32-shift_32))) | (static_cast<word>(v) << shift_32); - x.set_word_at(i/2, w); + x.set_word_at(i/2, (static_cast<uint64_t>(R1) << 32) | R0); #else #error "Not implemented" #endif @@ -127,60 +120,97 @@ const BigInt& prime_p192() void redc_p192(BigInt& x, secure_vector<word>& ws) { - const uint32_t X6 = get_uint32_t(x, 6); - const uint32_t X7 = get_uint32_t(x, 7); - const uint32_t X8 = get_uint32_t(x, 8); - const uint32_t X9 = get_uint32_t(x, 9); - const uint32_t X10 = get_uint32_t(x, 10); - const uint32_t X11 = get_uint32_t(x, 11); + BOTAN_UNUSED(ws); + + static const size_t p192_limbs = 192 / BOTAN_MP_WORD_BITS; + + const uint64_t X00 = get_uint32_t(x, 0); + const uint64_t X01 = get_uint32_t(x, 1); + const uint64_t X02 = get_uint32_t(x, 2); + const uint64_t X03 = get_uint32_t(x, 3); + const uint64_t X04 = get_uint32_t(x, 4); + const uint64_t X05 = get_uint32_t(x, 5); + const uint64_t X06 = get_uint32_t(x, 6); + const uint64_t X07 = get_uint32_t(x, 7); + const uint64_t X08 = get_uint32_t(x, 8); + const uint64_t X09 = get_uint32_t(x, 9); + const uint64_t X10 = get_uint32_t(x, 10); + const uint64_t X11 = get_uint32_t(x, 11); + + const uint64_t S0 = X00 + X06 + X10; + const uint64_t S1 = X01 + X07 + X11; + const uint64_t S2 = X02 + X06 + X08 + X10; + const uint64_t S3 = X03 + X07 + X09 + X11; + const uint64_t S4 = X04 + X08 + X10; + const uint64_t S5 = X05 + X09 + X11; x.mask_bits(192); uint64_t S = 0; + uint32_t R0 = 0, R1 = 0; - S += get_uint32_t(x, 0); - S += X6; - S += X10; - set_uint32_t(x, 0, S); + S += S0; + R0 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 1); - S += X7; - S += X11; - set_uint32_t(x, 1, S); + S += S1; + R1 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 2); - S += X6; - S += X8; - S += X10; - set_uint32_t(x, 2, S); + set_words(x, 0, R0, R1); + + S += S2; + R0 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 3); - S += X7; - S += X9; - S += X11; - set_uint32_t(x, 3, S); + S += S3; + R1 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 4); - S += X8; - S += X10; - set_uint32_t(x, 4, S); + set_words(x, 2, R0, R1); + + S += S4; + R0 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 5); - S += X9; - S += X11; - set_uint32_t(x, 5, S); + S += S5; + R1 = static_cast<uint32_t>(S); S >>= 32; - set_uint32_t(x, 6, S); + set_words(x, 4, R0, R1); // No underflow possible - x.reduce_below(prime_p192(), ws); + BOTAN_ASSERT(S <= 2, "Expected overflow in P-192 reduce"); + + /* + This is a table of (i*P-192) % 2**192 for i in 1...3 + */ + static const word p192_mults[3][p192_limbs] = { +#if (BOTAN_MP_WORD_BITS == 64) + {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF}, + {0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFD, 0xFFFFFFFFFFFFFFFF}, + {0xFFFFFFFFFFFFFFFD, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFFF}, +#else + {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, + {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, + {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, +#endif + }; + + if(S == 0 && x.word_at(p192_limbs-1) < p192_mults[0][p192_limbs-1]) + { + return; + } + + word borrow = bigint_sub2(x.mutable_data(), x.size(), p192_mults[S], p192_limbs); + + BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-192 reduction"); + + if(borrow) + { + bigint_add2(x.mutable_data(), x.size() - 1, p192_mults[0], p192_limbs); + } } const BigInt& prime_p224() @@ -191,74 +221,104 @@ const BigInt& prime_p224() void redc_p224(BigInt& x, secure_vector<word>& ws) { - const uint32_t X7 = get_uint32_t(x, 7); - const uint32_t X8 = get_uint32_t(x, 8); - const uint32_t X9 = get_uint32_t(x, 9); - const uint32_t X10 = get_uint32_t(x, 10); - const uint32_t X11 = get_uint32_t(x, 11); - const uint32_t X12 = get_uint32_t(x, 12); - const uint32_t X13 = get_uint32_t(x, 13); + BOTAN_UNUSED(ws); - x.mask_bits(224); + const int64_t X00 = get_uint32_t(x, 0); + const int64_t X01 = get_uint32_t(x, 1); + const int64_t X02 = get_uint32_t(x, 2); + const int64_t X03 = get_uint32_t(x, 3); + const int64_t X04 = get_uint32_t(x, 4); + const int64_t X05 = get_uint32_t(x, 5); + const int64_t X06 = get_uint32_t(x, 6); + const int64_t X07 = get_uint32_t(x, 7); + const int64_t X08 = get_uint32_t(x, 8); + const int64_t X09 = get_uint32_t(x, 9); + const int64_t X10 = get_uint32_t(x, 10); + const int64_t X11 = get_uint32_t(x, 11); + const int64_t X12 = get_uint32_t(x, 12); + const int64_t X13 = get_uint32_t(x, 13); // One full copy of P224 is added, so the result is always positive + const int64_t S0 = 0x00000001 + X00 - X07 - X11; + const int64_t S1 = 0x00000000 + X01 - X08 - X12; + const int64_t S2 = 0x00000000 + X02 - X09 - X13; + const int64_t S3 = 0xFFFFFFFF + X03 + X07 + X11 - X10; + const int64_t S4 = 0xFFFFFFFF + X04 + X08 + X12 - X11; + const int64_t S5 = 0xFFFFFFFF + X05 + X09 + X13 - X12; + const int64_t S6 = 0xFFFFFFFF + X06 + X10 - X13; + + x.mask_bits(224); + int64_t S = 0; + uint32_t R0 = 0, R1 = 0; - S += get_uint32_t(x, 0); - S += 1; - S -= X7; - S -= X11; - set_uint32_t(x, 0, S); + S += S0; + R0 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 1); - S -= X8; - S -= X12; - set_uint32_t(x, 1, S); + S += S1; + R1 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 2); - S -= X9; - S -= X13; - set_uint32_t(x, 2, S); + set_words(x, 0, R0, R1); + + S += S2; + R0 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 3); - S += 0xFFFFFFFF; - S += X7; - S += X11; - S -= X10; - set_uint32_t(x, 3, S); + S += S3; + R1 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 4); - S += 0xFFFFFFFF; - S += X8; - S += X12; - S -= X11; - set_uint32_t(x, 4, S); + set_words(x, 2, R0, R1); + + S += S4; + R0 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 5); - S += 0xFFFFFFFF; - S += X9; - S += X13; - S -= X12; - set_uint32_t(x, 5, S); + S += S5; + R1 = static_cast<uint32_t>(S); S >>= 32; - S += get_uint32_t(x, 6); - S += 0xFFFFFFFF; - S += X10; - S -= X13; - set_uint32_t(x, 6, S); + set_words(x, 4, R0, R1); + + S += S6; + R0 = static_cast<uint32_t>(S); S >>= 32; - set_uint32_t(x, 7, S); - BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); + set_words(x, 6, R0, 0); + + BOTAN_ASSERT(S >= 0 && S <= 2, "Expected overflow in P-224 reduce"); + + static const size_t p224_limbs = (BOTAN_MP_WORD_BITS == 32) ? 7 : 4; + + static const word p224_mults[3][p224_limbs] = { +#if (BOTAN_MP_WORD_BITS == 64) + {0x0000000000000001, 0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF}, + {0x0000000000000002, 0xFFFFFFFE00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF}, + {0x0000000000000003, 0xFFFFFFFD00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF}, +#else + {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, + {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, + {0x00000003, 0x00000000, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} +#endif - x.reduce_below(prime_p224(), ws); + }; + + if(S == 0 && x.word_at(p224_limbs-1) < p224_mults[0][p224_limbs-1]) + { + return; + } + + word borrow = bigint_sub2(x.mutable_data(), x.size(), p224_mults[S], p224_limbs); + + BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-224 reduction"); + + if(borrow) + { + bigint_add2(x.mutable_data(), x.size() - 1, p224_mults[0], p224_limbs); + } } const BigInt& prime_p256() @@ -273,116 +333,80 @@ void redc_p256(BigInt& x, secure_vector<word>& ws) BOTAN_UNUSED(ws); - const uint32_t X8 = get_uint32_t(x, 8); - const uint32_t X9 = get_uint32_t(x, 9); - const uint32_t X10 = get_uint32_t(x, 10); - const uint32_t X11 = get_uint32_t(x, 11); - const uint32_t X12 = get_uint32_t(x, 12); - const uint32_t X13 = get_uint32_t(x, 13); - const uint32_t X14 = get_uint32_t(x, 14); - const uint32_t X15 = get_uint32_t(x, 15); + const int64_t X00 = get_uint32_t(x, 0); + const int64_t X01 = get_uint32_t(x, 1); + const int64_t X02 = get_uint32_t(x, 2); + const int64_t X03 = get_uint32_t(x, 3); + const int64_t X04 = get_uint32_t(x, 4); + const int64_t X05 = get_uint32_t(x, 5); + const int64_t X06 = get_uint32_t(x, 6); + const int64_t X07 = get_uint32_t(x, 7); + const int64_t X08 = get_uint32_t(x, 8); + const int64_t X09 = get_uint32_t(x, 9); + const int64_t X10 = get_uint32_t(x, 10); + const int64_t X11 = get_uint32_t(x, 11); + const int64_t X12 = get_uint32_t(x, 12); + const int64_t X13 = get_uint32_t(x, 13); + const int64_t X14 = get_uint32_t(x, 14); + const int64_t X15 = get_uint32_t(x, 15); + + // Adds 6 * P-256 to prevent underflow + const int64_t S0 = 0xFFFFFFFA + X00 + X08 + X09 - X11 - X12 - X13 - X14; + const int64_t S1 = 0xFFFFFFFF + X01 + X09 + X10 - X12 - X13 - X14 - X15; + const int64_t S2 = 0xFFFFFFFF + X02 + X10 + X11 - X13 - X14 - X15; + const int64_t S3 = 0x00000005 + X03 + (X11 + X12)*2 + X13 - X15 - X08 - X09; + const int64_t S4 = 0x00000000 + X04 + (X12 + X13)*2 + X14 - X09 - X10; + const int64_t S5 = 0x00000000 + X05 + (X13 + X14)*2 + X15 - X10 - X11; + const int64_t S6 = 0x00000006 + X06 + X13 + X14*3 + X15*2 - X08 - X09; + const int64_t S7 = 0xFFFFFFFA + X07 + X15*3 + X08 - X10 - X11 - X12 - X13; x.mask_bits(256); x.shrink_to_fit(p256_limbs + 1); int64_t S = 0; - // Adds 6 * P-256 to prevent underflow + uint32_t R0 = 0, R1 = 0; + + S += S0; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S1; + R1 = static_cast<uint32_t>(S); + S >>= 32; - S = get_uint32_t(x, 0); - S += 0xFFFFFFFA; - S += X8; - S += X9; - S -= X11; - S -= X12; - S -= X13; - S -= X14; - set_uint32_t(x, 0, S); - S >>= 32; - - S += get_uint32_t(x, 1); - S += 0xFFFFFFFF; - S += X9; - S += X10; - S -= X12; - S -= X13; - S -= X14; - S -= X15; - set_uint32_t(x, 1, S); - S >>= 32; - - S += get_uint32_t(x, 2); - S += 0xFFFFFFFF; - S += X10; - S += X11; - S -= X13; - S -= X14; - S -= X15; - set_uint32_t(x, 2, S); - S >>= 32; - - S += get_uint32_t(x, 3); - S += 5; - S += X11; - S += X11; - S += X12; - S += X12; - S += X13; - S -= X15; - S -= X8; - S -= X9; - set_uint32_t(x, 3, S); - S >>= 32; - - S += get_uint32_t(x, 4); - S += X12; - S += X12; - S += X13; - S += X13; - S += X14; - S -= X9; - S -= X10; - set_uint32_t(x, 4, S); - S >>= 32; - - S += get_uint32_t(x, 5); - S += X13; - S += X13; - S += X14; - S += X14; - S += X15; - S -= X10; - S -= X11; - set_uint32_t(x, 5, S); - S >>= 32; - - S += get_uint32_t(x, 6); - S += 6; - S += X14; - S += X14; - S += X15; - S += X15; - S += X14; - S += X13; - S -= X8; - S -= X9; - set_uint32_t(x, 6, S); - S >>= 32; - - S += get_uint32_t(x, 7); - S += 0xFFFFFFFA; - S += X15; - S += X15; - S += X15; - S += X8; - S -= X10; - S -= X11; - S -= X12; - S -= X13; - set_uint32_t(x, 7, S); - S >>= 32; - - S += 5; // final carry of 6*P-256 + set_words(x, 0, R0, R1); + + S += S2; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S3; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 2, R0, R1); + + S += S4; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S5; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 4, R0, R1); + + S += S6; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S7; + R1 = static_cast<uint32_t>(S); + S >>= 32; + set_words(x, 6, R0, R1); + + S += 5; // the top digits of 6*P-256 BOTAN_ASSERT(S >= 0 && S <= 10, "Expected overflow"); @@ -417,6 +441,11 @@ void redc_p256(BigInt& x, secure_vector<word>& ws) #endif }; + if(S == 0 && x.word_at(p256_limbs-1) < p256_mults[0][p256_limbs-1]) + { + return; + } + word borrow = bigint_sub2(x.mutable_data(), x.size(), p256_mults[S], p256_limbs); BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-256 reduction"); @@ -439,149 +468,112 @@ void redc_p384(BigInt& x, secure_vector<word>& ws) static const size_t p384_limbs = (BOTAN_MP_WORD_BITS == 32) ? 12 : 6; - const uint32_t X12 = get_uint32_t(x, 12); - const uint32_t X13 = get_uint32_t(x, 13); - const uint32_t X14 = get_uint32_t(x, 14); - const uint32_t X15 = get_uint32_t(x, 15); - const uint32_t X16 = get_uint32_t(x, 16); - const uint32_t X17 = get_uint32_t(x, 17); - const uint32_t X18 = get_uint32_t(x, 18); - const uint32_t X19 = get_uint32_t(x, 19); - const uint32_t X20 = get_uint32_t(x, 20); - const uint32_t X21 = get_uint32_t(x, 21); - const uint32_t X22 = get_uint32_t(x, 22); - const uint32_t X23 = get_uint32_t(x, 23); + const int64_t X00 = get_uint32_t(x, 0); + const int64_t X01 = get_uint32_t(x, 1); + const int64_t X02 = get_uint32_t(x, 2); + const int64_t X03 = get_uint32_t(x, 3); + const int64_t X04 = get_uint32_t(x, 4); + const int64_t X05 = get_uint32_t(x, 5); + const int64_t X06 = get_uint32_t(x, 6); + const int64_t X07 = get_uint32_t(x, 7); + const int64_t X08 = get_uint32_t(x, 8); + const int64_t X09 = get_uint32_t(x, 9); + const int64_t X10 = get_uint32_t(x, 10); + const int64_t X11 = get_uint32_t(x, 11); + const int64_t X12 = get_uint32_t(x, 12); + const int64_t X13 = get_uint32_t(x, 13); + const int64_t X14 = get_uint32_t(x, 14); + const int64_t X15 = get_uint32_t(x, 15); + const int64_t X16 = get_uint32_t(x, 16); + const int64_t X17 = get_uint32_t(x, 17); + const int64_t X18 = get_uint32_t(x, 18); + const int64_t X19 = get_uint32_t(x, 19); + const int64_t X20 = get_uint32_t(x, 20); + const int64_t X21 = get_uint32_t(x, 21); + const int64_t X22 = get_uint32_t(x, 22); + const int64_t X23 = get_uint32_t(x, 23); + + // One copy of P-384 is added to prevent underflow + const int64_t S0 = 0xFFFFFFFF + X00 + X12 + X20 + X21 - X23; + const int64_t S1 = 0x00000000 + X01 + X13 + X22 + X23 - X12 - X20; + const int64_t S2 = 0x00000000 + X02 + X14 + X23 - X13 - X21; + const int64_t S3 = 0xFFFFFFFF + X03 + X12 + X15 + X20 + X21 - X14 - X22 - X23; + const int64_t S4 = 0xFFFFFFFE + X04 + X12 + X13 + X16 + X20 + X21*2 + X22 - X15 - X23*2; + const int64_t S5 = 0xFFFFFFFF + X05 + X13 + X14 + X17 + X21 + X22*2 + X23 - X16; + const int64_t S6 = 0xFFFFFFFF + X06 + X14 + X15 + X18 + X22 + X23*2 - X17; + const int64_t S7 = 0xFFFFFFFF + X07 + X15 + X16 + X19 + X23 - X18; + const int64_t S8 = 0xFFFFFFFF + X08 + X16 + X17 + X20 - X19; + const int64_t S9 = 0xFFFFFFFF + X09 + X17 + X18 + X21 - X20; + const int64_t SA = 0xFFFFFFFF + X10 + X18 + X19 + X22 - X21; + const int64_t SB = 0xFFFFFFFF + X11 + X19 + X20 + X23 - X22; x.mask_bits(384); x.shrink_to_fit(p384_limbs + 1); int64_t S = 0; - // One copy of P-384 is added to prevent underflow - S = get_uint32_t(x, 0); - S += 0xFFFFFFFF; - S += X12; - S += X21; - S += X20; - S -= X23; - set_uint32_t(x, 0, S); - S >>= 32; - - S += get_uint32_t(x, 1); - S += X13; - S += X22; - S += X23; - S -= X12; - S -= X20; - set_uint32_t(x, 1, S); - S >>= 32; - - S += get_uint32_t(x, 2); - S += X14; - S += X23; - S -= X13; - S -= X21; - set_uint32_t(x, 2, S); - S >>= 32; - - S += get_uint32_t(x, 3); - S += 0xFFFFFFFF; - S += X15; - S += X12; - S += X20; - S += X21; - S -= X14; - S -= X22; - S -= X23; - set_uint32_t(x, 3, S); - S >>= 32; - - S += get_uint32_t(x, 4); - S += 0xFFFFFFFE; - S += X21; - S += X21; - S += X16; - S += X13; - S += X12; - S += X20; - S += X22; - S -= X15; - S -= X23; - S -= X23; - set_uint32_t(x, 4, S); - S >>= 32; - - S += get_uint32_t(x, 5); - S += 0xFFFFFFFF; - S += X22; - S += X22; - S += X17; - S += X14; - S += X13; - S += X21; - S += X23; - S -= X16; - set_uint32_t(x, 5, S); - S >>= 32; - - S += get_uint32_t(x, 6); - S += 0xFFFFFFFF; - S += X23; - S += X23; - S += X18; - S += X15; - S += X14; - S += X22; - S -= X17; - set_uint32_t(x, 6, S); - S >>= 32; - - S += get_uint32_t(x, 7); - S += 0xFFFFFFFF; - S += X19; - S += X16; - S += X15; - S += X23; - S -= X18; - set_uint32_t(x, 7, S); - S >>= 32; - - S += get_uint32_t(x, 8); - S += 0xFFFFFFFF; - S += X20; - S += X17; - S += X16; - S -= X19; - set_uint32_t(x, 8, S); - S >>= 32; - - S += get_uint32_t(x, 9); - S += 0xFFFFFFFF; - S += X21; - S += X18; - S += X17; - S -= X20; - set_uint32_t(x, 9, S); - S >>= 32; - - S += get_uint32_t(x, 10); - S += 0xFFFFFFFF; - S += X22; - S += X19; - S += X18; - S -= X21; - set_uint32_t(x, 10, S); - S >>= 32; - - S += get_uint32_t(x, 11); - S += 0xFFFFFFFF; - S += X23; - S += X20; - S += X19; - S -= X22; - set_uint32_t(x, 11, S); + uint32_t R0 = 0, R1 = 0; + + S += S0; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S1; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 0, R0, R1); + + S += S2; + R0 = static_cast<uint32_t>(S); S >>= 32; + S += S3; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 2, R0, R1); + + S += S4; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S5; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 4, R0, R1); + + S += S6; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S7; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 6, R0, R1); + + S += S8; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += S9; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 8, R0, R1); + + S += SA; + R0 = static_cast<uint32_t>(S); + S >>= 32; + + S += SB; + R1 = static_cast<uint32_t>(S); + S >>= 32; + + set_words(x, 10, R0, R1); + BOTAN_ASSERT(S >= 0 && S <= 4, "Expected overflow in P-384 reduction"); /* @@ -609,6 +601,11 @@ void redc_p384(BigInt& x, secure_vector<word>& ws) #endif }; + if(S == 0 && x.word_at(p384_limbs-1) < p384_mults[0][p384_limbs-1]) + { + return; + } + word borrow = bigint_sub2(x.mutable_data(), x.size(), p384_mults[S], p384_limbs); BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-384 reduction"); diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp index 76d7936bc..10f44a1ee 100644 --- a/src/lib/math/numbertheory/numthry.cpp +++ b/src/lib/math/numbertheory/numthry.cpp @@ -8,9 +8,11 @@ #include <botan/numthry.h> #include <botan/pow_mod.h> #include <botan/reducer.h> +#include <botan/monty.h> #include <botan/internal/bit_ops.h> #include <botan/internal/mp_core.h> #include <botan/internal/ct_utils.h> +#include <botan/internal/monty_exp.h> #include <algorithm> 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<uint8_t>(X[0] >= X[1]); + + X[sel^1] -= X[sel]; + X[sel^1] >>= 1; } - return (y << shift); + return (X[1] << shift); } /* @@ -453,22 +461,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; @@ -499,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<Montgomery_Params>(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; 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/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 <botan/dsa.h> #include <botan/keypair.h> -#include <botan/pow_mod.h> #include <botan/reducer.h> #include <botan/rng.h> #include <botan/internal/pk_ops_impl.h> diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp index 8953edba4..112213d6c 100644 --- a/src/lib/pubkey/ec_group/curve_gfp.cpp +++ b/src/lib/pubkey/ec_group/curve_gfp.cpp @@ -34,8 +34,14 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr m_r3 = mod_p.multiply(m_r, m_r2); m_a_r = mod_p.multiply(m_r, m_a); m_b_r = mod_p.multiply(m_r, m_b); + + m_a_is_zero = m_a.is_zero(); + m_a_is_minus_3 = (m_a + 3 == m_p); } + bool a_is_zero() const override { return m_a_is_zero; } + bool a_is_minus_3() const override { return m_a_is_minus_3; } + const BigInt& get_a() const override { return m_a; } const BigInt& get_b() const override { return m_b; } @@ -46,6 +52,8 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr const BigInt& get_b_rep() const override { return m_b_r; } + const BigInt& get_1_rep() const override { return m_r; } + bool is_one(const BigInt& x) const override { return x == m_r; } size_t get_p_words() const override { return m_p_words; } @@ -78,6 +86,9 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr // Montgomery parameters BigInt m_r, m_r2, m_r3; word m_p_dash; + + bool m_a_is_zero; + bool m_a_is_minus_3; }; BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const @@ -188,14 +199,20 @@ class CurveGFp_NIST : public CurveGFp_Repr { public: CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : - m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) + m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) { + // All Solinas prime curves are assumed a == -3 } + bool a_is_zero() const override { return false; } + bool a_is_minus_3() const override { return true; } + const BigInt& get_a() const override { return m_a; } const BigInt& get_b() const override { return m_b; } + const BigInt& get_1_rep() const override { return m_1; } + size_t get_p_words() const override { return m_p_words; } size_t get_ws_size() const override { return 2*m_p_words + 4; } @@ -223,17 +240,29 @@ class CurveGFp_NIST : public CurveGFp_Repr const BigInt& y, secure_vector<word>& ws) const override; + void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector<word>& ws) const + { + curve_mul(tmp, x, y, ws); + x.swap(tmp); + } + + void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const + { + curve_sqr(tmp, x, ws); + x.swap(tmp); + } + void curve_sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const override; private: virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0; // Curve parameters + BigInt m_1; BigInt m_a, m_b; size_t m_p_words; // cache of m_p.sig_words() }; - BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const { BOTAN_UNUSED(ws); @@ -340,8 +369,71 @@ class CurveGFp_P256 final : public CurveGFp_NIST const BigInt& get_p() const override { return prime_p256(); } private: void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); } + BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; }; +BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const + { + BigInt r, p2, p4, p8, p16, p32, tmp; + + curve_sqr(r, x, ws); + + curve_mul(p2, r, x, ws); + curve_sqr(r, p2, ws); + curve_sqr_tmp(r, tmp, ws); + + curve_mul(p4, r, p2, ws); + + curve_sqr(r, p4, ws); + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul(p8, r, p4, ws);; + + curve_sqr(r, p8, ws); + for(size_t i = 0; i != 7; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul(p16, r, p8, ws); + + curve_sqr(r, p16, ws); + for(size_t i = 0; i != 15; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul(p32, r, p16, ws); + + curve_sqr(r, p32, ws); + for(size_t i = 0; i != 31; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + for(size_t i = 0; i != 32*4; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p32, tmp, ws); + + for(size_t i = 0; i != 32; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p32, tmp, ws); + + for(size_t i = 0; i != 16; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p16, tmp, ws); + for(size_t i = 0; i != 8; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p8, tmp, ws); + + for(size_t i = 0; i != 4; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p4, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, p2, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + return r; + } + /** * The NIST P-384 curve */ @@ -352,8 +444,80 @@ class CurveGFp_P384 final : public CurveGFp_NIST const BigInt& get_p() const override { return prime_p384(); } private: void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); } + BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; }; +BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const + { + BigInt r, x2, x3, x15, x30, tmp, rl; + + r = x; + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + x2 = r; + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + x3 = r; + + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x3, tmp, ws); + + rl = r; + for(size_t i = 0; i != 6; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x3, tmp, ws); + + x15 = r; + for(size_t i = 0; i != 15; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x15, tmp, ws); + + x30 = r; + for(size_t i = 0; i != 30; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x30, tmp, ws); + + rl = r; + for(size_t i = 0; i != 60; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 120; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + for(size_t i = 0; i != 15; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x15, tmp, ws); + + for(size_t i = 0; i != 31; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x30, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x2, tmp, ws); + + for(size_t i = 0; i != 94; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x30, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + + curve_mul_tmp(r, x, tmp, ws); + + return r; + } + #endif /** @@ -366,8 +530,76 @@ class CurveGFp_P521 final : public CurveGFp_NIST const BigInt& get_p() const override { return prime_p521(); } private: void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); } + BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; }; +BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const + { + BigInt r; + BigInt rl; + BigInt a7; + BigInt tmp; + + curve_sqr(r, x, ws); + curve_mul_tmp(r, x, tmp, ws); + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + rl = r; + + for(size_t i = 0; i != 3; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + a7 = r; // need this value later + + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + rl = r; + for(size_t i = 0; i != 8; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 16; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 32; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 64; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 128; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + rl = r; + for(size_t i = 0; i != 256; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, rl, tmp, ws); + + for(size_t i = 0; i != 7; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, a7, tmp, ws); + + for(size_t i = 0; i != 2; ++i) + curve_sqr_tmp(r, tmp, ws); + curve_mul_tmp(r, x, tmp, ws); + + return r; + } + } std::shared_ptr<CurveGFp_Repr> diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h index 8a83a9c41..865bb68f8 100644 --- a/src/lib/pubkey/ec_group/curve_gfp.h +++ b/src/lib/pubkey/ec_group/curve_gfp.h @@ -30,6 +30,10 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr virtual bool is_one(const BigInt& x) const = 0; + virtual bool a_is_zero() const = 0; + + virtual bool a_is_minus_3() const = 0; + /* * Returns to_curve_rep(get_a()) */ @@ -40,6 +44,11 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr */ virtual const BigInt& get_b_rep() const = 0; + /* + * Returns to_curve_rep(1) + */ + virtual const BigInt& get_1_rep() const = 0; + virtual BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const = 0; virtual void to_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0; @@ -116,6 +125,11 @@ class BOTAN_UNSTABLE_API CurveGFp final const BigInt& get_b_rep() const { return m_repr->get_b_rep(); } + const BigInt& get_1_rep() const { return m_repr->get_1_rep(); } + + bool a_is_minus_3() const { return m_repr->a_is_minus_3(); } + bool a_is_zero() const { return m_repr->a_is_zero(); } + bool is_one(const BigInt& x) const { return m_repr->is_one(x); } BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp index 1fb762e4b..ac23aa151 100644 --- a/src/lib/pubkey/ec_group/ec_group.cpp +++ b/src/lib/pubkey/ec_group/ec_group.cpp @@ -43,7 +43,8 @@ class EC_Group_Data final m_oid(oid), m_p_bits(p.bits()), m_order_bits(order.bits()), - m_a_is_minus_3(a == p - 3) + m_a_is_minus_3(a == p - 3), + m_a_is_zero(a.is_zero()) { } @@ -79,6 +80,7 @@ class EC_Group_Data final const PointGFp& base_point() const { return m_base_point; } bool a_is_minus_3() const { return m_a_is_minus_3; } + bool a_is_zero() const { return m_a_is_zero; } BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); } @@ -87,6 +89,11 @@ class EC_Group_Data final return m_mod_order.multiply(x, y); } + BigInt inverse_mod_order(const BigInt& x) const + { + return inverse_mod(x, m_order); + } + PointGFp blinded_base_point_multiply(const BigInt& k, RandomNumberGenerator& rng, std::vector<BigInt>& ws) const @@ -108,6 +115,7 @@ class EC_Group_Data final size_t m_p_bits; size_t m_order_bits; bool m_a_is_minus_3; + bool m_a_is_zero; }; class EC_Group_Data_Map final @@ -399,6 +407,11 @@ bool EC_Group::a_is_minus_3() const return data().a_is_minus_3(); } +bool EC_Group::a_is_zero() const + { + return data().a_is_zero(); + } + size_t EC_Group::get_p_bits() const { return data().p_bits(); @@ -469,6 +482,11 @@ BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const return data().multiply_mod_order(x, y); } +BigInt EC_Group::inverse_mod_order(const BigInt& x) const + { + return data().inverse_mod_order(x); + } + const OID& EC_Group::get_curve_oid() const { return data().oid(); @@ -520,7 +538,7 @@ PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point, std::vector<BigInt>& ws) const { PointGFp_Var_Point_Precompute mul(point); - mul.randomize_repr(rng); + mul.randomize_repr(rng, ws); return mul.mul(k, rng, get_order(), ws); } diff --git a/src/lib/pubkey/ec_group/ec_group.h b/src/lib/pubkey/ec_group/ec_group.h index 031e5cc34..f273108d2 100644 --- a/src/lib/pubkey/ec_group/ec_group.h +++ b/src/lib/pubkey/ec_group/ec_group.h @@ -132,6 +132,11 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final bool a_is_minus_3() const; /** + * Return if a == 0 mod p + */ + bool a_is_zero() const; + + /** * Return the size of p in bits (same as get_p().bits()) */ size_t get_p_bits() const; @@ -194,6 +199,11 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final BigInt mod_order(const BigInt& x) const; /* + * Return inverse of x modulo the order + */ + BigInt inverse_mod_order(const BigInt& x) const; + + /* * Reduce (x*y) modulo the order */ BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const; diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp index acbda95d4..8f53bb079 100644 --- a/src/lib/pubkey/ec_group/point_gfp.cpp +++ b/src/lib/pubkey/ec_group/point_gfp.cpp @@ -17,20 +17,17 @@ namespace Botan { PointGFp::PointGFp(const CurveGFp& curve) : m_curve(curve), m_coord_x(0), - m_coord_y(1), + m_coord_y(curve.get_1_rep()), m_coord_z(0) { - secure_vector<word> monty_ws(m_curve.get_ws_size()); - m_curve.to_rep(m_coord_x, monty_ws); - m_curve.to_rep(m_coord_y, monty_ws); - m_curve.to_rep(m_coord_z, monty_ws); + // Assumes Montgomery rep of zero is zero } PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) : m_curve(curve), m_coord_x(x), m_coord_y(y), - m_coord_z(1) + m_coord_z(m_curve.get_1_rep()) { if(x <= 0 || x >= curve.get_p()) throw Invalid_Argument("Invalid PointGFp affine x"); @@ -40,7 +37,6 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) : secure_vector<word> monty_ws(m_curve.get_ws_size()); m_curve.to_rep(m_coord_x, monty_ws); m_curve.to_rep(m_coord_y, monty_ws); - m_curve.to_rep(m_coord_z, monty_ws); } void PointGFp::randomize_repr(RandomNumberGenerator& rng) @@ -111,20 +107,20 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, // FIXME avoid the copy here m_coord_x = BigInt(x_words, x_size); m_coord_y = BigInt(y_words, y_size); - m_coord_z = 1; - m_curve.to_rep(m_coord_z, ws_bn[0].get_word_vector()); + m_coord_z = m_curve.get_1_rep(); return; } resize_ws(ws_bn, m_curve.get_ws_size()); secure_vector<word>& ws = ws_bn[0].get_word_vector(); + secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); - BigInt& T0 = ws_bn[1]; - BigInt& T1 = ws_bn[2]; - BigInt& T2 = ws_bn[3]; - BigInt& T3 = ws_bn[4]; - BigInt& T4 = ws_bn[5]; + BigInt& T0 = ws_bn[2]; + BigInt& T1 = ws_bn[3]; + BigInt& T2 = ws_bn[4]; + BigInt& T3 = ws_bn[5]; + BigInt& T4 = ws_bn[6]; /* https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2 @@ -139,13 +135,9 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, m_curve.mul(T2, m_coord_z, T3, ws); // z1^3 m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3 - T4 -= m_coord_x; // x2*z1^2 - x1*z2^2 - if(T4.is_negative()) - T4 += p; + T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2 - T0 -= m_coord_y; - if(T0.is_negative()) - T0 += p; + T0.mod_sub(m_coord_y, p, sub_ws); if(T4.is_zero()) { @@ -157,7 +149,7 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, // setting to zero: m_coord_x = 0; - m_coord_y = 1; + m_coord_y = m_curve.get_1_rep(); m_coord_z = 0; return; } @@ -169,22 +161,16 @@ void PointGFp::add_affine(const word x_words[], size_t x_size, m_curve.mul(T1, T2, T4, ws); m_curve.sqr(m_coord_x, T0, ws); - m_coord_x -= T1; - m_coord_x -= T3; - m_coord_x -= T3; - while(m_coord_x.is_negative()) - m_coord_x += p; + m_coord_x.mod_sub(T1, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); - T3 -= m_coord_x; - if(T3.is_negative()) - T3 += p; + T3.mod_sub(m_coord_x, p, sub_ws); T2 = m_coord_y; m_curve.mul(T2, T0, T3, ws); m_curve.mul(T3, m_coord_y, T1, ws); - T2 -= T3; - if(T2.is_negative()) - T2 += p; + T2.mod_sub(T3, p, sub_ws); m_coord_y = T2; m_curve.mul(T3, m_coord_z, T4, ws); @@ -208,13 +194,14 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) resize_ws(ws_bn, m_curve.get_ws_size()); secure_vector<word>& ws = ws_bn[0].get_word_vector(); + secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); - BigInt& T0 = ws_bn[1]; - BigInt& T1 = ws_bn[2]; - BigInt& T2 = ws_bn[3]; - BigInt& T3 = ws_bn[4]; - BigInt& T4 = ws_bn[5]; - BigInt& T5 = ws_bn[6]; + BigInt& T0 = ws_bn[2]; + BigInt& T1 = ws_bn[3]; + BigInt& T2 = ws_bn[4]; + BigInt& T3 = ws_bn[5]; + BigInt& T4 = ws_bn[6]; + BigInt& T5 = ws_bn[7]; /* https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2 @@ -233,18 +220,13 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) m_curve.mul(T5, m_coord_z, T3, ws); // z1^3 m_curve.mul(T0, rhs.m_coord_y, T5, ws); // y2*z1^3 - T4 -= T1; // x2*z1^2 - x1*z2^2 - if(T4.is_negative()) - T4 += p; + T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2 - T3 = T0; - T3 -= T2; - if(T3.is_negative()) - T3 += p; + T0.mod_sub(T2, p, sub_ws); if(T4.is_zero()) { - if(T3.is_zero()) + if(T0.is_zero()) { mult2(ws_bn); return; @@ -252,36 +234,50 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) // setting to zero: m_coord_x = 0; - m_coord_y = 1; + m_coord_y = m_curve.get_1_rep(); m_coord_z = 0; return; } m_curve.sqr(T5, T4, ws); - m_curve.mul(T0, T1, T5, ws); + m_curve.mul(T3, T1, T5, ws); m_curve.mul(T1, T5, T4, ws); - m_curve.sqr(m_coord_x, T3, ws); - m_coord_x -= T1; - m_coord_x -= T0; - m_coord_x -= T0; - while(m_coord_x.is_negative()) - m_coord_x += p; - - T0 -= m_coord_x; - if(T0.is_negative()) - T0 += p; - - m_curve.mul(m_coord_y, T3, T0, ws); - m_curve.mul(T0, T2, T1, ws); - m_coord_y -= T0; - if(m_coord_y.is_negative()) - m_coord_y += p; - - m_curve.mul(T0, m_coord_z, rhs.m_coord_z, ws); - m_curve.mul(m_coord_z, T0, T4, ws); + m_curve.sqr(m_coord_x, T0, ws); + m_coord_x.mod_sub(T1, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); + m_coord_x.mod_sub(T3, p, sub_ws); + + T3.mod_sub(m_coord_x, p, sub_ws); + + m_curve.mul(m_coord_y, T0, T3, ws); + m_curve.mul(T3, T2, T1, ws); + + m_coord_y.mod_sub(T3, p, sub_ws); + + m_curve.mul(T3, m_coord_z, rhs.m_coord_z, ws); + m_curve.mul(m_coord_z, T3, T4, ws); + } + +void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn) + { + if(iterations == 0) + return; + + if(m_coord_y.is_zero()) + { + *this = PointGFp(m_curve); // setting myself to zero + return; + } + + /* + TODO we can save 2 squarings per iteration by computing + a*Z^4 using values cached from previous iteration + */ + for(size_t i = 0; i != iterations; ++i) + mult2(ws_bn); } // *this *= 2 @@ -299,11 +295,13 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn) resize_ws(ws_bn, m_curve.get_ws_size()); secure_vector<word>& ws = ws_bn[0].get_word_vector(); - BigInt& T0 = ws_bn[1]; - BigInt& T1 = ws_bn[2]; - BigInt& T2 = ws_bn[6]; - BigInt& T3 = ws_bn[4]; - BigInt& T4 = ws_bn[5]; + secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); + + BigInt& T0 = ws_bn[2]; + BigInt& T1 = ws_bn[3]; + BigInt& T2 = ws_bn[4]; + BigInt& T3 = ws_bn[5]; + BigInt& T4 = ws_bn[6]; /* https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc @@ -314,41 +312,64 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn) m_curve.mul(T1, m_coord_x, T0, ws); T1 <<= 2; // * 4 - T1.reduce_below(p, T3.get_word_vector()); + T1.reduce_below(p, sub_ws); + + if(m_curve.a_is_zero()) + { + // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2 + m_curve.sqr(T4, m_coord_x, ws); // x^2 + T4 *= 3; // 3*x^2 + T4.reduce_below(p, sub_ws); + } + else if(m_curve.a_is_minus_3()) + { + /* + if a == -3 then + 3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2) + */ + m_curve.sqr(T3, m_coord_z, ws); // z^2 - m_curve.sqr(T3, m_coord_z, ws); // z^2 - m_curve.sqr(T4, T3, ws); // z^4 - m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); + // (x-z^2) + T2 = m_coord_x; + T2.mod_sub(T3, p, sub_ws); - m_curve.sqr(T4, m_coord_x, ws); - T4 *= 3; - T4 += T3; - T4.reduce_below(p, T3.get_word_vector()); + // (x+z^2) + T3.mod_add(m_coord_x, p, sub_ws); + + m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2) + + T4 *= 3; // 3*(x-z^2)*(x+z^2) + T4.reduce_below(p, sub_ws); + } + else + { + m_curve.sqr(T3, m_coord_z, ws); // z^2 + m_curve.sqr(T4, T3, ws); // z^4 + m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4 + + m_curve.sqr(T4, m_coord_x, ws); // x^2 + T4 *= 3; // 3*x^2 + T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4 + } m_curve.sqr(T2, T4, ws); - T2 -= T1; - T2 -= T1; - while(T2.is_negative()) - T2 += p; + T2.mod_sub(T1, p, sub_ws); + T2.mod_sub(T1, p, sub_ws); m_curve.sqr(T3, T0, ws); T3 <<= 3; - T3.reduce_below(p, T0.get_word_vector()); + T3.reduce_below(p, sub_ws); - T1 -= T2; - while(T1.is_negative()) - T1 += p; + T1.mod_sub(T2, p, sub_ws); m_curve.mul(T0, T4, T1, ws); - T0 -= T3; - if(T0.is_negative()) - T0 += p; + T0.mod_sub(T3, p, sub_ws); m_coord_x = T2; m_curve.mul(T2, m_coord_y, m_coord_z, ws); T2 <<= 1; - T2.reduce_below(p, T3.get_word_vector()); + T2.reduce_below(p, sub_ws); m_coord_y = T0; m_coord_z = T2; @@ -426,13 +447,11 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points, */ const CurveGFp& curve = points[0].m_curve; + const BigInt& rep_1 = curve.get_1_rep(); if(ws.size() < curve.get_ws_size()) ws.resize(curve.get_ws_size()); - BigInt rep_1 = 1; - curve.to_rep(rep_1, ws); - std::vector<BigInt> c(points.size()); c[0] = points[0].m_coord_z; @@ -479,8 +498,7 @@ void PointGFp::force_affine() const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws); m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws); m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws); - m_coord_z = 1; - m_curve.to_rep(m_coord_z, ws); + m_coord_z = m_curve.get_1_rep(); } bool PointGFp::is_affine() const diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h index 2a9948fde..cce2adcc6 100644 --- a/src/lib/pubkey/ec_group/point_gfp.h +++ b/src/lib/pubkey/ec_group/point_gfp.h @@ -49,7 +49,7 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final HYBRID = 2 }; - enum { WORKSPACE_SIZE = 7 }; + enum { WORKSPACE_SIZE = 8 }; /** * Construct an uninitialized PointGFp @@ -152,6 +152,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final const BigInt& get_y() const { return m_coord_y; } const BigInt& get_z() const { return m_coord_z; } + void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z) + { + m_coord_x.swap(new_x); + m_coord_y.swap(new_y); + m_coord_z.swap(new_z); + } + /** * Force this point to affine coordinates */ @@ -236,6 +243,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final void mult2(std::vector<BigInt>& workspace); /** + * Repeated point doubling + * @param i number of doublings to perform + * @param workspace temp space, at least WORKSPACE_SIZE elements + */ + void mult2i(size_t i, std::vector<BigInt>& workspace); + + /** * Point addition * @param other the point to add to *this * @param workspace temp space, at least WORKSPACE_SIZE elements @@ -249,6 +263,18 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final } /** + * Point doubling + * @param workspace temp space, at least WORKSPACE_SIZE elements + * @return *this doubled + */ + PointGFp double_of(std::vector<BigInt>& workspace) const + { + PointGFp x = (*this); + x.mult2(workspace); + return x; + } + + /** * Return the zero (aka infinite) point associated with this curve */ PointGFp zero() const { return PointGFp(m_curve); } diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp index d052b837c..17087a6ed 100644 --- a/src/lib/pubkey/ec_group/point_mul.cpp +++ b/src/lib/pubkey/ec_group/point_mul.cpp @@ -140,22 +140,54 @@ PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& poi { m_window_bits = 4; + std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); + m_U.resize(1U << m_window_bits); m_U[0] = point.zero(); m_U[1] = point; - std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); - for(size_t i = 2; i < m_U.size(); ++i) + for(size_t i = 2; i < m_U.size(); i += 2) { - m_U[i] = m_U[i-1]; - m_U[i].add(point, ws); + m_U[i] = m_U[i/2].double_of(ws); + m_U[i+1] = m_U[i].plus(point, ws); } } -void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng) +void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng, + std::vector<BigInt>& ws_bn) { + if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS <= 1) + return; + + if(ws_bn.size() < 7) + ws_bn.resize(7); + + BigInt& mask = ws_bn[0]; + BigInt& mask2 = ws_bn[1]; + BigInt& mask3 = ws_bn[2]; + BigInt& new_x = ws_bn[3]; + BigInt& new_y = ws_bn[4]; + BigInt& new_z = ws_bn[5]; + secure_vector<word>& ws = ws_bn[6].get_word_vector(); + + const CurveGFp& curve = m_U[0].get_curve(); + + // Skipping zero point since it can't be randomized for(size_t i = 1; i != m_U.size(); ++i) - m_U[i].randomize_repr(rng); + { + mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false); + // Easy way of ensuring mask != 0 + mask.set_bit(0); + + curve.sqr(mask2, mask, ws); + curve.mul(mask3, mask, mask2, ws); + + curve.mul(new_x, m_U[i].get_x(), mask2, ws); + curve.mul(new_y, m_U[i].get_y(), mask3, ws); + curve.mul(new_z, m_U[i].get_z(), mask, ws); + + m_U[i].swap_coords(new_x, new_y, new_z); + } } PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k, @@ -193,8 +225,7 @@ PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k, while(windows) { - for(size_t i = 0; i != m_window_bits; ++i) - R.mult2(ws); + R.mult2i(m_window_bits, ws); const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_window_bits, m_window_bits); // cache side channel here, we are relying on blinding... @@ -261,8 +292,7 @@ PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1, { if(i > 0) { - H.mult2(ws); - H.mult2(ws); + H.mult2i(2, ws); } const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2); diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h index cfce05d5c..a85c2bee9 100644 --- a/src/lib/pubkey/ec_group/point_mul.h +++ b/src/lib/pubkey/ec_group/point_mul.h @@ -15,7 +15,7 @@ class Modular_Reducer; static const size_t PointGFp_SCALAR_BLINDING_BITS = 80; -class PointGFp_Base_Point_Precompute +class PointGFp_Base_Point_Precompute final { public: PointGFp_Base_Point_Precompute(const PointGFp& base_point, @@ -38,12 +38,13 @@ class PointGFp_Base_Point_Precompute std::vector<word> m_W; }; -class PointGFp_Var_Point_Precompute +class PointGFp_Var_Point_Precompute final { public: PointGFp_Var_Point_Precompute(const PointGFp& point); - void randomize_repr(RandomNumberGenerator& rng); + void randomize_repr(RandomNumberGenerator& rng, + std::vector<BigInt>& ws); PointGFp mul(const BigInt& k, RandomNumberGenerator& rng, @@ -54,7 +55,7 @@ class PointGFp_Var_Point_Precompute std::vector<PointGFp> m_U; }; -class PointGFp_Multi_Point_Precompute +class PointGFp_Multi_Point_Precompute final { public: PointGFp_Multi_Point_Precompute(const PointGFp& g1, diff --git a/src/lib/pubkey/ecc_key/ecc_key.cpp b/src/lib/pubkey/ecc_key/ecc_key.cpp index 7c46a2fa0..2c23c1b47 100644 --- a/src/lib/pubkey/ecc_key/ecc_key.cpp +++ b/src/lib/pubkey/ecc_key/ecc_key.cpp @@ -118,8 +118,6 @@ EC_PrivateKey::EC_PrivateKey(RandomNumberGenerator& rng, else m_domain_encoding = EC_DOMPAR_ENC_EXPLICIT; - const BigInt& order = m_domain_params.get_order(); - if(x == 0) { m_private_key = ec_group.random_scalar(rng); @@ -133,7 +131,7 @@ EC_PrivateKey::EC_PrivateKey(RandomNumberGenerator& rng, if(with_modular_inverse) { // ECKCDSA - m_public_key = domain().get_base_point() * inverse_mod(m_private_key, order); + m_public_key = domain().get_base_point() * m_domain_params.inverse_mod_order(m_private_key); } else { @@ -183,8 +181,7 @@ EC_PrivateKey::EC_PrivateKey(const AlgorithmIdentifier& alg_id, if(with_modular_inverse) { // ECKCDSA - const BigInt& order = m_domain_params.get_order(); - m_public_key = domain().get_base_point() * inverse_mod(m_private_key, order); + m_public_key = domain().get_base_point() * m_domain_params.inverse_mod_order(m_private_key); } else { diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp index adadb2703..59f245a00 100644 --- a/src/lib/pubkey/ecdh/ecdh.cpp +++ b/src/lib/pubkey/ecdh/ecdh.cpp @@ -31,7 +31,7 @@ class ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF m_group(key.domain()), m_rng(rng) { - m_l_times_priv = inverse_mod(m_group.get_cofactor(), m_group.get_order()) * key.private_value(); + m_l_times_priv = m_group.inverse_mod_order(m_group.get_cofactor()) * key.private_value(); } secure_vector<uint8_t> raw_agree(const uint8_t w[], size_t w_len) override diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp index 03f5e57ab..6e104f164 100644 --- a/src/lib/pubkey/ecdsa/ecdsa.cpp +++ b/src/lib/pubkey/ecdsa/ecdsa.cpp @@ -89,7 +89,7 @@ ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len, const BigInt k = m_group.random_scalar(rng); #endif - const BigInt k_inv = inverse_mod(k, m_group.get_order()); + const BigInt k_inv = m_group.inverse_mod_order(k); const BigInt r = m_group.mod_order( m_group.blinded_base_point_multiply_x(k, rng, m_ws)); @@ -142,7 +142,7 @@ bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order()) return false; - const BigInt w = inverse_mod(s, m_group.get_order()); + const BigInt w = m_group.inverse_mod_order(s); const BigInt u1 = m_group.multiply_mod_order(e, w); const BigInt u2 = m_group.multiply_mod_order(r, w); diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp index 062bb524d..61b7ae055 100644 --- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp +++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp @@ -10,6 +10,7 @@ #include <botan/keypair.h> #include <botan/reducer.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> namespace Botan { @@ -86,7 +87,7 @@ class ECGDSA_Verification_Operation final : public PK_Ops::Verification_with_EMS const std::string& emsa) : PK_Ops::Verification_with_EMSA(emsa), m_group(ecgdsa.domain()), - m_public_point(ecgdsa.public_point()) + m_gy_mul(m_group.get_base_point(), ecgdsa.public_point()) { } @@ -98,7 +99,7 @@ class ECGDSA_Verification_Operation final : public PK_Ops::Verification_with_EMS const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; }; bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, @@ -115,11 +116,11 @@ bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order()) return false; - const BigInt w = inverse_mod(r, m_group.get_order()); + const BigInt w = m_group.inverse_mod_order(r); const BigInt u1 = m_group.multiply_mod_order(e, w); const BigInt u2 = m_group.multiply_mod_order(s, w); - const PointGFp R = m_group.point_multiply(u1, m_public_point, u2); + const PointGFp R = m_gy_mul.multi_exp(u1, u2); if(R.is_zero()) return false; diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp index f16fb027e..90716228a 100644 --- a/src/lib/pubkey/eckcdsa/eckcdsa.cpp +++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp @@ -8,6 +8,7 @@ #include <botan/eckcdsa.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> #include <botan/keypair.h> #include <botan/reducer.h> #include <botan/emsa.h> @@ -113,11 +114,11 @@ class ECKCDSA_Verification_Operation final : public PK_Ops::Verification_with_EM const std::string& emsa) : PK_Ops::Verification_with_EMSA(emsa), m_group(eckcdsa.domain()), - m_public_point(eckcdsa.public_point()), + m_gy_mul(m_group.get_base_point(), eckcdsa.public_point()), m_prefix() { - const BigInt public_point_x = m_public_point.get_affine_x(); - const BigInt public_point_y = m_public_point.get_affine_y(); + const BigInt public_point_x = eckcdsa.public_point().get_affine_x(); + const BigInt public_point_y = eckcdsa.public_point().get_affine_y(); m_prefix.resize(public_point_x.bytes() + public_point_y.bytes()); public_point_x.binary_encode(&m_prefix[0]); @@ -136,7 +137,7 @@ class ECKCDSA_Verification_Operation final : public PK_Ops::Verification_with_EM const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; secure_vector<uint8_t> m_prefix; }; @@ -169,7 +170,7 @@ bool ECKCDSA_Verification_Operation::verify(const uint8_t msg[], size_t, BigInt w(r_xor_e.data(), r_xor_e.size()); w = m_group.mod_order(w); - const PointGFp q = m_group.point_multiply(w, m_public_point, s); + const PointGFp q = m_gy_mul.multi_exp(w, s); const BigInt q_x = q.get_affine_x(); secure_vector<uint8_t> c(q_x.bytes()); q_x.binary_encode(c.data()); diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp index 0fcca1b8d..1d1b0d75e 100644 --- a/src/lib/pubkey/gost_3410/gost_3410.cpp +++ b/src/lib/pubkey/gost_3410/gost_3410.cpp @@ -9,6 +9,7 @@ #include <botan/gost_3410.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> #include <botan/reducer.h> #include <botan/der_enc.h> #include <botan/ber_dec.h> @@ -151,7 +152,7 @@ class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_ const std::string& emsa) : PK_Ops::Verification_with_EMSA(emsa), m_group(gost.domain()), - m_public_point(gost.public_point()) + m_gy_mul(m_group.get_base_point(), gost.public_point()) {} size_t max_input_bits() const override { return m_group.get_order_bits(); } @@ -162,7 +163,7 @@ class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_ const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; }; bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, @@ -184,12 +185,12 @@ bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_le if(e == 0) e = 1; - const BigInt v = inverse_mod(e, order); + const BigInt v = m_group.inverse_mod_order(e); const BigInt z1 = m_group.multiply_mod_order(s, v); const BigInt z2 = m_group.multiply_mod_order(-r, v); - const PointGFp R = m_group.point_multiply(z1, m_public_point, z2); + const PointGFp R = m_gy_mul.multi_exp(z1, z2); if(R.is_zero()) return false; diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp index 69d7052dc..fdc5b63d0 100644 --- a/src/lib/pubkey/rsa/rsa.cpp +++ b/src/lib/pubkey/rsa/rsa.cpp @@ -141,14 +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 { - m_p = random_prime(rng, (bits + 1) / 2, m_e); - m_q = random_prime(rng, bits - m_p.bits(), m_e); + 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); @@ -356,7 +361,7 @@ class RSA_Public_Operation const size_t powm_window = 1; - auto powm_m_n = monty_precompute(m_monty_n, m, powm_window); + auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false); return monty_execute_vartime(*powm_m_n, m_e); } diff --git a/src/lib/pubkey/sm2/sm2.cpp b/src/lib/pubkey/sm2/sm2.cpp index 4b5610c85..1096ea99f 100644 --- a/src/lib/pubkey/sm2/sm2.cpp +++ b/src/lib/pubkey/sm2/sm2.cpp @@ -8,6 +8,7 @@ #include <botan/sm2.h> #include <botan/internal/pk_ops_impl.h> +#include <botan/internal/point_mul.h> #include <botan/numthry.h> #include <botan/keypair.h> #include <botan/hash.h> @@ -30,7 +31,7 @@ SM2_Signature_PrivateKey::SM2_Signature_PrivateKey(const AlgorithmIdentifier& al const secure_vector<uint8_t>& key_bits) : EC_PrivateKey(alg_id, key_bits) { - m_da_inv = inverse_mod(m_private_key + 1, domain().get_order()); + m_da_inv = domain().inverse_mod_order(m_private_key + 1); } SM2_Signature_PrivateKey::SM2_Signature_PrivateKey(RandomNumberGenerator& rng, @@ -38,7 +39,7 @@ SM2_Signature_PrivateKey::SM2_Signature_PrivateKey(RandomNumberGenerator& rng, const BigInt& x) : EC_PrivateKey(rng, domain, x) { - m_da_inv = inverse_mod(m_private_key + 1, domain.get_order()); + m_da_inv = domain.inverse_mod_order(m_private_key + 1); } std::vector<uint8_t> sm2_compute_za(HashFunction& hash, @@ -136,11 +137,11 @@ class SM2_Verification_Operation final : public PK_Ops::Verification const std::string& ident, const std::string& hash) : m_group(sm2.domain()), - m_public_point(sm2.public_point()), + m_gy_mul(m_group.get_base_point(), sm2.public_point()), m_hash(HashFunction::create_or_throw(hash)) { // ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) - m_za = sm2_compute_za(*m_hash, ident, m_group, m_public_point); + m_za = sm2_compute_za(*m_hash, ident, m_group, sm2.public_point()); m_hash->update(m_za); } @@ -152,7 +153,7 @@ class SM2_Verification_Operation final : public PK_Ops::Verification bool is_valid_signature(const uint8_t sig[], size_t sig_len) override; private: const EC_Group m_group; - const PointGFp& m_public_point; + const PointGFp_Multi_Point_Precompute m_gy_mul; std::vector<uint8_t> m_za; std::unique_ptr<HashFunction> m_hash; }; @@ -178,7 +179,7 @@ bool SM2_Verification_Operation::is_valid_signature(const uint8_t sig[], size_t if(t == 0) return false; - const PointGFp R = m_group.point_multiply(s, m_public_point, t); + const PointGFp R = m_gy_mul.multi_exp(s, t); // ??? if(R.is_zero()) diff --git a/src/lib/pubkey/xmss/xmss_hash.cpp b/src/lib/pubkey/xmss/xmss_hash.cpp index a691453dc..cd714873c 100644 --- a/src/lib/pubkey/xmss/xmss_hash.cpp +++ b/src/lib/pubkey/xmss/xmss_hash.cpp @@ -56,11 +56,6 @@ void XMSS_Hash::h_msg_init(const secure_vector<uint8_t>& randomness, m_msg_hash->update(index_bytes); } -void XMSS_Hash::h_msg_update(const secure_vector<uint8_t>& data) - { - m_msg_hash->update(data); - } - void XMSS_Hash::h_msg_update(const uint8_t data[], size_t size) { m_msg_hash->update(data, size); diff --git a/src/lib/pubkey/xmss/xmss_hash.h b/src/lib/pubkey/xmss/xmss_hash.h index 85cebdc91..f45432d59 100644 --- a/src/lib/pubkey/xmss/xmss_hash.h +++ b/src/lib/pubkey/xmss/xmss_hash.h @@ -120,13 +120,6 @@ class XMSS_Hash final * Adds a message block to buffered h_msg computation. * * @param data A message block - **/ - void h_msg_update(const secure_vector<uint8_t>& data); - - /** - * Adds a message block to buffered h_msg computation. - * - * @param data A message block * @param size Length of the message block in bytes. **/ void h_msg_update(const uint8_t data[], size_t size); diff --git a/src/lib/pubkey/xmss/xmss_signature.cpp b/src/lib/pubkey/xmss/xmss_signature.cpp index 88ef42655..88809cf7b 100644 --- a/src/lib/pubkey/xmss/xmss_signature.cpp +++ b/src/lib/pubkey/xmss/xmss_signature.cpp @@ -1,6 +1,6 @@ /* * XMSS Signature - * (C) 2016,2017 Matthias Gierlings + * (C) 2016,2017,2018 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) **/ @@ -14,24 +14,23 @@ XMSS_Signature::XMSS_Signature(XMSS_Parameters::xmss_algorithm_t oid, const secure_vector<uint8_t>& raw_sig) : m_leaf_idx(0), m_randomness(0, 0x00), m_tree_sig() { - BOTAN_ASSERT(sizeof(size_t) >= std::ceil(static_cast<float>( - (XMSS_Parameters(oid)).tree_height()) / 8.f), - "System type \"size_t\" not big enough to support" - " leaf index."); - XMSS_Parameters xmss_params(oid); - uint64_t leaf_idx = 0; + + if(raw_sig.size() != (xmss_params.len() + xmss_params.tree_height() + 1) + * xmss_params.element_size() + sizeof(m_leaf_idx)) + { + throw Integrity_Failure("XMSS signature size invalid."); + } + for(size_t i = 0; i < 8; i++) - { leaf_idx = ((leaf_idx << 8) | raw_sig[i]); } + { m_leaf_idx = ((m_leaf_idx << 8) | raw_sig[i]); } - if(leaf_idx >= (1ull << (xmss_params.tree_height() - 1))) + if(m_leaf_idx >= (1ull << (xmss_params.tree_height() - 1))) { - throw Integrity_Failure("XMSS signature leaf index out of " - "bounds."); + throw Integrity_Failure("XMSS signature leaf index out of bounds."); } - m_leaf_idx = static_cast<size_t>(leaf_idx); - auto begin = raw_sig.begin() + sizeof(uint64_t); + auto begin = raw_sig.begin() + sizeof(m_leaf_idx); auto end = begin + xmss_params.element_size(); std::copy(begin, end, std::back_inserter(m_randomness)); @@ -64,14 +63,14 @@ secure_vector<uint8_t> XMSS_Signature::bytes() const { secure_vector<uint8_t> result { - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 56U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 48U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 40U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 32U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 24U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 16U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx) >> 8U), - static_cast<uint8_t>(static_cast<uint64_t>(m_leaf_idx)) + static_cast<uint8_t>(m_leaf_idx >> 56U), + static_cast<uint8_t>(m_leaf_idx >> 48U), + static_cast<uint8_t>(m_leaf_idx >> 40U), + static_cast<uint8_t>(m_leaf_idx >> 32U), + static_cast<uint8_t>(m_leaf_idx >> 24U), + static_cast<uint8_t>(m_leaf_idx >> 16U), + static_cast<uint8_t>(m_leaf_idx >> 8U), + static_cast<uint8_t>(m_leaf_idx) }; std::copy(m_randomness.begin(), diff --git a/src/lib/pubkey/xmss/xmss_signature.h b/src/lib/pubkey/xmss/xmss_signature.h index 838aae2e8..25e168fd8 100644 --- a/src/lib/pubkey/xmss/xmss_signature.h +++ b/src/lib/pubkey/xmss/xmss_signature.h @@ -117,7 +117,7 @@ class XMSS_Signature final secure_vector<uint8_t> bytes() const; private: - size_t m_leaf_idx; + uint64_t m_leaf_idx; secure_vector<uint8_t> m_randomness; XMSS_WOTS_PublicKey::TreeSignature m_tree_sig; }; diff --git a/src/lib/pubkey/xmss/xmss_tools.cpp b/src/lib/pubkey/xmss/xmss_tools.cpp index f4f762aeb..585e14f2e 100644 --- a/src/lib/pubkey/xmss/xmss_tools.cpp +++ b/src/lib/pubkey/xmss/xmss_tools.cpp @@ -19,26 +19,28 @@ size_t XMSS_Tools::max_threads() size_t XMSS_Tools::bench_threads() { - if(std::thread::hardware_concurrency() <= 1) + const size_t hardware_concurrency = std::thread::hardware_concurrency(); + + if(hardware_concurrency <= 1) { return 1; } const size_t BENCH_ITERATIONS = 1000; std::vector<std::thread> threads; - threads.reserve(std::thread::hardware_concurrency()); + threads.reserve(hardware_concurrency); std::vector<std::chrono::nanoseconds> durations; - std::vector<size_t> concurrency { std::thread::hardware_concurrency(), - std::thread::hardware_concurrency() / 2 }; + std::vector<size_t> concurrency { hardware_concurrency, + hardware_concurrency / 2 }; for(const auto& cc : concurrency) { - std::vector<XMSS_Hash> hash(std::thread::hardware_concurrency(), + std::vector<XMSS_Hash> hash(hardware_concurrency, XMSS_Hash("SHA-256")); const std::vector<uint8_t> buffer(hash[0].output_length()); std::vector<secure_vector<uint8_t>> data( - std::thread::hardware_concurrency(), + hardware_concurrency, secure_vector<uint8_t>(hash[0].output_length())); auto start = std::chrono::high_resolution_clock::now(); for(size_t i = 0; i < cc; ++i) @@ -46,7 +48,7 @@ size_t XMSS_Tools::bench_threads() auto& hs = hash[i]; auto& d = data[i]; - const size_t n_iters = BENCH_ITERATIONS * (std::thread::hardware_concurrency() / cc); + const size_t n_iters = BENCH_ITERATIONS * (hardware_concurrency / cc); threads.emplace_back(std::thread([n_iters, &hs, &d]() { for(size_t n = 0; n < n_iters; n++) @@ -66,11 +68,19 @@ size_t XMSS_Tools::bench_threads() if(durations[0].count() < durations[1].count()) { +#if defined(BOTAN_TEST_MODE) + return 4; +#else return concurrency[0]; +#endif } else { +#if defined(BOTAN_TEST_MODE) + return 4; +#else return concurrency[1]; +#endif } } diff --git a/src/lib/tls/tls_callbacks.h b/src/lib/tls/tls_callbacks.h index 88e502e89..1e0aca9a9 100644 --- a/src/lib/tls/tls_callbacks.h +++ b/src/lib/tls/tls_callbacks.h @@ -353,40 +353,43 @@ class BOTAN_PUBLIC_API(2,0) Compat_Callbacks final : public Callbacks * @param next_proto is called with ALPN protocol data sent by the client */ BOTAN_DEPRECATED("Use TLS::Callbacks (virtual interface).") - Compat_Callbacks(output_fn output_fn, data_cb app_data_cb, alert_cb alert_cb, + Compat_Callbacks(output_fn data_output_fn, data_cb app_data_cb, alert_cb recv_alert_cb, handshake_cb hs_cb, handshake_msg_cb hs_msg_cb = nullptr, next_protocol_fn next_proto = nullptr) - : m_output_function(output_fn), m_app_data_cb(app_data_cb), - m_alert_cb(std::bind(alert_cb, std::placeholders::_1, nullptr, 0)), + : m_output_function(data_output_fn), m_app_data_cb(app_data_cb), + m_alert_cb(std::bind(recv_alert_cb, std::placeholders::_1, nullptr, 0)), m_hs_cb(hs_cb), m_hs_msg_cb(hs_msg_cb), m_next_proto(next_proto) {} BOTAN_DEPRECATED("Use TLS::Callbacks (virtual interface).") - Compat_Callbacks(output_fn output_fn, data_cb app_data_cb, - std::function<void (Alert)> alert_cb, + Compat_Callbacks(output_fn data_output_fn, data_cb app_data_cb, + std::function<void (Alert)> recv_alert_cb, handshake_cb hs_cb, handshake_msg_cb hs_msg_cb = nullptr, next_protocol_fn next_proto = nullptr) - : m_output_function(output_fn), m_app_data_cb(app_data_cb), - m_alert_cb(alert_cb), + : m_output_function(data_output_fn), m_app_data_cb(app_data_cb), + m_alert_cb(recv_alert_cb), m_hs_cb(hs_cb), m_hs_msg_cb(hs_msg_cb), m_next_proto(next_proto) {} enum class SILENCE_DEPRECATION_WARNING { PLEASE = 0 }; Compat_Callbacks(SILENCE_DEPRECATION_WARNING, - output_fn output_fn, data_cb app_data_cb, - std::function<void (Alert)> alert_cb, + output_fn data_output_fn, data_cb app_data_cb, + std::function<void (Alert)> recv_alert_cb, handshake_cb hs_cb, handshake_msg_cb hs_msg_cb = nullptr, next_protocol_fn next_proto = nullptr) - : m_output_function(output_fn), m_app_data_cb(app_data_cb), - m_alert_cb(alert_cb), - m_hs_cb(hs_cb), m_hs_msg_cb(hs_msg_cb), m_next_proto(next_proto) {} + : m_output_function(data_output_fn), + m_app_data_cb(app_data_cb), + m_alert_cb(recv_alert_cb), + m_hs_cb(hs_cb), + m_hs_msg_cb(hs_msg_cb), + m_next_proto(next_proto) {} Compat_Callbacks(SILENCE_DEPRECATION_WARNING, - output_fn output_fn, data_cb app_data_cb, alert_cb alert_cb, + output_fn data_output_fn, data_cb app_data_cb, alert_cb recv_alert_cb, handshake_cb hs_cb, handshake_msg_cb hs_msg_cb = nullptr, next_protocol_fn next_proto = nullptr) - : m_output_function(output_fn), m_app_data_cb(app_data_cb), - m_alert_cb(std::bind(alert_cb, std::placeholders::_1, nullptr, 0)), + : m_output_function(data_output_fn), m_app_data_cb(app_data_cb), + m_alert_cb(std::bind(recv_alert_cb, std::placeholders::_1, nullptr, 0)), m_hs_cb(hs_cb), m_hs_msg_cb(hs_msg_cb), m_next_proto(next_proto) {} diff --git a/src/lib/tls/tls_channel.cpp b/src/lib/tls/tls_channel.cpp index 6e3e5987b..37f3ec415 100644 --- a/src/lib/tls/tls_channel.cpp +++ b/src/lib/tls/tls_channel.cpp @@ -40,7 +40,7 @@ Channel::Channel(Callbacks& callbacks, Channel::Channel(output_fn out, data_cb app_data_cb, - alert_cb alert_cb, + alert_cb recv_alert_cb, handshake_cb hs_cb, handshake_msg_cb hs_msg_cb, Session_Manager& session_manager, @@ -55,7 +55,7 @@ Channel::Channel(output_fn out, relies on a deprecated API */ Compat_Callbacks::SILENCE_DEPRECATION_WARNING::PLEASE, - out, app_data_cb, alert_cb, hs_cb, hs_msg_cb)), + out, app_data_cb, recv_alert_cb, hs_cb, hs_msg_cb)), m_callbacks(*m_compat_callbacks.get()), m_session_manager(session_manager), m_policy(policy), diff --git a/src/lib/tls/tls_client.cpp b/src/lib/tls/tls_client.cpp index 39e69d8ea..94616c60b 100644 --- a/src/lib/tls/tls_client.cpp +++ b/src/lib/tls/tls_client.cpp @@ -64,10 +64,10 @@ Client::Client(Callbacks& callbacks, init(offer_version, next_protos); } -Client::Client(output_fn output_fn, +Client::Client(output_fn data_output_fn, data_cb proc_cb, - alert_cb alert_cb, - handshake_cb handshake_cb, + alert_cb recv_alert_cb, + handshake_cb hs_cb, Session_Manager& session_manager, Credentials_Manager& creds, const Policy& policy, @@ -76,7 +76,7 @@ Client::Client(output_fn output_fn, const Protocol_Version& offer_version, const std::vector<std::string>& next_protos, size_t io_buf_sz) : - Channel(output_fn, proc_cb, alert_cb, handshake_cb, Channel::handshake_msg_cb(), + Channel(data_output_fn, proc_cb, recv_alert_cb, hs_cb, Channel::handshake_msg_cb(), session_manager, rng, policy, offer_version.is_datagram_protocol(), io_buf_sz), m_creds(creds), m_info(info) @@ -84,10 +84,10 @@ Client::Client(output_fn output_fn, init(offer_version, next_protos); } -Client::Client(output_fn output_fn, +Client::Client(output_fn data_output_fn, data_cb proc_cb, - alert_cb alert_cb, - handshake_cb handshake_cb, + alert_cb recv_alert_cb, + handshake_cb hs_cb, handshake_msg_cb hs_msg_cb, Session_Manager& session_manager, Credentials_Manager& creds, @@ -96,7 +96,7 @@ Client::Client(output_fn output_fn, const Server_Information& info, const Protocol_Version& offer_version, const std::vector<std::string>& next_protos) : - Channel(output_fn, proc_cb, alert_cb, handshake_cb, hs_msg_cb, + Channel(data_output_fn, proc_cb, recv_alert_cb, hs_cb, hs_msg_cb, session_manager, rng, policy, offer_version.is_datagram_protocol()), m_creds(creds), m_info(info) diff --git a/src/lib/tls/tls_client.h b/src/lib/tls/tls_client.h index 67a086e15..63c26b9cd 100644 --- a/src/lib/tls/tls_client.h +++ b/src/lib/tls/tls_client.h @@ -63,15 +63,16 @@ class BOTAN_PUBLIC_API(2,0) Client final : public Channel /** * DEPRECATED. This constructor is only provided for backward - * compatibility and should not be used in new code. - * + * compatibility and should not be used in new code. It will be + * removed in a future release. + * * Set up a new TLS client session * - * @param output_fn is called with data for the outbound socket + * @param data_output_fn is called with data for the outbound socket * * @param app_data_cb is called when new application data is received * - * @param alert_cb is called when a TLS alert is received + * @param recv_alert_cb is called when a TLS alert is received * * @param hs_cb is called when a handshake is completed * @@ -95,9 +96,9 @@ class BOTAN_PUBLIC_API(2,0) Client final : public Channel * values just mean reallocations and copies are more likely. */ BOTAN_DEPRECATED("Use TLS::Client(TLS::Callbacks ...)") - Client(output_fn output_fn, + Client(output_fn data_output_fn, data_cb app_data_cb, - alert_cb alert_cb, + alert_cb recv_alert_cb, handshake_cb hs_cb, Session_Manager& session_manager, Credentials_Manager& creds, diff --git a/src/lib/tls/tls_record.cpp b/src/lib/tls/tls_record.cpp index 1f564a689..b5ea33c07 100644 --- a/src/lib/tls/tls_record.cpp +++ b/src/lib/tls/tls_record.cpp @@ -299,8 +299,15 @@ void decrypt_record(secure_vector<uint8_t>& output, const uint8_t* msg = &record_contents[cs.nonce_bytes_from_record()]; const size_t msg_length = record_len - cs.nonce_bytes_from_record(); + /* + * This early rejection is based just on public information (length of the + * encrypted packet) and so does not leak any information. We used to use + * decode_error here which really is more appropriate, but that confuses some + * tools which are attempting automated detection of padding oracles, + * including older versions of TLS-Attacker. + */ if(msg_length < aead->minimum_final_size()) - throw Decoding_Error("AEAD packet is shorter than the tag"); + throw TLS_Exception(Alert::BAD_RECORD_MAC, "AEAD packet is shorter than the tag"); const size_t ptext_size = aead->output_length(msg_length); diff --git a/src/lib/tls/tls_server.cpp b/src/lib/tls/tls_server.cpp index 786932a1d..2b1885e45 100644 --- a/src/lib/tls/tls_server.cpp +++ b/src/lib/tls/tls_server.cpp @@ -303,9 +303,9 @@ Server::Server(Callbacks& callbacks, } Server::Server(output_fn output, - data_cb data_cb, - alert_cb alert_cb, - handshake_cb handshake_cb, + data_cb got_data_cb, + alert_cb recv_alert_cb, + handshake_cb hs_cb, Session_Manager& session_manager, Credentials_Manager& creds, const Policy& policy, @@ -313,7 +313,7 @@ Server::Server(output_fn output, next_protocol_fn next_proto, bool is_datagram, size_t io_buf_sz) : - Channel(output, data_cb, alert_cb, handshake_cb, + Channel(output, got_data_cb, recv_alert_cb, hs_cb, Channel::handshake_msg_cb(), session_manager, rng, policy, is_datagram, io_buf_sz), m_creds(creds), @@ -323,9 +323,9 @@ Server::Server(output_fn output, Server::Server(output_fn output, - data_cb data_cb, - alert_cb alert_cb, - handshake_cb handshake_cb, + data_cb got_data_cb, + alert_cb recv_alert_cb, + handshake_cb hs_cb, handshake_msg_cb hs_msg_cb, Session_Manager& session_manager, Credentials_Manager& creds, @@ -333,7 +333,7 @@ Server::Server(output_fn output, RandomNumberGenerator& rng, next_protocol_fn next_proto, bool is_datagram) : - Channel(output, data_cb, alert_cb, handshake_cb, hs_msg_cb, + Channel(output, got_data_cb, recv_alert_cb, hs_cb, hs_msg_cb, session_manager, rng, policy, is_datagram), m_creds(creds), m_choose_next_protocol(next_proto) diff --git a/src/lib/tls/tls_server.h b/src/lib/tls/tls_server.h index 7c5d9668f..c55c3f93d 100644 --- a/src/lib/tls/tls_server.h +++ b/src/lib/tls/tls_server.h @@ -61,12 +61,13 @@ class BOTAN_PUBLIC_API(2,0) Server final : public Channel /** * DEPRECATED. This constructor is only provided for backward * compatibility and should not be used in new implementations. + * It will be removed in a future release. */ BOTAN_DEPRECATED("Use TLS::Server(TLS::Callbacks ...)") Server(output_fn output, data_cb data_cb, - alert_cb alert_cb, - handshake_cb handshake_cb, + alert_cb recv_alert_cb, + handshake_cb hs_cb, Session_Manager& session_manager, Credentials_Manager& creds, const Policy& policy, @@ -79,12 +80,13 @@ class BOTAN_PUBLIC_API(2,0) Server final : public Channel /** * DEPRECATED. This constructor is only provided for backward * compatibility and should not be used in new implementations. + * It will be removed in a future release. */ BOTAN_DEPRECATED("Use TLS::Server(TLS::Callbacks ...)") Server(output_fn output, data_cb data_cb, - alert_cb alert_cb, - handshake_cb handshake_cb, + alert_cb recv_alert_cb, + handshake_cb hs_cb, handshake_msg_cb hs_msg_cb, Session_Manager& session_manager, Credentials_Manager& creds, diff --git a/src/lib/utils/bit_ops.h b/src/lib/utils/bit_ops.h index aa41db391..c7e401492 100644 --- a/src/lib/utils/bit_ops.h +++ b/src/lib/utils/bit_ops.h @@ -107,11 +107,36 @@ inline size_t ctz(T n) template<> inline size_t ctz(uint32_t n) { + if(n == 0) + return 32; return __builtin_ctz(n); } -#endif +template<> +inline size_t ctz(uint64_t n) + { + if(n == 0) + return 64; + return __builtin_ctzll(n); + } +template<> +inline size_t high_bit(uint32_t x) + { + if(x == 0) + return 0; + return (32 - __builtin_clz(x)); + } + +template<> +inline size_t high_bit(uint64_t x) + { + if(x == 0) + return 0; + return (64 - __builtin_clzll(x)); + } + +#endif template<typename T> size_t ceil_log2(T x) diff --git a/src/lib/x509/x509_ext.cpp b/src/lib/x509/x509_ext.cpp index b969ad7cf..9686eacda 100644 --- a/src/lib/x509/x509_ext.cpp +++ b/src/lib/x509/x509_ext.cpp @@ -434,6 +434,11 @@ Subject_Key_ID::Subject_Key_ID(const std::vector<uint8_t>& pub_key, const std::s hash->update(pub_key); hash->final(m_key_id.data()); + + // Truncate longer hashes, 192 bits here seems plenty + const size_t max_skid_len = (192 / 8); + if(m_key_id.size() > max_skid_len) + m_key_id.resize(max_skid_len); } /* diff --git a/src/lib/x509/x509self.cpp b/src/lib/x509/x509self.cpp index 78bbe8615..32f21c101 100644 --- a/src/lib/x509/x509self.cpp +++ b/src/lib/x509/x509self.cpp @@ -82,13 +82,10 @@ X509_Certificate create_self_signed_cert(const X509_Cert_Options& opts, extensions.add_new(new Cert_Extension::Key_Usage(constraints), true); } - std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw(hash_fn)); - hash->update(pub_key); - std::vector<uint8_t> skid(hash->output_length()); - hash->final(skid.data()); + std::unique_ptr<Cert_Extension::Subject_Key_ID> skid(new Cert_Extension::Subject_Key_ID(pub_key, hash_fn)); - extensions.add_new(new Cert_Extension::Subject_Key_ID(skid)); - extensions.add_new(new Cert_Extension::Authority_Key_ID(skid)); + extensions.add_new(new Cert_Extension::Authority_Key_ID(skid->get_key_id())); + extensions.add_new(skid.release()); extensions.add_new( new Cert_Extension::Subject_Alternative_Name(subject_alt)); |