diff options
author | noloader <noloader@57ff6487-cd31-0410-9ec3-f628ee90f5f0> | 2015-07-02 21:35:21 +0000 |
---|---|---|
committer | noloader <noloader@57ff6487-cd31-0410-9ec3-f628ee90f5f0> | 2015-07-02 21:35:21 +0000 |
commit | e29b709a97502ac919356f528d74ccdcdf66b651 (patch) | |
tree | 097263dd6e90e3c74326808bb5e2a8f4a98bd830 /rw.cpp | |
parent | 0fd98cb23b696c2bafc9255bd73ebbe5ce576f41 (diff) | |
download | cryptopp-e29b709a97502ac919356f528d74ccdcdf66b651.tar.gz |
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
Diffstat (limited to 'rw.cpp')
-rw-r--r-- | rw.cpp | 129 |
1 files changed, 106 insertions, 23 deletions
@@ -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 |