10 NAMESPACE_BEGIN(CryptoPP)
37 if (Jacobi(in, m_n)==-1)
49 pass = pass && Jacobi(m_r, m_n) == -1 && Jacobi(m_s, m_n) == -1;
55 return GetValueHelper(
this, name, valueType, pValue).Assignable()
56 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
57 CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime1)
58 CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime2)
64 AssignFromHelper(
this, source)
65 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
66 CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime1)
67 CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime2)
77 int modulusSize = 2048;
81 throw InvalidArgument(
"InvertibleRabinFunction: specified modulus size is too small");
84 bool rFound=
false, sFound=
false;
88 (
"EquivalentTo", 3)(
"Mod", 4);
89 m_p.GenerateRandom(rng, primeParam);
90 m_q.GenerateRandom(rng, primeParam);
92 while (!(rFound && sFound))
94 int jp = Jacobi(t, m_p);
95 int jq = Jacobi(t, m_q);
97 if (!rFound && jp==1 && jq==-1)
103 if (!sFound && jp==-1 && jq==1)
142 DoQuickSanityCheck();
148 Integer c = modn.Multiply(in, r2);
152 int jp = Jacobi(cp, m_p);
153 int jq = Jacobi(cq, m_q);
157 cp = cp*EuclideanMultiplicativeInverse(m_r, m_p)%m_p;
158 cq = cq*EuclideanMultiplicativeInverse(m_r, m_q)%m_q;
163 cp = cp*EuclideanMultiplicativeInverse(m_s, m_p)%m_p;
164 cq = cq*EuclideanMultiplicativeInverse(m_s, m_q)%m_q;
167 cp = ModularSquareRoot(cp, m_p);
168 cq = ModularSquareRoot(cq, m_q);
173 Integer out = CRT(cq, m_q, cp, m_p, m_u);
175 out = modn.
Divide(out, r);
177 if ((jq==-1 && out.IsEven()) || (jq==1 && out.IsOdd()))
186 pass = pass && m_p >
Integer::One() && m_p%4 == 3 && m_p < m_n;
187 pass = pass && m_q >
Integer::One() && m_q%4 == 3 && m_q < m_n;
188 pass = pass && m_u.IsPositive() && m_u < m_p;
191 pass = pass && m_p * m_q == m_n;
192 pass = pass && m_u * m_q % m_p == 1;
193 pass = pass && Jacobi(m_r, m_p) == 1;
194 pass = pass && Jacobi(m_r, m_q) == -1;
195 pass = pass && Jacobi(m_s, m_p) == -1;
196 pass = pass && Jacobi(m_s, m_q) == 1;
199 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
205 return GetValueHelper<RabinFunction>(
this, name, valueType, pValue).Assignable()
206 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
207 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
208 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
214 AssignFromHelper<RabinFunction>(
this, source)
215 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
216 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
217 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)