Switch to using Montgomery ladder for EC point multiplication.

The test function create_random_point did not actually create a point
on the curve - fix.

2 files changed, 79 insertions, 103 deletions

diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp
index 6bae35e5f..a4856cef8 100644
--- a/src/lib/math/ec_gfp/point_gfp.cpp
+++ b/src/lib/math/ec_gfp/point_gfp.cpp
@@ -243,6 +243,8 @@ PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
 
 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
    {
+   //BOTAN_ASSERT(point.on_the_curve(), "Input is valid");
+
    const CurveGFp& curve = point.get_curve();
 
    if(scalar.is_zero())
@@ -267,8 +269,6 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
 
    const size_t scalar_bits = scalar.bits();
 
-#if 0
-
    PointGFp x1 = PointGFp(curve);
    PointGFp x2 = point;
 
@@ -296,53 +296,9 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
    if(scalar.is_negative())
       x1.negate();
 
-   return x1;
-
-#else
-   const size_t window_size = 4;
-
-   std::vector<PointGFp> Ps(1 << window_size);
-   Ps[0] = PointGFp(curve);
-   Ps[1] = point;
-
-   for(size_t i = 2; i != Ps.size(); ++i)
-      {
-      Ps[i] = Ps[i-1];
-      Ps[i].add(point, ws);
-      }
+   //BOTAN_ASSERT(x1.on_the_curve(), "Output is on the curve");
 
-   PointGFp H(curve); // create as zero
-   size_t bits_left = scalar_bits;
-
-   while(bits_left >= window_size)
-      {
-      for(size_t i = 0; i != window_size; ++i)
-         H.mult2(ws);
-
-      const u32bit nibble = scalar.get_substring(bits_left - window_size,
-                                                 window_size);
-
-      H.add(Ps[nibble], ws);
-
-      bits_left -= window_size;
-      }
-
-   while(bits_left)
-      {
-      H.mult2(ws);
-      if(scalar.get_bit(bits_left-1))
-         H.add(point, ws);
-
-      --bits_left;
-      }
-
-   if(scalar.is_negative())
-      H.negate();
-
-   //BOTAN_ASSERT(H.on_the_curve(), "Fault detected");
-
-   return H;
-#endif
+   return x1;
    }
 
 BigInt PointGFp::get_affine_x() const
diff --git a/src/tests/unit_ecc.cpp b/src/tests/unit_ecc.cpp
index 6834a7f59..976e9d385 100644
--- a/src/tests/unit_ecc.cpp
+++ b/src/tests/unit_ecc.cpp
@@ -42,18 +42,18 @@ PointGFp create_random_point(RandomNumberGenerator& rng,
 
    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);
+      const BigInt x = BigInt::random_integer(rng, 1, p);
+      const BigInt x3 = mod_p.multiply(x, mod_p.square(x));
+      const BigInt ax = mod_p.multiply(curve.get_a(), x);
+      const BigInt y = mod_p.reduce(x3 + ax + curve.get_b());
+      const BigInt sqrt_y = ressol(y, p);
+
+      if(sqrt_y > 1)
+         {
+         BOTAN_ASSERT_EQUAL(mod_p.square(sqrt_y), y, "Square root is correct");
+         PointGFp point(curve, x, sqrt_y);
+         return point;
+         }
       }
    }
 
@@ -756,7 +756,7 @@ size_t test_point_swap()
 
    PointGFp a(create_random_point(rng, dom_pars.get_curve()));
    PointGFp b(create_random_point(rng, dom_pars.get_curve()));
-   b *= BigInt(20);
+   b *= BigInt(rng, 20);
 
    PointGFp c(a);
    PointGFp d(b);
@@ -764,6 +764,7 @@ size_t test_point_swap()
    d.swap(c);
    CHECK(a == d);
    CHECK(b == c);
+
    return fails;
    }
 
