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>
61 struct AdditionFunction
62 {
63  explicit AdditionFunction(const ECP::Field& field,
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;
68  // Add(P, Q)
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 
110 AdditionFunction::AdditionFunction(const ECP::Field& field,
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);
151  t3 = field.Add(t3, t3);
152  Z3 = field.Multiply(X, Z);
153  Z3 = field.Add(Z3, Z3);
154  Y3 = field.Multiply(b, t2);
155  Y3 = field.Subtract(Y3, Z3);
156  X3 = field.Add(Y3, Y3);
157  Y3 = field.Add(X3, Y3);
158  X3 = field.Subtract(t1, Y3);
159  Y3 = field.Add(t1, Y3);
160  Y3 = field.Multiply(X3, Y3);
161  X3 = field.Multiply(X3, t3);
162  t3 = field.Add(t2, t2);
163  t2 = field.Add(t2, t3);
164  Z3 = field.Multiply(b, Z3);
165  Z3 = field.Subtract(Z3, t2);
166  Z3 = field.Subtract(Z3, t0);
167  t3 = field.Add(Z3, Z3);
168  Z3 = field.Add(Z3, t3);
169  t3 = field.Add(t0, t0);
170  t0 = field.Add(t3, t0);
171  t0 = field.Subtract(t0, t2);
172  t0 = field.Multiply(t0, Z3);
173  Y3 = field.Add(Y3, t0);
174  t0 = field.Multiply(Y, Z);
175  t0 = field.Add(t0, t0);
176  Z3 = field.Multiply(t0, Z3);
177  X3 = field.Subtract(X3, Z3);
178  Z3 = field.Multiply(t0, t1);
179  Z3 = field.Add(Z3, Z3);
180  Z3 = field.Add(Z3, Z3);
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  const ECP::FieldElement b3 = field.Multiply(b, 3);
195 
196  // Gyrations attempt to maintain constant-timeness
197  // We need either (P.x, P.y, 1) or (0, 1, 0).
198  const Integer x = P.x * IdentityToInteger(!P.identity);
199  const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
200  const Integer z = 1 * IdentityToInteger(!P.identity);
201 
202  ProjectivePoint p(x, y, z), r;
203 
204  ECP::FieldElement t0 = field.Square(Y);
205  Z3 = field.Add(t0, t0);
206  Z3 = field.Add(Z3, Z3);
207  Z3 = field.Add(Z3, Z3);
208  ECP::FieldElement t1 = field.Add(Y, Z);
209  ECP::FieldElement t2 = field.Square(Z);
210  t2 = field.Multiply(b3, t2);
211  X3 = field.Multiply(t2, Z3);
212  Y3 = field.Add(t0, t2);
213  Z3 = field.Multiply(t1, Z3);
214  t1 = field.Add(t2, t2);
215  t2 = field.Add(t1, t2);
216  t0 = field.Subtract(t0, t2);
217  Y3 = field.Multiply(t0, Y3);
218  Y3 = field.Add(X3, Y3);
219  t1 = field.Multiply(X, Y);
220  X3 = field.Multiply(t0, t1);
221  X3 = field.Add(X3, X3);
222 
223  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
224  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
225 
226  // More gyrations
227  R.x = X3*Z3.NotZero();
228  R.y = Y3*Z3.NotZero();
229  R.identity = Z3.IsZero();
230 
231  return R;
232  }
233  else if (m_alpha == A_Star)
234  {
235  const ECP::FieldElement b3 = field.Multiply(b, 3);
236 
237  // Gyrations attempt to maintain constant-timeness
238  // We need either (P.x, P.y, 1) or (0, 1, 0).
239  const Integer x = P.x * IdentityToInteger(!P.identity);
240  const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
241  const Integer z = 1 * IdentityToInteger(!P.identity);
242 
243  ProjectivePoint p(x, y, z), r;
244 
245  ECP::FieldElement t0 = field.Square(Y);
246  Z3 = field.Add(t0, t0);
247  Z3 = field.Add(Z3, Z3);
248  Z3 = field.Add(Z3, Z3);
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);
253  Y3 = field.Add(t0, t2);
254  Z3 = field.Multiply(t1, Z3);
255  t1 = field.Add(t2, t2);
256  t2 = field.Add(t1, t2);
257  t0 = field.Subtract(t0, t2);
258  Y3 = field.Multiply(t0, Y3);
259  Y3 = field.Add(X3, Y3);
260  t1 = field.Multiply(X, Y);
261  X3 = field.Multiply(t0, t1);
262  X3 = field.Add(X3, X3);
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  else // A_Montgomery
275  {
276  // More gyrations
277  bool identity = !!(P.identity + (P.y == field.Identity()));
278 
279  ECP::FieldElement t = field.Square(P.x);
280  t = field.Add(field.Add(field.Double(t), t), a);
281  t = field.Divide(t, field.Double(P.y));
282  ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);
283  R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
284  R.x.swap(x);
285 
286  // More gyrations
287  R.x *= IdentityToInteger(!identity);
288  R.y *= IdentityToInteger(!identity);
289  R.identity = identity;
290 
291  return R;
292  }
293 }
294 
295 ECP::Point AdditionFunction::operator()(const ECP::Point& P, const ECP::Point& Q) const
296 {
297  if (m_alpha == A_3)
298  {
299  // Gyrations attempt to maintain constant-timeness
300  // We need either (P.x, P.y, 1) or (0, 1, 0).
301  const Integer x1 = P.x * IdentityToInteger(!P.identity);
302  const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
303  const Integer z1 = 1 * IdentityToInteger(!P.identity);
304 
305  const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
306  const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
307  const Integer z2 = 1 * IdentityToInteger(!Q.identity);
308 
309  ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
310 
311  ECP::FieldElement t0 = field.Multiply(X1, X2);
312  ECP::FieldElement t1 = field.Multiply(Y1, Y2);
313  ECP::FieldElement t2 = field.Multiply(Z1, Z2);
314  ECP::FieldElement t3 = field.Add(X1, Y1);
315  ECP::FieldElement t4 = field.Add(X2, Y2);
316  t3 = field.Multiply(t3, t4);
317  t4 = field.Add(t0, t1);
318  t3 = field.Subtract(t3, t4);
319  t4 = field.Add(Y1, Z1);
320  X3 = field.Add(Y2, Z2);
321  t4 = field.Multiply(t4, X3);
322  X3 = field.Add(t1, t2);
323  t4 = field.Subtract(t4, X3);
324  X3 = field.Add(X1, Z1);
325  Y3 = field.Add(X2, Z2);
326  X3 = field.Multiply(X3, Y3);
327  Y3 = field.Add(t0, t2);
328  Y3 = field.Subtract(X3, Y3);
329  Z3 = field.Multiply(b, t2);
330  X3 = field.Subtract(Y3, Z3);
331  Z3 = field.Add(X3, X3);
332  X3 = field.Add(X3, Z3);
333  Z3 = field.Subtract(t1, X3);
334  X3 = field.Add(t1, X3);
335  Y3 = field.Multiply(b, Y3);
336  t1 = field.Add(t2, t2);
337  t2 = field.Add(t1, t2);
338  Y3 = field.Subtract(Y3, t2);
339  Y3 = field.Subtract(Y3, t0);
340  t1 = field.Add(Y3, Y3);
341  Y3 = field.Add(t1, Y3);
342  t1 = field.Add(t0, t0);
343  t0 = field.Add(t1, t0);
344  t0 = field.Subtract(t0, t2);
345  t1 = field.Multiply(t4, Y3);
346  t2 = field.Multiply(t0, Y3);
347  Y3 = field.Multiply(X3, Z3);
348  Y3 = field.Add(Y3, t2);
349  X3 = field.Multiply(t3, X3);
350  X3 = field.Subtract(X3, t1);
351  Z3 = field.Multiply(t4, Z3);
352  t1 = field.Multiply(t3, t0);
353  Z3 = field.Add(Z3, t1);
354 
355  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
356  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
357 
358  // More gyrations
359  R.x = X3*Z3.NotZero();
360  R.y = Y3*Z3.NotZero();
361  R.identity = Z3.IsZero();
362 
363  return R;
364  }
365  else if (m_alpha == A_0)
366  {
367  const ECP::FieldElement b3 = field.Multiply(b, 3);
368 
369  // Gyrations attempt to maintain constant-timeness
370  // We need either (P.x, P.y, 1) or (0, 1, 0).
371  const Integer x1 = P.x * IdentityToInteger(!P.identity);
372  const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
373  const Integer z1 = 1 * IdentityToInteger(!P.identity);
374 
375  const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
376  const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
377  const Integer z2 = 1 * IdentityToInteger(!Q.identity);
378 
379  ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
380 
381  ECP::FieldElement t0 = field.Square(Y);
382  Z3 = field.Add(t0, t0);
383  Z3 = field.Add(Z3, Z3);
384  Z3 = field.Add(Z3, Z3);
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);
389  Y3 = field.Add(t0, t2);
390  Z3 = field.Multiply(t1, Z3);
391  t1 = field.Add(t2, t2);
392  t2 = field.Add(t1, t2);
393  t0 = field.Subtract(t0, t2);
394  Y3 = field.Multiply(t0, Y3);
395  Y3 = field.Add(X3, Y3);
396  t1 = field.Multiply(X, Y);
397  X3 = field.Multiply(t0, t1);
398  X3 = field.Add(X3, X3);
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  else if (m_alpha == A_Star)
411  {
412  const ECP::FieldElement b3 = field.Multiply(b, 3);
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 
426  ECP::FieldElement t0 = field.Multiply(X1, X2);
427  ECP::FieldElement t1 = field.Multiply(Y1, Y2);
428  ECP::FieldElement t2 = field.Multiply(Z1, Z2);
429  ECP::FieldElement t3 = field.Add(X1, Y1);
430  ECP::FieldElement t4 = field.Add(X2, Y2);
431  t3 = field.Multiply(t3, t4);
432  t4 = field.Add(t0, t1);
433  t3 = field.Subtract(t3, t4);
434  t4 = field.Add(X1, Z1);
435  ECP::FieldElement t5 = field.Add(X2, Z2);
436  t4 = field.Multiply(t4, t5);
437  t5 = field.Add(t0, t2);
438  t4 = field.Subtract(t4, t5);
439  t5 = field.Add(Y1, Z1);
440  X3 = field.Add(Y2, Z2);
441  t5 = field.Multiply(t5, X3);
442  X3 = field.Add(t1, t2);
443  t5 = field.Subtract(t5, X3);
444  Z3 = field.Multiply(a, t4);
445  X3 = field.Multiply(b3, t2);
446  Z3 = field.Add(X3, Z3);
447  X3 = field.Subtract(t1, Z3);
448  Z3 = field.Add(t1, Z3);
449  Y3 = field.Multiply(X3, Z3);
450  t1 = field.Add(t0, t0);
451  t1 = field.Add(t1, t0);
452  t2 = field.Multiply(a, t2);
453  t4 = field.Multiply(b3, t4);
454  t1 = field.Add(t1, t2);
455  t2 = field.Subtract(t0, t2);
456  t2 = field.Multiply(a, t2);
457  t4 = field.Add(t4, t2);
458  t0 = field.Multiply(t1, t4);
459  Y3 = field.Add(Y3, t0);
460  t0 = field.Multiply(t5, t4);
461  X3 = field.Multiply(t3, X3);
462  X3 = field.Subtract(X3, t0);
463  t0 = field.Multiply(t3, t1);
464  Z3 = field.Multiply(t5, Z3);
465  Z3 = field.Add(Z3, t0);
466 
467  const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);
468  X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);
469 
470  // More gyrations
471  R.x = X3*Z3.NotZero();
472  R.y = Y3*Z3.NotZero();
473  R.identity = Z3.IsZero();
474 
475  return R;
476  }
477  else // A_Montgomery
478  {
479  ECP::Point S = R;
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  if (double_P)
491  {
492  // This code taken from Double(P)
493  ECP::FieldElement t = field.Square(P.x);
494  t = field.Add(field.Add(field.Double(t), t), a);
495  t = field.Divide(t, field.Double(P.y));
496  ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);
497  R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
498  R.x.swap(x);
499  }
500  else
501  {
502  // Original Add(P,Q) code
503  ECP::FieldElement t = field.Subtract(Q.y, P.y);
504  t = field.Divide(t, field.Subtract(Q.x, P.x));
505  ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), Q.x);
506  R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
507  R.x.swap(x);
508  }
509 
510  // More gyrations
511  R.x = R.x * IdentityToInteger(!identity);
512  R.y = R.y * IdentityToInteger(!identity);
513  R.identity = identity;
514 
515  if (return_Q)
516  return (R = S), Q;
517  else if (return_P)
518  return (R = S), P;
519  else
520  return (S = R), R;
521  }
522 }
523 
524 #undef X
525 #undef Y
526 #undef Z
527 
528 #undef X1
529 #undef Y1
530 #undef Z1
531 
532 #undef X2
533 #undef Y2
534 #undef Z2
535 
536 #undef X3
537 #undef Y3
538 #undef Z3
539 
540 ANONYMOUS_NAMESPACE_END
541 
542 NAMESPACE_BEGIN(CryptoPP)
543 
544 ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation)
545 {
546  if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
547  {
548  m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus()));
549  m_a = GetField().ConvertIn(ecp.m_a);
550  m_b = GetField().ConvertIn(ecp.m_b);
551  }
552  else
553  operator=(ecp);
554 }
555 
557  : m_fieldPtr(new Field(bt))
558 {
559  BERSequenceDecoder seq(bt);
560  GetField().BERDecodeElement(seq, m_a);
561  GetField().BERDecodeElement(seq, m_b);
562  // skip optional seed
563  if (!seq.EndReached())
564  {
565  SecByteBlock seed;
566  unsigned int unused;
567  BERDecodeBitString(seq, seed, unused);
568  }
569  seq.MessageEnd();
570 }
571 
573 {
574  GetField().DEREncode(bt);
575  DERSequenceEncoder seq(bt);
576  GetField().DEREncodeElement(seq, m_a);
577  GetField().DEREncodeElement(seq, m_b);
578  seq.MessageEnd();
579 }
580 
581 bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
582 {
583  StringStore store(encodedPoint, encodedPointLen);
584  return DecodePoint(P, store, encodedPointLen);
585 }
586 
587 bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
588 {
589  byte type;
590  if (encodedPointLen < 1 || !bt.Get(type))
591  return false;
592 
593  switch (type)
594  {
595  case 0:
596  P.identity = true;
597  return true;
598  case 2:
599  case 3:
600  {
601  if (encodedPointLen != EncodedPointSize(true))
602  return false;
603 
604  Integer p = FieldSize();
605 
606  P.identity = false;
607  P.x.Decode(bt, GetField().MaxElementByteLength());
608  P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
609 
610  if (Jacobi(P.y, p) !=1)
611  return false;
612 
613  P.y = ModularSquareRoot(P.y, p);
614 
615  if ((type & 1) != P.y.GetBit(0))
616  P.y = p-P.y;
617 
618  return true;
619  }
620  case 4:
621  {
622  if (encodedPointLen != EncodedPointSize(false))
623  return false;
624 
625  unsigned int len = GetField().MaxElementByteLength();
626  P.identity = false;
627  P.x.Decode(bt, len);
628  P.y.Decode(bt, len);
629  return true;
630  }
631  default:
632  return false;
633  }
634 }
635 
636 void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
637 {
638  if (P.identity)
639  NullStore().TransferTo(bt, EncodedPointSize(compressed));
640  else if (compressed)
641  {
642  bt.Put((byte)(2U + P.y.GetBit(0)));
643  P.x.Encode(bt, GetField().MaxElementByteLength());
644  }
645  else
646  {
647  unsigned int len = GetField().MaxElementByteLength();
648  bt.Put(4U); // uncompressed
649  P.x.Encode(bt, len);
650  P.y.Encode(bt, len);
651  }
652 }
653 
654 void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
655 {
656  ArraySink sink(encodedPoint, EncodedPointSize(compressed));
657  EncodePoint(sink, P, compressed);
658  CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
659 }
660 
662 {
663  SecByteBlock str;
664  BERDecodeOctetString(bt, str);
665  Point P;
666  if (!DecodePoint(P, str, str.size()))
667  BERDecodeError();
668  return P;
669 }
670 
671 void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
672 {
673  SecByteBlock str(EncodedPointSize(compressed));
674  EncodePoint(str, P, compressed);
675  DEREncodeOctetString(bt, str);
676 }
677 
678 bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
679 {
680  Integer p = FieldSize();
681 
682  bool pass = p.IsOdd();
683  pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
684 
685  if (level >= 1)
686  pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
687 
688  if (level >= 2)
689  pass = pass && VerifyPrime(rng, p);
690 
691  return pass;
692 }
693 
694 bool ECP::VerifyPoint(const Point &P) const
695 {
696  const FieldElement &x = P.x, &y = P.y;
697  Integer p = FieldSize();
698  return P.identity ||
699  (!x.IsNegative() && x<p && !y.IsNegative() && y<p
700  && !(((x*x+m_a)*x+m_b-y*y)%p));
701 }
702 
703 bool ECP::Equal(const Point &P, const Point &Q) const
704 {
705  if (P.identity && Q.identity)
706  return true;
707 
708  if (P.identity && !Q.identity)
709  return false;
710 
711  if (!P.identity && Q.identity)
712  return false;
713 
714  return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
715 }
716 
717 const ECP::Point& ECP::Identity() const
718 {
719 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
720  return g_identity;
721 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
722  static const ECP::Point g_identity;
723  return g_identity;
724 #else
725  return Singleton<Point>().Ref();
726 #endif
727 }
728 
729 const ECP::Point& ECP::Inverse(const Point &P) const
730 {
731  if (P.identity)
732  return P;
733  else
734  {
735  m_R.identity = false;
736  m_R.x = P.x;
737  m_R.y = GetField().Inverse(P.y);
738  return m_R;
739  }
740 }
741 
742 const ECP::Point& ECP::Add(const Point &P, const Point &Q) const
743 {
744  AdditionFunction add(GetField(), m_a, m_b, m_R);
745  return (m_R = add(P, Q));
746 }
747 
748 const ECP::Point& ECP::Double(const Point &P) const
749 {
750  AdditionFunction add(GetField(), m_a, m_b, m_R);
751  return (m_R = add(P));
752 }
753 
754 template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)
755 {
756  size_t n = end-begin;
757  if (n == 1)
758  *begin = ring.MultiplicativeInverse(*begin);
759  else if (n > 1)
760  {
761  std::vector<T> vec((n+1)/2);
762  unsigned int i;
763  Iterator it;
764 
765  for (i=0, it=begin; i<n/2; i++, it+=2)
766  vec[i] = ring.Multiply(*it, *(it+1));
767  if (n%2 == 1)
768  vec[n/2] = *it;
769 
770  ParallelInvert(ring, vec.begin(), vec.end());
771 
772  for (i=0, it=begin; i<n/2; i++, it+=2)
773  {
774  if (!vec[i])
775  {
776  *it = ring.MultiplicativeInverse(*it);
777  *(it+1) = ring.MultiplicativeInverse(*(it+1));
778  }
779  else
780  {
781  std::swap(*it, *(it+1));
782  *it = ring.Multiply(*it, vec[i]);
783  *(it+1) = ring.Multiply(*(it+1), vec[i]);
784  }
785  }
786  if (n%2 == 1)
787  *it = vec[n/2];
788  }
789 }
790 
792 {
793 public:
794  ProjectiveDoubling(const ModularArithmetic &m_mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q)
795  : mr(m_mr)
796  {
797  CRYPTOPP_UNUSED(m_b);
798  if (Q.identity)
799  {
800  sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
801  aZ4 = P.z = mr.Identity();
802  }
803  else
804  {
805  P.x = Q.x;
806  P.y = Q.y;
807  sixteenY4 = P.z = mr.MultiplicativeIdentity();
808  aZ4 = m_a;
809  }
810  }
811 
812  void Double()
813  {
814  twoY = mr.Double(P.y);
815  P.z = mr.Multiply(P.z, twoY);
816  fourY2 = mr.Square(twoY);
817  S = mr.Multiply(fourY2, P.x);
818  aZ4 = mr.Multiply(aZ4, sixteenY4);
819  M = mr.Square(P.x);
820  M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
821  P.x = mr.Square(M);
822  mr.Reduce(P.x, S);
823  mr.Reduce(P.x, S);
824  mr.Reduce(S, P.x);
825  P.y = mr.Multiply(M, S);
826  sixteenY4 = mr.Square(fourY2);
827  mr.Reduce(P.y, mr.Half(sixteenY4));
828  }
829 
830  const ModularArithmetic &mr;
831  ProjectivePoint P;
832  Integer sixteenY4, aZ4, twoY, fourY2, S, M;
833 };
834 
835 struct ZIterator
836 {
837  ZIterator() {}
838  ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
839  Integer& operator*() {return it->z;}
840  int operator-(ZIterator it2) {return int(it-it2.it);}
841  ZIterator operator+(int i) {return ZIterator(it+i);}
842  ZIterator& operator+=(int i) {it+=i; return *this;}
843  std::vector<ProjectivePoint>::iterator it;
844 };
845 
846 ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
847 {
848  Element result;
849  if (k.BitCount() <= 5)
851  else
852  ECP::SimultaneousMultiply(&result, P, &k, 1);
853  return result;
854 }
855 
856 void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
857 {
858  if (!GetField().IsMontgomeryRepresentation())
859  {
860  ECP ecpmr(*this, true);
861  const ModularArithmetic &mr = ecpmr.GetField();
862  ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
863  for (unsigned int i=0; i<expCount; i++)
864  results[i] = FromMontgomery(mr, results[i]);
865  return;
866  }
867 
868  ProjectiveDoubling rd(GetField(), m_a, m_b, P);
869  std::vector<ProjectivePoint> bases;
870  std::vector<WindowSlider> exponents;
871  exponents.reserve(expCount);
872  std::vector<std::vector<word32> > baseIndices(expCount);
873  std::vector<std::vector<bool> > negateBase(expCount);
874  std::vector<std::vector<word32> > exponentWindows(expCount);
875  unsigned int i;
876 
877  for (i=0; i<expCount; i++)
878  {
879  CRYPTOPP_ASSERT(expBegin->NotNegative());
880  exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
881  exponents[i].FindNextWindow();
882  }
883 
884  unsigned int expBitPosition = 0;
885  bool notDone = true;
886 
887  while (notDone)
888  {
889  notDone = false;
890  bool baseAdded = false;
891  for (i=0; i<expCount; i++)
892  {
893  if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
894  {
895  if (!baseAdded)
896  {
897  bases.push_back(rd.P);
898  baseAdded =true;
899  }
900 
901  exponentWindows[i].push_back(exponents[i].expWindow);
902  baseIndices[i].push_back((word32)bases.size()-1);
903  negateBase[i].push_back(exponents[i].negateNext);
904 
905  exponents[i].FindNextWindow();
906  }
907  notDone = notDone || !exponents[i].finished;
908  }
909 
910  if (notDone)
911  {
912  rd.Double();
913  expBitPosition++;
914  }
915  }
916 
917  // convert from projective to affine coordinates
918  ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
919  for (i=0; i<bases.size(); i++)
920  {
921  if (bases[i].z.NotZero())
922  {
923  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
924  bases[i].z = GetField().Square(bases[i].z);
925  bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
926  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
927  }
928  }
929 
930  std::vector<BaseAndExponent<Point, Integer> > finalCascade;
931  for (i=0; i<expCount; i++)
932  {
933  finalCascade.resize(baseIndices[i].size());
934  for (unsigned int j=0; j<baseIndices[i].size(); j++)
935  {
936  ProjectivePoint &base = bases[baseIndices[i][j]];
937  if (base.z.IsZero())
938  finalCascade[j].base.identity = true;
939  else
940  {
941  finalCascade[j].base.identity = false;
942  finalCascade[j].base.x = base.x;
943  if (negateBase[i][j])
944  finalCascade[j].base.y = GetField().Inverse(base.y);
945  else
946  finalCascade[j].base.y = base.y;
947  }
948  finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
949  }
950  results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end());
951  }
952 }
953 
954 ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
955 {
956  if (!GetField().IsMontgomeryRepresentation())
957  {
958  ECP ecpmr(*this, true);
959  const ModularArithmetic &mr = ecpmr.GetField();
960  return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
961  }
962  else
963  return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
964 }
965 
966 NAMESPACE_END
967 
968 #endif
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
Definition: modarith.h:160
bool VerifyPoint(const Point &P) const
Verifies points on elliptic curve.
Definition: ecp.cpp:694
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4595
bool NotZero() const
Determines if the Integer is non-0.
Definition: integer.h:333
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
Multiplication.
Definition: integer.h:750
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
Definition: modarith.h:119
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: modarith.h:181
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Definition: modarith.h:202
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:263
Elliptical Curve Point over GF(p), where p is prime.
Definition: ecpoint.h:20
virtual const Element & Multiply(const Element &a, const Element &b) const =0
Multiplies elements in the group.
Classes for Elliptic Curves over prime fields.
Elliptic Curve over GF(p), where p is prime.
Definition: ecp.h:26
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
Definition: modarith.h:107
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
Definition: integer.cpp:4612
bool InversionIsFast() const
Determine if inversion is fast.
Definition: ecp.h:63
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Definition: integer.cpp:4578
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition: modarith.h:194
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
Definition: modarith.h:232
bool IsNegative() const
Determines if the Integer is negative.
Definition: integer.h:336
Ring of congruence classes modulo n.
Definition: modarith.h:38
Interface for random number generators.
Definition: cryptlib.h:1383
int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Definition: nbtheory.cpp:785
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
Definition: ecp.cpp:587
Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
Definition: nbtheory.cpp:572
SecBlock<byte> typedef.
Definition: secblock.h:1058
BER Sequence Decoder.
Definition: asn.h:309
Interface for buffered transformations.
Definition: cryptlib.h:1598
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:342
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:339
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition: algebra.cpp:97
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
Definition: integer.cpp:4538
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:4877
Abstract ring.
Definition: algebra.h:118
const Integer & Identity() const
Provides the Identity element.
Definition: modarith.h:124
const Point & Identity() const
Provides the Identity element.
Definition: ecp.cpp:717
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Definition: integer.cpp:4517
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
Definition: ecp.cpp:954
const Point & Inverse(const Point &P) const
Inverts the element in the group.
Definition: ecp.cpp:729
Copy input to a memory buffer.
Definition: filters.h:1136
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
Definition: integer.h:747
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
Definition: integer.cpp:4522
Empty store.
Definition: filters.h:1257
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:1901
Point ScalarMultiply(const Point &P, const Integer &k) const
Performs a scalar multiplication.
Definition: ecp.cpp:846
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1620
size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
Definition: asn.cpp:117
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: modarith.h:174
bool Equal(const Point &P, const Point &Q) const
Compare two elements for equality.
Definition: ecp.cpp:703
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Definition: nbtheory.cpp:247
virtual const Element & MultiplicativeInverse(const Element &a) const =0
Calculate the multiplicative inverse of an element in the group.
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
Precompiled header file.
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
const Integer & GetModulus() const
Retrieves the modulus.
Definition: modarith.h:83
const Integer & Half(const Integer &a) const
Divides an element by 2.
Definition: integer.cpp:4527
String-based implementation of Store interface.
Definition: filters.h:1195
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:69
Abstract group.
Definition: algebra.h:26
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition: modarith.h:99
Classes and functions for working with ANS.1 objects.
void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
DER Encodes an elliptic curve point.
Definition: ecp.cpp:671
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3345
Implementation of BufferedTransformation&#39;s attachment interface.
Classes and functions for number theoretic operations.
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
Definition: integer.cpp:3410
DER Sequence Encoder.
Definition: asn.h:319
const Point & Double(const Point &P) const
Doubles an element in the group.
Definition: ecp.cpp:748
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:274
void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
Encodes an elliptic curve point.
Definition: ecp.cpp:654
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
Definition: integer.cpp:3354
ECP()
Construct an ECP.
Definition: ecp.h:36
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.
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
Definition: ecp.h:78
size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
Definition: asn.cpp:191
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:527
Class file for performing modular arithmetic.
Crypto++ library namespace.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Definition: integer.cpp:3103
void DEREncode(BufferedTransformation &bt) const
Encode the fields fieldID and curve of the sequence ECParameters.
Definition: ecp.cpp:572
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition: modarith.h:166
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
Definition: ecp.cpp:661
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:856
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:797
lword TotalPutLength()
Provides the number of bytes written to the Sink.
Definition: filters.h:1159
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Definition: integer.cpp:4509
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
Definition: ecp.cpp:742
the value is positive or 0
Definition: integer.h:75
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:351
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.
Definition: modarith.h:92