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