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