- Main Page
- Namespaces
- Classes
- Files

# 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         {
    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