diff options
| -rw-r--r-- | src/build-data/buildh.in | 6 | ||||
| -rw-r--r-- | src/lib/math/bigint/bigint.cpp | 39 | ||||
| -rw-r--r-- | src/lib/math/bigint/bigint.h | 31 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.cpp | 31 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_nistp.cpp | 500 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_nistp.h | 77 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/point_gfp.cpp | 44 | ||||
| -rw-r--r-- | src/lib/utils/types.h | 1 |
8 files changed, 674 insertions, 55 deletions
diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in index fdb141ffb..02f2731d6 100644 --- a/src/build-data/buildh.in +++ b/src/build-data/buildh.in @@ -50,6 +50,12 @@ otherwise does a byte at a time write via a volatile pointer. */ #define BOTAN_USE_VOLATILE_MEMSET_FOR_ZERO 1 +/* +* If enabled the ECC implementation will use Montgomery ladder +* instead of a fixed window implementation. +*/ +#define BOTAN_CURVE_GFP_USE_MONTGOMERY_LADDER 0 + /* PK key consistency checking toggles */ #define BOTAN_PUBLIC_KEY_STRONG_CHECKS_ON_LOAD 1 #define BOTAN_PRIVATE_KEY_STRONG_CHECKS_ON_LOAD 0 diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index 6acd04f00..b5a8e0dd5 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -1,6 +1,6 @@ /* * BigInt Base -* (C) 1999-2011,2012 Jack Lloyd +* (C) 1999-2011,2012,2014 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -93,15 +93,6 @@ BigInt::BigInt(RandomNumberGenerator& rng, size_t bits) } /* -* Grow the internal storage -*/ -void BigInt::grow_to(size_t n) - { - if(n > size()) - m_reg.resize(round_up<size_t>(n, 8)); - } - -/* * Comparison Function */ s32bit BigInt::cmp(const BigInt& other, bool check_signs) const @@ -155,8 +146,8 @@ u32bit BigInt::to_u32bit() const throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert"); u32bit out = 0; - for(u32bit j = 0; j != 4; ++j) - out = (out << 8) | byte_at(3-j); + for(size_t i = 0; i != 4; ++i) + out = (out << 8) | byte_at(3-i); return out; } @@ -183,30 +174,6 @@ void BigInt::clear_bit(size_t n) } /* -* Clear all but the lowest n bits -*/ -void BigInt::mask_bits(size_t n) - { - if(n == 0) { clear(); return; } - - const size_t top_word = n / MP_WORD_BITS; - const word mask = (static_cast<word>(1) << (n % MP_WORD_BITS)) - 1; - - if(top_word < size()) - clear_mem(&m_reg[top_word+1], size() - (top_word + 1)); - - m_reg[top_word] &= mask; - } - -/* -* Count how many bytes are being used -*/ -size_t BigInt::bytes() const - { - return (bits() + 7) / 8; - } - -/* * Count how many bits are being used */ size_t BigInt::bits() const diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index 4993f5d0c..269a74259 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -269,7 +269,19 @@ class BOTAN_DLL BigInt * Clear all but the lowest n bits * @param n amount of bits to keep */ - void mask_bits(size_t n); + void mask_bits(size_t n) + { + if(n == 0) { clear(); return; } + + const size_t top_word = n / BOTAN_MP_WORD_BITS; + const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1; + + if(top_word < size()) + { + clear_mem(&m_reg[top_word+1], size() - (top_word + 1)); + m_reg[top_word] &= mask; + } + } /** * Return bit value at specified position @@ -315,6 +327,12 @@ class BOTAN_DLL BigInt word word_at(size_t n) const { return ((n < size()) ? m_reg[n] : 0); } + void set_word_at(size_t i, word w) + { + grow_to(i + 1); + m_reg[i] = w; + } + /** * Tests if the sign of the integer is negative * @result true, iff the integer has a negative sign @@ -378,7 +396,7 @@ class BOTAN_DLL BigInt * Give byte length of the integer * @result byte length of the represented integer value */ - size_t bytes() const; + size_t bytes() const { return (bits() + 7) / 8; } /** * Get the bit length of the integer @@ -398,11 +416,18 @@ class BOTAN_DLL BigInt */ const word* data() const { return &m_reg[0]; } + secure_vector<word>& get_word_vector() { return m_reg; } + const secure_vector<word>& get_word_vector() const { return m_reg; } + /** * Increase internal register buffer to at least n words * @param n new size of register */ - void grow_to(size_t n); + void grow_to(size_t n) + { + if(n > size()) + m_reg.resize(n + (8 - n % 8)); + } /** * Fill BigInt with a random number with size of bitsize diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp index 02265b53a..cb21dd04e 100644 --- a/src/lib/math/ec_gfp/curve_gfp.cpp +++ b/src/lib/math/ec_gfp/curve_gfp.cpp @@ -8,6 +8,7 @@ #include <botan/curve_gfp.h> #include <botan/internal/curve_nistp.h> #include <botan/internal/mp_core.h> +#include <botan/internal/mp_asmi.h> namespace Botan { @@ -117,25 +118,30 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, } // Default implementation -void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t /*bound*/) const +void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t bound) const { const BigInt& p = get_p(); + const word* prime = p.data(); + const size_t p_words = get_p_words(); while(x.is_negative()) x += p; - const size_t p_words = get_p_words(); - const word* prime = p.data(); - x.grow_to(p_words + 1); if(ws.size() < p_words + 1) ws.resize(p_words + 1); - //FIXME: take into account bound if > 0 - while(true) + for(size_t i = 0; bound == 0 || i < bound; ++i) { - if(bigint_sub3(&ws[0], x.data(), p_words, prime, p_words)) // borrow? + const word* xd = x.data(); + word borrow = 0; + + for(size_t i = 0; i != p_words; ++i) + ws[i] = word_sub(xd[i], prime[i], &borrow); + ws[p_words] = word_sub(xd[p_words], 0, &borrow); + + if(borrow) break; x.swap_reg(ws); @@ -145,6 +151,17 @@ void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t /*bound std::shared_ptr<CurveGFp_Repr> CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) { +#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) + if(p == CurveGFp_P192::prime()) + return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); + if(p == CurveGFp_P224::prime()) + return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); + if(p == CurveGFp_P256::prime()) + return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); + if(p == CurveGFp_P384::prime()) + return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); +#endif + if(p == CurveGFp_P521::prime()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); diff --git a/src/lib/math/ec_gfp/curve_nistp.cpp b/src/lib/math/ec_gfp/curve_nistp.cpp index d0ccf929a..4f99b54f0 100644 --- a/src/lib/math/ec_gfp/curve_nistp.cpp +++ b/src/lib/math/ec_gfp/curve_nistp.cpp @@ -1,14 +1,12 @@ /* * NIST curve reduction -* (C) 2014 Jack Lloyd +* (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ #include <botan/internal/curve_nistp.h> #include <botan/internal/mp_core.h> -#include <botan/internal/rounding.h> -#include <botan/hex.h> namespace Botan { @@ -92,4 +90,500 @@ void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const normalize(x, ws, max_redc_subtractions()); } +#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) + +namespace { + +/** +* Treating this MPI as a sequence of 32-bit words in big-endian +* order, return word i (or 0 if out of range) +*/ +inline u32bit get_u32bit(const BigInt& x, size_t i) + { +#if (BOTAN_MP_WORD_BITS == 32) + return x.word_at(i); +#elif (BOTAN_MP_WORD_BITS == 64) + return (x.word_at(i/2) >> ((i % 2)*32)); +#else + #error "Not implemented" +#endif + } + +/** +* Treating this MPI as a sequence of 32-bit words in big-endian +* order, set word i to the value x +*/ +inline void set_u32bit(BigInt& x, size_t i, u32bit v) + { +#if (BOTAN_MP_WORD_BITS == 32) + x.set_word_at(i, v); +#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); +#else + #error "Not implemented" +#endif + } + +} + +//static +const BigInt& CurveGFp_P192::prime() + { + static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"); + return p192; + } + +void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const + { + const u32bit X6 = get_u32bit(x, 6); + const u32bit X7 = get_u32bit(x, 7); + const u32bit X8 = get_u32bit(x, 8); + const u32bit X9 = get_u32bit(x, 9); + const u32bit X10 = get_u32bit(x, 10); + const u32bit X11 = get_u32bit(x, 11); + + x.mask_bits(192); + + u64bit S = 0; + + S += get_u32bit(x, 0); + S += X6; + S += X10; + set_u32bit(x, 0, S); + S >>= 32; + + S += get_u32bit(x, 1); + S += X7; + S += X11; + set_u32bit(x, 1, S); + S >>= 32; + + S += get_u32bit(x, 2); + S += X6; + S += X8; + S += X10; + set_u32bit(x, 2, S); + S >>= 32; + + S += get_u32bit(x, 3); + S += X7; + S += X9; + S += X11; + set_u32bit(x, 3, S); + S >>= 32; + + S += get_u32bit(x, 4); + S += X8; + S += X10; + set_u32bit(x, 4, S); + S >>= 32; + + S += get_u32bit(x, 5); + S += X9; + S += X11; + set_u32bit(x, 5, S); + S >>= 32; + + set_u32bit(x, 6, S); + + // No underflow possible + + normalize(x, ws, max_redc_subtractions()); + } + +//static +const BigInt& CurveGFp_P224::prime() + { + static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"); + return p224; + } + +void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const + { + const u32bit X7 = get_u32bit(x, 7); + const u32bit X8 = get_u32bit(x, 8); + const u32bit X9 = get_u32bit(x, 9); + const u32bit X10 = get_u32bit(x, 10); + const u32bit X11 = get_u32bit(x, 11); + const u32bit X12 = get_u32bit(x, 12); + const u32bit X13 = get_u32bit(x, 13); + + x.mask_bits(224); + + // One full copy of P224 is added, so the result is always positive + + int64_t S = 0; + + S += get_u32bit(x, 0); + S += 1; + S -= X7; + S -= X11; + set_u32bit(x, 0, S); + S >>= 32; + + S += get_u32bit(x, 1); + S -= X8; + S -= X12; + set_u32bit(x, 1, S); + S >>= 32; + + S += get_u32bit(x, 2); + S -= X9; + S -= X13; + set_u32bit(x, 2, S); + S >>= 32; + + S += get_u32bit(x, 3); + S += 0xFFFFFFFF; + S += X7; + S += X11; + S -= X10; + set_u32bit(x, 3, S); + S >>= 32; + + S += get_u32bit(x, 4); + S += 0xFFFFFFFF; + S += X8; + S += X12; + S -= X11; + set_u32bit(x, 4, S); + S >>= 32; + + S += get_u32bit(x, 5); + S += 0xFFFFFFFF; + S += X9; + S += X13; + S -= X12; + set_u32bit(x, 5, S); + S >>= 32; + + S += get_u32bit(x, 6); + S += 0xFFFFFFFF; + S += X10; + S -= X13; + set_u32bit(x, 6, S); + S >>= 32; + set_u32bit(x, 7, S); + + BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); + + normalize(x, ws, max_redc_subtractions()); + } + +//static +const BigInt& CurveGFp_P256::prime() + { + static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"); + return p256; + } + +void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const + { + const u32bit X8 = get_u32bit(x, 8); + const u32bit X9 = get_u32bit(x, 9); + const u32bit X10 = get_u32bit(x, 10); + const u32bit X11 = get_u32bit(x, 11); + const u32bit X12 = get_u32bit(x, 12); + const u32bit X13 = get_u32bit(x, 13); + const u32bit X14 = get_u32bit(x, 14); + const u32bit X15 = get_u32bit(x, 15); + + x.mask_bits(256); + + int64_t S = 0; + + // Adds 6 * P-256 to prevent underflow + + S = get_u32bit(x, 0); + S += 0xFFFFFFFA; + S += X8; + S += X9; + S -= X11; + S -= X12; + S -= X13; + S -= X14; + set_u32bit(x, 0, S); + S >>= 32; + + S += get_u32bit(x, 1); + S += 0xFFFFFFFF; + S += X9; + S += X10; + S -= X12; + S -= X13; + S -= X14; + S -= X15; + set_u32bit(x, 1, S); + S >>= 32; + + S += get_u32bit(x, 2); + S += 0xFFFFFFFF; + S += X10; + S += X11; + S -= X13; + S -= X14; + S -= X15; + set_u32bit(x, 2, S); + S >>= 32; + + S += get_u32bit(x, 3); + S += 5; + S += X11; + S += X11; + S += X12; + S += X12; + S += X13; + S -= X15; + S -= X8; + S -= X9; + set_u32bit(x, 3, S); + S >>= 32; + + S += get_u32bit(x, 4); + S += X12; + S += X12; + S += X13; + S += X13; + S += X14; + S -= X9; + S -= X10; + set_u32bit(x, 4, S); + S >>= 32; + + S += get_u32bit(x, 5); + S += X13; + S += X13; + S += X14; + S += X14; + S += X15; + S -= X10; + S -= X11; + set_u32bit(x, 5, S); + S >>= 32; + + S += get_u32bit(x, 6); + S += 6; + S += X14; + S += X14; + S += X15; + S += X15; + S += X14; + S += X13; + S -= X8; + S -= X9; + set_u32bit(x, 6, S); + S >>= 32; + + S += get_u32bit(x, 7); + S += 0xFFFFFFFA; + S += X15; + S += X15; + S += X15; + S += X8; + S -= X10; + S -= X11; + S -= X12; + S -= X13; + set_u32bit(x, 7, S); + S >>= 32; + + S += 5; + set_u32bit(x, 8, S); + + BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); + + if(S >= 2) + { + BOTAN_ASSERT(S <= 10, "Expected overflow"); + static const BigInt P256_mults[9] = { + 2*get_p(), + 3*get_p(), + 4*get_p(), + 5*get_p(), + 6*get_p(), + 7*get_p(), + 8*get_p(), + 9*get_p(), + 10*get_p() + }; + x -= P256_mults[S - 2]; + } + + normalize(x, ws, max_redc_subtractions()); + } + +//static +const BigInt& CurveGFp_P384::prime() + { + static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"); + return p384; + } + +void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const + { + const u32bit X12 = get_u32bit(x, 12); + const u32bit X13 = get_u32bit(x, 13); + const u32bit X14 = get_u32bit(x, 14); + const u32bit X15 = get_u32bit(x, 15); + const u32bit X16 = get_u32bit(x, 16); + const u32bit X17 = get_u32bit(x, 17); + const u32bit X18 = get_u32bit(x, 18); + const u32bit X19 = get_u32bit(x, 19); + const u32bit X20 = get_u32bit(x, 20); + const u32bit X21 = get_u32bit(x, 21); + const u32bit X22 = get_u32bit(x, 22); + const u32bit X23 = get_u32bit(x, 23); + + x.mask_bits(384); + + int64_t S = 0; + + // One copy of P-384 is added to prevent underflow + S = get_u32bit(x, 0); + S += 0xFFFFFFFF; + S += X12; + S += X21; + S += X20; + S -= X23; + set_u32bit(x, 0, S); + S >>= 32; + + S += get_u32bit(x, 1); + S += X13; + S += X22; + S += X23; + S -= X12; + S -= X20; + set_u32bit(x, 1, S); + S >>= 32; + + S += get_u32bit(x, 2); + S += X14; + S += X23; + S -= X13; + S -= X21; + set_u32bit(x, 2, S); + S >>= 32; + + S += get_u32bit(x, 3); + S += 0xFFFFFFFF; + S += X15; + S += X12; + S += X20; + S += X21; + S -= X14; + S -= X22; + S -= X23; + set_u32bit(x, 3, S); + S >>= 32; + + S += get_u32bit(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_u32bit(x, 4, S); + S >>= 32; + + S += get_u32bit(x, 5); + S += 0xFFFFFFFF; + S += X22; + S += X22; + S += X17; + S += X14; + S += X13; + S += X21; + S += X23; + S -= X16; + set_u32bit(x, 5, S); + S >>= 32; + + S += get_u32bit(x, 6); + S += 0xFFFFFFFF; + S += X23; + S += X23; + S += X18; + S += X15; + S += X14; + S += X22; + S -= X17; + set_u32bit(x, 6, S); + S >>= 32; + + S += get_u32bit(x, 7); + S += 0xFFFFFFFF; + S += X19; + S += X16; + S += X15; + S += X23; + S -= X18; + set_u32bit(x, 7, S); + S >>= 32; + + S += get_u32bit(x, 8); + S += 0xFFFFFFFF; + S += X20; + S += X17; + S += X16; + S -= X19; + set_u32bit(x, 8, S); + S >>= 32; + + S += get_u32bit(x, 9); + S += 0xFFFFFFFF; + S += X21; + S += X18; + S += X17; + S -= X20; + set_u32bit(x, 9, S); + S >>= 32; + + S += get_u32bit(x, 10); + S += 0xFFFFFFFF; + S += X22; + S += X19; + S += X18; + S -= X21; + set_u32bit(x, 10, S); + S >>= 32; + + S += get_u32bit(x, 11); + S += 0xFFFFFFFF; + S += X23; + S += X20; + S += X19; + S -= X22; + set_u32bit(x, 11, S); + S >>= 32; + BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); + set_u32bit(x, 12, S); + + if(S >= 2) + { + BOTAN_ASSERT(S <= 4, "Expected overflow"); + + static const BigInt P384_mults[3] = { + 2*get_p(), + 3*get_p(), + 4*get_p() + }; + + x -= P384_mults[S - 2]; + } + + normalize(x, ws, max_redc_subtractions()); + } + +#endif + + } diff --git a/src/lib/math/ec_gfp/curve_nistp.h b/src/lib/math/ec_gfp/curve_nistp.h index 3a1a603c8..0bf707f58 100644 --- a/src/lib/math/ec_gfp/curve_nistp.h +++ b/src/lib/math/ec_gfp/curve_nistp.h @@ -52,6 +52,83 @@ class CurveGFp_NIST : public CurveGFp_Repr size_t m_p_words; // cache of m_p.sig_words() }; +#if (BOTAN_MP_WORD_BITS == 32) || (BOTAN_MP_WORD_BITS == 64) + +#define BOTAN_HAS_CURVEGFP_NISTP_M32 + +/** +* The NIST P-192 curve +*/ +class CurveGFp_P192 : public CurveGFp_NIST + { + public: + CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} + + static const BigInt& prime(); + + const BigInt& get_p() const override { return CurveGFp_P192::prime(); } + + private: + void redc(BigInt& x, secure_vector<word>& ws) const override; + + size_t max_redc_subtractions() const override { return 3; } + }; + +/** +* The NIST P-224 curve +*/ +class CurveGFp_P224 : public CurveGFp_NIST + { + public: + CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} + + static const BigInt& prime(); + + const BigInt& get_p() const override { return CurveGFp_P224::prime(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override; + + size_t max_redc_subtractions() const override { return 3; } + }; + +/** +* The NIST P-256 curve +*/ +class CurveGFp_P256 : public CurveGFp_NIST + { + public: + CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} + + static const BigInt& prime(); + + const BigInt& get_p() const override { return CurveGFp_P256::prime(); } + + private: + void redc(BigInt& x, secure_vector<word>& ws) const override; + + size_t max_redc_subtractions() const override { return 10; } + }; + +/** +* The NIST P-384 curve +*/ +class CurveGFp_P384 : public CurveGFp_NIST + { + public: + CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} + + static const BigInt& prime(); + + const BigInt& get_p() const override { return CurveGFp_P384::prime(); } + + private: + void redc(BigInt& x, secure_vector<word>& ws) const override; + + size_t max_redc_subtractions() const override { return 4; } + }; + +#endif + /** * The NIST P-521 curve */ diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp index 103bb35b5..2505e4d54 100644 --- a/src/lib/math/ec_gfp/point_gfp.cpp +++ b/src/lib/math/ec_gfp/point_gfp.cpp @@ -277,17 +277,16 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point) const size_t scalar_bits = scalar.bits(); - PointGFp x1 = PointGFp(curve); - PointGFp x2 = point; + PointGFp x1(curve); // zero size_t bits_left = scalar_bits; - // Montgomery Ladder +#if BOTAN_CURVE_GFP_USE_MONTGOMERY_LADDER + + PointGFp x2 = point; while(bits_left) { - const bool bit_set = scalar.get_bit(bits_left - 1); - - if(bit_set) + if(scalar.get_bit(bits_left - 1)) { x1.add(x2, ws); x2.mult2(ws); @@ -301,6 +300,39 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point) --bits_left; } +#else + const size_t window_bits = 4; + + std::vector<PointGFp> Ps(1 << window_bits); + Ps[0] = x1; + Ps[1] = point; + + for(size_t i = 2; i < Ps.size(); ++i) + { + Ps[i] = Ps[i-1]; + Ps[i].add(point, ws); + } + + while(bits_left >= window_bits) + { + for(size_t i = 0; i != window_bits; ++i) + x1.mult2(ws); + + const u32bit nibble = scalar.get_substring(bits_left - window_bits, window_bits); + x1.add(Ps[nibble], ws); + bits_left -= window_bits; + } + + while(bits_left) + { + x1.mult2(ws); + if(scalar.get_bit(bits_left-1)) + x1.add(point, ws); + --bits_left; + } + +#endif + if(scalar.is_negative()) x1.negate(); diff --git a/src/lib/utils/types.h b/src/lib/utils/types.h index 4427038a6..d1de9e2a6 100644 --- a/src/lib/utils/types.h +++ b/src/lib/utils/types.h @@ -24,6 +24,7 @@ using ::uint16_t; using ::uint32_t; using ::uint64_t; using ::int32_t; +using ::int64_t; using ::size_t; |