1// rabin.cpp - written and placed in the public domain by Wei Dai 2 3#include "pch.h" 4#include "rabin.h" 5#include "nbtheory.h" 6#include "asn.h" 7#include "sha.h" 8#include "modarith.h" 9 10NAMESPACE_BEGIN(CryptoPP) 11 12void RabinFunction::BERDecode(BufferedTransformation &bt) 13{ 14 BERSequenceDecoder seq(bt); 15 m_n.BERDecode(seq); 16 m_r.BERDecode(seq); 17 m_s.BERDecode(seq); 18 seq.MessageEnd(); 19} 20 21void RabinFunction::DEREncode(BufferedTransformation &bt) const 22{ 23 DERSequenceEncoder seq(bt); 24 m_n.DEREncode(seq); 25 m_r.DEREncode(seq); 26 m_s.DEREncode(seq); 27 seq.MessageEnd(); 28} 29 30Integer RabinFunction::ApplyFunction(const Integer &in) const 31{ 32 DoQuickSanityCheck(); 33 34 Integer out = in.Squared()%m_n; 35 if (in.IsOdd()) 36 out = out*m_r%m_n; 37 if (Jacobi(in, m_n)==-1) 38 out = out*m_s%m_n; 39 return out; 40} 41 42bool RabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 43{ 44 bool pass = true; 45 pass = pass && m_n > Integer::One() && m_n%4 == 1; 46 pass = pass && m_r > Integer::One() && m_r < m_n; 47 pass = pass && m_s > Integer::One() && m_s < m_n; 48 if (level >= 1) 49 pass = pass && Jacobi(m_r, m_n) == -1 && Jacobi(m_s, m_n) == -1; 50 return pass; 51} 52 53bool RabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 54{ 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) 59 ; 60} 61 62void RabinFunction::AssignFrom(const NameValuePairs &source) 63{ 64 AssignFromHelper(this, source) 65 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus) 66 CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime1) 67 CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime2) 68 ; 69} 70 71// ***************************************************************************** 72// private key operations: 73 74// generate a random private key 75void InvertibleRabinFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 76{ 77 int modulusSize = 2048; 78 alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize); 79 80 if (modulusSize < 16) 81 throw InvalidArgument("InvertibleRabinFunction: specified modulus size is too small"); 82 83 // VC70 workaround: putting these after primeParam causes overlapped stack allocation 84 bool rFound=false, sFound=false; 85 Integer t=2; 86 87 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize) 88 ("EquivalentTo", 3)("Mod", 4); 89 m_p.GenerateRandom(rng, primeParam); 90 m_q.GenerateRandom(rng, primeParam); 91 92 while (!(rFound && sFound)) 93 { 94 int jp = Jacobi(t, m_p); 95 int jq = Jacobi(t, m_q); 96 97 if (!rFound && jp==1 && jq==-1) 98 { 99 m_r = t; 100 rFound = true; 101 } 102 103 if (!sFound && jp==-1 && jq==1) 104 { 105 m_s = t; 106 sFound = true; 107 } 108 109 ++t; 110 } 111 112 m_n = m_p * m_q; 113 m_u = m_q.InverseMod(m_p); 114} 115 116void InvertibleRabinFunction::BERDecode(BufferedTransformation &bt) 117{ 118 BERSequenceDecoder seq(bt); 119 m_n.BERDecode(seq); 120 m_r.BERDecode(seq); 121 m_s.BERDecode(seq); 122 m_p.BERDecode(seq); 123 m_q.BERDecode(seq); 124 m_u.BERDecode(seq); 125 seq.MessageEnd(); 126} 127 128void InvertibleRabinFunction::DEREncode(BufferedTransformation &bt) const 129{ 130 DERSequenceEncoder seq(bt); 131 m_n.DEREncode(seq); 132 m_r.DEREncode(seq); 133 m_s.DEREncode(seq); 134 m_p.DEREncode(seq); 135 m_q.DEREncode(seq); 136 m_u.DEREncode(seq); 137 seq.MessageEnd(); 138} 139 140Integer InvertibleRabinFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &in) const 141{ 142 DoQuickSanityCheck(); 143 144 ModularArithmetic modn(m_n); 145 Integer r(rng, Integer::One(), m_n - Integer::One()); 146 r = modn.Square(r); 147 Integer r2 = modn.Square(r); 148 Integer c = modn.Multiply(in, r2); // blind 149 150 Integer cp=c%m_p, cq=c%m_q; 151 152 int jp = Jacobi(cp, m_p); 153 int jq = Jacobi(cq, m_q); 154 155 if (jq==-1) 156 { 157 cp = cp*EuclideanMultiplicativeInverse(m_r, m_p)%m_p; 158 cq = cq*EuclideanMultiplicativeInverse(m_r, m_q)%m_q; 159 } 160 161 if (jp==-1) 162 { 163 cp = cp*EuclideanMultiplicativeInverse(m_s, m_p)%m_p; 164 cq = cq*EuclideanMultiplicativeInverse(m_s, m_q)%m_q; 165 } 166 167 cp = ModularSquareRoot(cp, m_p); 168 cq = ModularSquareRoot(cq, m_q); 169 170 if (jp==-1) 171 cp = m_p-cp; 172 173 Integer out = CRT(cq, m_q, cp, m_p, m_u); 174 175 out = modn.Divide(out, r); // unblind 176 177 if ((jq==-1 && out.IsEven()) || (jq==1 && out.IsOdd())) 178 out = m_n-out; 179 180 return out; 181} 182 183bool InvertibleRabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 184{ 185 bool pass = RabinFunction::Validate(rng, level); 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; 189 if (level >= 1) 190 { 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; 197 } 198 if (level >= 2) 199 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2); 200 return pass; 201} 202 203bool InvertibleRabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 204{ 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) 209 ; 210} 211 212void InvertibleRabinFunction::AssignFrom(const NameValuePairs &source) 213{ 214 AssignFromHelper<RabinFunction>(this, source) 215 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1) 216 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) 217 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 218 ; 219} 220 221NAMESPACE_END 222