diff options
Diffstat (limited to 'src/math')
| -rw-r--r-- | src/math/gfpmath/curve_gfp.cpp | 58 | ||||
| -rw-r--r-- | src/math/gfpmath/curve_gfp.h | 133 | ||||
| -rw-r--r-- | src/math/gfpmath/gfp_element.cpp | 559 | ||||
| -rw-r--r-- | src/math/gfpmath/gfp_element.h | 230 | ||||
| -rw-r--r-- | src/math/gfpmath/gfp_modulus.h | 131 | ||||
| -rw-r--r-- | src/math/gfpmath/info.txt | 19 | ||||
| -rw-r--r-- | src/math/gfpmath/point_gfp.cpp | 750 | ||||
| -rw-r--r-- | src/math/gfpmath/point_gfp.h | 268 | ||||
| -rw-r--r-- | src/math/numbertheory/curve_gfp.h | 96 | ||||
| -rw-r--r-- | src/math/numbertheory/info.txt | 3 | ||||
| -rw-r--r-- | src/math/numbertheory/numthry.cpp | 100 | ||||
| -rw-r--r-- | src/math/numbertheory/numthry.h | 16 | ||||
| -rw-r--r-- | src/math/numbertheory/point_gfp.cpp | 423 | ||||
| -rw-r--r-- | src/math/numbertheory/point_gfp.h | 201 | ||||
| -rw-r--r-- | src/math/numbertheory/reducer.cpp | 19 | ||||
| -rw-r--r-- | src/math/numbertheory/reducer.h | 32 |
16 files changed, 806 insertions, 2232 deletions
diff --git a/src/math/gfpmath/curve_gfp.cpp b/src/math/gfpmath/curve_gfp.cpp deleted file mode 100644 index e6e69ab0f..000000000 --- a/src/math/gfpmath/curve_gfp.cpp +++ /dev/null @@ -1,58 +0,0 @@ -/* -* Elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/curve_gfp.h> -#include <botan/bigint.h> -#include <assert.h> -#include <ostream> - -namespace Botan { - -CurveGFp::CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p) : - modulus(p), mA(a), mB(b), - mres_a(mA), mres_b(mB), mres_one(p, 1) - { - if(p != mA.get_p() || p != mB.get_p()) - throw Invalid_Argument("could not construct curve: moduli of arguments differ"); - - mres_a.turn_on_sp_red_mul(); - mres_a.get_mres(); - - mres_b.turn_on_sp_red_mul(); - mres_b.get_mres(); - - mres_one.turn_on_sp_red_mul(); - mres_one.get_mres(); - } - -// swaps the states of *this and other, does not throw -void CurveGFp::swap(CurveGFp& other) - { - std::swap(mA, other.mA); - std::swap(mB, other.mB); - std::swap(modulus, other.modulus); - std::swap(mres_a, other.mres_a); - std::swap(mres_b, other.mres_b); - std::swap(mres_one, other.mres_one); - } - -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()); - } - -std::ostream& operator<<(std::ostream& output, const CurveGFp& elem) - { - return output << "y^2 = x^3 + (" << elem.get_a() << ")x + (" << elem.get_b() << ")"; - } - -} diff --git a/src/math/gfpmath/curve_gfp.h b/src/math/gfpmath/curve_gfp.h deleted file mode 100644 index d2ca437fb..000000000 --- a/src/math/gfpmath/curve_gfp.h +++ /dev/null @@ -1,133 +0,0 @@ -/* -* Elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_CURVE_H__ -#define BOTAN_GFP_CURVE_H__ - -#include <botan/bigint.h> -#include <botan/gfp_element.h> -#include <iosfwd> - -namespace Botan { - -/** -* This class represents an elliptic curve over GF(p) -*/ -class BOTAN_DLL CurveGFp - { - public: - - /** - * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) - * @param a first coefficient - * @param b second coefficient - * @param p prime number of the field - */ - CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p); - - // CurveGFp(const CurveGFp& other) = default; - // CurveGFp& operator=(const CurveGFp& other) = default; - - // getters - - /** - * Get coefficient a - * @result coefficient a - */ - const GFpElement& get_a() const { return mA; } - - /** - * Get coefficient b - * @result coefficient b - */ - const GFpElement& get_b() const { return mB; } - - /** - * Get the GFpElement coefficient a transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient a, transformed to its m-residue - */ - const GFpElement& get_mres_a() const { return mres_a; } - - /** - * Get the GFpElement coefficient b transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient b, transformed to its m-residue - */ - const GFpElement& get_mres_b() const { return mres_b; } - - /** - * Get the GFpElement 1 transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the GFpElement 1, transformed to its m-residue - */ - const GFpElement& get_mres_one() { return mres_one; } - - /** - * Get prime modulus of the field of the curve - * @result prime modulus of the field of the curve - */ - const BigInt& get_p() const { return modulus.get_p(); } - - /** - * swaps the states of *this and other, does not throw - * @param other The curve to swap values with - */ - void swap(CurveGFp& other); - - private: - GFpModulus modulus; - GFpElement mA; - GFpElement mB; - GFpElement mres_a, mres_b, mres_one; - }; - -// relational operators -bool operator==(const CurveGFp& lhs, const CurveGFp& rhs); - -inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) - { - return !(lhs == rhs); - } - -// io operators -std::ostream& operator<<(std::ostream& output, const CurveGFp& elem); - -// swaps the states of curve1 and curve2, does not throw! -// cf. Meyers, Item 25 -inline -void swap(CurveGFp& curve1, CurveGFp& curve2) - { - curve1.swap(curve2); - } - -} // namespace Botan - - -namespace std { - -// swaps the states of curve1 and curve2, does not throw! -// cf. Meyers, Item 25 -template<> inline -void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, - Botan::CurveGFp& curve2) - { - curve1.swap(curve2); - } - -} // namespace std - -#endif diff --git a/src/math/gfpmath/gfp_element.cpp b/src/math/gfpmath/gfp_element.cpp deleted file mode 100644 index 3bb4d0002..000000000 --- a/src/math/gfpmath/gfp_element.cpp +++ /dev/null @@ -1,559 +0,0 @@ -/* -* Arithmetic for prime fields GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/gfp_element.h> -#include <botan/numthry.h> -#include <botan/internal/def_powm.h> -#include <botan/internal/mp_asm.h> -#include <botan/internal/mp_asmi.h> -#include <ostream> -#include <assert.h> - -namespace Botan { - -namespace { - -void inner_montg_mult_sos(word result[], - const word* a_bar, const word* b_bar, - const word* n, const word* n_dash, u32bit s) - { - SecureVector<word> t; - t.grow_to(2*s+1); - - // t = a_bar * b_bar - for (u32bit i=0; i<s; i++) - { - word C = 0; - word S = 0; - for (u32bit j=0; j<s; j++) - { - // we use: - // word word_madd3(word a, word b, word c, word d, word* carry) - // returns a * b + c + d and resets the carry (not using it as input) - - S = word_madd3(a_bar[j], b_bar[i], t[i+j], &C); - t[i+j] = S; - } - t[i+s] = C; - } - - // ??? - for (u32bit i=0; i<s; i++) - { - // word word_madd2(word a, word b, word c, word* carry) - // returns a * b + c, resets the carry - - word C = 0; - word zero = 0; - word m = word_madd2(t[i], n_dash[0], &zero); - - for (u32bit j=0; j<s; j++) - { - word S = word_madd3(m, n[j], t[i+j], &C); - t[i+j] = S; - } - - //// mp_mulop.cpp: - ////word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y) - u32bit cnt = 0; - while (C > 0) - { - // we need not worry here about C > 1, because the other operand is zero - - word tmp = t[i+s+cnt] + C; - C = (tmp < t[i+s+cnt]); - t[i+s+cnt] = tmp; - cnt++; - } - } - - // u = t - SecureVector<word> u; - u.grow_to(s+1); - for (u32bit j=0; j<s+1; j++) - { - u[j] = t[j+s]; - } - - // t = u - n - word B = 0; - word D = 0; - for (u32bit i=0; i<s; i++) - { - D = word_sub(u[i], n[i], &B); - t[i] = D; - } - D = word_sub(u[s], 0, &B); - t[s] = D; - - // if t >= 0 (B == 0 -> no borrow), return t - if(B == 0) - { - for (u32bit i=0; i<s; i++) - { - result[i] = t[i]; - } - } - else // else return u - { - for (u32bit i=0; i<s; i++) - { - result[i] = u[i]; - } - } - } - -void montg_mult(BigInt& result, BigInt& a_bar, BigInt& b_bar, const BigInt& m, const BigInt& m_dash, const BigInt) - { - if(m.is_zero() || m_dash.is_zero()) - throw Invalid_Argument("montg_mult(): neither modulus nor m_dash may be zero (and one of them was)"); - - if(a_bar.is_zero() || b_bar.is_zero()) - result = 0; - - u32bit s = m.sig_words(); - a_bar.grow_to(s); - b_bar.grow_to(s); - result.grow_to(s); - - inner_montg_mult_sos(result.get_reg(), a_bar.data(), b_bar.data(), - m.data(), m_dash.data(), s); - } - -/** -* Calculates R=b^n (here b=2) with R>m (and R beeing as small as -* possible) for an odd modulus m. No check for parity is performed! -*/ -BigInt montgm_calc_r_oddmod(const BigInt& prime) - { - u32bit n = prime.sig_words(); - BigInt result(1); - result <<= n*BOTAN_MP_WORD_BITS; - return result; - } - -/** -*calculates m' with r*r^-1 - m*m' = 1 -* where r^-1 is the multiplicative inverse of r to the modulus m -*/ -BigInt montgm_calc_m_dash(const BigInt& r, const BigInt& m, const BigInt& r_inv) - { - BigInt result = ((r * r_inv) - BigInt(1))/m; - return result; - } - -BigInt montg_trf_to_mres(const BigInt& ord_res, const BigInt& r, const BigInt& m) - { - BigInt result(ord_res); - result *= r; - result %= m; - return result; - } - -BigInt montg_trf_to_ordres(const BigInt& m_res, const BigInt& m, const BigInt& r_inv) - { - BigInt result(m_res); - result *= r_inv; - result %= m; - return result; - } - -} - -GFpElement::GFpElement(const BigInt& p, const BigInt& value, bool use_montgomery) - : modulus(p), m_value(value %p), m_use_montgm(use_montgomery), m_is_trf(false) - { - if(m_use_montgm) - ensure_montgm_precomp(); - } - -void GFpElement::turn_on_sp_red_mul() - { - ensure_montgm_precomp(); - m_use_montgm = true; - } - -void GFpElement::turn_off_sp_red_mul() - { - if(m_is_trf) - { - trf_to_ordres(); - // will happen soon anyway, so we can do it here already - // (this is not lazy but way more secure concerning our internal logic here) - } - m_use_montgm = false; - } - -void GFpElement::ensure_montgm_precomp() - { - if((!modulus.get_r().is_zero()) && (!modulus.get_r_inv().is_zero()) && (!modulus.get_p_dash().is_zero())) - { - // values are already set, nothing more to do - } - else - { - BigInt tmp_r(montgm_calc_r_oddmod(modulus.get_p())); - - BigInt tmp_r_inv(inverse_mod(tmp_r, modulus.get_p())); - - BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, modulus.get_p(), tmp_r_inv)); - - modulus.reset_values(tmp_p_dash, tmp_r, tmp_r_inv); - } - - } - -void GFpElement::trf_to_mres() const - { - if(!m_use_montgm) - { - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - assert(m_is_trf == false); - assert(!modulus.get_r_inv().is_zero()); - assert(!modulus.get_p_dash().is_zero()); - m_value = montg_trf_to_mres(m_value, modulus.get_r(), modulus.get_p()); - m_is_trf = true; - } - -void GFpElement::trf_to_ordres() const - { - assert(m_is_trf == true); - m_value = montg_trf_to_ordres(m_value, modulus.get_p(), modulus.get_r_inv()); - m_is_trf = false; - } - -bool GFpElement::align_operands_res(const GFpElement& lhs, const GFpElement& rhs) //static - { - assert(lhs.modulus.get_p() == rhs.modulus.get_p()); - if(lhs.m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.modulus.get_p_dash() == lhs.modulus.get_p_dash()); - assert(rhs.modulus.get_r() == lhs.modulus.get_r()); - assert(rhs.modulus.get_r_inv() == lhs.modulus.get_r_inv()); - if(!lhs.m_is_trf && !rhs.m_is_trf) - { - return false; - } - else if(lhs.m_is_trf && rhs.m_is_trf) - { - return true; - } - else // one is transf., the other not - { - if(!lhs.m_is_trf) - { - lhs.trf_to_mres(); - assert(rhs.m_is_trf==true); - return true; - } - assert(rhs.m_is_trf==false); - assert(lhs.m_is_trf==true); - rhs.trf_to_mres(); // the only possibility left... - return true; - } - } - else // at least one of them does not use mm - // (so it is impossible that both use it) - { - if(lhs.m_is_trf) - { - lhs.trf_to_ordres(); - assert(rhs.m_is_trf == false); - return false; - } - if(rhs.m_is_trf) - { - rhs.trf_to_ordres(); - assert(lhs.m_is_trf == false); - return false; - } - return false; - } - assert(false); - } - -bool GFpElement::is_trf_to_mres() const - { - return m_is_trf; - } - -const BigInt& GFpElement::get_p() const - { - return (modulus.get_p()); - } - -const BigInt& GFpElement::get_value() const - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - return m_value; - } - -const BigInt& GFpElement::get_mres() const - { - if(!m_use_montgm) - { - // does the following exception really make sense? - // wouldn't it be better to simply turn on montg.mult. when - // this explicit request is made? - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - if(!m_is_trf) - { - trf_to_mres(); - } - - return m_value; - } - -GFpElement& GFpElement::operator+=(const GFpElement& rhs) - { - GFpElement::align_operands_res(*this, rhs); - - BigInt workspace = m_value; - workspace += rhs.m_value; - if(workspace >= modulus.get_p()) - workspace -= modulus.get_p(); - - m_value = workspace; - assert(m_value < modulus.get_p()); - assert(m_value >= 0); - - return *this; - } - -GFpElement& GFpElement::operator-=(const GFpElement& rhs) - { - GFpElement::align_operands_res(*this, rhs); - - BigInt workspace = m_value; - - workspace -= rhs.m_value; - - if(workspace.is_negative()) - workspace += modulus.get_p(); - - m_value = workspace; - assert(m_value < modulus.get_p()); - assert(m_value >= 0); - return *this; - } - -GFpElement& GFpElement::operator*= (u32bit rhs) - { - BigInt workspace = m_value; - workspace *= rhs; - workspace %= modulus.get_p(); - m_value = workspace; - return *this; - } - -GFpElement& GFpElement::operator*=(const GFpElement& rhs) - { - assert(rhs.modulus.get_p() == modulus.get_p()); - // here, we do not use align_operands_res() for one simple reason: - // we want to enforce the transformation to an m-residue, otherwise it would - // never happen - if(m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.modulus.get_p() == modulus.get_p()); // is montgm. mult is on, then precomps must be there - assert(rhs.modulus.get_p_dash() == modulus.get_p_dash()); - assert(rhs.modulus.get_r() == modulus.get_r()); - if(!m_is_trf) - { - trf_to_mres(); - } - if(!rhs.m_is_trf) - { - rhs.trf_to_mres(); - } - BigInt workspace = m_value; - montg_mult(m_value, workspace, rhs.m_value, modulus.get_p(), modulus.get_p_dash(), modulus.get_r()); - } - else // ordinary multiplication - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - if(rhs.m_is_trf) - { - assert(rhs.m_use_montgm); - rhs.trf_to_ordres(); - } - - BigInt workspace = m_value; - workspace *= rhs.m_value; - workspace %= modulus.get_p(); - m_value = workspace; - } - return *this; - } - -GFpElement& GFpElement::operator/=(const GFpElement& rhs) - { - bool use_mres = GFpElement::align_operands_res(*this, rhs); - assert((this->m_is_trf && rhs.m_is_trf) || !(this->m_is_trf && rhs.m_is_trf)); - - if(use_mres) - { - assert(m_use_montgm && rhs.m_use_montgm); - GFpElement rhs_ordres(rhs); - rhs_ordres.trf_to_ordres(); - rhs_ordres.inverse_in_place(); - BigInt workspace = m_value; - workspace *= rhs_ordres.get_value(); - workspace %= modulus.get_p(); - m_value = workspace; - } - else - { - GFpElement inv_rhs(rhs); - inv_rhs.inverse_in_place(); - *this *= inv_rhs; - } - return *this; - } - -bool GFpElement::is_zero() - { - return (m_value.is_zero()); - // this is correct because x_bar = x * r = x = 0 for x = 0 - } - -GFpElement& GFpElement::inverse_in_place() - { - m_value = inverse_mod(m_value, modulus.get_p()); - - if(m_is_trf) - { - assert(m_use_montgm); - - m_value *= modulus.get_r(); - m_value *= modulus.get_r(); - m_value %= modulus.get_p(); - } - assert(m_value <= modulus.get_p()); - return *this; - } - -GFpElement& GFpElement::negate() - { - m_value = modulus.get_p() - m_value; - assert(m_value <= modulus.get_p()); - return *this; - } - -void GFpElement::swap(GFpElement& other) - { - std::swap(m_value, other.m_value); - std::swap(modulus, other.modulus); - std::swap<bool>(m_use_montgm,other.m_use_montgm); - std::swap<bool>(m_is_trf,other.m_is_trf); - } - -std::ostream& operator<<(std::ostream& output, const GFpElement& elem) - { - return output << '(' << elem.get_value() << "," << elem.get_p() << ')'; - } - -bool operator==(const GFpElement& lhs, const GFpElement& rhs) - { - if(lhs.get_p() != rhs.get_p()) - return false; - - // so the modulus is equal, now check the values - bool use_mres = GFpElement::align_operands_res(lhs, rhs); - - if(use_mres) - { - return (lhs.get_mres() == rhs.get_mres()); - } - else - { - return(lhs.get_value() == rhs.get_value()); - } - } - -GFpElement operator+(const GFpElement& lhs, const GFpElement& rhs) - { - // consider the case that lhs and rhs both use montgm: - // then += returns an element which uses montgm. - // thus the return value of op+ here will be an element - // using montgm in this case - // NOTE: the rhs might be transformed when using op+, the lhs never - GFpElement result(lhs); - result += rhs; - return result; - } - -GFpElement operator-(const GFpElement& lhs, const GFpElement& rhs) - { - GFpElement result(lhs); - result -= rhs; - return result; - // NOTE: the rhs might be transformed when using op-, the lhs never - } - -GFpElement operator-(const GFpElement& lhs) - { - return(GFpElement(lhs)).negate(); - } - -GFpElement operator*(const GFpElement& lhs, const GFpElement& rhs) - { - // consider the case that lhs and rhs both use montgm: - // then *= returns an element which uses montgm. - // thus the return value of op* here will be an element - // using montgm in this case - GFpElement result(lhs); - result *= rhs; - return result; - } - -GFpElement operator*(const GFpElement& lhs, u32bit rhs) - { - GFpElement result(lhs); - result *= rhs; - return result; - } - -GFpElement operator*(u32bit lhs, const GFpElement& rhs) - { - return rhs*lhs; - } - -GFpElement operator/(const GFpElement& lhs, const GFpElement& rhs) - { - GFpElement result (lhs); - result /= rhs; - return result; - } - -SecureVector<byte> FE2OSP(const GFpElement& elem) - { - return BigInt::encode_1363(elem.get_value(), elem.get_p().bytes()); - } - -GFpElement OS2FEP(MemoryRegion<byte> const& os, BigInt p) - { - return GFpElement(p, BigInt::decode(os.begin(), os.size())); - } - -GFpElement inverse(const GFpElement& elem) - { - return GFpElement(elem).inverse_in_place(); - } - -} - diff --git a/src/math/gfpmath/gfp_element.h b/src/math/gfpmath/gfp_element.h deleted file mode 100644 index 538d41a47..000000000 --- a/src/math/gfpmath/gfp_element.h +++ /dev/null @@ -1,230 +0,0 @@ -/* -* Arithmetic for prime fields GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2009-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_ELEMENT_H__ -#define BOTAN_GFP_ELEMENT_H__ - -#include <botan/bigint.h> -#include <botan/gfp_modulus.h> -#include <iosfwd> - -namespace Botan { - -struct BOTAN_DLL Illegal_Transformation : public Exception - { - Illegal_Transformation(const std::string& err = - "Requested transformation is not possible") : - Exception(err) {} - }; - -/** - * This class represents one element in GF(p). Enables the convenient, - * transparent use of the montgomery multiplication. - */ -class BOTAN_DLL GFpElement - { - public: - - /** construct an element of GF(p) with the given value. - * use_montg defaults to false and determines wether Montgomery - * multiplications will be use when applying operators *, *= - * @param p the prime number of the field - * @param value the element value - * @param use_montgm whether this object will use Montgomery multiplication - */ - GFpElement(const BigInt& p, const BigInt& value, bool use_montgm = true); - - // GFpElement(const GFpElement& other) = default; - - // const GFpElement& operator=(const GFpElement& other) = default; - - /** - * Switch Montgomery multiplcation optimizations ON - */ - void turn_on_sp_red_mul(); - - /** - * Switch Montgomery multiplcation optimizations OFF - */ - void turn_off_sp_red_mul(); - - /** - * += Operator - * @param rhs the GFpElement to add to the local value - * @result *this - */ - GFpElement& operator+=(const GFpElement& rhs); - - /** - * -= Operator - * @param rhs the GFpElement to subtract from the local value - * @result *this - */ - GFpElement& operator-=(const GFpElement& rhs); - - /** - * *= Operator - * @param rhs the GFpElement to multiply with the local value - * @result *this - */ - GFpElement& operator*=(const GFpElement& rhs); - /** - * /= Operator - * @param rhs the GFpElement to divide the local value by - * @result *this - */ - GFpElement& operator/=(const GFpElement& rhs); - - /** - * *= Operator - * @param rhs the value to multiply with the local value - * @result *this - */ - GFpElement& operator*=(u32bit rhs); - - /** - * Negate internal value(*this *= -1 ) - * @return *this - */ - GFpElement& negate(); - - /** - * Assigns the inverse of *this to *this, i.e. - * *this = (*this)^(-1) - * @result *this - */ - GFpElement& inverse_in_place(); - - /** - * checks whether the value is zero (without provoking - * a backtransformation to the ordinary-residue) - * @result true, if the value is zero, false otherwise. - */ - bool is_zero(); - - /** - * return prime number of GF(p) - * @result a prime number - */ - const BigInt& get_p() const; - - /** - * Return the represented value in GF(p) - * @result The value in GF(p) - */ - const BigInt& get_value() const; - - /** - * Tells whether this GFpElement is currently transformed to an m-residue, - * i.e. in the form x_bar = x * r mod m. - * @result true if it is currently transformed to its m-residue. - */ - bool is_trf_to_mres() const; - - /** - * Transforms this to x_bar = x * r mod m - * @result return the value x_bar. - */ - const BigInt& get_mres() const; - - /** - * Check, if montgomery multiplication is used. - * @result true, if montgomery multiplication is used, false otherwise - */ - bool is_use_montgm() const - { - return m_use_montgm; - } - - /** - * Transforms the arguments in such way that either both - * are in m-residue representation (returns true) or both are - * in ordinary residue representation (returns false). - * m-residue is prefered in case of ambiguity. - * does not toggle m_use_montgm of the arguments. - * Don't be confused about the constness of the arguments: - * the transformation between normal residue and m-residue is - * considered as leaving the object const. - * @param lhs the first operand to be aligned - * @param rhs the second operand to be aligned - * @result true if both are transformed to their m-residue, - * false it both are transformed to their normal residue. - */ - static bool align_operands_res(const GFpElement& lhs, const GFpElement& rhs); - - /** - * swaps the states of *this and other, does not throw! - * @param other The value to swap with - */ - void swap(GFpElement& other); - private: - void ensure_montgm_precomp(); - void trf_to_mres() const; - void trf_to_ordres() const; - - GFpModulus modulus; - mutable BigInt m_value; // ordinary residue or m-residue respectively - - // data members for montgomery multiplication - bool m_use_montgm; - mutable bool m_is_trf; // if m_value is montgomery - }; - -// relational operators -bool BOTAN_DLL operator==(const GFpElement& lhs, const GFpElement& rhs); -inline bool operator!=(const GFpElement& lhs, const GFpElement& rhs ) - { - return !operator==(lhs, rhs); - } - -// arithmetic operators -GFpElement BOTAN_DLL operator+(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator-(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator-(const GFpElement& lhs); - -GFpElement BOTAN_DLL operator*(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator/(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator*(const GFpElement& lhs, u32bit rhs); -GFpElement BOTAN_DLL operator*(u32bit rhs, const GFpElement& lhs); - - -/** -* write a GFpElement to an output stream. -* @param output the output stream to write to -* @param elem the object to write -* @result the output stream -*/ -BOTAN_DLL std::ostream& operator<<(std::ostream& output, const GFpElement& elem); - -// return (*this)^(-1) -GFpElement BOTAN_DLL inverse(const GFpElement& elem); - -// encoding and decoding -SecureVector<byte> BOTAN_DLL FE2OSP(const GFpElement& elem); -GFpElement BOTAN_DLL OS2FEP(MemoryRegion<byte> const& os, BigInt p); - -inline void swap(GFpElement& x, GFpElement& y) - { - x.swap(y); - } - -} - -namespace std { - -template<> inline -void swap<Botan::GFpElement>(Botan::GFpElement& x, - Botan::GFpElement& y) - { - x.swap(y); - } - -} - -#endif diff --git a/src/math/gfpmath/gfp_modulus.h b/src/math/gfpmath/gfp_modulus.h deleted file mode 100644 index fcdd13ee1..000000000 --- a/src/math/gfpmath/gfp_modulus.h +++ /dev/null @@ -1,131 +0,0 @@ -/* -* Modulus and related data for a specific implementation of GF(p) -* -* (C) 2008 Martin Doering, Christoph Ludwig, Falko Strenzke -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_MODULUS_H__ -#define BOTAN_GFP_MODULUS_H__ - -#include <botan/bigint.h> - -namespace Botan { - -class GFpElement; - -/** -* This class represents a GFpElement modulus including the modulus -* related values necessary for the montgomery multiplication. -*/ -class BOTAN_DLL GFpModulus - { - public: - - /** - * Construct a GF(P)-Modulus from a BigInt - */ - GFpModulus(const BigInt& p) - : m_p(p), - m_p_dash(), - m_r(), - m_r_inv() - {} - - // GFpModulus(const GFpModulus& other) = default; - // GFpModulus& operator=(const GFpModulus& other) = default; - - /** - * Tells whether the precomputations necessary for the use of the - * montgomery multiplication have yet been established. - * @result true if the precomputated value are already available. - */ - bool has_precomputations() const - { - return(!m_p_dash.is_zero() && !m_r.is_zero() && !m_r_inv.is_zero()); - } - - /** - * Swaps this with another GFpModulus, does not throw. - * @param other the GFpModulus to swap *this with. - */ - void swap(GFpModulus& other) - { - std::swap(m_p, other.m_p); - std::swap(m_p_dash, other.m_p_dash); - std::swap(m_r, other.m_r); - std::swap(m_r_inv, other.m_r_inv); - } - - /** - * Tells whether the modulus of *this is equal to the argument. - * @param mod the modulus to compare this with - * @result true if the modulus of *this and the argument are equal. - */ - bool p_equal_to(const BigInt& mod) const - { - return (m_p == mod); - } - - /** - * Return the modulus of this GFpModulus. - * @result the modulus of *this. - */ - const BigInt& get_p() const - { - return m_p; - } - - /** - * returns the montgomery multiplication related value r. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result r - */ - const BigInt& get_r() const - { - return m_r; - } - - /** - * returns the montgomery multiplication related value r^{-1}. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result r^{-1} - */ - const BigInt& get_r_inv() const - { - return m_r_inv; - } - - /** - * returns the montgomery multiplication related value p'. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result p' - */ - const BigInt& get_p_dash() const - { - return m_p_dash; - } - - void reset_values(const BigInt& new_p_dash, - const BigInt& new_r, - const BigInt& new_r_inv) - { - m_p_dash = new_p_dash; - m_r = new_r; - m_r_inv = new_r_inv; - } - - private: - BigInt m_p; // the modulus itself - BigInt m_p_dash; - BigInt m_r; - BigInt m_r_inv; - }; - -} - -#endif diff --git a/src/math/gfpmath/info.txt b/src/math/gfpmath/info.txt deleted file mode 100644 index b7b430805..000000000 --- a/src/math/gfpmath/info.txt +++ /dev/null @@ -1,19 +0,0 @@ -define BIGINT_GFP - -<header:public> -curve_gfp.h -gfp_element.h -gfp_modulus.h -point_gfp.h -</header:public> - -<source> -curve_gfp.cpp -gfp_element.cpp -point_gfp.cpp -</source> - -<requires> -bigint -numbertheory -</requires> diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp deleted file mode 100644 index 4b2de7913..000000000 --- a/src/math/gfpmath/point_gfp.cpp +++ /dev/null @@ -1,750 +0,0 @@ -/* -* Arithmetic for point groups of elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/point_gfp.h> -#include <botan/numthry.h> - -namespace Botan { - -// construct the point at infinity or a random point -PointGFp::PointGFp(const CurveGFp& curve) : - mC(curve), - mX(curve.get_p(), 0), - mY(curve.get_p(), 1), - mZ(curve.get_p(), 0) - { - } - -// construct a point given its jacobian projective coordinates -PointGFp::PointGFp(const CurveGFp& curve, const GFpElement& x, - const GFpElement& y, const GFpElement& z) : - mC(curve), - mX(x), - mY(y), - mZ(z) - { - } - -PointGFp::PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y) : - mC(curve), - mX(x), - mY(y), - mZ(curve.get_p(),1) - { - } - -// arithmetic operators -PointGFp& PointGFp::operator+=(const PointGFp& rhs) - { - if(is_zero()) - { - *this = rhs; - return *this; - } - if(rhs.is_zero()) - { - return *this; - } - - GFpElement U1 = mX; - GFpElement S1 = mY; - - if(rhs.mZ != mC.get_mres_one()) - { - GFpElement rhs_z2 = rhs.mZ * rhs.mZ; - - U1 *= rhs_z2; - S1 *= rhs_z2 * rhs.mZ; - } - - GFpElement U2 = rhs.mX; - GFpElement S2 = rhs.mY; - - if(mZ != mC.get_mres_one()) - { - GFpElement lhs_z2 = mZ * mZ; - - U2 *= lhs_z2; - S2 *= lhs_z2 * mZ; - } - - GFpElement H(U2 - U1); - GFpElement r(S2 - S1); - - if(H.is_zero()) - { - if(r.is_zero()) - { - mult2_in_place(); - return *this; - } - - *this = PointGFp(mC); // setting myself to zero - return *this; - } - - U2 = H * H; - - S2 = U2 * H; - - U2 *= U1; - - GFpElement x(r*r - S2 - (U2+U2)); - - GFpElement z(S1 * S2); - - GFpElement y(r * (U2-x) - z); - - if(mZ == mC.get_mres_one()) - { - if(rhs.mZ != mC.get_mres_one()) - z = rhs.mZ * H; - else - z = H; - } - else if(rhs.mZ != mC.get_mres_one()) - { - U1 = mZ * rhs.mZ; - z = U1 * H; - } - else - z = mZ * H; - - mX = x; - mY = y; - mZ = z; - - return *this; - - } -PointGFp& PointGFp::operator-=(const PointGFp& rhs) - { - PointGFp minus_rhs = PointGFp(rhs).negate(); - - if(is_zero()) - { - *this = minus_rhs; - } - else - { - *this += minus_rhs; - } - return *this; - } - -PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, - const BigInt& /*point_order*/, - const BigInt& /*max_secr*/) - { - // NOTE: FS: so far this is code duplication of op*=. - // we have to see how we deal with this. - // fact is that we will probably modify this function - // while evaluating the countermeasures - // whereas we probably will not start modifying the - // function operator*=. - // however, in the end both should be merged. - - // use montgomery mult. in this operation - this->turn_on_sp_red_mul(); - - PointGFp H(mC); - - PointGFp P(*this); - BigInt m(scalar); - - if(m < BigInt(0)) - { - m = -m; - P.negate(); - } - if(P.is_zero() || (m == BigInt(0))) - { - *this = H; - return *this; - } - if(m == BigInt(1)) - return *this; - - int mul_bits = m.bits(); - - for(int i = mul_bits - 1; i >= 0; i--) - { - H.mult2_in_place(); - - if(m.get_bit(i)) - H += P; - } - - if(!H.is_zero()) // cannot convert if H == O - *this = H.get_z_to_one(); - else - *this = H; - - mX.turn_off_sp_red_mul(); - mY.turn_off_sp_red_mul(); - mZ.turn_off_sp_red_mul(); - return *this; - } - -PointGFp& PointGFp::operator*=(const BigInt& scalar) - { - // use montgomery mult. in this operation - - this->turn_on_sp_red_mul(); - - PointGFp H(this->mC); // create as zero - H.turn_on_sp_red_mul(); - PointGFp P(*this); - P.turn_on_sp_red_mul(); - BigInt m(scalar); - - if(m < BigInt(0)) - { - m = -m; - P.negate(); - } - - if(P.is_zero() || (m == BigInt(0))) - { - *this = H; - return *this; - } - - if(m == BigInt(1)) //*this == P already - return *this; - - const int l = m.bits() - 1; - for(int i = l; i >= 0; --i) - { - H.mult2_in_place(); - if(m.get_bit(i)) - H += P; - } - - if(!H.is_zero()) // cannot convert if H == O - *this = H.get_z_to_one(); - else - *this = H; - - return *this; - } - -PointGFp& PointGFp::negate() - { - if(!is_zero()) - mY.negate(); - - return *this; - } - -// *this *= 2 -PointGFp& PointGFp::mult2_in_place() - { - if(is_zero()) - return *this; - else if(mY.is_zero()) - { - *this = PointGFp(mC); // setting myself to zero - return *this; - } - - GFpElement Y_squared = mY*mY; - - GFpElement S = mX * Y_squared; - - GFpElement x = S + S; - - S = x + x; - - GFpElement a_z4 = mC.get_mres_a(); - if(mZ != mC.get_mres_one()) - { - GFpElement z2 = mZ * mZ; - a_z4 *= z2; - a_z4 *= z2; - } - - GFpElement y(mX * mX); - - GFpElement M(y + y + y + a_z4); - - x = M * M - (S+S); - - y = Y_squared * Y_squared; - - GFpElement U(y + y); - - GFpElement z = U + U; - - U = z + z; - - y = M * (S - x) - U; - - if(mZ != mC.get_mres_one()) - z = mY * mZ; - else - z = mY; - - z = z + z; - - mX = x; - mY = y; - mZ = z; - - return *this; - } - -void PointGFp::turn_on_sp_red_mul() const - { - mX.turn_on_sp_red_mul(); - mY.turn_on_sp_red_mul(); - mZ.turn_on_sp_red_mul(); - - // also pretransform, otherwise - // we might have bad results with respect to - // performance because - // additions/subtractions in mult2_in_place() - // and op+= spread untransformed GFpElements - mX.get_mres(); - mY.get_mres(); - mZ.get_mres(); - } - -/** -* returns a point equivalent to *this but were -* Z has value one, i.e. x and y correspond to -* their values in affine coordinates -*/ -PointGFp PointGFp::get_z_to_one() const - { - return PointGFp(*this).set_z_to_one(); - } - -/** -* changes the representation of *this so that -* Z has value one, i.e. x and y correspond to -* their values in affine coordinates. -* returns *this. -*/ -const PointGFp& PointGFp::set_z_to_one() const - { - if(!(mZ.get_value() == BigInt(1)) && !(mZ.get_value() == BigInt(0))) - { - GFpElement z = inverse(mZ); - GFpElement z2 = z * z; - z *= z2; - GFpElement x = mX * z2; - GFpElement y = mY * z; - mZ = GFpElement(mC.get_p(), BigInt(1)); - mX = x; - mY = y; - } - else - { - if(mZ.get_value() == BigInt(0)) - { - throw Illegal_Transformation("cannot convert Z to one"); - } - } - return *this; // mZ = 1 already - } - -GFpElement PointGFp::get_affine_x() const - { - if(is_zero()) - throw Illegal_Transformation("cannot convert to affine"); - - GFpElement z2 = mZ * mZ; - return mX * z2.inverse_in_place(); - } - -GFpElement PointGFp::get_affine_y() const - { - if(is_zero()) - throw Illegal_Transformation("cannot convert to affine"); - - GFpElement z3 = mZ * mZ * mZ; - return mY * z3.inverse_in_place(); - } - -GFpElement PointGFp::get_jac_proj_x() const - { - return GFpElement(mX); - } - -GFpElement PointGFp::get_jac_proj_y() const - { - return GFpElement(mY); - } - -GFpElement PointGFp::get_jac_proj_z() const - { - return GFpElement(mZ); - } - -// Is this the point at infinity? -bool PointGFp::is_zero() const - { - return(mX.is_zero() && mZ.is_zero()); - //NOTE: the calls to GFpElement::is_zero() instead of getting the value and - // and comparing it are import because they do not provoke backtransformations - // to the ordinary residue. - } - -// Is the point still on the curve?? -// (If everything is correct, the point is always on its curve; then the -// function will return silently. If Oskar managed to corrupt this object's state, -// then it will throw an exception.) - -void PointGFp::check_invariants() const - { - if(is_zero()) - { - return; - } - const GFpElement y2 = mY * mY; - const GFpElement x3 = mX * mX * mX; - - if(mZ.get_value() == BigInt(1)) - { - GFpElement ax = mC.get_a() * mX; - if(y2 != (x3 + ax + mC.get_b())) - { - throw Illegal_Point(); - } - - } - - GFpElement Zpow2 = mZ * mZ; - GFpElement Zpow3 = Zpow2 * mZ; - GFpElement AZpow4 = Zpow3 * mZ * mC.get_a(); - const GFpElement aXZ4 = AZpow4 * mX; - const GFpElement bZ6 = mC.get_b() * Zpow3 * Zpow3; - - if(y2 != (x3 + aXZ4 + bZ6)) - throw Illegal_Point(); - } - -// swaps the states of *this and other, does not throw! -void PointGFp::swap(PointGFp& other) - { - mC.swap(other.mC); - mX.swap(other.mX); - mY.swap(other.mY); - mZ.swap(other.mZ); - } - -PointGFp mult2(const PointGFp& point) - { - return (PointGFp(point)).mult2_in_place(); - } - -bool operator==(const PointGFp& lhs, PointGFp const& rhs) - { - if(lhs.is_zero() && rhs.is_zero()) - { - return true; - } - if((lhs.is_zero() && !rhs.is_zero()) || (!lhs.is_zero() && rhs.is_zero())) - { - return false; - } - // neither operand is zero, so we can call get_z_to_one() - //assert(!lhs.is_zero()); - //assert(!rhs.is_zero()); - PointGFp aff_lhs = lhs.get_z_to_one(); - PointGFp aff_rhs = rhs.get_z_to_one(); - return (aff_lhs.get_curve() == aff_rhs.get_curve() && - aff_lhs.get_jac_proj_x() == aff_rhs.get_jac_proj_x() && - aff_lhs.get_jac_proj_y() == aff_rhs.get_jac_proj_y()); - } - -// arithmetic operators -PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) - { - PointGFp tmp(lhs); - return tmp += rhs; - } - -PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) - { - PointGFp tmp(lhs); - return tmp -= rhs; - } - -PointGFp operator-(const PointGFp& lhs) - { - return PointGFp(lhs).negate(); - } - -PointGFp operator*(const BigInt& scalar, const PointGFp& point) - { - PointGFp result(point); - return result *= scalar; - } - -PointGFp operator*(const PointGFp& point, const BigInt& scalar) - { - PointGFp result(point); - return result *= scalar; - } - -PointGFp mult_point_secure(const PointGFp& point, const BigInt& scalar, - const BigInt& point_order, const BigInt& max_secret) - { - PointGFp result(point); - result.mult_this_secure(scalar, point_order, max_secret); - return result; - } - -// encoding and decoding -SecureVector<byte> EC2OSP(const PointGFp& point, byte format) - { - SecureVector<byte> result; - if(format == PointGFp::UNCOMPRESSED) - { - result = encode_uncompressed(point); - } - else if(format == PointGFp::COMPRESSED) - { - result = encode_compressed(point); - - } - else if(format == PointGFp::HYBRID) - { - result = encode_hybrid(point); - } - else - { - throw Invalid_Argument("illegal point encoding format specification"); - } - return result; - } -SecureVector<byte> encode_compressed(const PointGFp& point) - { - - - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (l+1); - result[0] = 2; - BigInt x = point.get_affine_x().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - result.copy(1, bX.begin(), bX.size()); - BigInt y = point.get_affine_y().get_value(); - if(y.get_bit(0)) - { - result[0] |= 1; - } - return result; - } - - -SecureVector<byte> encode_uncompressed(const PointGFp& point) - { - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (2*l+1); - result[0] = 4; - BigInt x = point.get_affine_x().get_value(); - BigInt y = point.get_affine_y().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - SecureVector<byte> bY = BigInt::encode_1363(y, l); - result.copy(1, bX.begin(), l); - result.copy(l+1, bY.begin(), l); - return result; - - } - -SecureVector<byte> encode_hybrid(const PointGFp& point) - { - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (2*l+1); - result[0] = 6; - BigInt x = point.get_affine_x().get_value(); - BigInt y = point.get_affine_y().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - SecureVector<byte> bY = BigInt::encode_1363(y, l); - result.copy(1, bX.begin(), bX.size()); - result.copy(l+1, bY.begin(), bY.size()); - if(y.get_bit(0)) - { - result[0] |= 1; - } - return result; - } - -PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve) - { - if(os.size() == 1 && os[0] == 0) - { - return PointGFp(curve); // return zero - } - SecureVector<byte> bX; - SecureVector<byte> bY; - - GFpElement x(1,0); - GFpElement y(1,0); - GFpElement z(1,0); - - const byte pc = os[0]; - BigInt bi_dec_x; - BigInt bi_dec_y; - switch (pc) - { - case 2: - case 3: - //compressed form - bX = SecureVector<byte>(os.size() - 1); - bX.copy(os.begin()+1, os.size()-1); - - bi_dec_x = BigInt::decode(bX, bX.size()); - x = GFpElement(curve.get_p(), bi_dec_x); - bool yMod2; - yMod2 = (pc & 1) == 1; - y = PointGFp::decompress(yMod2, x, curve); - break; - case 4: - // uncompressed form - int l; - l = (os.size() -1)/2; - bX = SecureVector<byte>(l); - bY = SecureVector<byte>(l); - bX.copy(os.begin()+1, l); - bY.copy(os.begin()+1+l, l); - bi_dec_x = BigInt::decode(bX.begin(), bX.size()); - - bi_dec_y = BigInt::decode(bY.begin(),bY.size()); - x = GFpElement(curve.get_p(), bi_dec_x); - y = GFpElement(curve.get_p(), bi_dec_y); - break; - - case 6: - case 7: - //hybrid form - l = (os.size() - 1)/2; - bX = SecureVector<byte>(l); - bY = SecureVector<byte>(l); - bX.copy(os.begin() + 1, l); - bY.copy(os.begin()+1+l, l); - yMod2 = (pc & 0x01) == 1; - if(!(PointGFp::decompress(yMod2, x, curve) == y)) - { - throw Illegal_Point("error during decoding hybrid format"); - } - break; - default: - throw Invalid_Argument("encountered illegal format specification while decoding point"); - } - z = GFpElement(curve.get_p(), BigInt(1)); - //assert((x.is_trf_to_mres() && x.is_use_montgm()) || !x.is_trf_to_mres()); - //assert((y.is_trf_to_mres() && y.is_use_montgm()) || !y.is_trf_to_mres()); - //assert((z.is_trf_to_mres() && z.is_use_montgm()) || !z.is_trf_to_mres()); - PointGFp result(curve, x, y, z); - result.check_invariants(); - //assert((result.get_jac_proj_x().is_trf_to_mres() && result.get_jac_proj_x().is_use_montgm()) || !result.get_jac_proj_x().is_trf_to_mres()); - //assert((result.get_jac_proj_y().is_trf_to_mres() && result.get_jac_proj_y().is_use_montgm()) || !result.get_jac_proj_y().is_trf_to_mres()); - //assert((result.get_jac_proj_z().is_trf_to_mres() && result.get_jac_proj_z().is_use_montgm()) || !result.get_jac_proj_z().is_trf_to_mres()); - return result; - } - -GFpElement PointGFp::decompress(bool yMod2, const GFpElement& x, - const CurveGFp& curve) - { - BigInt xVal = x.get_value(); - BigInt xpow3 = xVal * xVal * xVal; - BigInt g = curve.get_a().get_value() * xVal; - g += xpow3; - g += curve.get_b().get_value(); - g = g%curve.get_p(); - BigInt z = ressol(g, curve.get_p()); - - if(z < 0) - throw Illegal_Point("error during decompression"); - - bool zMod2 = z.get_bit(0); - if((zMod2 && ! yMod2) || (!zMod2 && yMod2)) - { - z = curve.get_p() - z; - } - return GFpElement(curve.get_p(),z); - } - -PointGFp create_random_point(RandomNumberGenerator& rng, - const CurveGFp& curve) - { - - // create a random point - GFpElement mX(1,1); - GFpElement mY(1,1); - GFpElement mZ(1,1); - GFpElement minusOne(curve.get_p(), BigInt(BigInt::Negative,1)); - mY = minusOne; - GFpElement y2(1,1); - GFpElement x(1,1); - - while (mY == minusOne) - { - BigInt value(rng, curve.get_p().bits()); - mX = GFpElement(curve.get_p(),value); - y2 = curve.get_a() * mX; - x = mX * mX; - x *= mX; - y2 += (x + curve.get_b()); - - value = ressol(y2.get_value(), curve.get_p()); - - if(value < 0) - mY = minusOne; - else - mY = GFpElement(curve.get_p(), value); - } - mZ = GFpElement(curve.get_p(), BigInt(1)); - - return PointGFp(curve, mX, mY, mZ); - } - -} // namespace Botan diff --git a/src/math/gfpmath/point_gfp.h b/src/math/gfpmath/point_gfp.h deleted file mode 100644 index 276635f56..000000000 --- a/src/math/gfpmath/point_gfp.h +++ /dev/null @@ -1,268 +0,0 @@ -/* -* Arithmetic for point groups of elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_POINT_GFP_H__ -#define BOTAN_POINT_GFP_H__ - -#include <botan/curve_gfp.h> -#include <vector> - -namespace Botan { - -struct BOTAN_DLL Illegal_Point : public Exception - { - Illegal_Point(const std::string& err = "") : Exception(err) {} - }; - -/** -* This class represents one point on a curve of GF(p) -*/ -class BOTAN_DLL PointGFp - { - public: - /** - * uncompressed encoding byte value - */ - static const int UNCOMPRESSED = 0; - - /** - * compressed encoding byte value - */ - static const int COMPRESSED = 1; - - /** - * hybrid encoding byte value - */ - static const int HYBRID = 2; - - /** - * Construct the point O - * @param curve The base curve - */ - PointGFp(const CurveGFp& curve); - - /** - * Construct a point given its affine coordinates - * @param curve the base curve - * @param x affine x coordinate - * @param y affine y coordinate - */ - PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y); - - /** - * Construct a point given its jacobian projective coordinates - * @param curve the base curve - * @param x jacobian projective x coordinate - * @param y jacobian projective y coordinate - * @param z jacobian projective y coordinate - */ - PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y, - const GFpElement& z); - - //PointGFp(const PointGFp& other) = default; - //PointGFp& operator=(const PointGFp& other) = default; - - /** - * += Operator - * @param rhs the PointGFp to add to the local value - * @result resulting PointGFp - */ - PointGFp& operator+=(const PointGFp& rhs); - - /** - * -= Operator - * @param rhs the PointGFp to subtract from the local value - * @result resulting PointGFp - */ - PointGFp& operator-=(const PointGFp& rhs); - - /** - * *= Operator - * This function turns on the the special reduction multiplication - * itself for fast computation, turns it off again when finished. - * @param scalar the PointGFp to multiply with *this - * @result resulting PointGFp - */ - PointGFp& operator*=(const BigInt& scalar); - - /** - * the equivalent to operator*= with countermeasures against - * sidechannel attacks, using the randomized exponent - * and add-and-double-always - * countermeasures (suitable for ECDSA and ECKAEG) - * @param scalar the scalar to multiply the point with - * @param point_order a multiple of the order of the point - *(= n * k in the general case; k is the cofactor) - * @param max_secr the maximal size of the scalar - * (will usually be n-1 ) - * @result resulting PointGFp - */ - PointGFp& mult_this_secure(const BigInt& scalar, - const BigInt& point_order, - const BigInt& max_secr); - - /** - * Negate internal value(*this *= -1 ) - * @return *this - */ - PointGFp& negate(); - - /** - * Multiply the point by two(*this *= 2 ) - * @return *this - */ - PointGFp& mult2_in_place(); - - /** - * Set z coordinate to one. - * @return *this - */ - const PointGFp& set_z_to_one() const; - - /** - * Turn on the special reduction multiplication (i.e. the - * Montgomery multiplication in the current implementation) for - * the coordinates. This enables fast execution of mult2_in_place() - * and operator+=(). - */ - void turn_on_sp_red_mul() const; - - /** - * Return a point - * where the coordinates are transformed - * so that z equals one, - * thus x and y have just the affine values. - * @result *this - */ - PointGFp get_z_to_one() const; - - /** - * Return base curve of this point - * @result the curve over GF(p) of this point - */ - const CurveGFp& get_curve() const { return mC; } - - /** - * get affine x coordinate - * @result affine x coordinate - */ - GFpElement get_affine_x() const; - - /** - * get affine y coordinate - * @result affine y coordinate - */ - GFpElement get_affine_y() const; - - /** - * get the jacobian projective x coordinate - * @result jacobian projective x coordinate - */ - GFpElement get_jac_proj_x() const; - - /** - * get the jacobian projective y coordinate - * @result jacobian projective y coordinate - */ - GFpElement get_jac_proj_y() const; - - /** - * get the jacobian projective z coordinate - * @result jacobian projective z coordinate - */ - GFpElement get_jac_proj_z() const; - - /** - * Is this the point at infinity? - * @result true, if this point is at infinity, false otherwise. - */ - bool is_zero() const; - - /** - * Checks whether the point is to be found on the underlying curve. - * Throws an Invalid_Point exception in case of detecting that the point - * does not satisfy the curve equation. - * To be used to ensure against fault attacks. - */ - void check_invariants() const; - - /** - * swaps the states of *this and other, does not throw! - * @param other the object to swap values with - */ - void swap(PointGFp& other); - - static GFpElement decompress(bool yMod2, GFpElement const& x, const CurveGFp& curve); - - private: - CurveGFp mC; - mutable GFpElement mX; // NOTE: these values must be mutable (affine<->proj) - mutable GFpElement mY; - mutable GFpElement mZ; - }; - -// relational operators -bool BOTAN_DLL operator==(const PointGFp& lhs, const PointGFp& rhs); -inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs ) - { - return !operator==(lhs, rhs); - } - -// arithmetic operators -PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); -PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); -PointGFp BOTAN_DLL operator-(const PointGFp& lhs); - -PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); -PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); -PointGFp BOTAN_DLL mult_point_secure(const PointGFp& point, - const BigInt& scalar, - const BigInt& point_order, - const BigInt& max_secret); - -PointGFp BOTAN_DLL mult2(const PointGFp& point); - -PointGFp BOTAN_DLL create_random_point(RandomNumberGenerator& rng, - const CurveGFp& curve); - -// encoding and decoding -SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); -PointGFp BOTAN_DLL OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve); - -/* Should these be private? */ -SecureVector<byte> -BOTAN_DLL encode_uncompressed(const PointGFp& point); - -SecureVector<byte> BOTAN_DLL encode_hybrid(const PointGFp& point); -SecureVector<byte> BOTAN_DLL encode_compressed(const PointGFp& point); - -// swaps the states of point1 and point2, does not throw! -// cf. Meyers, Item 25 -inline -void swap(PointGFp& point1, PointGFp& point2 ) - { - point1.swap(point2); - } - -} // namespace Botan - -namespace std { - -// swaps the states of point1 and point2, does not throw! -// cf. Meyers, Item 25 -template<> inline void -swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) { x.swap(y); } - -} // namespace std - -#endif diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h new file mode 100644 index 000000000..697065dfe --- /dev/null +++ b/src/math/numbertheory/curve_gfp.h @@ -0,0 +1,96 @@ +/* +* Elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_GFP_CURVE_H__ +#define BOTAN_GFP_CURVE_H__ + +#include <botan/numthry.h> +#include <botan/reducer.h> + +namespace Botan { + +/** +* This class represents an elliptic curve over GF(p) +*/ +class BOTAN_DLL CurveGFp + { + public: + + /** + * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) + * @param p prime number of the field + * @param a first coefficient + * @param b second coefficient + */ + CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) : + p(p), a(a), b(b), reducer_p(p) {} + + // CurveGFp(const CurveGFp& other) = default; + // CurveGFp& operator=(const CurveGFp& other) = default; + + /** + * Get coefficient a + * @result coefficient a + */ + const BigInt& get_a() const { return a; } + + /** + * Get coefficient b + * @result coefficient b + */ + const BigInt& get_b() const { return b; } + + /** + * Get prime modulus of the field of the curve + * @result prime modulus of the field of the curve + */ + const BigInt& get_p() const { return p; } + + const Modular_Reducer& mod_p() const { return reducer_p; } + + /** + * swaps the states of *this and other, does not throw + * @param other The curve to swap values with + */ + void swap(CurveGFp& other) + { + std::swap(a, other.a); + std::swap(b, other.b); + std::swap(p, other.p); + } + + bool operator==(const CurveGFp& other) const + { + return (p == other.p && a == other.a && b == other.b); + } + + private: + BigInt p, a, b; + Modular_Reducer reducer_p; + }; + +inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) + { + return !(lhs == rhs); + } + +} + +namespace std { + +template<> inline +void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, + Botan::CurveGFp& curve2) + { + curve1.swap(curve2); + } + +} // namespace std + +#endif diff --git a/src/math/numbertheory/info.txt b/src/math/numbertheory/info.txt index 19abfaaa0..58851e055 100644 --- a/src/math/numbertheory/info.txt +++ b/src/math/numbertheory/info.txt @@ -4,7 +4,9 @@ define BIGINT_MATH <header:public> blinding.h +curve_gfp.h numthry.h +point_gfp.h pow_mod.h reducer.h </header:public> @@ -20,6 +22,7 @@ jacobi.cpp make_prm.cpp mp_numth.cpp numthry.cpp +point_gfp.cpp pow_mod.cpp powm_fw.cpp powm_mnt.cpp diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp index 760250712..f79fdec2b 100644 --- a/src/math/numbertheory/numthry.cpp +++ b/src/math/numbertheory/numthry.cpp @@ -1,11 +1,12 @@ /* * Number Theory Functions -* (C) 1999-2009 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/numthry.h> +#include <botan/reducer.h> #include <botan/internal/bit_ops.h> #include <algorithm> @@ -14,6 +15,62 @@ namespace Botan { namespace { /* +* Miller-Rabin Primality Tester +*/ +class MillerRabin_Test + { + public: + bool passes_test(const BigInt& nonce); + MillerRabin_Test(const BigInt& num); + private: + BigInt n, r, n_minus_1; + u32bit s; + Fixed_Exponent_Power_Mod pow_mod; + Modular_Reducer reducer; + }; + +/* +* Miller-Rabin Test +*/ +bool MillerRabin_Test::passes_test(const BigInt& a) + { + if(a < 2 || a >= n_minus_1) + throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); + + BigInt y = pow_mod(a); + if(y == 1 || y == n_minus_1) + return true; + + for(u32bit i = 1; i != s; ++i) + { + y = reducer.square(y); + + if(y == 1) + return false; + if(y == n_minus_1) + return true; + } + return false; + } + +/* +* Miller-Rabin Constructor +*/ +MillerRabin_Test::MillerRabin_Test(const BigInt& num) + { + if(num.is_even() || num < 3) + throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); + + n = num; + n_minus_1 = n - 1; + s = low_zero_bits(n_minus_1); + r = n_minus_1 >> s; + + pow_mod = Fixed_Exponent_Power_Mod(r, n); + reducer = Modular_Reducer(n); + } + +/* * Miller-Rabin Iterations */ u32bit miller_rabin_test_iterations(u32bit bits, bool verify) @@ -300,45 +357,4 @@ bool passes_mr_tests(RandomNumberGenerator& rng, return true; } -/* -* Miller-Rabin Test -*/ -bool MillerRabin_Test::passes_test(const BigInt& a) - { - if(a < 2 || a >= n_minus_1) - throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); - - BigInt y = pow_mod(a); - if(y == 1 || y == n_minus_1) - return true; - - for(u32bit i = 1; i != s; ++i) - { - y = reducer.square(y); - - if(y == 1) - return false; - if(y == n_minus_1) - return true; - } - return false; - } - -/* -* Miller-Rabin Constructor -*/ -MillerRabin_Test::MillerRabin_Test(const BigInt& num) - { - if(num.is_even() || num < 3) - throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); - - n = num; - n_minus_1 = n - 1; - s = low_zero_bits(n_minus_1); - r = n_minus_1 >> s; - - pow_mod = Fixed_Exponent_Power_Mod(r, n); - reducer = Modular_Reducer(n); - } - } diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h index ae2c219fc..080f184a4 100644 --- a/src/math/numbertheory/numthry.h +++ b/src/math/numbertheory/numthry.h @@ -9,7 +9,6 @@ #define BOTAN_NUMBER_THEORY_H__ #include <botan/bigint.h> -#include <botan/reducer.h> #include <botan/pow_mod.h> #include <botan/rng.h> @@ -100,21 +99,6 @@ const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256; extern const u16bit BOTAN_DLL PRIMES[]; extern const u64bit PRIME_PRODUCTS[]; -/* -* Miller-Rabin Primality Tester -*/ -class BOTAN_DLL MillerRabin_Test - { - public: - bool passes_test(const BigInt&); - MillerRabin_Test(const BigInt&); - private: - BigInt n, r, n_minus_1; - u32bit s; - Fixed_Exponent_Power_Mod pow_mod; - Modular_Reducer reducer; - }; - } #endif diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp new file mode 100644 index 000000000..06c42d18c --- /dev/null +++ b/src/math/numbertheory/point_gfp.cpp @@ -0,0 +1,423 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/point_gfp.h> +#include <botan/numthry.h> + +namespace Botan { + +namespace { + +BigInt decompress_point(bool yMod2, + const BigInt& x, + const CurveGFp& curve) + { + BigInt xpow3 = x * x * x; + + BigInt g = curve.get_a() * x; + g += xpow3; + g += curve.get_b(); + g = g % curve.get_p(); + + BigInt z = ressol(g, curve.get_p()); + + if(z < 0) + throw Illegal_Point("error during decompression"); + + if(z.get_bit(0) != yMod2) + z = curve.get_p() - z; + + return z; + } + +} + +// arithmetic operators +PointGFp& PointGFp::operator+=(const PointGFp& rhs) + { + if(rhs.is_zero()) + return *this; + + if(is_zero()) + { + *this = rhs; + return *this; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt rhs_z2 = mod_p.square(rhs.coord_z); + BigInt U1 = mod_p.multiply(coord_x, rhs_z2); + BigInt S1 = mod_p.multiply(coord_y, mod_p.multiply(rhs.coord_z, rhs_z2)); + + BigInt lhs_z2 = mod_p.square(coord_z); + BigInt U2 = mod_p.multiply(rhs.coord_x, lhs_z2); + BigInt S2 = mod_p.multiply(rhs.coord_y, mod_p.multiply(coord_z, lhs_z2)); + + BigInt H = mod_p.reduce(U2 - U1); + BigInt r = mod_p.reduce(S2 - S1); + + if(H.is_zero()) + { + if(r.is_zero()) + { + mult2_in_place(); + return *this; + } + + *this = PointGFp(curve); // setting myself to zero + return *this; + } + + U2 = mod_p.square(H); + + S2 = mod_p.multiply(U2, H); + + U2 = mod_p.multiply(U1, U2); + + BigInt x = mod_p.reduce(mod_p.square(r) - S2 - mod_p.multiply(2, U2)); + BigInt y = mod_p.reduce(mod_p.multiply(r, (U2-x)) - mod_p.multiply(S1, S2)); + BigInt z = mod_p.multiply(mod_p.multiply(coord_z, rhs.coord_z), H); + + coord_x = x; + coord_y = y; + coord_z = z; + + return *this; + } + +PointGFp& PointGFp::operator-=(const PointGFp& rhs) + { + PointGFp minus_rhs = PointGFp(rhs).negate(); + + if(is_zero()) + *this = minus_rhs; + else + *this += minus_rhs; + + return *this; + } + +PointGFp& PointGFp::operator*=(const BigInt& scalar) + { + if(scalar.abs() <= 2) // special cases for small values + { + u32bit value = scalar.abs().to_u32bit(); + + if(value == 0) + *this = PointGFp(curve); // set to zero point + else if(value == 1) + { + if(scalar.is_negative()) + this->negate(); + } + else if(value == 2) + { + this->mult2_in_place(); + if(scalar.is_negative()) + this->negate(); + } + + return *this; + } + + PointGFp H(this->curve); // create as zero + PointGFp P(*this); + + if(scalar.is_negative()) + P.negate(); + + for(int i = scalar.bits() - 1; i >= 0; --i) + { + H.mult2_in_place(); + if(scalar.get_bit(i)) + H += P; + } + + if(!H.is_zero()) // cannot convert if H == O + { + /** + * Convert H to an equivalent point with z == 1, thus x and y + * correspond to their affine coordinates + */ + if(H.coord_z != 1) + { + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z_inv = inverse_mod(H.coord_z, curve.get_p()); + + BigInt z_inv_2 = mod_p.square(z_inv); + + H.coord_x = mod_p.multiply(H.coord_x, z_inv_2); + H.coord_y = mod_p.multiply(H.coord_y, mod_p.multiply(z_inv, z_inv_2)); + H.coord_z = 1; + } + } + + *this = H; + return *this; + } + +PointGFp& PointGFp::negate() + { + if(!is_zero()) + coord_y = curve.get_p() - coord_y; + + return *this; + } + +// *this *= 2 +void PointGFp::mult2_in_place() + { + if(is_zero()) + return; + else if(coord_y.is_zero()) + { + *this = PointGFp(curve); // setting myself to zero + return; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y_2 = mod_p.square(coord_y); + + BigInt S = mod_p.multiply(4, mod_p.multiply(coord_x, y_2)); + + BigInt a_z4 = mod_p.multiply(curve.get_a(), + mod_p.square(mod_p.square(coord_z))); + + BigInt M = mod_p.reduce(a_z4 + 3 * mod_p.square(coord_x)); + + BigInt x = mod_p.reduce(mod_p.square(M) - mod_p.multiply(2, S)); + + BigInt y = mod_p.square(y_2); + + BigInt z = mod_p.multiply(2, mod_p.reduce(y + y)); + + BigInt U = mod_p.reduce(z + z); + + y = mod_p.reduce(mod_p.multiply(M, S - x) - U); + + z = mod_p.multiply(2, mod_p.multiply(coord_y, coord_z)); + + coord_x = x; + coord_y = y; + coord_z = z; + } + +BigInt PointGFp::get_affine_x() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z2 = mod_p.square(coord_z); + return mod_p.multiply(coord_x, inverse_mod(z2, curve.get_p())); + } + +BigInt PointGFp::get_affine_y() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z3 = mod_p.cube(coord_z); + return mod_p.multiply(coord_y, inverse_mod(z3, curve.get_p())); + } + +// Is this the point at infinity? +bool PointGFp::is_zero() const + { + return(coord_x.is_zero() && coord_z.is_zero()); + } + +void PointGFp::check_invariants() const + { + /* + Is the point still on the curve?? (If everything is correct, the + point is always on its curve; then the function will return + silently. If Oskar managed to corrupt this object's state, then it + will throw an exception.) + */ + + if(is_zero()) + return; + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y2 = mod_p.square(coord_y); + BigInt x3 = mod_p.cube(coord_x); + + BigInt ax = mod_p.multiply(coord_x, curve.get_a()); + + if(coord_z == 1) + { + if(mod_p.reduce(x3 + ax + curve.get_b()) != y2) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x + b"); + } + + BigInt z2 = mod_p.square(coord_z); + BigInt z3 = mod_p.multiply(coord_z, z2); + + BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, coord_z), ax); + + BigInt b_z6 = mod_p.multiply(curve.get_b(), mod_p.square(z3)); + + if(y2 != mod_p.reduce(x3 + ax_z4 + b_z6)) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x*z^4 + b*z^6"); + } + +// swaps the states of *this and other, does not throw! +void PointGFp::swap(PointGFp& other) + { + curve.swap(other.curve); + coord_x.swap(other.coord_x); + coord_y.swap(other.coord_y); + coord_z.swap(other.coord_z); + } + +bool PointGFp::operator==(const PointGFp& other) const + { + return (coord_x == other.coord_x && + coord_y == other.coord_y && + coord_z == other.coord_z && + get_curve() == other.get_curve()); + } + +// arithmetic operators +PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp += rhs; + } + +PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp -= rhs; + } + +PointGFp operator-(const PointGFp& lhs) + { + return PointGFp(lhs).negate(); + } + +PointGFp operator*(const BigInt& scalar, const PointGFp& point) + { + PointGFp result(point); + return result *= scalar; + } + +PointGFp operator*(const PointGFp& point, const BigInt& scalar) + { + PointGFp result(point); + return result *= scalar; + } + +// encoding and decoding +SecureVector<byte> EC2OSP(const PointGFp& point, byte format) + { + if(point.is_zero()) + return SecureVector<byte>(1); // single 0 byte + + const u32bit p_bytes = point.get_curve().get_p().bytes(); + + BigInt x = point.get_affine_x(); + BigInt y = point.get_affine_y(); + + SecureVector<byte> bX = BigInt::encode_1363(x, p_bytes); + SecureVector<byte> bY = BigInt::encode_1363(y, p_bytes); + + if(format == PointGFp::UNCOMPRESSED) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 4; + + result.copy(1, bX.begin(), p_bytes); + result.copy(p_bytes+1, bY.begin(), p_bytes); + return result; + } + else if(format == PointGFp::COMPRESSED) + { + SecureVector<byte> result(p_bytes+1); + result[0] = 2; + + result.copy(1, bX.begin(), bX.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else if(format == PointGFp::HYBRID) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 6; + + result.copy(1, bX.begin(), bX.size()); + result.copy(p_bytes+1, bY.begin(), bY.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else + throw Invalid_Argument("illegal point encoding format specification"); + } + +PointGFp OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve) + { + if(os.size() == 1 && os[0] == 0) + return PointGFp(curve); // return zero + + const byte pc = os[0]; + + BigInt x, y; + + if(pc == 2 || pc == 3) + { + //compressed form + x = BigInt::decode(&os[1], os.size() - 1); + + bool yMod2 = ((pc & 0x01) == 1); + y = decompress_point(yMod2, x, curve); + } + else if(pc == 4) + { + // uncompressed form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + } + else if(pc == 6 || pc == 7) + { + // hybrid form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + + bool yMod2 = ((pc & 0x01) == 1); + + if(decompress_point(yMod2, x, curve) != y) + throw Illegal_Point("OS2ECP: Decoding error in hybrid format"); + } + else + throw Invalid_Argument("OS2ECP: Unknown format type"); + + PointGFp result(curve, x, y); + result.check_invariants(); + return result; + } + +} diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h new file mode 100644 index 000000000..0741b5e56 --- /dev/null +++ b/src/math/numbertheory/point_gfp.h @@ -0,0 +1,201 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_POINT_GFP_H__ +#define BOTAN_POINT_GFP_H__ + +#include <botan/curve_gfp.h> +#include <vector> + +namespace Botan { + +struct BOTAN_DLL Illegal_Transformation : public Exception + { + Illegal_Transformation(const std::string& err = + "Requested transformation is not possible") : + Exception(err) {} + }; + +struct BOTAN_DLL Illegal_Point : public Exception + { + Illegal_Point(const std::string& err = "Malformed ECP point detected") : + Exception(err) {} + }; + +/** +* This class represents one point on a curve of GF(p) +*/ +class BOTAN_DLL PointGFp + { + public: + enum Compression_Type { + UNCOMPRESSED = 0, + COMPRESSED = 1, + HYBRID = 2 + }; + + /** + * Construct the point O + * @param curve The base curve + */ + PointGFp(const CurveGFp& curve) : + curve(curve), coord_x(0), coord_y(1), coord_z(0) {} + + /** + * Construct a point given its affine coordinates + * @param curve the base curve + * @param x affine x coordinate + * @param y affine y coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y) : + curve(curve), coord_x(x), coord_y(y), coord_z(1) {} + + /** + * Construct a point given its jacobian projective coordinates + * @param curve the base curve + * @param x jacobian projective x coordinate + * @param y jacobian projective y coordinate + * @param z jacobian projective z coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y, const BigInt& z) : + curve(curve), coord_x(x), coord_y(y), coord_z(z) {} + + //PointGFp(const PointGFp& other) = default; + //PointGFp& operator=(const PointGFp& other) = default; + + /** + * += Operator + * @param rhs the PointGFp to add to the local value + * @result resulting PointGFp + */ + PointGFp& operator+=(const PointGFp& rhs); + + /** + * -= Operator + * @param rhs the PointGFp to subtract from the local value + * @result resulting PointGFp + */ + PointGFp& operator-=(const PointGFp& rhs); + + /** + * *= Operator + * This function turns on the the special reduction multiplication + * itself for fast computation, turns it off again when finished. + * @param scalar the PointGFp to multiply with *this + * @result resulting PointGFp + */ + PointGFp& operator*=(const BigInt& scalar); + + /** + * Negate this point + * @return *this + */ + PointGFp& negate(); + + /** + * Return base curve of this point + * @result the curve over GF(p) of this point + */ + const CurveGFp& get_curve() const { return curve; } + + /** + * get affine x coordinate + * @result affine x coordinate + */ + BigInt get_affine_x() const; + + /** + * get affine y coordinate + * @result affine y coordinate + */ + BigInt get_affine_y() const; + + /** + * get the jacobian projective x coordinate + * @result jacobian projective x coordinate + */ + const BigInt& get_jac_proj_x() const { return coord_x; } + + /** + * get the jacobian projective y coordinate + * @result jacobian projective y coordinate + */ + const BigInt& get_jac_proj_y() const { return coord_y; } + + /** + * get the jacobian projective z coordinate + * @result jacobian projective z coordinate + */ + const BigInt& get_jac_proj_z() const { return coord_z; } + + /** + * Is this the point at infinity? + * @result true, if this point is at infinity, false otherwise. + */ + bool is_zero() const; + + /** + * Checks whether the point is to be found on the underlying curve. + * Throws an Invalid_Point exception in case of detecting that the point + * does not satisfy the curve equation. + * To be used to ensure against fault attacks. + */ + void check_invariants() const; + + /** + * swaps the states of *this and other, does not throw! + * @param other the object to swap values with + */ + void swap(PointGFp& other); + + /** + * Equality operator + */ + bool operator==(const PointGFp& other) const; + private: + /** + * Multiply the point by two + */ + void mult2_in_place(); + + CurveGFp curve; + BigInt coord_x, coord_y, coord_z; + }; + +// relational operators +inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) + { + return !(rhs == lhs); + } + +// arithmetic operators +PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs); + +PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); +PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); + +// encoding and decoding +SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); +PointGFp BOTAN_DLL OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve); + +} + +namespace std { + +template<> +inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) + { x.swap(y); } + +} + +#endif diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp index aa53f1a0e..257ece56e 100644 --- a/src/math/numbertheory/reducer.cpp +++ b/src/math/numbertheory/reducer.cpp @@ -1,12 +1,11 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/reducer.h> -#include <botan/numthry.h> #include <botan/internal/mp_core.h> namespace Botan { @@ -78,20 +77,4 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const return t1; } -/* -* Multiply, followed by a reduction -*/ -BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const - { - return reduce(x * y); - } - -/* -* Square, followed by a reduction -*/ -BigInt Modular_Reducer::square(const BigInt& x) const - { - return reduce(Botan::square(x)); - } - } diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h index d234e0735..80c0f27e1 100644 --- a/src/math/numbertheory/reducer.h +++ b/src/math/numbertheory/reducer.h @@ -1,14 +1,14 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ -#ifndef BOTAN_MODARITH_H__ -#define BOTAN_MODARITH_H__ +#ifndef BOTAN_MODULAR_REDUCER_H__ +#define BOTAN_MODULAR_REDUCER_H__ -#include <botan/bigint.h> +#include <botan/numthry.h> namespace Botan { @@ -18,14 +18,30 @@ namespace Botan { class BOTAN_DLL Modular_Reducer { public: - BigInt multiply(const BigInt&, const BigInt&) const; - BigInt square(const BigInt&) const; - BigInt reduce(const BigInt&) const; + BigInt reduce(const BigInt& x) const; + + /** + * Multiply mod p + */ + BigInt multiply(const BigInt& x, const BigInt& y) const + { return reduce(x * y); } + + /** + * Square mod p + */ + BigInt square(const BigInt& x) const + { return reduce(Botan::square(x)); } + + /** + * Cube mod p + */ + BigInt cube(const BigInt& x) const + { return multiply(x, this->square(x)); } bool initialized() const { return (mod_words != 0); } Modular_Reducer() { mod_words = 0; } - Modular_Reducer(const BigInt&); + Modular_Reducer(const BigInt& mod); private: BigInt modulus, modulus_2, mu; u32bit mod_words, mod2_words, mu_words; |