add almost constant-time pow

3 files changed, 56 insertions, 3 deletions

diff --git a/include/mcl/ec.hpp b/include/mcl/ec.hpp
index 72779a2..f4268dc 100644
--- a/include/mcl/ec.hpp
+++ b/include/mcl/ec.hpp
@@ -588,6 +588,17 @@ public:
 	{
 		mulArray(z, x, gmp::getUnit(y), abs(y.get_mpz_t()->_mp_size), y < 0);
 	}
+	template<class tag, size_t maxBitSize, template<class _tag, size_t _maxBitSize>class FpT>
+	static inline void mul_s(EcT& z, const EcT& x, const FpT<tag, maxBitSize>& y)
+	{
+		fp::Block b;
+		y.getBlock(b);
+		mulArray(z, x, b.p, b.n, false, true);
+	}
+	static inline void mul_s(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);
+	}
 	/*
 		0 <= P for any P
 		(Px, Py) <= (P'x, P'y) iff Px < P'x or Px == P'x and Py <= P'y
@@ -755,7 +766,7 @@ public:
 	bool operator>(const EcT& rhs) const { return rhs < *this; }
 	bool operator<=(const EcT& rhs) const { return !operator>(rhs); }
 private:
-	static inline void mulArray(EcT& z, const EcT& x, const fp::Unit *y, size_t yn, bool isNegative)
+	static inline void mulArray(EcT& z, const EcT& x, const fp::Unit *y, size_t yn, bool isNegative, bool constTime = false)
 	{
 		x.normalize();
 		EcT tmp;
@@ -765,7 +776,7 @@ private:
 			px = &tmp;
 		}
 		z.clear();
-		fp::powGeneric(z, *px, y, yn, EcT::add, EcT::dbl);
+		fp::powGeneric(z, *px, y, yn, EcT::add, EcT::dbl, constTime);
 		if (isNegative) {
 			neg(z, z);
 		}
diff --git a/include/mcl/util.hpp b/include/mcl/util.hpp
index 33f114b..4cdf229 100644
--- a/include/mcl/util.hpp
+++ b/include/mcl/util.hpp
@@ -195,7 +195,7 @@ void getRandVal(T *out, RG& rg, const T *in, size_t bitSize)
 	@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 powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&, const G&) , void sqr(G&, const G&), bool constTime = false)
 {
 #if 0
 	assert(&out != &x);
@@ -262,6 +262,10 @@ void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&,
 	} else {
 		out = x;
 	}
+	G dummy;
+	if (constTime) {
+		dummy = x;
+	}
 	for (int i = (int)n - 1; i >= 0; i--) {
 		T v = y[i];
 		for (int j = m - 2; j >= 0; j -= 2) {
@@ -270,6 +274,8 @@ void powGeneric(G& out, const G& x, const T *y, size_t n, void mul(G&, const G&,
 			T idx = (v >> j) & 3;
 			if (idx > 0) {
 				mul(out, out, tbl[idx - 1]);
+			} else if (constTime) {
+				mul(dummy, dummy, tbl[0]);
 			}
 		}
 		m = (int)sizeof(T) * 8;
diff --git a/test/ec_test.cpp b/test/ec_test.cpp
index bcecd60..1cfa377 100644
--- a/test/ec_test.cpp
+++ b/test/ec_test.cpp
@@ -2,12 +2,14 @@
 #define CYBOZU_TEST_DISABLE_AUTO_RUN
 #include <cybozu/test.hpp>
 #include <cybozu/benchmark.hpp>
+#include <cybozu/xorshift.hpp>
 #include <mcl/gmp_util.hpp>
 
 #include <mcl/fp.hpp>
 #include <mcl/ec.hpp>
 #include <mcl/ecparam.hpp>
 #include <time.h>
+#include <math.h>
 
 typedef mcl::FpT<> Fp;
 struct tagZn;
@@ -306,6 +308,39 @@ struct Test {
 		}
 		Fp::setIoMode(mcl::IoAuto);
 	}
+	void bench_mul_s(void f(Ec&, const Ec&, const Zn&)) const
+	{
+		Fp x(para.gx);
+		Fp y(para.gy);
+		Ec P(x, y);
+		cybozu::XorShift rg;
+		std::vector<double> tv(100);
+		for (size_t i = 0; i < tv.size(); i++) {
+			Zn r;
+			r.setRand(rg);
+			CYBOZU_BENCH_C("", 30, f, P, P, r);
+			tv[i] = cybozu::bench::g_clk.getClock();
+printf("%.1f\n", tv[i]);
+		}
+		double ave = 0;
+		for (size_t i = 0; i < tv.size(); i++) {
+			ave += tv[i];
+		}
+		ave /= tv.size();
+		double v = 0;
+		for (size_t i = 0; i < tv.size(); i++) {
+			double t = tv[i] - ave;
+			v += t * t;
+		}
+		v /= tv.size();
+		v = sqrt(v);
+		printf("ave %.2f v %.2f\n", ave, v);
+	}
+	void mul_s() const
+	{
+		bench_mul_s(Ec::mul);
+		bench_mul_s(Ec::mul_s);
+	}
 
 	template<class F>
 	void test(F f, const char *msg) const
@@ -344,6 +379,7 @@ mul 499.00usec
 		squareRoot();
 		str();
 		ioMode();
+//		mul_s();
 	}
 private:
 	Test(const Test&);