Convert 3-arg constructoor of PointGFp to take BigInts instead of

GFpElements.

Clean up OS2ECP

4 files changed, 97 insertions, 155 deletions

diff --git a/checks/ec_tests.cpp b/checks/ec_tests.cpp
index e5295288d..ae8ee65e9 100644
--- a/checks/ec_tests.cpp
+++ b/checks/ec_tests.cpp
@@ -131,7 +131,8 @@ void test_coordinates()
    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));
+   PointGFp point_exp(secp160r1, exp_affine_x, exp_affine_y);
+
    try
       {
       point_exp.check_invariants();
@@ -529,9 +530,7 @@ void test_mult_point()
 
    p1 *= p0.get_jac_proj_x().get_value();
 
-   PointGFp expected(secp160r1,
-                     GFpElement(bi_p_secp, BigInt(exp_mult_x)),
-                     GFpElement(bi_p_secp, BigInt(exp_mult_y)));
+   PointGFp expected(secp160r1, exp_mult_x, exp_mult_y);
 
    CHECK(p1 == expected);
    }
diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp
index f6aa97aa0..9947ea41b 100644
--- a/src/math/gfpmath/point_gfp.cpp
+++ b/src/math/gfpmath/point_gfp.cpp
@@ -2,7 +2,7 @@
 * Arithmetic for point groups of elliptic curves over GF(p)
 *
 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-*     2008 Jack Lloyd
+*     2008-2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -12,6 +12,32 @@
 
 namespace Botan {
 
+namespace {
+
+BigInt decompress_point(bool yMod2,
+                        const BigInt& x,
+                        const CurveGFp& curve)
+   {
+   BigInt xpow3 = x * x * x;
+
+   BigInt g = curve.get_a().get_value() * x;
+   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");
+
+   if(z.get_bit(0) != yMod2)
+      z = curve.get_p() - z;
+
+   return z;
+   }
+
+}
+
 // construct the point at infinity or a random point
 PointGFp::PointGFp(const CurveGFp& curve) :
    mC(curve),
@@ -32,11 +58,11 @@ PointGFp::PointGFp(const CurveGFp& curve, const GFpElement& x,
    }
 
 PointGFp::PointGFp(const CurveGFp& curve,
-                   const GFpElement& x,
-                   const GFpElement& y) :
+                   const BigInt& x,
+                   const BigInt& y) :
    mC(curve),
-   mX(x),
-   mY(y),
+   mX(curve.get_p(),x),
+   mY(curve.get_p(),y),
    mZ(curve.get_p(),1)
    {
    }
@@ -277,22 +303,20 @@ GFpElement PointGFp::get_affine_y() const
 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
    {
+   /*
+   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 GFpElement y2 = mY * mY;
    const GFpElement x3 = mX * mX * mX;
 
@@ -363,37 +387,25 @@ PointGFp operator*(const PointGFp& point, const BigInt& scalar)
 // encoding and decoding
 SecureVector<byte> EC2OSP(const PointGFp& point, byte format)
    {
-   SecureVector<byte> result;
    if(format == PointGFp::UNCOMPRESSED)
-      {
-      result = encode_uncompressed(point);
-      }
+      return result = encode_uncompressed(point);
    else if(format == PointGFp::COMPRESSED)
-      {
-      result = encode_compressed(point);
-
-      }
+      return encode_compressed(point);
    else if(format == PointGFp::HYBRID)
-      {
-      result = encode_hybrid(point);
-      }
+      return 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)
@@ -414,7 +426,6 @@ SecureVector<byte> encode_compressed(const PointGFp& point)
    return result;
    }
 
-
 SecureVector<byte> encode_uncompressed(const PointGFp& point)
    {
    if(point.is_zero())
@@ -472,130 +483,69 @@ SecureVector<byte> encode_hybrid(const PointGFp& point)
    return result;
    }
 
-PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve)
+PointGFp OS2ECP(const MemoryRegion<byte>& 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)
+
+   BigInt x, y;
+
+   if(pc == 2 || pc == 3)
       {
-      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");
+      //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;
 
-   PointGFp result(curve, x, y);
-   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;
-   }
+      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;
 
-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());
+      x = BigInt::decode(&os[1], l);
+      y = BigInt::decode(&os[l+1], l);
 
-   if(z < 0)
-      throw Illegal_Point("error during decompression");
+      bool yMod2 = ((pc & 0x01) == 1);
 
-   bool zMod2 = z.get_bit(0);
-   if((zMod2 && ! yMod2) || (!zMod2 && yMod2))
-      {
-      z = curve.get_p() - z;
+      if(decompress_point(yMod2, x, curve) != y)
+         throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
       }
-   return GFpElement(curve.get_p(),z);
+   else
+      throw Invalid_Argument("OS2ECP: Unknown format type");
+
+   PointGFp result(curve, x, y);
+   result.check_invariants();
+   return result;
    }
 
 PointGFp create_random_point(RandomNumberGenerator& rng,
                              const CurveGFp& curve)
    {
+   const BigInt& p = curve.get_p();
 
-   // 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)
+   while(true)
       {
-      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);
-      }
+      BigInt r(rng, p.bits());
+
+      GFpElement x = GFpElement(p, r);
+      GFpElement x3 = x * x * x;
 
-   return PointGFp(curve, mX, mY);
+      GFpElement y = (curve.get_a() * x) + (x3 * curve.get_b());
+
+      if(ressol(y.get_value(), p) > 0)
+         return PointGFp(curve, x.get_value(), y.get_value());
+      }
    }
 
 } // namespace Botan
diff --git a/src/math/gfpmath/point_gfp.h b/src/math/gfpmath/point_gfp.h
index 8f189ccd5..9c67ae53c 100644
--- a/src/math/gfpmath/point_gfp.h
+++ b/src/math/gfpmath/point_gfp.h
@@ -44,9 +44,7 @@ class BOTAN_DLL PointGFp
       * @param x affine x coordinate
       * @param y affine y coordinate
       */
-      PointGFp(const CurveGFp& curve,
-               const GFpElement& x,
-               const GFpElement& y);
+      PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y);
 
       /**
       * Construct a point given its jacobian projective coordinates
@@ -87,13 +85,13 @@ class BOTAN_DLL PointGFp
       PointGFp& operator*=(const BigInt& scalar);
 
       /**
-      * Negate internal value(*this *= -1 )
+      * Negate this point
       * @return *this
       */
       PointGFp& negate();
 
       /**
-      * Multiply the point by two(*this *= 2 )
+      * Multiply the point by two
       * @return *this
       */
       PointGFp& mult2_in_place();
@@ -169,8 +167,6 @@ class BOTAN_DLL PointGFp
       */
       void swap(PointGFp& other);
 
-      static GFpElement decompress(bool yMod2, GFpElement const& x, const CurveGFp& curve);
-
       /**
       * Equality operator
       */
@@ -183,7 +179,7 @@ class BOTAN_DLL PointGFp
    };
 
 // relational operators
-inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs )
+inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs)
    {
    return !(rhs == lhs);
    }
@@ -204,16 +200,14 @@ 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_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 )
+void swap(PointGFp& point1, PointGFp& point2)
    {
    point1.swap(point2);
    }
diff --git a/src/pubkey/gost_3410/gost_3410.cpp b/src/pubkey/gost_3410/gost_3410.cpp
index 43e8a9c7b..bb68e2b8d 100644
--- a/src/pubkey/gost_3410/gost_3410.cpp
+++ b/src/pubkey/gost_3410/gost_3410.cpp
@@ -125,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();
             }