diff options
author | lloyd <[email protected]> | 2010-02-24 21:34:50 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2010-02-24 21:34:50 +0000 |
commit | 9efa59d4322babc444601052aa79f7b3fe304fd6 (patch) | |
tree | 720fdac9668ef4313af82d7f0f4bdecd15c73b0e /src/math | |
parent | b06a941a98f49172b203914810483589cf86cc76 (diff) |
Remove the montgomery optimizations from GFpElement entirely.
This makes things even slower than they were before, but will make
refactoring easier. And most of the montgomery code there was
duplicates of other code that already existed in the
codebase. Anything useful can be pulled back out from history later if
needed.
Diffstat (limited to 'src/math')
-rw-r--r-- | src/math/gfpmath/curve_gfp.cpp | 15 | ||||
-rw-r--r-- | src/math/gfpmath/curve_gfp.h | 30 | ||||
-rw-r--r-- | src/math/gfpmath/gfp_element.cpp | 395 | ||||
-rw-r--r-- | src/math/gfpmath/gfp_element.h | 70 | ||||
-rw-r--r-- | src/math/gfpmath/point_gfp.cpp | 72 | ||||
-rw-r--r-- | src/math/gfpmath/point_gfp.h | 8 |
6 files changed, 29 insertions, 561 deletions
diff --git a/src/math/gfpmath/curve_gfp.cpp b/src/math/gfpmath/curve_gfp.cpp index e6e69ab0f..b3be7d228 100644 --- a/src/math/gfpmath/curve_gfp.cpp +++ b/src/math/gfpmath/curve_gfp.cpp @@ -16,20 +16,10 @@ namespace Botan { CurveGFp::CurveGFp(const GFpElement& a, const GFpElement& b, const BigInt& p) : - modulus(p), mA(a), mB(b), - mres_a(mA), mres_b(mB), mres_one(p, 1) + modulus(p), mA(a), mB(b) { if(p != mA.get_p() || p != mB.get_p()) throw Invalid_Argument("could not construct curve: moduli of arguments differ"); - - mres_a.turn_on_sp_red_mul(); - mres_a.get_mres(); - - mres_b.turn_on_sp_red_mul(); - mres_b.get_mres(); - - mres_one.turn_on_sp_red_mul(); - mres_one.get_mres(); } // swaps the states of *this and other, does not throw @@ -38,9 +28,6 @@ void CurveGFp::swap(CurveGFp& other) std::swap(mA, other.mA); std::swap(mB, other.mB); std::swap(modulus, other.modulus); - std::swap(mres_a, other.mres_a); - std::swap(mres_b, other.mres_b); - std::swap(mres_one, other.mres_one); } bool operator==(const CurveGFp& lhs, const CurveGFp& rhs) diff --git a/src/math/gfpmath/curve_gfp.h b/src/math/gfpmath/curve_gfp.h index 70225217c..5be2c9af6 100644 --- a/src/math/gfpmath/curve_gfp.h +++ b/src/math/gfpmath/curve_gfp.h @@ -34,8 +34,6 @@ class BOTAN_DLL CurveGFp // CurveGFp(const CurveGFp& other) = default; // CurveGFp& operator=(const CurveGFp& other) = default; - // getters - /** * Get coefficient a * @result coefficient a @@ -49,33 +47,6 @@ class BOTAN_DLL CurveGFp const GFpElement& get_b() const { return mB; } /** - * Get the GFpElement coefficient a transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient a, transformed to its m-residue - */ - const GFpElement& get_mres_a() const { return mres_a; } - - /** - * Get the GFpElement coefficient b transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient b, transformed to its m-residue - */ - const GFpElement& get_mres_b() const { return mres_b; } - - /** - * Get the GFpElement 1 transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the GFpElement 1, transformed to its m-residue - */ - const GFpElement& get_mres_one() { return mres_one; } - - /** * Get prime modulus of the field of the curve * @result prime modulus of the field of the curve */ @@ -91,7 +62,6 @@ class BOTAN_DLL CurveGFp BigInt modulus; GFpElement mA; GFpElement mB; - 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 a3a097220..d49ca4989 100644 --- a/src/math/gfpmath/gfp_element.cpp +++ b/src/math/gfpmath/gfp_element.cpp @@ -16,305 +16,14 @@ namespace Botan { -namespace { - -void inner_montg_mult_sos(word result[], - const word* a_bar, const word* b_bar, - const word* n, const word* n_dash, u32bit s) - { - SecureVector<word> t; - t.grow_to(2*s+1); - - // t = a_bar * b_bar - for (u32bit i=0; i<s; i++) - { - word C = 0; - word S = 0; - for (u32bit j=0; j<s; j++) - { - // we use: - // word word_madd3(word a, word b, word c, word d, word* carry) - // returns a * b + c + d and resets the carry (not using it as input) - - S = word_madd3(a_bar[j], b_bar[i], t[i+j], &C); - t[i+j] = S; - } - t[i+s] = C; - } - - // ??? - for (u32bit i=0; i<s; i++) - { - // word word_madd2(word a, word b, word c, word* carry) - // returns a * b + c, resets the carry - - word C = 0; - word zero = 0; - word m = word_madd2(t[i], n_dash[0], &zero); - - for (u32bit j=0; j<s; j++) - { - word S = word_madd3(m, n[j], t[i+j], &C); - t[i+j] = S; - } - - //// mp_mulop.cpp: - ////word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y) - u32bit cnt = 0; - while (C > 0) - { - // we need not worry here about C > 1, because the other operand is zero - - word tmp = t[i+s+cnt] + C; - C = (tmp < t[i+s+cnt]); - t[i+s+cnt] = tmp; - cnt++; - } - } - - // u = t - SecureVector<word> u; - u.grow_to(s+1); - for (u32bit j=0; j<s+1; j++) - { - u[j] = t[j+s]; - } - - // t = u - n - word B = 0; - word D = 0; - for (u32bit i=0; i<s; i++) - { - D = word_sub(u[i], n[i], &B); - t[i] = D; - } - D = word_sub(u[s], 0, &B); - t[s] = D; - - // if t >= 0 (B == 0 -> no borrow), return t - if(B == 0) - { - for (u32bit i=0; i<s; i++) - { - result[i] = t[i]; - } - } - else // else return u - { - for (u32bit i=0; i<s; i++) - { - result[i] = u[i]; - } - } - } - -void montg_mult(BigInt& result, BigInt& a_bar, - BigInt& b_bar, const BigInt& m, - const BigInt& m_dash) - { - if(m.is_zero() || m_dash.is_zero()) - throw Invalid_Argument("montg_mult(): neither modulus nor m_dash may be zero (and one of them was)"); - - if(a_bar.is_zero() || b_bar.is_zero()) - result = 0; - - u32bit s = m.sig_words(); - a_bar.grow_to(s); - b_bar.grow_to(s); - result.grow_to(s); - - inner_montg_mult_sos(result.get_reg(), a_bar.data(), b_bar.data(), - m.data(), m_dash.data(), s); - } - -/** -* Calculates R=b^n (here b=2) with R>m (and R beeing as small as -* possible) for an odd modulus m. No check for parity is performed! -*/ -BigInt montgm_calc_r_oddmod(const BigInt& prime) - { - u32bit n = prime.sig_words(); - BigInt result(1); - result <<= n*BOTAN_MP_WORD_BITS; - return result; - } - -/** -*calculates m' with r*r^-1 - m*m' = 1 -* where r^-1 is the multiplicative inverse of r to the modulus m -*/ -BigInt montgm_calc_m_dash(const BigInt& r, const BigInt& m, const BigInt& r_inv) - { - BigInt result = ((r * r_inv) - BigInt(1))/m; - return result; - } - -BigInt montg_trf_to_mres(const BigInt& ord_res, const BigInt& r, const BigInt& m) - { - BigInt result(ord_res); - result *= r; - result %= m; - return result; - } - -BigInt montg_trf_to_ordres(const BigInt& m_res, const BigInt& m, const BigInt& r_inv) - { - BigInt result(m_res); - result *= r_inv; - result %= m; - return result; - } - -} - -GFpElement::GFpElement(const BigInt& p, const BigInt& value, bool use_montgomery) : +GFpElement::GFpElement(const BigInt& p, const BigInt& value) : mod_p(p), - m_value(value %p), - m_use_montgm(use_montgomery), - m_is_trf(false) - { - if(m_use_montgm) - ensure_montgm_precomp(); - } - -void GFpElement::turn_on_sp_red_mul() - { - ensure_montgm_precomp(); - m_use_montgm = true; - } - -void GFpElement::turn_off_sp_red_mul() - { - if(m_is_trf) - { - trf_to_ordres(); - // will happen soon anyway, so we can do it here already - // (this is not lazy but way more secure concerning our internal logic here) - } - m_use_montgm = false; - } - -void GFpElement::ensure_montgm_precomp() - { - if(mod_r == 0 || mod_r_inv == 0 || mod_p_dash == 0) - { - mod_r = montgm_calc_r_oddmod(mod_p); - mod_r_inv = inverse_mod(mod_r, mod_p); - mod_p_dash = montgm_calc_m_dash(mod_r, mod_p, mod_r_inv); - } - } - -void GFpElement::trf_to_mres() const - { - if(!m_use_montgm) - { - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - assert(m_is_trf == false); - assert(!mod_r_inv.is_zero()); - assert(!mod_p_dash.is_zero()); - m_value = montg_trf_to_mres(m_value, mod_r, mod_p); - m_is_trf = true; - } - -void GFpElement::trf_to_ordres() const - { - assert(m_is_trf == true); - m_value = montg_trf_to_ordres(m_value, mod_p, mod_r_inv); - m_is_trf = false; - } - -bool GFpElement::align_operands_res(const GFpElement& lhs, const GFpElement& rhs) //static - { - assert(lhs.mod_p == rhs.mod_p); - if(lhs.m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.mod_p_dash == lhs.mod_p_dash); - assert(rhs.mod_r == lhs.mod_r); - assert(rhs.mod_r_inv == lhs.mod_r_inv); - if(!lhs.m_is_trf && !rhs.m_is_trf) - { - return false; - } - else if(lhs.m_is_trf && rhs.m_is_trf) - { - return true; - } - else // one is transf., the other not - { - if(!lhs.m_is_trf) - { - lhs.trf_to_mres(); - assert(rhs.m_is_trf==true); - return true; - } - assert(rhs.m_is_trf==false); - assert(lhs.m_is_trf==true); - rhs.trf_to_mres(); // the only possibility left... - return true; - } - } - else // at least one of them does not use mm - // (so it is impossible that both use it) - { - if(lhs.m_is_trf) - { - lhs.trf_to_ordres(); - assert(rhs.m_is_trf == false); - return false; - } - if(rhs.m_is_trf) - { - rhs.trf_to_ordres(); - assert(lhs.m_is_trf == false); - return false; - } - return false; - } - assert(false); - } - -bool GFpElement::is_trf_to_mres() const - { - return m_is_trf; - } - -const BigInt& GFpElement::get_p() const - { - return (mod_p); - } - -const BigInt& GFpElement::get_value() const + m_value(value %p) { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - return m_value; - } - -const BigInt& GFpElement::get_mres() const - { - if(!m_use_montgm) - { - // does the following exception really make sense? - // wouldn't it be better to simply turn on montg.mult. when - // this explicit request is made? - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - if(!m_is_trf) - { - trf_to_mres(); - } - - return m_value; } GFpElement& GFpElement::operator+=(const GFpElement& rhs) { - GFpElement::align_operands_res(*this, rhs); - BigInt workspace = m_value; workspace += rhs.m_value; if(workspace >= mod_p) @@ -329,8 +38,6 @@ GFpElement& GFpElement::operator+=(const GFpElement& rhs) GFpElement& GFpElement::operator-=(const GFpElement& rhs) { - GFpElement::align_operands_res(*this, rhs); - BigInt workspace = m_value; workspace -= rhs.m_value; @@ -355,70 +62,18 @@ GFpElement& GFpElement::operator*= (u32bit rhs) GFpElement& GFpElement::operator*=(const GFpElement& rhs) { - assert(rhs.mod_p == mod_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.mod_p == mod_p); // is montgm. mult is on, then precomps must be there - assert(rhs.mod_p_dash == mod_p_dash); - assert(rhs.mod_r == mod_r); - if(!m_is_trf) - { - trf_to_mres(); - } - if(!rhs.m_is_trf) - { - rhs.trf_to_mres(); - } - BigInt workspace = m_value; - montg_mult(m_value, workspace, - rhs.m_value, mod_p, mod_p_dash); - } - else // ordinary multiplication - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - if(rhs.m_is_trf) - { - assert(rhs.m_use_montgm); - rhs.trf_to_ordres(); - } - - BigInt workspace = m_value; - workspace *= rhs.m_value; - workspace %= mod_p; - m_value = workspace; - } + BigInt workspace = m_value; + workspace *= rhs.m_value; + workspace %= mod_p; + m_value = workspace; return *this; } GFpElement& GFpElement::operator/=(const GFpElement& rhs) { - bool use_mres = GFpElement::align_operands_res(*this, rhs); - assert((this->m_is_trf && rhs.m_is_trf) || !(this->m_is_trf && rhs.m_is_trf)); - - if(use_mres) - { - assert(m_use_montgm && rhs.m_use_montgm); - GFpElement rhs_ordres(rhs); - rhs_ordres.trf_to_ordres(); - rhs_ordres.inverse_in_place(); - BigInt workspace = m_value; - workspace *= rhs_ordres.get_value(); - workspace %= mod_p; - m_value = workspace; - } - else - { - GFpElement inv_rhs(rhs); - inv_rhs.inverse_in_place(); - *this *= inv_rhs; - } + GFpElement inv_rhs(rhs); + inv_rhs.inverse_in_place(); + *this *= inv_rhs; return *this; } @@ -431,16 +86,6 @@ bool GFpElement::is_zero() GFpElement& GFpElement::inverse_in_place() { m_value = inverse_mod(m_value, mod_p); - - if(m_is_trf) - { - assert(m_use_montgm); - - m_value *= mod_r; - m_value *= mod_r; - m_value %= mod_p; - } - assert(m_value <= mod_p); return *this; } @@ -455,12 +100,6 @@ void GFpElement::swap(GFpElement& other) { std::swap(m_value, other.m_value); std::swap(mod_p, other.mod_p); - std::swap(mod_p_dash, other.mod_p_dash); - std::swap(mod_r, other.mod_r); - std::swap(mod_r_inv, other.mod_r_inv); - - std::swap<bool>(m_use_montgm,other.m_use_montgm); - std::swap<bool>(m_is_trf,other.m_is_trf); } std::ostream& operator<<(std::ostream& output, const GFpElement& elem) @@ -470,20 +109,8 @@ std::ostream& operator<<(std::ostream& output, const GFpElement& elem) bool operator==(const GFpElement& lhs, const GFpElement& rhs) { - if(lhs.get_p() != rhs.get_p()) - return false; - - // so the modulus is equal, now check the values - bool use_mres = GFpElement::align_operands_res(lhs, rhs); - - if(use_mres) - { - return (lhs.get_mres() == rhs.get_mres()); - } - else - { - return(lhs.get_value() == rhs.get_value()); - } + return (lhs.get_p() == rhs.get_p() && + lhs.get_value() == rhs.get_value()); } GFpElement operator+(const GFpElement& lhs, const GFpElement& rhs) diff --git a/src/math/gfpmath/gfp_element.h b/src/math/gfpmath/gfp_element.h index 5e1f73ec4..a13de0568 100644 --- a/src/math/gfpmath/gfp_element.h +++ b/src/math/gfpmath/gfp_element.h @@ -35,25 +35,13 @@ class BOTAN_DLL GFpElement * multiplications will be use when applying operators *, *= * @param p the prime number of the field * @param value the element value - * @param use_montgm whether this object will use Montgomery multiplication */ - GFpElement(const BigInt& p, const BigInt& value, bool use_montgm = true); + GFpElement(const BigInt& p, const BigInt& value); // GFpElement(const GFpElement& other) = default; - // const GFpElement& operator=(const GFpElement& other) = default; /** - * Switch Montgomery multiplcation optimizations ON - */ - void turn_on_sp_red_mul(); - - /** - * Switch Montgomery multiplcation optimizations OFF - */ - void turn_off_sp_red_mul(); - - /** * += Operator * @param rhs the GFpElement to add to the local value * @result *this @@ -111,51 +99,13 @@ class BOTAN_DLL GFpElement * return prime number of GF(p) * @result a prime number */ - const BigInt& get_p() const; + const BigInt& get_p() const { return mod_p; } /** * Return the represented value in GF(p) * @result The value in GF(p) */ - const BigInt& get_value() const; - - /** - * Tells whether this GFpElement is currently transformed to an m-residue, - * i.e. in the form x_bar = x * r mod m. - * @result true if it is currently transformed to its m-residue. - */ - bool is_trf_to_mres() const; - - /** - * Transforms this to x_bar = x * r mod m - * @result return the value x_bar. - */ - const BigInt& get_mres() const; - - /** - * Check, if montgomery multiplication is used. - * @result true, if montgomery multiplication is used, false otherwise - */ - bool is_use_montgm() const - { - return m_use_montgm; - } - - /** - * Transforms the arguments in such way that either both - * are in m-residue representation (returns true) or both are - * in ordinary residue representation (returns false). - * m-residue is prefered in case of ambiguity. - * does not toggle m_use_montgm of the arguments. - * Don't be confused about the constness of the arguments: - * the transformation between normal residue and m-residue is - * considered as leaving the object const. - * @param lhs the first operand to be aligned - * @param rhs the second operand to be aligned - * @result true if both are transformed to their m-residue, - * false it both are transformed to their normal residue. - */ - static bool align_operands_res(const GFpElement& lhs, const GFpElement& rhs); + const BigInt& get_value() const { return m_value; } /** * swaps the states of *this and other, does not throw! @@ -163,20 +113,8 @@ class BOTAN_DLL GFpElement */ void swap(GFpElement& other); private: - void ensure_montgm_precomp(); - void trf_to_mres() const; - void trf_to_ordres() const; - BigInt mod_p; // modulus - BigInt mod_p_dash; - BigInt mod_r; - BigInt mod_r_inv; - - mutable BigInt m_value; // ordinary residue or m-residue respectively - - // data members for montgomery multiplication - bool m_use_montgm; - mutable bool m_is_trf; // if m_value is montgomery + BigInt m_value; }; // relational operators diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp index f1d38f5fd..11708d3ea 100644 --- a/src/math/gfpmath/point_gfp.cpp +++ b/src/math/gfpmath/point_gfp.cpp @@ -57,24 +57,16 @@ PointGFp& PointGFp::operator+=(const PointGFp& rhs) GFpElement U1 = mX; GFpElement S1 = mY; - if(rhs.mZ != mC.get_mres_one()) - { - GFpElement rhs_z2 = rhs.mZ * rhs.mZ; - - U1 *= rhs_z2; - S1 *= rhs_z2 * rhs.mZ; - } + GFpElement rhs_z2 = rhs.mZ * rhs.mZ; + U1 *= rhs_z2; + S1 *= rhs_z2 * rhs.mZ; GFpElement U2 = rhs.mX; GFpElement S2 = rhs.mY; - if(mZ != mC.get_mres_one()) - { - GFpElement lhs_z2 = mZ * mZ; - - U2 *= lhs_z2; - S2 *= lhs_z2 * mZ; - } + GFpElement lhs_z2 = mZ * mZ; + U2 *= lhs_z2; + S2 *= lhs_z2 * mZ; GFpElement H(U2 - U1); GFpElement r(S2 - S1); @@ -103,20 +95,7 @@ PointGFp& PointGFp::operator+=(const PointGFp& rhs) GFpElement y(r * (U2-x) - z); - if(mZ == mC.get_mres_one()) - { - if(rhs.mZ != mC.get_mres_one()) - z = rhs.mZ * H; - else - z = H; - } - else if(rhs.mZ != mC.get_mres_one()) - { - U1 = mZ * rhs.mZ; - z = U1 * H; - } - else - z = mZ * H; + z = (mZ * rhs.mZ) * H; mX = x; mY = y; @@ -144,12 +123,8 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar) { // use montgomery mult. in this operation - this->turn_on_sp_red_mul(); - PointGFp H(this->mC); // create as zero - H.turn_on_sp_red_mul(); PointGFp P(*this); - P.turn_on_sp_red_mul(); BigInt m(scalar); if(m < BigInt(0)) @@ -210,13 +185,11 @@ PointGFp& PointGFp::mult2_in_place() S = x + x; - GFpElement a_z4 = mC.get_mres_a(); - if(mZ != mC.get_mres_one()) - { - GFpElement z2 = mZ * mZ; - a_z4 *= z2; - a_z4 *= z2; - } + GFpElement a_z4 = mC.get_a(); + + GFpElement z2 = mZ * mZ; + a_z4 *= z2; + a_z4 *= z2; GFpElement y(mX * mX); @@ -234,10 +207,7 @@ PointGFp& PointGFp::mult2_in_place() y = M * (S - x) - U; - if(mZ != mC.get_mres_one()) - z = mY * mZ; - else - z = mY; + z = mY * mZ; z = z + z; @@ -248,22 +218,6 @@ PointGFp& PointGFp::mult2_in_place() return *this; } -void PointGFp::turn_on_sp_red_mul() const - { - mX.turn_on_sp_red_mul(); - mY.turn_on_sp_red_mul(); - mZ.turn_on_sp_red_mul(); - - // also pretransform, otherwise - // we might have bad results with respect to - // performance because - // additions/subtractions in mult2_in_place() - // and op+= spread untransformed GFpElements - mX.get_mres(); - mY.get_mres(); - mZ.get_mres(); - } - /** * returns a point equivalent to *this but were * Z has value one, i.e. x and y correspond to diff --git a/src/math/gfpmath/point_gfp.h b/src/math/gfpmath/point_gfp.h index 08de259af..e413e2311 100644 --- a/src/math/gfpmath/point_gfp.h +++ b/src/math/gfpmath/point_gfp.h @@ -114,14 +114,6 @@ class BOTAN_DLL PointGFp const PointGFp& set_z_to_one() const; /** - * Turn on the special reduction multiplication (i.e. the - * Montgomery multiplication in the current implementation) for - * the coordinates. This enables fast execution of mult2_in_place() - * and operator+=(). - */ - void turn_on_sp_red_mul() const; - - /** * Return a point * where the coordinates are transformed * so that z equals one, |