12#ifndef CRYPTOPP_IMPORTS
15# define CRYPTOPP_RW_USE_OMP 1
17# define CRYPTOPP_RW_USE_OMP 0
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");
120 m_n = n; m_p = p; m_q = q; m_u = u;
125void InvertibleRWFunction::PrecomputeTweakedRoots()
const
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);
181 m_precompute =
false;
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);
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;
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.
An object that implements NameValuePairs.
Combines two sets of NameValuePairs.
void DoQuickSanityCheck() const
Perform a quick sanity check.
Base class for all exceptions thrown by the library.
@ OTHER_ERROR
Some other error occurred not belonging to other categories.
Multiple precision integer with arithmetic operations.
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs ¶ms=g_nullNameValuePairs)
Generate a random number.
bool IsPositive() const
Determines if the Integer is positive.
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 BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
void Negate()
Reverse the Sign of the Integer.
bool IsZero() const
Determines if the Integer is 0.
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
static const Integer & One()
Integer representing 1.
An invalid argument was detected.
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.
Ring of congruence classes modulo n.
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.