diff options
49 files changed, 1061 insertions, 3398 deletions
diff --git a/checks/ec_tests.cpp b/checks/ec_tests.cpp index 1820db1b6..637e3d988 100644 --- a/checks/ec_tests.cpp +++ b/checks/ec_tests.cpp @@ -18,7 +18,6 @@ void do_ec_tests(RandomNumberGenerator&) { return; } #include <botan/numthry.h> #include <botan/curve_gfp.h> #include <botan/point_gfp.h> -#include <botan/gfp_element.h> #include <botan/ecdsa.h> using namespace Botan; @@ -35,15 +34,28 @@ using namespace Botan; namespace { -void test_point_turn_on_sp_red_mul_simple() +PointGFp create_random_point(RandomNumberGenerator& rng, + const CurveGFp& curve) { - std::cout << "." << std::flush; + const BigInt& p = curve.get_p(); - // 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)); + const Modular_Reducer& mod_p = curve.mod_p(); + + while(true) + { + BigInt x(rng, p.bits()); + + BigInt x3 = mod_p.multiply(x, mod_p.square(x)); + + BigInt ax = mod_p.multiply(curve.get_a(), x); + + BigInt bx3 = mod_p.multiply(curve.get_b(), x3); + + BigInt y = mod_p.reduce(ax + bx3); + + if(ressol(y, p) > 0) + return PointGFp(curve, x, y); + } } void test_point_turn_on_sp_red_mul() @@ -69,55 +81,44 @@ void test_point_turn_on_sp_red_mul() BigInt bi_p_secp = BigInt::decode(sv_p_secp.begin(), sv_p_secp.size()); BigInt bi_a_secp = BigInt::decode(sv_a_secp.begin(), sv_a_secp.size()); BigInt bi_b_secp = BigInt::decode(sv_b_secp.begin(), sv_b_secp.size()); - CurveGFp secp160r1(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP(sv_G_secp_comp, secp160r1); BigInt d("459183204582304"); PointGFp r1 = d * p_G; - CHECK(r1.get_affine_x().get_value() != BigInt("0")); + CHECK(r1.get_affine_x() != BigInt("0")); 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")); + CHECK(r1.get_affine_x() != BigInt("0")); PointGFp p_r1 = r1; 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 + p_r1 *= 2; + p_r2 *= 2; 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(); + CHECK(p_r1.get_affine_x() != BigInt("0")); + CHECK(p_r2.get_affine_x() != BigInt("0")); + r1 *= 2; - r2.turn_on_sp_red_mul(); - r2.turn_on_sp_red_mul(); - r2.mult2_in_place(); + r2 *= 2; CHECK_MESSAGE(r1 == r2, "error with mult2 after extra turn on sp red mul"); CHECK_MESSAGE(r1.get_affine_x() == r2.get_affine_x(), "error with mult2 after extra turn on sp red mul"); - CHECK(r1.get_affine_x().get_value() != BigInt("0")); - //std::cout << "r1 x = " << r1.get_affine_x() << endl; + CHECK(r1.get_affine_x() != BigInt("0")); r1 += p_G; r2 += p_G2; 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; @@ -148,26 +149,22 @@ void test_coordinates() BigInt bi_p_secp = BigInt::decode ( sv_p_secp.begin(), sv_p_secp.size() ); BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1 (bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); PointGFp p0 = p_G; - PointGFp p1 = p_G.mult2_in_place(); - PointGFp point_exp(secp160r1, GFpElement(bi_p_secp, exp_affine_x), GFpElement(bi_p_secp, exp_affine_y)); - try - { - point_exp.check_invariants(); - } - catch (Illegal_Point e) - { - assert(false); - } + PointGFp p1 = p_G * 2; + PointGFp point_exp(secp160r1, exp_affine_x, exp_affine_y); + point_exp.check_invariants(); + + if(p1.get_jac_proj_x() != exp_x) + std::cout << p1.get_jac_proj_x() << " != " << exp_x << "\n"; + if(p1.get_jac_proj_y() != exp_y) + std::cout << p1.get_jac_proj_y() << " != " << exp_y << "\n"; + if(p1.get_jac_proj_z() != exp_z) + std::cout << p1.get_jac_proj_z() << " != " << exp_z << "\n"; - // testarea - CHECK( p1.get_jac_proj_x().get_value() == exp_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_y); - CHECK( p1.get_jac_proj_z().get_value() == exp_z); - CHECK_MESSAGE( p1.get_affine_x().get_value() == exp_affine_x, " p1_x = " << p1.get_affine_x().get_value() << "\n" << "exp_x = " << exp_affine_x << "\n"); - CHECK_MESSAGE( p1.get_affine_y().get_value() == exp_affine_y, " p1_y = " << p1.get_affine_y().get_value() << "\n" << "exp_y = " << exp_affine_y << "\n"); + CHECK_MESSAGE( p1.get_affine_x() == exp_affine_x, " p1_x = " << p1.get_affine_x() << "\n" << "exp_x = " << exp_affine_x << "\n"); + CHECK_MESSAGE( p1.get_affine_y() == exp_affine_y, " p1_y = " << p1.get_affine_y() << "\n" << "exp_y = " << exp_affine_y << "\n"); } @@ -196,12 +193,11 @@ 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.!"); - CHECK_MESSAGE( p.get_affine_x().get_value() == q.get_affine_x().get_value(), "affine_x changed while turning on montg.!"); - CHECK_MESSAGE( p.get_affine_y().get_value() == q.get_affine_y().get_value(), "affine_y changed while turning on montg.!"); + CHECK_MESSAGE( p.get_jac_proj_x() == q.get_jac_proj_x(), "projective_x changed while turning on montg.!"); + CHECK_MESSAGE( p.get_jac_proj_y() == q.get_jac_proj_y(), "projective_y changed while turning on montg.!"); + CHECK_MESSAGE( p.get_jac_proj_z() == q.get_jac_proj_z(), "projective_z changed while turning on montg.!"); + CHECK_MESSAGE( p.get_affine_x() == q.get_affine_x(), "affine_x changed while turning on montg.!"); + CHECK_MESSAGE( p.get_affine_y() == q.get_affine_y(), "affine_y changed while turning on montg.!"); } void test_point_mult () @@ -227,7 +223,7 @@ void test_point_mult () BigInt bi_p_secp = BigInt::decode(sv_p_secp.begin(), sv_p_secp.size()); BigInt bi_a_secp = BigInt::decode(sv_a_secp.begin(), sv_a_secp.size()); BigInt bi_b_secp = BigInt::decode(sv_b_secp.begin(), sv_b_secp.size()); - CurveGFp secp160r1(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP(sv_G_secp_comp, secp160r1); SecureVector<byte> sv_G_dec = EC2OSP(p_G,0x01); @@ -235,77 +231,10 @@ void test_point_mult () SecureVector<byte> sv_d_U = decode_hex(str_d_U); BigInt d_U = BigInt::decode(sv_d_U.begin(), sv_d_U.size()); PointGFp Q_U = d_U * p_G; - CHECK( Q_U.get_jac_proj_x().get_value() == exp_Qx); - CHECK( Q_U.get_jac_proj_y().get_value() == exp_Qy); - CHECK( Q_U.get_jac_proj_z().get_value() == exp_Qz); - } - -#if 0 -void test_montgm_calc_R () - { - // this tests isnt´t correct anymore. the determination of R has changed - // to be 0 mod word_range. - - // setting up (expected) values - BigInt prime_modulus(101); - u64bit n = prime_modulus.bits(); - BigInt exp_R(128); - // function under test - BigInt calc_R = montgm_calc_r_oddmod(prime_modulus); - CHECK_MESSAGE(exp_R == calc_R, "exp_R = " << exp_R << ", calc_R = " << calc_R << ", n = " << n << "\n"); - - } -#endif - -#if 0 -void test_naive_montg_mult () - { - std::cout << "." << std::flush; - - BigInt a_bar(1); - BigInt b_bar(2); - BigInt m(11); - BigInt m_dash(13); - BigInt r(5); - //BigInt test_res = montg_mult(a_bar, b_bar, m, m_dash, r); - //cout << "test_res = " << test_res << "\n"; - GFpElement a_norm_mult(11, 3); - GFpElement b_norm_mult(11, 5); - GFpElement c_norm_mult = a_norm_mult * b_norm_mult; - //cout << "c_norm_mult = " << c_norm_mult << "\n"; - GFpElement a_mm(11, 3, true); - GFpElement b_mm(11, 5, true); - GFpElement c_mm = a_mm * b_mm; - //cout << "c_mm = " << c_mm << "\n"; - CHECK_MESSAGE(c_norm_mult == c_mm, "c_norm_mult = " << c_norm_mult << "\n" << "c_mm = " << c_mm << "\n"); - } -#endif - -#if 0 - -void test_trf_mres () - { - // this tests isnt´t correct anymore. the determination of R has changed - // to be 0 mod word_range. - - // - BigInt modulus(11); - BigInt r = montgm_calc_r_oddmod(modulus); - //cout << "r = " << r << "\n"; - BigInt r_inv = inverse_mod(r, modulus); - //cout << "r_inv = " << r_inv << "\n"; - // see C43: - BigInt exp_m_dash(13); - BigInt calc_m_dash = montgm_calc_m_dash(r, modulus, r_inv); - CHECK_MESSAGE(exp_m_dash == calc_m_dash, "exp_m_dash = " << exp_m_dash << "\n" << "calc_m_dash = " << calc_m_dash << "\n"); - BigInt ord_res(7); - BigInt exp_m_res(2); // see C43 - BigInt calc_m_res = montg_trf_to_mres(ord_res, r, modulus); - CHECK_MESSAGE(calc_m_res == exp_m_res, "calc_m_res = " << calc_m_res << "\nexp_m_res = " << exp_m_res); - BigInt calc_ord_res_back = montg_trf_to_ordres(calc_m_res,modulus, r_inv); - CHECK_MESSAGE(ord_res == calc_ord_res_back, "ord_res = " << ord_res << "\ncalc_ord_res_back = " << calc_ord_res_back << "\n"); + CHECK( Q_U.get_jac_proj_x() == exp_Qx); + CHECK( Q_U.get_jac_proj_y() == exp_Qy); + CHECK( Q_U.get_jac_proj_z() == exp_Qz); } -#endif void test_point_negative() { @@ -329,20 +258,20 @@ void test_point_negative() BigInt bi_p_secp = BigInt::decode ( sv_p_secp.begin(), sv_p_secp.size() ); BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); - PointGFp p1 = p_G.mult2_in_place(); + PointGFp p1 = p_G *= 2; - CHECK( p1.get_jac_proj_x().get_value() == exp_p1_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_p1_y); + CHECK( p1.get_jac_proj_x() == exp_p1_x); + CHECK( p1.get_jac_proj_y() == exp_p1_y); //cout << "p1.y_proj = " << p1.get_jac_proj_y() << "\n"; PointGFp p1_neg = p1.negate(); //cout << "p1_neg.y_proj = " << p1_neg.get_jac_proj_y() << "\n"; //p1.negate(); - BigInt calc_y_value = p1_neg.get_jac_proj_y().get_value(); - BigInt calc_z_value = p1_neg.get_jac_proj_z().get_value(); - CHECK( p1_neg.get_jac_proj_x().get_value() == exp_p1_neg_x); + BigInt calc_y_value = p1_neg.get_jac_proj_y(); + BigInt calc_z_value = p1_neg.get_jac_proj_z(); + CHECK( p1_neg.get_jac_proj_x() == exp_p1_neg_x); CHECK_MESSAGE( calc_y_value == exp_p1_neg_y, "calc_y_value = " << calc_y_value << "\nexp_p1_neg_v = " << exp_p1_neg_y); //CHECK_MESSAGE( calc_z_value == exp_p1_neg_y, "calc_y_value = " << calc_y_value << "\nexp_p1_neg_v = " << exp_p1_neg_y); } @@ -357,24 +286,15 @@ void test_zeropoint() BigInt bi_p_secp("0xffffffffffffffffffffffffffffffff7fffffff"); BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); BigInt bi_p1_xval ("1340569834321789103897171369812910390864714275730"); BigInt bi_p1_yval ("1270827321510686389126940426305655825361326281787"); BigInt bi_p1_zval ("407040228325808215747982915914693784055965283940"); - GFpElement elem_p1_x(bi_p_secp, bi_p1_xval); - GFpElement elem_p1_y(bi_p_secp, bi_p1_yval); - GFpElement elem_p1_z(bi_p_secp, bi_p1_zval); - - - PointGFp p1(secp160r1,elem_p1_x, elem_p1_y, elem_p1_z); - + PointGFp p1(secp160r1, bi_p1_xval, bi_p1_yval, bi_p1_zval); p1.check_invariants(); p1 -= p1; - // cout << "p1 x " << p1.get_jac_proj_x().get_value() << "\n"; - // cout << "p1 y " << p1.get_jac_proj_y().get_value() << "\n"; - // cout << "p1 z " << p1.get_jac_proj_z().get_value() << "\n"; CHECK_MESSAGE( p1.is_zero(), "p - q with q = p is not zero!"); } @@ -387,7 +307,7 @@ void test_zeropoint_enc_dec() BigInt bi_p_secp("0xffffffffffffffffffffffffffffffff7fffffff"); BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); - CurveGFp curve ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p(curve); CHECK_MESSAGE( p.is_zero(), "by constructor created zeropoint is no zeropoint!"); @@ -417,17 +337,13 @@ void test_calc_with_zeropoint() BigInt bi_p_secp("0xffffffffffffffffffffffffffffffff7fffffff"); BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); - CurveGFp curve ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); BigInt bi_p1_xval ("1340569834321789103897171369812910390864714275730"); BigInt bi_p1_yval ("1270827321510686389126940426305655825361326281787"); BigInt bi_p1_zval ("407040228325808215747982915914693784055965283940"); - GFpElement elem_p1_x(bi_p_secp, bi_p1_xval); - GFpElement elem_p1_y(bi_p_secp, bi_p1_yval); - GFpElement elem_p1_z(bi_p_secp, bi_p1_zval); - - PointGFp p(curve,elem_p1_x, elem_p1_y, elem_p1_z); + PointGFp p(curve, bi_p1_xval, bi_p1_yval, bi_p1_zval); p.check_invariants(); CHECK_MESSAGE( !p.is_zero(), "created is zeropoint, shouldn't be!"); @@ -466,22 +382,16 @@ void test_add_point() BigInt bi_p_secp = BigInt::decode ( sv_p_secp.begin(), sv_p_secp.size() ); BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); PointGFp p0 = p_G; - PointGFp p1 = p_G.mult2_in_place(); + PointGFp p1 = p_G *= 2; - PointGFp expected ( secp160r1, GFpElement(bi_p_secp, BigInt(exp_add_x)), - GFpElement(bi_p_secp, BigInt(exp_add_y)), GFpElement(bi_p_secp, BigInt(exp_add_z))); + PointGFp expected(secp160r1, exp_add_x, exp_add_y, exp_add_z); p1 += p0; CHECK(p1 == expected); -#if 0 - CHECK( p1.get_jac_proj_x().get_value() == exp_add_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_add_y); - CHECK( p1.get_jac_proj_z().get_value() == exp_add_z); -#endif } void test_sub_point() @@ -505,22 +415,16 @@ void test_sub_point() BigInt bi_p_secp = BigInt::decode ( sv_p_secp.begin(), sv_p_secp.size() ); BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); PointGFp p0 = p_G; - PointGFp p1 = p_G.mult2_in_place(); + PointGFp p1 = p_G *= 2; p1 -= p0; - PointGFp expected ( secp160r1, GFpElement(bi_p_secp, BigInt(exp_sub_x)), - GFpElement(bi_p_secp, BigInt(exp_sub_y)), GFpElement(bi_p_secp, BigInt(exp_sub_z))); - CHECK(p1 == expected); -#if 0 - CHECK( p1.get_jac_proj_x().get_value() == exp_sub_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_sub_y); - CHECK( p1.get_jac_proj_z().get_value() == exp_sub_z); -#endif + PointGFp expected(secp160r1, exp_sub_x, exp_sub_y, exp_sub_z); + CHECK(p1 == expected); } void test_mult_point() @@ -530,7 +434,6 @@ void test_mult_point() //Setting up expected values BigInt exp_mult_x(std::string("967697346845926834906555988570157345422864716250")); BigInt exp_mult_y(std::string("512319768365374654866290830075237814703869061656")); - BigInt exp_mult_z(std::string("1")); // precalculation std::string p_secp = "ffffffffffffffffffffffffffffffff7fffffff"; @@ -544,23 +447,17 @@ void test_mult_point() BigInt bi_p_secp = BigInt::decode ( sv_p_secp.begin(), sv_p_secp.size() ); BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); PointGFp p0 = p_G; - PointGFp p1 = p_G.mult2_in_place(); + PointGFp p1 = p_G *= 2; - p1 *= p0.get_jac_proj_x().get_value(); + p1 *= p0.get_jac_proj_x(); - PointGFp expected ( secp160r1, GFpElement(bi_p_secp, BigInt(exp_mult_x)), - GFpElement(bi_p_secp, BigInt(exp_mult_y)), GFpElement(bi_p_secp, BigInt(exp_mult_z))); - CHECK(p1 == expected); + PointGFp expected(secp160r1, exp_mult_x, exp_mult_y); -#if 0 - CHECK( p1.get_jac_proj_x().get_value() == exp_mult_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_mult_y); - CHECK( p1.get_jac_proj_z().get_value() == exp_mult_z); -#endif + CHECK(p1 == expected); } void test_basic_operations() @@ -601,59 +498,42 @@ void test_basic_operations() BigInt bi_p_secp = BigInt::decode ( sv_p_secp.begin(), sv_p_secp.size() ); BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); + PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); PointGFp p0 = p_G; - PointGFp p1 = p_G.mult2_in_place(); + PointGFp p1 = p_G *= 2; // check that all points have correct values - CHECK( p1.get_jac_proj_x().get_value() == exp_p1_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_p1_y); - CHECK( p1.get_jac_proj_z().get_value() == exp_p1_z); + CHECK( p1.get_jac_proj_x() == exp_p1_x); + CHECK( p1.get_jac_proj_y() == exp_p1_y); + CHECK( p1.get_jac_proj_z() == exp_p1_z); - PointGFp expected ( secp160r1, GFpElement(bi_p_secp, exp_p0_x), - GFpElement(bi_p_secp, exp_p0_y), GFpElement(bi_p_secp, exp_p0_z)); + PointGFp expected(secp160r1, exp_p0_x, exp_p0_y, exp_p0_z); CHECK(p0 == expected); -#if 0 - CHECK( p0.get_jac_proj_x().get_value() == exp_p0_x); - CHECK( p0.get_jac_proj_y().get_value() == exp_p0_y); - CHECK( p0.get_jac_proj_z().get_value() == exp_p0_z); -#endif PointGFp simplePlus= p1 + p0; - PointGFp exp_simplePlus ( secp160r1, GFpElement(bi_p_secp, exp_plus_x), - GFpElement(bi_p_secp, exp_plus_y), GFpElement(bi_p_secp, exp_plus_z)); + PointGFp exp_simplePlus(secp160r1, exp_plus_x, exp_plus_y, exp_plus_z); CHECK(simplePlus == exp_simplePlus); -#if 0 - CHECK( simplePlus.get_jac_proj_x().get_value() == exp_plus_x); - CHECK( simplePlus.get_jac_proj_y().get_value() == exp_plus_y); - CHECK( simplePlus.get_jac_proj_z().get_value() == exp_plus_z); -#endif PointGFp simpleMinus= p1 - p0; - PointGFp exp_simpleMinus ( secp160r1, GFpElement(bi_p_secp, exp_minus_x), - GFpElement(bi_p_secp, exp_minus_y), GFpElement(bi_p_secp, exp_minus_z)); + PointGFp exp_simpleMinus(secp160r1, exp_minus_x, exp_minus_y, exp_minus_z); CHECK(simpleMinus == exp_simpleMinus); -#if 0 - CHECK( simpleMinus.get_jac_proj_x().get_value() == exp_minus_x); - CHECK( simpleMinus.get_jac_proj_y().get_value() == exp_minus_y); - CHECK( simpleMinus.get_jac_proj_z().get_value() == exp_minus_z); -#endif PointGFp simpleMult= p1 * 123456789; - CHECK( simpleMult.get_jac_proj_x().get_value() == exp_mult_x); - CHECK( simpleMult.get_jac_proj_y().get_value() == exp_mult_y); - CHECK( simpleMult.get_jac_proj_z().get_value() == exp_mult_z); + CHECK( simpleMult.get_jac_proj_x() == exp_mult_x); + CHECK( simpleMult.get_jac_proj_y() == exp_mult_y); + CHECK( simpleMult.get_jac_proj_z() == exp_mult_z); // check that all initial points hasn't changed - CHECK( p1.get_jac_proj_x().get_value() == exp_p1_x); - CHECK( p1.get_jac_proj_y().get_value() == exp_p1_y); - CHECK( p1.get_jac_proj_z().get_value() == exp_p1_z); + CHECK( p1.get_jac_proj_x() == exp_p1_x); + CHECK( p1.get_jac_proj_y() == exp_p1_y); + CHECK( p1.get_jac_proj_z() == exp_p1_z); - CHECK( p0.get_jac_proj_x().get_value() == exp_p0_x); - CHECK( p0.get_jac_proj_y().get_value() == exp_p0_y); - CHECK( p0.get_jac_proj_z().get_value() == exp_p0_z); + CHECK( p0.get_jac_proj_x() == exp_p0_x); + CHECK( p0.get_jac_proj_y() == exp_p0_y); + CHECK( p0.get_jac_proj_z() == exp_p0_z); } void test_enc_dec_compressed_160() @@ -677,7 +557,7 @@ void test_enc_dec_compressed_160() BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); SecureVector<byte> sv_result = EC2OSP(p_G, PointGFp::COMPRESSED); @@ -706,7 +586,7 @@ void test_enc_dec_compressed_256() BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 ); SecureVector<byte> sv_result = EC2OSP(p_G, PointGFp::COMPRESSED); @@ -737,7 +617,7 @@ void test_enc_dec_uncompressed_112() BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_uncomp, secp160r1 ); SecureVector<byte> sv_result = EC2OSP(p_G, PointGFp::UNCOMPRESSED); @@ -766,7 +646,7 @@ void test_enc_dec_uncompressed_521() BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp160r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_uncomp, secp160r1 ); @@ -798,7 +678,7 @@ void test_enc_dec_uncompressed_521_prime_too_large() BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); - CurveGFp secp521r1 ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp secp521r1 (bi_p_secp, bi_a_secp, bi_b_secp); std::unique_ptr<PointGFp> p_G; bool exc = false; try @@ -812,11 +692,6 @@ void test_enc_dec_uncompressed_521_prime_too_large() } CHECK_MESSAGE(exc, "attempt of creation of point on curve with too high prime did not throw an exception"); -#if 0 - cout << "mX == " << p_G.get_jac_proj_x() << endl; - std::cout << "mY == " << p_G.get_jac_proj_y() << endl; - std::cout << "mZ == " << p_G.get_jac_proj_x() << endl; -#endif //SecureVector<byte> sv_result = EC2OSP(p_G, PointGFp::UNCOMPRESSED); //string result = hex_encode(sv_result.begin(), sv_result.size()); //string exp_result = hex_encode(sv_G_secp_uncomp.begin(), sv_G_secp_uncomp.size()); @@ -859,7 +734,7 @@ void test_cdc_curve_33() BigInt bi_a_secp("0xa377dede6b523333d36c78e9b0eaa3bf48ce93041f6d4fc34014d08f6833807498deedd4290101c5866e8dfb589485d13357b9e78c2d7fbe9fe"); BigInt bi_b_secp("0xa9acf8c8ba617777e248509bcb4717d4db346202bf9e352cd5633731dd92a51b72a4dc3b3d17c823fcc8fbda4da08f25dea89046087342595a7"); - CurveGFp curve( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_uncomp, curve); bool exc = false; try @@ -878,57 +753,43 @@ void test_more_zeropoint() std::cout << "." << std::flush; // by Falko - - std::string G = "024a96b5688ef573284664698968c38bb913cbfc82"; SecureVector<byte> sv_G_secp_comp = decode_hex ( G ); BigInt bi_p("0xffffffffffffffffffffffffffffffff7fffffff"); BigInt bi_a("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); - CurveGFp curve( GFpElement ( bi_p,bi_a ), GFpElement ( bi_p, bi_b ), bi_p ); + CurveGFp curve(bi_p, bi_a, bi_b); BigInt bi_p1_xval ("1340569834321789103897171369812910390864714275730"); BigInt bi_p1_yval ("1270827321510686389126940426305655825361326281787"); BigInt bi_p1_zval ("407040228325808215747982915914693784055965283940"); - GFpElement elem_p1_x(bi_p, bi_p1_xval); - GFpElement elem_p1_y(bi_p, bi_p1_yval); - GFpElement elem_p1_z(bi_p, bi_p1_zval); - - PointGFp p1(curve,elem_p1_x, elem_p1_y, elem_p1_z); + PointGFp p1(curve, bi_p1_xval, bi_p1_yval, bi_p1_zval); p1.check_invariants(); PointGFp minus_p1 = -p1; minus_p1.check_invariants(); PointGFp shouldBeZero = p1 + minus_p1; shouldBeZero.check_invariants(); - GFpElement x1 = p1.get_affine_x(); - GFpElement y1 = p1.get_affine_y(); - GFpElement shouldBeY2 = -y1; + BigInt y1 = p1.get_affine_y(); + y1 = curve.get_p() - y1; - CHECK_MESSAGE(minus_p1.get_affine_x() == x1, "problem with minus_p1 : x"); - CHECK_MESSAGE(minus_p1.get_affine_y() == shouldBeY2, "problem with minus_p1 : y"); + CHECK_MESSAGE(p1.get_affine_x() == minus_p1.get_affine_x(), + "problem with minus_p1 : x"); + CHECK_MESSAGE(minus_p1.get_affine_y() == y1, + "problem with minus_p1 : y"); PointGFp zero(curve); zero.check_invariants(); CHECK_MESSAGE(p1 + zero == p1, "addition of zero modified point"); -#if 0 - std::cout << "sbz x " << shouldBeZero.get_jac_proj_x().get_value() << "\n"; - std::cout << "sbz y " << shouldBeZero.get_jac_proj_y().get_value() << "\n"; - std::cout << "sbz z " << shouldBeZero.get_jac_proj_z().get_value() << "\n"; -#endif - CHECK_MESSAGE( shouldBeZero.is_zero(), "p - q with q = p is not zero!"); } void test_mult_by_order() { std::cout << "." << std::flush; - // std::cout << "starting test_mult_by_order..." << endl; - - // generate point //EC_Domain_Params dom_pars = global_config().get_ec_dompar("1.3.132.0.8"); @@ -936,79 +797,9 @@ void test_mult_by_order() EC_Domain_Params dom_pars = get_EC_Dom_Pars_by_oid("1.3.132.0.8"); PointGFp p = dom_pars.get_base_point(); PointGFp shouldBeZero = p * dom_pars.get_order(); -#if 0 - cout << "sbz x " << shouldBeZero.get_jac_proj_x().get_value() << "\n"; - std::cout << "sbz y " << shouldBeZero.get_jac_proj_y().get_value() << "\n"; - std::cout << "sbz z " << shouldBeZero.get_jac_proj_z().get_value() << "\n"; -#endif - CHECK_MESSAGE(shouldBeZero.is_zero(), "G * order != O"); - } - -void test_gfp_curve_precomp_mres() - { - std::cout << "." << std::flush; - - - //EC_Domain_Params parA("1.2.840.10045.3.1.1"); - EC_Domain_Params parA(get_EC_Dom_Pars_by_oid("1.2.840.10045.3.1.1")); - CurveGFp curve1 = parA.get_curve(); - CurveGFp curve2 = parA.get_curve(); - 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 a2_mr = curve2.get_mres_a(); - CHECK(a2_mr.is_trf_to_mres()); - - 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; - CHECK(prodA == prodB); - - CHECK(a1_or * x == a2_mr * x); - CHECK(x* a1_or == a1_or * x); - CHECK(x* a1_or == x * a2_mr); - CHECK(x* a1_or == a2_mr * x); - CHECK(a1_or + a2_mr == a2_mr + a1_or); - CHECK(a1_or + b1_mr == a2_mr + b1_mr); - CHECK(a1_or + x == a2_mr + x); - } - -#if 0 -void test_point_worksp() - { - - EC_Domain_Params dom_pars(get_EC_Dom_Pars_by_oid("1.3.132.0.8")); - std::shared_ptr<std::vector<GFpElement> > worksp1; - assert(worksp1.get() == 0); - { - PointGFp p = dom_pars.get_base_point(); - worksp1 = p.get_worksp_gfp(); - } - PointGFp p2 = dom_pars.get_base_point(); - p2.set_worksp_gfp(worksp1); - PointGFp p3 = p2*6; - PointGFp p4 = dom_pars.get_base_point(); - p4 *= 6; - CHECK_MESSAGE(p4 == p3,"points are not equal" ); - p2 *= 10; - for(int i=0; i<3; i++) - { - - PointGFp p5 = dom_pars.get_base_point(); - p5.set_worksp_gfp(worksp1); - p5 *= 10; - CHECK(p5 == p2); - } + CHECK_MESSAGE(shouldBeZero.is_zero(), "G * order != O"); } -#endif void test_point_swap(RandomNumberGenerator& rng) { @@ -1032,26 +823,6 @@ void test_point_swap(RandomNumberGenerator& rng) * This test verifies that the side channel attack resistant multiplication function * yields the same result as the normal (insecure) multiplication via operator*= */ -void test_mult_sec() - { - std::cout << "." << std::flush; - - EC_Domain_Params dom_pars(get_EC_Dom_Pars_by_oid("1.3.132.0.8")); - PointGFp a(dom_pars.get_base_point()); - BigInt scal("123413545342234"); - PointGFp b = a * scal; - PointGFp c(a); - c.mult_this_secure(scal, dom_pars.get_order(), dom_pars.get_order()-1); - PointGFp d(a); - d.mult_this_secure(scal, BigInt(0), dom_pars.get_order()-1); - CHECK(b == c); - CHECK(c == d); - } - -/** -* This test verifies that the side channel attack resistant multiplication function -* yields the same result as the normal (insecure) multiplication via operator*= -*/ void test_mult_sec_mass(RandomNumberGenerator& rng) { @@ -1064,11 +835,9 @@ void test_mult_sec_mass(RandomNumberGenerator& rng) BigInt scal(BigInt(rng, 40)); PointGFp b = a * scal; PointGFp c(a); - c.mult_this_secure(scal, dom_pars.get_order()*dom_pars.get_cofactor(), dom_pars.get_order()-1); - //PointGFp d(a); - //d.mult_this_secure(scal, BigInt(0), dom_pars.get_order()-1); + + c *= scal; CHECK(b == c); - //CHECK(c == d); } } @@ -1094,7 +863,8 @@ void test_ec_key_cp_and_assignment(RandomNumberGenerator& rng) BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); BigInt order = BigInt("0x0100000000000000000001f4c8f927aed3ca752257"); - CurveGFp curve(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); + BigInt cofactor = BigInt(1); PointGFp p_G = OS2ECP ( sv_g_secp, curve ); @@ -1106,7 +876,6 @@ void test_ec_key_cp_and_assignment(RandomNumberGenerator& rng) // sign with the original key SecureVector<byte> signature = my_priv_key.sign(sv_message.begin(), sv_message.size(), rng); - //cout << "signature = " << hex_encode(signature.begin(), signature.size()) << "\n"; bool ver_success = my_priv_key.verify(sv_message.begin(), sv_message.size(), signature.begin(), signature.size()); CHECK_MESSAGE(ver_success, "generated signature could not be verified positively"); @@ -1137,7 +906,7 @@ void test_ec_key_cast(RandomNumberGenerator& rng) BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); BigInt order = BigInt("0x0100000000000000000001f4c8f927aed3ca752257"); - CurveGFp curve(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); BigInt cofactor = BigInt(1); PointGFp p_G = OS2ECP ( sv_g_secp, curve ); @@ -1153,7 +922,7 @@ void test_ec_key_cast(RandomNumberGenerator& rng) // sign with the original key SecureVector<byte> signature = my_priv_key.sign(sv_message.begin(), sv_message.size(), rng); - //cout << "signature = " << hex_encode(signature.begin(), signature.size()) << "\n"; + bool ver_success = ec_cast_back->verify(sv_message.begin(), sv_message.size(), signature.begin(), signature.size()); CHECK_MESSAGE(ver_success, "generated signature could not be verified positively"); } @@ -1164,14 +933,10 @@ 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 (); test_point_mult (); - //test_montgm_calc_R (); - //test_naive_montg_mult (); - //test_trf_mres (); test_point_negative(); test_zeropoint(); test_zeropoint_enc_dec(); @@ -1189,10 +954,7 @@ void do_ec_tests(RandomNumberGenerator& rng) test_cdc_curve_33(); test_more_zeropoint(); test_mult_by_order(); - test_gfp_curve_precomp_mres(); - //test_point_worksp(); test_point_swap(rng); - test_mult_sec(); test_mult_sec_mass(rng); test_curve_cp_ctor(); test_ec_key_cp_and_assignment(rng); diff --git a/checks/ecdsa.cpp b/checks/ecdsa.cpp index 8991c8a6d..862677e63 100644 --- a/checks/ecdsa.cpp +++ b/checks/ecdsa.cpp @@ -195,7 +195,7 @@ void test_sign_then_ver(RandomNumberGenerator& rng) BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); BigInt order = BigInt("0x0100000000000000000001f4c8f927aed3ca752257"); - CurveGFp curve(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); BigInt cofactor = BigInt(1); PointGFp p_G = OS2ECP ( sv_g_secp, curve ); @@ -332,7 +332,7 @@ void test_create_and_verify(RandomNumberGenerator& rng) BigInt bi_a_secp = BigInt::decode ( sv_a_secp.begin(), sv_a_secp.size() ); BigInt bi_b_secp = BigInt::decode ( sv_b_secp.begin(), sv_b_secp.size() ); BigInt bi_order_g = BigInt::decode ( sv_order_g.begin(), sv_order_g.size() ); - CurveGFp curve ( GFpElement ( bi_p_secp,bi_a_secp ), GFpElement ( bi_p_secp, bi_b_secp ), bi_p_secp ); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); PointGFp p_G = OS2ECP ( sv_G_secp_comp, curve ); EC_Domain_Params dom_params(curve, p_G, bi_order_g, BigInt(1)); diff --git a/checks/eckaeg.cpp b/checks/eckaeg.cpp index 501ad8c3d..3f5443607 100644 --- a/checks/eckaeg.cpp +++ b/checks/eckaeg.cpp @@ -24,7 +24,6 @@ #include <botan/point_gfp.h> #include <botan/curve_gfp.h> -#include <botan/gfp_element.h> using namespace Botan; @@ -58,7 +57,7 @@ void test_eckaeg_normal_derivation(RandomNumberGenerator& rng) BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); BigInt order = BigInt("0x0100000000000000000001f4c8f927aed3ca752257"); - CurveGFp curve(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); BigInt cofactor = BigInt(1); PointGFp p_G = OS2ECP ( sv_g_secp, curve ); @@ -166,7 +165,7 @@ void test_eckaeg_cp_ctor_as_op(RandomNumberGenerator& rng) BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); BigInt order = BigInt("0x0100000000000000000001f4c8f927aed3ca752257"); - CurveGFp curve(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); BigInt cofactor = BigInt(1); PointGFp p_G = OS2ECP ( sv_g_secp, curve ); Botan::EC_Domain_Params dom_pars = Botan::EC_Domain_Params(curve, p_G, order, cofactor); @@ -225,7 +224,7 @@ void test_non_init_eckaeg_keys(RandomNumberGenerator& rng) BigInt bi_a_secp("0xffffffffffffffffffffffffffffffff7ffffffc"); BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45"); BigInt order = BigInt("0x0100000000000000000001f4c8f927aed3ca752257"); - CurveGFp curve(GFpElement(bi_p_secp,bi_a_secp), GFpElement(bi_p_secp, bi_b_secp), bi_p_secp); + CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp); BigInt cofactor = BigInt(1); PointGFp p_G = OS2ECP ( sv_g_secp, curve ); Botan::EC_Domain_Params dom_pars = Botan::EC_Domain_Params(curve, p_G, order, cofactor); diff --git a/checks/gfpmath.cpp b/checks/gfpmath.cpp deleted file mode 100644 index 50e1818c7..000000000 --- a/checks/gfpmath.cpp +++ /dev/null @@ -1,658 +0,0 @@ -/****************************************************** -* gfp_element tests * -* * -* (C) 2007 Patrick Sona * -* * -* Falko Strenzke * -* [email protected] * -* (C) 2008 Jack Lloyd * -******************************************************/ - -#include "validate.h" - -#if defined(BOTAN_HAS_BIGINT_GFP) - -#include <botan/bigint.h> -#include <botan/numthry.h> -#include <botan/gfp_element.h> -#include <botan/gfp_modulus.h> -#include <botan/curve_gfp.h> -#include <botan/ec_dompar.h> - -#include <iostream> - -using namespace Botan; - -#define CHECK_MESSAGE(expr, print) if(!(expr)) { std::cout << print << "\n"; pass = false; } -#define CHECK(expr) if(!(expr)) { std::cout << #expr << "\n"; pass = false; } - -namespace { - -bool test_turn_on_sp_red_mul() - { - std::cout << "." << std::flush; - - bool pass = true; - - GFpElement a1(23,15); - GFpElement b1(23,18); - - GFpElement c1 = a1*b1; - - 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) - { - std::cout << "test_turn_on_sp_red_mul: "; - std::cout << "c1 = " << c1 << " != "; - std::cout << "c2 = " << c2 << "\n"; - return false; // test failed - } - - return pass; // pass - } - -bool test_bi_div_even() - { - std::cout << "." << std::flush; - - bool pass = true; - - std::string str_large("1552518092300708935148979488462502555256886017116696611139052038026050952686323255099158638440248181850494907312621195144895406865083132424709500362534691373159016049946612882688577088900506460909202178541447303914546699487373976586"); - BigInt to_div(str_large); - BigInt half = to_div/2; - BigInt should_be_to_div = half*2; - CHECK_MESSAGE(should_be_to_div == to_div, "error in division/multiplication of large BigInt"); - - // also testing /=... - BigInt before_div = to_div; - to_div /= 2; - BigInt should_be_before(to_div*2); - CHECK_MESSAGE(should_be_before == before_div, "error in division/multiplication of large BigInt"); - - return pass; - } - -bool test_bi_div_odd() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string str_large("1552518092300708935148979488462502555256886017116696611139052038026050952686323255099158638440248181850494907312621195144895406865083132424709500362534691373159016049946612882688577088900506460909202178541447303914546699487373976585"); - BigInt to_div(str_large); - BigInt half = to_div/2; - BigInt should_be_to_div = half*2; - BigInt diff = should_be_to_div-to_div; - CHECK_MESSAGE((diff <= 1) && (diff >= BigInt("-1")), "error in division/multiplication (/) of large BigInt, differnce = " << diff); - - // also testing /=... - BigInt before_div = to_div; - to_div /= 2; - BigInt should_be_before(to_div*2); - BigInt diff2(should_be_before - before_div); - CHECK_MESSAGE((diff2 <= 1) && (diff2 >= BigInt("-1")), "error in division/multiplication (/=) of large BigInt, difference = " << diff2); - - return pass; - } - -bool test_deep_montgm() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - //std::string s_prime = "5"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333334"; - //std::string s_value_a = "4"; - BigInt bi_value_a(s_value_a); - std::string s_value_b = "4444444444444"; - //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 c_trf(gfp_a_trf * gfp_b_trf); - GFpElement c_ntrf(gfp_a_ntrf * gfp_b_ntrf); - - if(c_trf != c_ntrf) - { - std::cout << "test_deep_montgm - " << c_trf << " != " << c_ntrf << "\n"; - } - return pass; // pass - } - -bool test_gfp_div_small_numbers() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "13"; - BigInt bi_prime(s_prime); - std::string s_value_a = "2"; - BigInt bi_value_a(s_value_a); - 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 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"); - CHECK_MESSAGE(gfp_b.get_value() == s_value_b, "GFpElement has changed while division operation"); - GFpElement inverse_b = inverse(gfp_b); - GFpElement res_div_alternative = gfp_a * inverse_b; - - if(res_div_m != res_div_alternative) - { - std::cout << "test_gfp_div_small_numbers - a/b != a*b^-1 where\n" - << "a = " << gfp_a << "\n" - << "b = " << gfp_b << "\n" - << "b^-1 = " << inverse_b << "\n" - << "a*b^-1 = " << res_div_alternative << "\n" - << "a/b = " << res_div_n << "\n"; - pass = false; - } - - CHECK_MESSAGE(res_div_m == res_div_alternative, "a/b is not as equal to a * b^-1"); - //cout << "Div-result transformed:" << res_div_m.get_value() << endl; - //cout << "Div-result untransformed:" << res_div_n.get_value() << endl; - //cout << "Div-Alternative: " << res_div_alternative.get_value() << endl; - return pass; - } - -bool test_gfp_basics() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333333"; - BigInt bi_value_a(s_value_a); - - GFpElement gfp_a(bi_prime, bi_value_a, true); - 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; - } - -bool test_gfp_addSubNegate() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - 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); - - gfp_b.negate(); - GFpElement zero = gfp_a + gfp_b; - BigInt bi_zero("0"); - CHECK(zero.get_value() == bi_zero); - CHECK(gfp_a.get_value() == bi_value_a); - return pass; - } - -bool test_gfp_mult() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333333"; - BigInt bi_value_a(s_value_a); - 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 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 << " =? " - << "n = " << res_mult_n << " != m = " << res_mult_m << "\n"; - return pass; - } - -bool test_gfp_div() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333333"; - BigInt bi_value_a(s_value_a); - 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 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"); - CHECK_MESSAGE(gfp_b.get_value() == s_value_b, "GFpElement has changed while division operation"); - GFpElement inverse_b = inverse(gfp_b); - GFpElement res_div_alternative = gfp_a * inverse_b; - CHECK_MESSAGE(res_div_m == res_div_alternative, "a/b is not as equal to a * b^-1"); - //cout << "Div-result transformed:" << res_div_m.get_value() << endl; - //cout << "Div-result untransformed:" << res_div_n.get_value() << endl; - //cout << "Div-Alternative: " << res_div_alternative.get_value() << endl; - return pass; - } - -bool test_gfp_add() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333333"; - BigInt bi_value_a(s_value_a); - 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 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; - } - -bool test_gfp_sub() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333333"; - BigInt bi_value_a(s_value_a); - 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 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; - } - -bool test_more_gfp_div() - { - std::cout << '.' << std::flush; - - bool pass = true; - - std::string s_prime = "5334243285367"; - BigInt bi_prime(s_prime); - std::string s_value_a = "3333333333333"; - BigInt bi_value_a(s_value_a); - 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()); - - CHECK_MESSAGE(gfp_b_trf == gfp_b_ntrf, "b is not equal to itself (trf)"); - - GFpElement b_trf_inv(gfp_b_trf); - b_trf_inv.inverse_in_place(); - GFpElement b_ntrf_inv(gfp_b_ntrf); - b_ntrf_inv.inverse_in_place(); - CHECK_MESSAGE(b_trf_inv == b_ntrf_inv, "b inverted is not equal to itself (trf)"); - - CHECK(gfp_b_trf/gfp_b_ntrf == GFpElement(bi_prime, 1)); - CHECK(gfp_b_trf/gfp_b_trf == GFpElement(bi_prime, 1)); - CHECK(gfp_b_ntrf/gfp_b_ntrf == GFpElement(bi_prime, 1)); - GFpElement rhs(gfp_a/gfp_b_trf); - GFpElement lhs(gfp_a/gfp_b_ntrf); - - if(lhs != rhs) - { - std::cout << "test_more_gfp_div - " << lhs << " != " << rhs << "\n"; - pass = false; - } - - return pass; - } - -bool test_gfp_mult_u32bit() - { - std::cout << '.' << std::flush; - - bool pass = true; - - /* - Botan::EC_Domain_Params parA(Botan::get_EC_Dom_Pars_by_oid("1.2.840.10045.3.1.1")); - CurveGFp curve = parA.get_curve(); - //CurveGFp curve2 = parA.get_curve(); - BigInt p = curve.get_p(); - GFpElement a = curve.get_a(); - GFpElement a_mr = curve.get_mres_a(); - Botan::u32bit u_x = 134234; - BigInt b_x(u_x); - GFpElement g_x(p, b_x); - CHECK(a*u_x == a*g_x); - CHECK(a*u_x == u_x*a); - CHECK(a*g_x == g_x*a); - CHECK(a_mr*u_x == a*g_x); - CHECK(u_x*a_mr == a*g_x); - */ - return pass; - } - -bool test_gfp_swap() - { - std::cout << '.' << std::flush; - - bool pass = true; - - BigInt p("173"); - GFpElement a(p, BigInt("2342")); - GFpElement b(p, BigInt("423420")); - - swap(a,b); - CHECK_MESSAGE(b.get_value() == 2342%173, "actual value of b was: " << b.get_value() ); - CHECK_MESSAGE(a.get_value() == 423420%173, "actual value of a was: " << a.get_value() ); - - GFpElement c(p, BigInt("2342329")); - GFpElement d(1,1); - d = c; - d += d; - c.swap(d); - CHECK(d.get_value() == 2342329%173); - CHECK(c.get_value() == (d*2).get_value()); - return pass; - } - -bool test_inv_in_place() - { - std::cout << '.' << std::flush; - - bool pass = true; - - 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(); - - GFpElement a2(mod, 288); - GFpElement a2_inv(a2); - a2_inv.inverse_in_place(); - - /*cout << "a1_inv = " << a1_inv << endl; - cout << "a2_inv = " << a2_inv << endl;*/ - CHECK_MESSAGE(a1_inv == a2_inv, "error with inverting tranformed GFpElement"); - - CHECK(a1_inv.inverse_in_place() == a1); - CHECK(a2_inv.inverse_in_place() == a2); - return pass; - } - -bool test_op_eq() - { - std::cout << '.' << std::flush; - - bool pass = true; - - 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; - } - -bool test_rand_int(RandomNumberGenerator& rng) - { - bool pass = true; - - for(int i=0; i< 100; i++) - { - std::cout << '.' << std::flush; - BigInt x = BigInt::random_integer(rng, 1,3); - //cout << "x = " << x << "\n"; // only 1,2 are put out - CHECK(x == 1 || x==2); - } - - return pass; - } - -bool test_bi_bit_access() - { - std::cout << '.' << std::flush; - - bool pass = true; - - BigInt a(323); - CHECK(a.get_bit(1) == 1); - CHECK(a.get_bit(1000) == 0); - return pass; - } - -#if 0 -bool test_sec_mod_mul() - { - //cout << "starting test_sec_mod_mul" << endl; - - bool pass = true; - - //mod_mul_secure(BigInt const& a, BigInt const& b, BigInt const& m) - - BigInt m("5334243285367"); - BigInt a("3333333333333"); - BigInt b("4444444444444"); - for(int i = 0; i<10; i++) - { - std::cout << '.' << std::flush; - BigInt c1 = a * b; - c1 %= m; - BigInt c2 = mod_mul_secure(a, b, m); - CHECK_MESSAGE(c1 == c2, "should be " << c1 << ", was " << c2); - } - //cout << "ending test_sec_mod_mul" << endl; - return pass; - } -#endif - -#if 0 -bool test_sec_bi_mul() - { - //mod_mul_secure(BigInt const& a, BigInt const& b, BigInt const& m) - - bool pass = true; - - BigInt m("5334243285367"); - BigInt a("3333333333333"); - BigInt b("4444444444444"); - for(int i = 0; i<10; i++) - { - std::cout << '.' << std::flush; - BigInt c1 = a * b; - //c1 %= m; - BigInt c2(a); - c2.mult_this_secure(b, m); - CHECK_MESSAGE(c1 == c2, "should be " << c1 << ", was " << c2); - } - - return pass; - } -#endif - -} - -u32bit do_gfpmath_tests(Botan::RandomNumberGenerator& rng) - { - std::cout << "Testing GF(p) math " << std::flush; - - u32bit failed = 0; - - failed += !test_turn_on_sp_red_mul(); - failed += !test_bi_div_even(); - failed += !test_bi_div_odd(); - failed += !test_deep_montgm(); - failed += !test_gfp_div_small_numbers(); - failed += !test_gfp_basics(); - failed += !test_gfp_addSubNegate(); - failed += !test_gfp_mult(); - failed += !test_gfp_div(); - failed += !test_gfp_add(); - failed += !test_gfp_sub(); - failed += !test_more_gfp_div(); - failed += !test_gfp_mult_u32bit(); - failed += !test_gfp_swap(); - failed += !test_inv_in_place(); - failed += !test_op_eq(); - failed += !test_rand_int(rng); - failed += !test_bi_bit_access(); - //failed += !test_sec_mod_mul(); - //failed += !test_sec_bi_mul(); - -#if 0 - if(failed == 0) - std::cout << " OK"; - else - std::cout << ' ' << failed << " failed"; -#endif - - std::cout << std::endl; - - return failed; - } -#else -u32bit do_gfpmath_tests(Botan::RandomNumberGenerator&) { return 0; } -#endif diff --git a/checks/pk.cpp b/checks/pk.cpp index cb25c9212..b50ce17da 100644 --- a/checks/pk.cpp +++ b/checks/pk.cpp @@ -769,7 +769,6 @@ u32bit do_pk_validation_tests(const std::string& filename, std::cout << std::endl; - errors += do_gfpmath_tests(rng); do_ec_tests(rng); errors += do_ecdsa_tests(rng); errors += do_eckaeg_tests(rng); diff --git a/checks/validate.h b/checks/validate.h index f7cc4bdf9..b0e3565f8 100644 --- a/checks/validate.h +++ b/checks/validate.h @@ -17,9 +17,6 @@ u32bit do_validation_tests(const std::string&, u32bit do_bigint_tests(const std::string&, RandomNumberGenerator& rng); -u32bit do_gfpmath_tests(RandomNumberGenerator& rng); - - u32bit do_pk_validation_tests(const std::string&, RandomNumberGenerator&); diff --git a/readme.txt b/readme.txt index 55c5452ea..7a9f4851e 100644 --- a/readme.txt +++ b/readme.txt @@ -3,10 +3,9 @@ Botan 1.9.4-dev, ????-??-?? Botan is a C++ class library for performing a wide variety of cryptographic operations. -Botan is released under the BSD license. See license.txt for the -specifics. More information about the authors and contributors can be -found in credits.txt and thanks.txt. All of these files are included -in the doc/ directory of the source distribution. +Botan is released under the FreeBSD license (see doc/license.txt for +the specifics). More information about the authors and contributors +can be found in doc/credits.txt and doc/thanks.txt. You can file bugs at http://bugs.randombit.net/ or by sending a report to the botan-devel mailing list: @@ -20,14 +19,6 @@ tutorial.pdf - a set of simple examples and tutorials A set of example programs can be found in the doc/examples directory. -Some higher level cryptographic protocols are implemented using -Botan in: - -- NetSieben SSH Library (SSHv2) - http://www.netsieben.com/products/ssh/ -- Ajisai (SSLv3/TLSv1) - http://www.randombit.net/code/ajisai/ - Check http://botan.randombit.net/ for announcements and new releases. If you'll be developing code using this library, consider joining the mailing lists to keep up to date with changes and new diff --git a/src/block/aes_intel/aes_intel.h b/src/block/aes_intel/aes_intel.h index 164655072..239516e24 100644 --- a/src/block/aes_intel/aes_intel.h +++ b/src/block/aes_intel/aes_intel.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL AES_128_Intel : public BlockCipher { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; @@ -38,6 +40,8 @@ class BOTAN_DLL AES_128_Intel : public BlockCipher class BOTAN_DLL AES_192_Intel : public BlockCipher { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; @@ -58,6 +62,8 @@ class BOTAN_DLL AES_192_Intel : public BlockCipher class BOTAN_DLL AES_256_Intel : public BlockCipher { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/block_cipher.h b/src/block/block_cipher.h index 06e8c5cea..2d9198c58 100644 --- a/src/block/block_cipher.h +++ b/src/block/block_cipher.h @@ -24,6 +24,11 @@ class BOTAN_DLL BlockCipher : public SymmetricAlgorithm const u32bit BLOCK_SIZE; /** + * @return the preferred parallelism of this cipher + */ + virtual u32bit parallelism() const { return 4; } + + /** * Encrypt a block. * @param in The plaintext block to be encrypted as a byte array. * Must be of length BLOCK_SIZE. diff --git a/src/block/idea_sse2/idea_sse2.h b/src/block/idea_sse2/idea_sse2.h index 167c981f8..657581d74 100644 --- a/src/block/idea_sse2/idea_sse2.h +++ b/src/block/idea_sse2/idea_sse2.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL IDEA_SSE2 : public IDEA { public: + u32bit parallelism() const { return 16; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/noekeon_simd/noekeon_simd.h b/src/block/noekeon_simd/noekeon_simd.h index 466c4b741..55fdfbd22 100644 --- a/src/block/noekeon_simd/noekeon_simd.h +++ b/src/block/noekeon_simd/noekeon_simd.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL Noekeon_SIMD : public Noekeon { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/serpent_simd/serp_simd.h b/src/block/serpent_simd/serp_simd.h index 1ecb70159..dc2b08736 100644 --- a/src/block/serpent_simd/serp_simd.h +++ b/src/block/serpent_simd/serp_simd.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL Serpent_SIMD : public Serpent { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/xtea_simd/xtea_simd.h b/src/block/xtea_simd/xtea_simd.h index e4ce734ed..04a4977ae 100644 --- a/src/block/xtea_simd/xtea_simd.h +++ b/src/block/xtea_simd/xtea_simd.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL XTEA_SIMD : public XTEA { public: + u32bit parallelism() const { return 16; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; BlockCipher* clone() const { return new XTEA_SIMD; } diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in index 231a7aeeb..6412d8a6a 100644 --- a/src/build-data/buildh.in +++ b/src/build-data/buildh.in @@ -22,17 +22,6 @@ #define BOTAN_KARAT_SQR_THRESHOLD 32 #define BOTAN_PRIVATE_KEY_OP_BLINDING_BITS 64 -/* -* Toggles for parallel block cipher mode processing -* -* CBC and CFB can only use parallel processing in decryption mode -*/ -#define BOTAN_PARALLEL_BLOCKS_ECB 16 -#define BOTAN_PARALLEL_BLOCKS_CBC 16 -#define BOTAN_PARALLEL_BLOCKS_CFB 16 -#define BOTAN_PARALLEL_BLOCKS_CTR 16 -#define BOTAN_PARALLEL_BLOCKS_XTS 16 - /* PK key consistency checking toggles */ #define BOTAN_PUBLIC_KEY_STRONG_CHECKS_ON_LOAD 1 #define BOTAN_PRIVATE_KEY_STRONG_CHECKS_ON_LOAD 1 diff --git a/src/filters/buf_filt.h b/src/filters/buf_filt.h index de4102844..582f585b0 100644 --- a/src/filters/buf_filt.h +++ b/src/filters/buf_filt.h @@ -27,6 +27,8 @@ class BOTAN_DLL Buffered_Filter virtual void buffered_block(const byte input[], u32bit length) = 0; virtual void buffered_final(const byte input[], u32bit length) = 0; + u32bit buffered_block_size() const { return main_block_mod; } + u32bit current_position() const { return buffer_pos; } void buffer_reset() { buffer_pos = 0; } private: diff --git a/src/filters/modes/cbc/cbc.cpp b/src/filters/modes/cbc/cbc.cpp index 7722fad2f..4f484da77 100644 --- a/src/filters/modes/cbc/cbc.cpp +++ b/src/filters/modes/cbc/cbc.cpp @@ -114,7 +114,7 @@ std::string CBC_Encryption::name() const */ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_CBC * ciph->BLOCK_SIZE, + Buffered_Filter(ciph->parallelism() * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE), cipher(ciph), padder(pad) { @@ -122,7 +122,7 @@ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, throw Invalid_Block_Size(name(), padder->name()); state.resize(cipher->BLOCK_SIZE); - temp.resize(BOTAN_PARALLEL_BLOCKS_CBC * cipher->BLOCK_SIZE); + temp.resize(buffered_block_size()); } /* @@ -132,7 +132,7 @@ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad, const SymmetricKey& key, const InitializationVector& iv) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_CBC * ciph->BLOCK_SIZE, + Buffered_Filter(ciph->parallelism() * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE), cipher(ciph), padder(pad) { @@ -140,7 +140,7 @@ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, throw Invalid_Block_Size(name(), padder->name()); state.resize(cipher->BLOCK_SIZE); - temp.resize(BOTAN_PARALLEL_BLOCKS_CBC * cipher->BLOCK_SIZE); + temp.resize(buffered_block_size()); set_key(key); set_iv(iv); diff --git a/src/filters/modes/ecb/ecb.cpp b/src/filters/modes/ecb/ecb.cpp index 2ce6576e3..948daf6c2 100644 --- a/src/filters/modes/ecb/ecb.cpp +++ b/src/filters/modes/ecb/ecb.cpp @@ -14,12 +14,12 @@ namespace Botan { */ ECB_Encryption::ECB_Encryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 0) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 0) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); } /* @@ -28,12 +28,12 @@ ECB_Encryption::ECB_Encryption(BlockCipher* ciph, ECB_Encryption::ECB_Encryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad, const SymmetricKey& key) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 0) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 0) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); cipher->set_key(key); } @@ -111,12 +111,12 @@ void ECB_Encryption::buffered_final(const byte input[], u32bit input_length) */ ECB_Decryption::ECB_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 1) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 1) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); } /* @@ -125,12 +125,12 @@ ECB_Decryption::ECB_Decryption(BlockCipher* ciph, ECB_Decryption::ECB_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad, const SymmetricKey& key) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 1) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 1) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); cipher->set_key(key); } diff --git a/src/filters/modes/xts/xts.cpp b/src/filters/modes/xts/xts.cpp index aeef4e88d..26095e830 100644 --- a/src/filters/modes/xts/xts.cpp +++ b/src/filters/modes/xts/xts.cpp @@ -30,13 +30,21 @@ void poly_double(byte tweak[], u32bit size) tweak[0] ^= polynomial; } +/* XTS needs to process at least 2 blocks in parallel + because block_size+1 bytes are needed at the end +*/ +u32bit xts_parallelism(BlockCipher* cipher) + { + return std::max<u32bit>(cipher->parallelism(), 2); + } + } /* * XTS_Encryption constructor */ XTS_Encryption::XTS_Encryption(BlockCipher* ciph) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -44,7 +52,7 @@ XTS_Encryption::XTS_Encryption(BlockCipher* ciph) : throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = cipher->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); } /* @@ -53,7 +61,7 @@ XTS_Encryption::XTS_Encryption(BlockCipher* ciph) : XTS_Encryption::XTS_Encryption(BlockCipher* ciph, const SymmetricKey& key, const InitializationVector& iv) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -61,7 +69,7 @@ XTS_Encryption::XTS_Encryption(BlockCipher* ciph, throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = cipher->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); set_key(key); set_iv(iv); @@ -210,7 +218,7 @@ void XTS_Encryption::buffered_final(const byte input[], u32bit length) * XTS_Decryption constructor */ XTS_Decryption::XTS_Decryption(BlockCipher* ciph) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -218,7 +226,7 @@ XTS_Decryption::XTS_Decryption(BlockCipher* ciph) : throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = ciph->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); } /* @@ -227,7 +235,7 @@ XTS_Decryption::XTS_Decryption(BlockCipher* ciph) : XTS_Decryption::XTS_Decryption(BlockCipher* ciph, const SymmetricKey& key, const InitializationVector& iv) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -235,7 +243,7 @@ XTS_Decryption::XTS_Decryption(BlockCipher* ciph, throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = ciph->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); set_key(key); set_iv(iv); diff --git a/src/math/gfpmath/curve_gfp.cpp b/src/math/gfpmath/curve_gfp.cpp deleted file mode 100644 index e6e69ab0f..000000000 --- a/src/math/gfpmath/curve_gfp.cpp +++ /dev/null @@ -1,58 +0,0 @@ -/* -* Elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/curve_gfp.h> -#include <botan/bigint.h> -#include <assert.h> -#include <ostream> - -namespace Botan { - -CurveGFp::CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p) : - modulus(p), mA(a), mB(b), - mres_a(mA), mres_b(mB), mres_one(p, 1) - { - if(p != mA.get_p() || p != mB.get_p()) - throw Invalid_Argument("could not construct curve: moduli of arguments differ"); - - mres_a.turn_on_sp_red_mul(); - mres_a.get_mres(); - - mres_b.turn_on_sp_red_mul(); - mres_b.get_mres(); - - mres_one.turn_on_sp_red_mul(); - mres_one.get_mres(); - } - -// swaps the states of *this and other, does not throw -void CurveGFp::swap(CurveGFp& other) - { - std::swap(mA, other.mA); - std::swap(mB, other.mB); - std::swap(modulus, other.modulus); - std::swap(mres_a, other.mres_a); - std::swap(mres_b, other.mres_b); - std::swap(mres_one, other.mres_one); - } - -bool operator==(const CurveGFp& lhs, const CurveGFp& rhs) - { - return (lhs.get_p() == rhs.get_p() && - lhs.get_a() == rhs.get_a() && - lhs.get_b() == rhs.get_b()); - } - -std::ostream& operator<<(std::ostream& output, const CurveGFp& elem) - { - return output << "y^2 = x^3 + (" << elem.get_a() << ")x + (" << elem.get_b() << ")"; - } - -} diff --git a/src/math/gfpmath/curve_gfp.h b/src/math/gfpmath/curve_gfp.h deleted file mode 100644 index d2ca437fb..000000000 --- a/src/math/gfpmath/curve_gfp.h +++ /dev/null @@ -1,133 +0,0 @@ -/* -* Elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_CURVE_H__ -#define BOTAN_GFP_CURVE_H__ - -#include <botan/bigint.h> -#include <botan/gfp_element.h> -#include <iosfwd> - -namespace Botan { - -/** -* This class represents an elliptic curve over GF(p) -*/ -class BOTAN_DLL CurveGFp - { - public: - - /** - * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) - * @param a first coefficient - * @param b second coefficient - * @param p prime number of the field - */ - CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p); - - // CurveGFp(const CurveGFp& other) = default; - // CurveGFp& operator=(const CurveGFp& other) = default; - - // getters - - /** - * Get coefficient a - * @result coefficient a - */ - const GFpElement& get_a() const { return mA; } - - /** - * Get coefficient b - * @result coefficient b - */ - const GFpElement& get_b() const { return mB; } - - /** - * Get the GFpElement coefficient a transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient a, transformed to its m-residue - */ - const GFpElement& get_mres_a() const { return mres_a; } - - /** - * Get the GFpElement coefficient b transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient b, transformed to its m-residue - */ - const GFpElement& get_mres_b() const { return mres_b; } - - /** - * Get the GFpElement 1 transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the GFpElement 1, transformed to its m-residue - */ - const GFpElement& get_mres_one() { return mres_one; } - - /** - * Get prime modulus of the field of the curve - * @result prime modulus of the field of the curve - */ - const BigInt& get_p() const { return modulus.get_p(); } - - /** - * swaps the states of *this and other, does not throw - * @param other The curve to swap values with - */ - void swap(CurveGFp& other); - - private: - GFpModulus modulus; - GFpElement mA; - GFpElement mB; - GFpElement mres_a, mres_b, mres_one; - }; - -// relational operators -bool operator==(const CurveGFp& lhs, const CurveGFp& rhs); - -inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) - { - return !(lhs == rhs); - } - -// io operators -std::ostream& operator<<(std::ostream& output, const CurveGFp& elem); - -// swaps the states of curve1 and curve2, does not throw! -// cf. Meyers, Item 25 -inline -void swap(CurveGFp& curve1, CurveGFp& curve2) - { - curve1.swap(curve2); - } - -} // namespace Botan - - -namespace std { - -// swaps the states of curve1 and curve2, does not throw! -// cf. Meyers, Item 25 -template<> inline -void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, - Botan::CurveGFp& curve2) - { - curve1.swap(curve2); - } - -} // namespace std - -#endif diff --git a/src/math/gfpmath/gfp_element.cpp b/src/math/gfpmath/gfp_element.cpp deleted file mode 100644 index 3bb4d0002..000000000 --- a/src/math/gfpmath/gfp_element.cpp +++ /dev/null @@ -1,559 +0,0 @@ -/* -* Arithmetic for prime fields GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/gfp_element.h> -#include <botan/numthry.h> -#include <botan/internal/def_powm.h> -#include <botan/internal/mp_asm.h> -#include <botan/internal/mp_asmi.h> -#include <ostream> -#include <assert.h> - -namespace Botan { - -namespace { - -void inner_montg_mult_sos(word result[], - const word* a_bar, const word* b_bar, - const word* n, const word* n_dash, u32bit s) - { - SecureVector<word> t; - t.grow_to(2*s+1); - - // t = a_bar * b_bar - for (u32bit i=0; i<s; i++) - { - word C = 0; - word S = 0; - for (u32bit j=0; j<s; j++) - { - // we use: - // word word_madd3(word a, word b, word c, word d, word* carry) - // returns a * b + c + d and resets the carry (not using it as input) - - S = word_madd3(a_bar[j], b_bar[i], t[i+j], &C); - t[i+j] = S; - } - t[i+s] = C; - } - - // ??? - for (u32bit i=0; i<s; i++) - { - // word word_madd2(word a, word b, word c, word* carry) - // returns a * b + c, resets the carry - - word C = 0; - word zero = 0; - word m = word_madd2(t[i], n_dash[0], &zero); - - for (u32bit j=0; j<s; j++) - { - word S = word_madd3(m, n[j], t[i+j], &C); - t[i+j] = S; - } - - //// mp_mulop.cpp: - ////word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y) - u32bit cnt = 0; - while (C > 0) - { - // we need not worry here about C > 1, because the other operand is zero - - word tmp = t[i+s+cnt] + C; - C = (tmp < t[i+s+cnt]); - t[i+s+cnt] = tmp; - cnt++; - } - } - - // u = t - SecureVector<word> u; - u.grow_to(s+1); - for (u32bit j=0; j<s+1; j++) - { - u[j] = t[j+s]; - } - - // t = u - n - word B = 0; - word D = 0; - for (u32bit i=0; i<s; i++) - { - D = word_sub(u[i], n[i], &B); - t[i] = D; - } - D = word_sub(u[s], 0, &B); - t[s] = D; - - // if t >= 0 (B == 0 -> no borrow), return t - if(B == 0) - { - for (u32bit i=0; i<s; i++) - { - result[i] = t[i]; - } - } - else // else return u - { - for (u32bit i=0; i<s; i++) - { - result[i] = u[i]; - } - } - } - -void montg_mult(BigInt& result, BigInt& a_bar, BigInt& b_bar, const BigInt& m, const BigInt& m_dash, const BigInt) - { - if(m.is_zero() || m_dash.is_zero()) - throw Invalid_Argument("montg_mult(): neither modulus nor m_dash may be zero (and one of them was)"); - - if(a_bar.is_zero() || b_bar.is_zero()) - result = 0; - - u32bit s = m.sig_words(); - a_bar.grow_to(s); - b_bar.grow_to(s); - result.grow_to(s); - - inner_montg_mult_sos(result.get_reg(), a_bar.data(), b_bar.data(), - m.data(), m_dash.data(), s); - } - -/** -* Calculates R=b^n (here b=2) with R>m (and R beeing as small as -* possible) for an odd modulus m. No check for parity is performed! -*/ -BigInt montgm_calc_r_oddmod(const BigInt& prime) - { - u32bit n = prime.sig_words(); - BigInt result(1); - result <<= n*BOTAN_MP_WORD_BITS; - return result; - } - -/** -*calculates m' with r*r^-1 - m*m' = 1 -* where r^-1 is the multiplicative inverse of r to the modulus m -*/ -BigInt montgm_calc_m_dash(const BigInt& r, const BigInt& m, const BigInt& r_inv) - { - BigInt result = ((r * r_inv) - BigInt(1))/m; - return result; - } - -BigInt montg_trf_to_mres(const BigInt& ord_res, const BigInt& r, const BigInt& m) - { - BigInt result(ord_res); - result *= r; - result %= m; - return result; - } - -BigInt montg_trf_to_ordres(const BigInt& m_res, const BigInt& m, const BigInt& r_inv) - { - BigInt result(m_res); - result *= r_inv; - result %= m; - return result; - } - -} - -GFpElement::GFpElement(const BigInt& p, const BigInt& value, bool use_montgomery) - : modulus(p), m_value(value %p), m_use_montgm(use_montgomery), m_is_trf(false) - { - if(m_use_montgm) - ensure_montgm_precomp(); - } - -void GFpElement::turn_on_sp_red_mul() - { - ensure_montgm_precomp(); - m_use_montgm = true; - } - -void GFpElement::turn_off_sp_red_mul() - { - if(m_is_trf) - { - trf_to_ordres(); - // will happen soon anyway, so we can do it here already - // (this is not lazy but way more secure concerning our internal logic here) - } - m_use_montgm = false; - } - -void GFpElement::ensure_montgm_precomp() - { - if((!modulus.get_r().is_zero()) && (!modulus.get_r_inv().is_zero()) && (!modulus.get_p_dash().is_zero())) - { - // values are already set, nothing more to do - } - else - { - BigInt tmp_r(montgm_calc_r_oddmod(modulus.get_p())); - - BigInt tmp_r_inv(inverse_mod(tmp_r, modulus.get_p())); - - BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, modulus.get_p(), tmp_r_inv)); - - modulus.reset_values(tmp_p_dash, tmp_r, tmp_r_inv); - } - - } - -void GFpElement::trf_to_mres() const - { - if(!m_use_montgm) - { - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - assert(m_is_trf == false); - assert(!modulus.get_r_inv().is_zero()); - assert(!modulus.get_p_dash().is_zero()); - m_value = montg_trf_to_mres(m_value, modulus.get_r(), modulus.get_p()); - m_is_trf = true; - } - -void GFpElement::trf_to_ordres() const - { - assert(m_is_trf == true); - m_value = montg_trf_to_ordres(m_value, modulus.get_p(), modulus.get_r_inv()); - m_is_trf = false; - } - -bool GFpElement::align_operands_res(const GFpElement& lhs, const GFpElement& rhs) //static - { - assert(lhs.modulus.get_p() == rhs.modulus.get_p()); - if(lhs.m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.modulus.get_p_dash() == lhs.modulus.get_p_dash()); - assert(rhs.modulus.get_r() == lhs.modulus.get_r()); - assert(rhs.modulus.get_r_inv() == lhs.modulus.get_r_inv()); - if(!lhs.m_is_trf && !rhs.m_is_trf) - { - return false; - } - else if(lhs.m_is_trf && rhs.m_is_trf) - { - return true; - } - else // one is transf., the other not - { - if(!lhs.m_is_trf) - { - lhs.trf_to_mres(); - assert(rhs.m_is_trf==true); - return true; - } - assert(rhs.m_is_trf==false); - assert(lhs.m_is_trf==true); - rhs.trf_to_mres(); // the only possibility left... - return true; - } - } - else // at least one of them does not use mm - // (so it is impossible that both use it) - { - if(lhs.m_is_trf) - { - lhs.trf_to_ordres(); - assert(rhs.m_is_trf == false); - return false; - } - if(rhs.m_is_trf) - { - rhs.trf_to_ordres(); - assert(lhs.m_is_trf == false); - return false; - } - return false; - } - assert(false); - } - -bool GFpElement::is_trf_to_mres() const - { - return m_is_trf; - } - -const BigInt& GFpElement::get_p() const - { - return (modulus.get_p()); - } - -const BigInt& GFpElement::get_value() const - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - return m_value; - } - -const BigInt& GFpElement::get_mres() const - { - if(!m_use_montgm) - { - // does the following exception really make sense? - // wouldn't it be better to simply turn on montg.mult. when - // this explicit request is made? - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - if(!m_is_trf) - { - trf_to_mres(); - } - - return m_value; - } - -GFpElement& GFpElement::operator+=(const GFpElement& rhs) - { - GFpElement::align_operands_res(*this, rhs); - - BigInt workspace = m_value; - workspace += rhs.m_value; - if(workspace >= modulus.get_p()) - workspace -= modulus.get_p(); - - m_value = workspace; - assert(m_value < modulus.get_p()); - assert(m_value >= 0); - - return *this; - } - -GFpElement& GFpElement::operator-=(const GFpElement& rhs) - { - GFpElement::align_operands_res(*this, rhs); - - BigInt workspace = m_value; - - workspace -= rhs.m_value; - - if(workspace.is_negative()) - workspace += modulus.get_p(); - - m_value = workspace; - assert(m_value < modulus.get_p()); - assert(m_value >= 0); - return *this; - } - -GFpElement& GFpElement::operator*= (u32bit rhs) - { - BigInt workspace = m_value; - workspace *= rhs; - workspace %= modulus.get_p(); - m_value = workspace; - return *this; - } - -GFpElement& GFpElement::operator*=(const GFpElement& rhs) - { - assert(rhs.modulus.get_p() == modulus.get_p()); - // here, we do not use align_operands_res() for one simple reason: - // we want to enforce the transformation to an m-residue, otherwise it would - // never happen - if(m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.modulus.get_p() == modulus.get_p()); // is montgm. mult is on, then precomps must be there - assert(rhs.modulus.get_p_dash() == modulus.get_p_dash()); - assert(rhs.modulus.get_r() == modulus.get_r()); - if(!m_is_trf) - { - trf_to_mres(); - } - if(!rhs.m_is_trf) - { - rhs.trf_to_mres(); - } - BigInt workspace = m_value; - montg_mult(m_value, workspace, rhs.m_value, modulus.get_p(), modulus.get_p_dash(), modulus.get_r()); - } - else // ordinary multiplication - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - if(rhs.m_is_trf) - { - assert(rhs.m_use_montgm); - rhs.trf_to_ordres(); - } - - BigInt workspace = m_value; - workspace *= rhs.m_value; - workspace %= modulus.get_p(); - m_value = workspace; - } - return *this; - } - -GFpElement& GFpElement::operator/=(const GFpElement& rhs) - { - bool use_mres = GFpElement::align_operands_res(*this, rhs); - assert((this->m_is_trf && rhs.m_is_trf) || !(this->m_is_trf && rhs.m_is_trf)); - - if(use_mres) - { - assert(m_use_montgm && rhs.m_use_montgm); - GFpElement rhs_ordres(rhs); - rhs_ordres.trf_to_ordres(); - rhs_ordres.inverse_in_place(); - BigInt workspace = m_value; - workspace *= rhs_ordres.get_value(); - workspace %= modulus.get_p(); - m_value = workspace; - } - else - { - GFpElement inv_rhs(rhs); - inv_rhs.inverse_in_place(); - *this *= inv_rhs; - } - return *this; - } - -bool GFpElement::is_zero() - { - return (m_value.is_zero()); - // this is correct because x_bar = x * r = x = 0 for x = 0 - } - -GFpElement& GFpElement::inverse_in_place() - { - m_value = inverse_mod(m_value, modulus.get_p()); - - if(m_is_trf) - { - assert(m_use_montgm); - - m_value *= modulus.get_r(); - m_value *= modulus.get_r(); - m_value %= modulus.get_p(); - } - assert(m_value <= modulus.get_p()); - return *this; - } - -GFpElement& GFpElement::negate() - { - m_value = modulus.get_p() - m_value; - assert(m_value <= modulus.get_p()); - return *this; - } - -void GFpElement::swap(GFpElement& other) - { - std::swap(m_value, other.m_value); - std::swap(modulus, other.modulus); - std::swap<bool>(m_use_montgm,other.m_use_montgm); - std::swap<bool>(m_is_trf,other.m_is_trf); - } - -std::ostream& operator<<(std::ostream& output, const GFpElement& elem) - { - return output << '(' << elem.get_value() << "," << elem.get_p() << ')'; - } - -bool operator==(const GFpElement& lhs, const GFpElement& rhs) - { - if(lhs.get_p() != rhs.get_p()) - return false; - - // so the modulus is equal, now check the values - bool use_mres = GFpElement::align_operands_res(lhs, rhs); - - if(use_mres) - { - return (lhs.get_mres() == rhs.get_mres()); - } - else - { - return(lhs.get_value() == rhs.get_value()); - } - } - -GFpElement operator+(const GFpElement& lhs, const GFpElement& rhs) - { - // consider the case that lhs and rhs both use montgm: - // then += returns an element which uses montgm. - // thus the return value of op+ here will be an element - // using montgm in this case - // NOTE: the rhs might be transformed when using op+, the lhs never - GFpElement result(lhs); - result += rhs; - return result; - } - -GFpElement operator-(const GFpElement& lhs, const GFpElement& rhs) - { - GFpElement result(lhs); - result -= rhs; - return result; - // NOTE: the rhs might be transformed when using op-, the lhs never - } - -GFpElement operator-(const GFpElement& lhs) - { - return(GFpElement(lhs)).negate(); - } - -GFpElement operator*(const GFpElement& lhs, const GFpElement& rhs) - { - // consider the case that lhs and rhs both use montgm: - // then *= returns an element which uses montgm. - // thus the return value of op* here will be an element - // using montgm in this case - GFpElement result(lhs); - result *= rhs; - return result; - } - -GFpElement operator*(const GFpElement& lhs, u32bit rhs) - { - GFpElement result(lhs); - result *= rhs; - return result; - } - -GFpElement operator*(u32bit lhs, const GFpElement& rhs) - { - return rhs*lhs; - } - -GFpElement operator/(const GFpElement& lhs, const GFpElement& rhs) - { - GFpElement result (lhs); - result /= rhs; - return result; - } - -SecureVector<byte> FE2OSP(const GFpElement& elem) - { - return BigInt::encode_1363(elem.get_value(), elem.get_p().bytes()); - } - -GFpElement OS2FEP(MemoryRegion<byte> const& os, BigInt p) - { - return GFpElement(p, BigInt::decode(os.begin(), os.size())); - } - -GFpElement inverse(const GFpElement& elem) - { - return GFpElement(elem).inverse_in_place(); - } - -} - diff --git a/src/math/gfpmath/gfp_element.h b/src/math/gfpmath/gfp_element.h deleted file mode 100644 index 538d41a47..000000000 --- a/src/math/gfpmath/gfp_element.h +++ /dev/null @@ -1,230 +0,0 @@ -/* -* Arithmetic for prime fields GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2009-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_ELEMENT_H__ -#define BOTAN_GFP_ELEMENT_H__ - -#include <botan/bigint.h> -#include <botan/gfp_modulus.h> -#include <iosfwd> - -namespace Botan { - -struct BOTAN_DLL Illegal_Transformation : public Exception - { - Illegal_Transformation(const std::string& err = - "Requested transformation is not possible") : - Exception(err) {} - }; - -/** - * This class represents one element in GF(p). Enables the convenient, - * transparent use of the montgomery multiplication. - */ -class BOTAN_DLL GFpElement - { - public: - - /** construct an element of GF(p) with the given value. - * use_montg defaults to false and determines wether Montgomery - * multiplications will be use when applying operators *, *= - * @param p the prime number of the field - * @param value the element value - * @param use_montgm whether this object will use Montgomery multiplication - */ - GFpElement(const BigInt& p, const BigInt& value, bool use_montgm = true); - - // GFpElement(const GFpElement& other) = default; - - // const GFpElement& operator=(const GFpElement& other) = default; - - /** - * Switch Montgomery multiplcation optimizations ON - */ - void turn_on_sp_red_mul(); - - /** - * Switch Montgomery multiplcation optimizations OFF - */ - void turn_off_sp_red_mul(); - - /** - * += Operator - * @param rhs the GFpElement to add to the local value - * @result *this - */ - GFpElement& operator+=(const GFpElement& rhs); - - /** - * -= Operator - * @param rhs the GFpElement to subtract from the local value - * @result *this - */ - GFpElement& operator-=(const GFpElement& rhs); - - /** - * *= Operator - * @param rhs the GFpElement to multiply with the local value - * @result *this - */ - GFpElement& operator*=(const GFpElement& rhs); - /** - * /= Operator - * @param rhs the GFpElement to divide the local value by - * @result *this - */ - GFpElement& operator/=(const GFpElement& rhs); - - /** - * *= Operator - * @param rhs the value to multiply with the local value - * @result *this - */ - GFpElement& operator*=(u32bit rhs); - - /** - * Negate internal value(*this *= -1 ) - * @return *this - */ - GFpElement& negate(); - - /** - * Assigns the inverse of *this to *this, i.e. - * *this = (*this)^(-1) - * @result *this - */ - GFpElement& inverse_in_place(); - - /** - * checks whether the value is zero (without provoking - * a backtransformation to the ordinary-residue) - * @result true, if the value is zero, false otherwise. - */ - bool is_zero(); - - /** - * return prime number of GF(p) - * @result a prime number - */ - const BigInt& get_p() const; - - /** - * Return the represented value in GF(p) - * @result The value in GF(p) - */ - const BigInt& get_value() const; - - /** - * Tells whether this GFpElement is currently transformed to an m-residue, - * i.e. in the form x_bar = x * r mod m. - * @result true if it is currently transformed to its m-residue. - */ - bool is_trf_to_mres() const; - - /** - * Transforms this to x_bar = x * r mod m - * @result return the value x_bar. - */ - const BigInt& get_mres() const; - - /** - * Check, if montgomery multiplication is used. - * @result true, if montgomery multiplication is used, false otherwise - */ - bool is_use_montgm() const - { - return m_use_montgm; - } - - /** - * Transforms the arguments in such way that either both - * are in m-residue representation (returns true) or both are - * in ordinary residue representation (returns false). - * m-residue is prefered in case of ambiguity. - * does not toggle m_use_montgm of the arguments. - * Don't be confused about the constness of the arguments: - * the transformation between normal residue and m-residue is - * considered as leaving the object const. - * @param lhs the first operand to be aligned - * @param rhs the second operand to be aligned - * @result true if both are transformed to their m-residue, - * false it both are transformed to their normal residue. - */ - static bool align_operands_res(const GFpElement& lhs, const GFpElement& rhs); - - /** - * swaps the states of *this and other, does not throw! - * @param other The value to swap with - */ - void swap(GFpElement& other); - private: - void ensure_montgm_precomp(); - void trf_to_mres() const; - void trf_to_ordres() const; - - GFpModulus modulus; - mutable BigInt m_value; // ordinary residue or m-residue respectively - - // data members for montgomery multiplication - bool m_use_montgm; - mutable bool m_is_trf; // if m_value is montgomery - }; - -// relational operators -bool BOTAN_DLL operator==(const GFpElement& lhs, const GFpElement& rhs); -inline bool operator!=(const GFpElement& lhs, const GFpElement& rhs ) - { - return !operator==(lhs, rhs); - } - -// arithmetic operators -GFpElement BOTAN_DLL operator+(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator-(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator-(const GFpElement& lhs); - -GFpElement BOTAN_DLL operator*(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator/(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator*(const GFpElement& lhs, u32bit rhs); -GFpElement BOTAN_DLL operator*(u32bit rhs, const GFpElement& lhs); - - -/** -* write a GFpElement to an output stream. -* @param output the output stream to write to -* @param elem the object to write -* @result the output stream -*/ -BOTAN_DLL std::ostream& operator<<(std::ostream& output, const GFpElement& elem); - -// return (*this)^(-1) -GFpElement BOTAN_DLL inverse(const GFpElement& elem); - -// encoding and decoding -SecureVector<byte> BOTAN_DLL FE2OSP(const GFpElement& elem); -GFpElement BOTAN_DLL OS2FEP(MemoryRegion<byte> const& os, BigInt p); - -inline void swap(GFpElement& x, GFpElement& y) - { - x.swap(y); - } - -} - -namespace std { - -template<> inline -void swap<Botan::GFpElement>(Botan::GFpElement& x, - Botan::GFpElement& y) - { - x.swap(y); - } - -} - -#endif diff --git a/src/math/gfpmath/gfp_modulus.h b/src/math/gfpmath/gfp_modulus.h deleted file mode 100644 index fcdd13ee1..000000000 --- a/src/math/gfpmath/gfp_modulus.h +++ /dev/null @@ -1,131 +0,0 @@ -/* -* Modulus and related data for a specific implementation of GF(p) -* -* (C) 2008 Martin Doering, Christoph Ludwig, Falko Strenzke -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_MODULUS_H__ -#define BOTAN_GFP_MODULUS_H__ - -#include <botan/bigint.h> - -namespace Botan { - -class GFpElement; - -/** -* This class represents a GFpElement modulus including the modulus -* related values necessary for the montgomery multiplication. -*/ -class BOTAN_DLL GFpModulus - { - public: - - /** - * Construct a GF(P)-Modulus from a BigInt - */ - GFpModulus(const BigInt& p) - : m_p(p), - m_p_dash(), - m_r(), - m_r_inv() - {} - - // GFpModulus(const GFpModulus& other) = default; - // GFpModulus& operator=(const GFpModulus& other) = default; - - /** - * Tells whether the precomputations necessary for the use of the - * montgomery multiplication have yet been established. - * @result true if the precomputated value are already available. - */ - bool has_precomputations() const - { - return(!m_p_dash.is_zero() && !m_r.is_zero() && !m_r_inv.is_zero()); - } - - /** - * Swaps this with another GFpModulus, does not throw. - * @param other the GFpModulus to swap *this with. - */ - void swap(GFpModulus& other) - { - std::swap(m_p, other.m_p); - std::swap(m_p_dash, other.m_p_dash); - std::swap(m_r, other.m_r); - std::swap(m_r_inv, other.m_r_inv); - } - - /** - * Tells whether the modulus of *this is equal to the argument. - * @param mod the modulus to compare this with - * @result true if the modulus of *this and the argument are equal. - */ - bool p_equal_to(const BigInt& mod) const - { - return (m_p == mod); - } - - /** - * Return the modulus of this GFpModulus. - * @result the modulus of *this. - */ - const BigInt& get_p() const - { - return m_p; - } - - /** - * returns the montgomery multiplication related value r. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result r - */ - const BigInt& get_r() const - { - return m_r; - } - - /** - * returns the montgomery multiplication related value r^{-1}. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result r^{-1} - */ - const BigInt& get_r_inv() const - { - return m_r_inv; - } - - /** - * returns the montgomery multiplication related value p'. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result p' - */ - const BigInt& get_p_dash() const - { - return m_p_dash; - } - - void reset_values(const BigInt& new_p_dash, - const BigInt& new_r, - const BigInt& new_r_inv) - { - m_p_dash = new_p_dash; - m_r = new_r; - m_r_inv = new_r_inv; - } - - private: - BigInt m_p; // the modulus itself - BigInt m_p_dash; - BigInt m_r; - BigInt m_r_inv; - }; - -} - -#endif diff --git a/src/math/gfpmath/info.txt b/src/math/gfpmath/info.txt deleted file mode 100644 index b7b430805..000000000 --- a/src/math/gfpmath/info.txt +++ /dev/null @@ -1,19 +0,0 @@ -define BIGINT_GFP - -<header:public> -curve_gfp.h -gfp_element.h -gfp_modulus.h -point_gfp.h -</header:public> - -<source> -curve_gfp.cpp -gfp_element.cpp -point_gfp.cpp -</source> - -<requires> -bigint -numbertheory -</requires> diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp deleted file mode 100644 index 4b2de7913..000000000 --- a/src/math/gfpmath/point_gfp.cpp +++ /dev/null @@ -1,750 +0,0 @@ -/* -* Arithmetic for point groups of elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/point_gfp.h> -#include <botan/numthry.h> - -namespace Botan { - -// construct the point at infinity or a random point -PointGFp::PointGFp(const CurveGFp& curve) : - mC(curve), - mX(curve.get_p(), 0), - mY(curve.get_p(), 1), - mZ(curve.get_p(), 0) - { - } - -// construct a point given its jacobian projective coordinates -PointGFp::PointGFp(const CurveGFp& curve, const GFpElement& x, - const GFpElement& y, const GFpElement& z) : - mC(curve), - mX(x), - mY(y), - mZ(z) - { - } - -PointGFp::PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y) : - mC(curve), - mX(x), - mY(y), - mZ(curve.get_p(),1) - { - } - -// arithmetic operators -PointGFp& PointGFp::operator+=(const PointGFp& rhs) - { - if(is_zero()) - { - *this = rhs; - return *this; - } - if(rhs.is_zero()) - { - return *this; - } - - GFpElement U1 = mX; - GFpElement S1 = mY; - - if(rhs.mZ != mC.get_mres_one()) - { - GFpElement rhs_z2 = rhs.mZ * rhs.mZ; - - U1 *= rhs_z2; - S1 *= rhs_z2 * rhs.mZ; - } - - GFpElement U2 = rhs.mX; - GFpElement S2 = rhs.mY; - - if(mZ != mC.get_mres_one()) - { - GFpElement lhs_z2 = mZ * mZ; - - U2 *= lhs_z2; - S2 *= lhs_z2 * mZ; - } - - GFpElement H(U2 - U1); - GFpElement r(S2 - S1); - - if(H.is_zero()) - { - if(r.is_zero()) - { - mult2_in_place(); - return *this; - } - - *this = PointGFp(mC); // setting myself to zero - return *this; - } - - U2 = H * H; - - S2 = U2 * H; - - U2 *= U1; - - GFpElement x(r*r - S2 - (U2+U2)); - - GFpElement z(S1 * S2); - - GFpElement y(r * (U2-x) - z); - - if(mZ == mC.get_mres_one()) - { - if(rhs.mZ != mC.get_mres_one()) - z = rhs.mZ * H; - else - z = H; - } - else if(rhs.mZ != mC.get_mres_one()) - { - U1 = mZ * rhs.mZ; - z = U1 * H; - } - else - z = mZ * H; - - mX = x; - mY = y; - mZ = z; - - return *this; - - } -PointGFp& PointGFp::operator-=(const PointGFp& rhs) - { - PointGFp minus_rhs = PointGFp(rhs).negate(); - - if(is_zero()) - { - *this = minus_rhs; - } - else - { - *this += minus_rhs; - } - return *this; - } - -PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, - const BigInt& /*point_order*/, - const BigInt& /*max_secr*/) - { - // NOTE: FS: so far this is code duplication of op*=. - // we have to see how we deal with this. - // fact is that we will probably modify this function - // while evaluating the countermeasures - // whereas we probably will not start modifying the - // function operator*=. - // however, in the end both should be merged. - - // use montgomery mult. in this operation - this->turn_on_sp_red_mul(); - - PointGFp H(mC); - - PointGFp P(*this); - BigInt m(scalar); - - if(m < BigInt(0)) - { - m = -m; - P.negate(); - } - if(P.is_zero() || (m == BigInt(0))) - { - *this = H; - return *this; - } - if(m == BigInt(1)) - return *this; - - int mul_bits = m.bits(); - - for(int i = mul_bits - 1; i >= 0; i--) - { - H.mult2_in_place(); - - if(m.get_bit(i)) - H += P; - } - - if(!H.is_zero()) // cannot convert if H == O - *this = H.get_z_to_one(); - else - *this = H; - - mX.turn_off_sp_red_mul(); - mY.turn_off_sp_red_mul(); - mZ.turn_off_sp_red_mul(); - return *this; - } - -PointGFp& PointGFp::operator*=(const BigInt& scalar) - { - // use montgomery mult. in this operation - - this->turn_on_sp_red_mul(); - - PointGFp H(this->mC); // create as zero - H.turn_on_sp_red_mul(); - PointGFp P(*this); - P.turn_on_sp_red_mul(); - BigInt m(scalar); - - if(m < BigInt(0)) - { - m = -m; - P.negate(); - } - - if(P.is_zero() || (m == BigInt(0))) - { - *this = H; - return *this; - } - - if(m == BigInt(1)) //*this == P already - return *this; - - const int l = m.bits() - 1; - for(int i = l; i >= 0; --i) - { - H.mult2_in_place(); - if(m.get_bit(i)) - H += P; - } - - if(!H.is_zero()) // cannot convert if H == O - *this = H.get_z_to_one(); - else - *this = H; - - return *this; - } - -PointGFp& PointGFp::negate() - { - if(!is_zero()) - mY.negate(); - - return *this; - } - -// *this *= 2 -PointGFp& PointGFp::mult2_in_place() - { - if(is_zero()) - return *this; - else if(mY.is_zero()) - { - *this = PointGFp(mC); // setting myself to zero - return *this; - } - - GFpElement Y_squared = mY*mY; - - GFpElement S = mX * Y_squared; - - GFpElement x = S + S; - - S = x + x; - - GFpElement a_z4 = mC.get_mres_a(); - if(mZ != mC.get_mres_one()) - { - GFpElement z2 = mZ * mZ; - a_z4 *= z2; - a_z4 *= z2; - } - - GFpElement y(mX * mX); - - GFpElement M(y + y + y + a_z4); - - x = M * M - (S+S); - - y = Y_squared * Y_squared; - - GFpElement U(y + y); - - GFpElement z = U + U; - - U = z + z; - - y = M * (S - x) - U; - - if(mZ != mC.get_mres_one()) - z = mY * mZ; - else - z = mY; - - z = z + z; - - mX = x; - mY = y; - mZ = z; - - return *this; - } - -void PointGFp::turn_on_sp_red_mul() const - { - mX.turn_on_sp_red_mul(); - mY.turn_on_sp_red_mul(); - mZ.turn_on_sp_red_mul(); - - // also pretransform, otherwise - // we might have bad results with respect to - // performance because - // additions/subtractions in mult2_in_place() - // and op+= spread untransformed GFpElements - mX.get_mres(); - mY.get_mres(); - mZ.get_mres(); - } - -/** -* returns a point equivalent to *this but were -* Z has value one, i.e. x and y correspond to -* their values in affine coordinates -*/ -PointGFp PointGFp::get_z_to_one() const - { - return PointGFp(*this).set_z_to_one(); - } - -/** -* changes the representation of *this so that -* Z has value one, i.e. x and y correspond to -* their values in affine coordinates. -* returns *this. -*/ -const PointGFp& PointGFp::set_z_to_one() const - { - if(!(mZ.get_value() == BigInt(1)) && !(mZ.get_value() == BigInt(0))) - { - GFpElement z = inverse(mZ); - GFpElement z2 = z * z; - z *= z2; - GFpElement x = mX * z2; - GFpElement y = mY * z; - mZ = GFpElement(mC.get_p(), BigInt(1)); - mX = x; - mY = y; - } - else - { - if(mZ.get_value() == BigInt(0)) - { - throw Illegal_Transformation("cannot convert Z to one"); - } - } - return *this; // mZ = 1 already - } - -GFpElement PointGFp::get_affine_x() const - { - if(is_zero()) - throw Illegal_Transformation("cannot convert to affine"); - - GFpElement z2 = mZ * mZ; - return mX * z2.inverse_in_place(); - } - -GFpElement PointGFp::get_affine_y() const - { - if(is_zero()) - throw Illegal_Transformation("cannot convert to affine"); - - GFpElement z3 = mZ * mZ * mZ; - return mY * z3.inverse_in_place(); - } - -GFpElement PointGFp::get_jac_proj_x() const - { - return GFpElement(mX); - } - -GFpElement PointGFp::get_jac_proj_y() const - { - return GFpElement(mY); - } - -GFpElement PointGFp::get_jac_proj_z() const - { - return GFpElement(mZ); - } - -// Is this the point at infinity? -bool PointGFp::is_zero() const - { - return(mX.is_zero() && mZ.is_zero()); - //NOTE: the calls to GFpElement::is_zero() instead of getting the value and - // and comparing it are import because they do not provoke backtransformations - // to the ordinary residue. - } - -// Is the point still on the curve?? -// (If everything is correct, the point is always on its curve; then the -// function will return silently. If Oskar managed to corrupt this object's state, -// then it will throw an exception.) - -void PointGFp::check_invariants() const - { - if(is_zero()) - { - return; - } - const GFpElement y2 = mY * mY; - const GFpElement x3 = mX * mX * mX; - - if(mZ.get_value() == BigInt(1)) - { - GFpElement ax = mC.get_a() * mX; - if(y2 != (x3 + ax + mC.get_b())) - { - throw Illegal_Point(); - } - - } - - GFpElement Zpow2 = mZ * mZ; - GFpElement Zpow3 = Zpow2 * mZ; - GFpElement AZpow4 = Zpow3 * mZ * mC.get_a(); - const GFpElement aXZ4 = AZpow4 * mX; - const GFpElement bZ6 = mC.get_b() * Zpow3 * Zpow3; - - if(y2 != (x3 + aXZ4 + bZ6)) - throw Illegal_Point(); - } - -// swaps the states of *this and other, does not throw! -void PointGFp::swap(PointGFp& other) - { - mC.swap(other.mC); - mX.swap(other.mX); - mY.swap(other.mY); - mZ.swap(other.mZ); - } - -PointGFp mult2(const PointGFp& point) - { - return (PointGFp(point)).mult2_in_place(); - } - -bool operator==(const PointGFp& lhs, PointGFp const& rhs) - { - if(lhs.is_zero() && rhs.is_zero()) - { - return true; - } - if((lhs.is_zero() && !rhs.is_zero()) || (!lhs.is_zero() && rhs.is_zero())) - { - return false; - } - // neither operand is zero, so we can call get_z_to_one() - //assert(!lhs.is_zero()); - //assert(!rhs.is_zero()); - PointGFp aff_lhs = lhs.get_z_to_one(); - PointGFp aff_rhs = rhs.get_z_to_one(); - return (aff_lhs.get_curve() == aff_rhs.get_curve() && - aff_lhs.get_jac_proj_x() == aff_rhs.get_jac_proj_x() && - aff_lhs.get_jac_proj_y() == aff_rhs.get_jac_proj_y()); - } - -// arithmetic operators -PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) - { - PointGFp tmp(lhs); - return tmp += rhs; - } - -PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) - { - PointGFp tmp(lhs); - return tmp -= rhs; - } - -PointGFp operator-(const PointGFp& lhs) - { - return PointGFp(lhs).negate(); - } - -PointGFp operator*(const BigInt& scalar, const PointGFp& point) - { - PointGFp result(point); - return result *= scalar; - } - -PointGFp operator*(const PointGFp& point, const BigInt& scalar) - { - PointGFp result(point); - return result *= scalar; - } - -PointGFp mult_point_secure(const PointGFp& point, const BigInt& scalar, - const BigInt& point_order, const BigInt& max_secret) - { - PointGFp result(point); - result.mult_this_secure(scalar, point_order, max_secret); - return result; - } - -// encoding and decoding -SecureVector<byte> EC2OSP(const PointGFp& point, byte format) - { - SecureVector<byte> result; - if(format == PointGFp::UNCOMPRESSED) - { - result = encode_uncompressed(point); - } - else if(format == PointGFp::COMPRESSED) - { - result = encode_compressed(point); - - } - else if(format == PointGFp::HYBRID) - { - result = encode_hybrid(point); - } - else - { - throw Invalid_Argument("illegal point encoding format specification"); - } - return result; - } -SecureVector<byte> encode_compressed(const PointGFp& point) - { - - - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (l+1); - result[0] = 2; - BigInt x = point.get_affine_x().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - result.copy(1, bX.begin(), bX.size()); - BigInt y = point.get_affine_y().get_value(); - if(y.get_bit(0)) - { - result[0] |= 1; - } - return result; - } - - -SecureVector<byte> encode_uncompressed(const PointGFp& point) - { - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (2*l+1); - result[0] = 4; - BigInt x = point.get_affine_x().get_value(); - BigInt y = point.get_affine_y().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - SecureVector<byte> bY = BigInt::encode_1363(y, l); - result.copy(1, bX.begin(), l); - result.copy(l+1, bY.begin(), l); - return result; - - } - -SecureVector<byte> encode_hybrid(const PointGFp& point) - { - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (2*l+1); - result[0] = 6; - BigInt x = point.get_affine_x().get_value(); - BigInt y = point.get_affine_y().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - SecureVector<byte> bY = BigInt::encode_1363(y, l); - result.copy(1, bX.begin(), bX.size()); - result.copy(l+1, bY.begin(), bY.size()); - if(y.get_bit(0)) - { - result[0] |= 1; - } - return result; - } - -PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve) - { - if(os.size() == 1 && os[0] == 0) - { - return PointGFp(curve); // return zero - } - SecureVector<byte> bX; - SecureVector<byte> bY; - - GFpElement x(1,0); - GFpElement y(1,0); - GFpElement z(1,0); - - const byte pc = os[0]; - BigInt bi_dec_x; - BigInt bi_dec_y; - switch (pc) - { - case 2: - case 3: - //compressed form - bX = SecureVector<byte>(os.size() - 1); - bX.copy(os.begin()+1, os.size()-1); - - bi_dec_x = BigInt::decode(bX, bX.size()); - x = GFpElement(curve.get_p(), bi_dec_x); - bool yMod2; - yMod2 = (pc & 1) == 1; - y = PointGFp::decompress(yMod2, x, curve); - break; - case 4: - // uncompressed form - int l; - l = (os.size() -1)/2; - bX = SecureVector<byte>(l); - bY = SecureVector<byte>(l); - bX.copy(os.begin()+1, l); - bY.copy(os.begin()+1+l, l); - bi_dec_x = BigInt::decode(bX.begin(), bX.size()); - - bi_dec_y = BigInt::decode(bY.begin(),bY.size()); - x = GFpElement(curve.get_p(), bi_dec_x); - y = GFpElement(curve.get_p(), bi_dec_y); - break; - - case 6: - case 7: - //hybrid form - l = (os.size() - 1)/2; - bX = SecureVector<byte>(l); - bY = SecureVector<byte>(l); - bX.copy(os.begin() + 1, l); - bY.copy(os.begin()+1+l, l); - yMod2 = (pc & 0x01) == 1; - if(!(PointGFp::decompress(yMod2, x, curve) == y)) - { - throw Illegal_Point("error during decoding hybrid format"); - } - break; - default: - throw Invalid_Argument("encountered illegal format specification while decoding point"); - } - z = GFpElement(curve.get_p(), BigInt(1)); - //assert((x.is_trf_to_mres() && x.is_use_montgm()) || !x.is_trf_to_mres()); - //assert((y.is_trf_to_mres() && y.is_use_montgm()) || !y.is_trf_to_mres()); - //assert((z.is_trf_to_mres() && z.is_use_montgm()) || !z.is_trf_to_mres()); - PointGFp result(curve, x, y, z); - result.check_invariants(); - //assert((result.get_jac_proj_x().is_trf_to_mres() && result.get_jac_proj_x().is_use_montgm()) || !result.get_jac_proj_x().is_trf_to_mres()); - //assert((result.get_jac_proj_y().is_trf_to_mres() && result.get_jac_proj_y().is_use_montgm()) || !result.get_jac_proj_y().is_trf_to_mres()); - //assert((result.get_jac_proj_z().is_trf_to_mres() && result.get_jac_proj_z().is_use_montgm()) || !result.get_jac_proj_z().is_trf_to_mres()); - return result; - } - -GFpElement PointGFp::decompress(bool yMod2, const GFpElement& x, - const CurveGFp& curve) - { - BigInt xVal = x.get_value(); - BigInt xpow3 = xVal * xVal * xVal; - BigInt g = curve.get_a().get_value() * xVal; - g += xpow3; - g += curve.get_b().get_value(); - g = g%curve.get_p(); - BigInt z = ressol(g, curve.get_p()); - - if(z < 0) - throw Illegal_Point("error during decompression"); - - bool zMod2 = z.get_bit(0); - if((zMod2 && ! yMod2) || (!zMod2 && yMod2)) - { - z = curve.get_p() - z; - } - return GFpElement(curve.get_p(),z); - } - -PointGFp create_random_point(RandomNumberGenerator& rng, - const CurveGFp& curve) - { - - // create a random point - GFpElement mX(1,1); - GFpElement mY(1,1); - GFpElement mZ(1,1); - GFpElement minusOne(curve.get_p(), BigInt(BigInt::Negative,1)); - mY = minusOne; - GFpElement y2(1,1); - GFpElement x(1,1); - - while (mY == minusOne) - { - BigInt value(rng, curve.get_p().bits()); - mX = GFpElement(curve.get_p(),value); - y2 = curve.get_a() * mX; - x = mX * mX; - x *= mX; - y2 += (x + curve.get_b()); - - value = ressol(y2.get_value(), curve.get_p()); - - if(value < 0) - mY = minusOne; - else - mY = GFpElement(curve.get_p(), value); - } - mZ = GFpElement(curve.get_p(), BigInt(1)); - - return PointGFp(curve, mX, mY, mZ); - } - -} // namespace Botan diff --git a/src/math/gfpmath/point_gfp.h b/src/math/gfpmath/point_gfp.h deleted file mode 100644 index 276635f56..000000000 --- a/src/math/gfpmath/point_gfp.h +++ /dev/null @@ -1,268 +0,0 @@ -/* -* Arithmetic for point groups of elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_POINT_GFP_H__ -#define BOTAN_POINT_GFP_H__ - -#include <botan/curve_gfp.h> -#include <vector> - -namespace Botan { - -struct BOTAN_DLL Illegal_Point : public Exception - { - Illegal_Point(const std::string& err = "") : Exception(err) {} - }; - -/** -* This class represents one point on a curve of GF(p) -*/ -class BOTAN_DLL PointGFp - { - public: - /** - * uncompressed encoding byte value - */ - static const int UNCOMPRESSED = 0; - - /** - * compressed encoding byte value - */ - static const int COMPRESSED = 1; - - /** - * hybrid encoding byte value - */ - static const int HYBRID = 2; - - /** - * Construct the point O - * @param curve The base curve - */ - PointGFp(const CurveGFp& curve); - - /** - * Construct a point given its affine coordinates - * @param curve the base curve - * @param x affine x coordinate - * @param y affine y coordinate - */ - PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y); - - /** - * Construct a point given its jacobian projective coordinates - * @param curve the base curve - * @param x jacobian projective x coordinate - * @param y jacobian projective y coordinate - * @param z jacobian projective y coordinate - */ - PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y, - const GFpElement& z); - - //PointGFp(const PointGFp& other) = default; - //PointGFp& operator=(const PointGFp& other) = default; - - /** - * += Operator - * @param rhs the PointGFp to add to the local value - * @result resulting PointGFp - */ - PointGFp& operator+=(const PointGFp& rhs); - - /** - * -= Operator - * @param rhs the PointGFp to subtract from the local value - * @result resulting PointGFp - */ - PointGFp& operator-=(const PointGFp& rhs); - - /** - * *= Operator - * This function turns on the the special reduction multiplication - * itself for fast computation, turns it off again when finished. - * @param scalar the PointGFp to multiply with *this - * @result resulting PointGFp - */ - PointGFp& operator*=(const BigInt& scalar); - - /** - * the equivalent to operator*= with countermeasures against - * sidechannel attacks, using the randomized exponent - * and add-and-double-always - * countermeasures (suitable for ECDSA and ECKAEG) - * @param scalar the scalar to multiply the point with - * @param point_order a multiple of the order of the point - *(= n * k in the general case; k is the cofactor) - * @param max_secr the maximal size of the scalar - * (will usually be n-1 ) - * @result resulting PointGFp - */ - PointGFp& mult_this_secure(const BigInt& scalar, - const BigInt& point_order, - const BigInt& max_secr); - - /** - * Negate internal value(*this *= -1 ) - * @return *this - */ - PointGFp& negate(); - - /** - * Multiply the point by two(*this *= 2 ) - * @return *this - */ - PointGFp& mult2_in_place(); - - /** - * Set z coordinate to one. - * @return *this - */ - const PointGFp& set_z_to_one() const; - - /** - * Turn on the special reduction multiplication (i.e. the - * Montgomery multiplication in the current implementation) for - * the coordinates. This enables fast execution of mult2_in_place() - * and operator+=(). - */ - void turn_on_sp_red_mul() const; - - /** - * Return a point - * where the coordinates are transformed - * so that z equals one, - * thus x and y have just the affine values. - * @result *this - */ - PointGFp get_z_to_one() const; - - /** - * Return base curve of this point - * @result the curve over GF(p) of this point - */ - const CurveGFp& get_curve() const { return mC; } - - /** - * get affine x coordinate - * @result affine x coordinate - */ - GFpElement get_affine_x() const; - - /** - * get affine y coordinate - * @result affine y coordinate - */ - GFpElement get_affine_y() const; - - /** - * get the jacobian projective x coordinate - * @result jacobian projective x coordinate - */ - GFpElement get_jac_proj_x() const; - - /** - * get the jacobian projective y coordinate - * @result jacobian projective y coordinate - */ - GFpElement get_jac_proj_y() const; - - /** - * get the jacobian projective z coordinate - * @result jacobian projective z coordinate - */ - GFpElement get_jac_proj_z() const; - - /** - * Is this the point at infinity? - * @result true, if this point is at infinity, false otherwise. - */ - bool is_zero() const; - - /** - * Checks whether the point is to be found on the underlying curve. - * Throws an Invalid_Point exception in case of detecting that the point - * does not satisfy the curve equation. - * To be used to ensure against fault attacks. - */ - void check_invariants() const; - - /** - * swaps the states of *this and other, does not throw! - * @param other the object to swap values with - */ - void swap(PointGFp& other); - - static GFpElement decompress(bool yMod2, GFpElement const& x, const CurveGFp& curve); - - private: - CurveGFp mC; - mutable GFpElement mX; // NOTE: these values must be mutable (affine<->proj) - mutable GFpElement mY; - mutable GFpElement mZ; - }; - -// relational operators -bool BOTAN_DLL operator==(const PointGFp& lhs, const PointGFp& rhs); -inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs ) - { - return !operator==(lhs, rhs); - } - -// arithmetic operators -PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); -PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); -PointGFp BOTAN_DLL operator-(const PointGFp& lhs); - -PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); -PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); -PointGFp BOTAN_DLL mult_point_secure(const PointGFp& point, - const BigInt& scalar, - const BigInt& point_order, - const BigInt& max_secret); - -PointGFp BOTAN_DLL mult2(const PointGFp& point); - -PointGFp BOTAN_DLL create_random_point(RandomNumberGenerator& rng, - const CurveGFp& curve); - -// encoding and decoding -SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); -PointGFp BOTAN_DLL OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve); - -/* Should these be private? */ -SecureVector<byte> -BOTAN_DLL encode_uncompressed(const PointGFp& point); - -SecureVector<byte> BOTAN_DLL encode_hybrid(const PointGFp& point); -SecureVector<byte> BOTAN_DLL encode_compressed(const PointGFp& point); - -// swaps the states of point1 and point2, does not throw! -// cf. Meyers, Item 25 -inline -void swap(PointGFp& point1, PointGFp& point2 ) - { - point1.swap(point2); - } - -} // namespace Botan - -namespace std { - -// swaps the states of point1 and point2, does not throw! -// cf. Meyers, Item 25 -template<> inline void -swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) { x.swap(y); } - -} // namespace std - -#endif diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h new file mode 100644 index 000000000..697065dfe --- /dev/null +++ b/src/math/numbertheory/curve_gfp.h @@ -0,0 +1,96 @@ +/* +* Elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_GFP_CURVE_H__ +#define BOTAN_GFP_CURVE_H__ + +#include <botan/numthry.h> +#include <botan/reducer.h> + +namespace Botan { + +/** +* This class represents an elliptic curve over GF(p) +*/ +class BOTAN_DLL CurveGFp + { + public: + + /** + * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) + * @param p prime number of the field + * @param a first coefficient + * @param b second coefficient + */ + CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) : + p(p), a(a), b(b), reducer_p(p) {} + + // CurveGFp(const CurveGFp& other) = default; + // CurveGFp& operator=(const CurveGFp& other) = default; + + /** + * Get coefficient a + * @result coefficient a + */ + const BigInt& get_a() const { return a; } + + /** + * Get coefficient b + * @result coefficient b + */ + const BigInt& get_b() const { return b; } + + /** + * Get prime modulus of the field of the curve + * @result prime modulus of the field of the curve + */ + const BigInt& get_p() const { return p; } + + const Modular_Reducer& mod_p() const { return reducer_p; } + + /** + * swaps the states of *this and other, does not throw + * @param other The curve to swap values with + */ + void swap(CurveGFp& other) + { + std::swap(a, other.a); + std::swap(b, other.b); + std::swap(p, other.p); + } + + bool operator==(const CurveGFp& other) const + { + return (p == other.p && a == other.a && b == other.b); + } + + private: + BigInt p, a, b; + Modular_Reducer reducer_p; + }; + +inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) + { + return !(lhs == rhs); + } + +} + +namespace std { + +template<> inline +void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, + Botan::CurveGFp& curve2) + { + curve1.swap(curve2); + } + +} // namespace std + +#endif diff --git a/src/math/numbertheory/info.txt b/src/math/numbertheory/info.txt index 19abfaaa0..58851e055 100644 --- a/src/math/numbertheory/info.txt +++ b/src/math/numbertheory/info.txt @@ -4,7 +4,9 @@ define BIGINT_MATH <header:public> blinding.h +curve_gfp.h numthry.h +point_gfp.h pow_mod.h reducer.h </header:public> @@ -20,6 +22,7 @@ jacobi.cpp make_prm.cpp mp_numth.cpp numthry.cpp +point_gfp.cpp pow_mod.cpp powm_fw.cpp powm_mnt.cpp diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp index 760250712..f79fdec2b 100644 --- a/src/math/numbertheory/numthry.cpp +++ b/src/math/numbertheory/numthry.cpp @@ -1,11 +1,12 @@ /* * Number Theory Functions -* (C) 1999-2009 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/numthry.h> +#include <botan/reducer.h> #include <botan/internal/bit_ops.h> #include <algorithm> @@ -14,6 +15,62 @@ namespace Botan { namespace { /* +* Miller-Rabin Primality Tester +*/ +class MillerRabin_Test + { + public: + bool passes_test(const BigInt& nonce); + MillerRabin_Test(const BigInt& num); + private: + BigInt n, r, n_minus_1; + u32bit s; + Fixed_Exponent_Power_Mod pow_mod; + Modular_Reducer reducer; + }; + +/* +* Miller-Rabin Test +*/ +bool MillerRabin_Test::passes_test(const BigInt& a) + { + if(a < 2 || a >= n_minus_1) + throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); + + BigInt y = pow_mod(a); + if(y == 1 || y == n_minus_1) + return true; + + for(u32bit i = 1; i != s; ++i) + { + y = reducer.square(y); + + if(y == 1) + return false; + if(y == n_minus_1) + return true; + } + return false; + } + +/* +* Miller-Rabin Constructor +*/ +MillerRabin_Test::MillerRabin_Test(const BigInt& num) + { + if(num.is_even() || num < 3) + throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); + + n = num; + n_minus_1 = n - 1; + s = low_zero_bits(n_minus_1); + r = n_minus_1 >> s; + + pow_mod = Fixed_Exponent_Power_Mod(r, n); + reducer = Modular_Reducer(n); + } + +/* * Miller-Rabin Iterations */ u32bit miller_rabin_test_iterations(u32bit bits, bool verify) @@ -300,45 +357,4 @@ bool passes_mr_tests(RandomNumberGenerator& rng, return true; } -/* -* Miller-Rabin Test -*/ -bool MillerRabin_Test::passes_test(const BigInt& a) - { - if(a < 2 || a >= n_minus_1) - throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); - - BigInt y = pow_mod(a); - if(y == 1 || y == n_minus_1) - return true; - - for(u32bit i = 1; i != s; ++i) - { - y = reducer.square(y); - - if(y == 1) - return false; - if(y == n_minus_1) - return true; - } - return false; - } - -/* -* Miller-Rabin Constructor -*/ -MillerRabin_Test::MillerRabin_Test(const BigInt& num) - { - if(num.is_even() || num < 3) - throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); - - n = num; - n_minus_1 = n - 1; - s = low_zero_bits(n_minus_1); - r = n_minus_1 >> s; - - pow_mod = Fixed_Exponent_Power_Mod(r, n); - reducer = Modular_Reducer(n); - } - } diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h index ae2c219fc..080f184a4 100644 --- a/src/math/numbertheory/numthry.h +++ b/src/math/numbertheory/numthry.h @@ -9,7 +9,6 @@ #define BOTAN_NUMBER_THEORY_H__ #include <botan/bigint.h> -#include <botan/reducer.h> #include <botan/pow_mod.h> #include <botan/rng.h> @@ -100,21 +99,6 @@ const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256; extern const u16bit BOTAN_DLL PRIMES[]; extern const u64bit PRIME_PRODUCTS[]; -/* -* Miller-Rabin Primality Tester -*/ -class BOTAN_DLL MillerRabin_Test - { - public: - bool passes_test(const BigInt&); - MillerRabin_Test(const BigInt&); - private: - BigInt n, r, n_minus_1; - u32bit s; - Fixed_Exponent_Power_Mod pow_mod; - Modular_Reducer reducer; - }; - } #endif diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp new file mode 100644 index 000000000..06c42d18c --- /dev/null +++ b/src/math/numbertheory/point_gfp.cpp @@ -0,0 +1,423 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/point_gfp.h> +#include <botan/numthry.h> + +namespace Botan { + +namespace { + +BigInt decompress_point(bool yMod2, + const BigInt& x, + const CurveGFp& curve) + { + BigInt xpow3 = x * x * x; + + BigInt g = curve.get_a() * x; + g += xpow3; + g += curve.get_b(); + g = g % curve.get_p(); + + BigInt z = ressol(g, curve.get_p()); + + if(z < 0) + throw Illegal_Point("error during decompression"); + + if(z.get_bit(0) != yMod2) + z = curve.get_p() - z; + + return z; + } + +} + +// arithmetic operators +PointGFp& PointGFp::operator+=(const PointGFp& rhs) + { + if(rhs.is_zero()) + return *this; + + if(is_zero()) + { + *this = rhs; + return *this; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt rhs_z2 = mod_p.square(rhs.coord_z); + BigInt U1 = mod_p.multiply(coord_x, rhs_z2); + BigInt S1 = mod_p.multiply(coord_y, mod_p.multiply(rhs.coord_z, rhs_z2)); + + BigInt lhs_z2 = mod_p.square(coord_z); + BigInt U2 = mod_p.multiply(rhs.coord_x, lhs_z2); + BigInt S2 = mod_p.multiply(rhs.coord_y, mod_p.multiply(coord_z, lhs_z2)); + + BigInt H = mod_p.reduce(U2 - U1); + BigInt r = mod_p.reduce(S2 - S1); + + if(H.is_zero()) + { + if(r.is_zero()) + { + mult2_in_place(); + return *this; + } + + *this = PointGFp(curve); // setting myself to zero + return *this; + } + + U2 = mod_p.square(H); + + S2 = mod_p.multiply(U2, H); + + U2 = mod_p.multiply(U1, U2); + + BigInt x = mod_p.reduce(mod_p.square(r) - S2 - mod_p.multiply(2, U2)); + BigInt y = mod_p.reduce(mod_p.multiply(r, (U2-x)) - mod_p.multiply(S1, S2)); + BigInt z = mod_p.multiply(mod_p.multiply(coord_z, rhs.coord_z), H); + + coord_x = x; + coord_y = y; + coord_z = z; + + return *this; + } + +PointGFp& PointGFp::operator-=(const PointGFp& rhs) + { + PointGFp minus_rhs = PointGFp(rhs).negate(); + + if(is_zero()) + *this = minus_rhs; + else + *this += minus_rhs; + + return *this; + } + +PointGFp& PointGFp::operator*=(const BigInt& scalar) + { + if(scalar.abs() <= 2) // special cases for small values + { + u32bit value = scalar.abs().to_u32bit(); + + if(value == 0) + *this = PointGFp(curve); // set to zero point + else if(value == 1) + { + if(scalar.is_negative()) + this->negate(); + } + else if(value == 2) + { + this->mult2_in_place(); + if(scalar.is_negative()) + this->negate(); + } + + return *this; + } + + PointGFp H(this->curve); // create as zero + PointGFp P(*this); + + if(scalar.is_negative()) + P.negate(); + + for(int i = scalar.bits() - 1; i >= 0; --i) + { + H.mult2_in_place(); + if(scalar.get_bit(i)) + H += P; + } + + if(!H.is_zero()) // cannot convert if H == O + { + /** + * Convert H to an equivalent point with z == 1, thus x and y + * correspond to their affine coordinates + */ + if(H.coord_z != 1) + { + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z_inv = inverse_mod(H.coord_z, curve.get_p()); + + BigInt z_inv_2 = mod_p.square(z_inv); + + H.coord_x = mod_p.multiply(H.coord_x, z_inv_2); + H.coord_y = mod_p.multiply(H.coord_y, mod_p.multiply(z_inv, z_inv_2)); + H.coord_z = 1; + } + } + + *this = H; + return *this; + } + +PointGFp& PointGFp::negate() + { + if(!is_zero()) + coord_y = curve.get_p() - coord_y; + + return *this; + } + +// *this *= 2 +void PointGFp::mult2_in_place() + { + if(is_zero()) + return; + else if(coord_y.is_zero()) + { + *this = PointGFp(curve); // setting myself to zero + return; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y_2 = mod_p.square(coord_y); + + BigInt S = mod_p.multiply(4, mod_p.multiply(coord_x, y_2)); + + BigInt a_z4 = mod_p.multiply(curve.get_a(), + mod_p.square(mod_p.square(coord_z))); + + BigInt M = mod_p.reduce(a_z4 + 3 * mod_p.square(coord_x)); + + BigInt x = mod_p.reduce(mod_p.square(M) - mod_p.multiply(2, S)); + + BigInt y = mod_p.square(y_2); + + BigInt z = mod_p.multiply(2, mod_p.reduce(y + y)); + + BigInt U = mod_p.reduce(z + z); + + y = mod_p.reduce(mod_p.multiply(M, S - x) - U); + + z = mod_p.multiply(2, mod_p.multiply(coord_y, coord_z)); + + coord_x = x; + coord_y = y; + coord_z = z; + } + +BigInt PointGFp::get_affine_x() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z2 = mod_p.square(coord_z); + return mod_p.multiply(coord_x, inverse_mod(z2, curve.get_p())); + } + +BigInt PointGFp::get_affine_y() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z3 = mod_p.cube(coord_z); + return mod_p.multiply(coord_y, inverse_mod(z3, curve.get_p())); + } + +// Is this the point at infinity? +bool PointGFp::is_zero() const + { + return(coord_x.is_zero() && coord_z.is_zero()); + } + +void PointGFp::check_invariants() const + { + /* + Is the point still on the curve?? (If everything is correct, the + point is always on its curve; then the function will return + silently. If Oskar managed to corrupt this object's state, then it + will throw an exception.) + */ + + if(is_zero()) + return; + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y2 = mod_p.square(coord_y); + BigInt x3 = mod_p.cube(coord_x); + + BigInt ax = mod_p.multiply(coord_x, curve.get_a()); + + if(coord_z == 1) + { + if(mod_p.reduce(x3 + ax + curve.get_b()) != y2) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x + b"); + } + + BigInt z2 = mod_p.square(coord_z); + BigInt z3 = mod_p.multiply(coord_z, z2); + + BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, coord_z), ax); + + BigInt b_z6 = mod_p.multiply(curve.get_b(), mod_p.square(z3)); + + if(y2 != mod_p.reduce(x3 + ax_z4 + b_z6)) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x*z^4 + b*z^6"); + } + +// swaps the states of *this and other, does not throw! +void PointGFp::swap(PointGFp& other) + { + curve.swap(other.curve); + coord_x.swap(other.coord_x); + coord_y.swap(other.coord_y); + coord_z.swap(other.coord_z); + } + +bool PointGFp::operator==(const PointGFp& other) const + { + return (coord_x == other.coord_x && + coord_y == other.coord_y && + coord_z == other.coord_z && + get_curve() == other.get_curve()); + } + +// arithmetic operators +PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp += rhs; + } + +PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp -= rhs; + } + +PointGFp operator-(const PointGFp& lhs) + { + return PointGFp(lhs).negate(); + } + +PointGFp operator*(const BigInt& scalar, const PointGFp& point) + { + PointGFp result(point); + return result *= scalar; + } + +PointGFp operator*(const PointGFp& point, const BigInt& scalar) + { + PointGFp result(point); + return result *= scalar; + } + +// encoding and decoding +SecureVector<byte> EC2OSP(const PointGFp& point, byte format) + { + if(point.is_zero()) + return SecureVector<byte>(1); // single 0 byte + + const u32bit p_bytes = point.get_curve().get_p().bytes(); + + BigInt x = point.get_affine_x(); + BigInt y = point.get_affine_y(); + + SecureVector<byte> bX = BigInt::encode_1363(x, p_bytes); + SecureVector<byte> bY = BigInt::encode_1363(y, p_bytes); + + if(format == PointGFp::UNCOMPRESSED) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 4; + + result.copy(1, bX.begin(), p_bytes); + result.copy(p_bytes+1, bY.begin(), p_bytes); + return result; + } + else if(format == PointGFp::COMPRESSED) + { + SecureVector<byte> result(p_bytes+1); + result[0] = 2; + + result.copy(1, bX.begin(), bX.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else if(format == PointGFp::HYBRID) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 6; + + result.copy(1, bX.begin(), bX.size()); + result.copy(p_bytes+1, bY.begin(), bY.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else + throw Invalid_Argument("illegal point encoding format specification"); + } + +PointGFp OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve) + { + if(os.size() == 1 && os[0] == 0) + return PointGFp(curve); // return zero + + const byte pc = os[0]; + + BigInt x, y; + + if(pc == 2 || pc == 3) + { + //compressed form + x = BigInt::decode(&os[1], os.size() - 1); + + bool yMod2 = ((pc & 0x01) == 1); + y = decompress_point(yMod2, x, curve); + } + else if(pc == 4) + { + // uncompressed form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + } + else if(pc == 6 || pc == 7) + { + // hybrid form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + + bool yMod2 = ((pc & 0x01) == 1); + + if(decompress_point(yMod2, x, curve) != y) + throw Illegal_Point("OS2ECP: Decoding error in hybrid format"); + } + else + throw Invalid_Argument("OS2ECP: Unknown format type"); + + PointGFp result(curve, x, y); + result.check_invariants(); + return result; + } + +} diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h new file mode 100644 index 000000000..0741b5e56 --- /dev/null +++ b/src/math/numbertheory/point_gfp.h @@ -0,0 +1,201 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_POINT_GFP_H__ +#define BOTAN_POINT_GFP_H__ + +#include <botan/curve_gfp.h> +#include <vector> + +namespace Botan { + +struct BOTAN_DLL Illegal_Transformation : public Exception + { + Illegal_Transformation(const std::string& err = + "Requested transformation is not possible") : + Exception(err) {} + }; + +struct BOTAN_DLL Illegal_Point : public Exception + { + Illegal_Point(const std::string& err = "Malformed ECP point detected") : + Exception(err) {} + }; + +/** +* This class represents one point on a curve of GF(p) +*/ +class BOTAN_DLL PointGFp + { + public: + enum Compression_Type { + UNCOMPRESSED = 0, + COMPRESSED = 1, + HYBRID = 2 + }; + + /** + * Construct the point O + * @param curve The base curve + */ + PointGFp(const CurveGFp& curve) : + curve(curve), coord_x(0), coord_y(1), coord_z(0) {} + + /** + * Construct a point given its affine coordinates + * @param curve the base curve + * @param x affine x coordinate + * @param y affine y coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y) : + curve(curve), coord_x(x), coord_y(y), coord_z(1) {} + + /** + * Construct a point given its jacobian projective coordinates + * @param curve the base curve + * @param x jacobian projective x coordinate + * @param y jacobian projective y coordinate + * @param z jacobian projective z coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y, const BigInt& z) : + curve(curve), coord_x(x), coord_y(y), coord_z(z) {} + + //PointGFp(const PointGFp& other) = default; + //PointGFp& operator=(const PointGFp& other) = default; + + /** + * += Operator + * @param rhs the PointGFp to add to the local value + * @result resulting PointGFp + */ + PointGFp& operator+=(const PointGFp& rhs); + + /** + * -= Operator + * @param rhs the PointGFp to subtract from the local value + * @result resulting PointGFp + */ + PointGFp& operator-=(const PointGFp& rhs); + + /** + * *= Operator + * This function turns on the the special reduction multiplication + * itself for fast computation, turns it off again when finished. + * @param scalar the PointGFp to multiply with *this + * @result resulting PointGFp + */ + PointGFp& operator*=(const BigInt& scalar); + + /** + * Negate this point + * @return *this + */ + PointGFp& negate(); + + /** + * Return base curve of this point + * @result the curve over GF(p) of this point + */ + const CurveGFp& get_curve() const { return curve; } + + /** + * get affine x coordinate + * @result affine x coordinate + */ + BigInt get_affine_x() const; + + /** + * get affine y coordinate + * @result affine y coordinate + */ + BigInt get_affine_y() const; + + /** + * get the jacobian projective x coordinate + * @result jacobian projective x coordinate + */ + const BigInt& get_jac_proj_x() const { return coord_x; } + + /** + * get the jacobian projective y coordinate + * @result jacobian projective y coordinate + */ + const BigInt& get_jac_proj_y() const { return coord_y; } + + /** + * get the jacobian projective z coordinate + * @result jacobian projective z coordinate + */ + const BigInt& get_jac_proj_z() const { return coord_z; } + + /** + * Is this the point at infinity? + * @result true, if this point is at infinity, false otherwise. + */ + bool is_zero() const; + + /** + * Checks whether the point is to be found on the underlying curve. + * Throws an Invalid_Point exception in case of detecting that the point + * does not satisfy the curve equation. + * To be used to ensure against fault attacks. + */ + void check_invariants() const; + + /** + * swaps the states of *this and other, does not throw! + * @param other the object to swap values with + */ + void swap(PointGFp& other); + + /** + * Equality operator + */ + bool operator==(const PointGFp& other) const; + private: + /** + * Multiply the point by two + */ + void mult2_in_place(); + + CurveGFp curve; + BigInt coord_x, coord_y, coord_z; + }; + +// relational operators +inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) + { + return !(rhs == lhs); + } + +// arithmetic operators +PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs); + +PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); +PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); + +// encoding and decoding +SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); +PointGFp BOTAN_DLL OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve); + +} + +namespace std { + +template<> +inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) + { x.swap(y); } + +} + +#endif diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp index aa53f1a0e..257ece56e 100644 --- a/src/math/numbertheory/reducer.cpp +++ b/src/math/numbertheory/reducer.cpp @@ -1,12 +1,11 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/reducer.h> -#include <botan/numthry.h> #include <botan/internal/mp_core.h> namespace Botan { @@ -78,20 +77,4 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const return t1; } -/* -* Multiply, followed by a reduction -*/ -BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const - { - return reduce(x * y); - } - -/* -* Square, followed by a reduction -*/ -BigInt Modular_Reducer::square(const BigInt& x) const - { - return reduce(Botan::square(x)); - } - } diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h index d234e0735..80c0f27e1 100644 --- a/src/math/numbertheory/reducer.h +++ b/src/math/numbertheory/reducer.h @@ -1,14 +1,14 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ -#ifndef BOTAN_MODARITH_H__ -#define BOTAN_MODARITH_H__ +#ifndef BOTAN_MODULAR_REDUCER_H__ +#define BOTAN_MODULAR_REDUCER_H__ -#include <botan/bigint.h> +#include <botan/numthry.h> namespace Botan { @@ -18,14 +18,30 @@ namespace Botan { class BOTAN_DLL Modular_Reducer { public: - BigInt multiply(const BigInt&, const BigInt&) const; - BigInt square(const BigInt&) const; - BigInt reduce(const BigInt&) const; + BigInt reduce(const BigInt& x) const; + + /** + * Multiply mod p + */ + BigInt multiply(const BigInt& x, const BigInt& y) const + { return reduce(x * y); } + + /** + * Square mod p + */ + BigInt square(const BigInt& x) const + { return reduce(Botan::square(x)); } + + /** + * Cube mod p + */ + BigInt cube(const BigInt& x) const + { return multiply(x, this->square(x)); } bool initialized() const { return (mod_words != 0); } Modular_Reducer() { mod_words = 0; } - Modular_Reducer(const BigInt&); + Modular_Reducer(const BigInt& mod); private: BigInt modulus, modulus_2, mu; u32bit mod_words, mod2_words, mu_words; diff --git a/src/pubkey/ec_dompar/ec_dompar.cpp b/src/pubkey/ec_dompar/ec_dompar.cpp index 3719153f0..30a121875 100644 --- a/src/pubkey/ec_dompar/ec_dompar.cpp +++ b/src/pubkey/ec_dompar/ec_dompar.cpp @@ -429,18 +429,19 @@ EC_Domain_Params get_ec_dompar(const std::string& oid) std::vector<std::string> dom_par = get_standard_domain_parameter(oid); BigInt p(dom_par[0]); // give as 0x... - GFpElement a(p, BigInt(dom_par[1])); - GFpElement b(p, BigInt(dom_par[2])); + BigInt a(dom_par[1]); + BigInt b(dom_par[2]); + BigInt order(dom_par[4]); + BigInt cofactor(dom_par[5]); Pipe pipe(new Hex_Decoder); pipe.process_msg(dom_par[3]); SecureVector<byte> sv_g = pipe.read_all(); - CurveGFp curve(a, b, p); - PointGFp G = OS2ECP ( sv_g, curve ); + CurveGFp curve(p, a, b); + + PointGFp G = OS2ECP(sv_g, curve); G.check_invariants(); - BigInt order(dom_par[4]); - BigInt cofactor(dom_par[5]); EC_Domain_Params result(curve, G, order, cofactor); return result; } @@ -465,32 +466,32 @@ EC_Domain_Params::EC_Domain_Params(const CurveGFp& curve, const PointGFp& base_p namespace { -SecureVector<byte> encode_der_ec_dompar_explicit(EC_Domain_Params const& dom_pars) +SecureVector<byte> encode_der_ec_dompar_explicit(const EC_Domain_Params& dom_pars) { u32bit ecpVers1 = 1; OID curve_type_oid("1.2.840.10045.1.1"); - DER_Encoder der; + const u32bit p_bytes = dom_pars.get_curve().get_p().bytes(); - der.start_cons(SEQUENCE) + return DER_Encoder() + .start_cons(SEQUENCE) .encode(ecpVers1) .start_cons(SEQUENCE) .encode(curve_type_oid) .encode(dom_pars.get_curve().get_p()) .end_cons() .start_cons(SEQUENCE) - .encode(FE2OSP ( dom_pars.get_curve().get_a() ), OCTET_STRING) - .encode(FE2OSP ( dom_pars.get_curve().get_b() ), OCTET_STRING) + .encode(BigInt::encode_1363(dom_pars.get_curve().get_a(), p_bytes), OCTET_STRING) + .encode(BigInt::encode_1363(dom_pars.get_curve().get_b(), p_bytes), OCTET_STRING) .end_cons() .encode(EC2OSP ( dom_pars.get_base_point(), PointGFp::UNCOMPRESSED), OCTET_STRING) .encode(dom_pars.get_order()) .encode(dom_pars.get_cofactor()) - .end_cons(); - - return der.get_contents(); + .end_cons() + .get_contents(); } -EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded) +EC_Domain_Params decode_ber_ec_dompar_explicit(const SecureVector<byte>& encoded) { BigInt ecpVers1(1); OID curve_type_oid; @@ -500,35 +501,37 @@ EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded SecureVector<byte> sv_base_point; BigInt order; BigInt cofactor; - BER_Decoder dec(encoded); - dec - .start_cons(SEQUENCE) - .decode(ecpVers1) - .start_cons(SEQUENCE) - .decode(curve_type_oid) - .decode(p) - .end_cons() + + BER_Decoder(encoded) .start_cons(SEQUENCE) - .decode(sv_a, OCTET_STRING) - .decode(sv_b, OCTET_STRING) + .decode(ecpVers1) + .start_cons(SEQUENCE) + .decode(curve_type_oid) + .decode(p) + .end_cons() + .start_cons(SEQUENCE) + .decode(sv_a, OCTET_STRING) + .decode(sv_b, OCTET_STRING) + .end_cons() + .decode(sv_base_point, OCTET_STRING) + .decode(order) + .decode(cofactor) .end_cons() - .decode(sv_base_point, OCTET_STRING) - .decode(order) - .decode(cofactor) - .verify_end() - .end_cons(); + .verify_end(); + if(ecpVers1 != 1) - { throw Decoding_Error("wrong ecpVers"); - } + // Set the domain parameters if(curve_type_oid.as_string() != "1.2.840.10045.1.1") // NOTE: hardcoded: prime field type { throw Decoding_Error("wrong curve type oid where prime field was expected"); } - GFpElement a(p,BigInt::decode(sv_a, sv_a.size())); - GFpElement b(p,BigInt::decode(sv_b, sv_b.size())); - CurveGFp curve(a,b,p); + + CurveGFp curve(p, + BigInt::decode(sv_a, sv_a.size()), + BigInt::decode(sv_b, sv_b.size())); + PointGFp G = OS2ECP ( sv_base_point, curve ); G.check_invariants(); return EC_Domain_Params(curve, G, order, cofactor); @@ -536,7 +539,7 @@ EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded } // end anonymous namespace -SecureVector<byte> encode_der_ec_dompar(EC_Domain_Params const& dom_pars, EC_dompar_enc enc_type) +SecureVector<byte> encode_der_ec_dompar(const EC_Domain_Params& dom_pars, EC_dompar_enc enc_type) { SecureVector<byte> result; @@ -560,7 +563,7 @@ SecureVector<byte> encode_der_ec_dompar(EC_Domain_Params const& dom_pars, EC_dom return result; } -EC_Domain_Params decode_ber_ec_dompar(SecureVector<byte> const& encoded) +EC_Domain_Params decode_ber_ec_dompar(const SecureVector<byte>& encoded) { BER_Decoder dec(encoded); BER_Object obj = dec.get_next_object(); @@ -579,7 +582,7 @@ EC_Domain_Params decode_ber_ec_dompar(SecureVector<byte> const& encoded) throw Decoding_Error("encountered unexpected when trying to decode domain parameters"); } -bool operator==(EC_Domain_Params const& lhs, EC_Domain_Params const& rhs) +bool operator==(const EC_Domain_Params& lhs, const EC_Domain_Params& rhs) { return ((lhs.get_curve() == rhs.get_curve()) && (lhs.get_base_point() == rhs.get_base_point()) && diff --git a/src/pubkey/ec_dompar/ec_dompar.h b/src/pubkey/ec_dompar/ec_dompar.h index 5f03f1c5f..f5f573ba9 100644 --- a/src/pubkey/ec_dompar/ec_dompar.h +++ b/src/pubkey/ec_dompar/ec_dompar.h @@ -11,9 +11,7 @@ #define BOTAN_ECC_DOMAIN_PARAMETERS_H__ #include <botan/point_gfp.h> -#include <botan/gfp_element.h> #include <botan/curve_gfp.h> -#include <botan/bigint.h> #include <botan/der_enc.h> #include <botan/ber_dec.h> #include <botan/alg_id.h> diff --git a/src/pubkey/ec_dompar/info.txt b/src/pubkey/ec_dompar/info.txt index b05903b69..fd40b887d 100644 --- a/src/pubkey/ec_dompar/info.txt +++ b/src/pubkey/ec_dompar/info.txt @@ -2,8 +2,7 @@ define ECC_DOMAIN_PARAMATERS <requires> asn1 -bigint filters -gfpmath +numbertheory hex </requires> diff --git a/src/pubkey/ecc_key/ecc_key.cpp b/src/pubkey/ecc_key/ecc_key.cpp index 7d3c79868..e6d4aeae6 100644 --- a/src/pubkey/ecc_key/ecc_key.cpp +++ b/src/pubkey/ecc_key/ecc_key.cpp @@ -163,15 +163,11 @@ void EC_PrivateKey::generate_private_key(RandomNumberGenerator& rng) throw Invalid_State("cannot generate private key when domain parameters are not set"); } - BigInt tmp_private_value(0); - tmp_private_value = BigInt::random_integer(rng, 1, mp_dom_pars->get_order()); + m_private_value = BigInt::random_integer(rng, 1, mp_dom_pars->get_order()); + mp_public_point = std::unique_ptr<PointGFp>( new PointGFp (mp_dom_pars->get_base_point())); - mp_public_point->mult_this_secure(tmp_private_value, - mp_dom_pars->get_order(), - mp_dom_pars->get_order()-1); - //assert(mp_public_point.get() != 0); - tmp_private_value.swap(m_private_value); + *mp_public_point *= m_private_value; } /** diff --git a/src/pubkey/ecc_key/ecc_key.h b/src/pubkey/ecc_key/ecc_key.h index ea0f3f4ad..f8a419ffe 100644 --- a/src/pubkey/ecc_key/ecc_key.h +++ b/src/pubkey/ecc_key/ecc_key.h @@ -10,10 +10,8 @@ #ifndef BOTAN_ECC_PUBLIC_KEY_BASE_H__ #define BOTAN_ECC_PUBLIC_KEY_BASE_H__ -#include <botan/bigint.h> -#include <botan/curve_gfp.h> -#include <botan/pk_keys.h> #include <botan/ec_dompar.h> +#include <botan/pk_keys.h> #include <botan/x509_key.h> #include <botan/pkcs8.h> #include <memory> diff --git a/src/pubkey/ecc_key/info.txt b/src/pubkey/ecc_key/info.txt index 92455189a..4650fb612 100644 --- a/src/pubkey/ecc_key/info.txt +++ b/src/pubkey/ecc_key/info.txt @@ -5,7 +5,6 @@ alloc asn1 bigint ec_dompar -gfpmath numbertheory pk_codecs </requires> diff --git a/src/pubkey/ecdsa/ecdsa.cpp b/src/pubkey/ecdsa/ecdsa.cpp index dffd37e6f..93c65c3a8 100644 --- a/src/pubkey/ecdsa/ecdsa.cpp +++ b/src/pubkey/ecdsa/ecdsa.cpp @@ -40,10 +40,10 @@ ECDSA_PrivateKey::ECDSA_PrivateKey(const EC_Domain_Params& domain, mp_dom_pars = std::unique_ptr<EC_Domain_Params>(new EC_Domain_Params(domain)); m_private_value = x; + mp_public_point = std::unique_ptr<PointGFp>(new PointGFp (mp_dom_pars->get_base_point())); - mp_public_point->mult_this_secure(m_private_value, - mp_dom_pars->get_order(), - mp_dom_pars->get_order()-1); + + *mp_public_point *= m_private_value; try { diff --git a/src/pubkey/ecdsa/ecdsa_op.cpp b/src/pubkey/ecdsa/ecdsa_op.cpp index 7bbeded73..dd92ac5c0 100644 --- a/src/pubkey/ecdsa/ecdsa_op.cpp +++ b/src/pubkey/ecdsa/ecdsa_op.cpp @@ -1,7 +1,7 @@ /* * ECDSA Operation * (C) 2007 FlexSecure GmbH -* 2008-2009 Jack Lloyd +* 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -14,7 +14,8 @@ namespace Botan { Default_ECDSA_Op::Default_ECDSA_Op(const EC_Domain_Params& domain, const BigInt& priv, const PointGFp& pub) : - dom_pars(domain), pub_key(pub), priv_key(priv) + dom_pars(domain), mod_n(dom_pars.get_order()), + pub_key(pub), priv_key(priv) { } @@ -26,10 +27,6 @@ bool Default_ECDSA_Op::verify(const byte msg[], u32bit msg_len, if(sig_len != n.bytes()*2) return false; - // NOTE: it is not checked whether the public point is set - if(dom_pars.get_curve().get_p() == 0) - throw Internal_Error("domain parameters not set"); - BigInt e(msg, msg_len); BigInt r(sig, sig_len / 2); @@ -44,9 +41,7 @@ bool Default_ECDSA_Op::verify(const byte msg[], u32bit msg_len, if(R.is_zero()) return false; - BigInt x = R.get_affine_x().get_value(); - - return (x % n == r); + return (mod_n.reduce(R.get_affine_x()) == r); } SecureVector<byte> Default_ECDSA_Op::sign(const byte msg[], u32bit msg_len, @@ -57,26 +52,18 @@ SecureVector<byte> Default_ECDSA_Op::sign(const byte msg[], u32bit msg_len, const BigInt& n = dom_pars.get_order(); - if(n == 0) - throw Internal_Error("Default_ECDSA_Op::sign(): domain parameters not set"); - BigInt e(msg, msg_len); - PointGFp k_times_P(dom_pars.get_base_point()); - k_times_P.mult_this_secure(k, n, n-1); - k_times_P.check_invariants(); - BigInt r = k_times_P.get_affine_x().get_value() % n; + PointGFp k_times_P = dom_pars.get_base_point() * k; + BigInt r = mod_n.reduce(k_times_P.get_affine_x()); if(r == 0) throw Internal_Error("Default_ECDSA_Op::sign: r was zero"); BigInt k_inv = inverse_mod(k, n); - BigInt s(r); - s *= priv_key; - s += e; - s *= k_inv; - s %= n; + BigInt s = mod_n.reduce(mod_n.multiply(r, priv_key) + e); + s = mod_n.multiply(s, k_inv); SecureVector<byte> output(2*n.bytes()); r.binary_encode(output + (output.size() / 2 - r.bytes())); diff --git a/src/pubkey/ecdsa/ecdsa_op.h b/src/pubkey/ecdsa/ecdsa_op.h index c203905f9..3a492ccf4 100644 --- a/src/pubkey/ecdsa/ecdsa_op.h +++ b/src/pubkey/ecdsa/ecdsa_op.h @@ -10,6 +10,7 @@ #define BOTAN_ECDSA_OPERATIONS_H__ #include <botan/ec_dompar.h> +#include <botan/reducer.h> namespace Botan { @@ -52,6 +53,8 @@ class BOTAN_DLL Default_ECDSA_Op : public ECDSA_Operation const PointGFp& pub_key); private: EC_Domain_Params dom_pars; + Modular_Reducer mod_n; + PointGFp pub_key; BigInt priv_key; }; diff --git a/src/pubkey/ecdsa/info.txt b/src/pubkey/ecdsa/info.txt index be5ac037a..799fff32f 100644 --- a/src/pubkey/ecdsa/info.txt +++ b/src/pubkey/ecdsa/info.txt @@ -5,7 +5,6 @@ alloc asn1 ec_dompar ecc_key -gfpmath libstate numbertheory rng diff --git a/src/pubkey/eckaeg/eckaeg_op.cpp b/src/pubkey/eckaeg/eckaeg_op.cpp index 0cb5c3d55..4fb0a23eb 100644 --- a/src/pubkey/eckaeg/eckaeg_op.cpp +++ b/src/pubkey/eckaeg/eckaeg_op.cpp @@ -1,7 +1,7 @@ /* * ECKAEG Operation * (C) 2007 FlexSecure GmbH -* 2008 Jack Lloyd +* 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -22,15 +22,18 @@ Default_ECKAEG_Op::Default_ECKAEG_Op(const EC_Domain_Params& dom_pars, SecureVector<byte> Default_ECKAEG_Op::agree(const PointGFp& i) const { - BigInt cofactor(m_dom_pars.get_cofactor()); + BigInt cofactor = m_dom_pars.get_cofactor(); BigInt n = m_dom_pars.get_order(); - BigInt l(inverse_mod(cofactor,n)); // l=h^-1 mod n - PointGFp Q(cofactor*i); // q = h*Pb - PointGFp S(Q); - BigInt group_order = m_dom_pars.get_cofactor() * n; - S.mult_this_secure((m_priv_key*l)%n, group_order, n-1); + + BigInt l = inverse_mod(cofactor, n); + + PointGFp S = cofactor * i; + S *= (m_priv_key * l) % n; + S.check_invariants(); - return FE2OSP(S.get_affine_x()); // fe2os(xs) + + return BigInt::encode_1363(S.get_affine_x(), + S.get_curve().get_p().bytes()); } } diff --git a/src/pubkey/eckaeg/info.txt b/src/pubkey/eckaeg/info.txt index 53a744daa..cac352a2a 100644 --- a/src/pubkey/eckaeg/info.txt +++ b/src/pubkey/eckaeg/info.txt @@ -5,7 +5,6 @@ alloc asn1 ec_dompar ecc_key -gfpmath libstate numbertheory </requires> diff --git a/src/pubkey/gost_3410/gost_3410.cpp b/src/pubkey/gost_3410/gost_3410.cpp index 21e2653c9..d3e98665d 100644 --- a/src/pubkey/gost_3410/gost_3410.cpp +++ b/src/pubkey/gost_3410/gost_3410.cpp @@ -2,7 +2,7 @@ * GOST 34.10-2001 implemenation * (C) 2007 Falko Strenzke, FlexSecure GmbH * Manuel Hartl, FlexSecure GmbH -* (C) 2008-2009 Jack Lloyd +* (C) 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -39,9 +39,8 @@ GOST_3410_PrivateKey::GOST_3410_PrivateKey(const EC_Domain_Params& domain, m_private_value = x; mp_public_point = std::unique_ptr<PointGFp>(new PointGFp (mp_dom_pars->get_base_point())); - mp_public_point->mult_this_secure(m_private_value, - mp_dom_pars->get_order(), - mp_dom_pars->get_order()-1); + + *mp_public_point *= m_private_value; try { @@ -73,8 +72,8 @@ X509_Encoder* GOST_3410_PublicKey::x509_encoder() const key->affirm_init(); // Trust CryptoPro to come up with something obnoxious - const BigInt x = key->mp_public_point->get_affine_x().get_value(); - const BigInt y = key->mp_public_point->get_affine_y().get_value(); + const BigInt x = key->mp_public_point->get_affine_x(); + const BigInt y = key->mp_public_point->get_affine_y(); SecureVector<byte> bits(2*std::max(x.bytes(), y.bytes())); @@ -126,8 +125,7 @@ X509_Decoder* GOST_3410_PublicKey::x509_decoder() key->mp_public_point.reset( new PointGFp(key->domain_parameters().get_curve(), - GFpElement(x, p), - GFpElement(y, p))); + x, y)); key->X509_load_hook(); } @@ -235,7 +233,7 @@ bool GOST_3410_PublicKey::verify(const byte msg[], u32bit msg_len, PointGFp R = (z1 * mp_dom_pars->get_base_point() + z2 * *mp_public_point); - return (R.get_affine_x().get_value() == r); + return (R.get_affine_x() == r); } GOST_3410_PublicKey::GOST_3410_PublicKey(const EC_Domain_Params& dom_par, @@ -331,10 +329,10 @@ GOST_3410_PrivateKey::sign(const byte msg[], if(e == 0) e = 1; - PointGFp k_times_P(mp_dom_pars->get_base_point()); - k_times_P.mult_this_secure(k, n, n-1); + PointGFp k_times_P = mp_dom_pars->get_base_point() * k; k_times_P.check_invariants(); - BigInt r = k_times_P.get_affine_x().get_value() % n; + + BigInt r = k_times_P.get_affine_x() % n; if(r == 0) throw Internal_Error("GOST_3410::sign: r was zero"); diff --git a/src/pubkey/gost_3410/info.txt b/src/pubkey/gost_3410/info.txt index 1d6c1ed17..05df445ec 100644 --- a/src/pubkey/gost_3410/info.txt +++ b/src/pubkey/gost_3410/info.txt @@ -7,7 +7,6 @@ alloc asn1 ec_dompar ecc_key -gfpmath libstate numbertheory rng diff --git a/src/stream/ctr/ctr.cpp b/src/stream/ctr/ctr.cpp index 0b0f72da2..421c9f0c0 100644 --- a/src/stream/ctr/ctr.cpp +++ b/src/stream/ctr/ctr.cpp @@ -22,8 +22,8 @@ CTR_BE::CTR_BE(BlockCipher* ciph) : { position = 0; - counter.resize(permutation->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_CTR); - buffer.resize(permutation->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_CTR); + counter.resize(permutation->BLOCK_SIZE * permutation->parallelism()); + buffer.resize(counter.size()); } /* |