Implmented Bernstein\'s Tweaked Roots for Rabin-Williams signatures. Thanks to Evgeny Sidorov for suggesting it

git-svn-id: svn://svn.code.sf.net/p/cryptopp/code/trunk/c5@565 57ff6487-cd31-0410-9ec3-f628ee90f5f0

2 files changed, 122 insertions, 25 deletions

diff --git a/rw.cpp b/rw.cpp
index 36985c0..e8916e9 100644
--- a/rw.cpp
+++ b/rw.cpp
@@ -5,8 +5,14 @@
 #include "nbtheory.h"
 #include "asn.h"
 
+#ifndef NDEBUG
+# include <cassert>
+#endif
+
 #ifndef CRYPTOPP_IMPORTS
 
+static const bool CRYPTOPP_RW_USE_OMP = false;
+
 NAMESPACE_BEGIN(CryptoPP)
 
 void RWFunction::BERDecode(BufferedTransformation &bt)
@@ -99,6 +105,55 @@ void InvertibleRWFunction::GenerateRandom(RandomNumberGenerator &rng, const Name
 
 	m_n = m_p * m_q;
 	m_u = m_q.InverseMod(m_p);
+
+	Precompute();
+}
+
+void InvertibleRWFunction::Initialize(const Integer &n, const Integer &p, const Integer &q, const Integer &u)
+{
+	m_n = n; m_p = p; m_q = q; m_u = u;
+
+	Precompute();
+}
+
+void InvertibleRWFunction::PrecomputeTweakedRoots() const
+{
+	ModularArithmetic modp(m_p), modq(m_q);
+
+	#pragma omp parallel sections if(CRYPTOPP_RW_USE_OMP)
+	{
+		#pragma omp section
+			m_pre_2_9p = modp.Exponentiate(2, (9 * m_p - 11)/8);
+		#pragma omp section
+			m_pre_2_3q = modq.Exponentiate(2, (3 * m_q - 5)/8);
+		#pragma omp section
+			m_pre_q_p = modp.Exponentiate(m_q, m_p - 2);
+	}
+
+	m_precompute = true;
+}
+
+void InvertibleRWFunction::LoadPrecomputation(BufferedTransformation &bt)
+{
+	BERSequenceDecoder seq(bt);
+	m_pre_2_9p.BERDecode(seq);
+	m_pre_2_3q.BERDecode(seq);
+	m_pre_q_p.BERDecode(seq);
+	seq.MessageEnd();
+
+	m_precompute = true;
+}
+
+void InvertibleRWFunction::SavePrecomputation(BufferedTransformation &bt) const
+{
+	if(!m_precompute)
+		Precompute();
+
+	DERSequenceEncoder seq(bt);
+	m_pre_2_9p.DEREncode(seq);
+	m_pre_2_3q.DEREncode(seq);
+	m_pre_q_p.DEREncode(seq);
+	seq.MessageEnd();
 }
 
 void InvertibleRWFunction::BERDecode(BufferedTransformation &bt)
@@ -109,6 +164,8 @@ void InvertibleRWFunction::BERDecode(BufferedTransformation &bt)
 	m_q.BERDecode(seq);
 	m_u.BERDecode(seq);
 	seq.MessageEnd();
+
+	m_precompute = false;
 }
 
 void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const
@@ -121,46 +178,70 @@ void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const
 	seq.MessageEnd();
 }
 
+// DJB's "RSA signatures and Rabin-Williams signatures..." (http://cr.yp.to/sigs/rwsota-20080131.pdf).
 Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
 {
 	DoQuickSanityCheck();
-	ModularArithmetic modn(m_n);
+
+	if(!m_precompute)
+		Precompute();
+
+	ModularArithmetic modn(m_n), modp(m_p), modq(m_q);
 	Integer r, rInv;
 
-	// do this in a loop for people using small numbers for testing
-	do {
+	do
+	{
+		// Do this in a loop for people using small numbers for testing
 		r.Randomize(rng, Integer::One(), m_n - Integer::One());
 		// Fix for CVE-2015-2141. Thanks to Evgeny Sidorov for reporting.
-		// Squaring to satisfy Jacobi requirements suggested by Jean-Pierre Muench.
+		// Squaring to satisfy Jacobi requirements suggested by Jean-Pierre Munch.
 		r = modn.Square(r);
 		rInv = modn.MultiplicativeInverse(r);
-	} while (rInv.IsZero());
+	} while(rInv.IsZero());
 
 	Integer re = modn.Square(r);
-	re = modn.Multiply(re, x);			// blind
+	re = modn.Multiply(re, x);    // blind
 
-	Integer cp=re%m_p, cq=re%m_q;
-	if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1)
-	{
-		cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1;
-		cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1;
-	}
+	const Integer &h = re, &p = m_p, &q = m_q, &n = m_n;
+	Integer e, f;
+
+	const Integer U = modq.Exponentiate(h, (q+1)/8);
+	if(((modq.Exponentiate(U, 4) - h) % q).IsZero())
+		e = Integer::One();
+	else
+		e = -1;
+
+	const Integer eh = e*h, V = modp.Exponentiate(eh, (p-3)/8);
+	if(((modp.Multiply(modp.Exponentiate(V, 4), modp.Exponentiate(eh, 2)) - eh) % p).IsZero())
+		f = Integer::One();
+	else
+		f = 2;
 
