Below is the next patch planned for Rabin-Williams. It improves efficiency
of the signature scheme while maintaining compatibility with P1363 and
preserving existing behavior.
The class members used in precomputation are mutable so Precompute can be
called from const member functions. The precomputation does not modify the
RW proper parameters, like n, p, q and u.
The OMP gear is guarded by an OMP if clause dependent upon
CRYPTOPP_RW_USE_OMP. We were not able to improve performance for the class
by utilizing OMP.
Optional blinding was removed in favor of a "better" planned cut-in.
Blinding applies to many (all?) integer factorization based problems, so it
should be more than a one-off cut-in.
The fix for CVE-2015-2141 was already committed.
Comments are welcomed.
**********
$ cat rw.diff
diff --git a/rw.cpp b/rw.cpp
index 0b9318b..00fc00d 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 = true;
+
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 JPM.
+ // 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
--
--
You received this message because you are subscribed to the "Crypto++ Users"
Google Group.
To unsubscribe, send an email to [email protected].
More information about Crypto++ and this group is available at
http://www.cryptopp.com.
---
You received this message because you are subscribed to the Google Groups
"Crypto++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
