secp256k1 supports GLV method

2 files changed, 24 insertions, 170 deletions

diff --git a/include/mcl/ec.hpp b/include/mcl/ec.hpp
index 115a8de..dd77193 100644
--- a/include/mcl/ec.hpp
+++ b/include/mcl/ec.hpp
@@ -10,7 +10,6 @@
 #include <cybozu/exception.hpp>
 #include <mcl/op.hpp>
 #include <mcl/util.hpp>
-#include <mcl/array.hpp>
 
 //#define MCL_EC_USE_AFFINE
 
@@ -1109,10 +1108,6 @@ public:
 	}
 #endif
 	/*
-		initGLV1() is defined in bn.hpp
-	*/
-	/*
-		L = lambda = p^4
 		L (x, y) = (rw x, y)
 	*/
 	static void mulLambda(G& Q, const G& P)
@@ -1183,6 +1178,28 @@ public:
 		if (isNegative) s = -s;
 		mul(z, x, s, constTime);
 	}
+	/*
+		initForBN() is defined in bn.hpp
+	*/
+	static void initForSecp256k1(const mpz_class& _r)
+	{
+		bool b = F::squareRoot(rw, -3);
+		assert(b);
+		(void)b;
+		rw = -(rw + 1) / 2;
+		r = _r;
+		rBitSize = gmp::getBitSize(r);
+		rBitSize = (rBitSize + fp::UnitBitSize - 1) & ~(fp::UnitBitSize - 1);
+		gmp::setStr(&b, B[0][0], "0x3086d221a7d46bcde86c90e49284eb15");
+		assert(b); (void)b;
+		gmp::setStr(&b, B[0][1], "-0xe4437ed6010e88286f547fa90abfe4c3");
+		assert(b); (void)b;
+		gmp::setStr(&b, B[1][0], "0x114ca50f7a8e2f3f657c1108d9d44cfd8");
+		assert(b); (void)b;
+		B[1][1] = B[0][0];
+		v0 = ((B[1][1]) << rBitSize) / r;
+		v1 = ((-B[0][1]) << rBitSize) / r;
+	}
 };
 
 // rw = 1 / w = (-1 - sqrt(-3)) / 2
diff --git a/test/ecdsa_test.cpp b/test/ecdsa_test.cpp
index 28f689e..f015514 100644
--- a/test/ecdsa_test.cpp
+++ b/test/ecdsa_test.cpp
@@ -15,174 +15,11 @@ void put(const void *buf, size_t bufSize)
 
 using namespace mcl::ecdsa;
 
