diff options
author | lloyd <[email protected]> | 2010-02-23 18:15:44 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2010-02-23 18:15:44 +0000 |
commit | cdc5e1aa4761da1a353aa71b9b35cb02bdf9800d (patch) | |
tree | 4f90049fe4421956ee96e68931e342e63e8b3d5b /src | |
parent | 9b3213732ac828e8cf00da95aa3d85fca700372f (diff) |
Remove use of tr1 entirely from gfpmath.
Remove a handful of tests which were based on testing the sharing
aspects, which are gone now; everything is based on value copies.
All tests pass on x86-64 with GCC. Valgrind output looks clean too.
Diffstat (limited to 'src')
-rw-r--r-- | src/math/gfpmath/curve_gfp.cpp | 147 | ||||
-rw-r--r-- | src/math/gfpmath/curve_gfp.h | 63 | ||||
-rw-r--r-- | src/math/gfpmath/gfp_element.cpp | 226 | ||||
-rw-r--r-- | src/math/gfpmath/gfp_element.h | 87 | ||||
-rw-r--r-- | src/math/gfpmath/gfp_modulus.h | 35 | ||||
-rw-r--r-- | src/math/gfpmath/info.txt | 2 | ||||
-rw-r--r-- | src/math/gfpmath/point_gfp.cpp | 571 | ||||
-rw-r--r-- | src/math/gfpmath/point_gfp.h | 78 |
8 files changed, 298 insertions, 911 deletions
diff --git a/src/math/gfpmath/curve_gfp.cpp b/src/math/gfpmath/curve_gfp.cpp index 9a3ffd482..cf687b6ab 100644 --- a/src/math/gfpmath/curve_gfp.cpp +++ b/src/math/gfpmath/curve_gfp.cpp @@ -2,7 +2,7 @@ * Elliptic curves over GF(p) * * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008 Jack Lloyd +* 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -14,147 +14,40 @@ namespace Botan { -void CurveGFp::set_shrd_mod(const std::tr1::shared_ptr<GFpModulus> mod) - { - mp_mod = mod; - mA.turn_off_sp_red_mul();// m.m. is not needed, must be trf. back - mB.turn_off_sp_red_mul();// m.m. is not needed, must be trf. back - //ok, above we destroy any evantually computated montg. mult. values, - // but that won't influence performance in usual applications - mA.set_shrd_mod(mod); - mB.set_shrd_mod(mod); - } - CurveGFp::CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p) - : mA(a), - mB(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()))) - { + if(p != mA.get_p() || p != mB.get_p()) throw Invalid_Argument("could not construct curve: moduli of arguments differ"); - } - std::tr1::shared_ptr<GFpModulus> p_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(p)); - // the above is the creation of the GFpModuls object which will be shared point-wide - // (in the context of a point of course) - set_shrd_mod(p_mod); - } -// copy constructor -CurveGFp::CurveGFp(const CurveGFp& other) - : mA(other.get_a()), - mB(other.get_b()) - { - mp_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(*other.mp_mod)); - assert(mp_mod->p_equal_to(mA.get_p())); - assert(mp_mod->p_equal_to(mB.get_p())); - set_shrd_mod(mp_mod); - if(other.mp_mres_a.get()) - { - mp_mres_a = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_a)); - } - if(other.mp_mres_b.get()) - { - mp_mres_b = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_b)); - } - if(other.mp_mres_one.get()) - { - mp_mres_one = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_one)); - } - - } -// assignment operator -const CurveGFp& CurveGFp::operator=(const CurveGFp& other) - { - // for exception safety... - GFpElement a_tmp = other.mA; - GFpElement b_tmp = other.mB; - mA.swap(a_tmp); - mB.swap(b_tmp); - - std::tr1::shared_ptr<GFpModulus> p_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(*other.mp_mod)); - set_shrd_mod(p_mod); - - // exception safety note: no problem if we have a throw from here on... - if(other.mp_mres_a.get()) - { - mp_mres_a = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_a)); - } - if(other.mp_mres_b.get()) - { - mp_mres_b = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_b)); - } - if(other.mp_mres_one.get()) - { - mp_mres_one = std::tr1::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_one)); - } - return *this; - } - -// getters -const GFpElement& CurveGFp::get_a() const - { - return mA; - } + mres_a.turn_on_sp_red_mul(); + mres_a.get_mres(); -const GFpElement& CurveGFp::get_b() const - { - return mB; - } + mres_b.turn_on_sp_red_mul(); + mres_b.get_mres(); -const BigInt CurveGFp::get_p() const - { - assert(mp_mod.get() != 0); - return mp_mod->get_p(); + 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) { - mA.swap(other.mA); - mB.swap(other.mB); - mp_mod.swap(other.mp_mod); - std::swap(mp_mres_a, other.mp_mres_a); - std::swap(mp_mres_b, other.mp_mres_b); - std::swap(mp_mres_one, other.mp_mres_one); - } - -GFpElement const CurveGFp::get_mres_a() const - { - if(mp_mres_a.get() == 0) - { - mp_mres_a = std::tr1::shared_ptr<GFpElement>(new GFpElement(mA)); - mp_mres_a->turn_on_sp_red_mul(); - mp_mres_a->get_mres(); - } - return GFpElement(*mp_mres_a); - } - -GFpElement const CurveGFp::get_mres_b() const - { - if(mp_mres_b.get() == 0) - { - mp_mres_b = std::tr1::shared_ptr<GFpElement>(new GFpElement(mB)); - mp_mres_b->turn_on_sp_red_mul(); - mp_mres_b->get_mres(); - } - return GFpElement(*mp_mres_b); - } - -std::tr1::shared_ptr<GFpElement const> const CurveGFp::get_mres_one() const - { - if(mp_mres_one.get() == 0) - { - mp_mres_one = std::tr1::shared_ptr<GFpElement>(new GFpElement(mp_mod->get_p(), 1)); - mp_mres_one->turn_on_sp_red_mul(); - mp_mres_one->get_mres(); - } - return mp_mres_one; + 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()); + 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) diff --git a/src/math/gfpmath/curve_gfp.h b/src/math/gfpmath/curve_gfp.h index 53bbc1f3c..5641e80d1 100644 --- a/src/math/gfpmath/curve_gfp.h +++ b/src/math/gfpmath/curve_gfp.h @@ -2,6 +2,7 @@ * Elliptic curves over GF(p) * * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -9,7 +10,6 @@ #ifndef BOTAN_GFP_CURVE_H__ #define BOTAN_GFP_CURVE_H__ -#include <botan/bigint.h> #include <botan/gfp_element.h> #include <iosfwd> @@ -31,28 +31,8 @@ class BOTAN_DLL CurveGFp CurveGFp(const GFpElement& a, const GFpElement& b, const BigInt& p); - /** - * Copy constructor - * @param other The curve to clone - */ - CurveGFp(const CurveGFp& other); - - /** - * Assignment operator - * @param other The curve to use as source for the assignment - */ - const CurveGFp& operator=(const CurveGFp& other); - - /** - * Set the shared GFpModulus object. - * Warning: do not use this function unless you know in detail how - * the sharing of values - * in the various EC related objects works. - * Do NOT spread pointers to a GFpModulus over different threads! - * @param mod a shared pointer to a GFpModulus object suitable for - * *this. - */ - void set_shrd_mod(const std::tr1::shared_ptr<GFpModulus> mod); + // CurveGFp(const CurveGFp& other) = default; + // CurveGFp& operator=(const CurveGFp& other) = default; // getters @@ -60,13 +40,13 @@ class BOTAN_DLL CurveGFp * Get coefficient a * @result coefficient a */ - const GFpElement& get_a() const; + const GFpElement& get_a() const { return mA; } /** * Get coefficient b * @result coefficient b */ - const GFpElement& get_b() const; + const GFpElement& get_b() const { return mB; } /** * Get the GFpElement coefficient a transformed @@ -75,7 +55,7 @@ class BOTAN_DLL CurveGFp * function. * @result the coefficient a, transformed to its m-residue */ - GFpElement const get_mres_a() const; + const GFpElement& get_mres_a() const { return mres_a; } /** * Get the GFpElement coefficient b transformed @@ -84,8 +64,7 @@ class BOTAN_DLL CurveGFp * function. * @result the coefficient b, transformed to its m-residue */ - GFpElement const get_mres_b() const; - + const GFpElement& get_mres_b() const { return mres_b; } /** * Get the GFpElement 1 transformed @@ -94,31 +73,13 @@ class BOTAN_DLL CurveGFp * function. * @result the GFpElement 1, transformed to its m-residue */ - std::tr1::shared_ptr<GFpElement const> const get_mres_one() const; + 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 */ - BigInt const get_p() const; - /*inline std::tr1::shared_ptr<BigInt> const get_ptr_p() const - { - return mp_p; - }*/ - - /** - * Retrieve a shared pointer to the curves GFpModulus object for - * efficient storage and computation of montgomery multiplication - * related data members and functions. Warning: do not use this - * function unless you know in detail how the sharing of values - * in the various EC related objects works. Do NOT spread - * pointers to a GFpModulus over different threads! - * @result a shared pointer to a GFpModulus object - */ - inline std::tr1::shared_ptr<GFpModulus> const get_ptr_mod() const - { - return mp_mod; - } + const BigInt& get_p() const { return modulus.get_p(); } /** * swaps the states of *this and other, does not throw @@ -127,12 +88,10 @@ class BOTAN_DLL CurveGFp void swap(CurveGFp& other); private: - std::tr1::shared_ptr<GFpModulus> mp_mod; + GFpModulus modulus; GFpElement mA; GFpElement mB; - mutable std::tr1::shared_ptr<GFpElement> mp_mres_a; - mutable std::tr1::shared_ptr<GFpElement> mp_mres_b; - mutable std::tr1::shared_ptr<GFpElement> mp_mres_one; + GFpElement mres_a, mres_b, mres_one; }; // relational operators diff --git a/src/math/gfpmath/gfp_element.cpp b/src/math/gfpmath/gfp_element.cpp index c76a4d020..7e660213e 100644 --- a/src/math/gfpmath/gfp_element.cpp +++ b/src/math/gfpmath/gfp_element.cpp @@ -166,39 +166,12 @@ BigInt montg_trf_to_ordres(const BigInt& m_res, const BigInt& m, const BigInt& r } GFpElement::GFpElement(const BigInt& p, const BigInt& value, bool use_montgm) - : mp_mod(), - m_value(value %p), - m_use_montgm(use_montgm), - m_is_trf(false) - { - assert(mp_mod.get() == 0); - mp_mod = std::tr1::shared_ptr<GFpModulus>(new GFpModulus(p)); - assert(mp_mod->get_p_dash() == 0); + : modulus(p), m_value(value %p), m_use_montgm(use_montgm), m_is_trf(false) + { if(m_use_montgm) ensure_montgm_precomp(); } -GFpElement::GFpElement(std::tr1::shared_ptr<GFpModulus> const mod, const BigInt& value, bool use_montgm) - : mp_mod(), - m_value(value % mod->get_p()), - m_use_montgm(use_montgm), - m_is_trf(false) - { - assert(mp_mod.get() == 0); - mp_mod = mod; - } - -GFpElement::GFpElement(const GFpElement& other) - : m_value(other.m_value), - m_use_montgm(other.m_use_montgm), - m_is_trf(other.m_is_trf) - - { - //creates an independent copy - assert((other.m_is_trf && other.m_use_montgm) || !other.m_is_trf); - mp_mod.reset(new GFpModulus(*other.mp_mod)); // copy-ctor of GFpModulus - } - void GFpElement::turn_on_sp_red_mul() const { ensure_montgm_precomp(); @@ -218,28 +191,23 @@ void GFpElement::turn_off_sp_red_mul() const void GFpElement::ensure_montgm_precomp() const { - if((!mp_mod->get_r().is_zero()) && (!mp_mod->get_r_inv().is_zero()) && (!mp_mod->get_p_dash().is_zero())) + 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(mp_mod->get_p())); + BigInt tmp_r(montgm_calc_r_oddmod(modulus.get_p())); - BigInt tmp_r_inv(inverse_mod(tmp_r, mp_mod->get_p())); + BigInt tmp_r_inv(inverse_mod(tmp_r, modulus.get_p())); - BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, mp_mod->get_p(), tmp_r_inv)); + BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, modulus.get_p(), tmp_r_inv)); - mp_mod->reset_values(tmp_p_dash, tmp_r, tmp_r_inv); + modulus.reset_values(tmp_p_dash, tmp_r, tmp_r_inv); } } -void GFpElement::set_shrd_mod(std::tr1::shared_ptr<GFpModulus> const p_mod) - { - mp_mod = p_mod; - } - void GFpElement::trf_to_mres() const { if(!m_use_montgm) @@ -247,27 +215,27 @@ void GFpElement::trf_to_mres() const throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); } assert(m_is_trf == false); - assert(!mp_mod->get_r_inv().is_zero()); - assert(!mp_mod->get_p_dash().is_zero()); - m_value = montg_trf_to_mres(m_value, mp_mod->get_r(), mp_mod->get_p()); + 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, mp_mod->get_p(), mp_mod->get_r_inv()); + 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.mp_mod->get_p() == rhs.mp_mod->get_p()); + assert(lhs.modulus.get_p() == rhs.modulus.get_p()); if(lhs.m_use_montgm && rhs.m_use_montgm) { - assert(rhs.mp_mod->get_p_dash() == lhs.mp_mod->get_p_dash()); - assert(rhs.mp_mod->get_r() == lhs.mp_mod->get_r()); - assert(rhs.mp_mod->get_r_inv() == lhs.mp_mod->get_r_inv()); + 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; @@ -317,7 +285,7 @@ bool GFpElement::is_trf_to_mres() const const BigInt& GFpElement::get_p() const { - return (mp_mod->get_p()); + return (modulus.get_p()); } const BigInt& GFpElement::get_value() const @@ -347,105 +315,17 @@ const BigInt& GFpElement::get_mres() const return m_value; } -const GFpElement& GFpElement::operator=(const GFpElement& other) - { - m_value.grow_reg(other.m_value.size()); // grow first for exception safety - - //m_value = other.m_value; - - // m_use_montgm = other.m_use_montgm; - // m_is_trf = other.m_is_trf; - // we want to keep the member pointers, which might be part of a "sharing group" - // but we may not simply overwrite the BigInt values with those of the argument!! - // if ours already contains precomputations, it would be hazardous to - // set them back to zero. - // thus we first check for equality of the moduli, - // then whether either of the two objects already contains - // precomputed values. - - // we also deal with the case were the pointers themsevles are equal: - if(mp_mod.get() == other.mp_mod.get()) - { - // everything ok, we are in the same sharing group anyway, nothing to do - m_value = other.m_value; // cannot throw - m_use_montgm = other.m_use_montgm; - m_is_trf = other.m_is_trf; - return *this; - } - if(mp_mod->get_p() != other.mp_mod->get_p()) - { - // the moduli are different, this is a special case - // which will not occur in usual applications, - // so we don´t hesitate to simply create new objects - // (we do want to create an independent copy) - mp_mod.reset(new GFpModulus(*other.mp_mod)); // this could throw, - // and because of this - // we haven't modified - // anything so far - m_value = other.m_value; // can't throw - m_use_montgm = other.m_use_montgm; - m_is_trf = other.m_is_trf; - return *this; - } - // exception safety note: from now on we are on the safe - // side with respect to the modulus, - // so we can assign the value now: - m_value = other.m_value; - m_use_montgm = other.m_use_montgm; - m_is_trf = other.m_is_trf; - // the moduli are equal, but we deal with different sharing groups. - // we will NOT fuse the sharing goups - // and we will NOT reset already precomputed values - if(mp_mod->has_precomputations()) - { - // our own sharing group already has precomputed values, - // so nothing to do. - return *this; - } - else - { - // let´s see whether the argument has something for us... - if(other.mp_mod->has_precomputations()) - { - // fetch them for our sharing group - // exc. safety note: grow first - - mp_mod->reset_values(other.mp_mod->get_p_dash(), - other.mp_mod->get_r(), - other.mp_mod->get_r_inv()); - - return *this; - } - } - // our precomputations aren´t set, the arguments neither, - // so we let them alone - return *this; - } - -void GFpElement::share_assign(const GFpElement& other) - { - assert((other.m_is_trf && other.m_use_montgm) || !other.m_is_trf); - - // use grow_to to make it exc safe - m_value.grow_reg(other.m_value.size()); - m_value = other.m_value; - - m_use_montgm = other.m_use_montgm; - m_is_trf = other.m_is_trf; - mp_mod = other.mp_mod; // cannot throw - } - GFpElement& GFpElement::operator+=(const GFpElement& rhs) { GFpElement::align_operands_res(*this, rhs); - workspace = m_value; + BigInt workspace = m_value; workspace += rhs.m_value; - if(workspace >= mp_mod->get_p()) - workspace -= mp_mod->get_p(); + if(workspace >= modulus.get_p()) + workspace -= modulus.get_p(); m_value = workspace; - assert(m_value < mp_mod->get_p()); + assert(m_value < modulus.get_p()); assert(m_value >= 0); return *this; @@ -455,39 +335,39 @@ GFpElement& GFpElement::operator-=(const GFpElement& rhs) { GFpElement::align_operands_res(*this, rhs); - workspace = m_value; + BigInt workspace = m_value; workspace -= rhs.m_value; if(workspace.is_negative()) - workspace += mp_mod->get_p(); + workspace += modulus.get_p(); m_value = workspace; - assert(m_value < mp_mod->get_p()); + assert(m_value < modulus.get_p()); assert(m_value >= 0); return *this; } GFpElement& GFpElement::operator*= (u32bit rhs) { - workspace = m_value; + BigInt workspace = m_value; workspace *= rhs; - workspace %= mp_mod->get_p(); + workspace %= modulus.get_p(); m_value = workspace; return *this; } GFpElement& GFpElement::operator*=(const GFpElement& rhs) { - assert(rhs.mp_mod->get_p() == mp_mod->get_p()); + 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.mp_mod->get_p() == mp_mod->get_p()); // is montgm. mult is on, then precomps must be there - assert(rhs.mp_mod->get_p_dash() == mp_mod->get_p_dash()); - assert(rhs.mp_mod->get_r() == mp_mod->get_r()); + 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(); @@ -496,8 +376,8 @@ GFpElement& GFpElement::operator*=(const GFpElement& rhs) { rhs.trf_to_mres(); } - workspace = m_value; - montg_mult(m_value, workspace, rhs.m_value, mp_mod->get_p(), mp_mod->get_p_dash(), mp_mod->get_r()); + 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 { @@ -512,9 +392,9 @@ GFpElement& GFpElement::operator*=(const GFpElement& rhs) rhs.trf_to_ordres(); } - workspace = m_value; + BigInt workspace = m_value; workspace *= rhs.m_value; - workspace %= mp_mod->get_p(); + workspace %= modulus.get_p(); m_value = workspace; } return *this; @@ -524,18 +404,17 @@ 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)); - // (internal note: see C86) + 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(); - workspace = m_value; - workspace *= rhs_ordres.get_value(); - workspace %= mp_mod->get_p(); + BigInt workspace = m_value; + workspace *= rhs_ordres.get_value(); + workspace %= modulus.get_p(); m_value = workspace; - } else { @@ -554,30 +433,31 @@ bool GFpElement::is_zero() GFpElement& GFpElement::inverse_in_place() { - m_value = inverse_mod(m_value, mp_mod->get_p()); + m_value = inverse_mod(m_value, modulus.get_p()); + if(m_is_trf) { assert(m_use_montgm); - m_value *= mp_mod->get_r(); - m_value *= mp_mod->get_r(); - m_value %= mp_mod->get_p(); + m_value *= modulus.get_r(); + m_value *= modulus.get_r(); + m_value %= modulus.get_p(); } - assert(m_value <= mp_mod->get_p()); + assert(m_value <= modulus.get_p()); return *this; } GFpElement& GFpElement::negate() { - m_value = mp_mod->get_p() - m_value; - assert(m_value <= mp_mod->get_p()); + m_value = modulus.get_p() - m_value; + assert(m_value <= modulus.get_p()); return *this; } void GFpElement::swap(GFpElement& other) { - m_value.swap(other.m_value); - mp_mod.swap(other.mp_mod); + 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); } @@ -589,15 +469,9 @@ std::ostream& operator<<(std::ostream& output, const GFpElement& elem) bool operator==(const GFpElement& lhs, const GFpElement& rhs) { - // for effeciency reasons we firstly check whether - //the modulus pointers are different in the first place: - if(lhs.get_ptr_mod() != rhs.get_ptr_mod()) - { - if(lhs.get_p() != rhs.get_p()) - { - return false; - } - } + 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); diff --git a/src/math/gfpmath/gfp_element.h b/src/math/gfpmath/gfp_element.h index 84009ef12..fd76516b5 100644 --- a/src/math/gfpmath/gfp_element.h +++ b/src/math/gfpmath/gfp_element.h @@ -2,6 +2,7 @@ * 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 */ @@ -13,14 +14,6 @@ #include <botan/gfp_modulus.h> #include <iosfwd> -#if defined(BOTAN_USE_STD_TR1) - #include <tr1/memory> -#elif defined(BOTAN_USE_BOOST_TR1) - #include <boost/tr1/memory.hpp> -#else - #error "Please choose a TR1 implementation in build.h" -#endif - namespace Botan { struct BOTAN_DLL Illegal_Transformation : public Exception @@ -45,47 +38,11 @@ class BOTAN_DLL GFpElement * @param value the element value * @param use_montgm whether this object will use Montgomery multiplication */ - explicit GFpElement (const BigInt& p, const BigInt& value, bool use_montgm = false); - - - /** construct an element of GF(p) with the given value (defaults - * to 0). use_montg defaults to false and determines wether - * montgomery multiplications will be use when applying operators - * '*' , '*='. Use this constructor for efficient use of - * Montgomery multiplication in a context with a fixed a modulus. - * Warning: do not use this function unless you know in detail - * about the implications of using the shared GFpModulus objects! - * @param mod shared pointer to the GFpModulus to be shared - * @param value the element value - * @param use_montgm whether this object will use Montgomery multiplication - */ - explicit GFpElement(std::tr1::shared_ptr<GFpModulus> const mod, - const BigInt& value, bool use_mongm = false); - - /** - * Copy constructor - * @param other The element to clone - */ - GFpElement(const GFpElement& other); - - /** - * Assignment operator. - * makes *this a totally independent object - * (gives *this independent modulus specific values). + GFpElement(const BigInt& p, const BigInt& value, bool use_montgm = false); - * @param other The element to assign to our object - */ - const GFpElement& operator=(const GFpElement& other); + // GFpElement(const GFpElement& other) = default; - /** - * Works like the assignment operator, but lets - * *this share the modulus dependend value with other. - * Warning: do not use this function unless you know in detail about - * the implications of using - * the shared GFpModulus objects! - * @param other The element to assign to our object - */ - void share_assign(const GFpElement& other); + // const GFpElement& operator=(const GFpElement& other) = default; /** * Switch Montgomery multiplcation optimizations ON @@ -129,7 +86,7 @@ class BOTAN_DLL GFpElement * @param rhs the value to multiply with the local value * @result *this */ - GFpElement& operator*= (u32bit rhs); + GFpElement& operator*=(u32bit rhs); /** * Negate internal value(*this *= -1 ) @@ -164,28 +121,6 @@ class BOTAN_DLL GFpElement const BigInt& get_value() const; /** - * Returns the shared pointer to the GFpModulus of *this. - * Warning: do not use this function unless you know in detail about - * the implications of using - * the shared GFpModulus objects! - * @result the shared pointer to the GFpModulus of *this - */ - inline std::tr1::shared_ptr<GFpModulus> const get_ptr_mod() const - { - return mp_mod; - } - - - /** - * Sets the shared pointer to the GFpModulus of *this. - * Warning: do not use this function unless you know in detail about - * the implications of using - * the shared GFpModulus objects! - * @param mod a shared pointer to a GFpModulus that will be held in *this - */ - void set_shrd_mod(std::tr1::shared_ptr<GFpModulus> const mod); - - /** * Tells whether this GFpElement is currently transformed to it´ m-residue, * i.e. in the form x_bar = x * r mod m. * @result true if it is currently transformed to it´s m-residue. @@ -233,16 +168,12 @@ class BOTAN_DLL GFpElement void trf_to_mres() const; void trf_to_ordres() const; - std::tr1::shared_ptr<GFpModulus> mp_mod; + mutable GFpModulus modulus; mutable BigInt m_value; // ordinary residue or m-residue respectively - mutable BigInt workspace; // data members for montgomery multiplication mutable bool m_use_montgm; - //mutable BigInt m_mres; - // this bool tells use whether the m_mres carries - // the actual value (in this case mValue doesn´t) - mutable bool m_is_trf; + mutable bool m_is_trf; // if m_value is montgomery }; // relational operators @@ -259,8 +190,8 @@ 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); +GFpElement BOTAN_DLL operator*(const GFpElement& lhs, u32bit rhs); +GFpElement BOTAN_DLL operator*(u32bit rhs, const GFpElement& lhs); /** diff --git a/src/math/gfpmath/gfp_modulus.h b/src/math/gfpmath/gfp_modulus.h index ace42b27d..fcdd13ee1 100644 --- a/src/math/gfpmath/gfp_modulus.h +++ b/src/math/gfpmath/gfp_modulus.h @@ -22,22 +22,26 @@ class GFpElement; class BOTAN_DLL GFpModulus { public: + /** * Construct a GF(P)-Modulus from a BigInt */ - GFpModulus(BigInt p) + 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. */ - inline bool has_precomputations() const + bool has_precomputations() const { return(!m_p_dash.is_zero() && !m_r.is_zero() && !m_r_inv.is_zero()); } @@ -46,12 +50,12 @@ class BOTAN_DLL GFpModulus * Swaps this with another GFpModulus, does not throw. * @param other the GFpModulus to swap *this with. */ - inline void swap(GFpModulus& other) + void swap(GFpModulus& other) { - m_p.swap(other.m_p); - m_p_dash.swap(other.m_p_dash); - m_r.swap(other.m_r); - m_r_inv.swap(other.m_r_inv); + 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); } /** @@ -59,7 +63,7 @@ class BOTAN_DLL GFpModulus * @param mod the modulus to compare this with * @result true if the modulus of *this and the argument are equal. */ - inline bool p_equal_to(const BigInt& mod) const + bool p_equal_to(const BigInt& mod) const { return (m_p == mod); } @@ -68,7 +72,7 @@ class BOTAN_DLL GFpModulus * Return the modulus of this GFpModulus. * @result the modulus of *this. */ - inline const BigInt& get_p() const + const BigInt& get_p() const { return m_p; } @@ -79,7 +83,7 @@ class BOTAN_DLL GFpModulus * performed! * @result r */ - inline const BigInt& get_r() const + const BigInt& get_r() const { return m_r; } @@ -90,7 +94,7 @@ class BOTAN_DLL GFpModulus * performed! * @result r^{-1} */ - inline const BigInt& get_r_inv() const + const BigInt& get_r_inv() const { return m_r_inv; } @@ -101,11 +105,10 @@ class BOTAN_DLL GFpModulus * performed! * @result p' */ - inline const BigInt& get_p_dash() const + const BigInt& get_p_dash() const { return m_p_dash; } - // default cp-ctor, op= are fine void reset_values(const BigInt& new_p_dash, const BigInt& new_r, @@ -118,9 +121,9 @@ class BOTAN_DLL GFpModulus private: BigInt m_p; // the modulus itself - mutable BigInt m_p_dash; - mutable BigInt m_r; - mutable BigInt m_r_inv; + BigInt m_p_dash; + BigInt m_r; + BigInt m_r_inv; }; } diff --git a/src/math/gfpmath/info.txt b/src/math/gfpmath/info.txt index a02dbc044..b7b430805 100644 --- a/src/math/gfpmath/info.txt +++ b/src/math/gfpmath/info.txt @@ -1,7 +1,5 @@ define BIGINT_GFP -uses_tr1 yes - <header:public> curve_gfp.h gfp_element.h diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp index 4203a3db3..c57ceebba 100644 --- a/src/math/gfpmath/point_gfp.cpp +++ b/src/math/gfpmath/point_gfp.cpp @@ -13,87 +13,50 @@ 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), - mZpow2(curve.get_p(),0), - mZpow3(curve.get_p(),0), - mAZpow4(curve.get_p(),0), - mZpow2_set(false), - mZpow3_set(false), - mAZpow4_set(false) +PointGFp::PointGFp(const CurveGFp& curve) : + mC(curve), + mX(curve.get_p(), 0), + mY(curve.get_p(), 1), + mZ(curve.get_p(), 0), + mZpow2(curve.get_p(),0), + mZpow3(curve.get_p(),0), + mAZpow4(curve.get_p(),0), + mZpow2_set(false), + mZpow3_set(false), + mAZpow4_set(false) { - // first set the point wide pointer - - set_shrd_mod(mC.get_ptr_mod()); - } // 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), - mZpow2(curve.get_p(),0), - mZpow3(curve.get_p(),0), - mAZpow4(curve.get_p(),0), - mZpow2_set(false), - mZpow3_set(false), - mAZpow4_set(false) - { - set_shrd_mod(mC.get_ptr_mod()); - } -PointGFp::PointGFp ( const CurveGFp& curve, const GFpElement& x, - const GFpElement& y ) - :mC(curve), - mX(x), - mY(y), - mZ(curve.get_p(),1), - mZpow2(curve.get_p(),0), - mZpow3(curve.get_p(),0), - mAZpow4(curve.get_p(),0), - mZpow2_set(false), - mZpow3_set(false), - mAZpow4_set(false) - { - set_shrd_mod(mC.get_ptr_mod()); - } - -// copy constructor -PointGFp::PointGFp(const PointGFp& other) - : mC(other.mC), - mX(other.mX), - mY(other.mY), - mZ(other.mZ), - mZpow2(other.mZpow2), - mZpow3(other.mZpow3), - mAZpow4(other.mAZpow4), - mZpow2_set(other.mZpow2_set), - mZpow3_set(other.mZpow3_set), - mAZpow4_set(other.mAZpow4_set) + const GFpElement& y, const GFpElement& z) : + mC(curve), + mX(x), + mY(y), + mZ(z), + mZpow2(curve.get_p(),0), + mZpow3(curve.get_p(),0), + mAZpow4(curve.get_p(),0), + mZpow2_set(false), + mZpow3_set(false), + mAZpow4_set(false) + { + } + +PointGFp::PointGFp(const CurveGFp& curve, + const GFpElement& x, + const GFpElement& y) : + mC(curve), + mX(x), + mY(y), + mZ(curve.get_p(),1), + mZpow2(curve.get_p(),0), + mZpow3(curve.get_p(),0), + mAZpow4(curve.get_p(),0), + mZpow2_set(false), + mZpow3_set(false), + mAZpow4_set(false) { - set_shrd_mod(mC.get_ptr_mod()); - } - -// assignment operator -const PointGFp& PointGFp::operator=(PointGFp const& other) - { - mC = other.get_curve(); - mX = other.get_jac_proj_x(); - mY = other.get_jac_proj_y(); - mZ = other.get_jac_proj_z(); - mZpow2 = GFpElement(other.mZpow2); - mZpow3 = GFpElement(other.mZpow3); - mAZpow4 = GFpElement(other.mAZpow4); - mZpow2_set = other.mZpow2_set; - mZpow3_set = other.mZpow3_set; - mAZpow4_set = other.mAZpow4_set; - set_shrd_mod(mC.get_ptr_mod()); - return *this; } const PointGFp& PointGFp::assign_within_same_curve(PointGFp const& other) @@ -108,64 +71,25 @@ const PointGFp& PointGFp::assign_within_same_curve(PointGFp const& other) return *this; } -void PointGFp::set_shrd_mod(std::tr1::shared_ptr<GFpModulus> p_mod) - { - mX.set_shrd_mod(p_mod); - mY.set_shrd_mod(p_mod); - mZ.set_shrd_mod(p_mod); - mZpow2.set_shrd_mod(p_mod); - mZpow3.set_shrd_mod(p_mod); - mAZpow4.set_shrd_mod(p_mod); - } - -void PointGFp::ensure_worksp() const - { - if (mp_worksp_gfp_el.get() != 0) - { - if ((*mp_worksp_gfp_el).size() == GFPEL_WKSP_SIZE) - { - return; - } - else - { - throw Invalid_State("encountered incorrect size for PointGFp´s GFpElement workspace"); - } - } - - mp_worksp_gfp_el = std::tr1::shared_ptr<std::vector<GFpElement> >(new std::vector<GFpElement>); - mp_worksp_gfp_el->reserve(9); - for (u32bit i=0; i<GFPEL_WKSP_SIZE; i++) - { - mp_worksp_gfp_el->push_back(GFpElement(1,0)); - - } - } - // arithmetic operators PointGFp& PointGFp::operator+=(const PointGFp& rhs) { - if (is_zero()) + if(is_zero()) { *this = rhs; return *this; } - if (rhs.is_zero()) + if(rhs.is_zero()) { return *this; } - ensure_worksp(); - if (rhs.mZ == *(mC.get_mres_one())) - { - //U1 = mX; - (*mp_worksp_gfp_el)[0].share_assign(mX); + GFpElement U1 = mX; + GFpElement S1 = mY; - //S1 = mY; - (*mp_worksp_gfp_el)[2].share_assign(mY); - } - else + if(rhs.mZ != mC.get_mres_one()) { - if ((!rhs.mZpow2_set) || (!rhs.mZpow3_set)) + if((!rhs.mZpow2_set) || (!rhs.mZpow3_set)) { rhs.mZpow2 = rhs.mZ; rhs.mZpow2 *= rhs.mZ; @@ -175,26 +99,17 @@ PointGFp& PointGFp::operator+=(const PointGFp& rhs) rhs.mZpow2_set = true; rhs.mZpow3_set = true; } - //U1 = mX * rhs.mZpow2; - (*mp_worksp_gfp_el)[0].share_assign(mX); - (*mp_worksp_gfp_el)[0] *= rhs.mZpow2; - - //S1 = mY * rhs.mZpow3; - (*mp_worksp_gfp_el)[2].share_assign(mY); - (*mp_worksp_gfp_el)[2] *= rhs.mZpow3; + U1 *= rhs.mZpow2; + S1 *= rhs.mZpow3; } - if (mZ == *(mC.get_mres_one())) - { - //U2 = rhs.mX; - (*mp_worksp_gfp_el)[1].share_assign(rhs.mX); - //S2 = rhs.mY; - (*mp_worksp_gfp_el)[3].share_assign(rhs.mY); - } - else + GFpElement U2 = rhs.mX; + GFpElement S2 = rhs.mY; + + if(mZ != mC.get_mres_one()) { - if ((!mZpow2_set) || (!mZpow3_set)) + if((!mZpow2_set) || (!mZpow3_set)) { // precomputation can´t be used, because *this changes anyway mZpow2 = mZ; @@ -203,105 +118,60 @@ PointGFp& PointGFp::operator+=(const PointGFp& rhs) mZpow3 = mZpow2; mZpow3 *= mZ; } - //U2 = rhs.mX * mZpow2; - (*mp_worksp_gfp_el)[1].share_assign(rhs.mX); - (*mp_worksp_gfp_el)[1] *= mZpow2; - - //S2 = rhs.mY * mZpow3; - (*mp_worksp_gfp_el)[3].share_assign(rhs.mY); - (*mp_worksp_gfp_el)[3] *= mZpow3; + U2 *= mZpow2; + S2 *= mZpow3; } - //GFpElement H(U2 - U1); - - (*mp_worksp_gfp_el)[4].share_assign((*mp_worksp_gfp_el)[1]); - (*mp_worksp_gfp_el)[4] -= (*mp_worksp_gfp_el)[0]; - //GFpElement r(S2 - S1); - (*mp_worksp_gfp_el)[5].share_assign((*mp_worksp_gfp_el)[3]); - (*mp_worksp_gfp_el)[5] -= (*mp_worksp_gfp_el)[2]; - - //if(H.is_zero()) - if ((*mp_worksp_gfp_el)[4].is_zero()) + GFpElement H(U2 - U1); + GFpElement r(S2 - S1); + if(H.is_zero()) { - if ((*mp_worksp_gfp_el)[5].is_zero()) - + if(r.is_zero()) { mult2_in_place(); return *this; } + *this = PointGFp(mC); // setting myself to zero return *this; } - //U2 = H * H; - (*mp_worksp_gfp_el)[1].share_assign((*mp_worksp_gfp_el)[4]); - (*mp_worksp_gfp_el)[1] *= (*mp_worksp_gfp_el)[4]; + U2 = H * H; - //S2 = U2 * H; - (*mp_worksp_gfp_el)[3].share_assign((*mp_worksp_gfp_el)[1]); - (*mp_worksp_gfp_el)[3] *= (*mp_worksp_gfp_el)[4]; + S2 = U2 * H; - //U2 *= U1; - (*mp_worksp_gfp_el)[1] *= (*mp_worksp_gfp_el)[0]; + U2 *= U1; - //GFpElement x(r*r - S2 - (U2+U2)); - (*mp_worksp_gfp_el)[6].share_assign((*mp_worksp_gfp_el)[5]); - (*mp_worksp_gfp_el)[6] *= (*mp_worksp_gfp_el)[5]; - (*mp_worksp_gfp_el)[6] -= (*mp_worksp_gfp_el)[3]; - (*mp_worksp_gfp_el)[6] -= (*mp_worksp_gfp_el)[1]; - (*mp_worksp_gfp_el)[6] -= (*mp_worksp_gfp_el)[1]; + GFpElement x(r*r - S2 - (U2+U2)); - //GFpElement z(S1 * S2); - (*mp_worksp_gfp_el)[8].share_assign((*mp_worksp_gfp_el)[2]); - (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[3]; + GFpElement z(S1 * S2); - //GFpElement y(r * (U2-x) - z); - (*mp_worksp_gfp_el)[7].share_assign((*mp_worksp_gfp_el)[1]); - (*mp_worksp_gfp_el)[7] -= (*mp_worksp_gfp_el)[6]; - (*mp_worksp_gfp_el)[7] *= (*mp_worksp_gfp_el)[5]; - (*mp_worksp_gfp_el)[7] -= (*mp_worksp_gfp_el)[8]; + GFpElement y(r * (U2-x) - z); - if (mZ == *(mC.get_mres_one())) + if(mZ == mC.get_mres_one()) { - if (rhs.mZ != *(mC.get_mres_one())) - { - //z = rhs.mZ * H; - (*mp_worksp_gfp_el)[8].share_assign(rhs.mZ); - (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[4]; - } + if(rhs.mZ != mC.get_mres_one()) + z = rhs.mZ * H; else - { - //z = H; - (*mp_worksp_gfp_el)[8].share_assign((*mp_worksp_gfp_el)[4]); - } + z = H; } - else if (rhs.mZ != *(mC.get_mres_one())) + else if(rhs.mZ != mC.get_mres_one()) { - //U1 = mZ * rhs.mZ; - (*mp_worksp_gfp_el)[0].share_assign(mZ); - (*mp_worksp_gfp_el)[0] *= rhs.mZ; - - //z = U1 * H; - (*mp_worksp_gfp_el)[8].share_assign((*mp_worksp_gfp_el)[0]); - (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[4]; - + U1 = mZ * rhs.mZ; + z = U1 * H; } else - { - //z = mZ * H; - (*mp_worksp_gfp_el)[8].share_assign(mZ); - (*mp_worksp_gfp_el)[8] *= (*mp_worksp_gfp_el)[4]; + z = mZ * H; - } mZpow2_set = false; mZpow3_set = false; mAZpow4_set = false; - mX = (*mp_worksp_gfp_el)[6]; - mY = (*mp_worksp_gfp_el)[7]; - mZ = (*mp_worksp_gfp_el)[8]; + mX = x; + mY = y; + mZ = z; return *this; @@ -310,7 +180,7 @@ PointGFp& PointGFp::operator-=(const PointGFp& rhs) { PointGFp minus_rhs = PointGFp(rhs).negate(); - if (is_zero()) + if(is_zero()) { *this = minus_rhs; } @@ -336,23 +206,22 @@ PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, // use montgomery mult. in this operation this->turn_on_sp_red_mul(); - std::tr1::shared_ptr<PointGFp> H(new PointGFp(this->mC)); - std::tr1::shared_ptr<PointGFp> tmp; // used for AADA + PointGFp H(mC); PointGFp P(*this); BigInt m(scalar); - if (m < BigInt(0)) + if(m < BigInt(0)) { m = -m; P.negate(); } - if (P.is_zero() || (m == BigInt(0))) + if(P.is_zero() || (m == BigInt(0))) { - *this = *H; + *this = H; return *this; } - if (m == BigInt(1)) + if(m == BigInt(1)) { return *this; } @@ -378,7 +247,7 @@ PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, // use randomized exponent #ifdef TA_COLL_T static BigInt r_randexp; - if (new_rand) + if(new_rand) { r_randexp = random_integer(rand_r_bit_len); } @@ -405,23 +274,24 @@ PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, #endif // CM_RAND_EXP // determine mul_bits... -#if (CM_AADA == 1 && CM_RAND_EXP != 1) +#if(CM_AADA == 1 && CM_RAND_EXP != 1) mul_bits = max_secr_bits; #endif // CM_AADA without CM_RAND_EXP //assert(mul_bits != 0); + mult_loop(mul_bits-1, m, H, P); - H = mult_loop(mul_bits-1, m, H, tmp, P); - - if (!H->is_zero()) // cannot convert if H == O + if(!H.is_zero()) // cannot convert if H == O { - *this = H->get_z_to_one(); - }else + *this = H.get_z_to_one(); + } + else { - *this = *H; + *this = H; } + mX.turn_off_sp_red_mul(); mY.turn_off_sp_red_mul(); mZ.turn_off_sp_red_mul(); @@ -439,34 +309,34 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar) PointGFp P(*this); P.turn_on_sp_red_mul(); BigInt m(scalar); - if (m < BigInt(0)) + if(m < BigInt(0)) { m = -m; P.negate(); } - if (P.is_zero() || (m == BigInt(0))) + if(P.is_zero() || (m == BigInt(0))) { *this = H; return *this; } - if (m == BigInt(1)) + if(m == BigInt(1)) { //*this == P already return *this; } const int l = m.bits() - 1; - for (int i=l; i >=0; i--) + for(int i=l; i >=0; i--) { H.mult2_in_place(); - if (m.get_bit(i)) + if(m.get_bit(i)) { H += P; } } - if (!H.is_zero()) // cannot convert if H == O + if(!H.is_zero()) // cannot convert if H == O { *this = H.get_z_to_one(); }else @@ -476,60 +346,23 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar) return *this; } -inline std::tr1::shared_ptr<PointGFp> PointGFp::mult_loop(int l, - const BigInt& m, - std::tr1::shared_ptr<PointGFp> H, - std::tr1::shared_ptr<PointGFp> tmp, - const PointGFp& P) +void PointGFp::mult_loop(int l, + const BigInt& m, + PointGFp& H, + const PointGFp& P) { - //assert(l >= (int)m.bits()- 1); - tmp = H; - std::tr1::shared_ptr<PointGFp> to_add(new PointGFp(P)); // we just need some point - // so that we can use op= - // inside the loop - for (int i=l; i >=0; i--) + for(int i=l; i >=0; i--) { - H->mult2_in_place(); - -#ifndef CM_AADA - - if (m.get_bit(i)) - { - *H += P; - } -#else // (CM_AADA is in) - - if (H.get() == to_add.get()) - { - to_add = tmp; // otherwise all pointers might point to the same object - // and we always need two objects to be able to switch around - } - to_add->assign_within_same_curve(*H); - tmp = H; - *tmp += P; // tmp already points to H - - if (m.get_bit(i)) - { - H = tmp; // NOTE: assign the pointer, not the value! - // (so that the operation is fast and thus as difficult - // to detect as possible) - } - else - { - H = to_add; // NOTE: this is necessary, because the assignment - // "*tmp = ..." already changed what H pointed to - - - } -#endif // CM_AADA + H.mult2_in_place(); + if(m.get_bit(i)) + H += P; } - return H; } PointGFp& PointGFp::negate() { - if (!is_zero()) + if(!is_zero()) { mY.negate(); } @@ -539,122 +372,71 @@ PointGFp& PointGFp::negate() // *this *= 2 PointGFp& PointGFp::mult2_in_place() { - if (is_zero()) - { + if(is_zero()) return *this; - } - if (mY.is_zero()) + else if(mY.is_zero()) { - *this = PointGFp(mC); // setting myself to zero return *this; } - ensure_worksp(); - (*mp_worksp_gfp_el)[0].share_assign(mY); - (*mp_worksp_gfp_el)[0] *= mY; + GFpElement Y_squared = mY*mY; - //GFpElement S(mX * z); - (*mp_worksp_gfp_el)[1].share_assign(mX); - (*mp_worksp_gfp_el)[1] *= (*mp_worksp_gfp_el)[0]; + GFpElement S = mX * Y_squared; - //GFpElement x(S + S); - (*mp_worksp_gfp_el)[2].share_assign((*mp_worksp_gfp_el)[1]); - (*mp_worksp_gfp_el)[2] += (*mp_worksp_gfp_el)[1]; + GFpElement x = S + S; - //S = x + x; - (*mp_worksp_gfp_el)[1].share_assign((*mp_worksp_gfp_el)[2]); - (*mp_worksp_gfp_el)[1] += (*mp_worksp_gfp_el)[2]; + S = x + x; - if (!mAZpow4_set) + if(!mAZpow4_set) { - if (mZ == *(mC.get_mres_one())) + if(mZ == mC.get_mres_one()) { mAZpow4 = mC.get_mres_a(); mAZpow4_set = true; } else { - if (!mZpow2_set) + if(!mZpow2_set) { mZpow2 = mZ; mZpow2 *= mZ; mZpow2_set = true; } - //x = mZpow2 * mZpow2; - (*mp_worksp_gfp_el)[2].share_assign(mZpow2); - (*mp_worksp_gfp_el)[2] *= mZpow2; - //mAZpow4 = mC.get_mres_a() * x; - mAZpow4 = mC.get_mres_a(); - mAZpow4 *= (*mp_worksp_gfp_el)[2]; + x = mZpow2 * mZpow2; + mAZpow4 = mC.get_mres_a() * x; } - } - //GFpElement y(mX * mX); - (*mp_worksp_gfp_el)[3].share_assign(mX); - (*mp_worksp_gfp_el)[3] *= mX; - - //GFpElement M(y + y + y + mAZpow4); - (*mp_worksp_gfp_el)[4].share_assign((*mp_worksp_gfp_el)[3]); - (*mp_worksp_gfp_el)[4] += (*mp_worksp_gfp_el)[3]; - (*mp_worksp_gfp_el)[4] += (*mp_worksp_gfp_el)[3]; - (*mp_worksp_gfp_el)[4] += mAZpow4; - - //x = M * M - (S+S); - (*mp_worksp_gfp_el)[2].share_assign((*mp_worksp_gfp_el)[4]); - (*mp_worksp_gfp_el)[2] *= (*mp_worksp_gfp_el)[4]; - (*mp_worksp_gfp_el)[2] -= (*mp_worksp_gfp_el)[1]; - (*mp_worksp_gfp_el)[2] -= (*mp_worksp_gfp_el)[1]; - - //y = z * z; - (*mp_worksp_gfp_el)[3].share_assign((*mp_worksp_gfp_el)[0]); - (*mp_worksp_gfp_el)[3] *= (*mp_worksp_gfp_el)[0]; - - //GFpElement U(y + y); - (*mp_worksp_gfp_el)[5].share_assign((*mp_worksp_gfp_el)[3]); - (*mp_worksp_gfp_el)[5] += (*mp_worksp_gfp_el)[3]; - - //z = U + U; - (*mp_worksp_gfp_el)[0].share_assign((*mp_worksp_gfp_el)[5]); - (*mp_worksp_gfp_el)[0] += (*mp_worksp_gfp_el)[5]; - - //U = z + z; - (*mp_worksp_gfp_el)[5].share_assign((*mp_worksp_gfp_el)[0]); - (*mp_worksp_gfp_el)[5] += (*mp_worksp_gfp_el)[0]; - - //y = M * (S - x) - U; - (*mp_worksp_gfp_el)[3].share_assign((*mp_worksp_gfp_el)[1]); - (*mp_worksp_gfp_el)[3] -= (*mp_worksp_gfp_el)[2]; - (*mp_worksp_gfp_el)[3] *= (*mp_worksp_gfp_el)[4]; - (*mp_worksp_gfp_el)[3] -= (*mp_worksp_gfp_el)[5]; - - if (mZ != *(mC.get_mres_one())) - { - //z = mY * mZ; - (*mp_worksp_gfp_el)[0].share_assign(mY); - (*mp_worksp_gfp_el)[0] *= mZ; + GFpElement y(mX * mX); - } + GFpElement M(y + y + y + mAZpow4); + + 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; - (*mp_worksp_gfp_el)[0].share_assign(mY); + z = mY; - } - //z = z + z; - (*mp_worksp_gfp_el)[6].share_assign((*mp_worksp_gfp_el)[0]); - (*mp_worksp_gfp_el)[0] += (*mp_worksp_gfp_el)[6]; + z = z + z; - //mX = x; - //mY = y; - //mZ = z; - mX = (*mp_worksp_gfp_el)[2]; - mY = (*mp_worksp_gfp_el)[3]; - mZ = (*mp_worksp_gfp_el)[0]; + mX = x; + mY = y; + mZ = z; mZpow2_set = false; mZpow3_set = false; @@ -688,7 +470,7 @@ void PointGFp::turn_on_sp_red_mul() const * Z has value one, i.e. x and y correspond to * their values in affine coordinates */ -PointGFp const PointGFp::get_z_to_one() const +PointGFp PointGFp::get_z_to_one() const { return PointGFp(*this).set_z_to_one(); } @@ -701,7 +483,7 @@ PointGFp const PointGFp::get_z_to_one() const */ const PointGFp& PointGFp::set_z_to_one() const { - if (!(mZ.get_value() == BigInt(1)) && !(mZ.get_value() == BigInt(0))) + if(!(mZ.get_value() == BigInt(1)) && !(mZ.get_value() == BigInt(0))) { GFpElement z = inverse(mZ); GFpElement z2 = z * z; @@ -714,7 +496,7 @@ const PointGFp& PointGFp::set_z_to_one() const } else { - if (mZ.get_value() == BigInt(0)) + if(mZ.get_value() == BigInt(0)) { throw Illegal_Transformation("cannot convert Z to one"); } @@ -722,58 +504,39 @@ const PointGFp& PointGFp::set_z_to_one() const return *this; // mZ = 1 already } -const CurveGFp PointGFp::get_curve() const - { - return mC; - } - -GFpElement const PointGFp::get_affine_x() const +GFpElement PointGFp::get_affine_x() const { - - if (is_zero()) - { + if(is_zero()) throw Illegal_Transformation("cannot convert to affine"); - } - /*if(!mZpow2_set) - {*/ mZpow2 = mZ * mZ; mZpow2_set = true; - //} - //assert(mZpow2 == mZ*mZ); GFpElement z2 = mZpow2; return mX * z2.inverse_in_place(); } -GFpElement const PointGFp::get_affine_y() const +GFpElement PointGFp::get_affine_y() const { - - if (is_zero()) - { + if(is_zero()) throw Illegal_Transformation("cannot convert to affine"); - } - /*if(!mZpow3_set ) - {*/ mZpow3 = mZ * mZ * mZ; mZpow3_set = true; - //} - //assert(mZpow3 == mZ * mZ *mZ); GFpElement z3 = mZpow3; return mY * z3.inverse_in_place(); } -GFpElement const PointGFp::get_jac_proj_x() const +GFpElement PointGFp::get_jac_proj_x() const { return GFpElement(mX); } -GFpElement const PointGFp::get_jac_proj_y() const +GFpElement PointGFp::get_jac_proj_y() const { return GFpElement(mY); } -GFpElement const PointGFp::get_jac_proj_z() const +GFpElement PointGFp::get_jac_proj_z() const { return GFpElement(mZ); } @@ -794,14 +557,14 @@ bool PointGFp::is_zero() const void PointGFp::check_invariants() const { - if (is_zero()) + if(is_zero()) { return; } const GFpElement y2 = mY * mY; const GFpElement x3 = mX * mX * mX; - if (mZ.get_value() == BigInt(1)) + if(mZ.get_value() == BigInt(1)) { GFpElement ax = mC.get_a() * mX; if(y2 != (x3 + ax + mC.get_b())) @@ -820,7 +583,7 @@ void PointGFp::check_invariants() const const GFpElement aXZ4 = mAZpow4 * mX; const GFpElement bZ6 = mC.get_b() * mZpow3 * mZpow3; - if (y2 != (x3 + aXZ4 + bZ6)) + if(y2 != (x3 + aXZ4 + bZ6)) throw Illegal_Point(); } @@ -846,11 +609,11 @@ PointGFp mult2(const PointGFp& point) bool operator==(const PointGFp& lhs, PointGFp const& rhs) { - if (lhs.is_zero() && rhs.is_zero()) + if(lhs.is_zero() && rhs.is_zero()) { return true; } - if ((lhs.is_zero() && !rhs.is_zero()) || (!lhs.is_zero() && rhs.is_zero())) + if((lhs.is_zero() && !rhs.is_zero()) || (!lhs.is_zero() && rhs.is_zero())) { return false; } @@ -906,16 +669,16 @@ PointGFp mult_point_secure(const PointGFp& point, const BigInt& scalar, SecureVector<byte> EC2OSP(const PointGFp& point, byte format) { SecureVector<byte> result; - if (format == PointGFp::UNCOMPRESSED) + if(format == PointGFp::UNCOMPRESSED) { result = encode_uncompressed(point); } - else if (format == PointGFp::COMPRESSED) + else if(format == PointGFp::COMPRESSED) { result = encode_compressed(point); } - else if (format == PointGFp::HYBRID) + else if(format == PointGFp::HYBRID) { result = encode_hybrid(point); } @@ -929,7 +692,7 @@ SecureVector<byte> encode_compressed(const PointGFp& point) { - if (point.is_zero()) + if(point.is_zero()) { SecureVector<byte> result (1); result[0] = 0; @@ -938,7 +701,7 @@ SecureVector<byte> encode_compressed(const PointGFp& point) } u32bit l = point.get_curve().get_p().bits(); int dummy = l & 7; - if (dummy != 0) + if(dummy != 0) { l += 8 - dummy; } @@ -949,7 +712,7 @@ SecureVector<byte> encode_compressed(const PointGFp& point) 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)) + if(y.get_bit(0)) { result[0] |= 1; } @@ -959,7 +722,7 @@ SecureVector<byte> encode_compressed(const PointGFp& point) SecureVector<byte> encode_uncompressed(const PointGFp& point) { - if (point.is_zero()) + if(point.is_zero()) { SecureVector<byte> result (1); result[0] = 0; @@ -967,7 +730,7 @@ SecureVector<byte> encode_uncompressed(const PointGFp& point) } u32bit l = point.get_curve().get_p().bits(); int dummy = l & 7; - if (dummy != 0) + if(dummy != 0) { l += 8 - dummy; } @@ -986,7 +749,7 @@ SecureVector<byte> encode_uncompressed(const PointGFp& point) SecureVector<byte> encode_hybrid(const PointGFp& point) { - if (point.is_zero()) + if(point.is_zero()) { SecureVector<byte> result (1); result[0] = 0; @@ -994,7 +757,7 @@ SecureVector<byte> encode_hybrid(const PointGFp& point) } u32bit l = point.get_curve().get_p().bits(); int dummy = l & 7; - if (dummy != 0) + if(dummy != 0) { l += 8 - dummy; } @@ -1007,7 +770,7 @@ SecureVector<byte> encode_hybrid(const PointGFp& point) 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)) + if(y.get_bit(0)) { result[0] |= 1; } @@ -1016,7 +779,7 @@ SecureVector<byte> encode_hybrid(const PointGFp& point) PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve) { - if (os.size() == 1 && os[0] == 0) + if(os.size() == 1 && os[0] == 0) { return PointGFp(curve); // return zero } @@ -1072,7 +835,7 @@ PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve) bX.copy(os.begin() + 1, l); bY.copy(os.begin()+1+l, l); yMod2 = (pc & 0x01) == 1; - if (!(PointGFp::decompress(yMod2, x, curve) == y)) + if(!(PointGFp::decompress(yMod2, x, curve) == y)) { throw Illegal_Point("error during decoding hybrid format"); } @@ -1107,7 +870,7 @@ GFpElement PointGFp::decompress(bool yMod2, const GFpElement& x, throw Illegal_Point("error during decompression"); bool zMod2 = z.get_bit(0); - if ((zMod2 && ! yMod2) || (!zMod2 && yMod2)) + if((zMod2 && ! yMod2) || (!zMod2 && yMod2)) { z = curve.get_p() - z; } diff --git a/src/math/gfpmath/point_gfp.h b/src/math/gfpmath/point_gfp.h index 0c7bb8428..1e47fa783 100644 --- a/src/math/gfpmath/point_gfp.h +++ b/src/math/gfpmath/point_gfp.h @@ -2,7 +2,7 @@ * Arithmetic for point groups of elliptic curves over GF(p) * * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008 Jack Lloyd +* 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -11,9 +11,6 @@ #define BOTAN_POINT_GFP_H__ #include <botan/curve_gfp.h> -#include <botan/gfp_element.h> -#include <botan/bigint.h> -#include <botan/exceptn.h> #include <vector> namespace Botan { @@ -24,7 +21,7 @@ struct BOTAN_DLL Illegal_Point : public Exception }; /** -* This class represents one point on a curve of GF(p). +* This class represents one point on a curve of GF(p) */ class BOTAN_DLL PointGFp { @@ -48,7 +45,7 @@ class BOTAN_DLL PointGFp * Construct the point O * @param curve The base curve */ - explicit PointGFp(const CurveGFp& curve); + PointGFp(const CurveGFp& curve); /** * Construct a point given its affine coordinates @@ -56,8 +53,9 @@ class BOTAN_DLL PointGFp * @param x affine x coordinate * @param y affine y coordinate */ - explicit PointGFp(const CurveGFp& curve, GFpElement const& x, - GFpElement const& y); + PointGFp(const CurveGFp& curve, + const GFpElement& x, + const GFpElement& y); /** * Construct a point given its jacobian projective coordinates @@ -66,20 +64,13 @@ class BOTAN_DLL PointGFp * @param y jacobian projective y coordinate * @param z jacobian projective y coordinate */ - explicit PointGFp(const CurveGFp& curve, GFpElement const& x, - GFpElement const& y, GFpElement const& z); + PointGFp(const CurveGFp& curve, + const GFpElement& x, + const GFpElement& y, + const GFpElement& z); - /** - * copy constructor - * @param other the value to clone - */ - PointGFp(const PointGFp& other); - - /** - * assignment operator - * @param other The point to use as source for the assignment - */ - const PointGFp& operator=(const PointGFp& other); + //PointGFp(const PointGFp& other) = default; + //PointGFp& operator=(const PointGFp& other) = default; /** * assign another point which is on the same curve as *this @@ -87,8 +78,6 @@ class BOTAN_DLL PointGFp */ const PointGFp& assign_within_same_curve(const PointGFp& other); - - /** * += Operator * @param rhs the PointGFp to add to the local value @@ -126,8 +115,7 @@ class BOTAN_DLL PointGFp */ PointGFp& mult_this_secure(const BigInt& scalar, const BigInt& point_order, - const BigInt& max_secr - ); + const BigInt& max_secr); /** * Negate internal value(*this *= -1 ) @@ -162,43 +150,43 @@ class BOTAN_DLL PointGFp * thus x and y have just the affine values. * @result *this */ - PointGFp const get_z_to_one() const; + PointGFp get_z_to_one() const; /** * Return base curve of this point * @result the curve over GF(p) of this point */ - CurveGFp const get_curve() const; + const CurveGFp& get_curve() const { return mC; } /** * get affine x coordinate * @result affine x coordinate */ - GFpElement const get_affine_x() const; + GFpElement get_affine_x() const; /** * get affine y coordinate * @result affine y coordinate */ - GFpElement const get_affine_y() const; + GFpElement get_affine_y() const; /** * get the jacobian projective x coordinate * @result jacobian projective x coordinate */ - GFpElement const get_jac_proj_x() const; + GFpElement get_jac_proj_x() const; /** * get the jacobian projective y coordinate * @result jacobian projective y coordinate */ - GFpElement const get_jac_proj_y() const; + GFpElement get_jac_proj_y() const; /** * get the jacobian projective z coordinate * @result jacobian projective z coordinate */ - GFpElement const get_jac_proj_z() const; + GFpElement get_jac_proj_z() const; /** * Is this the point at infinity? @@ -214,36 +202,16 @@ class BOTAN_DLL PointGFp */ void check_invariants() const; - /** - * swaps the states of *this and other, does not throw! + * swaps the states of *this and other, does not throw! * @param other the object to swap values with */ void swap(PointGFp& other); - /** - * Sets the shared pointer to the GFpModulus that will be - * held in *this, specifically the various members of *this. - * Warning: do not use this function unless you know in detail about - * the implications of using - * the shared GFpModulus objects! - * Do NOT spread a shared pointer to GFpModulus over different - * threads! - * @param mod a shared pointer to a GFpModulus that will - * be held in the members *this - */ - void set_shrd_mod(std::tr1::shared_ptr<GFpModulus> p_mod); - static GFpElement decompress(bool yMod2, GFpElement const& x, const CurveGFp& curve); private: - static const u32bit GFPEL_WKSP_SIZE = 9; - void ensure_worksp() const; - - inline std::tr1::shared_ptr<PointGFp> mult_loop(int l, const BigInt& m, - std::tr1::shared_ptr<PointGFp> H, - std::tr1::shared_ptr<PointGFp> tmp, - const PointGFp& P); + void mult_loop(int l, const BigInt& m, PointGFp& H, const PointGFp& P); CurveGFp mC; mutable GFpElement mX; // NOTE: these values must be mutable (affine<->proj) @@ -255,8 +223,6 @@ class BOTAN_DLL PointGFp mutable bool mZpow2_set; mutable bool mZpow3_set; mutable bool mAZpow4_set; - mutable std::tr1::shared_ptr<std::vector<GFpElement> > mp_worksp_gfp_el; - }; // relational operators |