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
PointGFp(const CurveGFp & curve)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
PointGFp(const CurveGFp & curve,const BigInt & x,const BigInt & y)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
randomize_repr(RandomNumberGenerator & rng)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
randomize_repr(RandomNumberGenerator & rng,secure_vector<word> & ws)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
resize_ws(std::vector<BigInt> & ws_bn,size_t cap_size)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
all_zeros(const word x[],size_t len)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
add_affine(const word x_words[],size_t x_size,const word y_words[],size_t y_size,std::vector<BigInt> & ws_bn)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
add(const word x_words[],size_t x_size,const word y_words[],size_t y_size,const word z_words[],size_t z_size,std::vector<BigInt> & ws_bn)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
mult2i(size_t iterations,std::vector<BigInt> & ws_bn)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
mult2(std::vector<BigInt> & ws_bn)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
operator +=(const PointGFp & rhs)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
operator -=(const PointGFp & rhs)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
operator *=(const BigInt & scalar)388 PointGFp& PointGFp::operator*=(const BigInt& scalar)
389 {
390 *this = scalar * *this;
391 return *this;
392 }
393
operator *(const BigInt & scalar,const PointGFp & point)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
force_all_affine(std::vector<PointGFp> & points,secure_vector<word> & ws)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 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
force_affine()485 void PointGFp::force_affine()
486 {
487 if(is_zero())
488 throw Invalid_State("Cannot convert zero ECC point to affine");
489
490 secure_vector<word> ws;
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
is_affine() const500 bool PointGFp::is_affine() const
501 {
502 return m_curve.is_one(m_coord_z);
503 }
504
get_affine_x() const505 BigInt PointGFp::get_affine_x() const
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
get_affine_y() const524 BigInt PointGFp::get_affine_y() const
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
on_the_curve() const544 bool PointGFp::on_the_curve() const
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!
swap(PointGFp & other)579 void PointGFp::swap(PointGFp& other)
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
operator ==(const PointGFp & other) const587 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
encode(PointGFp::Compression_Type format) const601 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
decompress_point(bool yMod2,const BigInt & x,const BigInt & curve_p,const BigInt & curve_a,const BigInt & curve_b)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
OS2ECP(const uint8_t data[],size_t data_len,const CurveGFp & curve)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
OS2ECP(const uint8_t data[],size_t data_len,const BigInt & curve_p,const BigInt & curve_a,const BigInt & curve_b)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 }
732