Crypto++  8.2 Free C++ class library of cryptographic schemes
ecp.cpp
1 // ecp.cpp - originally 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 "integer.h"
10 #include "nbtheory.h"
11 #include "modarith.h"
12 #include "filters.h"
13 #include "algebra.cpp"
14
15 ANONYMOUS_NAMESPACE_BEGIN
16
17 using CryptoPP::ECP;
18 using CryptoPP::Integer;
19 using CryptoPP::ModularArithmetic;
20
21 #if defined(HAVE_GCC_INIT_PRIORITY)
22  #define INIT_ATTRIBUTE __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 50)))
23  const ECP::Point g_identity INIT_ATTRIBUTE = ECP::Point();
24 #elif defined(HAVE_MSC_INIT_PRIORITY)
25  #pragma warning(disable: 4075)
26  #pragma init_seg(".CRT\$XCU")
27  const ECP::Point g_identity;
28  #pragma warning(default: 4075)
29 #elif defined(HAVE_XLC_INIT_PRIORITY)
30  #pragma priority(290)
31  const ECP::Point g_identity;
32 #endif
33
34 inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
35 {
36  return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
37 }
38
39 inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
40 {
41  return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
42 }
43
44 inline Integer IdentityToInteger(bool val)
45 {
46  return val ? Integer::One() : Integer::Zero();
47 }
48
49 struct ProjectivePoint
50 {
51  ProjectivePoint() {}
52  ProjectivePoint(const Integer &x, const Integer &y, const Integer &z)
53  : x(x), y(y), z(z) {}
54
55  Integer x, y, z;
56 };
57
58 /// \brief Addition and Double functions
59 /// \sa <A HREF="https://eprint.iacr.org/2015/1060.pdf">Complete
60 /// addition formulas for prime order elliptic curves</A>
62 {
64  const ECP::FieldElement &a, const ECP::FieldElement &b, ECP::Point &r);
65
66  // Double(P)
67  ECP::Point operator()(const ECP::Point& P) const;
69  ECP::Point operator()(const ECP::Point& P, const ECP::Point& Q) const;
70
71 protected:
72  /// \brief Parameters and representation for Addition
73  /// \details Addition and Doubling will use different algorithms,
74  /// depending on the <tt>A</tt> coefficient and the representation
75  /// (Affine or Montgomery with precomputation).
76  enum Alpha {
77  /// \brief Coefficient A is 0
78  A_0 = 1,
79  /// \brief Coefficient A is -3
80  A_3 = 2,
81  /// \brief Coefficient A is arbitrary
82  A_Star = 4,
83  /// \brief Representation is Montgomery
84  A_Montgomery = 8
85  };
86
87  const ECP::Field& field;
88  const ECP::FieldElement &a, &b;
89  ECP::Point &R;
90
91  Alpha m_alpha;
92 };
93
94 #define X p.x
95 #define Y p.y
96 #define Z p.z
97
98 #define X1 p.x
99 #define Y1 p.y
100 #define Z1 p.z
101
102 #define X2 q.x
103 #define Y2 q.y
104 #define Z2 q.z
105
106 #define X3 r.x
107 #define Y3 r.y
108 #define Z3 r.z
109
111  const ECP::FieldElement &a, const ECP::FieldElement &b, ECP::Point &r)
112  : field(field), a(a), b(b), R(r), m_alpha(static_cast<Alpha>(0))
113 {
114  if (field.IsMontgomeryRepresentation())
115  {
116  m_alpha = A_Montgomery;
117  }
118  else
119  {
120  if (a == 0)
121  {
122  m_alpha = A_0;
123  }
124  else if (a == -3 || (a - field.GetModulus()) == -3)
125  {
126  m_alpha = A_3;
127  }
128  else
129  {
130  m_alpha = A_Star;
131  }
132  }
133 }
134
135 ECP::Point AdditionFunction::operator()(const ECP::Point& P) const
136 {
137  if (m_alpha == A_3)
138  {
139  // Gyrations attempt to maintain constant-timeness
140  // We need either (P.x, P.y, 1) or (0, 1, 0).
141  const Integer x = P.x * IdentityToInteger(!P.identity);
142  const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
143  const Integer z = 1 * IdentityToInteger(!P.identity);
144
145  ProjectivePoint p(x, y, z), r;
146
147  ECP::FieldElement t0 = field.Square(X);
148  ECP::FieldElement t1 = field.Square(Y);
149  ECP::FieldElement t2 = field.Square(Z);
150  ECP::FieldElement t3 = field.Multiply(X, Y);
152  Z3 = field.Multiply(X, Z);
154  Y3 = field.Multiply(b, t2);
155  Y3 = field.Subtract(Y3, Z3);
158  X3 = field.Subtract(t1, Y3);
160  Y3 = field.Multiply(X3, Y3);
161  X3 = field.Multiply(X3, t3);
164  Z3 = field.Multiply(b, Z3);
165  Z3 = field.Subtract(Z3, t2);
166  Z3 = field.Subtract(Z3, t0);
171  t0 = field.Subtract(t0, t2);
172  t0 = field.Multiply(t0, Z3);
174  t0 = field.Multiply(Y, Z);
176  Z3 = field.Multiply(t0, Z3);
177  X3 = field.Subtract(X3, Z3);
178  Z3 = field.Multiply(t0, t1);
181
182  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
183  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
184
185  // More gyrations
186  R.x = X3*Z3.NotZero();
187  R.y = Y3*Z3.NotZero();
188  R.identity = Z3.IsZero();
189
190  return R;
191  }
192  else if (m_alpha == A_0)
193  {
194  // Gyrations attempt to maintain constant-timeness
195  // We need either (P.x, P.y, 1) or (0, 1, 0).
196  const Integer x = P.x * IdentityToInteger(!P.identity);
197  const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
198  const Integer z = 1 * IdentityToInteger(!P.identity);
199
200  ProjectivePoint p(x, y, z), r;
201  const ECP::FieldElement b3 = field.Multiply(b, 3);
202
203  ECP::FieldElement t0 = field.Square(Y);
207  ECP::FieldElement t1 = field.Add(Y, Z);
208  ECP::FieldElement t2 = field.Square(Z);
209  t2 = field.Multiply(b3, t2);
210  X3 = field.Multiply(t2, Z3);
212  Z3 = field.Multiply(t1, Z3);
215  t0 = field.Subtract(t0, t2);
216  Y3 = field.Multiply(t0, Y3);
218  t1 = field.Multiply(X, Y);
219  X3 = field.Multiply(t0, t1);
221
222  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
223  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
224
225  // More gyrations
226  R.x = X3*Z3.NotZero();
227  R.y = Y3*Z3.NotZero();
228  R.identity = Z3.IsZero();
229
230  return R;
231  }
232 #if 0
233  // Code path disabled at the moment due to https://github.com/weidai11/cryptopp/issues/878
234  else if (m_alpha == A_Star)
235  {
236  // Gyrations attempt to maintain constant-timeness
237  // We need either (P.x, P.y, 1) or (0, 1, 0).
238  const Integer x = P.x * IdentityToInteger(!P.identity);
239  const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
240  const Integer z = 1 * IdentityToInteger(!P.identity);
241
242  ProjectivePoint p(x, y, z), r;
243  const ECP::FieldElement b3 = field.Multiply(b, 3);
244
245  ECP::FieldElement t0 = field.Square(Y);
249  ECP::FieldElement t1 = field.Add(Y, Z);
250  ECP::FieldElement t2 = field.Square(Z);
251  t2 = field.Multiply(b3, t2);
252  X3 = field.Multiply(t2, Z3);
254  Z3 = field.Multiply(t1, Z3);
257  t0 = field.Subtract(t0, t2);
258  Y3 = field.Multiply(t0, Y3);
260  t1 = field.Multiply(X, Y);
261  X3 = field.Multiply(t0, t1);
263
264  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
265  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
266
267  // More gyrations
268  R.x = X3*Z3.NotZero();
269  R.y = Y3*Z3.NotZero();
270  R.identity = Z3.IsZero();
271
272  return R;
273  }
274 #endif
275  else // A_Montgomery
276  {
277  // More gyrations
278  bool identity = !!(P.identity + (P.y == field.Identity()));
279
280  ECP::FieldElement t = field.Square(P.x);
282  t = field.Divide(t, field.Double(P.y));
283  ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);
284  R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
285  R.x.swap(x);
286
287  // More gyrations
288  R.x *= IdentityToInteger(!identity);
289  R.y *= IdentityToInteger(!identity);
290  R.identity = identity;
291
292  return R;
293  }
294 }
295
296 ECP::Point AdditionFunction::operator()(const ECP::Point& P, const ECP::Point& Q) const
297 {
298  if (m_alpha == A_3)
299  {
300  // Gyrations attempt to maintain constant-timeness
301  // We need either (P.x, P.y, 1) or (0, 1, 0).
302  const Integer x1 = P.x * IdentityToInteger(!P.identity);
303  const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
304  const Integer z1 = 1 * IdentityToInteger(!P.identity);
305
306  const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
307  const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
308  const Integer z2 = 1 * IdentityToInteger(!Q.identity);
309
310  ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
311
312  ECP::FieldElement t0 = field.Multiply(X1, X2);
313  ECP::FieldElement t1 = field.Multiply(Y1, Y2);
314  ECP::FieldElement t2 = field.Multiply(Z1, Z2);
315  ECP::FieldElement t3 = field.Add(X1, Y1);
316  ECP::FieldElement t4 = field.Add(X2, Y2);
317  t3 = field.Multiply(t3, t4);
319  t3 = field.Subtract(t3, t4);
322  t4 = field.Multiply(t4, X3);
324  t4 = field.Subtract(t4, X3);
327  X3 = field.Multiply(X3, Y3);
329  Y3 = field.Subtract(X3, Y3);
330  Z3 = field.Multiply(b, t2);
331  X3 = field.Subtract(Y3, Z3);
334  Z3 = field.Subtract(t1, X3);
336  Y3 = field.Multiply(b, Y3);
339  Y3 = field.Subtract(Y3, t2);
340  Y3 = field.Subtract(Y3, t0);
345  t0 = field.Subtract(t0, t2);
346  t1 = field.Multiply(t4, Y3);
347  t2 = field.Multiply(t0, Y3);
348  Y3 = field.Multiply(X3, Z3);
350  X3 = field.Multiply(t3, X3);
351  X3 = field.Subtract(X3, t1);
352  Z3 = field.Multiply(t4, Z3);
353  t1 = field.Multiply(t3, t0);
355
356  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
357  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
358
359  // More gyrations
360  R.x = X3*Z3.NotZero();
361  R.y = Y3*Z3.NotZero();
362  R.identity = Z3.IsZero();
363
364  return R;
365  }
366  else if (m_alpha == A_0)
367  {
368  // Gyrations attempt to maintain constant-timeness
369  // We need either (P.x, P.y, 1) or (0, 1, 0).
370  const Integer x1 = P.x * IdentityToInteger(!P.identity);
371  const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
372  const Integer z1 = 1 * IdentityToInteger(!P.identity);
373
374  const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
375  const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
376  const Integer z2 = 1 * IdentityToInteger(!Q.identity);
377
378  ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
379  const ECP::FieldElement b3 = field.Multiply(b, 3);
380
381  ECP::FieldElement t0 = field.Square(Y);
385  ECP::FieldElement t1 = field.Add(Y, Z);
386  ECP::FieldElement t2 = field.Square(Z);
387  t2 = field.Multiply(b3, t2);
388  X3 = field.Multiply(t2, Z3);
390  Z3 = field.Multiply(t1, Z3);
393  t0 = field.Subtract(t0, t2);
394  Y3 = field.Multiply(t0, Y3);
396  t1 = field.Multiply(X, Y);
397  X3 = field.Multiply(t0, t1);
399
400  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
401  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
402
403  // More gyrations
404  R.x = X3*Z3.NotZero();
405  R.y = Y3*Z3.NotZero();
406  R.identity = Z3.IsZero();
407
408  return R;
409  }
410 #if 0
411  // Code path disabled at the moment due to https://github.com/weidai11/cryptopp/issues/878
412  else if (m_alpha == A_Star)
413  {
414  // Gyrations attempt to maintain constant-timeness
415  // We need either (P.x, P.y, 1) or (0, 1, 0).
416  const Integer x1 = P.x * IdentityToInteger(!P.identity);
417  const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
418  const Integer z1 = 1 * IdentityToInteger(!P.identity);
419
420  const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
421  const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
422  const Integer z2 = 1 * IdentityToInteger(!Q.identity);
423
424  ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
425  const ECP::FieldElement b3 = field.Multiply(b, 3);
426
427  ECP::FieldElement t0 = field.Multiply(X1, X2);
428  ECP::FieldElement t1 = field.Multiply(Y1, Y2);
429  ECP::FieldElement t2 = field.Multiply(Z1, Z2);
430  ECP::FieldElement t3 = field.Add(X1, Y1);
431  ECP::FieldElement t4 = field.Add(X2, Y2);
432  t3 = field.Multiply(t3, t4);
434  t3 = field.Subtract(t3, t4);
436  ECP::FieldElement t5 = field.Add(X2, Z2);
437  t4 = field.Multiply(t4, t5);
439  t4 = field.Subtract(t4, t5);
442  t5 = field.Multiply(t5, X3);
444  t5 = field.Subtract(t5, X3);
445  Z3 = field.Multiply(a, t4);
446  X3 = field.Multiply(b3, t2);
448  X3 = field.Subtract(t1, Z3);
450  Y3 = field.Multiply(X3, Z3);
453  t2 = field.Multiply(a, t2);
454  t4 = field.Multiply(b3, t4);
456  t2 = field.Subtract(t0, t2);
457  t2 = field.Multiply(a, t2);
459  t0 = field.Multiply(t1, t4);
461  t0 = field.Multiply(t5, t4);
462  X3 = field.Multiply(t3, X3);
463  X3 = field.Subtract(X3, t0);
464  t0 = field.Multiply(t3, t1);
465  Z3 = field.Multiply(t5, Z3);
467
468  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
469  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
470
471  // More gyrations
472  R.x = X3*Z3.NotZero();
473  R.y = Y3*Z3.NotZero();
474  R.identity = Z3.IsZero();
475
476  return R;
477  }
478 #endif
479  else // A_Montgomery
480  {
481  // More gyrations
482  bool return_Q = P.identity;
483  bool return_P = Q.identity;
484  bool double_P = field.Equal(P.x, Q.x) && field.Equal(P.y, Q.y);
485  bool identity = field.Equal(P.x, Q.x) && !field.Equal(P.y, Q.y);
486
487  // This code taken from Double(P) for below
488  identity = !!((double_P * (P.identity + (P.y == field.Identity()))) + identity);
489
490  ECP::Point S = R;
491  if (double_P)
492  {
493  // This code taken from Double(P)
494  ECP::FieldElement t = field.Square(P.x);
496  t = field.Divide(t, field.Double(P.y));
497  ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);
498  R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
499  R.x.swap(x);
500  }
501  else
502  {
504  ECP::FieldElement t = field.Subtract(Q.y, P.y);
505  t = field.Divide(t, field.Subtract(Q.x, P.x));
506  ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), Q.x);
507  R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
508  R.x.swap(x);
509  }
510
511  // More gyrations
512  R.x = R.x * IdentityToInteger(!identity);
513  R.y = R.y * IdentityToInteger(!identity);
514  R.identity = identity;
515
516  if (return_Q)
517  return (R = S), Q;
518  else if (return_P)
519  return (R = S), P;
520  else
521  return (S = R), R;
522  }
523 }
524
525 #undef X
526 #undef Y
527 #undef Z
528
529 #undef X1
530 #undef Y1
531 #undef Z1
532
533 #undef X2
534 #undef Y2
535 #undef Z2
536
537 #undef X3
538 #undef Y3
539 #undef Z3
540
541 ANONYMOUS_NAMESPACE_END
542
543 NAMESPACE_BEGIN(CryptoPP)
544
545 ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation)
546 {
547  if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
548  {
549  m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus()));
550  m_a = GetField().ConvertIn(ecp.m_a);
551  m_b = GetField().ConvertIn(ecp.m_b);
552  }
553  else
554  operator=(ecp);
555 }
556
558  : m_fieldPtr(new Field(bt))
559 {
560  BERSequenceDecoder seq(bt);
561  GetField().BERDecodeElement(seq, m_a);
562  GetField().BERDecodeElement(seq, m_b);
563  // skip optional seed
564  if (!seq.EndReached())
565  {
566  SecByteBlock seed;
567  unsigned int unused;
568  BERDecodeBitString(seq, seed, unused);
569  }
570  seq.MessageEnd();
571 }
572
574 {
575  GetField().DEREncode(bt);
576  DERSequenceEncoder seq(bt);
577  GetField().DEREncodeElement(seq, m_a);
578  GetField().DEREncodeElement(seq, m_b);
579  seq.MessageEnd();
580 }
581
582 bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
583 {
584  StringStore store(encodedPoint, encodedPointLen);
585  return DecodePoint(P, store, encodedPointLen);
586 }
587
588 bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
589 {
590  byte type;
591  if (encodedPointLen < 1 || !bt.Get(type))
592  return false;
593
594  switch (type)
595  {
596  case 0:
597  P.identity = true;
598  return true;
599  case 2:
600  case 3:
601  {
602  if (encodedPointLen != EncodedPointSize(true))
603  return false;
604
605  Integer p = FieldSize();
606
607  P.identity = false;
608  P.x.Decode(bt, GetField().MaxElementByteLength());
609  P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
610
611  if (Jacobi(P.y, p) !=1)
612  return false;
613
614  P.y = ModularSquareRoot(P.y, p);
615
616  if ((type & 1) != P.y.GetBit(0))
617  P.y = p-P.y;
618
619  return true;
620  }
621  case 4:
622  {
623  if (encodedPointLen != EncodedPointSize(false))
624  return false;
625
626  unsigned int len = GetField().MaxElementByteLength();
627  P.identity = false;
628  P.x.Decode(bt, len);
629  P.y.Decode(bt, len);
630  return true;
631  }
632  default:
633  return false;
634  }
635 }
636
637 void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
638 {
639  if (P.identity)
640  NullStore().TransferTo(bt, EncodedPointSize(compressed));
641  else if (compressed)
642  {
643  bt.Put((byte)(2U + P.y.GetBit(0)));
644  P.x.Encode(bt, GetField().MaxElementByteLength());
645  }
646  else
647  {
648  unsigned int len = GetField().MaxElementByteLength();
649  bt.Put(4U); // uncompressed
650  P.x.Encode(bt, len);
651  P.y.Encode(bt, len);
652  }
653 }
654
655 void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
656 {
657  ArraySink sink(encodedPoint, EncodedPointSize(compressed));
658  EncodePoint(sink, P, compressed);
659  CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
660 }
661
663 {
664  SecByteBlock str;
665  BERDecodeOctetString(bt, str);
666  Point P;
667  if (!DecodePoint(P, str, str.size()))
668  BERDecodeError();
669  return P;
670 }
671
672 void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
673 {
674  SecByteBlock str(EncodedPointSize(compressed));
675  EncodePoint(str, P, compressed);
676  DEREncodeOctetString(bt, str);
677 }
678
679 bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
680 {
681  Integer p = FieldSize();
682
683  bool pass = p.IsOdd();
684  pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
685
686  if (level >= 1)
687  pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
688
689  if (level >= 2)
690  pass = pass && VerifyPrime(rng, p);
691
692  return pass;
693 }
694
695 bool ECP::VerifyPoint(const Point &P) const
696 {
697  const FieldElement &x = P.x, &y = P.y;
698  Integer p = FieldSize();
699  return P.identity ||
700  (!x.IsNegative() && x<p && !y.IsNegative() && y<p
701  && !(((x*x+m_a)*x+m_b-y*y)%p));
702 }
703
704 bool ECP::Equal(const Point &P, const Point &Q) const
705 {
706  if (P.identity && Q.identity)
707  return true;
708
709  if (P.identity && !Q.identity)
710  return false;
711
712  if (!P.identity && Q.identity)
713  return false;
714
715  return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
716 }
717
718 const ECP::Point& ECP::Identity() const
719 {
720 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
721  return g_identity;
722 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
723  static const ECP::Point g_identity;
724  return g_identity;
725 #else
726  return Singleton<Point>().Ref();
727 #endif
728 }
729
730 const ECP::Point& ECP::Inverse(const Point &P) const
731 {
732  if (P.identity)
733  return P;
734  else
735  {
736  m_R.identity = false;
737  m_R.x = P.x;
738  m_R.y = GetField().Inverse(P.y);
739  return m_R;
740  }
741 }
742
743 const ECP::Point& ECP::Add(const Point &P, const Point &Q) const
744 {
746  return (m_R = add(P, Q));
747 }
748
749 const ECP::Point& ECP::Double(const Point &P) const
750 {
753 }
754
755 template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)
756 {
757  size_t n = end-begin;
758  if (n == 1)
759  *begin = ring.MultiplicativeInverse(*begin);
760  else if (n > 1)
761  {
762  std::vector<T> vec((n+1)/2);
763  unsigned int i;
764  Iterator it;
765
766  for (i=0, it=begin; i<n/2; i++, it+=2)
767  vec[i] = ring.Multiply(*it, *(it+1));
768  if (n%2 == 1)
769  vec[n/2] = *it;
770
771  ParallelInvert(ring, vec.begin(), vec.end());
772
773  for (i=0, it=begin; i<n/2; i++, it+=2)
774  {
775  if (!vec[i])
776  {
777  *it = ring.MultiplicativeInverse(*it);
778  *(it+1) = ring.MultiplicativeInverse(*(it+1));
779  }
780  else
781  {
782  std::swap(*it, *(it+1));
783  *it = ring.Multiply(*it, vec[i]);
784  *(it+1) = ring.Multiply(*(it+1), vec[i]);
785  }
786  }
787  if (n%2 == 1)
788  *it = vec[n/2];
789  }
790 }
791
793 {
794 public:
795  ProjectiveDoubling(const ModularArithmetic &m_mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q)
796  : mr(m_mr)
797  {
798  CRYPTOPP_UNUSED(m_b);
799  if (Q.identity)
800  {
801  sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
802  aZ4 = P.z = mr.Identity();
803  }
804  else
805  {
806  P.x = Q.x;
807  P.y = Q.y;
808  sixteenY4 = P.z = mr.MultiplicativeIdentity();
809  aZ4 = m_a;
810  }
811  }
812
813  void Double()
814  {
815  twoY = mr.Double(P.y);
816  P.z = mr.Multiply(P.z, twoY);
817  fourY2 = mr.Square(twoY);
818  S = mr.Multiply(fourY2, P.x);
819  aZ4 = mr.Multiply(aZ4, sixteenY4);
820  M = mr.Square(P.x);
822  P.x = mr.Square(M);
823  mr.Reduce(P.x, S);
824  mr.Reduce(P.x, S);
825  mr.Reduce(S, P.x);
826  P.y = mr.Multiply(M, S);
827  sixteenY4 = mr.Square(fourY2);
828  mr.Reduce(P.y, mr.Half(sixteenY4));
829  }
830
831  const ModularArithmetic &mr;
832  ProjectivePoint P;
833  Integer sixteenY4, aZ4, twoY, fourY2, S, M;
834 };
835
836 struct ZIterator
837 {
838  ZIterator() {}
839  ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
840  Integer& operator*() {return it->z;}
841  int operator-(ZIterator it2) {return int(it-it2.it);}
842  ZIterator operator+(int i) {return ZIterator(it+i);}
843  ZIterator& operator+=(int i) {it+=i; return *this;}
844  std::vector<ProjectivePoint>::iterator it;
845 };
846
847 ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
848 {
849  Element result;
850  if (k.BitCount() <= 5)
852  else
853  ECP::SimultaneousMultiply(&result, P, &k, 1);
854  return result;
855 }
856
857 void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
858 {
859  if (!GetField().IsMontgomeryRepresentation())
860  {
861  ECP ecpmr(*this, true);
862  const ModularArithmetic &mr = ecpmr.GetField();
863  ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
864  for (unsigned int i=0; i<expCount; i++)
865  results[i] = FromMontgomery(mr, results[i]);
866  return;
867  }
868
869  ProjectiveDoubling rd(GetField(), m_a, m_b, P);
870  std::vector<ProjectivePoint> bases;
871  std::vector<WindowSlider> exponents;
872  exponents.reserve(expCount);
873  std::vector<std::vector<word32> > baseIndices(expCount);
874  std::vector<std::vector<bool> > negateBase(expCount);
875  std::vector<std::vector<word32> > exponentWindows(expCount);
876  unsigned int i;
877
878  for (i=0; i<expCount; i++)
879  {
880  CRYPTOPP_ASSERT(expBegin->NotNegative());
881  exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
882  exponents[i].FindNextWindow();
883  }
884
885  unsigned int expBitPosition = 0;
886  bool notDone = true;
887
888  while (notDone)
889  {
890  notDone = false;
892  for (i=0; i<expCount; i++)
893  {
894  if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
895  {
897  {
898  bases.push_back(rd.P);
900  }
901
902  exponentWindows[i].push_back(exponents[i].expWindow);
903  baseIndices[i].push_back((word32)bases.size()-1);
904  negateBase[i].push_back(exponents[i].negateNext);
905
906  exponents[i].FindNextWindow();
907  }
908  notDone = notDone || !exponents[i].finished;
909  }
910
911  if (notDone)
912  {
913  rd.Double();
914  expBitPosition++;
915  }
916  }
917
918  // convert from projective to affine coordinates
919  ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
920  for (i=0; i<bases.size(); i++)
921  {
922  if (bases[i].z.NotZero())
923  {
924  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
925  bases[i].z = GetField().Square(bases[i].z);
926  bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
927  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
928  }
929  }
930
932  for (i=0; i<expCount; i++)
933  {
935  for (unsigned int j=0; j<baseIndices[i].size(); j++)
936  {
937  ProjectivePoint &base = bases[baseIndices[i][j]];
938  if (base.z.IsZero())
940  else
941  {
944  if (negateBase[i][j])
946  else
948  }
949  finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
950  }
952  }
953 }
954
955 ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
956 {
957  if (!GetField().IsMontgomeryRepresentation())
958  {
959  ECP ecpmr(*this, true);
960  const ModularArithmetic &mr = ecpmr.GetField();
961  return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
962  }
963  else
964  return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
965 }
966
967 NAMESPACE_END
968
969 #endif
DEREncodeOctetString
CRYPTOPP_DLL size_t CRYPTOPP_API DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
Definition: asn.cpp:107
ModularArithmetic::BERDecodeElement
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
Definition: integer.cpp:4513
Singleton::Ref
const T & Ref(...) const
Return a reference to the inner Singleton object.
Definition: misc.h:325
ModularArithmetic::Subtract
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Definition: integer.cpp:4569
ecp.h
Classes for Elliptic Curves over prime fields.
ModularArithmetic::MultiplicativeInverse
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition: modarith.h:210
ECP::DEREncode
void DEREncode(BufferedTransformation &bt) const
DER Encode.
Definition: ecp.cpp:573
ECP::BERDecodePoint
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
Definition: ecp.cpp:662
nbtheory.h
Classes and functions for number theoretic operations.
swap
void swap(::SecBlock< T, A > &a, ::SecBlock< T, A > &b)
Swap two SecBlocks.
Definition: secblock.h:1153
AbstractRing::Multiply
virtual const Element & Multiply(const Element &a, const Element &b) const =0
Multiplies elements in the group.
ModularArithmetic::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Definition: integer.cpp:4500
ECP
Elliptic Curve over GF(p), where p is prime.
Definition: ecp.h:26
ModularArithmetic::Inverse
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
Definition: integer.cpp:4603
ECP::Double
const Point & Double(const Point &P) const
Doubles an element in the group.
Definition: ecp.cpp:749
StringStore
String-based implementation of Store interface.
Definition: filters.h:1258
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:556
Integer::One
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition: integer.cpp:4868
Integer::POSITIVE
@ POSITIVE
the value is positive or 0
Definition: integer.h:75
ArraySink::TotalPutLength
lword TotalPutLength()
Provides the number of bytes written to the Sink.
Definition: filters.h:1222
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
Definition: ecp.cpp:955
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1630
BERDecodeBitString
CRYPTOPP_DLL size_t CRYPTOPP_API BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
Definition: asn.cpp:246
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:43
SecByteBlock
SecBlock<byte> typedef.
Definition: secblock.h:1091
BERGeneralDecoder::MessageEnd
void MessageEnd()
Signals the end of messages to the object.
Definition: asn.cpp:553
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
BufferedTransformation::Put
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1652
VerifyPrime
CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Definition: nbtheory.cpp:247
ModularArithmetic::ConvertOut
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
Definition: modarith.h:123
ProjectiveDoubling
Definition: ecp.cpp:792
Singleton
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:304
modarith.h
Class file for performing modular arithmetic.
ModularArithmetic::Multiply
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: modarith.h:190
pch.h
ModularArithmetic::MaxElementByteLength
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
Definition: modarith.h:248
filters.h
Implementation of BufferedTransformation's attachment interface.
ModularArithmetic::Square
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: modarith.h:197
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1413
ECP::EncodedPointSize
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
Definition: ecp.h:90
BERDecodeError
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:104
ModularArithmetic::GetModulus
const Integer & GetModulus() const
Retrieves the modulus.
Definition: modarith.h:99
ZIterator
Definition: ecp.cpp:836
ECP::SimultaneousMultiply
void SimultaneousMultiply(Point *results, const Point &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
Definition: ecp.cpp:857
ModularArithmetic::Identity
const Integer & Identity() const
Provides the Identity element.
Definition: modarith.h:140
const Point & Add(const Point &P, const Point &Q) const
Definition: ecp.cpp:743
ModularArithmetic::DEREncodeElement
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Definition: integer.cpp:4508
ArraySink
Copy input to a memory buffer.
Definition: filters.h:1199
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition: algebra.cpp:97
ECP::DEREncodePoint
void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
DER Encodes an elliptic curve point.
Definition: ecp.cpp:672
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:354
NullStore
Empty store.
Definition: filters.h:1320
AbstractRing::MultiplicativeInverse
virtual const Element & MultiplicativeInverse(const Element &a) const =0
Calculate the multiplicative inverse of an element in the group.
asn.h
Classes and functions for working with ANS.1 objects.
ECP::VerifyPoint
bool VerifyPoint(const Point &P) const
Verifies points on elliptic curve.
Definition: ecp.cpp:695
BufferedTransformation::TransferTo
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:1966
ECPPoint
Elliptical Curve Point over GF(p), where p is prime.
Definition: ecpoint.h:20
DERGeneralEncoder::MessageEnd
void MessageEnd()
Signals the end of messages to the object.
Definition: asn.cpp:624
ECP::Equal
bool Equal(const Point &P, const Point &Q) const
Compare two points.
Definition: ecp.cpp:704
Integer::NotNegative
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:342
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3348
ECP::DecodePoint
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
Definition: ecp.cpp:588
SecBlock::size
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:829
Jacobi
CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Definition: nbtheory.cpp:792
ModularArithmetic::Half
const Integer & Half(const Integer &a) const
Divides an element by 2.
Definition: integer.cpp:4518
BufferedTransformation::Get
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:528
ModularArithmetic::ConvertIn
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition: modarith.h:115
ModularArithmetic::MultiplicativeIdentity
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition: modarith.h:182
CryptoPP
Crypto++ library namespace.
WindowSlider
Definition: algebra.cpp:206
AbstractGroup::SimultaneousMultiply
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
Definition: algebra.cpp:256
Integer::IsNegative
bool IsNegative() const
Determines if the Integer is negative.
Definition: integer.h:339
BERDecodeOctetString
CRYPTOPP_DLL size_t CRYPTOPP_API BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
Definition: asn.cpp:120
AbstractRing
Abstract ring.
Definition: algebra.h:118
ModularArithmetic::Double
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
Definition: modarith.h:176
ModularArithmetic::Reduce
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4586
MontgomeryRepresentation
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:295
ModularArithmetic::Equal
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
Definition: modarith.h:135
ModularArithmetic::Divide
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Definition: modarith.h:218
ModularArithmetic::IsMontgomeryRepresentation
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.
Definition: modarith.h:108
ECP::ECP
ECP()
Construct an ECP.
Definition: ecp.h:36
ECP::ScalarMultiply
Point ScalarMultiply(const Point &P, const Integer &k) const
Performs a scalar multiplication.
Definition: ecp.cpp:847
ECP::Inverse
const Point & Inverse(const Point &P) const
Inverts the element in the group.
Definition: ecp.cpp:730
BERGeneralDecoder::EndReached
bool EndReached() const
Determine end of stream.
Definition: asn.cpp:527
ECP::EncodePoint
void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
Encodes an elliptic curve point.
Definition: ecp.cpp:655
integer.h
Multiple precision integer with arithmetic operations.
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:524