Crypto++  7.0
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 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 
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 
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  CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
636 }
637 
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)
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  Integer sixteenY4, aZ4, twoY, fourY2, S, M;
803 };
804 
805 struct ZIterator
806 {
807  ZIterator() {}
808  ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
809  Integer& operator*() {return it->z;}
810  int operator-(ZIterator it2) {return int(it-it2.it);}
811  ZIterator operator+(int i) {return ZIterator(it+i);}
812  ZIterator& operator+=(int i) {it+=i; return *this;}
813  std::vector<ProjectivePoint>::iterator it;
814 };
815 
816 ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
817 {
818  Element result;
819  if (k.BitCount() <= 5)
821  else
822  ECP::SimultaneousMultiply(&result, P, &k, 1);
823  return result;
824 }
825 
826 void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
827 {
828  if (!GetField().IsMontgomeryRepresentation())
829  {
830  ECP ecpmr(*this, true);
831  const ModularArithmetic &mr = ecpmr.GetField();
832  ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
833  for (unsigned int i=0; i<expCount; i++)
834  results[i] = FromMontgomery(mr, results[i]);
835  return;
836  }
837 
838  ProjectiveDoubling rd(GetField(), m_a, m_b, P);
839  std::vector<ProjectivePoint> bases;
840  std::vector<WindowSlider> exponents;
841  exponents.reserve(expCount);
842  std::vector<std::vector<word32> > baseIndices(expCount);
843  std::vector<std::vector<bool> > negateBase(expCount);
844  std::vector<std::vector<word32> > exponentWindows(expCount);
845  unsigned int i;
846 
847  for (i=0; i<expCount; i++)
848  {
849  CRYPTOPP_ASSERT(expBegin->NotNegative());
850  exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
851  exponents[i].FindNextWindow();
852  }
853 
854  unsigned int expBitPosition = 0;
855  bool notDone = true;
856 
857  while (notDone)
858  {
859  notDone = false;
860  bool baseAdded = false;
861  for (i=0; i<expCount; i++)
862  {
863  if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
864  {
865  if (!baseAdded)
866  {
867  bases.push_back(rd.P);
868  baseAdded =true;
869  }
870 
871  exponentWindows[i].push_back(exponents[i].expWindow);
872  baseIndices[i].push_back((word32)bases.size()-1);
873  negateBase[i].push_back(exponents[i].negateNext);
874 
875  exponents[i].FindNextWindow();
876  }
877  notDone = notDone || !exponents[i].finished;
878  }
879 
880  if (notDone)
881  {
882  rd.Double();
883  expBitPosition++;
884  }
885  }
886 
887  // convert from projective to affine coordinates
888  ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
889  for (i=0; i<bases.size(); i++)
890  {
891  if (bases[i].z.NotZero())
892  {
893  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
894  bases[i].z = GetField().Square(bases[i].z);
895  bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
896  bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
897  }
898  }
899 
900  std::vector<BaseAndExponent<Point, Integer> > finalCascade;
901  for (i=0; i<expCount; i++)
902  {
903  finalCascade.resize(baseIndices[i].size());
904  for (unsigned int j=0; j<baseIndices[i].size(); j++)
905  {
906  ProjectivePoint &base = bases[baseIndices[i][j]];
907  if (base.z.IsZero())
908  finalCascade[j].base.identity = true;
909  else
910  {
911  finalCascade[j].base.identity = false;
912  finalCascade[j].base.x = base.x;
913  if (negateBase[i][j])
914  finalCascade[j].base.y = GetField().Inverse(base.y);
915  else
916  finalCascade[j].base.y = base.y;
917  }
918  finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
919  }
920  results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end());
921  }
922 }
923 
924 ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
925 {
926  if (!GetField().IsMontgomeryRepresentation())
927  {
928  ECP ecpmr(*this, true);
929  const ModularArithmetic &mr = ecpmr.GetField();
930  return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
931  }
932  else
933  return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
934 }
935 
936 NAMESPACE_END
937 
938 #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.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
Definition: integer.cpp:4551
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:291
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.
const Point & Identity() const
Provides the Identity element.
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 Point & Inverse(const Point &P) const
Inverts the element in the group.
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
Definition: integer.cpp:4568
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:4534
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:1330
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.
Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
Definition: nbtheory.cpp:572
SecBlock<byte> typedef.
Definition: secblock.h:822
BER Sequence Decoder.
Definition: asn.h:305
Interface for buffered transformations.
Definition: cryptlib.h:1545
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:4494
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:4824
Abstract ring.
Definition: algebra.h:118
const Integer & Identity() const
Provides the Identity element.
Definition: modarith.h:124
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Definition: integer.cpp:4473
Copy input to a memory buffer.
Definition: filters.h:1132
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
Definition: integer.h:747
Empty store.
Definition: filters.h:1253
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:1848
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1567
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
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 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:4483
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:1191
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:60
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.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3319
Implementation of BufferedTransformation'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:315
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.
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
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:533
Class file for performing modular arithmetic.
Crypto++ library namespace.
void DEREncode(BufferedTransformation &bt) const
Encode the fields fieldID and curve of the sequence ECParameters.
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition: modarith.h:166
void SimultaneousMultiply(Point *results, const Point &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
const T & Ref(...) const
Return a reference to the inner Singleton object.
Definition: misc.h:312
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:561
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Definition: integer.cpp:4465
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