@@ -780,14 +781,23 @@ size_t test_mult_sec_mass()
    EC_Group dom_pars(OID("1.3.132.0.8"));
    for(int i = 0; i<50; i++)
       {
-      PointGFp a(create_random_point(rng, dom_pars.get_curve()));
-      BigInt scal(BigInt(rng, 40));
-      PointGFp b = a * scal;
-      PointGFp c(a);
-
-      c *= scal;
-      CHECK(b == c);
+      try
+         {
+         PointGFp a(create_random_point(rng, dom_pars.get_curve()));
+         BigInt scal(BigInt(rng, 40));
+         PointGFp b = a * scal;
+         PointGFp c(a);
+
+         c *= scal;
+         CHECK(b == c);
+         }
+      catch(std::exception& e)
+         {
+         std::cout << "test_mult_sec_mass failed: " << e.what() << "\n";
+         ++fails;
+         }
       }
+
    return fails;
    }
 
@@ -807,37 +817,8 @@ size_t test_curve_cp_ctor()
    return 0;
    }
 
-size_t randomized_test(RandomNumberGenerator& rng, const EC_Group& group)
+size_t ecc_randomized_test()
    {
-   const BigInt a = BigInt::random_integer(rng, 2, group.get_order());
-   const BigInt b = BigInt::random_integer(rng, 2, group.get_order());
-   const BigInt c = a + b;
-
-   const PointGFp P = group.get_base_point() * a;
-   const PointGFp Q = group.get_base_point() * b;
-   const PointGFp R = group.get_base_point() * c;
-
-   const PointGFp A1 = P + Q;
-   const PointGFp A2 = Q + P;
-
-   size_t fails = 0;
-
-   CHECK(A1 == R);
-   CHECK(A2 == R);
-   CHECK(P.on_the_curve());
-   CHECK(Q.on_the_curve());
-   CHECK(R.on_the_curve());
-   CHECK(A1.on_the_curve());
-   CHECK(A2.on_the_curve());
-
-   return fails;
-   }
-
-size_t randomized_test()
-   {
-   AutoSeeded_RNG rng;
-   size_t fails = 0;
-
    const std::vector<std::string> groups = {
       "brainpool160r1",
       "brainpool192r1",
@@ -869,17 +850,55 @@ size_t randomized_test()
       "x962_p239v3"
    };
 
+   AutoSeeded_RNG rng;
+   size_t fails = 0;
+   size_t tests = 0;
+
    for(auto&& group_name : groups)
       {
       EC_Group group(group_name);
 
-      PointGFp inf = group.get_base_point() * group.get_order();
-      CHECK(inf.is_zero());
+      const PointGFp& base_point = group.get_base_point();
+      const BigInt& group_order = group.get_order();
 
-      for(size_t i = 0; i != 32; ++i)
-         fails += randomized_test(rng, group);
+      const PointGFp inf = base_point * group_order;
+      CHECK(inf.is_zero());
+      CHECK(inf.on_the_curve());
+
+      try
+         {
+         for(size_t i = 0; i != 10; ++i)
+            {
+            ++tests;
+
+            const BigInt a = BigInt::random_integer(rng, 2, group_order);
+            const BigInt b = BigInt::random_integer(rng, 2, group_order);
+            const BigInt c = a + b;
+
+            const PointGFp P = base_point * a;
+            const PointGFp Q = base_point * b;
+            const PointGFp R = base_point * c;
+
+            const PointGFp A1 = P + Q;
+            const PointGFp A2 = Q + P;
+
+            CHECK(A1 == R);
+            CHECK(A2 == R);
+            CHECK(P.on_the_curve());
+            CHECK(Q.on_the_curve());
+            CHECK(R.on_the_curve());
+            CHECK(A1.on_the_curve());
+            CHECK(A2.on_the_curve());
+            }
+         }
+      catch(std::exception& e)
+         {
+         std::cout << "Testing " << group_name << " failed: " << e.what() << "\n";
+         ++fails;
+         }
       }
 
+   test_report("ECC Randomized", tests, fails);
    return fails;
    }
 #endif
@@ -915,9 +934,10 @@ size_t test_ecc_unit()
    fails += test_point_swap();
    fails += test_mult_sec_mass();
    fails += test_curve_cp_ctor();
-   fails += randomized_test();
 
    test_report("ECC", 0, fails);
+
+   ecc_randomized_test();
 #endif
 
    return fails;