mulGeneric is constant time

8 files changed, 56 insertions, 44 deletions

diff --git a/include/mcl/bn.h b/include/mcl/bn.h
index c25ee8b..fb7053e 100644
--- a/include/mcl/bn.h
+++ b/include/mcl/bn.h
@@ -190,7 +190,6 @@ MCLBN_DLL_API void mclBnG1_mul(mclBnG1 *z, const mclBnG1 *x, const mclBnFr *y);
 
 /*
 	constant time mul
-	@note depending on bit length of y
 */
 MCLBN_DLL_API void mclBnG1_mulCT(mclBnG1 *z, const mclBnG1 *x, const mclBnFr *y);
 
@@ -219,6 +218,10 @@ MCLBN_DLL_API void mclBnG2_dbl(mclBnG2 *y, const mclBnG2 *x);
 MCLBN_DLL_API void mclBnG2_add(mclBnG2 *z, const mclBnG2 *x, const mclBnG2 *y);
 MCLBN_DLL_API void mclBnG2_sub(mclBnG2 *z, const mclBnG2 *x, const mclBnG2 *y);
 MCLBN_DLL_API void mclBnG2_mul(mclBnG2 *z, const mclBnG2 *x, const mclBnFr *y);
+/*
+	constant time mul
+*/
+MCLBN_DLL_API void mclBnG2_mulCT(mclBnG2 *z, const mclBnG2 *x, const mclBnFr *y);
 
 ////////////////////////////////////////////////
 // set zero
