Botan  1.10.9
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 Jack Lloyd
6 *
7 * Distributed under the terms of the Botan license
8 */
9 
10 #include <botan/point_gfp.h>
11 #include <botan/numthry.h>
12 #include <botan/reducer.h>
13 #include <botan/internal/mp_core.h>
14 
15 namespace Botan {
16 
18  curve(curve), ws(2 * (curve.get_p_words() + 2))
19  {
20  coord_x = 0;
21  coord_y = monty_mult(1, curve.get_r2());
22  coord_z = 0;
23  }
24 
25 PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
26  curve(curve), ws(2 * (curve.get_p_words() + 2))
27  {
28  coord_x = monty_mult(x, curve.get_r2());
29  coord_y = monty_mult(y, curve.get_r2());
30  coord_z = monty_mult(1, curve.get_r2());
31  }
32 
33 // Montgomery multiplication
34 void PointGFp::monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const
35  {
36  //assert(&z != &x && &z != &y);
37 
38  if(x.is_zero() || y.is_zero())
39  {
40  z = 0;
41  return;
42  }
43 
44  const BigInt& p = curve.get_p();
45  const size_t p_size = curve.get_p_words();
46  const word p_dash = curve.get_p_dash();
47 
48  SecureVector<word>& z_reg = z.get_reg();
49  z_reg.resize(2*p_size+1);
50  zeroise(z_reg);
51 
52  bigint_monty_mul(&z_reg[0], z_reg.size(),
53  x.data(), x.size(), x.sig_words(),
54  y.data(), y.size(), y.sig_words(),
55  p.data(), p_size, p_dash,
56  &ws[0]);
57  }
58 
59 // Montgomery squaring
60 void PointGFp::monty_sqr(BigInt& z, const BigInt& x) const
61  {
62  //assert(&z != &x);
63 
64  if(x.is_zero())
65  {
66  z = 0;
67  return;
68  }
69 
70  const BigInt& p = curve.get_p();
71  const size_t p_size = curve.get_p_words();
72  const word p_dash = curve.get_p_dash();
73 
74  SecureVector<word>& z_reg = z.get_reg();
75  z_reg.resize(2*p_size+1);
76  zeroise(z_reg);
77 
78  bigint_monty_sqr(&z_reg[0], z_reg.size(),
79  x.data(), x.size(), x.sig_words(),
80  p.data(), p_size, p_dash,
81  &ws[0]);
82  }
83 
84 // Point addition
85 void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
86  {
87  if(is_zero())
88  {
89  coord_x = rhs.coord_x;
90  coord_y = rhs.coord_y;
91  coord_z = rhs.coord_z;
92  return;
93  }
94  else if(rhs.is_zero())
95  return;
96 
97  const BigInt& p = curve.get_p();
98 
99  BigInt& rhs_z2 = ws_bn[0];
100  BigInt& U1 = ws_bn[1];
101  BigInt& S1 = ws_bn[2];
102 
103  BigInt& lhs_z2 = ws_bn[3];
104  BigInt& U2 = ws_bn[4];
105  BigInt& S2 = ws_bn[5];
106 
107  BigInt& H = ws_bn[6];
108  BigInt& r = ws_bn[7];
109 
110  monty_sqr(rhs_z2, rhs.coord_z);
111  monty_mult(U1, coord_x, rhs_z2);
112  monty_mult(S1, coord_y, monty_mult(rhs.coord_z, rhs_z2));
113 
114  monty_sqr(lhs_z2, coord_z);
115  monty_mult(U2, rhs.coord_x, lhs_z2);
116  monty_mult(S2, rhs.coord_y, monty_mult(coord_z, lhs_z2));
117 
118  H = U2;
119  H -= U1;
120  if(H.is_negative())
121  H += p;
122 
123  r = S2;
124  r -= S1;
125  if(r.is_negative())
126  r += p;
127 
128  if(H.is_zero())
129  {
130  if(r.is_zero())
131  {
132  mult2(ws_bn);
133  return;
134  }
135 
136  *this = PointGFp(curve); // setting myself to zero
137  return;
138  }
139 
140  monty_sqr(U2, H);
141 
142  monty_mult(S2, U2, H);
143 
144  U2 = monty_mult(U1, U2);
145 
146  monty_sqr(coord_x, r);
147  coord_x -= S2;
148  coord_x -= (U2 << 1);
149  while(coord_x.is_negative())
150  coord_x += p;
151 
152  U2 -= coord_x;
153  if(U2.is_negative())
154  U2 += p;
155 
156  monty_mult(coord_y, r, U2);
157  coord_y -= monty_mult(S1, S2);
158  if(coord_y.is_negative())
159  coord_y += p;
160 
161  monty_mult(coord_z, monty_mult(coord_z, rhs.coord_z), H);
162  }
163 
164 // *this *= 2
165 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
166  {
167  if(is_zero())
168  return;
169  else if(coord_y.is_zero())
170  {
171  *this = PointGFp(curve); // setting myself to zero
172  return;
173  }
174 
175  const BigInt& p = curve.get_p();
176 
177  BigInt& y_2 = ws_bn[0];
178  BigInt& S = ws_bn[1];
179  BigInt& z4 = ws_bn[2];
180  BigInt& a_z4 = ws_bn[3];
181  BigInt& M = ws_bn[4];
182  BigInt& U = ws_bn[5];
183  BigInt& x = ws_bn[6];
184  BigInt& y = ws_bn[7];
185  BigInt& z = ws_bn[8];
186 
187  monty_sqr(y_2, coord_y);
188 
189  monty_mult(S, coord_x, y_2);
190  S <<= 2; // * 4
191  while(S >= p)
192  S -= p;
193 
194  monty_sqr(z4, monty_sqr(coord_z));
195  monty_mult(a_z4, curve.get_a_r(), z4);
196 
197  M = 3 * monty_sqr(coord_x);
198  M += a_z4;
199  while(M >= p)
200  M -= p;
201 
202  monty_sqr(x, M);
203  x -= (S << 1);
204  while(x.is_negative())
205  x += p;
206 
207  monty_sqr(U, y_2);
208  U <<= 3;
209  while(U >= p)
210  U -= p;
211 
212  S -= x;
213  while(S.is_negative())
214  S += p;
215 
216  monty_mult(y, M, S);
217  y -= U;
218  if(y.is_negative())
219  y += p;
220 
221  monty_mult(z, coord_y, coord_z);
222  z <<= 1;
223  if(z >= p)
224  z -= p;
225 
226  coord_x = x;
227  coord_y = y;
228  coord_z = z;
229  }
230 
231 // arithmetic operators
233  {
234  std::vector<BigInt> ws(9);
235  add(rhs, ws);
236  return *this;
237  }
238 
240  {
241  PointGFp minus_rhs = PointGFp(rhs).negate();
242 
243  if(is_zero())
244  *this = minus_rhs;
245  else
246  *this += minus_rhs;
247 
248  return *this;
249  }
250 
252  {
253  *this = scalar * *this;
254  return *this;
255  }
256 
258  const PointGFp& p2, const BigInt& z2)
259  {
260  const PointGFp p3 = p1 + p2;
261 
262  PointGFp H(p1.curve); // create as zero
263  size_t bits_left = std::max(z1.bits(), z2.bits());
264 
265  std::vector<BigInt> ws(9);
266 
267  while(bits_left)
268  {
269  H.mult2(ws);
270 
271  const bool z1_b = z1.get_bit(bits_left - 1);
272  const bool z2_b = z2.get_bit(bits_left - 1);
273 
274  if(z1_b == true && z2_b == true)
275  H.add(p3, ws);
276  else if(z1_b)
277  H.add(p1, ws);
278  else if(z2_b)
279  H.add(p2, ws);
280 
281  --bits_left;
282  }
283 
284  if(z1.is_negative() != z2.is_negative())
285  H.negate();
286 
287  return H;
288  }
289 
290 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
291  {
292  const CurveGFp& curve = point.get_curve();
293 
294  if(scalar.is_zero())
295  return PointGFp(curve); // zero point
296 
297  std::vector<BigInt> ws(9);
298 
299  if(scalar.abs() <= 2) // special cases for small values
300  {
301  byte value = scalar.abs().byte_at(0);
302 
303  PointGFp result = point;
304 
305  if(value == 2)
306  result.mult2(ws);
307 
308  if(scalar.is_negative())
309  result.negate();
310 
311  return result;
312  }
313 
314  const size_t scalar_bits = scalar.bits();
315 
316 #if 0
317 
318  PointGFp x1 = PointGFp(curve);
319  PointGFp x2 = point;
320 
321  size_t bits_left = scalar_bits;
322 
323  // Montgomery Ladder
324  while(bits_left)
325  {
326  const bool bit_set = scalar.get_bit(bits_left - 1);
327 
328  if(bit_set)
329  {
330  x1.add(x2, ws);
331  x2.mult2(ws);
332  }
333  else
334  {
335  x2.add(x1, ws);
336  x1.mult2(ws);
337  }
338 
339  --bits_left;
340  }
341 
342  if(scalar.is_negative())
343  x1.negate();
344 
345  return x1;
346 
347 #else
348  const size_t window_size = 4;
349 
350  std::vector<PointGFp> Ps(1 << window_size);
351  Ps[0] = PointGFp(curve);
352  Ps[1] = point;
353 
354  for(size_t i = 2; i != Ps.size(); ++i)
355  {
356  Ps[i] = Ps[i-1];
357  Ps[i].add(point, ws);
358  }
359 
360  PointGFp H(curve); // create as zero
361  size_t bits_left = scalar_bits;
362 
363  while(bits_left >= window_size)
364  {
365  for(size_t i = 0; i != window_size; ++i)
366  H.mult2(ws);
367 
368  const u32bit nibble = scalar.get_substring(bits_left - window_size,
369  window_size);
370 
371  H.add(Ps[nibble], ws);
372 
373  bits_left -= window_size;
374  }
375 
376  while(bits_left)
377  {
378  H.mult2(ws);
379  if(scalar.get_bit(bits_left-1))
380  H.add(point, ws);
381 
382  --bits_left;
383  }
384 
385  if(scalar.is_negative())
386  H.negate();
387 
388  return H;
389 #endif
390  }
391 
393  {
394  if(is_zero())
395  throw Illegal_Transformation("Cannot convert zero point to affine");
396 
397  const BigInt& r2 = curve.get_r2();
398 
399  BigInt z2 = monty_sqr(coord_z);
400  z2 = inverse_mod(z2, curve.get_p());
401 
402  z2 = monty_mult(z2, r2);
403  return monty_mult(coord_x, z2);
404  }
405 
407  {
408  if(is_zero())
409  throw Illegal_Transformation("Cannot convert zero point to affine");
410 
411  const BigInt& r2 = curve.get_r2();
412 
413  BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z));
414  z3 = inverse_mod(z3, curve.get_p());
415  z3 = monty_mult(z3, r2);
416  return monty_mult(coord_y, z3);
417  }
418 
420  {
421  /*
422  Is the point still on the curve?? (If everything is correct, the
423  point is always on its curve; then the function will return true.
424  If somehow the state is corrupted, which suggests a fault attack
425  (or internal computational error), then return false.
426  */
427 
428  if(is_zero())
429  return true;
430 
431  BigInt y2 = monty_mult(monty_sqr(coord_y), 1);
432  BigInt x3 = monty_mult(coord_x, monty_sqr(coord_x));
433 
434  BigInt ax = monty_mult(coord_x, curve.get_a_r());
435 
436  const BigInt& b_r = curve.get_b_r();
437 
438  BigInt z2 = monty_sqr(coord_z);
439 
440  if(coord_z == z2) // Is z equal to 1 (in Montgomery form)?
441  {
442  if(y2 != monty_mult(x3 + ax + b_r, 1))
443  return false;
444  }
445 
446  BigInt z3 = monty_mult(coord_z, z2);
447 
448  BigInt ax_z4 = monty_mult(ax, monty_sqr(z2));
449 
450  BigInt b_z6 = monty_mult(b_r, monty_sqr(z3));
451 
452  if(y2 != monty_mult(x3 + ax_z4 + b_z6, 1))
453  return false;
454 
455  return true;
456  }
457 
458 // swaps the states of *this and other, does not throw!
460  {
461  curve.swap(other.curve);
462  coord_x.swap(other.coord_x);
463  coord_y.swap(other.coord_y);
464  coord_z.swap(other.coord_z);
465  ws.swap(other.ws);
466  }
467 
468 bool PointGFp::operator==(const PointGFp& other) const
469  {
470  if(get_curve() != other.get_curve())
471  return false;
472 
473  // If this is zero, only equal if other is also zero
474  if(is_zero())
475  return other.is_zero();
476 
477  return (get_affine_x() == other.get_affine_x() &&
478  get_affine_y() == other.get_affine_y());
479  }
480 
481 // encoding and decoding
482 SecureVector<byte> EC2OSP(const PointGFp& point, byte format)
483  {
484  if(point.is_zero())
485  return SecureVector<byte>(1); // single 0 byte
486 
487  const size_t p_bytes = point.get_curve().get_p().bytes();
488 
489  BigInt x = point.get_affine_x();
490  BigInt y = point.get_affine_y();
491 
492  SecureVector<byte> bX = BigInt::encode_1363(x, p_bytes);
493  SecureVector<byte> bY = BigInt::encode_1363(y, p_bytes);
494 
495  if(format == PointGFp::UNCOMPRESSED)
496  {
497  SecureVector<byte> result;
498  result.push_back(0x04);
499 
500  result += bX;
501  result += bY;
502 
503  return result;
504  }
505  else if(format == PointGFp::COMPRESSED)
506  {
507  SecureVector<byte> result;
508  result.push_back(0x02 | static_cast<byte>(y.get_bit(0)));
509 
510  result += bX;
511 
512  return result;
513  }
514  else if(format == PointGFp::HYBRID)
515  {
516  SecureVector<byte> result;
517  result.push_back(0x06 | static_cast<byte>(y.get_bit(0)));
518 
519  result += bX;
520  result += bY;
521 
522  return result;
523  }
524  else
525  throw Invalid_Argument("illegal point encoding format specification");
526  }
527 
528 namespace {
529 
530 BigInt decompress_point(bool yMod2,
531  const BigInt& x,
532  const CurveGFp& curve)
533  {
534  BigInt xpow3 = x * x * x;
535 
536  BigInt g = curve.get_a() * x;
537  g += xpow3;
538  g += curve.get_b();
539  g = g % curve.get_p();
540 
541  BigInt z = ressol(g, curve.get_p());
542 
543  if(z < 0)
544  throw Illegal_Point("error during decompression");
545 
546  if(z.get_bit(0) != yMod2)
547  z = curve.get_p() - z;
548 
549  return z;
550  }
551 
552 }
553 
554 PointGFp OS2ECP(const byte data[], size_t data_len,
555  const CurveGFp& curve)
556  {
557  if(data_len <= 1)
558  return PointGFp(curve); // return zero
559 
560  const byte pc = data[0];
561 
562  BigInt x, y;
563 
564  if(pc == 2 || pc == 3)
565  {
566  //compressed form
567  x = BigInt::decode(&data[1], data_len - 1);
568 
569  const bool y_mod_2 = ((pc & 0x01) == 1);
570  y = decompress_point(y_mod_2, x, curve);
571  }
572  else if(pc == 4)
573  {
574  const size_t l = (data_len - 1) / 2;
575 
576  // uncompressed form
577  x = BigInt::decode(&data[1], l);
578  y = BigInt::decode(&data[l+1], l);
579  }
580  else if(pc == 6 || pc == 7)
581  {
582  const size_t l = (data_len - 1) / 2;
583 
584  // hybrid form
585  x = BigInt::decode(&data[1], l);
586  y = BigInt::decode(&data[l+1], l);
587 
588  const bool y_mod_2 = ((pc & 0x01) == 1);
589 
590  if(decompress_point(y_mod_2, x, curve) != y)
591  throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
592  }
593  else
594  throw Invalid_Argument("OS2ECP: Unknown format type");
595 
596  PointGFp result(curve, x, y);
597 
598  if(!result.on_the_curve())
599  throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
600 
601  return result;
602  }
603 
604 }
size_t sig_words() const
Definition: bigint.h:290
void resize(size_t n)
Definition: secmem.h:211
BigInt get_affine_y() const
Definition: point_gfp.cpp:406
PointGFp & operator*=(const BigInt &scalar)
Definition: point_gfp.cpp:251
PointGFp OS2ECP(const byte data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:554
byte byte_at(size_t n) const
Definition: bigint.cpp:147
SecureVector< word > & get_reg()
Definition: bigint.h:325
const BigInt & get_b_r() const
Definition: curve_gfp.h:79
BigInt abs() const
Definition: bigint.cpp:330
void push_back(T x)
Definition: secmem.h:143
bool operator==(const PointGFp &other) const
Definition: point_gfp.cpp:468
bool is_negative() const
Definition: bigint.h:245
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
size_t get_p_words() const
Definition: curve_gfp.h:89
size_t size() const
Definition: bigint.h:284
void bigint_monty_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:84
void swap(BigInt &other)
Definition: bigint.cpp:106
const CurveGFp & get_curve() const
Definition: point_gfp.h:128
const BigInt & get_r2() const
Definition: curve_gfp.h:69
unsigned char byte
Definition: types.h:22
SecureVector< byte > EC2OSP(const PointGFp &point, byte format)
Definition: point_gfp.cpp:482
BigInt get_affine_x() const
Definition: point_gfp.cpp:392
u32bit get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:168
size_t bits() const
Definition: bigint.cpp:253
void swap(PointGFp &other)
Definition: point_gfp.cpp:459
const BigInt & get_a_r() const
Definition: curve_gfp.h:74
const word * data() const
Definition: bigint.h:317
PointGFp & negate()
Definition: point_gfp.h:117
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:83
void swap(CurveGFp &other)
Definition: curve_gfp.h:95
void bigint_monty_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:69
void swap(MemoryRegion< T > &other)
Definition: secmem.h:254
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:202
const BigInt & get_p() const
Definition: curve_gfp.h:64
static BigInt decode(const byte buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:102
bool on_the_curve() const
Definition: point_gfp.cpp:419
BigInt r
Definition: numthry.cpp:26
word get_p_dash() const
Definition: curve_gfp.h:84
bool is_zero() const
Definition: point_gfp.h:146
bool get_bit(size_t n) const
Definition: bigint.cpp:160
PointGFp & operator+=(const PointGFp &rhs)
Definition: point_gfp.cpp:232
bool is_zero() const
Definition: bigint.h:176
PointGFp & operator-=(const PointGFp &rhs)
Definition: point_gfp.cpp:239
void zeroise(MemoryRegion< T > &vec)
Definition: secmem.h:415
static SecureVector< byte > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:78
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_gfp.cpp:257
unsigned int u32bit
Definition: types.h:32
size_t bytes() const
Definition: bigint.cpp:245