1// rw.cpp - written and placed in the public domain by Wei Dai 2 3#include "pch.h" 4#include "rw.h" 5#include "nbtheory.h" 6#include "asn.h" 7 8#ifndef CRYPTOPP_IMPORTS 9 10NAMESPACE_BEGIN(CryptoPP) 11 12void RWFunction::BERDecode(BufferedTransformation &bt) 13{ 14 BERSequenceDecoder seq(bt); 15 m_n.BERDecode(seq); 16 seq.MessageEnd(); 17} 18 19void RWFunction::DEREncode(BufferedTransformation &bt) const 20{ 21 DERSequenceEncoder seq(bt); 22 m_n.DEREncode(seq); 23 seq.MessageEnd(); 24} 25 26Integer RWFunction::ApplyFunction(const Integer &in) const 27{ 28 DoQuickSanityCheck(); 29 30 Integer out = in.Squared()%m_n; 31 const word r = 12; 32 // this code was written to handle both r = 6 and r = 12, 33 // but now only r = 12 is used in P1363 34 const word r2 = r/2; 35 const word r3a = (16 + 5 - r) % 16; // n%16 could be 5 or 13 36 const word r3b = (16 + 13 - r) % 16; 37 const word r4 = (8 + 5 - r/2) % 8; // n%8 == 5 38 switch (out % 16) 39 { 40 case r: 41 break; 42 case r2: 43 case r2+8: 44 out <<= 1; 45 break; 46 case r3a: 47 case r3b: 48 out.Negate(); 49 out += m_n; 50 break; 51 case r4: 52 case r4+8: 53 out.Negate(); 54 out += m_n; 55 out <<= 1; 56 break; 57 default: 58 out = Integer::Zero(); 59 } 60 return out; 61} 62 63bool RWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 64{ 65 bool pass = true; 66 pass = pass && m_n > Integer::One() && m_n%8 == 5; 67 return pass; 68} 69 70bool RWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 71{ 72 return GetValueHelper(this, name, valueType, pValue).Assignable() 73 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus) 74 ; 75} 76 77void RWFunction::AssignFrom(const NameValuePairs &source) 78{ 79 AssignFromHelper(this, source) 80 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus) 81 ; 82} 83 84// ***************************************************************************** 85// private key operations: 86 87// generate a random private key 88void InvertibleRWFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 89{ 90 int modulusSize = 2048; 91 alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize); 92 93 if (modulusSize < 16) 94 throw InvalidArgument("InvertibleRWFunction: specified modulus length is too small"); 95 96 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize); 97 m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 3)("Mod", 8))); 98 m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 7)("Mod", 8))); 99 100 m_n = m_p * m_q; 101 m_u = m_q.InverseMod(m_p); 102} 103 104void InvertibleRWFunction::BERDecode(BufferedTransformation &bt) 105{ 106 BERSequenceDecoder seq(bt); 107 m_n.BERDecode(seq); 108 m_p.BERDecode(seq); 109 m_q.BERDecode(seq); 110 m_u.BERDecode(seq); 111 seq.MessageEnd(); 112} 113 114void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const 115{ 116 DERSequenceEncoder seq(bt); 117 m_n.DEREncode(seq); 118 m_p.DEREncode(seq); 119 m_q.DEREncode(seq); 120 m_u.DEREncode(seq); 121 seq.MessageEnd(); 122} 123 124Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const 125{ 126 DoQuickSanityCheck(); 127 ModularArithmetic modn(m_n); 128 Integer r, rInv; 129 do { // do this in a loop for people using small numbers for testing 130 r.Randomize(rng, Integer::One(), m_n - Integer::One()); 131 rInv = modn.MultiplicativeInverse(r); 132 } while (rInv.IsZero()); 133 Integer re = modn.Square(r); 134 re = modn.Multiply(re, x); // blind 135 136 Integer cp=re%m_p, cq=re%m_q; 137 if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1) 138 { 139 cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1; 140 cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1; 141 } 142 143 #pragma omp parallel 144 #pragma omp sections 145 { 146 #pragma omp section 147 cp = ModularSquareRoot(cp, m_p); 148 #pragma omp section 149 cq = ModularSquareRoot(cq, m_q); 150 } 151 152 Integer y = CRT(cq, m_q, cp, m_p, m_u); 153 y = modn.Multiply(y, rInv); // unblind 154 y = STDMIN(y, m_n-y); 155 if (ApplyFunction(y) != x) // check 156 throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation"); 157 return y; 158} 159 160bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 161{ 162 bool pass = RWFunction::Validate(rng, level); 163 pass = pass && m_p > Integer::One() && m_p%8 == 3 && m_p < m_n; 164 pass = pass && m_q > Integer::One() && m_q%8 == 7 && m_q < m_n; 165 pass = pass && m_u.IsPositive() && m_u < m_p; 166 if (level >= 1) 167 { 168 pass = pass && m_p * m_q == m_n; 169 pass = pass && m_u * m_q % m_p == 1; 170 } 171 if (level >= 2) 172 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2); 173 return pass; 174} 175 176bool InvertibleRWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 177{ 178 return GetValueHelper<RWFunction>(this, name, valueType, pValue).Assignable() 179 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1) 180 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2) 181 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 182 ; 183} 184 185void InvertibleRWFunction::AssignFrom(const NameValuePairs &source) 186{ 187 AssignFromHelper<RWFunction>(this, source) 188 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1) 189 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) 190 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 191 ; 192} 193 194NAMESPACE_END 195 196#endif 197