From 4457657ac6048b5e0766dcc38d902d8fe99f2827 Mon Sep 17 00:00:00 2001 From: lloyd Date: Thu, 25 Feb 2010 01:35:33 +0000 Subject: Convert 3-arg constructoor of PointGFp to take BigInts instead of GFpElements. Clean up OS2ECP --- checks/ec_tests.cpp | 7 +- src/math/gfpmath/point_gfp.cpp | 224 ++++++++++++++----------------------- src/math/gfpmath/point_gfp.h | 18 +-- src/pubkey/gost_3410/gost_3410.cpp | 3 +- 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 EC2OSP(const PointGFp& point, byte format) { - SecureVector 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 encode_compressed(const PointGFp& point) { - - if(point.is_zero()) { SecureVector 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 encode_compressed(const PointGFp& point) return result; } - SecureVector encode_uncompressed(const PointGFp& point) { if(point.is_zero()) @@ -472,130 +483,69 @@ SecureVector encode_hybrid(const PointGFp& point) return result; } -PointGFp OS2ECP(MemoryRegion const& os, const CurveGFp& curve) +PointGFp OS2ECP(const MemoryRegion& os, const CurveGFp& curve) { if(os.size() == 1 && os[0] == 0) - { return PointGFp(curve); // return zero - } - SecureVector bX; - SecureVector 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(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(l); - bY = SecureVector(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(l); - bY = SecureVector(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 BOTAN_DLL EC2OSP(const PointGFp& point, byte format); PointGFp BOTAN_DLL OS2ECP(MemoryRegion const& os, const CurveGFp& curve); /* Should these be private? */ -SecureVector -BOTAN_DLL encode_uncompressed(const PointGFp& point); - +SecureVector BOTAN_DLL encode_uncompressed(const PointGFp& point); SecureVector BOTAN_DLL encode_hybrid(const PointGFp& point); SecureVector 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(); } -- cgit v1.2.3