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