Crypto++
ecp.cpp
1 // ecp.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 
5 #ifndef CRYPTOPP_IMPORTS
6 
7 #include "ecp.h"
8 #include "asn.h"
9 #include "nbtheory.h"
10 
11 #include "algebra.cpp"
12 
13 NAMESPACE_BEGIN(CryptoPP)
14 
15 ANONYMOUS_NAMESPACE_BEGIN
16 static inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
17 {
18  return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
19 }
20 
21 static inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
22 {
23  return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
24 }
25 NAMESPACE_END
26 
27 ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation)
28 {
29  if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
30  {
31  m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus()));
32  m_a = GetField().ConvertIn(ecp.m_a);
33  m_b = GetField().ConvertIn(ecp.m_b);
34  }
35  else
36  operator=(ecp);
37 }
38 
39 ECP::ECP(BufferedTransformation &bt)
40  : m_fieldPtr(new Field(bt))
41 {
42  BERSequenceDecoder seq(bt);
43  GetField().BERDecodeElement(seq, m_a);
44  GetField().BERDecodeElement(seq, m_b);
45  // skip optional seed
46  if (!seq.EndReached())
47  {
48  SecByteBlock seed;
49  unsigned int unused;
50  BERDecodeBitString(seq, seed, unused);
51  }
52  seq.MessageEnd();
53 }
54 
55 void ECP::DEREncode(BufferedTransformation &bt) const
56 {
57  GetField().DEREncode(bt);
58  DERSequenceEncoder seq(bt);
59  GetField().DEREncodeElement(seq, m_a);
60  GetField().DEREncodeElement(seq, m_b);
61  seq.MessageEnd();
62 }
63 
64 bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
65 {
66  StringStore store(encodedPoint, encodedPointLen);
67  return DecodePoint(P, store, encodedPointLen);
68 }
69 
70 bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
71 {
72  byte type;
73  if (encodedPointLen < 1 || !bt.Get(type))
74  return false;
75 
76  switch (type)
77  {
78  case 0:
79  P.identity = true;
80  return true;
81  case 2:
82  case 3:
83  {
84  if (encodedPointLen != EncodedPointSize(true))
85  return false;
86 
87  Integer p = FieldSize();
88 
89  P.identity = false;
90  P.x.Decode(bt, GetField().MaxElementByteLength());
91  P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
92 
93  if (Jacobi(P.y, p) !=1)
94  return false;
95 
96  P.y = ModularSquareRoot(P.y, p);
97 
98  if ((type & 1) != P.y.GetBit(0))
99  P.y = p-P.y;
100 
101  return true;
102  }
103  case 4:
104  {
105  if (encodedPointLen != EncodedPointSize(false))
106  return false;
107 
108  unsigned int len = GetField().MaxElementByteLength();
109  P.identity = false;
110  P.x.Decode(bt, len);
111  P.y.Decode(bt, len);
112  return true;
113  }
114  default:
115  return false;
116  }
117 }
118 
119 void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
120 {
121  if (P.identity)
122  NullStore().TransferTo(bt, EncodedPointSize(compressed));
123  else if (compressed)
124  {
125  bt.Put(2 + P.y.GetBit(0));
126  P.x.Encode(bt, GetField().MaxElementByteLength());
127  }
128  else
129  {
130  unsigned int len = GetField().MaxElementByteLength();
131  bt.Put(4); // uncompressed
132  P.x.Encode(bt, len);
133  P.y.Encode(bt, len);
134  }
135 }
136 
137 void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
138 {
139  ArraySink sink(encodedPoint, EncodedPointSize(compressed));
140  EncodePoint(sink, P, compressed);
141  assert(sink.TotalPutLength() == EncodedPointSize(compressed));
142 }
143 
144 ECP::Point ECP::BERDecodePoint(BufferedTransformation &bt) const
145 {
146  SecByteBlock str;
147  BERDecodeOctetString(bt, str);
148  Point P;
149  if (!DecodePoint(P, str, str.size()))
150  BERDecodeError();
151  return P;
152 }
153 
154 void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
155 {
156  SecByteBlock str(EncodedPointSize(compressed));
157  EncodePoint(str, P, compressed);
158  DEREncodeOctetString(bt, str);
159 }
160 
161 bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
162 {
163  Integer p = FieldSize();
164 
165  bool pass = p.IsOdd();
166  pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
167 
168  if (level >= 1)
169  pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
170 
171  if (level >= 2)
172  pass = pass && VerifyPrime(rng, p);
173 
174  return pass;
175 }
176 
177 bool ECP::VerifyPoint(const Point &P) const
178 {
179  const FieldElement &x = P.x, &y = P.y;
180  Integer p = FieldSize();
181  return P.identity ||
182  (!x.IsNegative() && x<p && !y.IsNegative() && y<p
183  && !(((x*x+m_a)*x+m_b-y*y)%p));
184 }
185 
186 bool ECP::Equal(const Point &P, const Point &Q) const
187 {
188  if (P.identity && Q.identity)
189  return true;
190 
191  if (P.identity && !Q.identity)
192  return false;
193 
194  if (!P.identity && Q.identity)
195  return false;
196 
197  return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
198 }
199 
200 const ECP::Point& ECP::Identity() const
201 {
202  return Singleton<Point>().Ref();
203 }
204 
205 const ECP::Point& ECP::Inverse(const Point &P) const
206 {
207  if (P.identity)
208  return P;
209  else
210  {
211  m_R.identity = false;
212  m_R.x = P.x;
213  m_R.y = GetField().Inverse(P.y);
214  return m_R;
215  }
216 }
217 
218 const ECP::Point& ECP::Add(const Point &P, const Point &Q) const
219 {
220  if (P.identity) return Q;
221  if (Q.identity) return P;
222  if (GetField().Equal(P.x, Q.x))
223  return GetField().Equal(P.y, Q.y) ? Double(P) : Identity();
224 
225  FieldElement t = GetField().Subtract(Q.y, P.y);
226  t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
227  FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), Q.x);
228  m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
229 
230  m_R.x.swap(x);
231  m_R.identity = false;
232  return m_R;
233 }
234 
235 const ECP::Point& ECP::Double(const Point &P) const
236 {
237  if (P.identity || P.y==GetField().Identity()) return Identity();
238 
239  FieldElement t = GetField().Square(P.x);
240  t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
241  t = GetField().Divide(t, GetField().Double(P.y));
242  FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), P.x);
243  m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
244 
245  m_R.x.swap(x);
246  m_R.identity = false;
247  return m_R;
248 }
249 
250 template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)
251 {
252  size_t n = end-begin;
253  if (n == 1)
254  *begin = ring.MultiplicativeInverse(*begin);
255  else if (n > 1)
256  {
257  std::vector<T> vec((n+1)/2);
258  unsigned int i;
259  Iterator it;
260 
261  for (i=0, it=begin; i<n/2; i++, it+=2)
262  vec[i] = ring.Multiply(*it, *(it+1));
263  if (n%2 == 1)
264  vec[n/2] = *it;
265 
266  ParallelInvert(ring, vec.begin(), vec.end());
267 
268  for (i=0, it=begin; i<n/2; i++, it+=2)
269  {
270  if (!vec[i])
271  {
272  *it = ring.MultiplicativeInverse(*it);
273  *(it+1) = ring.MultiplicativeInverse(*(it+1));
274  }
275  else
276  {
277  std::swap(*it, *(it+1));
278  *it = ring.Multiply(*it, vec[i]);
279  *(it+1) = ring.Multiply(*(it+1), vec[i]);
280  }
281  }
282  if (n%2 == 1)
283  *it = vec[n/2];
284  }
285 }
286 
287 struct ProjectivePoint
288 {
289  ProjectivePoint() {}
290  ProjectivePoint(const Integer &x, const Integer &y, const Integer &z)
291  : x(x), y(y), z(z) {}
292 
293  Integer x,y,z;
294 };
295 
296 class ProjectiveDoubling
297 {
298 public:
299  ProjectiveDoubling(const ModularArithmetic &mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q)
300  : mr(mr), firstDoubling(true), negated(false)
301  {
302  if (Q.identity)
303  {
304  sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
305  aZ4 = P.z = mr.Identity();
306  }
307  else
308  {
309  P.x = Q.x;
310  P.y = Q.y;
311  sixteenY4 = P.z = mr.MultiplicativeIdentity();
312  aZ4 = m_a;
313  }
314  }
315 
316  void Double()
317  {
318  twoY = mr.Double(P.y);
319  P.z = mr.Multiply(P.z, twoY);
320  fourY2 = mr.Square(twoY);
321  S = mr.Multiply(fourY2, P.x);
322  aZ4 = mr.Multiply(aZ4, sixteenY4);
323  M = mr.Square(P.x);
324  M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
325  P.x = mr.Square(M);
326  mr.Reduce(P.x, S);
327  mr.Reduce(P.x, S);
328  mr.Reduce(S, P.x);
329  P.y = mr.Multiply(M, S);
330  sixteenY4 = mr.Square(fourY2);
331  mr.Reduce(P.y, mr.Half(sixteenY4));
332  }
333 
334  const ModularArithmetic &mr;
335  ProjectivePoint P;
336  bool firstDoubling, negated;
337  Integer sixteenY4, aZ4, twoY, fourY2, S, M;
338 };
339 
340 struct ZIterator
341 {
342  ZIterator() {}
343  ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
344  Integer& operator*() {return it->z;}
345  int operator-(ZIterator it2) {return int(it-it2.it);}
346  ZIterator operator+(int i) {return ZIterator(it+i);}
347  ZIterator& operator+=(int i) {it+=i; return *this;}
348  std::vector<ProjectivePoint>::iterator it;
349 };
350 
351 ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
352 {
353  Element result;
354  if (k.BitCount() <= 5)
356  else
357  ECP::SimultaneousMultiply(&result, P, &k, 1);
358  return result;
359 }
360 
361 void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
362 {
363  if (!GetField().IsMontgomeryRepresentation())
364  {
365  ECP ecpmr(*this, true);
366  const ModularArithmetic &mr = ecpmr.GetField();
367  ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
368  for (unsigned int i=0; i<expCount; i++)
369  results[i] = FromMontgomery(mr, results[i]);
370  return;
371  }
372 
373  ProjectiveDoubling rd(GetField(), m_a, m_b, P);
374  std::vector<ProjectivePoint> bases;
375  std::vector<WindowSlider> exponents;
376  exponents.reserve(expCount);
377  std::vector<std::vector<word32> > baseIndices(expCount);
378  std::vector<std::vector<bool> > negateBase(expCount);
379  std::vector<std::vector<word32> > exponentWindows(expCount);
380  unsigned int i;
381 
382  for (i=0; i<expCount; i++)
383  {
384  assert(expBegin->NotNegative());
385  exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
386  exponents[i].FindNextWindow();
387  }
388 
389  unsigned int expBitPosition = 0;
390  bool notDone = true;
391 
392  while (notDone)
393  {
394  notDone = false;
395  bool baseAdded = false;
396  for (i=0; i<expCount; i++)
397  {
398  if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
399  {
400  if (!baseAdded)
401  {
402  bases.push_back(rd.P);
403  baseAdded =true;
404  }
405 
406  exponentWindows[i].push_back(exponents[i].expWindow);
407  baseIndices[i].push_back((word32)bases.size()-1);
408  negateBase[i].push_back(exponents[i].negateNext);
409 
410  exponents[i].FindNextWindow();
411  }
412  notDone = notDone || !exponents[i].finished;
413  }
414 
415  if (notDone)
416  {
417  rd.Double();
418  expBitPosition++;
419  }
420  }
421 
422  // convert from projective to affine coordinates
423  ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
424  for (i=0; i<bases.size(); i++)
425  {
426  if (bases[i].z.NotZero())
427  {
428  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
429  bases[i].z = GetField().Square(bases[i].z);
430  bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
431  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
432  }
433  }
434 
435  std::vector<BaseAndExponent<Point, Integer> > finalCascade;
436  for (i=0; i<expCount; i++)
437  {
438  finalCascade.resize(baseIndices[i].size());
439  for (unsigned int j=0; j<baseIndices[i].size(); j++)
440  {
441  ProjectivePoint &base = bases[baseIndices[i][j]];
442  if (base.z.IsZero())
443  finalCascade[j].base.identity = true;
444  else
445  {
446  finalCascade[j].base.identity = false;
447  finalCascade[j].base.x = base.x;
448  if (negateBase[i][j])
449  finalCascade[j].base.y = GetField().Inverse(base.y);
450  else
451  finalCascade[j].base.y = base.y;
452  }
453  finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
454  }
455  results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end());
456  }
457 }
458 
459 ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
460 {
461  if (!GetField().IsMontgomeryRepresentation())
462  {
463  ECP ecpmr(*this, true);
464  const ModularArithmetic &mr = ecpmr.GetField();
465  return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
466  }
467  else
468  return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
469 }
470 
471 NAMESPACE_END
472 
473 #endif
Elliptical Curve Point.
Definition: ecp.h:12
bool GetBit(size_t i) const
return the i-th bit, i=0 being the least significant bit
Definition: integer.cpp:2894
Elliptic Curve over GF(p), where p is prime.
Definition: ecp.h:30
a block of memory allocated using A
Definition: secblock.h:238
Square
Definition: square.h:19
ring of congruence classes modulo n
Definition: modarith.h:19
interface for random number generators
Definition: cryptlib.h:669
BER Sequence Decoder.
Definition: asn.h:177
interface for buffered transformations
Definition: cryptlib.h:771
Abstract Ring.
Definition: algebra.h:44
unsigned int BitCount() const
number of significant bits = floor(log2(abs(*this))) + 1
Definition: integer.cpp:3054
Copy input to a memory buffer.
Definition: filters.h:635
empty store
Definition: filters.h:713
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:900
size_t Put(byte inByte, bool blocking=true)
input a byte for processing
Definition: cryptlib.h:785
multiple precision integer and basic arithmetics
Definition: integer.h:26
string-based implementation of Store interface
Definition: filters.h:666
Abstract Group.
Definition: algebra.h:19
DER Sequence Encoder.
Definition: asn.h:187
do modular arithmetics in Montgomery representation for increased speed
Definition: modarith.h:122
virtual size_t Get(byte &outByte)
try to retrieve a single byte
Definition: cryptlib.cpp:405