Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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
18 PointGFp::PointGFp(const CurveGFp& curve) :
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
43 void PointGFp::randomize_repr(RandomNumberGenerator& rng)
44 {
45 secure_vector<word> ws(m_curve.get_ws_size());
46 randomize_repr(rng, ws);
47 }
48
49 void PointGFp::randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws)
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
369 PointGFp& PointGFp::operator+=(const PointGFp& rhs)
370 {
371 std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
372 add(rhs, ws);
373 return *this;
374 }
375
376 PointGFp& PointGFp::operator-=(const PointGFp& rhs)
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
388 PointGFp& PointGFp::operator*=(const BigInt& scalar)
389 {
390 *this = scalar * *this;
391 return *this;
392 }
393
394 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
395 {
396 BOTAN_DEBUG_ASSERT(point.on_the_curve());
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,
421 secure_vector<word>& ws)
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 /*
431 For >= 2 points use Montgomery's trick
432
433 See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
434 (Hankerson, Menezes, Vanstone)
435
436 TODO is it really necessary to save all k points in c?
437 */
438
439 const CurveGFp& curve = points[0].m_curve;
440 const BigInt& rep_1 = curve.get_1_rep();
441
442 if(ws.size() < curve.get_ws_size())
443 ws.resize(curve.get_ws_size());
444
445 std::vector<BigInt> c(points.size());
446 c[0] = points[0].m_coord_z;
447
448 for(size_t i = 1; i != points.size(); ++i)
449 {
450 curve.mul(c[i], c[i-1], points[i].m_coord_z, ws);
451 }
452
453 BigInt s_inv = curve.invert_element(c[c.size()-1], ws);
454
455 BigInt z_inv, z2_inv, z3_inv;
456
457 for(size_t i = points.size() - 1; i != 0; i--)
458 {
459 PointGFp& point = points[i];
460
461 curve.mul(z_inv, s_inv, c[i-1], ws);
462
463 s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);
464
465 curve.sqr(z2_inv, z_inv, ws);
466 curve.mul(z3_inv, z2_inv, z_inv, ws);
467 point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);
468 point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);
469 point.m_coord_z = rep_1;
470 }
471
472 curve.sqr(z2_inv, s_inv, ws);
473 curve.mul(z3_inv, z2_inv, s_inv, ws);
474 points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
475 points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
476 points[0].m_coord_z = rep_1;
477 }
478
479 void PointGFp::force_affine()
480 {
481 if(is_zero())
482 throw Invalid_State("Cannot convert zero ECC point to affine");
483
484 secure_vector<word> ws;
485
486 const BigInt z_inv = m_curve.invert_element(m_coord_z, ws);
487 const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws);
488 const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
489 m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
490 m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
491 m_coord_z = m_curve.get_1_rep();
492 }
493
494 bool PointGFp::is_affine() const
495 {
496 return m_curve.is_one(m_coord_z);
497 }
498
499 BigInt PointGFp::get_affine_x() const
500 {
501 if(is_zero())
502 throw Illegal_Transformation("Cannot convert zero point to affine");
503
504 secure_vector<word> monty_ws;
505
506 if(is_affine())
507 return m_curve.from_rep_to_tmp(m_coord_x, monty_ws);
508
509 BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
510 z2 = m_curve.invert_element(z2, monty_ws);
511
512 BigInt r;
513 m_curve.mul(r, m_coord_x, z2, monty_ws);
514 m_curve.from_rep(r, monty_ws);
515 return r;
516 }
517
518 BigInt PointGFp::get_affine_y() const
519 {
520 if(is_zero())
521 throw Illegal_Transformation("Cannot convert zero point to affine");
522
523 secure_vector<word> monty_ws;
524
525 if(is_affine())
526 return m_curve.from_rep_to_tmp(m_coord_y, monty_ws);
527
528 const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
529 const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
530 const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
531
532 BigInt r;
533 m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
534 m_curve.from_rep(r, monty_ws);
535 return r;
536 }
537
538 bool PointGFp::on_the_curve() const
539 {
540 /*
541 Is the point still on the curve?? (If everything is correct, the
542 point is always on its curve; then the function will return true.
543 If somehow the state is corrupted, which suggests a fault attack
544 (or internal computational error), then return false.
545 */
546 if(is_zero())
547 return true;
548
549 secure_vector<word> monty_ws;
550
551 const BigInt y2 = m_curve.from_rep_to_tmp(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);
552 const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);
553 const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);
554 const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
555
556 if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
557 {
558 if(y2 != m_curve.from_rep_to_tmp(x3 + ax + m_curve.get_b_rep(), monty_ws))
559 return false;
560 }
561
562 const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
563 const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);
564 const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws);
565
566 if(y2 != m_curve.from_rep_to_tmp(x3 + ax_z4 + b_z6, monty_ws))
567 return false;
568
569 return true;
570 }
571
572 // swaps the states of *this and other, does not throw!
573 void PointGFp::swap(PointGFp& other)
574 {
575 m_curve.swap(other.m_curve);
576 m_coord_x.swap(other.m_coord_x);
577 m_coord_y.swap(other.m_coord_y);
578 m_coord_z.swap(other.m_coord_z);
579 }
580
581 bool PointGFp::operator==(const PointGFp& other) const
582 {
583 if(m_curve != other.m_curve)
584 return false;
585
586 // If this is zero, only equal if other is also zero
587 if(is_zero())
588 return other.is_zero();
589
590 return (get_affine_x() == other.get_affine_x() &&
591 get_affine_y() == other.get_affine_y());
592 }
593
594 // encoding and decoding
595 std::vector<uint8_t> PointGFp::encode(PointGFp::Compression_Type format) const
596 {
597 if(is_zero())
598 return std::vector<uint8_t>(1); // single 0 byte
599
600 const size_t p_bytes = m_curve.get_p().bytes();
601
602 const BigInt x = get_affine_x();
603 const BigInt y = get_affine_y();
604
605 std::vector<uint8_t> result;
606
607 if(format == PointGFp::UNCOMPRESSED)
608 {
609 result.resize(1 + 2*p_bytes);
610 result[0] = 0x04;
611 BigInt::encode_1363(&result[1], p_bytes, x);
612 BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
613 }
614 else if(format == PointGFp::COMPRESSED)
615 {
616 result.resize(1 + p_bytes);
617 result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));
618 BigInt::encode_1363(&result[1], p_bytes, x);
619 }
620 else if(format == PointGFp::HYBRID)
621 {
622 result.resize(1 + 2*p_bytes);
623 result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0));
624 BigInt::encode_1363(&result[1], p_bytes, x);
625 BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
626 }
627 else
628 throw Invalid_Argument("EC2OSP illegal point encoding");
629
630 return result;
631 }
632
633 namespace {
634
635 BigInt decompress_point(bool yMod2,
636 const BigInt& x,
637 const BigInt& curve_p,
638 const BigInt& curve_a,
639 const BigInt& curve_b)
640 {
641 BigInt xpow3 = x * x * x;
642
643 BigInt g = curve_a * x;
644 g += xpow3;
645 g += curve_b;
646 g = g % curve_p;
647
648 BigInt z = ressol(g, curve_p);
649
650 if(z < 0)
651 throw Illegal_Point("error during EC point decompression");
652
653 if(z.get_bit(0) != yMod2)
654 z = curve_p - z;
655
656 return z;
657 }
658
659 }
660
661 PointGFp OS2ECP(const uint8_t data[], size_t data_len,
662 const CurveGFp& curve)
663 {
664 // Should we really be doing this?
665 if(data_len <= 1)
666 return PointGFp(curve); // return zero
667
668 std::pair<BigInt, BigInt> xy = OS2ECP(data, data_len, curve.get_p(), curve.get_a(), curve.get_b());
669
670 PointGFp point(curve, xy.first, xy.second);
671
672 if(!point.on_the_curve())
673 throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
674
675 return point;
676 }
677
678 std::pair<BigInt, BigInt> OS2ECP(const uint8_t data[], size_t data_len,
679 const BigInt& curve_p,
680 const BigInt& curve_a,
681 const BigInt& curve_b)
682 {
683 if(data_len <= 1)
684 throw Decoding_Error("OS2ECP invalid point");
685
686 const uint8_t pc = data[0];
687
688 BigInt x, y;
689
690 if(pc == 2 || pc == 3)
691 {
692 //compressed form
693 x = BigInt::decode(&data[1], data_len - 1);
694
695 const bool y_mod_2 = ((pc & 0x01) == 1);
696 y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b);
697 }
698 else if(pc == 4)
699 {
700 const size_t l = (data_len - 1) / 2;
701
702 // uncompressed form
703 x = BigInt::decode(&data[1], l);
704 y = BigInt::decode(&data[l+1], l);
705 }
706 else if(pc == 6 || pc == 7)
707 {
708 const size_t l = (data_len - 1) / 2;
709
710 // hybrid form
711 x = BigInt::decode(&data[1], l);
712 y = BigInt::decode(&data[l+1], l);
713
714 const bool y_mod_2 = ((pc & 0x01) == 1);
715
716 if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y)
717 throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
718 }
719 else
720 throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));
721
722 return std::make_pair(x, y);
723 }
724
725 }
Botan::CurveGFp::get_a
const BigInt & get_a() const
Definition: curve_gfp.h:123
Botan::CurveGFp::sqr
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:186
Botan::PointGFp::COMPRESSED
Definition: point_gfp.h:52
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::CurveGFp::is_one
bool is_one(const BigInt &x) const
Definition: curve_gfp.h:149
Botan::Illegal_Transformation
Definition: point_gfp.h:26
Botan::PointGFp::UNCOMPRESSED
Definition: point_gfp.h:51
Botan::BigInt
Definition: bigint.h:24
Botan::PointGFp::get_affine_y
BigInt get_affine_y() const
Definition: point_gfp.cpp:518
Botan::PointGFp::is_affine
bool is_affine() const
Definition: point_gfp.cpp:494
Botan::PointGFp::operator*=
PointGFp & operator*=(const BigInt &scalar)
Definition: point_gfp.cpp:388
Botan::PointGFp
Definition: point_gfp.h:47
Botan::RandomNumberGenerator
Definition: rng.h:24
Botan::BigInt::resize
void resize(size_t s)
Definition: bigint.h:645
Botan::CurveGFp::get_b
const BigInt & get_b() const
Definition: curve_gfp.h:128
Botan::BigInt::get_word_vector
secure_vector< word > & get_word_vector()
Definition: bigint.h:623
Botan::BigInt::mod_sub
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
Botan::PointGFp::operator==
bool operator==(const PointGFp &other) const
Definition: point_gfp.cpp:581
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:525
Botan::ressol
BigInt ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
Botan::CurveGFp::get_a_rep
const BigInt & get_a_rep() const
Definition: curve_gfp.h:140
Botan::ASN1::to_string
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
Botan::BigInt::swap
void swap(BigInt &other)
Definition: bigint.h:159
Botan::BigInt::random_integer
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
Botan::PointGFp::force_affine
void force_affine()
Definition: point_gfp.cpp:479
Botan::PointGFp::WORKSPACE_SIZE
Definition: point_gfp.h:56
Botan::PointGFp::add
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:221
Botan::PointGFp::Compression_Type
Compression_Type
Definition: point_gfp.h:50
Botan::CurveGFp::a_is_zero
bool a_is_zero() const
Definition: curve_gfp.h:147
Botan::CurveGFp::get_ws_size
size_t get_ws_size() const
Definition: curve_gfp.h:138
Botan::CurveGFp::invert_element
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:151
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
Botan::Decoding_Error
Definition: exceptn.h:199
Botan::PointGFp::get_affine_x
BigInt get_affine_x() const
Definition: point_gfp.cpp:499
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:288
Botan::PointGFp::swap
void swap(PointGFp &other)
Definition: point_gfp.cpp:573
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
Botan::PointGFp::PointGFp
PointGFp()=default
Botan::CurveGFp::to_rep
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:156
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::PointGFp::randomize_repr
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:43
Botan::PointGFp::mult2i
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:259
Botan::BigInt::mod_add
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
Botan::CurveGFp::from_rep
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:161
Botan::CurveGFp::a_is_minus_3
bool a_is_minus_3() const
Definition: curve_gfp.h:146
Botan::PointGFp::zero
PointGFp zero() const
Definition: point_gfp.h:319
Botan::CurveGFp::get_b_rep
const BigInt & get_b_rep() const
Definition: curve_gfp.h:142
Botan::BigInt::set_words
void set_words(const word w[], size_t len)
Definition: bigint.h:516
Botan::PointGFp::HYBRID
Definition: point_gfp.h:53
Botan::Illegal_Point
Definition: point_gfp.h:38
Botan::CurveGFp::swap
void swap(CurveGFp &other)
Definition: curve_gfp.h:220
Botan
Definition: alg_id.cpp:13
Botan::PointGFp::mult2
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
Botan::BigInt::mod_mul
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:139
Botan::BigInt::clear
void clear()
Definition: bigint.h:364
Botan::PointGFp::add_affine
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:254
Botan::CurveGFp::get_p
const BigInt & get_p() const
Definition: curve_gfp.h:134
Botan::operator*
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
Botan::Invalid_State
Definition: exceptn.h:215
Botan::BigInt::decode
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:798
Botan::PointGFp::force_all_affine
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:420
Botan::CurveGFp::from_rep_to_tmp
BigInt from_rep_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:166
Botan::PointGFp::on_the_curve
bool on_the_curve() const
Definition: point_gfp.cpp:538
Botan::CurveGFp::mul_to_tmp
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:206
Botan::BigInt::encode_1363
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:111
Botan::PointGFp::is_zero
bool is_zero() const
Definition: point_gfp.h:184
Botan::BigInt::get_bit
bool get_bit(size_t n) const
Definition: bigint.h:463
Botan::PointGFp::operator+=
PointGFp & operator+=(const PointGFp &rhs)
Definition: point_gfp.cpp:369
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:419
Botan::CurveGFp::get_1_rep
const BigInt & get_1_rep() const
Definition: curve_gfp.h:144
Botan::CT::Mask::is_zero
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
Botan::PointGFp::encode
std::vector< uint8_t > encode(PointGFp::Compression_Type format) const
Definition: point_gfp.cpp:595
Botan::PointGFp::operator-=
PointGFp & operator-=(const PointGFp &rhs)
Definition: point_gfp.cpp:376
Botan::CurveGFp::mul
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:175
Botan::CurveGFp::sqr_to_tmp
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:213
Botan::OS2ECP
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
Definition: point_gfp.cpp:661
Botan::CurveGFp
Definition: curve_gfp.h:96
Botan::BigInt::bytes
size_t bytes() const
Definition: bigint.cpp:273