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

ec2n.cpp

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

Generated on Sun Mar 14 20:44:25 2004 for Crypto++ by doxygen 1.3.6-20040222