From 837bc18cba61043c59a6f46654fba82642592601 Mon Sep 17 00:00:00 2001 From: weidai Date: Sun, 15 Apr 2007 22:58:24 +0000 Subject: added blinding and error checking for RW private key operation --- rw.cpp | 42 ++++++++++++++++++++++++++++-------------- 1 file changed, 28 insertions(+), 14 deletions(-) (limited to 'rw.cpp') diff --git a/rw.cpp b/rw.cpp index 2e565496..c1306b39 100644 --- a/rw.cpp +++ b/rw.cpp @@ -121,26 +121,40 @@ void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const seq.MessageEnd(); } -Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &in) const +Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const { - // no need to do blinding because RW is only used for signatures - DoQuickSanityCheck(); - - Integer cp=in%m_p, cq=in%m_q; - + ModularArithmetic modn(m_n); + Integer r, rInv; + do { // do this in a loop for people using small numbers for testing + r.Randomize(rng, Integer::One(), m_n - Integer::One()); + rInv = modn.MultiplicativeInverse(r); + } while (rInv.IsZero()); + Integer re = modn.Square(r); + 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%2 ? (cp+m_p) >> 1 : cp >> 1; - cq = cq%2 ? (cq+m_q) >> 1 : cq >> 1; + cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1; + cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1; } - cp = ModularSquareRoot(cp, m_p); - cq = ModularSquareRoot(cq, m_q); - - Integer out = CRT(cq, m_q, cp, m_p, m_u); - - return STDMIN(out, m_n-out); + #pragma omp parallel + #pragma omp sections + { + #pragma omp section + cp = ModularSquareRoot(cp, m_p); + #pragma omp section + cq = ModularSquareRoot(cq, m_q); + } + + 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 + throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation"); + return y; } bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const -- cgit v1.2.1