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