Botan  2.7.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 #include <botan/internal/rounding.h>
14 
15 namespace Botan {
16 
18  m_curve(curve),
19  m_coord_x(0),
20  m_coord_y(curve.get_1_rep()),
21  m_coord_z(0)
22  {
23  // Assumes Montgomery rep of zero is zero
24  }
25 
26 PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
27  m_curve(curve),
28  m_coord_x(x),
29  m_coord_y(y),
30  m_coord_z(m_curve.get_1_rep())
31  {
32  if(x <= 0 || x >= curve.get_p())
33  throw Invalid_Argument("Invalid PointGFp affine x");
34  if(y <= 0 || y >= curve.get_p())
35  throw Invalid_Argument("Invalid PointGFp affine y");
36 
37  secure_vector<word> monty_ws(m_curve.get_ws_size());
38  m_curve.to_rep(m_coord_x, monty_ws);
39  m_curve.to_rep(m_coord_y, monty_ws);
40  }
41 
43  {
44  secure_vector<word> ws(m_curve.get_ws_size());
45  randomize_repr(rng, ws);
46  }
47 
49  {
50  const BigInt mask = BigInt::random_integer(rng, 2, m_curve.get_p());
51 
52  /*
53  * No reason to convert this to Montgomery representation first,
54  * just pretend the random mask was chosen as Redc(mask) and the
55  * random mask we generated above is in the Montgomery
56  * representation.
57  * //m_curve.to_rep(mask, ws);
58  */
59  const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);
60  const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);
61 
62  m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws);
63  m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws);
64  m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws);
65  }
66 
67 namespace {
68 
69 inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size)
70  {
71  BOTAN_ASSERT(ws_bn.size() >= PointGFp::WORKSPACE_SIZE,
72  "Expected size for PointGFp workspace");
73 
74  for(size_t i = 0; i != ws_bn.size(); ++i)
75  if(ws_bn[i].size() < cap_size)
76  ws_bn[i].get_word_vector().resize(cap_size);
77  }
78 
79 inline bool all_zeros(const word x[], size_t len)
80  {
81  word z = 0;
82  for(size_t i = 0; i != len; ++i)
83  z |= x[i];
84  return (z == 0);
85  }
86 
87 }
88 
89 void PointGFp::add_affine(const word x_words[], size_t x_size,
90  const word y_words[], size_t y_size,
91  std::vector<BigInt>& ws_bn)
92  {
93  if(all_zeros(x_words, x_size) && all_zeros(y_words, y_size))
94  return;
95 
96  if(is_zero())
97  {
98  m_coord_x.set_words(x_words, x_size);
99  m_coord_y.set_words(y_words, y_size);
100  m_coord_z = m_curve.get_1_rep();
101  return;
102  }
103 
104  resize_ws(ws_bn, m_curve.get_ws_size());
105 
106  secure_vector<word>& ws = ws_bn[0].get_word_vector();
107  secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
108 
109  BigInt& T0 = ws_bn[2];
110  BigInt& T1 = ws_bn[3];
111  BigInt& T2 = ws_bn[4];
112  BigInt& T3 = ws_bn[5];
113  BigInt& T4 = ws_bn[6];
114 
115  /*
116  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
117  simplified with Z2 = 1
118  */
119 
120  const BigInt& p = m_curve.get_p();
121 
122  m_curve.sqr(T3, m_coord_z, ws); // z1^2
123  m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
124 
125  m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
126  m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3
127 
128  T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2
129 
130  T0.mod_sub(m_coord_y, p, sub_ws);
131 
132  if(T4.is_zero())
133  {
134  if(T0.is_zero())
135  {
136  mult2(ws_bn);
137  return;
138  }
139 
140  // setting to zero:
141  m_coord_x = 0;
142  m_coord_y = m_curve.get_1_rep();
143  m_coord_z = 0;
144  return;
145  }
146 
147  m_curve.sqr(T2, T4, ws);
148 
149  m_curve.mul(T3, m_coord_x, T2, ws);
150 
151  m_curve.mul(T1, T2, T4, ws);
152 
153  m_curve.sqr(m_coord_x, T0, ws);
154  m_coord_x.mod_sub(T1, p, sub_ws);
155  m_coord_x.mod_sub(T3, p, sub_ws);
156  m_coord_x.mod_sub(T3, p, sub_ws);
157 
158  T3.mod_sub(m_coord_x, p, sub_ws);
159 
160  T2 = m_coord_y;
161  m_curve.mul(T2, T0, T3, ws);
162  m_curve.mul(T3, m_coord_y, T1, ws);
163  T2.mod_sub(T3, p, sub_ws);
164  m_coord_y = T2;
165 
166  m_curve.mul(T3, m_coord_z, T4, ws);
167  m_coord_z = T3;
168  }
169 
170 void PointGFp::add(const word x_words[], size_t x_size,
171  const word y_words[], size_t y_size,
172  const word z_words[], size_t z_size,
173  std::vector<BigInt>& ws_bn)
174  {
175  if(all_zeros(x_words, x_size) && all_zeros(z_words, z_size))
176  return;
177 
178  if(is_zero())
179  {
180  m_coord_x.set_words(x_words, x_size);
181  m_coord_y.set_words(y_words, y_size);
182  m_coord_z.set_words(z_words, z_size);
183  return;
184  }
185 
186  resize_ws(ws_bn, m_curve.get_ws_size());
187 
188  secure_vector<word>& ws = ws_bn[0].get_word_vector();
189  secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
190 
191  BigInt& T0 = ws_bn[2];
192  BigInt& T1 = ws_bn[3];
193  BigInt& T2 = ws_bn[4];
194  BigInt& T3 = ws_bn[5];
195  BigInt& T4 = ws_bn[6];
196  BigInt& T5 = ws_bn[7];
197 
198  /*
199  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
200  */
201 
202  const BigInt& p = m_curve.get_p();
203 
204  m_curve.sqr(T0, z_words, z_size, ws); // z2^2
205  m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2
206  m_curve.mul(T3, z_words, z_size, T0, ws); // z2^3
207  m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3
208 
209  m_curve.sqr(T3, m_coord_z, ws); // z1^2
210  m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
211 
212  m_curve.mul(T5, m_coord_z, T3, ws); // z1^3
213  m_curve.mul(T0, y_words, y_size, T5, ws); // y2*z1^3
214 
215  T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2
216 
217  T0.mod_sub(T2, p, sub_ws);
218 
219  if(T4.is_zero())
220  {
221  if(T0.is_zero())
222  {
223  mult2(ws_bn);
224  return;
225  }
226 
227  // setting to zero:
228  m_coord_x = 0;
229  m_coord_y = m_curve.get_1_rep();
230  m_coord_z = 0;
231  return;
232  }
233 
234  m_curve.sqr(T5, T4, ws);
235 
236  m_curve.mul(T3, T1, T5, ws);
237 
238  m_curve.mul(T1, T5, T4, ws);
239 
240  m_curve.sqr(m_coord_x, T0, ws);
241  m_coord_x.mod_sub(T1, p, sub_ws);
242  m_coord_x.mod_sub(T3, p, sub_ws);
243  m_coord_x.mod_sub(T3, p, sub_ws);
244 
245  T3.mod_sub(m_coord_x, p, sub_ws);
246 
247  m_curve.mul(m_coord_y, T0, T3, ws);
248  m_curve.mul(T3, T2, T1, ws);
249 
250  m_coord_y.mod_sub(T3, p, sub_ws);
251 
252  m_curve.mul(T3, z_words, z_size, m_coord_z, ws);
253  m_curve.mul(m_coord_z, T3, T4, ws);
254  }
255 
256 void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn)
257  {
258  if(iterations == 0)
259  return;
260 
261  if(m_coord_y.is_zero())
262  {
263  *this = PointGFp(m_curve); // setting myself to zero
264  return;
265  }
266 
267  /*
268  TODO we can save 2 squarings per iteration by computing
269  a*Z^4 using values cached from previous iteration
270  */
271  for(size_t i = 0; i != iterations; ++i)
272  mult2(ws_bn);
273  }
274 
275 // *this *= 2
276 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
277  {
278  if(is_zero())
279  return;
280 
281  if(m_coord_y.is_zero())
282  {
283  *this = PointGFp(m_curve); // setting myself to zero
284  return;
285  }
286 
287  resize_ws(ws_bn, m_curve.get_ws_size());
288 
289  secure_vector<word>& ws = ws_bn[0].get_word_vector();
290  secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
291 
292  BigInt& T0 = ws_bn[2];
293  BigInt& T1 = ws_bn[3];
294  BigInt& T2 = ws_bn[4];
295  BigInt& T3 = ws_bn[5];
296  BigInt& T4 = ws_bn[6];
297 
298  /*
299  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
300  */
301  const BigInt& p = m_curve.get_p();
302 
303  m_curve.sqr(T0, m_coord_y, ws);
304 
305  m_curve.mul(T1, m_coord_x, T0, ws);
306  T1 <<= 2; // * 4
307  m_curve.redc_mod_p(T1, sub_ws);
308 
309  if(m_curve.a_is_zero())
310  {
311  // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
312  m_curve.sqr(T4, m_coord_x, ws); // x^2
313  T4 *= 3; // 3*x^2
314  m_curve.redc_mod_p(T4, sub_ws);
315  }
316  else if(m_curve.a_is_minus_3())
317  {
318  /*
319  if a == -3 then
320  3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2)
321  */
322  m_curve.sqr(T3, m_coord_z, ws); // z^2
323 
324  // (x-z^2)
325  T2 = m_coord_x;
326  T2.mod_sub(T3, p, sub_ws);
327 
328  // (x+z^2)
329  T3.mod_add(m_coord_x, p, sub_ws);
330 
331  m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)
332 
333  T4 *= 3; // 3*(x-z^2)*(x+z^2)
334  m_curve.redc_mod_p(T4, sub_ws);
335  }
336  else
337  {
338  m_curve.sqr(T3, m_coord_z, ws); // z^2
339  m_curve.sqr(T4, T3, ws); // z^4
340  m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4
341 
342  m_curve.sqr(T4, m_coord_x, ws); // x^2
343  T4 *= 3; // 3*x^2
344  T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
345  }
346 
347  m_curve.sqr(T2, T4, ws);
348  T2.mod_sub(T1, p, sub_ws);
349  T2.mod_sub(T1, p, sub_ws);
350 
351  m_curve.sqr(T3, T0, ws);
352  T3 <<= 3;
353  m_curve.redc_mod_p(T3, sub_ws);
354 
355  T1.mod_sub(T2, p, sub_ws);
356 
357  m_curve.mul(T0, T4, T1, ws);
358  T0.mod_sub(T3, p, sub_ws);
359 
360  m_coord_x = T2;
361 
362  m_curve.mul(T2, m_coord_y, m_coord_z, ws);
363  T2 <<= 1;
364  m_curve.redc_mod_p(T2, sub_ws);
365 
366  m_coord_y = T0;
367  m_coord_z = T2;
368  }
369 
370 // arithmetic operators
372  {
373  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
374  add(rhs, ws);
375  return *this;
376  }
377 
379  {
380  PointGFp minus_rhs = PointGFp(rhs).negate();
381 
382  if(is_zero())
383  *this = minus_rhs;
384  else
385  *this += minus_rhs;
386 
387  return *this;
388  }
389 
391  {
392  *this = scalar * *this;
393  return *this;
394  }
395 
396 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
397  {
399 
400  const size_t scalar_bits = scalar.bits();
401 
402  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
403 
404  PointGFp R[2] = { point.zero(), point };
405 
406  for(size_t i = scalar_bits; i > 0; i--)
407  {
408  const size_t b = scalar.get_bit(i - 1);
409  R[b ^ 1].add(R[b], ws);
410  R[b].mult2(ws);
411  }
412 
413  if(scalar.is_negative())
414  R[0].negate();
415 
416  BOTAN_DEBUG_ASSERT(R[0].on_the_curve());
417 
418  return R[0];
419  }
420 
421 //static
422 void PointGFp::force_all_affine(std::vector<PointGFp>& points,
424  {
425  if(points.size() <= 1)
426  {
427  for(size_t i = 0; i != points.size(); ++i)
428  points[i].force_affine();
429  return;
430  }
431 
432  /*
433  For >= 2 points use Montgomery's trick
434 
435  See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
436  (Hankerson, Menezes, Vanstone)
437 
438  TODO is it really necessary to save all k points in c?
439  */
440 
441  const CurveGFp& curve = points[0].m_curve;
442  const BigInt& rep_1 = curve.get_1_rep();
443 
444  if(ws.size() < curve.get_ws_size())
445  ws.resize(curve.get_ws_size());
446 
447  std::vector<BigInt> c(points.size());
448  c[0] = points[0].m_coord_z;
449 
450  for(size_t i = 1; i != points.size(); ++i)
451  {
452  curve.mul(c[i], c[i-1], points[i].m_coord_z, ws);
453  }
454 
455  BigInt s_inv = curve.invert_element(c[c.size()-1], ws);
456 
457  BigInt z_inv, z2_inv, z3_inv;
458 
459  for(size_t i = points.size() - 1; i != 0; i--)
460  {
461  PointGFp& point = points[i];
462 
463  curve.mul(z_inv, s_inv, c[i-1], ws);
464 
465  s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);
466 
467  curve.sqr(z2_inv, z_inv, ws);
468  curve.mul(z3_inv, z2_inv, z_inv, ws);
469  point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);
470  point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);
471  point.m_coord_z = rep_1;
472  }
473 
474  curve.sqr(z2_inv, s_inv, ws);
475  curve.mul(z3_inv, z2_inv, s_inv, ws);
476  points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
477  points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
478  points[0].m_coord_z = rep_1;
479  }
480 
482  {
483  if(is_zero())
484  throw Invalid_State("Cannot convert zero ECC point to affine");
485 
487 
488  const BigInt z_inv = m_curve.invert_element(m_coord_z, ws);
489  const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws);
490  const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
491  m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
492  m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
493  m_coord_z = m_curve.get_1_rep();
494  }
495 
497  {
498  return m_curve.is_one(m_coord_z);
499  }
500 
502  {
503  if(is_zero())
504  throw Illegal_Transformation("Cannot convert zero point to affine");
505 
506  secure_vector<word> monty_ws;
507 
508  if(is_affine())
509  return m_curve.from_rep(m_coord_x, monty_ws);
510 
511  BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
512  z2 = m_curve.invert_element(z2, monty_ws);
513 
514  BigInt r;
515  m_curve.mul(r, m_coord_x, z2, monty_ws);
516  m_curve.from_rep(r, monty_ws);
517  return r;
518  }
519 
521  {
522  if(is_zero())
523  throw Illegal_Transformation("Cannot convert zero point to affine");
524 
525  secure_vector<word> monty_ws;
526 
527  if(is_affine())
528  return m_curve.from_rep(m_coord_y, monty_ws);
529 
530  const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
531  const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
532  const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
533 
534  BigInt r;
535  m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
536  m_curve.from_rep(r, monty_ws);
537  return r;
538  }
539 
541  {
542  /*
543  Is the point still on the curve?? (If everything is correct, the
544  point is always on its curve; then the function will return true.
545  If somehow the state is corrupted, which suggests a fault attack
546  (or internal computational error), then return false.
547  */
548  if(is_zero())
549  return true;
550 
551  secure_vector<word> monty_ws;
552 
553  const BigInt y2 = m_curve.from_rep(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);
554  const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);
555  const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);
556  const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
557 
558  if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
559  {
560  if(y2 != m_curve.from_rep(x3 + ax + m_curve.get_b_rep(), monty_ws))
561  return false;
562  }
563 
564  const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
565  const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);
566  const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws);
567 
568  if(y2 != m_curve.from_rep(x3 + ax_z4 + b_z6, monty_ws))
569  return false;
570 
571  return true;
572  }
573 
574 // swaps the states of *this and other, does not throw!
576  {
577  m_curve.swap(other.m_curve);
578  m_coord_x.swap(other.m_coord_x);
579  m_coord_y.swap(other.m_coord_y);
580  m_coord_z.swap(other.m_coord_z);
581  }
582 
583 bool PointGFp::operator==(const PointGFp& other) const
584  {
585  if(m_curve != other.m_curve)
586  return false;
587 
588  // If this is zero, only equal if other is also zero
589  if(is_zero())
590  return other.is_zero();
591 
592  return (get_affine_x() == other.get_affine_x() &&
593  get_affine_y() == other.get_affine_y());
594  }
595 
596 // encoding and decoding
597 std::vector<uint8_t> PointGFp::encode(PointGFp::Compression_Type format) const
598  {
599  if(is_zero())
600  return std::vector<uint8_t>(1); // single 0 byte
601 
602  const size_t p_bytes = m_curve.get_p().bytes();
603 
604  const BigInt x = get_affine_x();
605  const BigInt y = get_affine_y();
606 
607  std::vector<uint8_t> result;
608 
609  if(format == PointGFp::UNCOMPRESSED)
610  {
611  result.resize(1 + 2*p_bytes);
612  result[0] = 0x04;
613  BigInt::encode_1363(&result[1], p_bytes, x);
614  BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
615  }
616  else if(format == PointGFp::COMPRESSED)
617  {
618  result.resize(1 + p_bytes);
619  result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));
620  BigInt::encode_1363(&result[1], p_bytes, x);
621  }
622  else if(format == PointGFp::HYBRID)
623  {
624  result.resize(1 + 2*p_bytes);
625  result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0));
626  BigInt::encode_1363(&result[1], p_bytes, x);
627  BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
628  }
629  else
630  throw Invalid_Argument("EC2OSP illegal point encoding");
631 
632  return result;
633  }
634 
635 namespace {
636 
637 BigInt decompress_point(bool yMod2,
638  const BigInt& x,
639  const BigInt& curve_p,
640  const BigInt& curve_a,
641  const BigInt& curve_b)
642  {
643  BigInt xpow3 = x * x * x;
644 
645  BigInt g = curve_a * x;
646  g += xpow3;
647  g += curve_b;
648  g = g % curve_p;
649 
650  BigInt z = ressol(g, curve_p);
651 
652  if(z < 0)
653  throw Illegal_Point("error during EC point decompression");
654 
655  if(z.get_bit(0) != yMod2)
656  z = curve_p - z;
657 
658  return z;
659  }
660 
661 }
662 
663 PointGFp OS2ECP(const uint8_t data[], size_t data_len,
664  const CurveGFp& curve)
665  {
666  // Should we really be doing this?
667  if(data_len <= 1)
668  return PointGFp(curve); // return zero
669 
670  std::pair<BigInt, BigInt> xy = OS2ECP(data, data_len, curve.get_p(), curve.get_a(), curve.get_b());
671 
672  PointGFp point(curve, xy.first, xy.second);
673 
674  if(!point.on_the_curve())
675  throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
676 
677  return point;
678  }
679 
680 std::pair<BigInt, BigInt> OS2ECP(const uint8_t data[], size_t data_len,
681  const BigInt& curve_p,
682  const BigInt& curve_a,
683  const BigInt& curve_b)
684  {
685  if(data_len <= 1)
686  throw Decoding_Error("OS2ECP invalid point");
687 
688  const uint8_t pc = data[0];
689 
690  BigInt x, y;
691 
692  if(pc == 2 || pc == 3)
693  {
694  //compressed form
695  x = BigInt::decode(&data[1], data_len - 1);
696 
697  const bool y_mod_2 = ((pc & 0x01) == 1);
698  y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b);
699  }
700  else if(pc == 4)
701  {
702  const size_t l = (data_len - 1) / 2;
703 
704  // uncompressed form
705  x = BigInt::decode(&data[1], l);
706  y = BigInt::decode(&data[l+1], l);
707  }
708  else if(pc == 6 || pc == 7)
709  {
710  const size_t l = (data_len - 1) / 2;
711 
712  // hybrid form
713  x = BigInt::decode(&data[1], l);
714  y = BigInt::decode(&data[l+1], l);
715 
716  const bool y_mod_2 = ((pc & 0x01) == 1);
717 
718  if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y)
719  throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
720  }
721  else
722  throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));
723 
724  return std::make_pair(x, y);
725  }
726 
727 }
bool get_bit(size_t n) const
Definition: bigint.h:404
bool a_is_minus_3() const
Definition: curve_gfp.h:145
const BigInt & get_a_rep() const
Definition: curve_gfp.h:139
bool is_negative() const
Definition: bigint.h:460
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:155
PointGFp & operator*=(const BigInt &scalar)
Definition: point_gfp.cpp:390
const BigInt & get_b_rep() const
Definition: curve_gfp.h:141
std::vector< uint8_t > encode(PointGFp::Compression_Type format) const
Definition: point_gfp.cpp:597
size_t bits() const
Definition: bigint.cpp:228
secure_vector< word > & get_word_vector()
Definition: bigint.h:553
void redc_mod_p(BigInt &z, secure_vector< word > &ws) const
Definition: curve_gfp.h:174
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:124
bool is_zero() const
Definition: bigint.h:355
BigInt ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
bool is_affine() const
Definition: point_gfp.cpp:496
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:210
void swap(BigInt &other)
Definition: bigint.h:150
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:179
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
void force_affine()
Definition: point_gfp.cpp:481
size_t get_ws_size() const
Definition: curve_gfp.h:137
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:218
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:160
BigInt get_affine_x() const
Definition: point_gfp.cpp:501
BigInt get_affine_y() const
Definition: point_gfp.cpp:520
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:43
const BigInt & get_1_rep() const
Definition: curve_gfp.h:143
void swap(PointGFp &other)
Definition: point_gfp.cpp:575
PointGFp zero() const
Definition: point_gfp.h:316
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:150
PointGFp()=default
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:111
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:42
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:256
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:112
bool is_one(const BigInt &x) const
Definition: curve_gfp.h:148
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:217
void set_words(const word w[], size_t len)
Definition: bigint.h:450
void swap(CurveGFp &other)
Definition: curve_gfp.h:224
Definition: alg_id.cpp:13
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:210
size_t bytes() const
Definition: bigint.cpp:220
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:276
const BigInt & get_b() const
Definition: curve_gfp.h:127
bool on_the_curve() const
Definition: point_gfp.cpp:540
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:251
const BigInt & get_a() const
Definition: curve_gfp.h:122
bool a_is_zero() const
Definition: curve_gfp.h:146
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:103
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:422
bool operator==(const PointGFp &other) const
Definition: point_gfp.cpp:583
bool is_zero() const
Definition: point_gfp.h:180
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
PointGFp & operator+=(const PointGFp &rhs)
Definition: point_gfp.cpp:371
const BigInt & get_p() const
Definition: curve_gfp.h:133
PointGFp & operator-=(const PointGFp &rhs)
Definition: point_gfp.cpp:378
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:190
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:663