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 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 return Singleton<Point>().Ref(); 00175 } 00176 00177 const EC2N::Point& EC2N::Inverse(const Point &P) const 00178 { 00179 if (P.identity) 00180 return P; 00181 else 00182 { 00183 m_R.identity = false; 00184 m_R.y = m_field->Add(P.x, P.y); 00185 m_R.x = P.x; 00186 return m_R; 00187 } 00188 } 00189 00190 const EC2N::Point& EC2N::Add(const Point &P, const Point &Q) const 00191 { 00192 if (P.identity) return Q; 00193 if (Q.identity) return P; 00194 if (Equal(P, Q)) return Double(P); 00195 if (m_field->Equal(P.x, Q.x) && m_field->Equal(P.y, m_field->Add(Q.x, Q.y))) return Identity(); 00196 00197 FieldElement t = m_field->Add(P.y, Q.y); 00198 t = m_field->Divide(t, m_field->Add(P.x, Q.x)); 00199 FieldElement x = m_field->Square(t); 00200 m_field->Accumulate(x, t); 00201 m_field->Accumulate(x, Q.x); 00202 m_field->Accumulate(x, m_a); 00203 m_R.y = m_field->Add(P.y, m_field->Multiply(t, x)); 00204 m_field->Accumulate(x, P.x); 00205 m_field->Accumulate(m_R.y, x); 00206 00207 m_R.x.swap(x); 00208 m_R.identity = false; 00209 return m_R; 00210 } 00211 00212 const EC2N::Point& EC2N::Double(const Point &P) const 00213 { 00214 if (P.identity) return P; 00215 if (!m_field->IsUnit(P.x)) return Identity(); 00216 00217 FieldElement t = m_field->Divide(P.y, P.x); 00218 m_field->Accumulate(t, P.x); 00219 m_R.y = m_field->Square(P.x); 00220 m_R.x = m_field->Square(t); 00221 m_field->Accumulate(m_R.x, t); 00222 m_field->Accumulate(m_R.x, m_a); 00223 m_field->Accumulate(m_R.y, m_field->Multiply(t, m_R.x)); 00224 m_field->Accumulate(m_R.y, m_R.x); 00225 00226 m_R.identity = false; 00227 return m_R; 00228 } 00229 00230 // ******************************************************** 00231 00232 /* 00233 EcPrecomputation<EC2N>& EcPrecomputation<EC2N>::operator=(const EcPrecomputation<EC2N> &rhs) 00234 { 00235 m_ec = rhs.m_ec; 00236 m_ep = rhs.m_ep; 00237 m_ep.m_group = m_ec.get(); 00238 return *this; 00239 } 00240 00241 void EcPrecomputation<EC2N>::SetCurveAndBase(const EC2N &ec, const EC2N::Point &base) 00242 { 00243 m_ec.reset(new EC2N(ec)); 00244 m_ep.SetGroupAndBase(*m_ec, base); 00245 } 00246 00247 void EcPrecomputation<EC2N>::Precompute(unsigned int maxExpBits, unsigned int storage) 00248 { 00249 m_ep.Precompute(maxExpBits, storage); 00250 } 00251 00252 void EcPrecomputation<EC2N>::Load(BufferedTransformation &bt) 00253 { 00254 BERSequenceDecoder seq(bt); 00255 word32 version; 00256 BERDecodeUnsigned<word32>(seq, version, INTEGER, 1, 1); 00257 m_ep.m_exponentBase.BERDecode(seq); 00258 m_ep.m_windowSize = m_ep.m_exponentBase.BitCount() - 1; 00259 m_ep.m_bases.clear(); 00260 while (!seq.EndReached()) 00261 m_ep.m_bases.push_back(m_ec->BERDecodePoint(seq)); 00262 seq.MessageEnd(); 00263 } 00264 00265 void EcPrecomputation<EC2N>::Save(BufferedTransformation &bt) const 00266 { 00267 DERSequenceEncoder seq(bt); 00268 DEREncodeUnsigned<word32>(seq, 1); // version 00269 m_ep.m_exponentBase.DEREncode(seq); 00270 for (unsigned i=0; i<m_ep.m_bases.size(); i++) 00271 m_ec->DEREncodePoint(seq, m_ep.m_bases[i]); 00272 seq.MessageEnd(); 00273 } 00274 00275 EC2N::Point EcPrecomputation<EC2N>::Exponentiate(const Integer &exponent) const 00276 { 00277 return m_ep.Exponentiate(exponent); 00278 } 00279 00280 EC2N::Point EcPrecomputation<EC2N>::CascadeExponentiate(const Integer &exponent, const DL_FixedBasePrecomputation<Element> &pc2, const Integer &exponent2) const 00281 { 00282 return m_ep.CascadeExponentiate(exponent, static_cast<const EcPrecomputation<EC2N> &>(pc2).m_ep, exponent2); 00283 } 00284 */ 00285 00286 NAMESPACE_END 00287 00288 #endif

Generated on Fri Aug 27 13:57:07 2004 for Crypto++ by doxygen 1.3.8