Crypto++
|
00001 // ecp.cpp - written and placed in the public domain by Wei Dai 00002 00003 #include "pch.h" 00004 00005 #ifndef CRYPTOPP_IMPORTS 00006 00007 #include "ecp.h" 00008 #include "asn.h" 00009 #include "nbtheory.h" 00010 00011 #include "algebra.cpp" 00012 00013 NAMESPACE_BEGIN(CryptoPP) 00014 00015 ANONYMOUS_NAMESPACE_BEGIN 00016 static inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P) 00017 { 00018 return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y)); 00019 } 00020 00021 static inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P) 00022 { 00023 return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y)); 00024 } 00025 NAMESPACE_END 00026 00027 ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation) 00028 { 00029 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation()) 00030 { 00031 m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus())); 00032 m_a = GetField().ConvertIn(ecp.m_a); 00033 m_b = GetField().ConvertIn(ecp.m_b); 00034 } 00035 else 00036 operator=(ecp); 00037 } 00038 00039 ECP::ECP(BufferedTransformation &bt) 00040 : m_fieldPtr(new Field(bt)) 00041 { 00042 BERSequenceDecoder seq(bt); 00043 GetField().BERDecodeElement(seq, m_a); 00044 GetField().BERDecodeElement(seq, m_b); 00045 // skip optional seed 00046 if (!seq.EndReached()) 00047 { 00048 SecByteBlock seed; 00049 unsigned int unused; 00050 BERDecodeBitString(seq, seed, unused); 00051 } 00052 seq.MessageEnd(); 00053 } 00054 00055 void ECP::DEREncode(BufferedTransformation &bt) const 00056 { 00057 GetField().DEREncode(bt); 00058 DERSequenceEncoder seq(bt); 00059 GetField().DEREncodeElement(seq, m_a); 00060 GetField().DEREncodeElement(seq, m_b); 00061 seq.MessageEnd(); 00062 } 00063 00064 bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, size_t encodedPointLen) const 00065 { 00066 StringStore store(encodedPoint, encodedPointLen); 00067 return DecodePoint(P, store, encodedPointLen); 00068 } 00069 00070 bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const 00071 { 00072 byte type; 00073 if (encodedPointLen < 1 || !bt.Get(type)) 00074 return false; 00075 00076 switch (type) 00077 { 00078 case 0: 00079 P.identity = true; 00080 return true; 00081 case 2: 00082 case 3: 00083 { 00084 if (encodedPointLen != EncodedPointSize(true)) 00085 return false; 00086 00087 Integer p = FieldSize(); 00088 00089 P.identity = false; 00090 P.x.Decode(bt, GetField().MaxElementByteLength()); 00091 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p; 00092 00093 if (Jacobi(P.y, p) !=1) 00094 return false; 00095 00096 P.y = ModularSquareRoot(P.y, p); 00097 00098 if ((type & 1) != P.y.GetBit(0)) 00099 P.y = p-P.y; 00100 00101 return true; 00102 } 00103 case 4: 00104 { 00105 if (encodedPointLen != EncodedPointSize(false)) 00106 return false; 00107 00108 unsigned int len = GetField().MaxElementByteLength(); 00109 P.identity = false; 00110 P.x.Decode(bt, len); 00111 P.y.Decode(bt, len); 00112 return true; 00113 } 00114 default: 00115 return false; 00116 } 00117 } 00118 00119 void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const 00120 { 00121 if (P.identity) 00122 NullStore().TransferTo(bt, EncodedPointSize(compressed)); 00123 else if (compressed) 00124 { 00125 bt.Put(2 + P.y.GetBit(0)); 00126 P.x.Encode(bt, GetField().MaxElementByteLength()); 00127 } 00128 else 00129 { 00130 unsigned int len = GetField().MaxElementByteLength(); 00131 bt.Put(4); // uncompressed 00132 P.x.Encode(bt, len); 00133 P.y.Encode(bt, len); 00134 } 00135 } 00136 00137 void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const 00138 { 00139 ArraySink sink(encodedPoint, EncodedPointSize(compressed)); 00140 EncodePoint(sink, P, compressed); 00141 assert(sink.TotalPutLength() == EncodedPointSize(compressed)); 00142 } 00143 00144 ECP::Point ECP::BERDecodePoint(BufferedTransformation &bt) const 00145 { 00146 SecByteBlock str; 00147 BERDecodeOctetString(bt, str); 00148 Point P; 00149 if (!DecodePoint(P, str, str.size())) 00150 BERDecodeError(); 00151 return P; 00152 } 00153 00154 void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const 00155 { 00156 SecByteBlock str(EncodedPointSize(compressed)); 00157 EncodePoint(str, P, compressed); 00158 DEREncodeOctetString(bt, str); 00159 } 00160 00161 bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const 00162 { 00163 Integer p = FieldSize(); 00164 00165 bool pass = p.IsOdd(); 00166 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p; 00167 00168 if (level >= 1) 00169 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive(); 00170 00171 if (level >= 2) 00172 pass = pass && VerifyPrime(rng, p); 00173 00174 return pass; 00175 } 00176 00177 bool ECP::VerifyPoint(const Point &P) const 00178 { 00179 const FieldElement &x = P.x, &y = P.y; 00180 Integer p = FieldSize(); 00181 return P.identity || 00182 (!x.IsNegative() && x<p && !y.IsNegative() && y<p 00183 && !(((x*x+m_a)*x+m_b-y*y)%p)); 00184 } 00185 00186 bool ECP::Equal(const Point &P, const Point &Q) const 00187 { 00188 if (P.identity && Q.identity) 00189 return true; 00190 00191 if (P.identity && !Q.identity) 00192 return false; 00193 00194 if (!P.identity && Q.identity) 00195 return false; 00196 00197 return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y)); 00198 } 00199 00200 const ECP::Point& ECP::Identity() const 00201 { 00202 return Singleton<Point>().Ref(); 00203 } 00204 00205 const ECP::Point& ECP::Inverse(const Point &P) const 00206 { 00207 if (P.identity) 00208 return P; 00209 else 00210 { 00211 m_R.identity = false; 00212 m_R.x = P.x; 00213 m_R.y = GetField().Inverse(P.y); 00214 return m_R; 00215 } 00216 } 00217 00218 const ECP::Point& ECP::Add(const Point &P, const Point &Q) const 00219 { 00220 if (P.identity) return Q; 00221 if (Q.identity) return P; 00222 if (GetField().Equal(P.x, Q.x)) 00223 return GetField().Equal(P.y, Q.y) ? Double(P) : Identity(); 00224 00225 FieldElement t = GetField().Subtract(Q.y, P.y); 00226 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x)); 00227 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), Q.x); 00228 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y); 00229 00230 m_R.x.swap(x); 00231 m_R.identity = false; 00232 return m_R; 00233 } 00234 00235 const ECP::Point& ECP::Double(const Point &P) const 00236 { 00237 if (P.identity || P.y==GetField().Identity()) return Identity(); 00238 00239 FieldElement t = GetField().Square(P.x); 00240 t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a); 00241 t = GetField().Divide(t, GetField().Double(P.y)); 00242 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), P.x); 00243 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y); 00244 00245 m_R.x.swap(x); 00246 m_R.identity = false; 00247 return m_R; 00248 } 00249 00250 template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end) 00251 { 00252 size_t n = end-begin; 00253 if (n == 1) 00254 *begin = ring.MultiplicativeInverse(*begin); 00255 else if (n > 1) 00256 { 00257 std::vector<T> vec((n+1)/2); 00258 unsigned int i; 00259 Iterator it; 00260 00261 for (i=0, it=begin; i<n/2; i++, it+=2) 00262 vec[i] = ring.Multiply(*it, *(it+1)); 00263 if (n%2 == 1) 00264 vec[n/2] = *it; 00265 00266 ParallelInvert(ring, vec.begin(), vec.end()); 00267 00268 for (i=0, it=begin; i<n/2; i++, it+=2) 00269 { 00270 if (!vec[i]) 00271 { 00272 *it = ring.MultiplicativeInverse(*it); 00273 *(it+1) = ring.MultiplicativeInverse(*(it+1)); 00274 } 00275 else 00276 { 00277 std::swap(*it, *(it+1)); 00278 *it = ring.Multiply(*it, vec[i]); 00279 *(it+1) = ring.Multiply(*(it+1), vec[i]); 00280 } 00281 } 00282 if (n%2 == 1) 00283 *it = vec[n/2]; 00284 } 00285 } 00286 00287 struct ProjectivePoint 00288 { 00289 ProjectivePoint() {} 00290 ProjectivePoint(const Integer &x, const Integer &y, const Integer &z) 00291 : x(x), y(y), z(z) {} 00292 00293 Integer x,y,z; 00294 }; 00295 00296 class ProjectiveDoubling 00297 { 00298 public: 00299 ProjectiveDoubling(const ModularArithmetic &mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q) 00300 : mr(mr), firstDoubling(true), negated(false) 00301 { 00302 if (Q.identity) 00303 { 00304 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity(); 00305 aZ4 = P.z = mr.Identity(); 00306 } 00307 else 00308 { 00309 P.x = Q.x; 00310 P.y = Q.y; 00311 sixteenY4 = P.z = mr.MultiplicativeIdentity(); 00312 aZ4 = m_a; 00313 } 00314 } 00315 00316 void Double() 00317 { 00318 twoY = mr.Double(P.y); 00319 P.z = mr.Multiply(P.z, twoY); 00320 fourY2 = mr.Square(twoY); 00321 S = mr.Multiply(fourY2, P.x); 00322 aZ4 = mr.Multiply(aZ4, sixteenY4); 00323 M = mr.Square(P.x); 00324 M = mr.Add(mr.Add(mr.Double(M), M), aZ4); 00325 P.x = mr.Square(M); 00326 mr.Reduce(P.x, S); 00327 mr.Reduce(P.x, S); 00328 mr.Reduce(S, P.x); 00329 P.y = mr.Multiply(M, S); 00330 sixteenY4 = mr.Square(fourY2); 00331 mr.Reduce(P.y, mr.Half(sixteenY4)); 00332 } 00333 00334 const ModularArithmetic &mr; 00335 ProjectivePoint P; 00336 bool firstDoubling, negated; 00337 Integer sixteenY4, aZ4, twoY, fourY2, S, M; 00338 }; 00339 00340 struct ZIterator 00341 { 00342 ZIterator() {} 00343 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {} 00344 Integer& operator*() {return it->z;} 00345 int operator-(ZIterator it2) {return int(it-it2.it);} 00346 ZIterator operator+(int i) {return ZIterator(it+i);} 00347 ZIterator& operator+=(int i) {it+=i; return *this;} 00348 std::vector<ProjectivePoint>::iterator it; 00349 }; 00350 00351 ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const 00352 { 00353 Element result; 00354 if (k.BitCount() <= 5) 00355 AbstractGroup<ECPPoint>::SimultaneousMultiply(&result, P, &k, 1); 00356 else 00357 ECP::SimultaneousMultiply(&result, P, &k, 1); 00358 return result; 00359 } 00360 00361 void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const 00362 { 00363 if (!GetField().IsMontgomeryRepresentation()) 00364 { 00365 ECP ecpmr(*this, true); 00366 const ModularArithmetic &mr = ecpmr.GetField(); 00367 ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount); 00368 for (unsigned int i=0; i<expCount; i++) 00369 results[i] = FromMontgomery(mr, results[i]); 00370 return; 00371 } 00372 00373 ProjectiveDoubling rd(GetField(), m_a, m_b, P); 00374 std::vector<ProjectivePoint> bases; 00375 std::vector<WindowSlider> exponents; 00376 exponents.reserve(expCount); 00377 std::vector<std::vector<word32> > baseIndices(expCount); 00378 std::vector<std::vector<bool> > negateBase(expCount); 00379 std::vector<std::vector<word32> > exponentWindows(expCount); 00380 unsigned int i; 00381 00382 for (i=0; i<expCount; i++) 00383 { 00384 assert(expBegin->NotNegative()); 00385 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5)); 00386 exponents[i].FindNextWindow(); 00387 } 00388 00389 unsigned int expBitPosition = 0; 00390 bool notDone = true; 00391 00392 while (notDone) 00393 { 00394 notDone = false; 00395 bool baseAdded = false; 00396 for (i=0; i<expCount; i++) 00397 { 00398 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin) 00399 { 00400 if (!baseAdded) 00401 { 00402 bases.push_back(rd.P); 00403 baseAdded =true; 00404 } 00405 00406 exponentWindows[i].push_back(exponents[i].expWindow); 00407 baseIndices[i].push_back((word32)bases.size()-1); 00408 negateBase[i].push_back(exponents[i].negateNext); 00409 00410 exponents[i].FindNextWindow(); 00411 } 00412 notDone = notDone || !exponents[i].finished; 00413 } 00414 00415 if (notDone) 00416 { 00417 rd.Double(); 00418 expBitPosition++; 00419 } 00420 } 00421 00422 // convert from projective to affine coordinates 00423 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end())); 00424 for (i=0; i<bases.size(); i++) 00425 { 00426 if (bases[i].z.NotZero()) 00427 { 00428 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z); 00429 bases[i].z = GetField().Square(bases[i].z); 00430 bases[i].x = GetField().Multiply(bases[i].x, bases[i].z); 00431 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z); 00432 } 00433 } 00434 00435 std::vector<BaseAndExponent<Point, Integer> > finalCascade; 00436 for (i=0; i<expCount; i++) 00437 { 00438 finalCascade.resize(baseIndices[i].size()); 00439 for (unsigned int j=0; j<baseIndices[i].size(); j++) 00440 { 00441 ProjectivePoint &base = bases[baseIndices[i][j]]; 00442 if (base.z.IsZero()) 00443 finalCascade[j].base.identity = true; 00444 else 00445 { 00446 finalCascade[j].base.identity = false; 00447 finalCascade[j].base.x = base.x; 00448 if (negateBase[i][j]) 00449 finalCascade[j].base.y = GetField().Inverse(base.y); 00450 else 00451 finalCascade[j].base.y = base.y; 00452 } 00453 finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]); 00454 } 00455 results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end()); 00456 } 00457 } 00458 00459 ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const 00460 { 00461 if (!GetField().IsMontgomeryRepresentation()) 00462 { 00463 ECP ecpmr(*this, true); 00464 const ModularArithmetic &mr = ecpmr.GetField(); 00465 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2)); 00466 } 00467 else 00468 return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2); 00469 } 00470 00471 NAMESPACE_END 00472 00473 #endif