Botan  2.1.0
Crypto and TLS for C++11
point_gfp.cpp
Go to the documentation of this file.
1 /*
2 * Point arithmetic on elliptic curves over GF(p)
3 *
4 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
5 * 2008-2011,2012,2014,2015 Jack Lloyd
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9 
10 #include <botan/point_gfp.h>
11 #include <botan/numthry.h>
12 #include <botan/loadstor.h>
13 #include <botan/internal/rounding.h>
14 
15 namespace Botan {
16 
17 
19  m_curve(curve),
20  m_coord_x(0),
21  m_coord_y(1),
22  m_coord_z(0)
23  {
24  m_curve.to_rep(m_coord_x, m_monty_ws);
25  m_curve.to_rep(m_coord_y, m_monty_ws);
26  m_curve.to_rep(m_coord_z, m_monty_ws);
27  }
28 
29 PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
30  m_curve(curve),
31  m_coord_x(x),
32  m_coord_y(y),
33  m_coord_z(1)
34  {
35  if(x <= 0 || x >= curve.get_p())
36  throw Invalid_Argument("Invalid PointGFp affine x");
37  if(y <= 0 || y >= curve.get_p())
38  throw Invalid_Argument("Invalid PointGFp affine y");
39 
40  m_curve.to_rep(m_coord_x, m_monty_ws);
41  m_curve.to_rep(m_coord_y, m_monty_ws);
42  m_curve.to_rep(m_coord_z, m_monty_ws);
43  }
44 
46  {
47  if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS > 1)
48  {
49  BigInt mask;
50  while(mask.is_zero())
51  mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false);
52 
53  m_curve.to_rep(mask, m_monty_ws);
54  const BigInt mask2 = curve_mult(mask, mask);
55  const BigInt mask3 = curve_mult(mask2, mask);
56 
57  m_coord_x = curve_mult(m_coord_x, mask2);
58  m_coord_y = curve_mult(m_coord_y, mask3);
59  m_coord_z = curve_mult(m_coord_z, mask);
60  }
61  }
62 
63 // Point addition
64 void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
65  {
66  if(is_zero())
67  {
68  m_coord_x = rhs.m_coord_x;
69  m_coord_y = rhs.m_coord_y;
70  m_coord_z = rhs.m_coord_z;
71  return;
72  }
73  else if(rhs.is_zero())
74  return;
75 
76  const BigInt& p = m_curve.get_p();
77 
78  BigInt& rhs_z2 = ws_bn[0];
79  BigInt& U1 = ws_bn[1];
80  BigInt& S1 = ws_bn[2];
81 
82  BigInt& lhs_z2 = ws_bn[3];
83  BigInt& U2 = ws_bn[4];
84  BigInt& S2 = ws_bn[5];
85 
86  BigInt& H = ws_bn[6];
87  BigInt& r = ws_bn[7];
88 
89  /*
90  http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
91  */
92 
93  curve_sqr(rhs_z2, rhs.m_coord_z);
94  curve_mult(U1, m_coord_x, rhs_z2);
95  curve_mult(S1, m_coord_y, curve_mult(rhs.m_coord_z, rhs_z2));
96 
97  curve_sqr(lhs_z2, m_coord_z);
98  curve_mult(U2, rhs.m_coord_x, lhs_z2);
99  curve_mult(S2, rhs.m_coord_y, curve_mult(m_coord_z, lhs_z2));
100 
101  H = U2;
102  H -= U1;
103  if(H.is_negative())
104  H += p;
105 
106  r = S2;
107  r -= S1;
108  if(r.is_negative())
109  r += p;
110 
111  if(H.is_zero())
112  {
113  if(r.is_zero())
114  {
115  mult2(ws_bn);
116  return;
117  }
118 
119  // setting to zero:
120  m_coord_x = 0;
121  m_coord_y = 1;
122  m_coord_z = 0;
123  return;
124  }
125 
126  curve_sqr(U2, H);
127 
128  curve_mult(S2, U2, H);
129 
130  U2 = curve_mult(U1, U2);
131 
132  curve_sqr(m_coord_x, r);
133  m_coord_x -= S2;
134  m_coord_x -= (U2 << 1);
135  while(m_coord_x.is_negative())
136  m_coord_x += p;
137 
138  U2 -= m_coord_x;
139  if(U2.is_negative())
140  U2 += p;
141 
142  curve_mult(m_coord_y, r, U2);
143  m_coord_y -= curve_mult(S1, S2);
144  if(m_coord_y.is_negative())
145  m_coord_y += p;
146 
147  curve_mult(m_coord_z, curve_mult(m_coord_z, rhs.m_coord_z), H);
148  }
149 
150 // *this *= 2
151 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
152  {
153  if(is_zero())
154  return;
155  else if(m_coord_y.is_zero())
156  {
157  *this = PointGFp(m_curve); // setting myself to zero
158  return;
159  }
160 
161  /*
162  http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
163  */
164 
165  const BigInt& p = m_curve.get_p();
166 
167  BigInt& y_2 = ws_bn[0];
168  BigInt& S = ws_bn[1];
169  BigInt& z4 = ws_bn[2];
170  BigInt& a_z4 = ws_bn[3];
171  BigInt& M = ws_bn[4];
172  BigInt& U = ws_bn[5];
173  BigInt& x = ws_bn[6];
174  BigInt& y = ws_bn[7];
175  BigInt& z = ws_bn[8];
176 
177  curve_sqr(y_2, m_coord_y);
178 
179  curve_mult(S, m_coord_x, y_2);
180  S <<= 2; // * 4
181  while(S >= p)
182  S -= p;
183 
184  curve_sqr(z4, curve_sqr(m_coord_z));
185  curve_mult(a_z4, m_curve.get_a_rep(), z4);
186 
187  M = curve_sqr(m_coord_x);
188  M *= 3;
189  M += a_z4;
190  while(M >= p)
191  M -= p;
192 
193  curve_sqr(x, M);
194  x -= (S << 1);
195  while(x.is_negative())
196  x += p;
197 
198  curve_sqr(U, y_2);
199  U <<= 3;
200  while(U >= p)
201  U -= p;
202 
203  S -= x;
204  while(S.is_negative())
205  S += p;
206 
207  curve_mult(y, M, S);
208  y -= U;
209  if(y.is_negative())
210  y += p;
211 
212  curve_mult(z, m_coord_y, m_coord_z);
213  z <<= 1;
214  if(z >= p)
215  z -= p;
216 
217  m_coord_x = x;
218  m_coord_y = y;
219  m_coord_z = z;
220  }
221 
222 // arithmetic operators
224  {
225  std::vector<BigInt> ws(9);
226  add(rhs, ws);
227  return *this;
228  }
229 
231  {
232  PointGFp minus_rhs = PointGFp(rhs).negate();
233 
234  if(is_zero())
235  *this = minus_rhs;
236  else
237  *this += minus_rhs;
238 
239  return *this;
240  }
241 
243  {
244  *this = scalar * *this;
245  return *this;
246  }
247 
249  const PointGFp& p2, const BigInt& z2)
250  {
251  const PointGFp p3 = p1 + p2;
252 
253  PointGFp H(p1.get_curve()); // create as zero
254  size_t bits_left = std::max(z1.bits(), z2.bits());
255 
256  std::vector<BigInt> ws(9);
257 
258  while(bits_left)
259  {
260  H.mult2(ws);
261 
262  const bool z1_b = z1.get_bit(bits_left - 1);
263  const bool z2_b = z2.get_bit(bits_left - 1);
264 
265  if(z1_b == true && z2_b == true)
266  H.add(p3, ws);
267  else if(z1_b)
268  H.add(p1, ws);
269  else if(z2_b)
270  H.add(p2, ws);
271 
272  --bits_left;
273  }
274 
275  if(z1.is_negative() != z2.is_negative())
276  H.negate();
277 
278  return H;
279  }
280 
281 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
282  {
283  //BOTAN_ASSERT(point.on_the_curve(), "Input is on the curve");
284 
285  const CurveGFp& curve = point.get_curve();
286 
287  const size_t scalar_bits = scalar.bits();
288 
289  std::vector<BigInt> ws(9);
290 
291  PointGFp R[2] = { PointGFp(curve), point };
292 
293  for(size_t i = scalar_bits; i > 0; i--)
294  {
295  const size_t b = scalar.get_bit(i - 1);
296  R[b ^ 1].add(R[b], ws);
297  R[b].mult2(ws);
298  }
299 
300  if(scalar.is_negative())
301  R[0].negate();
302 
303  //BOTAN_ASSERT(R[0].on_the_curve(), "Output is on the curve");
304 
305  return R[0];
306  }
307 
308 Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h) :
309  m_h(h > 0 ? h : 4), m_order(order), m_ws(9)
310  {
311  // Upper bound is a sanity check rather than hard limit
312  if(m_h < 1 || m_h > 8)
313  throw Invalid_Argument("Blinded_Point_Multiply invalid h param");
314 
315  const CurveGFp& curve = base.get_curve();
316 
317  const PointGFp inv = -base;
318 
319  m_U.resize(6*m_h + 3);
320 
321  m_U[3*m_h+0] = inv;
322  m_U[3*m_h+1] = PointGFp::zero_of(curve);
323  m_U[3*m_h+2] = base;
324 
325  for(size_t i = 1; i <= 3 * m_h + 1; ++i)
326  {
327  m_U[3*m_h+1+i] = m_U[3*m_h+i];
328  m_U[3*m_h+1+i].add(base, m_ws);
329 
330  m_U[3*m_h+1-i] = m_U[3*m_h+2-i];
331  m_U[3*m_h+1-i].add(inv, m_ws);
332  }
333  }
334 
337  {
338  if(scalar_in.is_negative())
339  throw Invalid_Argument("Blinded_Point_Multiply scalar must be positive");
340 
341 #if BOTAN_POINTGFP_USE_SCALAR_BLINDING
342  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
343  const BigInt mask(rng, (m_order.bits()+1)/2, false);
344  const BigInt scalar = scalar_in + m_order * mask;
345 #else
346  const BigInt& scalar = scalar_in;
347 #endif
348 
349  const size_t scalar_bits = scalar.bits();
350 
351  // Randomize each point representation (Coron's 3rd countermeasure)
352  for(size_t i = 0; i != m_U.size(); ++i)
353  m_U[i].randomize_repr(rng);
354 
355  PointGFp R = m_U.at(3*m_h + 2); // base point
356  int32_t alpha = 0;
357 
358  R.randomize_repr(rng);
359 
360  /*
361  Algorithm 7 from "Randomizing the Montgomery Powering Ladder"
362  Duc-Phong Le, Chik How Tan and Michael Tunstall
363  http://eprint.iacr.org/2015/657
364 
365  It takes a random walk through (a subset of) the set of addition
366  chains that end in k.
367  */
368  for(size_t i = scalar_bits; i > 0; i--)
369  {
370  const int32_t ki = scalar.get_bit(i);
371 
372  // choose gamma from -h,...,h
373  const int32_t gamma = static_cast<int32_t>((rng.next_byte() % (2*m_h))) - m_h;
374  const int32_t l = gamma - 2*alpha + ki - (ki ^ 1);
375 
376  R.mult2(m_ws);
377  R.add(m_U.at(3*m_h + 1 + l), m_ws);
378  alpha = gamma;
379  }
380 
381  const int32_t k0 = scalar.get_bit(0);
382  R.add(m_U[3*m_h + 1 - alpha - (k0 ^ 1)], m_ws);
383 
384 
385  //BOTAN_ASSERT(R.on_the_curve(), "Output is on the curve");
386 
387  return R;
388  }
389 
391  {
392  if(is_zero())
393  throw Illegal_Transformation("Cannot convert zero point to affine");
394 
395  BigInt z2 = curve_sqr(m_coord_z);
396  m_curve.from_rep(z2, m_monty_ws);
397  z2 = inverse_mod(z2, m_curve.get_p());
398 
399  return curve_mult(z2, m_coord_x);
400  }
401 
403  {
404  if(is_zero())
405  throw Illegal_Transformation("Cannot convert zero point to affine");
406 
407  BigInt z3 = curve_mult(m_coord_z, curve_sqr(m_coord_z));
408  z3 = inverse_mod(z3, m_curve.get_p());
409  m_curve.to_rep(z3, m_monty_ws);
410 
411  return curve_mult(z3, m_coord_y);
412  }
413 
415  {
416  /*
417  Is the point still on the curve?? (If everything is correct, the
418  point is always on its curve; then the function will return true.
419  If somehow the state is corrupted, which suggests a fault attack
420  (or internal computational error), then return false.
421  */
422  if(is_zero())
423  return true;
424 
425  const BigInt y2 = m_curve.from_rep(curve_sqr(m_coord_y), m_monty_ws);
426  const BigInt x3 = curve_mult(m_coord_x, curve_sqr(m_coord_x));
427  const BigInt ax = curve_mult(m_coord_x, m_curve.get_a_rep());
428  const BigInt z2 = curve_sqr(m_coord_z);
429 
430  if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
431  {
432  if(y2 != m_curve.from_rep(x3 + ax + m_curve.get_b_rep(), m_monty_ws))
433  return false;
434  }
435 
436  const BigInt z3 = curve_mult(m_coord_z, z2);
437  const BigInt ax_z4 = curve_mult(ax, curve_sqr(z2));
438  const BigInt b_z6 = curve_mult(m_curve.get_b_rep(), curve_sqr(z3));
439 
440  if(y2 != m_curve.from_rep(x3 + ax_z4 + b_z6, m_monty_ws))
441  return false;
442 
443  return true;
444  }
445 
446 // swaps the states of *this and other, does not throw!
448  {
449  m_curve.swap(other.m_curve);
450  m_coord_x.swap(other.m_coord_x);
451  m_coord_y.swap(other.m_coord_y);
452  m_coord_z.swap(other.m_coord_z);
453  m_monty_ws.swap(other.m_monty_ws);
454  }
455 
456 bool PointGFp::operator==(const PointGFp& other) const
457  {
458  if(get_curve() != other.get_curve())
459  return false;
460 
461  // If this is zero, only equal if other is also zero
462  if(is_zero())
463  return other.is_zero();
464 
465  return (get_affine_x() == other.get_affine_x() &&
466  get_affine_y() == other.get_affine_y());
467  }
468 
469 // encoding and decoding
470 secure_vector<uint8_t> EC2OSP(const PointGFp& point, uint8_t format)
471  {
472  if(point.is_zero())
473  return secure_vector<uint8_t>(1); // single 0 byte
474 
475  const size_t p_bytes = point.get_curve().get_p().bytes();
476 
477  BigInt x = point.get_affine_x();
478  BigInt y = point.get_affine_y();
479 
482 
483  if(format == PointGFp::UNCOMPRESSED)
484  {
485  secure_vector<uint8_t> result;
486  result.push_back(0x04);
487 
488  result += bX;
489  result += bY;
490 
491  return result;
492  }
493  else if(format == PointGFp::COMPRESSED)
494  {
495  secure_vector<uint8_t> result;
496  result.push_back(0x02 | static_cast<uint8_t>(y.get_bit(0)));
497 
498  result += bX;
499 
500  return result;
501  }
502  else if(format == PointGFp::HYBRID)
503  {
504  secure_vector<uint8_t> result;
505  result.push_back(0x06 | static_cast<uint8_t>(y.get_bit(0)));
506 
507  result += bX;
508  result += bY;
509 
510  return result;
511  }
512  else
513  throw Invalid_Argument("EC2OSP illegal point encoding");
514  }
515 
516 namespace {
517 
518 BigInt decompress_point(bool yMod2,
519  const BigInt& x,
520  const CurveGFp& curve)
521  {
522  BigInt xpow3 = x * x * x;
523 
524  const BigInt& p = curve.get_p();
525 
526  BigInt g = curve.get_a() * x;
527  g += xpow3;
528  g += curve.get_b();
529  g = g % p;
530 
531  BigInt z = ressol(g, p);
532 
533  if(z < 0)
534  throw Illegal_Point("error during EC point decompression");
535 
536  if(z.get_bit(0) != yMod2)
537  z = p - z;
538 
539  return z;
540  }
541 
542 }
543 
544 PointGFp OS2ECP(const uint8_t data[], size_t data_len,
545  const CurveGFp& curve)
546  {
547  if(data_len <= 1)
548  return PointGFp(curve); // return zero
549 
550  const uint8_t pc = data[0];
551 
552  BigInt x, y;
553 
554  if(pc == 2 || pc == 3)
555  {
556  //compressed form
557  x = BigInt::decode(&data[1], data_len - 1);
558 
559  const bool y_mod_2 = ((pc & 0x01) == 1);
560  y = decompress_point(y_mod_2, x, curve);
561  }
562  else if(pc == 4)
563  {
564  const size_t l = (data_len - 1) / 2;
565 
566  // uncompressed form
567  x = BigInt::decode(&data[1], l);
568  y = BigInt::decode(&data[l+1], l);
569  }
570  else if(pc == 6 || pc == 7)
571  {
572  const size_t l = (data_len - 1) / 2;
573 
574  // hybrid form
575  x = BigInt::decode(&data[1], l);
576  y = BigInt::decode(&data[l+1], l);
577 
578  const bool y_mod_2 = ((pc & 0x01) == 1);
579 
580  if(decompress_point(y_mod_2, x, curve) != y)
581  throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
582  }
583  else
584  throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));
585 
586  PointGFp result(curve, x, y);
587 
588  if(!result.on_the_curve())
589  throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
590 
591  return result;
592  }
593 
594 }
BigInt get_affine_y() const
Definition: point_gfp.cpp:402
static PointGFp zero_of(const CurveGFp &curve)
Definition: point_gfp.h:61
PointGFp & operator*=(const BigInt &scalar)
Definition: point_gfp.cpp:242
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
Definition: point_gfp.cpp:470
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
const CurveGFp & m_curve
Definition: ecdh.cpp:48
bool operator==(const PointGFp &other) const
Definition: point_gfp.cpp:456
bool is_negative() const
Definition: bigint.h:348
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
const BigInt & get_a_rep() const
Definition: curve_gfp.h:93
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:47
void swap(BigInt &other)
Definition: bigint.h:122
const CurveGFp & get_curve() const
Definition: point_gfp.h:159
BigInt get_affine_x() const
Definition: point_gfp.cpp:390
size_t bits() const
Definition: bigint.cpp:184
void swap(PointGFp &other)
Definition: point_gfp.cpp:447
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
PointGFp()=default
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:97
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:45
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:544
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:102
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
Definition: point_gfp.cpp:335
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:84
const BigInt & get_b_rep() const
Definition: curve_gfp.h:95
void swap(CurveGFp &other)
Definition: curve_gfp.h:140
Definition: alg_id.cpp:13
const BigInt & m_order
Definition: ecdh.cpp:50
T max(T a, T b)
Definition: ct_utils.h:173
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:276
const BigInt & get_p() const
Definition: curve_gfp.h:91
bool on_the_curve() const
Definition: point_gfp.cpp:414
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:82
bool is_zero() const
Definition: point_gfp.h:177
bool get_bit(size_t n) const
Definition: bigint.h:299
PointGFp & operator+=(const PointGFp &rhs)
Definition: point_gfp.cpp:223
bool is_zero() const
Definition: bigint.h:250
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
Definition: point_gfp.cpp:308
PointGFp & operator-=(const PointGFp &rhs)
Definition: point_gfp.cpp:230
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_gfp.cpp:248
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114
size_t bytes() const
Definition: bigint.cpp:176