diff options
Diffstat (limited to 'src/lib/math/ec_gfp')
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.cpp | 172 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.h | 14 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_nistp.cpp | 137 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_nistp.h | 152 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/info.txt | 9 |
5 files changed, 229 insertions, 255 deletions
diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp index 64d45572d..96fe873af 100644 --- a/src/lib/math/ec_gfp/curve_gfp.cpp +++ b/src/lib/math/ec_gfp/curve_gfp.cpp @@ -1,12 +1,12 @@ /* * Elliptic curves over GF(p) Montgomery Representation -* (C) 2014 Jack Lloyd +* (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ #include <botan/curve_gfp.h> -#include <botan/internal/curve_nistp.h> +#include <botan/curve_nistp.h> #include <botan/internal/mp_core.h> #include <botan/internal/mp_asmi.h> @@ -115,54 +115,170 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, ws.data()); } -} +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) + { + } + + const BigInt& get_a() const override { return m_a; } + + const BigInt& get_b() const override { return m_b; } + + size_t get_p_words() const override { return m_p_words; } + + const BigInt& get_a_rep() const override { return m_a; } + + const BigInt& get_b_rep() const override { return m_b; } + + void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override + { redc(x, ws); } + + void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override + { redc(x, ws); } + + void curve_mul(BigInt& z, const BigInt& x, const BigInt& y, + secure_vector<word>& ws) const override; + + 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_a, m_b; + size_t m_p_words; // cache of m_p.sig_words() + }; -// Default implementation -void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t bound) const +void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, + secure_vector<word>& ws) const { - const BigInt& p = get_p(); - const word* prime = p.data(); + if(x.is_zero() || y.is_zero()) + { + z = 0; + return; + } + const size_t p_words = get_p_words(); + const size_t output_size = 2*p_words + 1; + ws.resize(2*(p_words+2)); - while(x.is_negative()) - x += p; + z.grow_to(output_size); + z.clear(); - x.grow_to(p_words + 1); + bigint_mul(z.mutable_data(), output_size, ws.data(), + x.data(), x.size(), x.sig_words(), + y.data(), y.size(), y.sig_words()); - if(ws.size() < p_words + 1) - ws.resize(p_words + 1); + this->redc(z, ws); + } - for(size_t i = 0; bound == 0 || i < bound; ++i) +void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x, + secure_vector<word>& ws) const + { + if(x.is_zero()) { - const word* xd = x.data(); - word borrow = 0; + z = 0; + return; + } + + const size_t p_words = get_p_words(); + const size_t output_size = 2*p_words + 1; - 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); + ws.resize(2*(p_words+2)); - if(borrow) - break; + z.grow_to(output_size); + z.clear(); - x.swap_reg(ws); - } + bigint_sqr(z.mutable_data(), output_size, ws.data(), + x.data(), x.size(), x.sig_words()); + + this->redc(z, ws); } +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) + +/** +* 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) {} + const BigInt& get_p() const override { return prime_p192(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); } + }; + +/** +* 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) {} + const BigInt& get_p() const override { return prime_p224(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); } + }; + +/** +* 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) {} + const BigInt& get_p() const override { return prime_p256(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); } + }; + +/** +* 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) {} + const BigInt& get_p() const override { return prime_p384(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); } + }; + +#endif + +/** +* The NIST P-521 curve +*/ +class CurveGFp_P521 : public CurveGFp_NIST + { + public: + CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} + const BigInt& get_p() const override { return prime_p521(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); } + }; + +} + 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()) +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) + if(p == prime_p192()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); - if(p == CurveGFp_P224::prime()) + if(p == prime_p224()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); - if(p == CurveGFp_P256::prime()) + if(p == prime_p256()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); - if(p == CurveGFp_P384::prime()) + if(p == prime_p384()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); #endif - if(p == CurveGFp_P521::prime()) + if(p == prime_p521()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b)); diff --git a/src/lib/math/ec_gfp/curve_gfp.h b/src/lib/math/ec_gfp/curve_gfp.h index 68fe93274..dde9f633e 100644 --- a/src/lib/math/ec_gfp/curve_gfp.h +++ b/src/lib/math/ec_gfp/curve_gfp.h @@ -45,10 +45,6 @@ class CurveGFp_Repr virtual void curve_sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const = 0; - - virtual void normalize(BigInt& x, - secure_vector<word>& ws, - size_t bound) const; }; /** @@ -141,16 +137,6 @@ class BOTAN_DLL CurveGFp return z; } - /** - * Adjust x to be in [0,p) - * @param bound if greater than zero, assume that no more than bound - * additions or subtractions are required to move x into range. - */ - void normalize(BigInt& x, secure_vector<word>& ws, size_t bound = 0) const - { - m_repr->normalize(x, ws, bound); - } - void swap(CurveGFp& other) { std::swap(m_repr, other.m_repr); diff --git a/src/lib/math/ec_gfp/curve_nistp.cpp b/src/lib/math/ec_gfp/curve_nistp.cpp index 002cf2d47..bbc11ff21 100644 --- a/src/lib/math/ec_gfp/curve_nistp.cpp +++ b/src/lib/math/ec_gfp/curve_nistp.cpp @@ -1,63 +1,51 @@ /* -* NIST curve reduction +* NIST prime reductions * (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ -#include <botan/internal/curve_nistp.h> +#include <botan/curve_nistp.h> #include <botan/internal/mp_core.h> +#include <botan/internal/mp_asmi.h> namespace Botan { -void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, - secure_vector<word>& ws) const - { - if(x.is_zero() || y.is_zero()) - { - z = 0; - return; - } +namespace { - const size_t p_words = get_p_words(); - const size_t output_size = 2*p_words + 1; - ws.resize(2*(p_words+2)); +void normalize(const BigInt& p, BigInt& x, secure_vector<word>& ws, size_t bound) + { + const word* prime = p.data(); + const size_t p_words = p.sig_words(); - z.grow_to(output_size); - z.clear(); + while(x.is_negative()) + x += p; - bigint_mul(z.mutable_data(), output_size, ws.data(), - x.data(), x.size(), x.sig_words(), - y.data(), y.size(), y.sig_words()); + // TODO: provide a high level function for this compare-and-sub operation + x.grow_to(p_words + 1); - this->redc(z, ws); - } + if(ws.size() < p_words + 1) + ws.resize(p_words + 1); -void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x, - secure_vector<word>& ws) const - { - if(x.is_zero()) + for(size_t i = 0; bound == 0 || i < bound; ++i) { - z = 0; - return; - } - - const size_t p_words = get_p_words(); - const size_t output_size = 2*p_words + 1; - - ws.resize(2*(p_words+2)); + const word* xd = x.data(); + word borrow = 0; - z.grow_to(output_size); - z.clear(); + 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); - bigint_sqr(z.mutable_data(), output_size, ws.data(), - x.data(), x.size(), x.sig_words()); + if(borrow) + break; - this->redc(z, ws); + x.swap_reg(ws); + } } -//static -const BigInt& CurveGFp_P521::prime() +} + +const BigInt& prime_p521() { static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"); @@ -65,12 +53,11 @@ const BigInt& CurveGFp_P521::prime() return p521; } -void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p521(BigInt& x, secure_vector<word>& ws) { - const size_t p_words = get_p_words(); - - const size_t shift_words = 521 / MP_WORD_BITS, - shift_bits = 521 % MP_WORD_BITS; + const size_t p_full_words = 521 / MP_WORD_BITS; + const size_t p_top_bits = 521 % MP_WORD_BITS; + const size_t p_words = p_full_words + 1; const size_t x_sw = x.sig_words(); @@ -81,16 +68,16 @@ void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const ws.resize(p_words + 1); clear_mem(ws.data(), ws.size()); - bigint_shr2(ws.data(), x.data(), x_sw, shift_words, shift_bits); + bigint_shr2(ws.data(), x.data(), x_sw, p_full_words, p_top_bits); x.mask_bits(521); bigint_add3(x.mutable_data(), x.data(), p_words, ws.data(), p_words); - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p521(), x, ws, 1); } -#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) namespace { @@ -130,14 +117,13 @@ inline void set_u32bit(BigInt& x, size_t i, T v_in) } -//static -const BigInt& CurveGFp_P192::prime() +const BigInt& prime_p192() { static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"); return p192; } -void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p192(BigInt& x, secure_vector<word>& ws) { const u32bit X6 = get_u32bit(x, 6); const u32bit X7 = get_u32bit(x, 7); @@ -192,17 +178,16 @@ void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const // No underflow possible - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p192(), x, ws, 3); } -//static -const BigInt& CurveGFp_P224::prime() +const BigInt& prime_p224() { static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"); return p224; } -void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p224(BigInt& x, secure_vector<word>& ws) { const u32bit X7 = get_u32bit(x, 7); const u32bit X8 = get_u32bit(x, 8); @@ -271,17 +256,16 @@ void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p224(), x, ws, 3); } -//static -const BigInt& CurveGFp_P256::prime() +const BigInt& prime_p256() { static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"); return p256; } -void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p256(BigInt& x, secure_vector<word>& ws) { const u32bit X8 = get_u32bit(x, 8); const u32bit X9 = get_u32bit(x, 9); @@ -396,34 +380,35 @@ void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); + #if 0 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() + 2*CurveGFp_P256::prime(), + 3*CurveGFp_P256::prime(), + 4*CurveGFp_P256::prime(), + 5*CurveGFp_P256::prime(), + 6*CurveGFp_P256::prime(), + 7*CurveGFp_P256::prime(), + 8*CurveGFp_P256::prime(), + 9*CurveGFp_P256::prime(), + 10*CurveGFp_P256::prime() }; x -= P256_mults[S - 2]; } + #endif - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p256(), x, ws, 10); } -//static -const BigInt& CurveGFp_P384::prime() +const BigInt& prime_p384() { static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"); return p384; } -void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p384(BigInt& x, secure_vector<word>& ws) { const u32bit X12 = get_u32bit(x, 12); const u32bit X13 = get_u32bit(x, 13); @@ -569,20 +554,22 @@ void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); set_u32bit(x, 12, S); + #if 0 if(S >= 2) { BOTAN_ASSERT(S <= 4, "Expected overflow"); static const BigInt P384_mults[3] = { - 2*get_p(), - 3*get_p(), - 4*get_p() + 2*CurveGFp_P384::prime(), + 3*CurveGFp_P384::prime(), + 4*CurveGFp_P384::prime() }; x -= P384_mults[S - 2]; } + #endif - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p384(), x, ws, 4); } #endif diff --git a/src/lib/math/ec_gfp/curve_nistp.h b/src/lib/math/ec_gfp/curve_nistp.h index 0bf707f58..e7af69964 100644 --- a/src/lib/math/ec_gfp/curve_nistp.h +++ b/src/lib/math/ec_gfp/curve_nistp.h @@ -1,152 +1,46 @@ /* -* NIST elliptic curves over GF(p) -* (C) 2014 Jack Lloyd +* Arithmetic operations specialized for NIST ECC primes +* (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ -#ifndef BOTAN_GFP_CURVE_NIST_H__ -#define BOTAN_GFP_CURVE_NIST_H__ +#ifndef BOTAN_NIST_PRIMES_H__ +#define BOTAN_NIST_PRIMES_H__ -#include <botan/curve_gfp.h> -#include <memory> +#include <botan/bigint.h> namespace Botan { -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) - { - } - - size_t get_p_words() const override { return m_p_words; } - - const BigInt& get_a() const override { return m_a; } - - const BigInt& get_b() const override { return m_b; } - - const BigInt& get_a_rep() const override { return m_a; } - - const BigInt& get_b_rep() const override { return m_b; } - - void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override - { redc(x, ws); } - - void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override - { redc(x, ws); } - - void curve_mul(BigInt& z, const BigInt& x, const BigInt& y, - secure_vector<word>& ws) const override; - - 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; - - virtual size_t max_redc_subtractions() const = 0; - - // Curve parameters - BigInt m_a, m_b; - 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 +* NIST Prime reduction functions. +* +* Reduces the value in place +* +* ws is a workspace function which is used as a temporary, +* and will be resized as needed. */ -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; +BOTAN_DLL const BigInt& prime_p521(); +BOTAN_DLL void redc_p521(BigInt& x, secure_vector<word>& ws); - size_t max_redc_subtractions() const override { return 10; } - }; +#if (BOTAN_MP_WORD_BITS == 32) || (BOTAN_MP_WORD_BITS == 64) -/** -* 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) {} +#define BOTAN_HAS_NIST_PRIME_REDUCERS_W32 - static const BigInt& prime(); +BOTAN_DLL const BigInt& prime_p384(); +BOTAN_DLL void redc_p384(BigInt& x, secure_vector<word>& ws); - const BigInt& get_p() const override { return CurveGFp_P384::prime(); } +BOTAN_DLL const BigInt& prime_p256(); +BOTAN_DLL void redc_p256(BigInt& x, secure_vector<word>& ws); - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; +BOTAN_DLL const BigInt& prime_p224(); +BOTAN_DLL void redc_p224(BigInt& x, secure_vector<word>& ws); - size_t max_redc_subtractions() const override { return 4; } - }; +BOTAN_DLL const BigInt& prime_p192(); +BOTAN_DLL void redc_p192(BigInt& x, secure_vector<word>& ws); #endif -/** -* The NIST P-521 curve -*/ -class CurveGFp_P521 : public CurveGFp_NIST - { - public: - CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} - - static const BigInt& prime(); - - const BigInt& get_p() const override { return CurveGFp_P521::prime(); } - - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; - - size_t max_redc_subtractions() const override { return 1; } - }; - } #endif diff --git a/src/lib/math/ec_gfp/info.txt b/src/lib/math/ec_gfp/info.txt index 9af40c752..060551562 100644 --- a/src/lib/math/ec_gfp/info.txt +++ b/src/lib/math/ec_gfp/info.txt @@ -2,15 +2,6 @@ define EC_CURVE_GFP 20131128 load_on auto -<header:public> -curve_gfp.h -point_gfp.h -</header:public> - -<header:internal> -curve_nistp.h -</header:internal> - <requires> numbertheory </requires> |