1 /**
2 * Point arithmetic on elliptic curves over GF(p)
3 *
4 * Copyright:
5 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
6 * 2008-2011, 2014 Jack Lloyd
7 * (C) 2014-2015 Etienne Cimon
8 *
9 * License:
10 * Botan is released under the Simplified BSD License (see LICENSE.md)
11 */
12 module botan.math.ec_gfp.point_gfp;
13
14 import botan.constants;
15 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO):
16
17 import botan.constants;
18 import botan.math.ec_gfp.curve_gfp;
19 import botan.utils.types;
20 import botan.math.numbertheory.numthry;
21 import botan.math.numbertheory.reducer;
22 import botan.math.mp.mp_core;
23 import std.algorithm : max, swap;
24 import std.conv : to;
25
26 /**
27 * Exception thrown if you try to convert a zero point to an affine
28 * coordinate
29 */
30 class IllegalTransformation : Exception
31 {
32 this(in string err = "Requested transformation is not possible")
33 {
34 super(err);
35 }
36 }
37
38 /**
39 * Exception thrown if some form of illegal point is decoded
40 */
41 class IllegalPoint : Exception
42 {
43 this(in string err = "Malformed ECP point detected") { super(err); }
44 }
45
46
47 /**
48 * This class represents one point on a curve of GF(p)
49 */
50 struct PointGFp
51 {
52 public:
53 alias CompressionType = ubyte;
54 enum : CompressionType {
55 UNCOMPRESSED = 0,
56 COMPRESSED = 1,
57 HYBRID = 2
58 }
59
60 /**
61 * Construct the zero point
62 * Params:
63 * curve = The base curve
64 */
65 this()(auto const ref CurveGFp curve)
66 {
67 m_curve = curve.dup;
68 m_ws.resize(16);
69 m_coord_x = BigInt(0);
70 auto b1 = BigInt(1);
71 m_coord_y = b1.move;
72 m_coord_z = BigInt(0);
73 m_curve.toRep(m_coord_x, m_ws_ref);
74 m_curve.toRep(m_coord_y, m_ws_ref);
75 m_curve.toRep(m_coord_z, m_ws_ref);
76 }
77
78
79 /**
80 * Move Constructor
81 */
82 this()(auto ref PointGFp other)
83 {
84 m_curve = CurveGFp.init;
85 this.swap(other);
86 }
87
88 /**
89 * Move Assignment
90 */
91 ref PointGFp opAssign(PointGFp other)
92 {
93 this.swap(other);
94 return this;
95 }
96
97 /**
98 * Construct a point from its affine coordinates
99 * Params:
100 * curve = the base curve
101 * x = affine x coordinate
102 * y = affine y coordinate
103 */
104 this(const ref CurveGFp curve, const ref BigInt x, const ref BigInt y)
105 {
106 if (x <= 0 || x >= curve.getP())
107 throw new InvalidArgument("Invalid PointGFp affine x");
108 if (y <= 0 || y >= curve.getP())
109 throw new InvalidArgument("Invalid PointGFp affine y");
110 m_curve = curve.dup;
111 //m_ws.resize(2 * (curve.getPWords() + 2));
112 m_coord_x = x.dup;
113 m_coord_y = y.dup;
114 auto bi = BigInt(1);
115 m_coord_z = bi.move;
116 m_curve.toRep(m_coord_x, m_ws_ref);
117 m_curve.toRep(m_coord_y, m_ws_ref);
118 m_curve.toRep(m_coord_z, m_ws_ref);
119 }
120
121 /**
122 * += Operator
123 * Params:
124 * rhs = the PointGFp to add to the local value
125 * Returns: resulting PointGFp
126 */
127 void opOpAssign(string op)(const ref PointGFp rhs)
128 if (op == "+")
129 {
130 Vector!(RefCounted!BigInt) ws = Vector!(RefCounted!BigInt)(9);
131 add(rhs, ws);
132 }
133
134 /**
135 * -= Operator
136 * Params:
137 * rhs = the PointGFp to subtract from the local value
138 * Returns: resulting PointGFp
139 */
140 void opOpAssign(string op)(const ref PointGFp rhs)
141 if (op == "-")
142 {
143
144 if (isZero())
145 this.swap( PointGFp(rhs.dup).negate() );
146 else
147 this += PointGFp(rhs.dup).negate();
148
149 }
150
151 /**
152 * *= Operator
153 * Params:
154 * scalar = the PointGFp to multiply with this
155 * Returns: resulting PointGFp
156 */
157 void opOpAssign(string op)(auto const ref BigInt scalar)
158 if (op == "*")
159 {
160 this.swap(this * scalar);
161 }
162
163 /**
164 * Multiplication Operator
165 * Params:
166 * scalar = the scalar value
167 * Returns: scalar*point on the curve
168 */
169 PointGFp opBinary(string op)(auto const ref BigInt scalar) const
170 if (op == "*")
171 {
172 const PointGFp* point = &this;
173
174 if (scalar.isZero()) {
175 return PointGFp(point.getCurve()); // zero point
176 }
177 Vector!(RefCounted!BigInt) ws = Vector!(RefCounted!BigInt)(9);
178 if (scalar.abs() <= 2) // special cases for small values
179 {
180 ubyte value = scalar.abs().byteAt(0);
181
182 PointGFp result = point.dup;
183
184 if (value == 2)
185 result.mult2(ws);
186 if (scalar.isNegative())
187 result.negate();
188
189 return result.move();
190 }
191 const size_t scalar_bits = scalar.bits();
192
193
194 PointGFp x1 = PointGFp(m_curve);
195 PointGFp x2 = point.dup;
196
197 size_t bits_left = scalar_bits;
198
199 // Montgomery Ladder
200 while (bits_left)
201 {
202 const bool bit_set = scalar.getBit(bits_left - 1);
203
204 if (bit_set)
205 {
206 x1.add(x2, ws);
207 x2.mult2(ws);
208 }
209 else
210 {
211 x2.add(x1, ws);
212 x1.mult2(ws);
213 }
214
215 --bits_left;
216 }
217
218 if (scalar.isNegative())
219 x1.negate();
220
221 return x1.move;
222
223 }
224
225 /**
226 * Multiexponentiation
227 * Params:
228 * p1 = a point
229 * z1 = a scalar
230 * p2 = a point
231 * z2 = a scalar
232 * Returns: (p1 * z1 + p2 * z2)
233 */
234 static PointGFp multiExponentiate(const ref PointGFp p1, const ref BigInt z1,
235 const ref PointGFp p2, const ref BigInt z2)
236 {
237 const PointGFp p3 = p1 + p2;
238
239 PointGFp H = PointGFp(p1.m_curve); // create as zero
240 size_t bits_left = max(z1.bits(), z2.bits());
241
242 Vector!(RefCounted!BigInt) ws = Vector!(RefCounted!BigInt)(9);
243
244 while (bits_left)
245 {
246 H.mult2(ws);
247
248 const bool z1_b = z1.getBit(bits_left - 1);
249 const bool z2_b = z2.getBit(bits_left - 1);
250
251 if (z1_b == true && z2_b == true)
252 H.add(p3, ws);
253 else if (z1_b)
254 H.add(p1, ws);
255 else if (z2_b)
256 H.add(p2, ws);
257
258 --bits_left;
259 }
260
261 if (z1.isNegative() != z2.isNegative())
262 H.negate();
263
264 return H.move();
265 }
266
267 /**
268 * Negate this point
269 * Returns: this
270 */
271 ref PointGFp negate()
272 {
273 if (!isZero())
274 m_coord_y = m_curve.getP() - m_coord_y;
275 return this;
276 }
277
278 /**
279 * Return base curve of this point
280 * Returns: the curve over GF(p) of this point
281 */
282 ref const(CurveGFp) getCurve() const { return m_curve; }
283
284 /**
285 * get affine x coordinate
286 * Returns: affine x coordinate
287 */
288 BigInt getAffineX() const
289 {
290 if (isZero())
291 throw new IllegalTransformation("Cannot convert zero point to affine");
292
293 BigInt z2 = curveSqr(m_coord_z);
294 m_curve.fromRep(z2, m_ws_ref);
295 z2 = inverseMod(z2, m_curve.getP());
296
297 return curveMult(z2, m_coord_x);
298 }
299
300 /**
301 * get affine y coordinate
302 * Returns: affine y coordinate
303 */
304 BigInt getAffineY() const
305 {
306 if (isZero())
307 throw new IllegalTransformation("Cannot convert zero point to affine");
308
309 BigInt z3 = curveMult(m_coord_z, curveSqr(m_coord_z));
310 z3 = inverseMod(z3, m_curve.getP());
311 m_curve.toRep(z3, m_ws_ref);
312 return curveMult(z3, m_coord_y);
313 }
314
315 /**
316 * Is this the point at infinity?
317 * Returns: true, if this point is at infinity, false otherwise.
318 */
319 bool isZero() const
320 { return (m_coord_x.isZero() && m_coord_z.isZero()); }
321
322 /**
323 * Checks whether the point is to be found on the underlying
324 * curve; used to prevent fault attacks.
325 * Returns: if the point is on the curve
326 */
327 bool onTheCurve() const
328 {
329 /*
330 Is the point still on the curve?? (If everything is correct, the
331 point is always on its curve; then the function will return true.
332 If somehow the state is corrupted, which suggests a fault attack
333 (or internal computational error), then return false.
334 */
335 if (isZero()) {
336 return true;
337 }
338
339 BigInt y2 = m_curve.fromRep(curveSqr(m_coord_y), m_ws_ref);
340 BigInt x3 = curveMult(m_coord_x, curveSqr(m_coord_x));
341 BigInt ax = curveMult(m_coord_x, m_curve.getARep());
342 BigInt z2 = curveSqr(m_coord_z);
343
344 if (m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
345 {
346 if (y2 != m_curve.fromRep(x3 + ax + m_curve.getBRep(), m_ws_ref)) {
347 return false;
348 }
349 }
350
351 BigInt z3 = curveMult(m_coord_z, z2);
352 BigInt ax_z4 = curveMult(ax, curveSqr(z2));
353 BigInt b_z6 = curveMult(m_curve.getBRep(), curveSqr(z3));
354
355 if (y2 != m_curve.fromRep(x3 + ax_z4 + b_z6, m_ws_ref)) {
356 return false;
357 }
358 return true;
359 }
360
361
362 /**
363 * swaps the states of this and other, does not throw!
364 * Params:
365 * other = the object to swap values with
366 */
367 void swap()(auto ref PointGFp other)
368 {
369 m_curve.swap(other.m_curve);
370 m_coord_x.swap(other.m_coord_x);
371 m_coord_y.swap(other.m_coord_y);
372 m_coord_z.swap(other.m_coord_z);
373 m_ws.swap(other.m_ws);
374 }
375
376 @property PointGFp dup() const
377 {
378 auto point = PointGFp(m_curve);
379 point.m_coord_x = m_coord_x.dup;
380 point.m_coord_y = m_coord_y.dup;
381 point.m_coord_z = m_coord_z.dup;
382 point.m_ws = m_ws.dup;
383 return point;
384 }
385
386 /**
387 * Equality operator
388 */
389 bool opEquals(const ref PointGFp other) const
390 {
391 if (getCurve() != other.getCurve())
392 return false;
393
394 // If this is zero, only equal if other is also zero
395 if (isZero())
396 return other.isZero();
397
398 return (getAffineX() == other.getAffineX() &&
399 getAffineY() == other.getAffineY());
400 }
401
402 private:
403
404 /**
405 * Montgomery multiplication/reduction
406 * Params:
407 * x = first multiplicand
408 * y = second multiplicand
409 */
410 BigInt curveMult()(auto const ref BigInt x, auto const ref BigInt y) const
411 {
412 BigInt z = BigInt(0);
413 m_curve.mul(z, x, y, m_ws_ref);
414 return z.move();
415 }
416
417 /**
418 * Montgomery multiplication/reduction
419 * Params:
420 * z = output
421 * x = first multiplicand
422 * y = second multiplicand
423 */
424 void curveMult()(ref BigInt z, auto const ref BigInt x, auto const ref BigInt y) const
425 {
426 m_curve.mul(z, x, y, m_ws_ref);
427 }
428
429 /**
430 * Montgomery squaring/reduction
431 * Params:
432 * x = multiplicand
433 */
434 BigInt curveSqr()(auto const ref BigInt x) const
435 {
436 BigInt z;
437 m_curve.sqr(z, x, m_ws_ref);
438 return z.move();
439 }
440
441 /**
442 * Montgomery squaring/reduction
443 * Params:
444 * z = output
445 * x = multiplicand
446 */
447 void curveSqr()(ref BigInt z, auto const ref BigInt x) const
448 {
449 m_curve.sqr(z, x, m_ws_ref);
450 }
451
452 /**
453 * Point addition
454 * Params:
455 * workspace = temp space, at least 11 elements
456 */
457 void add()(auto const ref PointGFp rhs, ref Vector!(RefCounted!BigInt) ws_bn)
458 {
459 if (isZero())
460 {
461 m_coord_x = rhs.m_coord_x.dup;
462 m_coord_y = rhs.m_coord_y.dup;
463 m_coord_z = rhs.m_coord_z.dup;
464 return;
465 }
466 else if (rhs.isZero())
467 return;
468
469 const BigInt* p = &m_curve.getP();
470
471 BigInt* rhs_z2 = &*ws_bn[0];
472 BigInt* U1 = &*ws_bn[1];
473 BigInt* S1 = &*ws_bn[2];
474
475 BigInt* lhs_z2 = &*ws_bn[3];
476 BigInt* U2 = &*ws_bn[4];
477 BigInt* S2 = &*ws_bn[5];
478
479 BigInt* H = &*ws_bn[6];
480 BigInt* r = &*ws_bn[7];
481
482 curveSqr(*rhs_z2, rhs.m_coord_z);
483 curveMult(*U1, m_coord_x, *rhs_z2);
484 curveMult(*S1, m_coord_y, curveMult(rhs.m_coord_z, *rhs_z2));
485
486 curveSqr(*lhs_z2, m_coord_z);
487 curveMult(*U2, rhs.m_coord_x, *lhs_z2);
488 curveMult(*S2, rhs.m_coord_y, curveMult(m_coord_z, *lhs_z2));
489
490 *H = U2.dup;
491 *H -= *U1;
492 if (H.isNegative())
493 *H += *p;
494
495 *r = S2.dup;
496 *r -= *S1;
497 if (r.isNegative())
498 *r += *p;
499
500 if (H.isZero())
501 {
502 if (r.isZero())
503 {
504 mult2(ws_bn);
505 return;
506 }
507
508 this.swap( PointGFp(m_curve) ); // setting myself to zero
509 return;
510 }
511
512 curveSqr(*U2, *H);
513
514 curveMult(*S2, *U2, *H);
515
516 *U2 = curveMult(*U1, *U2);
517
518 curveSqr(m_coord_x, *r);
519 m_coord_x -= *S2;
520 m_coord_x -= (*U2 << 1);
521 while (m_coord_x.isNegative())
522 m_coord_x += *p;
523
524 *U2 -= m_coord_x;
525 if (U2.isNegative())
526 *U2 += *p;
527
528 curveMult(m_coord_y, *r, *U2);
529 m_coord_y -= curveMult(*S1, *S2);
530 if (m_coord_y.isNegative())
531 m_coord_y += *p;
532
533 curveMult(m_coord_z, curveMult(m_coord_z, rhs.m_coord_z), *H);
534 }
535
536
537 /**
538 * Point doubling
539 * Params:
540 * workspace = temp space, at least 9 elements
541 */
542 void mult2(ref Vector!(RefCounted!BigInt) ws_bn)
543 {
544 if (isZero())
545 return;
546 else if (m_coord_y.isZero())
547 {
548 this = PointGFp(m_curve); // setting myself to zero
549 return;
550 }
551
552 const BigInt* p = &m_curve.getP();
553
554 BigInt* y_2 = &*ws_bn[0];
555 BigInt* S = &*ws_bn[1];
556 BigInt* z4 = &*ws_bn[2];
557 BigInt* a_z4 = &*ws_bn[3];
558 BigInt* M = &*ws_bn[4];
559 BigInt* U = &*ws_bn[5];
560 BigInt* x = &*ws_bn[6];
561 BigInt* y = &*ws_bn[7];
562 BigInt* z = &*ws_bn[8];
563
564 curveSqr(*y_2, m_coord_y);
565
566 curveMult(*S, m_coord_x, *y_2);
567 *S <<= 2; // * 4
568 while (*S >= *p)
569 *S -= *p;
570
571 curveSqr(*z4, curveSqr(m_coord_z));
572 curveMult(*a_z4, m_curve.getARep(), *z4);
573
574 *M = curveSqr(m_coord_x);
575 *M *= 3;
576 *M += *a_z4;
577 while (*M >= *p)
578 *M -= *p;
579
580 curveSqr(*x, *M);
581 *x -= (*S << 1);
582 while (x.isNegative())
583 *x += *p;
584
585 curveSqr(*U, *y_2);
586 *U <<= 3;
587 while (*U >= *p)
588 *U -= *p;
589
590 *S -= *x;
591 while (S.isNegative())
592 *S += *p;
593
594 curveMult(*y, *M, *S);
595 *y -= *U;
596 if (y.isNegative())
597 *y += *p;
598
599 curveMult(*z, m_coord_y, m_coord_z);
600 *z <<= 1;
601 if (*z >= *p)
602 *z -= *p;
603
604 m_coord_x = (*x).dup;
605 m_coord_y = (*y).dup;
606 m_coord_z = (*z).dup;
607 }
608 public:
609 // relational operators
610 int opCmp(const ref PointGFp rhs) const
611 {
612 if (this == rhs) return 0;
613 else return -1;
614 }
615
616 // arithmetic operators
617 PointGFp opUnary(string op)() const
618 if (op == "-")
619 {
620 PointGFp ret = this.dup;
621 return ret.negate().dup;
622 }
623
624 PointGFp opBinary(string op)(auto const ref PointGFp rhs) const
625 if (op == "+")
626 {
627 PointGFp ret = this.dup;
628 ret += rhs;
629 return ret;
630 }
631
632 PointGFp opBinary(string op)(auto const ref PointGFp rhs) const
633 if (op == "-")
634 {
635 PointGFp ret = this.dup;
636 ret -= rhs;
637 return ret;
638 }
639
640 PointGFp opBinary(string op)(auto const ref PointGFp point) const
641 if (op == "*")
642 {
643 PointGFp ret = this.dup;
644 ret *= point;
645 return ret;
646 }
647
648 @disable this(this);
649
650 public Vector!char toVector() const {
651 Vector!char ret;
652 ret ~= "m_curve: ";
653 ret ~= m_curve.toVector()[];
654 ret ~= "\nm_coord_x: ";
655 ret ~= m_coord_x.toVector()[];
656 ret ~= "\nm_coord_y: ";
657 ret ~= m_coord_y.toVector()[];
658 ret ~= "\nm_coord_z: ";
659 ret ~= m_coord_z.toVector()[];
660 ret ~= "\nm_ws: ";
661 ret ~= m_ws.ptr[0 .. m_ws.length].to!string;
662 return ret.move;
663 }
664
665 public string toString() const {
666 return toVector()[].idup;
667 }
668
669 public PointGFp move() {
670 return PointGFp(this);
671 }
672
673 CurveGFp m_curve;
674 BigInt m_coord_x, m_coord_y, m_coord_z;
675 SecureVector!word m_ws; // workspace for Montgomery
676 @property SecureVector!word* m_ws_ref() const { return cast(mutable)&m_ws; }
677 alias mutable = SecureVector!word*;
678 }
679
680 // encoding and decoding
681 SecureVector!ubyte EC2OSP(const ref PointGFp point, ubyte format)
682 {
683 if (point.isZero())
684 return SecureVector!ubyte(1); // single 0 ubyte
685
686 const size_t p_bytes = point.getCurve().getP().bytes();
687
688 BigInt x = point.getAffineX();
689 BigInt y = point.getAffineY();
690
691 SecureVector!ubyte bX = BigInt.encode1363(x, p_bytes);
692 SecureVector!ubyte bY = BigInt.encode1363(y, p_bytes);
693
694 if (format == PointGFp.UNCOMPRESSED)
695 {
696 SecureVector!ubyte result;
697 result.pushBack(0x04);
698
699 result ~= bX[];
700 result ~= bY[];
701
702 return result.move();
703 }
704 else if (format == PointGFp.COMPRESSED)
705 {
706 SecureVector!ubyte result;
707 result.pushBack(0x02 | cast(ubyte)(y.getBit(0)));
708
709 result ~= bX[];
710
711 return result.move();
712 }
713 else if (format == PointGFp.HYBRID)
714 {
715 SecureVector!ubyte result;
716 result.pushBack(0x06 | cast(ubyte)(y.getBit(0)));
717
718 result ~= bX[];
719 result ~= bY[];
720
721 return result.move();
722 }
723 else
724 throw new InvalidArgument("EC2OSP illegal point encoding");
725 }
726
727 PointGFp OS2ECP()(const(ubyte)* data, size_t data_len, auto const ref CurveGFp curve)
728 {
729 if (data_len <= 1) {
730 return PointGFp(curve); // return zero
731 }
732 const ubyte pc = data[0];
733 BigInt x, y;
734
735 if (pc == 2 || pc == 3)
736 {
737 //compressed form
738 x = BigInt.decode(&data[1], data_len - 1);
739
740 const bool y_mod_2 = ((pc & 0x01) == 1);
741 y = decompressPoint(y_mod_2, x, curve);
742 }
743 else if (pc == 4)
744 {
745 const size_t l = (data_len - 1) / 2;
746
747 // uncompressed form
748 x = BigInt.decode(&data[1], l);
749 y = BigInt.decode(&data[l+1], l);
750 }
751 else if (pc == 6 || pc == 7)
752 {
753 const size_t l = (data_len - 1) / 2;
754
755 // hybrid form
756 x = BigInt.decode(&data[1], l);
757 y = BigInt.decode(&data[l+1], l);
758
759 const bool y_mod_2 = ((pc & 0x01) == 1);
760
761 if (decompressPoint(y_mod_2, x, curve) != y)
762 throw new IllegalPoint("OS2ECP: Decoding error in hybrid format");
763 }
764 else
765 throw new InvalidArgument("OS2ECP: Unknown format type " ~ to!string(pc));
766 PointGFp result = PointGFp(curve, x, y);
767 if (!result.onTheCurve())
768 throw new IllegalPoint("OS2ECP: Decoded point was not on the curve");
769 return result.move();
770 }
771
772 PointGFp OS2ECP(Alloc)(auto const ref Vector!( ubyte, Alloc ) data, auto const ref CurveGFp curve)
773 { return OS2ECP(data.ptr, data.length, curve); }
774
775 private:
776
777 BigInt decompressPoint(bool yMod2,
778 ref BigInt x,
779 const ref CurveGFp curve)
780 {
781 BigInt xpow3 = x * x * x;
782
783 const BigInt* p = &curve.getP();
784
785 BigInt g = curve.getA() * x;
786 g += xpow3;
787 g += curve.getB();
788 g = g % (*p);
789
790 BigInt z = ressol(g, *p);
791
792 if (z < 0)
793 throw new IllegalPoint("error during EC point decompression");
794
795 if (z.getBit(0) != yMod2)
796 z = *p - z;
797 return z;
798 }