diff options
| -rw-r--r-- | checks/ec_tests.cpp | 31 | ||||
| -rw-r--r-- | checks/gfpmath.cpp | 136 | ||||
| -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 |
8 files changed, 56 insertions, 701 deletions
diff --git a/checks/ec_tests.cpp b/checks/ec_tests.cpp index cf63cc529..3ff13a429 100644 --- a/checks/ec_tests.cpp +++ b/checks/ec_tests.cpp @@ -35,17 +35,6 @@ using namespace Botan; namespace { -void test_point_turn_on_sp_red_mul_simple() - { - std::cout << "." << std::flush; - - // setting up expected values - EC_Domain_Params dom_pars(get_EC_Dom_Pars_by_oid("1.3.36.3.3.2.8.1.1.5")); - PointGFp p(dom_pars.get_base_point()); - p.turn_on_sp_red_mul(); - CHECK(p.get_affine_x().get_value() != BigInt(0)); - } - void test_point_turn_on_sp_red_mul() { std::cout << "." << std::flush; @@ -79,8 +68,6 @@ void test_point_turn_on_sp_red_mul() PointGFp p_G2(p_G); - p_G2.turn_on_sp_red_mul(); - PointGFp r2 = d * p_G2; CHECK_MESSAGE(r1 == r2, "error with point mul after extra turn on sp red mul"); CHECK(r1.get_affine_x().get_value() != BigInt("0")); @@ -89,16 +76,12 @@ void test_point_turn_on_sp_red_mul() PointGFp p_r2 = r2; p_r1.mult2_in_place(); // wird für Fehler nicht gebraucht - p_r2.turn_on_sp_red_mul(); // 1. t_o() macht nur p_r2 kaputt - p_r2.turn_on_sp_red_mul(); // 2. t_o() macht auch p_r1 kaputt!!! p_r2.mult2_in_place(); // wird für Fehler nicht gebraucht CHECK_MESSAGE(p_r1.get_affine_x() == p_r2.get_affine_x(), "error with mult2 after extra turn on sp red mul"); CHECK(p_r1.get_affine_x().get_value() != BigInt("0")); CHECK(p_r2.get_affine_x().get_value() != BigInt("0")); r1.mult2_in_place(); - r2.turn_on_sp_red_mul(); - r2.turn_on_sp_red_mul(); r2.mult2_in_place(); CHECK_MESSAGE(r1 == r2, "error with mult2 after extra turn on sp red mul"); @@ -110,14 +93,10 @@ void test_point_turn_on_sp_red_mul() CHECK_MESSAGE(r1 == r2, "error with op+= after extra turn on sp red mul"); - p_G2.turn_on_sp_red_mul(); - r1 += p_G; r2 += p_G2; CHECK_MESSAGE(r1 == r2, "error with op+= after extra turn on sp red mul for both operands"); - p_G2.turn_on_sp_red_mul(); - r1.turn_on_sp_red_mul(); r1 += p_G; r2 += p_G2; @@ -196,7 +175,6 @@ void test_point_transformation () PointGFp q = p; //turn on montg. - p.turn_on_sp_red_mul(); CHECK_MESSAGE( p.get_jac_proj_x().get_value() == q.get_jac_proj_x().get_value(), "projective_x changed while turning on montg.!"); CHECK_MESSAGE( p.get_jac_proj_y().get_value() == q.get_jac_proj_y().get_value(), "projective_y changed while turning on montg.!"); CHECK_MESSAGE( p.get_jac_proj_z().get_value() == q.get_jac_proj_z().get_value(), "projective_z changed while turning on montg.!"); @@ -956,16 +934,12 @@ void test_gfp_curve_precomp_mres() BigInt p = curve1.get_p(); GFpElement x(p, BigInt("2304042084023")); GFpElement a1_or = curve1.get_a(); - CHECK(!a1_or.is_trf_to_mres()); - GFpElement b1_mr = curve1.get_mres_b(); - CHECK(b1_mr.is_trf_to_mres()); + GFpElement b1_mr = curve1.get_b(); - GFpElement a2_mr = curve2.get_mres_a(); - CHECK(a2_mr.is_trf_to_mres()); + GFpElement a2_mr = curve2.get_a(); GFpElement b2_or = curve2.get_b(); - CHECK(!b2_or.is_trf_to_mres()); GFpElement prodA = a1_or*b1_mr; GFpElement prodB = a2_mr*b2_or; @@ -1142,7 +1116,6 @@ void do_ec_tests(RandomNumberGenerator& rng) { std::cout << "Testing ECC: " << std::flush; - test_point_turn_on_sp_red_mul_simple(); test_point_turn_on_sp_red_mul(); test_coordinates(); test_point_transformation (); diff --git a/checks/gfpmath.cpp b/checks/gfpmath.cpp index 439b9be9b..18aa4f341 100644 --- a/checks/gfpmath.cpp +++ b/checks/gfpmath.cpp @@ -41,11 +41,6 @@ bool test_turn_on_sp_red_mul() GFpElement a2(23,15); GFpElement b2(23,18); - a2.turn_on_sp_red_mul(); - a2.turn_on_sp_red_mul(); - b2.turn_on_sp_red_mul(); - b2.turn_on_sp_red_mul(); - GFpElement c2 = a2*b2; if(c1 != c2) @@ -119,14 +114,10 @@ bool test_deep_montgm() //std::string s_value_b = "3"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a_trf(bi_prime, bi_value_a, true); - GFpElement gfp_a_ntrf(bi_prime, bi_value_a, false); - GFpElement gfp_b_trf(bi_prime, bi_value_b, true); - GFpElement gfp_b_ntrf(bi_prime, bi_value_b, false); - - //CHECK(!gfp_b_trf.is_trf_to_mres()); - gfp_b_trf.get_mres(); - gfp_a_trf.get_mres(); + GFpElement gfp_a_trf(bi_prime, bi_value_a); + GFpElement gfp_a_ntrf(bi_prime, bi_value_a); + GFpElement gfp_b_trf(bi_prime, bi_value_b); + GFpElement gfp_b_ntrf(bi_prime, bi_value_b); GFpElement c_trf(gfp_a_trf * gfp_b_trf); GFpElement c_ntrf(gfp_a_ntrf * gfp_b_ntrf); @@ -151,21 +142,13 @@ bool test_gfp_div_small_numbers() std::string s_value_b = "3"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b(bi_prime, bi_value_b, true); - GFpElement gfp_c(bi_prime, bi_value_b, false); - - CHECK(!gfp_a.is_trf_to_mres()); - //convert to montgomery - gfp_b.get_mres(); - CHECK(gfp_b.is_trf_to_mres()); - CHECK(!gfp_c.is_trf_to_mres()); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b(bi_prime, bi_value_b); + GFpElement gfp_c(bi_prime, bi_value_b); GFpElement res_div_m = gfp_a / gfp_b; - CHECK(res_div_m.is_trf_to_mres()); GFpElement res_div_n = gfp_a / gfp_c; - CHECK(!res_div_n.is_trf_to_mres()); CHECK_MESSAGE(res_div_n.get_value() == res_div_m.get_value(), "transformed result is not equal to untransformed result"); CHECK_MESSAGE(gfp_a.get_value() == s_value_a, "GFpElement has changed while division operation"); @@ -202,12 +185,9 @@ bool test_gfp_basics() std::string s_value_a = "3333333333333"; BigInt bi_value_a(s_value_a); - GFpElement gfp_a(bi_prime, bi_value_a, true); + GFpElement gfp_a(bi_prime, bi_value_a); CHECK(gfp_a.get_p() == s_prime); CHECK(gfp_a.get_value() == s_value_a); - CHECK(!gfp_a.is_trf_to_mres()); - gfp_a.get_mres(); - CHECK(gfp_a.is_trf_to_mres()); return pass; } @@ -222,8 +202,8 @@ bool test_gfp_addSubNegate() std::string s_value_a = "3333333333333"; BigInt bi_value_a(s_value_a); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b(bi_prime, bi_value_a, true); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b(bi_prime, bi_value_a); gfp_b.negate(); GFpElement zero = gfp_a + gfp_b; @@ -246,21 +226,13 @@ bool test_gfp_mult() std::string s_value_b = "4444444444444"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b(bi_prime, bi_value_b, true); - GFpElement gfp_c(bi_prime, bi_value_b, false); - - CHECK(!gfp_a.is_trf_to_mres()); - //convert to montgomery - gfp_b.get_mres(); - CHECK(gfp_b.is_trf_to_mres()); - CHECK(!gfp_c.is_trf_to_mres()); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b(bi_prime, bi_value_b); + GFpElement gfp_c(bi_prime, bi_value_b); GFpElement res_mult_m = gfp_a * gfp_b; - CHECK(res_mult_m.is_trf_to_mres()); GFpElement res_mult_n = gfp_a * gfp_c; - CHECK(!res_mult_n.is_trf_to_mres()); if(res_mult_n != res_mult_m) std::cout << gfp_a << " * " << gfp_b << " =? " @@ -281,21 +253,13 @@ bool test_gfp_div() std::string s_value_b = "4444444444444"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b(bi_prime, bi_value_b, true); - GFpElement gfp_c(bi_prime, bi_value_b, false); - - CHECK(!gfp_a.is_trf_to_mres()); - //convert to montgomery - gfp_b.get_mres(); - CHECK(gfp_b.is_trf_to_mres()); - CHECK(!gfp_c.is_trf_to_mres()); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b(bi_prime, bi_value_b); + GFpElement gfp_c(bi_prime, bi_value_b); GFpElement res_div_m = gfp_a / gfp_b; - CHECK(res_div_m.is_trf_to_mres()); GFpElement res_div_n = gfp_a / gfp_c; - CHECK(!res_div_n.is_trf_to_mres()); CHECK_MESSAGE(res_div_n.get_value() == res_div_m.get_value(), "transformed result is not equal to untransformed result"); CHECK_MESSAGE(gfp_a.get_value() == s_value_a, "GFpElement has changed while division operation"); @@ -322,24 +286,13 @@ bool test_gfp_add() std::string s_value_b = "4444444444444"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b(bi_prime, bi_value_b, true); - GFpElement gfp_c(bi_prime, bi_value_b, true); - - CHECK(!gfp_a.is_trf_to_mres()); - //convert to montgomery - gfp_b.get_mres(); - CHECK(gfp_b.is_trf_to_mres()); - CHECK(!gfp_c.is_trf_to_mres()); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b(bi_prime, bi_value_b); + GFpElement gfp_c(bi_prime, bi_value_b); GFpElement res_add_m = gfp_a + gfp_b; - CHECK(res_add_m.is_trf_to_mres()); GFpElement res_add_n = gfp_a + gfp_c; - // commented out by patrick, behavior is clear: - // rhs might be transformed, lhs never - // for now, this behavior is only intern, doesn't matter for programm function - // CHECK_MESSAGE(res_add_n.is_trf_to_mres(), "!! Falko: NO FAIL, wrong test, please repair"); // clear: rhs might be transformed, lhs never CHECK(res_add_n.get_value() == res_add_m.get_value()); return pass; @@ -358,30 +311,14 @@ bool test_gfp_sub() std::string s_value_b = "4444444444444"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b(bi_prime, bi_value_b, true); - GFpElement gfp_c(bi_prime, bi_value_b, true); - - CHECK(!gfp_a.is_trf_to_mres()); - //convert to montgomery - gfp_b.get_mres(); - CHECK(gfp_b.is_trf_to_mres()); - CHECK(!gfp_c.is_trf_to_mres()); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b(bi_prime, bi_value_b); + GFpElement gfp_c(bi_prime, bi_value_b); GFpElement res_sub_m = gfp_b - gfp_a; - CHECK(res_sub_m.is_trf_to_mres()); - CHECK(gfp_a.is_trf_to_mres()); // added by Falko GFpElement res_sub_n = gfp_c - gfp_a; - // commented out by psona, behavior is clear: - // rhs might be transformed, lhs never - // for now, this behavior is only intern, doesn't matter for programm function - // CHECK_MESSAGE(!res_sub_n.is_trf_to_mres(), "!! Falko: NO FAIL, wrong test, please repair"); // falsche - // Erwartung: a wurde durch die operation oben auch - // ins m-residue transformiert, daher passiert das hier auch mit - // c, und das Ergebnis ist es auch - CHECK(res_sub_n.get_value() == res_sub_m.get_value()); return pass; } @@ -399,28 +336,9 @@ bool test_more_gfp_div() std::string s_value_b = "4444444444444"; BigInt bi_value_b(s_value_b); - GFpElement gfp_a(bi_prime, bi_value_a, true); - GFpElement gfp_b_trf(bi_prime, bi_value_b, true); - GFpElement gfp_b_ntrf(bi_prime, bi_value_b, false); - - CHECK(!gfp_b_trf.is_trf_to_mres()); - gfp_b_trf.get_mres(); - CHECK(gfp_b_trf.is_trf_to_mres()); - - CHECK(!gfp_a.is_trf_to_mres()); - - bool exc_ntrf = false; - try - { - gfp_b_ntrf.get_mres(); - } - catch(Botan::Illegal_Transformation e) - { - exc_ntrf = true; - } - CHECK(exc_ntrf); - - CHECK(!gfp_b_ntrf.is_trf_to_mres()); + GFpElement gfp_a(bi_prime, bi_value_a); + GFpElement gfp_b_trf(bi_prime, bi_value_b); + GFpElement gfp_b_ntrf(bi_prime, bi_value_b); CHECK_MESSAGE(gfp_b_trf == gfp_b_ntrf, "b is not equal to itself (trf)"); @@ -502,8 +420,6 @@ bool test_inv_in_place() BigInt mod(173); GFpElement a1(mod, 288); - a1.turn_on_sp_red_mul(); - a1.get_mres(); // enforce the conversion GFpElement a1_inv(a1); a1_inv.inverse_in_place(); @@ -529,8 +445,6 @@ bool test_op_eq() BigInt mod(173); GFpElement a1(mod, 299); - a1.turn_on_sp_red_mul(); - a1.get_mres(); // enforce the conversion GFpElement a2(mod, 288); CHECK_MESSAGE(a1 != a2, "error with GFpElement comparison"); return pass; 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, |