diff --git a/include/mcl/bn.hpp b/include/mcl/bn.hpp
index 22bedae..4c0fd93 100644
--- a/include/mcl/bn.hpp
+++ b/include/mcl/bn.hpp
@@ -239,7 +239,7 @@ struct GLV1 {
 				uint32_t b1 = (w[1][i] >> j) & 1;
 				uint32_t c = b1 * 2 + b0;
 				if (c == 0) {
-					if (constTime) tbl[0] += tbl[c];
+					if (constTime) tbl[0] += tbl[1];
 				} else {
 					Q += tbl[c];
 				}
@@ -406,7 +406,7 @@ struct GLV2 {
 				uint32_t b3 = (w[3][i] >> j) & 1;
 				uint32_t c = b3 * 8 + b2 * 4 + b1 * 2 + b0;
 				if (c == 0) {
-					if (constTime) tbl[0] += tbl[c];
+					if (constTime) tbl[0] += tbl[1];
 				} else {
 					Q += tbl[c];
 				}
diff --git a/include/mcl/ec.hpp b/include/mcl/ec.hpp
index f2e36ed..4156241 100644
--- a/include/mcl/ec.hpp
+++ b/include/mcl/ec.hpp
@@ -594,7 +594,6 @@ public:
 	{
 		mulArray(z, x, gmp::getUnit(y), abs(y.get_mpz_t()->_mp_size), y < 0);
 	}
-	// @note time is depend on bitlength of y
 	template<class tag, size_t maxBitSize, template<class _tag, size_t _maxBitSize>class FpT>
 	static inline void mulCT(EcT& z, const EcT& x, const FpT<tag, maxBitSize>& y)
 	{
@@ -602,7 +601,6 @@ public:
 		y.getBlock(b);
 		mulArray(z, x, b.p, b.n, false, true);
 	}
-	// @note time is depend on bitlength of y
 	static inline void mulCT(EcT& z, const EcT& x, const mpz_class& y)
 	{
 		mulArray(z, x, gmp::getUnit(y), abs(y.get_mpz_t()->_mp_size), y < 0, true);
@@ -841,7 +839,7 @@ public:
 			px = &tmp;
 		}
 		z.clear();
-		fp::powGeneric(z, *px, y, yn, EcT::add, EcT::dbl, EcT::normalize, constTime);
+		fp::powGeneric(z, *px, y, yn, EcT::add, EcT::dbl, EcT::normalize, constTime ? Fp::BaseFp::getBitSize() : 0);
 		if (isNegative) {
 			neg(z, z);
 		}
diff --git a/include/mcl/fp_tower.hpp b/include/mcl/fp_tower.hpp
index 9d02953..086cfe8 100644
--- a/include/mcl/fp_tower.hpp
+++ b/include/mcl/fp_tower.hpp
@@ -582,6 +582,7 @@ template<class Fp>
 struct Fp6T : public fp::Operator<Fp6T<Fp> > {
 	typedef Fp2T<Fp> Fp2;
 	typedef Fp2DblT<Fp> Fp2Dbl;
+	typedef Fp BaseFp;
 	Fp2 a, b, c;
 	Fp6T() { }
 	Fp6T(int64_t a) : a(a) , b(0) , c(0) { }
@@ -829,6 +830,7 @@ template<class Fp>
 struct Fp12T : public fp::Operator<Fp12T<Fp> > {
 	typedef Fp2T<Fp> Fp2;
 	typedef Fp6T<Fp> Fp6;
+	typedef Fp BaseFp;
 	Fp6 a, b;
 	Fp12T() {}
 	Fp12T(int64_t a) : a(a), b(0) {}
diff --git a/include/mcl/operator.hpp b/include/mcl/operator.hpp
index 55aaad5..0419f55 100644
--- a/include/mcl/operator.hpp
+++ b/include/mcl/operator.hpp
@@ -47,7 +47,6 @@ struct Operator : E {
 		y.getBlock(b);
 		powArray(z, x, b.p, b.n, false, false);
 	}
-	// @note time is depend on bitlength of y
 	template<class tag2, size_t maxBitSize2, template<class _tag, size_t _maxBitSize> class FpT>
 	static void powCT(T& z, const T& x, const FpT<tag2, maxBitSize2>& y)
 	{
@@ -64,7 +63,6 @@ struct Operator : E {
 	{
 		powArray(z, x, gmp::getUnit(y), abs(y.get_mpz_t()->_mp_size), y < 0, false);
 	}
-	// @note time is depend on bitlength of y
 	static void powCT(T& z, const T& x, const mpz_class& y)
 	{
 		powArray(z, x, gmp::getUnit(y), abs(y.get_mpz_t()->_mp_size), y < 0, true);
@@ -79,7 +77,7 @@ private:
 			px = &tmp;
 		}
 		z = 1;
-		fp::powGeneric(z, *px, y, yn, T::mul, T::sqr, (void (*)(T&, const T&))0, constTime);
+		fp::powGeneric(z, *px, y, yn, T::mul, T::sqr, (void (*)(T&, const T&))0, constTime ? T::BaseFp::getBitSize() : 0);
 		if (isNegative) {
 			T::inv(z, z);
 		}
diff --git a/include/mcl/util.hpp b/include/mcl/util.hpp
index 1be9b7d..8b33599 100644
--- a/include/mcl/util.hpp
+++ b/include/mcl/util.hpp
@@ -192,19 +192,27 @@ void getRandVal(T *out, RG& rg, const T *in, size_t bitSize)
 	@param x [in]
 	@param y [in]
 	@param n [in] size of y[]
-	@param constTime [in] use const-time method depending on only bit length of y if true
+	@param limitBit [in] const time version if the value is positive
 	@note &out != x and out = the unit element of G
 */
 template<class G, class T>
-void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&, const G&) , void sqr(G&, const G&), void normalize(G&, const G&), bool constTime = false)
+void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&, const G&) , void sqr(G&, const G&), void normalize(G&, const G&), size_t limitBit = 0)
 {
 	assert(&out != &x);
+	G tbl[4]; // tbl = { discard, x, x^2, x^3 }
+	T v;
+	bool constTime = limitBit > 0;
+	int maxBit = 0;
+	int m = 0;
 	while (n > 0) {
 		if (y[n - 1]) break;
 		n--;
 	}
-	if (n == 0) return;
-	if (n == 1) {
+	if (n == 0) {
+		if (constTime) goto DummyLoop;
+		return;
+	}
+	if (!constTime && n == 1) {
 		switch (y[0]) {
 		case 1:
 			out = x;
@@ -222,7 +230,6 @@ void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&,
 			return;
 		}
 	}
-	G tbl[4]; // tbl = { discard, x, x^2, x^3 }
 	if (normalize != 0) {
 		normalize(tbl[0], x);
 	} else {
@@ -233,8 +240,10 @@ void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&,
 	if (normalize != 0) { normalize(tbl[2], tbl[2]); }
 	mul(tbl[3], tbl[2], x);
 	if (normalize != 0) { normalize(tbl[3], tbl[3]); }
-	T v = y[n - 1];
-	int m = cybozu::bsr<T>(v);
+	v = y[n - 1];
+	assert(v);
+	m = cybozu::bsr<T>(v);
+	maxBit = int(m + (n - 1) * sizeof(T) * 8);
 	if (m & 1) {
 		m--;
 		T idx = (v >> m) & 3;
@@ -243,31 +252,27 @@ void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&,
 	} else {
 		out = x;
 	}
-	if (constTime) {
-		G *pTbl[] = { &tbl[0], &out, &out, &out };
-		for (int i = (int)n - 1; i >= 0; i--) {
-			T v = y[i];
-			for (int j = m - 2; j >= 0; j -= 2) {
-				sqr(out, out);
-				sqr(out, out);
-				T idx = (v >> j) & 3;
-				mul(*pTbl[idx], *pTbl[idx], tbl[idx]);
-			}
-			m = (int)sizeof(T) * 8;
-		}
-	} else {
-		for (int i = (int)n - 1; i >= 0; i--) {
-			T v = y[i];
-			for (int j = m - 2; j >= 0; j -= 2) {
-				sqr(out, out);
-				sqr(out, out);
-				T idx = (v >> j) & 3;
-				if (idx > 0) {
-					mul(out, out, tbl[idx]);
-				}
+	for (int i = (int)n - 1; i >= 0; i--) {
+		T v = y[i];
+		for (int j = m - 2; j >= 0; j -= 2) {
+			sqr(out, out);
+			sqr(out, out);
+			T idx = (v >> j) & 3;
+			if (idx == 0) {
+				if (constTime) mul(tbl[0], tbl[0], tbl[1]);
+			} else {
+				mul(out, out, tbl[idx]);
 			}
-			m = (int)sizeof(T) * 8;
 		}
+		m = (int)sizeof(T) * 8;
+	}
+DummyLoop:
+	if (!constTime) return;
+	G D = out;
+	for (size_t i = maxBit + 1; i < limitBit; i += 2) {
+		sqr(D, D);
+		sqr(D, D);
+		mul(D, D, tbl[1]);
 	}
 }
 
diff --git a/sample/bench.cpp b/sample/bench.cpp
index 565e8d2..67f5da5 100644
--- a/sample/bench.cpp
+++ b/sample/bench.cpp
@@ -84,19 +84,21 @@ void benchEcSub(const mcl::EcParam& para, mcl::fp::Mode mode, mcl::ec::Mode ecMo
 	Ec P(x, y);
 	Ec P2; Ec::add(P2, P, P);
 	Ec Q = P + P + P;
-	double addT, add2T, subT, dblT, mulT, mulRandT, normT;
+	double addT, add2T, subT, dblT, mulT, mulCTT, mulRandT, mulCTRandT, normT;
 	CYBOZU_BENCH_T(addT, P = P2; Ec::add, Q, P, Q);
 	P.normalize();
 	CYBOZU_BENCH_T(add2T, Ec::add, Q, P, Q);
 	CYBOZU_BENCH_T(subT, Ec::sub, Q, P, Q);
 	CYBOZU_BENCH_T(dblT, Ec::dbl, P, P);
-	Zn z("-3");
-	CYBOZU_BENCH_T(mulT, Ec::mul, P, P, z);
+	Zn z("3");
+	CYBOZU_BENCH_T(mulT, Ec::mul, Q, P, z);
+	CYBOZU_BENCH_T(mulCTT, Ec::mulCT, Q, P, z);
 	cybozu::XorShift rg;
 	z.setRand(rg);
-	CYBOZU_BENCH_T(mulRandT, Ec::mul, P, P, z);
+	CYBOZU_BENCH_T(mulRandT, Ec::mul, Q, P, z);
+	CYBOZU_BENCH_T(mulCTRandT, Ec::mulCT, Q, P, z);
 	CYBOZU_BENCH_T(normT, Q = P; Q.normalize);
-	printf("%10s %10s add %8.2f add2 %8.2f sub %8.2f dbl %8.2f mul(-3) %8.2f mul(rand) %8.2f norm %8.2f\n", para.name, mcl::fp::ModeToStr(mode), addT, add2T, subT, dblT, mulT, mulRandT, normT);
+	printf("%10s %10s add %8.2f add2 %8.2f sub %8.2f dbl %8.2f mul(3) %8.2f mulCT(3) %8.2f mul(rand) %8.2f mulCT(rand) %8.2f norm %8.2f\n", para.name, mcl::fp::ModeToStr(mode), addT, add2T, subT, dblT, mulT, mulCTT, mulRandT, mulCTRandT, normT);
 
 }
 void benchEc(size_t bitSize, int mode, mcl::ec::Mode ecMode)
diff --git a/src/bn_c_impl.hpp b/src/bn_c_impl.hpp
index 26eea30..878919c 100644
--- a/src/bn_c_impl.hpp
+++ b/src/bn_c_impl.hpp
@@ -411,6 +411,10 @@ void mclBnG2_mul(mclBnG2 *z, const mclBnG2 *x, const mclBnFr *y)
 {
 	G2::mul(*cast(z),*cast(x), *cast(y));
 }
+void mclBnG2_mulCT(mclBnG2 *z, const mclBnG2 *x, const mclBnFr *y)
+{
+	G2::mulCT(*cast(z),*cast(x), *cast(y));
+}
 
 ////////////////////////////////////////////////
 // set zero