Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound Members | File Members

# ecp.cpp

    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                 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);      // uncompressed
    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         // convert from projective to affine coordinates
    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