diff options
Diffstat (limited to 'src/math/gfpmath')
| -rw-r--r-- | src/math/gfpmath/curve_gfp.cpp | 149 | ||||
| -rw-r--r-- | src/math/gfpmath/curve_gfp.h | 62 | ||||
| -rw-r--r-- | src/math/gfpmath/gfp_element.cpp | 248 | ||||
| -rw-r--r-- | src/math/gfpmath/gfp_element.h | 98 | ||||
| -rw-r--r-- | src/math/gfpmath/gfp_modulus.h | 44 | ||||
| -rw-r--r-- | src/math/gfpmath/point_gfp.cpp | 703 | ||||
| -rw-r--r-- | src/math/gfpmath/point_gfp.h | 90 |
7 files changed, 302 insertions, 1092 deletions
diff --git a/src/math/gfpmath/curve_gfp.cpp b/src/math/gfpmath/curve_gfp.cpp index d88146dd5..e6e69ab0f 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,152 +14,45 @@ namespace Botan { -void CurveGFp::set_shrd_mod(const std::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::shared_ptr<GFpModulus> p_mod = std::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::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::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_a)); - } - if(other.mp_mres_b.get()) - { - mp_mres_b = std::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_b)); - } - if(other.mp_mres_one.get()) - { - mp_mres_one = std::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::shared_ptr<GFpModulus> p_mod = std::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::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_a)); - } - if(other.mp_mres_b.get()) - { - mp_mres_b = std::shared_ptr<GFpElement>(new GFpElement(*other.mp_mres_b)); - } - if(other.mp_mres_one.get()) - { - mp_mres_one = std::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::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::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::shared_ptr<GFpElement const> const CurveGFp::get_mres_one() const - { - if(mp_mres_one.get() == 0) - { - mp_mres_one = std::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) { - return output << "y^2f = x^3 + (" << elem.get_a() << ")x + (" << elem.get_b() << ")"; + 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 index 5b0ec0558..d2ca437fb 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 */ @@ -31,28 +32,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::shared_ptr<GFpModulus> mod); + // CurveGFp(const CurveGFp& other) = default; + // CurveGFp& operator=(const CurveGFp& other) = default; // getters @@ -60,13 +41,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 +56,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 +65,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 +74,13 @@ class BOTAN_DLL CurveGFp * function. * @result the GFpElement 1, transformed to its m-residue */ - std::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::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::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 +89,10 @@ class BOTAN_DLL CurveGFp void swap(CurveGFp& other); private: - std::shared_ptr<GFpModulus> mp_mod; + GFpModulus modulus; GFpElement mA; GFpElement mB; - mutable std::shared_ptr<GFpElement> mp_mres_a; - mutable std::shared_ptr<GFpElement> mp_mres_b; - mutable std::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 3f028f34f..3bb4d0002 100644 --- a/src/math/gfpmath/gfp_element.cpp +++ b/src/math/gfpmath/gfp_element.cpp @@ -165,47 +165,20 @@ 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::shared_ptr<GFpModulus>(new GFpModulus(p)); - assert(mp_mod->m_p_dash == 0); +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(); } -GFpElement::GFpElement(std::shared_ptr<GFpModulus> const mod, const BigInt& value, bool use_montgm) - : mp_mod(), - m_value(value % mod->m_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 +void GFpElement::turn_on_sp_red_mul() { ensure_montgm_precomp(); m_use_montgm = true; } -void GFpElement::turn_off_sp_red_mul() const +void GFpElement::turn_off_sp_red_mul() { if(m_is_trf) { @@ -216,40 +189,25 @@ void GFpElement::turn_off_sp_red_mul() const m_use_montgm = false; } -void GFpElement::ensure_montgm_precomp() const +void GFpElement::ensure_montgm_precomp() { - if((!mp_mod->m_r.is_zero()) && (!mp_mod->m_r_inv.is_zero()) && (!mp_mod->m_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->m_p)); - - BigInt tmp_r_inv(inverse_mod(tmp_r, mp_mod->m_p)); + BigInt tmp_r(montgm_calc_r_oddmod(modulus.get_p())); - BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, mp_mod->m_p, tmp_r_inv)); + BigInt tmp_r_inv(inverse_mod(tmp_r, modulus.get_p())); - mp_mod->m_r.grow_reg(tmp_r.size()); - mp_mod->m_r_inv.grow_reg(tmp_r_inv.size()); - mp_mod->m_p_dash.grow_reg(tmp_p_dash.size()); + BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, modulus.get_p(), tmp_r_inv)); - mp_mod->m_r = tmp_r; - mp_mod->m_r_inv = tmp_r_inv; - mp_mod->m_p_dash = tmp_p_dash; - - assert(!mp_mod->m_r.is_zero()); - assert(!mp_mod->m_r_inv.is_zero()); - assert(!mp_mod->m_p_dash.is_zero()); + modulus.reset_values(tmp_p_dash, tmp_r, tmp_r_inv); } } -void GFpElement::set_shrd_mod(std::shared_ptr<GFpModulus> const p_mod) - { - mp_mod = p_mod; - } - void GFpElement::trf_to_mres() const { if(!m_use_montgm) @@ -257,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->m_r_inv.is_zero()); - assert(!mp_mod->m_p_dash.is_zero()); - m_value = montg_trf_to_mres(m_value, mp_mod->m_r, mp_mod->m_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->m_p, mp_mod->m_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->m_p == rhs.mp_mod->m_p); + assert(lhs.modulus.get_p() == rhs.modulus.get_p()); if(lhs.m_use_montgm && rhs.m_use_montgm) { - assert(rhs.mp_mod->m_p_dash == lhs.mp_mod->m_p_dash); - assert(rhs.mp_mod->m_r == lhs.mp_mod->m_r); - assert(rhs.mp_mod->m_r_inv == lhs.mp_mod->m_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; @@ -327,7 +285,7 @@ bool GFpElement::is_trf_to_mres() const const BigInt& GFpElement::get_p() const { - return (mp_mod->m_p); + return (modulus.get_p()); } const BigInt& GFpElement::get_value() const @@ -345,7 +303,7 @@ 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 + // 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"); } @@ -357,107 +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->m_p != other.mp_mod->m_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->m_p_dash.grow_reg(other.mp_mod->m_p_dash.size()); - mp_mod->m_r.grow_reg(other.mp_mod->m_r.size()); - mp_mod->m_r_inv.grow_reg(other.mp_mod->m_r_inv.size()); - - mp_mod->m_p_dash = other.mp_mod->m_p_dash; - mp_mod->m_r = other.mp_mod->m_r; - mp_mod->m_r_inv = other.mp_mod->m_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->m_p) - workspace -= mp_mod->m_p; + if(workspace >= modulus.get_p()) + workspace -= modulus.get_p(); m_value = workspace; - assert(m_value < mp_mod->m_p); + assert(m_value < modulus.get_p()); assert(m_value >= 0); return *this; @@ -467,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->m_p; + workspace += modulus.get_p(); m_value = workspace; - assert(m_value < mp_mod->m_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->m_p; + workspace %= modulus.get_p(); m_value = workspace; return *this; } GFpElement& GFpElement::operator*=(const GFpElement& rhs) { - assert(rhs.mp_mod->m_p == mp_mod->m_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->m_p == mp_mod->m_p); // is montgm. mult is on, then precomps must be there - assert(rhs.mp_mod->m_p_dash == mp_mod->m_p_dash); - assert(rhs.mp_mod->m_r == mp_mod->m_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(); @@ -508,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->m_p, mp_mod->m_p_dash, mp_mod->m_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 { @@ -524,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->m_p; + workspace %= modulus.get_p(); m_value = workspace; } return *this; @@ -536,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->m_p; + BigInt workspace = m_value; + workspace *= rhs_ordres.get_value(); + workspace %= modulus.get_p(); m_value = workspace; - } else { @@ -566,30 +433,31 @@ bool GFpElement::is_zero() GFpElement& GFpElement::inverse_in_place() { - m_value = inverse_mod(m_value, mp_mod->m_p); + m_value = inverse_mod(m_value, modulus.get_p()); + if(m_is_trf) { assert(m_use_montgm); - m_value *= mp_mod->m_r; - m_value *= mp_mod->m_r; - m_value %= mp_mod->m_p; + m_value *= modulus.get_r(); + m_value *= modulus.get_r(); + m_value %= modulus.get_p(); } - assert(m_value <= mp_mod->m_p); + assert(m_value <= modulus.get_p()); return *this; } GFpElement& GFpElement::negate() { - m_value = mp_mod->m_p - m_value; - assert(m_value <= mp_mod->m_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); } @@ -601,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 a4d9ac250..538d41a47 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 */ @@ -12,7 +13,6 @@ #include <botan/bigint.h> #include <botan/gfp_modulus.h> #include <iosfwd> -#include <memory> namespace Botan { @@ -38,57 +38,21 @@ 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); + GFpElement(const BigInt& p, const BigInt& value, bool use_montgm = true); + // GFpElement(const GFpElement& other) = default; - /** 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::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). - - * @param other The element to assign to our object - */ - const GFpElement& operator=(const GFpElement& other); - - /** - * 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 */ - void turn_on_sp_red_mul() const; + void turn_on_sp_red_mul(); /** * Switch Montgomery multiplcation optimizations OFF */ - void turn_off_sp_red_mul() const; + void turn_off_sp_red_mul(); /** * += Operator @@ -122,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 ) @@ -157,31 +121,9 @@ 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::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::shared_ptr<GFpModulus> const mod); - - /** - * Tells whether this GFpElement is currently transformed to it´ m-residue, + * 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 it´s m-residue. + * @result true if it is currently transformed to its m-residue. */ bool is_trf_to_mres() const; @@ -206,7 +148,7 @@ class BOTAN_DLL GFpElement * 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: + * 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 @@ -216,30 +158,22 @@ class BOTAN_DLL GFpElement */ static bool align_operands_res(const GFpElement& lhs, const GFpElement& rhs); - //friend declarations for non-member functions - - friend class Point_Coords_GFp; - /** * 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() const; + void ensure_montgm_precomp(); void trf_to_mres() const; void trf_to_ordres() const; - std::shared_ptr<GFpModulus> mp_mod; + 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; + bool m_use_montgm; + mutable bool m_is_trf; // if m_value is montgomery }; // relational operators @@ -256,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 03e8a19e0..fcdd13ee1 100644 --- a/src/math/gfpmath/gfp_modulus.h +++ b/src/math/gfpmath/gfp_modulus.h @@ -22,24 +22,26 @@ class GFpElement; class BOTAN_DLL GFpModulus { public: - friend class GFpElement; /** * 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()); } @@ -48,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); } /** @@ -61,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); } @@ -70,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; } @@ -81,7 +83,7 @@ class BOTAN_DLL GFpModulus * performed! * @result r */ - inline const BigInt& get_r() const + const BigInt& get_r() const { return m_r; } @@ -92,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; } @@ -103,17 +105,25 @@ 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, + 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 - 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/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp index 050fd0f50..00331f25b 100644 --- a/src/math/gfpmath/point_gfp.cpp +++ b/src/math/gfpmath/point_gfp.cpp @@ -13,295 +13,114 @@ 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) +nPointGFp::PointGFp(const CurveGFp& curve) : + mC(curve), + mX(curve.get_p(), 0), + mY(curve.get_p(), 1), + mZ(curve.get_p(), 0) { - // 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) { - set_shrd_mod(mC.get_ptr_mod()); } -// assignment operator -const PointGFp& PointGFp::operator=(PointGFp const& other) +PointGFp::PointGFp(const CurveGFp& curve, + const GFpElement& x, + const GFpElement& y) : + mC(curve), + mX(x), + mY(y), + mZ(curve.get_p(),1) { - 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) - { - mX = other.get_jac_proj_x(); - mY = other.get_jac_proj_y(); - mZ = other.get_jac_proj_z(); - mZpow2_set = false; - mZpow3_set = false; - mAZpow4_set = false; - // the rest stays! - return *this; - } - -void PointGFp::set_shrd_mod(std::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::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); - - //S1 = mY; - (*mp_worksp_gfp_el)[2].share_assign(mY); - } - else - { - if ((!rhs.mZpow2_set) || (!rhs.mZpow3_set)) - { - rhs.mZpow2 = rhs.mZ; - rhs.mZpow2 *= rhs.mZ; - rhs.mZpow3 = rhs.mZpow2; - rhs.mZpow3 *= rhs.mZ; - - 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; + GFpElement U1 = mX; + GFpElement S1 = mY; - } - if (mZ == *(mC.get_mres_one())) + if(rhs.mZ != mC.get_mres_one()) { - //U2 = rhs.mX; - (*mp_worksp_gfp_el)[1].share_assign(rhs.mX); + GFpElement rhs_z2 = rhs.mZ * rhs.mZ; - //S2 = rhs.mY; - (*mp_worksp_gfp_el)[3].share_assign(rhs.mY); + U1 *= rhs_z2; + S1 *= rhs_z2 * rhs.mZ; } - else - { - if ((!mZpow2_set) || (!mZpow3_set)) - { - // precomputation can´t be used, because *this changes anyway - mZpow2 = mZ; - mZpow2 *= mZ; - mZpow3 = mZpow2; - mZpow3 *= mZ; - } - //U2 = rhs.mX * mZpow2; - (*mp_worksp_gfp_el)[1].share_assign(rhs.mX); - (*mp_worksp_gfp_el)[1] *= mZpow2; + GFpElement U2 = rhs.mX; + GFpElement S2 = rhs.mY; - //S2 = rhs.mY * mZpow3; - (*mp_worksp_gfp_el)[3].share_assign(rhs.mY); - (*mp_worksp_gfp_el)[3] *= mZpow3; + if(mZ != mC.get_mres_one()) + { + GFpElement lhs_z2 = mZ * mZ; + U2 *= lhs_z2; + S2 *= lhs_z2 * mZ; } - //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 +129,7 @@ PointGFp& PointGFp::operator-=(const PointGFp& rhs) { PointGFp minus_rhs = PointGFp(rhs).negate(); - if (is_zero()) + if(is_zero()) { *this = minus_rhs; } @@ -336,92 +155,39 @@ PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, // use montgomery mult. in this operation this->turn_on_sp_red_mul(); - std::shared_ptr<PointGFp> H(new PointGFp(this->mC)); - std::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; - } - // -#ifdef CM_AADA -#ifndef CM_RAND_EXP - int max_secr_bits = max_secr.bits(); -#endif -#endif - - int mul_bits = m.bits(); // this is used for a determined number of loop runs in - // the mult_loop where leading zero´s are padded if necessary. - // Here we assign the value that will be used when no countermeasures are specified -#ifdef CM_RAND_EXP - u32bit rand_r_bit_len = 20; // Coron(99) proposes 20 bit for r -#ifdef CM_AADA + int mul_bits = m.bits(); - BigInt r_max(1); - -#endif // CM_AADA - - // use randomized exponent -#ifdef TA_COLL_T - static BigInt r_randexp; - if (new_rand) + for(int i = mul_bits - 1; i >= 0; i--) { - r_randexp = random_integer(rand_r_bit_len); - } - //assert(!r_randexp.is_zero()); -#else - BigInt r_randexp(random_integer(rand_r_bit_len)); -#endif - - m += r_randexp * point_order; - // determine mul_bits... -#ifdef CM_AADA - // AADA with rand. Exp. - //assert(rand_r_bit_len > 0); - r_max <<= rand_r_bit_len; - r_max -= 1; - //assert(r_max.bits() == rand_r_bit_len); - mul_bits = (max_secr + point_order * r_max).bits(); -#else - // rand. Exp. without AADA - mul_bits = m.bits(); -#endif // CM_AADA - - -#endif // CM_RAND_EXP - - // determine mul_bits... -#if (CM_AADA == 1 && CM_RAND_EXP != 1) - - mul_bits = max_secr_bits; -#endif // CM_AADA without CM_RAND_EXP - - //assert(mul_bits != 0); + H.mult2_in_place(); + if(m.get_bit(i)) + H += P; + } - H = mult_loop(mul_bits-1, m, H, tmp, P); + if(!H.is_zero()) // cannot convert if H == O + *this = H.get_z_to_one(); + else + *this = H; - 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(); @@ -439,226 +205,100 @@ 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)) - { - //*this == P already + + 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 - { + else *this = H; - } - return *this; - } - -inline std::shared_ptr<PointGFp> PointGFp::mult_loop(int l, - const BigInt& m, - std::shared_ptr<PointGFp> H, - std::shared_ptr<PointGFp> tmp, - const PointGFp& P) - { - //assert(l >= (int)m.bits()- 1); - tmp = H; - std::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--) - { - 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 - } - return H; + return *this; } PointGFp& PointGFp::negate() { - if (!is_zero()) - { + if(!is_zero()) mY.negate(); - } + return *this; } // *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) + GFpElement a_z4 = mC.get_mres_a(); + if(mZ != mC.get_mres_one()) { - if (mZ == *(mC.get_mres_one())) - { - mAZpow4 = mC.get_mres_a(); - mAZpow4_set = true; - } - else - { - if (!mZpow2_set) - { - mZpow2 = mZ; - mZpow2 *= mZ; + GFpElement z2 = mZ * mZ; + a_z4 *= z2; + a_z4 *= z2; + } - mZpow2_set = true; - } - //x = mZpow2 * mZpow2; - (*mp_worksp_gfp_el)[2].share_assign(mZpow2); - (*mp_worksp_gfp_el)[2] *= mZpow2; + GFpElement y(mX * mX); - //mAZpow4 = mC.get_mres_a() * x; - mAZpow4 = mC.get_mres_a(); - mAZpow4 *= (*mp_worksp_gfp_el)[2]; + GFpElement M(y + y + y + a_z4); - } + x = M * M - (S+S); - } + y = Y_squared * Y_squared; - //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 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; + + mX = x; + mY = y; + mZ = z; - } - //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]; - - //mX = x; - //mY = y; - //mZ = z; - mX = (*mp_worksp_gfp_el)[2]; - mY = (*mp_worksp_gfp_el)[3]; - mZ = (*mp_worksp_gfp_el)[0]; - - mZpow2_set = false; - mZpow3_set = false; - mAZpow4_set = false; return *this; } @@ -676,19 +316,14 @@ void PointGFp::turn_on_sp_red_mul() const mX.get_mres(); mY.get_mres(); mZ.get_mres(); - - mZpow2.turn_on_sp_red_mul(); - mZpow3.turn_on_sp_red_mul(); - mAZpow4.turn_on_sp_red_mul(); } -// getters /** * 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 const PointGFp::get_z_to_one() const +PointGFp PointGFp::get_z_to_one() const { return PointGFp(*this).set_z_to_one(); } @@ -701,7 +336,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 +349,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 +357,35 @@ const PointGFp& PointGFp::set_z_to_one() const return *this; // mZ = 1 already } -const CurveGFp PointGFp::get_curve() const +GFpElement PointGFp::get_affine_x() const { - return mC; - } - -GFpElement const 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; + GFpElement z2 = mZ * mZ; 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; + GFpElement z3 = mZ * mZ * mZ; 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 +406,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())) @@ -811,16 +423,13 @@ void PointGFp::check_invariants() const } - mZpow2 = mZ * mZ; - mZpow2_set = true; - mZpow3 = mZpow2 * mZ; - mZpow3_set = true; - mAZpow4 = mZpow3 * mZ * mC.get_a(); - mAZpow4_set = true; - const GFpElement aXZ4 = mAZpow4 * mX; - const GFpElement bZ6 = mC.get_b() * mZpow3 * mZpow3; + 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)) + if(y2 != (x3 + aXZ4 + bZ6)) throw Illegal_Point(); } @@ -831,12 +440,6 @@ void PointGFp::swap(PointGFp& other) mX.swap(other.mX); mY.swap(other.mY); mZ.swap(other.mZ); - mZpow2.swap(other.mZpow2); - mZpow3.swap(other.mZpow3); - mAZpow4.swap(other.mAZpow4); - std::swap<bool>(mZpow2_set, other.mZpow2_set); - std::swap<bool>(mZpow3_set, other.mZpow3_set); - std::swap<bool>(mAZpow4_set, other.mAZpow4_set); } PointGFp mult2(const PointGFp& point) @@ -846,11 +449,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 +509,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 +532,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 +541,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 +552,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 +562,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 +570,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 +589,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 +597,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 +610,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 +619,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 } @@ -1038,10 +641,6 @@ PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve) bX = SecureVector<byte>(os.size() - 1); bX.copy(os.begin()+1, os.size()-1); - /* Problem wäre, wenn decode() das erste bit als Vorzeichen interpretiert. - *--------------------- - * AW(FS): decode() interpretiert das erste Bit nicht als Vorzeichen - */ bi_dec_x = BigInt::decode(bX, bX.size()); x = GFpElement(curve.get_p(), bi_dec_x); bool yMod2; @@ -1072,7 +671,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 +706,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 10fc404bf..276635f56 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,28 +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); - - /** - * 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); - - /** - * assign another point which is on the same curve as *this - * @param other The point to use as source for the assignment - */ - const PointGFp& assign_within_same_curve(const PointGFp& other); - + 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 @@ -126,8 +109,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 +144,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,49 +196,19 @@ 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::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::shared_ptr<PointGFp> mult_loop(int l, const BigInt& m, - std::shared_ptr<PointGFp> H, - std::shared_ptr<PointGFp> tmp, - const PointGFp& P); - CurveGFp mC; mutable GFpElement mX; // NOTE: these values must be mutable (affine<->proj) mutable GFpElement mY; mutable GFpElement mZ; - mutable GFpElement mZpow2; // mZ^2 - mutable GFpElement mZpow3; // mZ^3 - mutable GFpElement mAZpow4; // mA*mZ^4 - mutable bool mZpow2_set; - mutable bool mZpow3_set; - mutable bool mAZpow4_set; - mutable std::shared_ptr<std::vector<GFpElement> > mp_worksp_gfp_el; - }; // relational operators |