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

# ec2n.cpp

    00001 // ec2n.cpp - written and placed in the public domain by Wei Dai
    00002
    00003 #include "pch.h"
    00004
    00005 #ifndef CRYPTOPP_IMPORTS
    00006
    00007 #include "ec2n.h"
    00008 #include "asn.h"
    00009
    00010 #include "algebra.cpp"
    00011 #include "eprecomp.cpp"
    00012
    00013 NAMESPACE_BEGIN(CryptoPP)
    00014
    00015 EC2N::EC2N(BufferedTransformation &bt)
    00016         : m_field(BERDecodeGF2NP(bt))
    00017 {
    00018         BERSequenceDecoder seq(bt);
    00019         m_field->BERDecodeElement(seq, m_a);
    00020         m_field->BERDecodeElement(seq, m_b);
    00021         // skip optional seed
    00022         if (!seq.EndReached())
    00023                 BERDecodeOctetString(seq, TheBitBucket());
    00024         seq.MessageEnd();
    00025 }
    00026
    00027 void EC2N::DEREncode(BufferedTransformation &bt) const
    00028 {
    00029         m_field->DEREncode(bt);
    00030         DERSequenceEncoder seq(bt);
    00031         m_field->DEREncodeElement(seq, m_a);
    00032         m_field->DEREncodeElement(seq, m_b);
    00033         seq.MessageEnd();
    00034 }
    00035
    00036 bool EC2N::DecodePoint(EC2N::Point &P, const byte *encodedPoint, unsigned int encodedPointLen) const
    00037 {
    00038         StringStore store(encodedPoint, encodedPointLen);
    00039         return DecodePoint(P, store, encodedPointLen);
    00040 }
    00041
    00042 bool EC2N::DecodePoint(EC2N::Point &P, BufferedTransformation &bt, unsigned int encodedPointLen) const
    00043 {
    00044         byte type;
    00045         if (encodedPointLen < 1 || !bt.Get(type))
    00046                 return false;
    00047
    00048         switch (type)
    00049         {
    00050         case 0:
    00051                 P.identity = true;
    00052                 return true;
    00053         case 2:
    00054         case 3:
    00055         {
    00056                 if (encodedPointLen != EncodedPointSize(true))
    00057                         return false;
    00058
    00059                 P.identity = false;
    00060                 P.x.Decode(bt, m_field->MaxElementByteLength());
    00061
    00062                 if (P.x.IsZero())
    00063                 {
    00064                         P.y = m_field->SquareRoot(m_b);
    00065                         return true;
    00066                 }
    00067
    00068                 FieldElement z = m_field->Square(P.x);
    00069                 assert(P.x == m_field->SquareRoot(z));
    00070                 P.y = m_field->Divide(m_field->Add(m_field->Multiply(z, m_field->Add(P.x, m_a)), m_b), z);
    00071                 assert(P.x == m_field->Subtract(m_field->Divide(m_field->Subtract(m_field->Multiply(P.y, z), m_b), z), m_a));
    00072                 z = m_field->SolveQuadraticEquation(P.y);
    00073                 assert(m_field->Add(m_field->Square(z), z) == P.y);
    00074                 z.SetCoefficient(0, type & 1);
    00075
    00076                 P.y = m_field->Multiply(z, P.x);
    00077                 return true;
    00078         }
    00079         case 4:
    00080         {
    00081                 if (encodedPointLen != EncodedPointSize(false))
    00082                         return false;
    00083
    00084                 unsigned int len = m_field->MaxElementByteLength();
    00085                 P.identity = false;
    00086                 P.x.Decode(bt, len);
    00087                 P.y.Decode(bt, len);
    00088                 return true;
    00089         }
    00090         default:
    00091                 return false;
    00092         }
    00093 }
    00094
    00095 void EC2N::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
    00096 {
    00097         if (P.identity)
    00098                 NullStore().TransferTo(bt, EncodedPointSize(compressed));
    00099         else if (compressed)
    00100         {
    00101                 bt.Put(2 + (!P.x ? 0 : m_field->Divide(P.y, P.x).GetBit(0)));
    00102                 P.x.Encode(bt, m_field->MaxElementByteLength());
    00103         }
    00104         else
    00105         {
    00106                 unsigned int len = m_field->MaxElementByteLength();
    00107                 bt.Put(4);      // uncompressed
    00108                 P.x.Encode(bt, len);
    00109                 P.y.Encode(bt, len);
    00110         }
    00111 }
    00112
    00113 void EC2N::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
    00114 {
    00115         ArraySink sink(encodedPoint, EncodedPointSize(compressed));
    00116         EncodePoint(sink, P, compressed);
    00117         assert(sink.TotalPutLength() == EncodedPointSize(compressed));
    00118 }
    00119
    00120 EC2N::Point EC2N::BERDecodePoint(BufferedTransformation &bt) const
    00121 {
    00122         SecByteBlock str;
    00123         BERDecodeOctetString(bt, str);
    00124         Point P;
    00125         if (!DecodePoint(P, str, str.size()))
    00126                 BERDecodeError();
    00127         return P;
    00128 }
    00129
    00130 void EC2N::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
    00131 {
    00132         SecByteBlock str(EncodedPointSize(compressed));
    00133         EncodePoint(str, P, compressed);
    00134         DEREncodeOctetString(bt, str);
    00135 }
    00136
    00137 bool EC2N::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
    00138 {
    00139         bool pass = !!m_b;
    00140         pass = pass && m_a.CoefficientCount() <= m_field->MaxElementBitLength();
    00141         pass = pass && m_b.CoefficientCount() <= m_field->MaxElementBitLength();
    00142
    00143         if (level >= 1)
    00144                 pass = pass && m_field->GetModulus().IsIrreducible();
    00145
    00146         return pass;
    00147 }
    00148
    00149 bool EC2N::VerifyPoint(const Point &P) const
    00150 {
    00151         const FieldElement &x = P.x, &y = P.y;
    00152         return P.identity ||
    00153                 (x.CoefficientCount() <= m_field->MaxElementBitLength()
    00154                 && y.CoefficientCount() <= m_field->MaxElementBitLength()
    00155                 && !(((x+m_a)*x*x+m_b-(x+y)*y)%m_field->GetModulus()));
    00156 }
    00157
    00158 bool EC2N::Equal(const Point &P, const Point &Q) const
    00159 {
    00160         if (P.identity && Q.identity)
    00161                 return true;
    00162
    00163         if (P.identity && !Q.identity)
    00164                 return false;
    00165
    00166         if (!P.identity && Q.identity)
    00167                 return false;
    00168
    00169         return (m_field->Equal(P.x,Q.x) && m_field->Equal(P.y,Q.y));
    00170 }
    00171
    00172 const EC2N::Point& EC2N::Identity() const
    00173 {
    00174         static const Point zero;
    00175         return zero;
    00176 }
    00177
    00178 const EC2N::Point& EC2N::Inverse(const Point &P) const
    00179 {
    00180         if (P.identity)
    00181                 return P;
    00182         else
    00183         {
    00184                 m_R.identity = false;
    00185                 m_R.y = m_field->Add(P.x, P.y);
    00186                 m_R.x = P.x;
    00187                 return m_R;
    00188         }
    00189 }
    00190
    00191 const EC2N::Point& EC2N::Add(const Point &P, const Point &Q) const
    00192 {
    00193         if (P.identity) return Q;
    00194         if (Q.identity) return P;
    00195         if (Equal(P, Q)) return Double(P);
    00196         if (m_field->Equal(P.x, Q.x) && m_field->Equal(P.y, m_field->Add(Q.x, Q.y))) return Identity();
    00197
    00198         FieldElement t = m_field->Add(P.y, Q.y);
    00199         t = m_field->Divide(t, m_field->Add(P.x, Q.x));
    00200         FieldElement x = m_field->Square(t);
    00201         m_field->Accumulate(x, t);
    00202         m_field->Accumulate(x, Q.x);
    00203         m_field->Accumulate(x, m_a);
    00204         m_R.y = m_field->Add(P.y, m_field->Multiply(t, x));
    00205         m_field->Accumulate(x, P.x);
    00206         m_field->Accumulate(m_R.y, x);
    00207
    00208         m_R.x.swap(x);
    00209         m_R.identity = false;
    00210         return m_R;
    00211 }
    00212
    00213 const EC2N::Point& EC2N::Double(const Point &P) const
    00214 {
    00215         if (P.identity) return P;
    00216         if (!m_field->IsUnit(P.x)) return Identity();
    00217
    00218         FieldElement t = m_field->Divide(P.y, P.x);
    00219         m_field->Accumulate(t, P.x);
    00220         m_R.y = m_field->Square(P.x);
    00221         m_R.x = m_field->Square(t);
    00222         m_field->Accumulate(m_R.x, t);
    00223         m_field->Accumulate(m_R.x, m_a);
    00224         m_field->Accumulate(m_R.y, m_field->Multiply(t, m_R.x));
    00225         m_field->Accumulate(m_R.y, m_R.x);
    00226
    00227         m_R.identity = false;
    00228         return m_R;
    00229 }
    00230
    00231 // ********************************************************
    00232
    00233 /*
    00234 EcPrecomputation<EC2N>& EcPrecomputation<EC2N>::operator=(const EcPrecomputation<EC2N> &rhs)
    00235 {
    00236         m_ec = rhs.m_ec;
    00237         m_ep = rhs.m_ep;
    00238         m_ep.m_group = m_ec.get();
    00239         return *this;
    00240 }
    00241
    00242 void EcPrecomputation<EC2N>::SetCurveAndBase(const EC2N &ec, const EC2N::Point &base)
    00243 {
    00244         m_ec.reset(new EC2N(ec));
    00245         m_ep.SetGroupAndBase(*m_ec, base);
    00246 }
    00247
    00248 void EcPrecomputation<EC2N>::Precompute(unsigned int maxExpBits, unsigned int storage)
    00249 {
    00250         m_ep.Precompute(maxExpBits, storage);
    00251 }
    00252
    00253 void EcPrecomputation<EC2N>::Load(BufferedTransformation &bt)
    00254 {
    00255         BERSequenceDecoder seq(bt);
    00256         word32 version;
    00257         BERDecodeUnsigned<word32>(seq, version, INTEGER, 1, 1);
    00258         m_ep.m_exponentBase.BERDecode(seq);
    00259         m_ep.m_windowSize = m_ep.m_exponentBase.BitCount() - 1;
    00260         m_ep.m_bases.clear();
    00261         while (!seq.EndReached())
    00262                 m_ep.m_bases.push_back(m_ec->BERDecodePoint(seq));
    00263         seq.MessageEnd();
    00264 }
    00265
    00266 void EcPrecomputation<EC2N>::Save(BufferedTransformation &bt) const
    00267 {
    00268         DERSequenceEncoder seq(bt);
    00269         DEREncodeUnsigned<word32>(seq, 1);      // version
    00270         m_ep.m_exponentBase.DEREncode(seq);
    00271         for (unsigned i=0; i<m_ep.m_bases.size(); i++)
    00272                 m_ec->DEREncodePoint(seq, m_ep.m_bases[i]);
    00273         seq.MessageEnd();
    00274 }
    00275
    00276 EC2N::Point EcPrecomputation<EC2N>::Exponentiate(const Integer &exponent) const
    00277 {
    00278         return m_ep.Exponentiate(exponent);
    00279 }
    00280
    00281 EC2N::Point EcPrecomputation<EC2N>::CascadeExponentiate(const Integer &exponent, const DL_FixedBasePrecomputation<Element> &pc2, const Integer &exponent2) const
    00282 {
    00283         return m_ep.CascadeExponentiate(exponent, static_cast<const EcPrecomputation<EC2N> &>(pc2).m_ep, exponent2);
    00284 }
    00285 */
    00286
    00287 NAMESPACE_END
    00288
    00289 #endif