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;
125 void 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)
303 AssignFromHelper<RWFunction>(
this, source)
304 CRYPTOPP_SET_FUNCTION_ENTRY(
Prime1)
305 CRYPTOPP_SET_FUNCTION_ENTRY(
Prime2)
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.
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.
static const Integer & One()
Integer representing 1.
void Negate()
Reverse the Sign of the Integer.
static const Integer & Zero()
Integer representing 0.
bool IsZero() const
Determines if the Integer is 0.
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
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.
const char * Prime1()
Integer.
const char * Modulus()
Integer.
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
const char * Prime2()
Integer.
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.