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 }