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