-typedef mcl::FixedArray<int8_t, 256 / 2 + 2> NafArray;
-
-template<class G>
-void addTbl(G& Q, const G *tbl, const NafArray& naf, size_t i)
-{
-	if (i >= naf.size()) return;
-	int n = naf[i];
-	if (n > 0) {
-		Q += tbl[(n - 1) >> 1];
-	} else if (n < 0) {
-		Q -= tbl[(-n - 1) >> 1];
-	}
-}
-
-using namespace mcl;
-
-template<class G1>
-struct GLV1 {
-	Fp rw; // rw = 1 / w = (-1 - sqrt(-3)) / 2
-	size_t rBitSize;
-	mpz_class v0, v1;
-	mpz_class B[2][2];
-	mpz_class r;
-private:
-public:
-	bool operator==(const GLV1& rhs) const
-	{
-		return rw == rhs.rw && rBitSize == rhs.rBitSize && v0 == rhs.v0 && v1 == rhs.v1
-			&& B[0][0] == rhs.B[0][0] && B[0][1] == rhs.B[0][1] && B[1][0] == rhs.B[1][0]
-			&& B[1][1] == rhs.B[1][1] && r == rhs.r;
-	}
-	bool operator!=(const GLV1& rhs) const { return !operator==(rhs); }
-#ifndef CYBOZU_DONT_USE_STRING
-	void dump(const mpz_class& x) const
-	{
-		printf("\"%s\",\n", mcl::gmp::getStr(x, 16).c_str());
-	}
-	void dump() const
-	{
-		printf("\"%s\",\n", rw.getStr(16).c_str());
-		printf("%d,\n", (int)rBitSize);
-		dump(v0);
-		dump(v1);
-		dump(B[0][0]); dump(B[0][1]); dump(B[1][0]); dump(B[1][1]);
-		dump(r);
-	}
-#endif
-	void init(const mpz_class& r, const mpz_class& z, bool isBLS12 = false, int curveType = -1)
-	{
-	}
-	/*
-		L = lambda = p^4
-		L (x, y) = (rw x, y)
-	*/
-	void mulLambda(G1& Q, const G1& P) const
-	{
-		Fp::mul(Q.x, P.x, rw);
-		Q.y = P.y;
-		Q.z = P.z;
-	}
-	/*
-		x = a + b * lambda mod r
-	*/
-	void split(mpz_class& a, mpz_class& b, const mpz_class& x) const
-	{
-		mpz_class t;
-		t = (x * v0) >> rBitSize;
-		b = (x * v1) >> rBitSize;
-//t = (B[1][1] * x) / r;
-//b = (-B[0][1] * x) / r;
-		a = x - (t * B[0][0] + b * B[1][0]);
-		b = - (t * B[0][1] + b * B[1][1]);
-	}
-	void mul(G1& Q, const G1& P, mpz_class x, bool constTime = false) const
-	{
-		const int w = 5;
-		const size_t tblSize = 1 << (w - 2);
-		NafArray naf[2];
-		mpz_class u[2];
-		G1 tbl[2][tblSize];
-		bool b;
-
-		x %= r;
-		if (x == 0) {
-			Q.clear();
-			if (!constTime) return;
-		}
-		if (x < 0) {
-			x += r;
-		}
-		split(u[0], u[1], x);
-		gmp::getNAFwidth(&b, naf[0], u[0], w);
-		assert(b); (void)b;
-		gmp::getNAFwidth(&b, naf[1], u[1], w);
-		assert(b); (void)b;
-
-		tbl[0][0] = P;
-		mulLambda(tbl[1][0], tbl[0][0]);
-		{
-			G1 P2;
-			G1::dbl(P2, P);
-			for (size_t i = 1; i < tblSize; i++) {
-				G1::add(tbl[0][i], tbl[0][i - 1], P2);
-				mulLambda(tbl[1][i], tbl[0][i]);
-			}
-		}
-		const size_t maxBit = fp::max_(naf[0].size(), naf[1].size());
-		Q.clear();
-		for (size_t i = 0; i < maxBit; i++) {
-			G1::dbl(Q, Q);
-			addTbl(Q, tbl[0], naf[0], maxBit - 1 - i);
-			addTbl(Q, tbl[1], naf[1], maxBit - 1 - i);
-		}
-	}
-};
-
-static GLV1<Ec> glv1;
-
-inline void mulArrayEc(Ec& z, const Ec& x, const mcl::fp::Unit *y, size_t yn, bool isNegative, bool constTime)
-{
-	mpz_class s;
-	bool b;
-	mcl::gmp::setArray(&b, s, y, yn);
-	assert(b);
-	if (isNegative) s = -s;
-	glv1.mul(z, x, s, constTime);
-}
-
-void initGLV()
-{
-	const mcl::ecdsa::local::Param& p = mcl::ecdsa::local::getParam();
-	const mcl::EcParam& ecParam = p.ecParam;
-	{
-		Fp& rw = glv1.rw;
-		bool b = Fp::squareRoot(rw, -3);
-		assert(b);
-		printf("b=%d\n", b);
-		if (!b) exit(1);
-		rw = -(rw + 1) / 2;
-		glv1.r = ecParam.n;
-		glv1.rBitSize = gmp::getBitSize(glv1.r);
-		glv1.rBitSize = (glv1.rBitSize + fp::UnitBitSize - 1) & ~(fp::UnitBitSize - 1);
-		gmp::setStr(glv1.B[0][0], "0x3086d221a7d46bcde86c90e49284eb15");
-		gmp::setStr(glv1.B[0][1], "-0xe4437ed6010e88286f547fa90abfe4c3");
-		gmp::setStr(glv1.B[1][0], "0x114ca50f7a8e2f3f657c1108d9d44cfd8");
-		glv1.B[1][1] = glv1.B[0][0];
-		glv1.v0 = ((glv1.B[1][1]) << glv1.rBitSize) / glv1.r;
-		glv1.v1 = ((-glv1.B[0][1]) << glv1.rBitSize) / glv1.r;
-	}
-	PUT(p.P);
-	Ec Q1, Q2;
-	mpz_class L;
-	gmp::setStr(L, "0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72");
-	PUT(L);
-	Ec::mul(Q1, p.P, L);
-	PUT(Q1);
-	glv1.mulLambda(Q2, p.P);
-	PUT(Q2);
-	PUT(Q1 == Q2);
-	// enable GLV
-	Ec::setMulArrayGLV(mulArrayEc);
-}
-
-
 CYBOZU_TEST_AUTO(ecdsa)
 {
 	init();
-	initGLV();
+	mcl::GLV1T<Fp, Ec>::initForSecp256k1(Zn::getOp().mp);
+	Ec::setMulArrayGLV(mcl::GLV1T<Fp, Ec>::mulArray);
 	SecretKey sec;
 	PublicKey pub;
 	sec.setByCSPRNG();