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