Crypto++  5.6.5
Free C++ class library of cryptographic schemes
ec2n.cpp
1 // ec2n.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 
5 #ifndef CRYPTOPP_IMPORTS
6 
7 #include "ec2n.h"
8 #include "asn.h"
9 #include "integer.h"
10 #include "filters.h"
11 #include "algebra.cpp"
12 #include "eprecomp.cpp"
13 
14 NAMESPACE_BEGIN(CryptoPP)
15 
17  : m_field(BERDecodeGF2NP(bt))
18 {
19  BERSequenceDecoder seq(bt);
20  m_field->BERDecodeElement(seq, m_a);
21  m_field->BERDecodeElement(seq, m_b);
22  // skip optional seed
23  if (!seq.EndReached())
24  {
25  SecByteBlock seed;
26  unsigned int unused;
27  BERDecodeBitString(seq, seed, unused);
28  }
29  seq.MessageEnd();
30 }
31 
33 {
34  m_field->DEREncode(bt);
35  DERSequenceEncoder seq(bt);
36  m_field->DEREncodeElement(seq, m_a);
37  m_field->DEREncodeElement(seq, m_b);
38  seq.MessageEnd();
39 }
40 
41 bool EC2N::DecodePoint(EC2N::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
42 {
43  StringStore store(encodedPoint, encodedPointLen);
44  return DecodePoint(P, store, encodedPointLen);
45 }
46 
47 bool EC2N::DecodePoint(EC2N::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
48 {
49  byte type;
50  if (encodedPointLen < 1 || !bt.Get(type))
51  return false;
52 
53  switch (type)
54  {
55  case 0:
56  P.identity = true;
57  return true;
58  case 2:
59  case 3:
60  {
61  if (encodedPointLen != EncodedPointSize(true))
62  return false;
63 
64  P.identity = false;
65  P.x.Decode(bt, m_field->MaxElementByteLength());
66 
67  if (P.x.IsZero())
68  {
69  P.y = m_field->SquareRoot(m_b);
70  return true;
71  }
72 
73  FieldElement z = m_field->Square(P.x);
74  CRYPTOPP_ASSERT(P.x == m_field->SquareRoot(z));
75  P.y = m_field->Divide(m_field->Add(m_field->Multiply(z, m_field->Add(P.x, m_a)), m_b), z);
76  CRYPTOPP_ASSERT(P.x == m_field->Subtract(m_field->Divide(m_field->Subtract(m_field->Multiply(P.y, z), m_b), z), m_a));
77  z = m_field->SolveQuadraticEquation(P.y);
78  CRYPTOPP_ASSERT(m_field->Add(m_field->Square(z), z) == P.y);
79  z.SetCoefficient(0, type & 1);
80 
81  P.y = m_field->Multiply(z, P.x);
82  return true;
83  }
84  case 4:
85  {
86  if (encodedPointLen != EncodedPointSize(false))
87  return false;
88 
89  unsigned int len = m_field->MaxElementByteLength();
90  P.identity = false;
91  P.x.Decode(bt, len);
92  P.y.Decode(bt, len);
93  return true;
94  }
95  default:
96  return false;
97  }
98 }
99 
100 void EC2N::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
101 {
102  if (P.identity)
103  NullStore().TransferTo(bt, EncodedPointSize(compressed));
104  else if (compressed)
105  {
106  bt.Put(2 + (!P.x ? 0 : m_field->Divide(P.y, P.x).GetBit(0)));
107  P.x.Encode(bt, m_field->MaxElementByteLength());
108  }
109  else
110  {
111  unsigned int len = m_field->MaxElementByteLength();
112  bt.Put(4); // uncompressed
113  P.x.Encode(bt, len);
114  P.y.Encode(bt, len);
115  }
116 }
117 
118 void EC2N::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
119 {
120  ArraySink sink(encodedPoint, EncodedPointSize(compressed));
121  EncodePoint(sink, P, compressed);
122  CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
123 }
124 
126 {
127  SecByteBlock str;
128  BERDecodeOctetString(bt, str);
129  Point P;
130  if (!DecodePoint(P, str, str.size()))
131  BERDecodeError();
132  return P;
133 }
134 
135 void EC2N::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
136 {
137  SecByteBlock str(EncodedPointSize(compressed));
138  EncodePoint(str, P, compressed);
139  DEREncodeOctetString(bt, str);
140 }
141 
142 bool EC2N::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
143 {
144  CRYPTOPP_UNUSED(rng);
145  bool pass = !!m_b;
146  pass = pass && m_a.CoefficientCount() <= m_field->MaxElementBitLength();
147  pass = pass && m_b.CoefficientCount() <= m_field->MaxElementBitLength();
148 
149  if (level >= 1)
150  pass = pass && m_field->GetModulus().IsIrreducible();
151 
152  return pass;
153 }
154 
155 bool EC2N::VerifyPoint(const Point &P) const
156 {
157  const FieldElement &x = P.x, &y = P.y;
158  return P.identity ||
159  (x.CoefficientCount() <= m_field->MaxElementBitLength()
160  && y.CoefficientCount() <= m_field->MaxElementBitLength()
161  && !(((x+m_a)*x*x+m_b-(x+y)*y)%m_field->GetModulus()));
162 }
163 
164 bool EC2N::Equal(const Point &P, const Point &Q) const
165 {
166  if (P.identity && Q.identity)
167  return true;
168 
169  if (P.identity && !Q.identity)
170  return false;
171 
172  if (!P.identity && Q.identity)
173  return false;
174 
175  return (m_field->Equal(P.x,Q.x) && m_field->Equal(P.y,Q.y));
176 }
177 
179 {
180  return Singleton<Point>().Ref();
181 }
182 
183 const EC2N::Point& EC2N::Inverse(const Point &P) const
184 {
185  if (P.identity)
186  return P;
187  else
188  {
189  m_R.identity = false;
190  m_R.y = m_field->Add(P.x, P.y);
191  m_R.x = P.x;
192  return m_R;
193  }
194 }
195 
196 const EC2N::Point& EC2N::Add(const Point &P, const Point &Q) const
197 {
198  if (P.identity) return Q;
199  if (Q.identity) return P;
200  if (Equal(P, Q)) return Double(P);
201  if (m_field->Equal(P.x, Q.x) && m_field->Equal(P.y, m_field->Add(Q.x, Q.y))) return Identity();
202 
203  FieldElement t = m_field->Add(P.y, Q.y);
204  t = m_field->Divide(t, m_field->Add(P.x, Q.x));
205  FieldElement x = m_field->Square(t);
206  m_field->Accumulate(x, t);
207  m_field->Accumulate(x, Q.x);
208  m_field->Accumulate(x, m_a);
209  m_R.y = m_field->Add(P.y, m_field->Multiply(t, x));
210  m_field->Accumulate(x, P.x);
211  m_field->Accumulate(m_R.y, x);
212 
213  m_R.x.swap(x);
214  m_R.identity = false;
215  return m_R;
216 }
217 
218 const EC2N::Point& EC2N::Double(const Point &P) const
219 {
220  if (P.identity) return P;
221  if (!m_field->IsUnit(P.x)) return Identity();
222 
223  FieldElement t = m_field->Divide(P.y, P.x);
224  m_field->Accumulate(t, P.x);
225  m_R.y = m_field->Square(P.x);
226  m_R.x = m_field->Square(t);
227  m_field->Accumulate(m_R.x, t);
228  m_field->Accumulate(m_R.x, m_a);
229  m_field->Accumulate(m_R.y, m_field->Multiply(t, m_R.x));
230  m_field->Accumulate(m_R.y, m_R.x);
231 
232  m_R.identity = false;
233  return m_R;
234 }
235 
236 // ********************************************************
237 
238 /*
239 EcPrecomputation<EC2N>& EcPrecomputation<EC2N>::operator=(const EcPrecomputation<EC2N> &rhs)
240 {
241  m_ec = rhs.m_ec;
242  m_ep = rhs.m_ep;
243  m_ep.m_group = m_ec.get();
244  return *this;
245 }
246 
247 void EcPrecomputation<EC2N>::SetCurveAndBase(const EC2N &ec, const EC2N::Point &base)
248 {
249  m_ec.reset(new EC2N(ec));
250  m_ep.SetGroupAndBase(*m_ec, base);
251 }
252 
253 void EcPrecomputation<EC2N>::Precompute(unsigned int maxExpBits, unsigned int storage)
254 {
255  m_ep.Precompute(maxExpBits, storage);
256 }
257 
258 void EcPrecomputation<EC2N>::Load(BufferedTransformation &bt)
259 {
260  BERSequenceDecoder seq(bt);
261  word32 version;
262  BERDecodeUnsigned<word32>(seq, version, INTEGER, 1, 1);
263  m_ep.m_exponentBase.BERDecode(seq);
264  m_ep.m_windowSize = m_ep.m_exponentBase.BitCount() - 1;
265  m_ep.m_bases.clear();
266  while (!seq.EndReached())
267  m_ep.m_bases.push_back(m_ec->BERDecodePoint(seq));
268  seq.MessageEnd();
269 }
270 
271 void EcPrecomputation<EC2N>::Save(BufferedTransformation &bt) const
272 {
273  DERSequenceEncoder seq(bt);
274  DEREncodeUnsigned<word32>(seq, 1); // version
275  m_ep.m_exponentBase.DEREncode(seq);
276  for (unsigned i=0; i<m_ep.m_bases.size(); i++)
277  m_ec->DEREncodePoint(seq, m_ep.m_bases[i]);
278  seq.MessageEnd();
279 }
280 
281 EC2N::Point EcPrecomputation<EC2N>::Exponentiate(const Integer &exponent) const
282 {
283  return m_ep.Exponentiate(exponent);
284 }
285 
286 EC2N::Point EcPrecomputation<EC2N>::CascadeExponentiate(const Integer &exponent, const DL_FixedBasePrecomputation<Element> &pc2, const Integer &exponent2) const
287 {
288  return m_ep.CascadeExponentiate(exponent, static_cast<const EcPrecomputation<EC2N> &>(pc2).m_ep, exponent2);
289 }
290 */
291 
292 NAMESPACE_END
293 
294 #endif
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:274
bool VerifyPoint(const Point &P) const
Verifies points on elliptic curve.
Definition: ec2n.cpp:155
bool Equal(const Point &P, const Point &Q) const
Compare two elements for equality.
Definition: ec2n.cpp:164
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
Definition: ec2n.cpp:47
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:524
Interface for random number generators.
Definition: cryptlib.h:1188
SecBlock typedef.
Definition: secblock.h:731
BER Sequence Decoder.
Definition: asn.h:302
Interface for buffered transformations.
Definition: cryptlib.h:1352
Classes for Elliptic Curves over binary fields.
Copy input to a memory buffer.
Definition: filters.h:1101
empty store
Definition: filters.h:1215
void DEREncode(BufferedTransformation &bt) const
Encode the fields fieldID and curve of the sequence ECParameters.
Definition: ec2n.cpp:32
lword TransferTo(BufferedTransformation &target, lword transferMax=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL)
move transferMax bytes of the buffered output to target as input
Definition: cryptlib.h:1654
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
Definition: ec2n.h:67
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1376
size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
Definition: asn.cpp:117
void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
DER Encodes an elliptic curve point.
Definition: ec2n.cpp:135
const Point & Inverse(const Point &P) const
Inverts the element in the group.
Definition: ec2n.cpp:183
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
Definition: gf2n.cpp:150
Elliptic Curve over GF(2^n)
Definition: ec2n.h:24
String-based implementation of Store interface.
Definition: filters.h:1155
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:62
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:68
Classes and functions for working with ANS.1 objects.
const Point & Double(const Point &P) const
Doubles an element in the group.
Definition: ec2n.cpp:218
Implementation of BufferedTransformation's attachment interface.
const Point & Identity() const
Provides the Identity element.
Definition: ec2n.cpp:178
void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
Encodes an elliptic curve point.
Definition: ec2n.cpp:118
DER Sequence Encoder.
Definition: asn.h:312
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
Definition: ec2n.cpp:125
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
Definition: asn.cpp:104
Multiple precision integer with arithmetic operations.
size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
Definition: asn.cpp:182
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:515
Crypto++ library namespace.
Elliptical Curve Point over GF(2^n)
Definition: ecpoint.h:55
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
Definition: ec2n.cpp:196
lword TotalPutLength()
Provides the number of bytes written to the Sink.
Definition: filters.h:1124