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