Hey Jeff,
1. Shouldn't CRYPTOPP_RW_USE_OMP live in config.h and be a #define
rather than a "static const bool"?
2. Why do you default-/enable/ OMP, if it gives us worse performance
than non-OMP (or did you fix it without telling us?)?
3. May you please change my name to Muench rather than Munch?
That's all I see for now, hopefully we've fixed everything in our RW
code with this patch.
BR
JPM
Am 29.06.2015 um 17:33 schrieb Jeffrey Walton:
> 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]
> <mailto:[email protected]>.
> For more options, visit https://groups.google.com/d/optout.
--
--
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.
smime.p7s
Description: S/MIME Cryptographic Signature