-	#pragma omp parallel
-		#pragma omp sections
+	Integer W, X;
+	#pragma omp parallel sections if(CRYPTOPP_RW_USE_OMP)
+	{
+		#pragma omp section
+		{
+			W = (f.IsUnit() ? U : modq.Multiply(m_pre_2_3q, U));
+		}
+		#pragma omp section
 		{
-			#pragma omp section
-				cp = ModularSquareRoot(cp, m_p);
-			#pragma omp section
-				cq = ModularSquareRoot(cq, m_q);
+			const Integer t = modp.Multiply(modp.Exponentiate(V, 3), eh);
+			X = (f.IsUnit() ? t : modp.Multiply(m_pre_2_9p, t));
 		}
+	}
+	const Integer Y = W + q * modp.Multiply(m_pre_q_p, (X - W));
+
+	// Signature
+	Integer s = modn.Multiply(modn.Square(Y), rInv);
+	assert((e * f * s.Squared()) % m_n == x);
 
-	Integer y = CRT(cq, m_q, cp, m_p, m_u);
-	y = modn.Multiply(y, rInv);				// unblind
-	y = STDMIN(y, m_n-y);
-	if (ApplyFunction(y) != x)				// check
+	// IEEE P1363, Section 8.2.8 IFSP-RW, p.44
+	s = STDMIN(s, m_n - s);
+	if (ApplyFunction(s) != x)                      // check
 		throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation");
-	return y;
+
+	return s;
 }
 
 bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
@@ -195,6 +276,8 @@ void InvertibleRWFunction::AssignFrom(const NameValuePairs &source)
 		CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
 		CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
 		;
+
+	m_precompute = false;
 }
 
 NAMESPACE_END
diff --git a/rw.h b/rw.h
index 6820251..45b3946 100644
--- a/rw.h
+++ b/rw.h
@@ -48,8 +48,9 @@ class CRYPTOPP_DLL InvertibleRWFunction : public RWFunction, public TrapdoorFunc
 	typedef InvertibleRWFunction ThisClass;
 
 public:
-	void Initialize(const Integer &n, const Integer &p, const Integer &q, const Integer &u)
-		{m_n = n; m_p = p; m_q = q; m_u = u;}
+	InvertibleRWFunction() : m_precompute(false) {}
+
+	void Initialize(const Integer &n, const Integer &p, const Integer &q, const Integer &u);
 	// generate a random private key
 	void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits)
 		{GenerateRandomWithKeySize(rng, modulusBits);}
@@ -79,8 +80,21 @@ public:
 	void SetPrime2(const Integer &q) {m_q = q;}
 	void SetMultiplicativeInverseOfPrime2ModPrime1(const Integer &u) {m_u = u;}
 
+	virtual bool SupportsPrecomputation() const {return true;}
+	virtual void Precompute(unsigned int unused = 0) {PrecomputeTweakedRoots();}
+	virtual void Precompute(unsigned int unused = 0) const {PrecomputeTweakedRoots();}
+
+	virtual void LoadPrecomputation(BufferedTransformation &storedPrecomputation);
+	virtual void SavePrecomputation(BufferedTransformation &storedPrecomputation) const;
+
+protected:
+	void PrecomputeTweakedRoots() const;
+
 protected:
 	Integer m_p, m_q, m_u;
+
+	mutable Integer m_pre_2_9p, m_pre_2_3q, m_pre_q_p;
+	mutable bool m_precompute;
 };
 
 //! RW