12#ifndef CRYPTOPP_IMPORTS
15# define CRYPTOPP_RW_USE_OMP 1
17# define CRYPTOPP_RW_USE_OMP 0
24 BERSequenceDecoder seq(bt);
31 DERSequenceEncoder seq(bt);
45 const word r3a = (16 + 5 - r) % 16;
46 const word r3b = (16 + 13 - r) % 16;
47 const word r4 = (8 + 5 - r/2) % 8;
75 CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(level);
84 return GetValueHelper(
this, name, valueType, pValue).Assignable()
85 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
91 AssignFromHelper(
this, source)
92 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
102 int modulusSize = 2048;
105 if (modulusSize < 16)
106 throw InvalidArgument(
"InvertibleRWFunction: specified modulus length is too small");
108 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize);
109 m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam,
MakeParameters(
"EquivalentTo", 3)(
"Mod", 8)));
110 m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam,
MakeParameters(
"EquivalentTo", 7)(
"Mod", 8)));
113 m_u = m_q.InverseMod(m_p);
120 m_n = n; m_p = p; m_q = q; m_u = u;
125void InvertibleRWFunction::PrecomputeTweakedRoots()
const
127 ModularArithmetic modp(m_p), modq(m_q);
131 #pragma omp parallel sections if(CRYPTOPP_RW_USE_OMP)
134 m_pre_2_9p = modp.Exponentiate(2, (9 * m_p - 11)/8);
136 m_pre_2_3q = modq.Exponentiate(2, (3 * m_q - 5)/8);
138 m_pre_q_p = modp.Exponentiate(m_q, m_p - 2);
141 m_pre_2_9p = modp.Exponentiate(2, (9 * m_p - 11)/8);
142 m_pre_2_3q = modq.Exponentiate(2, (3 * m_q - 5)/8);
143 m_pre_q_p = modp.Exponentiate(m_q, m_p - 2);
151 BERSequenceDecoder seq(bt);
152 m_pre_2_9p.BERDecode(seq);
153 m_pre_2_3q.BERDecode(seq);
154 m_pre_q_p.BERDecode(seq);
165 DERSequenceEncoder seq(bt);
166 m_pre_2_9p.DEREncode(seq);
167 m_pre_2_3q.DEREncode(seq);
168 m_pre_q_p.DEREncode(seq);
174 BERSequenceDecoder seq(bt);
181 m_precompute =
false;
186 DERSequenceEncoder seq(bt);
202 ModularArithmetic modn(m_n), modp(m_p), modq(m_q);
215 Integer re = modn.Square(r);
216 re = modn.Multiply(re, x);
218 const Integer &h = re, &p = m_p, &q = m_q;
221 const Integer U = modq.Exponentiate(h, (q+1)/8);
222 if(((modq.Exponentiate(U, 4) - h) % q).IsZero())
227 const Integer eh = e*h, V = modp.Exponentiate(eh, (p-3)/8);
228 if(((modp.Multiply(modp.Exponentiate(V, 4), modp.Exponentiate(eh, 2)) - eh) % p).IsZero())
235 #pragma omp parallel sections if(CRYPTOPP_RW_USE_OMP)
239 W = (f.IsUnit() ? U : modq.Multiply(m_pre_2_3q, U));
243 const Integer t = modp.Multiply(modp.Exponentiate(V, 3), eh);
244 X = (f.IsUnit() ? t : modp.Multiply(m_pre_2_9p, t));
248 const Integer W = (f.IsUnit() ? U : modq.Multiply(m_pre_2_3q, U));
249 const Integer t = modp.Multiply(modp.Exponentiate(V, 3), eh);
250 const Integer X = (f.IsUnit() ? t : modp.Multiply(m_pre_2_9p, t));
253 const Integer Y = W + q * modp.Multiply(m_pre_q_p, (X - W));
256 Integer s = modn.Multiply(modn.Square(Y), rInv);
262 throw Exception(
Exception::OTHER_ERROR,
"InvertibleRWFunction: computational error during private key operation");
271 pass = pass && m_p >
Integer::One() && m_p%8 == 3 && m_p < m_n;
273 pass = pass && m_q >
Integer::One() && m_q%8 == 7 && m_q < m_n;
275 pass = pass && m_u.IsPositive() && m_u < m_p;
279 pass = pass && m_p * m_q == m_n;
281 pass = pass && m_u * m_q % m_p == 1;
294 return GetValueHelper<RWFunction>(
this, name, valueType, pValue).Assignable()
295 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
296 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
297 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
303 AssignFromHelper<RWFunction>(
this, source)
304 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
305 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
306 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
309 m_precompute =
false;
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Classes and functions for working with ANS.1 objects.
void DoQuickSanityCheck() const
Perform a quick sanity check.
@ OTHER_ERROR
Some other error occurred not belonging to other categories.
Multiple precision integer with arithmetic operations.
static const Integer & Zero()
Integer representing 0.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Integer Squared() const
Multiply this integer by itself.
void Negate()
Reverse the Sign of the Integer.
bool IsZero() const
Determines if the Integer is 0.
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
static const Integer & One()
Integer representing 1.
virtual void LoadPrecomputation(BufferedTransformation &storedPrecomputation)
Retrieve previously saved precomputation.
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
void Initialize(const Integer &n, const Integer &p, const Integer &q, const Integer &u)
Initialize a Rabin-Williams private key.
virtual void SavePrecomputation(BufferedTransformation &storedPrecomputation) const
Save precomputation for later use.
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
virtual void Precompute(unsigned int unused=0)
Perform precomputation.
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Interface for retrieving values given their names.
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Interface for random number generators.
word64 word
Full word used for multiprecision integer arithmetic.
Multiple precision integer with arithmetic operations.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Class file for performing modular arithmetic.
Crypto++ library namespace.
Classes and functions for number theoretic operations.
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Classes for Rabin-Williams signature scheme.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.