diff options
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.cpp | 122 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.h | 148 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/point_gfp.cpp | 171 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/point_gfp.h | 51 |
4 files changed, 279 insertions, 213 deletions
diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp new file mode 100644 index 000000000..2fa9f391e --- /dev/null +++ b/src/lib/math/ec_gfp/curve_gfp.cpp @@ -0,0 +1,122 @@ +/* +* Elliptic curves over GF(p) Montgomery Representation +* (C) 2014 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/curve_gfp.h> +#include <botan/internal/mp_core.h> + +namespace Botan { + +namespace { + +class CurveGFp_Montgomery : public CurveGFp_Repr + { + public: + CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) : + m_p(p), m_a(a), m_b(b), + m_p_words(m_p.sig_words()), + m_p_dash(monty_inverse(m_p.word_at(0))) + { + const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS); + + m_r2 = (r * r) % p; + m_a_r = (m_a * r) % p; + m_b_r = (m_b * r) % p; + } + + const BigInt& get_a() const override { return m_a; } + + const BigInt& get_b() const override { return m_b; } + + const BigInt& get_p() const override { return m_p; } + + const BigInt& get_a_rep() const override { return m_a_r; } + + const BigInt& get_b_rep() const override { return m_b_r; } + + void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override; + + void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override; + + 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: + BigInt m_p, m_a, m_b; + size_t m_p_words; // cache of m_p.sig_words() + + // Montgomery parameters + BigInt m_r2, m_a_r, m_b_r; + word m_p_dash; + }; + +void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const + { + const BigInt tx = x; + curve_mul(x, tx, m_r2, ws); + } + +void CurveGFp_Montgomery::from_curve_rep(BigInt& x, secure_vector<word>& ws) const + { + const BigInt tx = x; + curve_mul(x, tx, 1, ws); + } + +void CurveGFp_Montgomery::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; + } + + const size_t output_size = 2*m_p_words + 1; + ws.resize(2*(m_p_words+2)); + + z.grow_to(output_size); + z.clear(); + + bigint_monty_mul(z.mutable_data(), output_size, + x.data(), x.size(), x.sig_words(), + y.data(), y.size(), y.sig_words(), + m_p.data(), m_p_words, m_p_dash, + &ws[0]); + } + +void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, + secure_vector<word>& ws) const + { + if(x.is_zero()) + { + z = 0; + return; + } + + const size_t output_size = 2*m_p_words + 1; + + ws.resize(2*(m_p_words+2)); + + z.grow_to(output_size); + z.clear(); + + bigint_monty_sqr(z.mutable_data(), output_size, + x.data(), x.size(), x.sig_words(), + m_p.data(), m_p_words, m_p_dash, + &ws[0]); + } + +} + +std::shared_ptr<CurveGFp_Repr> +CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& 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 267d5f152..48aeb4343 100644 --- a/src/lib/math/ec_gfp/curve_gfp.h +++ b/src/lib/math/ec_gfp/curve_gfp.h @@ -2,7 +2,7 @@ * Elliptic curves over GF(p) * * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2010-2011,2012 Jack Lloyd +* 2010-2011,2012,2014 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -11,9 +11,40 @@ #define BOTAN_GFP_CURVE_H__ #include <botan/numthry.h> +#include <memory> namespace Botan { +class CurveGFp_Repr + { + public: + virtual ~CurveGFp_Repr() {} + + virtual const BigInt& get_p() const = 0; + virtual const BigInt& get_a() const = 0; + virtual const BigInt& get_b() const = 0; + + /* + * Returns to_curve_rep(get_a()) + */ + virtual const BigInt& get_a_rep() const = 0; + + /* + * Returns to_curve_rep(get_b()) + */ + virtual const BigInt& get_b_rep() const = 0; + + virtual void to_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0; + + virtual void from_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0; + + virtual void curve_mul(BigInt& z, const BigInt& x, const BigInt& y, + secure_vector<word>& ws) const = 0; + + virtual void curve_sqr(BigInt& z, const BigInt& x, + secure_vector<word>& ws) const = 0; + }; + /** * This class represents an elliptic curve over GF(p) */ @@ -33,17 +64,8 @@ class BOTAN_DLL CurveGFp * @param b second coefficient */ CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) : - m_p(p), - m_a(a), - m_b(b), - m_p_words(m_p.sig_words()), - m_p_dash(monty_inverse(m_p.word_at(0))) + m_repr(choose_repr(p, a, b)) { - const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS); - - m_r2 = (r * r) % p; - m_a_r = (a * r) % p; - m_b_r = (b * r) % p; } CurveGFp(const CurveGFp&) = default; @@ -53,93 +75,89 @@ class BOTAN_DLL CurveGFp /** * @return curve coefficient a */ - const BigInt& get_a() const { return m_a; } + const BigInt& get_a() const { return m_repr->get_a(); } /** * @return curve coefficient b */ - const BigInt& get_b() const { return m_b; } + const BigInt& get_b() const { return m_repr->get_b(); } /** * Get prime modulus of the field of the curve * @return prime modulus of the field of the curve */ - const BigInt& get_p() const { return m_p; } - - /** - * @return Montgomery parameter r^2 % p - */ - const BigInt& get_r2() const { return m_r2; } + const BigInt& get_p() const { return m_repr->get_p(); } - /** - * @return a * r mod p - */ - const BigInt& get_a_r() const { return m_a_r; } + const BigInt& get_a_rep() const { return m_repr->get_a_rep(); } - /** - * @return b * r mod p - */ - const BigInt& get_b_r() const { return m_b_r; } + const BigInt& get_b_rep() const { return m_repr->get_b_rep(); } - /** - * @return Montgomery parameter p-dash - */ - word get_p_dash() const { return m_p_dash; } + void to_rep(BigInt& x, secure_vector<word>& ws) const + { + m_repr->to_curve_rep(x, ws); + } - /** - * @return p.sig_words() - */ - size_t get_p_words() const { return m_p_words; } + void from_rep(BigInt& x, secure_vector<word>& ws) const + { + m_repr->from_curve_rep(x, ws); + } - /** - * swaps the states of *this and other, does not throw - * @param other curve to swap values with - */ - void swap(CurveGFp& other) + BigInt from_rep(const BigInt& x, secure_vector<word>& ws) const { - std::swap(m_p, other.m_p); + BigInt xt(x); + m_repr->from_curve_rep(xt, ws); + return xt; + } - std::swap(m_a, other.m_a); - std::swap(m_b, other.m_b); + void mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const + { + m_repr->curve_mul(z, x, y, ws); + } - std::swap(m_a_r, other.m_a_r); - std::swap(m_b_r, other.m_b_r); + BigInt mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const + { + BigInt z; + m_repr->curve_mul(z, x, y, ws); + return z; + } - std::swap(m_p_words, other.m_p_words); + void sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const + { + m_repr->curve_sqr(z, x, ws); + } - std::swap(m_r2, other.m_r2); - std::swap(m_p_dash, other.m_p_dash); + BigInt sqr(const BigInt& x, secure_vector<word>& ws) const + { + BigInt z; + m_repr->curve_sqr(z, x, ws); + return z; } - /** - * Equality operator - * @param other curve to compare with - * @return true iff this is the same curve as other - */ - bool operator==(const CurveGFp& other) const + void swap(CurveGFp& other) { - return (m_p == other.m_p && - m_a == other.m_a && - m_b == other.m_b); + std::swap(m_repr, other.m_repr); } private: - // Curve parameters - BigInt m_p, m_a, m_b; - - size_t m_p_words; // cache of m_p.sig_words() + static std::shared_ptr<CurveGFp_Repr> + choose_repr(const BigInt& p, const BigInt& a, const BigInt& b); - // Montgomery parameters - BigInt m_r2, m_a_r, m_b_r; - word m_p_dash; + std::shared_ptr<CurveGFp_Repr> m_repr; }; /** * Equality operator * @param lhs a curve * @param rhs a curve -* @return true iff lhs is not the same as rhs +* @return true iff lhs is the same as rhs */ +inline bool operator==(const CurveGFp& lhs, const CurveGFp& rhs) + { + return (lhs.get_p() == rhs.get_p()) && + (lhs.get_a() == rhs.get_a()) && + (lhs.get_b() == rhs.get_b()); + } + inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) { return !(lhs == rhs); diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp index cf3a204d6..3d244d0f0 100644 --- a/src/lib/math/ec_gfp/point_gfp.cpp +++ b/src/lib/math/ec_gfp/point_gfp.cpp @@ -2,85 +2,36 @@ * Point arithmetic on elliptic curves over GF(p) * * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2011,2012 Jack Lloyd +* 2008-2011,2012,2014 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/point_gfp.h> #include <botan/numthry.h> -#include <botan/reducer.h> -#include <botan/internal/mp_core.h> namespace Botan { PointGFp::PointGFp(const CurveGFp& curve) : - curve(curve), ws(2 * (curve.get_p_words() + 2)) + curve(curve), + coord_x(0), + coord_y(1), + coord_z(0) { - coord_x = 0; - coord_y = monty_mult(1, curve.get_r2()); - coord_z = 0; + curve.to_rep(coord_x, ws); + curve.to_rep(coord_y, ws); + curve.to_rep(coord_z, ws); } PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) : - curve(curve), ws(2 * (curve.get_p_words() + 2)) + curve(curve), + coord_x(x), + coord_y(y), + coord_z(1) { - coord_x = monty_mult(x, curve.get_r2()); - coord_y = monty_mult(y, curve.get_r2()); - coord_z = monty_mult(1, curve.get_r2()); - } - -// Montgomery multiplication -void PointGFp::monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const - { - //assert(&z != &x && &z != &y); - - if(x.is_zero() || y.is_zero()) - { - z = 0; - return; - } - - const BigInt& p = curve.get_p(); - const size_t p_size = curve.get_p_words(); - const word p_dash = curve.get_p_dash(); - - const size_t output_size = 2*p_size + 1; - - z.grow_to(output_size); - z.clear(); - - bigint_monty_mul(z.mutable_data(), output_size, - x.data(), x.size(), x.sig_words(), - y.data(), y.size(), y.sig_words(), - p.data(), p_size, p_dash, - &ws[0]); - } - -// Montgomery squaring -void PointGFp::monty_sqr(BigInt& z, const BigInt& x) const - { - //assert(&z != &x); - - if(x.is_zero()) - { - z = 0; - return; - } - - const BigInt& p = curve.get_p(); - const size_t p_size = curve.get_p_words(); - const word p_dash = curve.get_p_dash(); - - const size_t output_size = 2*p_size + 1; - - z.grow_to(output_size); - z.clear(); - - bigint_monty_sqr(z.mutable_data(), output_size, - x.data(), x.size(), x.sig_words(), - p.data(), p_size, p_dash, - &ws[0]); + curve.to_rep(coord_x, ws); + curve.to_rep(coord_y, ws); + curve.to_rep(coord_z, ws); } // Point addition @@ -109,13 +60,13 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) BigInt& H = ws_bn[6]; BigInt& r = ws_bn[7]; - monty_sqr(rhs_z2, rhs.coord_z); - monty_mult(U1, coord_x, rhs_z2); - monty_mult(S1, coord_y, monty_mult(rhs.coord_z, rhs_z2)); + curve_sqr(rhs_z2, rhs.coord_z); + curve_mult(U1, coord_x, rhs_z2); + curve_mult(S1, coord_y, curve_mult(rhs.coord_z, rhs_z2)); - monty_sqr(lhs_z2, coord_z); - monty_mult(U2, rhs.coord_x, lhs_z2); - monty_mult(S2, rhs.coord_y, monty_mult(coord_z, lhs_z2)); + curve_sqr(lhs_z2, coord_z); + curve_mult(U2, rhs.coord_x, lhs_z2); + curve_mult(S2, rhs.coord_y, curve_mult(coord_z, lhs_z2)); H = U2; H -= U1; @@ -139,13 +90,13 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) return; } - monty_sqr(U2, H); + curve_sqr(U2, H); - monty_mult(S2, U2, H); + curve_mult(S2, U2, H); - U2 = monty_mult(U1, U2); + U2 = curve_mult(U1, U2); - monty_sqr(coord_x, r); + curve_sqr(coord_x, r); coord_x -= S2; coord_x -= (U2 << 1); while(coord_x.is_negative()) @@ -155,12 +106,12 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn) if(U2.is_negative()) U2 += p; - monty_mult(coord_y, r, U2); - coord_y -= monty_mult(S1, S2); + curve_mult(coord_y, r, U2); + coord_y -= curve_mult(S1, S2); if(coord_y.is_negative()) coord_y += p; - monty_mult(coord_z, monty_mult(coord_z, rhs.coord_z), H); + curve_mult(coord_z, curve_mult(coord_z, rhs.coord_z), H); } // *this *= 2 @@ -186,28 +137,28 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn) BigInt& y = ws_bn[7]; BigInt& z = ws_bn[8]; - monty_sqr(y_2, coord_y); + curve_sqr(y_2, coord_y); - monty_mult(S, coord_x, y_2); + curve_mult(S, coord_x, y_2); S <<= 2; // * 4 while(S >= p) S -= p; - monty_sqr(z4, monty_sqr(coord_z)); - monty_mult(a_z4, curve.get_a_r(), z4); + curve_sqr(z4, curve_sqr(coord_z)); + curve_mult(a_z4, curve.get_a_rep(), z4); - M = monty_sqr(coord_x); + M = curve_sqr(coord_x); M *= 3; M += a_z4; while(M >= p) M -= p; - monty_sqr(x, M); + curve_sqr(x, M); x -= (S << 1); while(x.is_negative()) x += p; - monty_sqr(U, y_2); + curve_sqr(U, y_2); U <<= 3; while(U >= p) U -= p; @@ -216,12 +167,12 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn) while(S.is_negative()) S += p; - monty_mult(y, M, S); + curve_mult(y, M, S); y -= U; if(y.is_negative()) y += p; - monty_mult(z, coord_y, coord_z); + curve_mult(z, coord_y, coord_z); z <<= 1; if(z >= p) z -= p; @@ -388,6 +339,8 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point) if(scalar.is_negative()) H.negate(); + //BOTAN_ASSERT(H.on_the_curve(), "Fault detected"); + return H; #endif } @@ -397,13 +350,11 @@ BigInt PointGFp::get_affine_x() const if(is_zero()) throw Illegal_Transformation("Cannot convert zero point to affine"); - const BigInt& r2 = curve.get_r2(); - - BigInt z2 = monty_sqr(coord_z); + BigInt z2 = curve_sqr(coord_z); + curve.from_rep(z2, ws); z2 = inverse_mod(z2, curve.get_p()); - z2 = monty_mult(z2, r2); - return monty_mult(coord_x, z2); + return curve_mult(z2, coord_x); } BigInt PointGFp::get_affine_y() const @@ -411,12 +362,11 @@ BigInt PointGFp::get_affine_y() const if(is_zero()) throw Illegal_Transformation("Cannot convert zero point to affine"); - const BigInt& r2 = curve.get_r2(); - - BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z)); + BigInt z3 = curve_mult(coord_z, curve_sqr(coord_z)); z3 = inverse_mod(z3, curve.get_p()); - z3 = monty_mult(z3, r2); - return monty_mult(coord_y, z3); + curve.to_rep(z3, ws); + + return curve_mult(z3, coord_y); } bool PointGFp::on_the_curve() const @@ -427,32 +377,25 @@ bool PointGFp::on_the_curve() const If somehow the state is corrupted, which suggests a fault attack (or internal computational error), then return false. */ - if(is_zero()) return true; - BigInt y2 = monty_mult(monty_sqr(coord_y), 1); - BigInt x3 = monty_mult(coord_x, monty_sqr(coord_x)); - - BigInt ax = monty_mult(coord_x, curve.get_a_r()); - - const BigInt& b_r = curve.get_b_r(); - - BigInt z2 = monty_sqr(coord_z); + const BigInt y2 = curve.from_rep(curve_sqr(coord_y), ws); + const BigInt x3 = curve_mult(coord_x, curve_sqr(coord_x)); + const BigInt ax = curve_mult(coord_x, curve.get_a_rep()); + const BigInt z2 = curve_sqr(coord_z); if(coord_z == z2) // Is z equal to 1 (in Montgomery form)? { - if(y2 != monty_mult(x3 + ax + b_r, 1)) + if(y2 != curve.from_rep(x3 + ax + curve.get_b_rep(), ws)) return false; } - BigInt z3 = monty_mult(coord_z, z2); - - BigInt ax_z4 = monty_mult(ax, monty_sqr(z2)); - - BigInt b_z6 = monty_mult(b_r, monty_sqr(z3)); + const BigInt z3 = curve_mult(coord_z, z2); + const BigInt ax_z4 = curve_mult(ax, curve_sqr(z2)); + const BigInt b_z6 = curve_mult(curve.get_b_rep(), curve_sqr(z3)); - if(y2 != monty_mult(x3 + ax_z4 + b_z6, 1)) + if(y2 != curve.from_rep(x3 + ax_z4 + b_z6, ws)) return false; return true; @@ -525,7 +468,7 @@ secure_vector<byte> EC2OSP(const PointGFp& point, byte format) return result; } else - throw Invalid_Argument("illegal point encoding format specification"); + throw Invalid_Argument("EC2OSP illegal point encoding"); } namespace { @@ -544,7 +487,7 @@ BigInt decompress_point(bool yMod2, BigInt z = ressol(g, curve.get_p()); if(z < 0) - throw Illegal_Point("error during decompression"); + throw Illegal_Point("error during EC point decompression"); if(z.get_bit(0) != yMod2) z = curve.get_p() - z; diff --git a/src/lib/math/ec_gfp/point_gfp.h b/src/lib/math/ec_gfp/point_gfp.h index 017f66e1c..c91b0513f 100644 --- a/src/lib/math/ec_gfp/point_gfp.h +++ b/src/lib/math/ec_gfp/point_gfp.h @@ -2,7 +2,7 @@ * Point arithmetic on elliptic curves over GF(p) * * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2011 Jack Lloyd +* 2008-2011,2014 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -190,46 +190,29 @@ class BOTAN_DLL PointGFp bool operator==(const PointGFp& other) const; private: - /** - * Montgomery multiplication/reduction - * @param x first multiplicand - * @param y second multiplicand - * @param workspace temp space - */ - BigInt monty_mult(const BigInt& x, const BigInt& y) const + BigInt curve_mult(const BigInt& x, const BigInt& y) const { - BigInt result; - monty_mult(result, x, y); - return result; + BigInt z; + curve.mul(z, x, y, ws); + return z; } - /** - * Montgomery multiplication/reduction - * @warning z cannot alias x or y - * @param z output - * @param x first multiplicand - * @param y second multiplicand - */ - void monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const; + void curve_mult(BigInt& z, const BigInt& x, const BigInt& y) const + { + curve.mul(z, x, y, ws); + } - /** - * Montgomery squaring/reduction - * @param x multiplicand - */ - BigInt monty_sqr(const BigInt& x) const + BigInt curve_sqr(const BigInt& x) const { - BigInt result; - monty_sqr(result, x); - return result; + BigInt z; + curve.sqr(z, x, ws); + return z; } - /** - * Montgomery squaring/reduction - * @warning z cannot alias x - * @param z output - * @param x multiplicand - */ - void monty_sqr(BigInt& z, const BigInt& x) const; + void curve_sqr(BigInt& z, const BigInt& x) const + { + curve.sqr(z, x, ws); + } /** * Point addition |