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.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()(PointGFp* other) 83 { 84 m_curve = CurveGFp.init; 85 swap(other); 86 } 87 88 /** 89 * Move Assignment 90 */ 91 ref PointGFp opAssign(PointGFp* other) 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.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 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.dup; 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.dup; 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.dup; 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.dup; 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 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().dup; 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 dup() const 399 { 400 auto point = PointGFp(m_curve); 401 point.m_coord_x = m_coord_x.dup; 402 point.m_coord_y = m_coord_y.dup; 403 point.m_coord_z = m_coord_z.dup; 404 point.m_ws = m_ws.dup; 405 return point; 406 } 407 408 /** 409 * Equality operator 410 */ 411 bool opEquals(const ref PointGFp other) const 412 { 413 if (getCurve() != other.getCurve()) 414 return false; 415 416 // If this is zero, only equal if other is also zero 417 if (isZero()) 418 return other.isZero(); 419 420 return (getAffineX() == other.getAffineX() && 421 getAffineY() == other.getAffineY()); 422 } 423 424 private: 425 426 /** 427 * Montgomery multiplication/reduction 428 * Params: 429 * x = first multiplicand 430 * y = second multiplicand 431 */ 432 BigInt curveMult()(const(BigInt)* x, const(BigInt*) y) const 433 { 434 BigInt z = BigInt(0); 435 m_curve.mul(&z, x, y, m_ws_const.move()); 436 return z.move(); 437 } 438 439 /** 440 * Montgomery multiplication/reduction 441 * Params: 442 * z = output 443 * x = first multiplicand 444 * y = second multiplicand 445 */ 446 void curveMult()(BigInt* z, const(BigInt)* x, const(BigInt*) y) const 447 { 448 m_curve.mul(z, x, y, m_ws_const.move()); 449 } 450 451 /** 452 * Montgomery squaring/reduction 453 * Params: 454 * x = multiplicand 455 */ 456 BigInt curveSqr()(const(BigInt)* x) const 457 { 458 BigInt z; 459 m_curve.sqr(&z, x, m_ws_const.move()); 460 return z.move(); 461 } 462 463 /** 464 * Montgomery squaring/reduction 465 * Params: 466 * z = output 467 * x = multiplicand 468 */ 469 void curveSqr(T, U)(T* z, U* x) const 470 if (!isPointer!T && !isPointer!U) 471 { 472 m_curve.sqr(z, x, m_ws_const.move()); 473 } 474 475 /** 476 * Point addition 477 * Params: 478 * workspace = temp space, at least 11 elements 479 */ 480 void add(const ref PointGFp rhs, ref Vector!(RefCounted!BigInt) ws_bn) 481 { 482 if (isZero()) 483 { 484 m_coord_x = rhs.m_coord_x.dup; 485 m_coord_y = rhs.m_coord_y.dup; 486 m_coord_z = rhs.m_coord_z.dup; 487 return; 488 } 489 else if (rhs.isZero()) 490 return; 491 const BigInt* p = &m_curve.getP(); 492 auto rhs_z = cast(BigInt*) &rhs.m_coord_z; 493 auto rhs_z2 = cast(BigInt*)&*(ws_bn[0]); 494 auto U1 = cast(BigInt*) &*(ws_bn[1]); 495 auto S1 = cast(BigInt*) &*(ws_bn[2]); 496 497 auto lhs_z2 = cast(BigInt*) &*(ws_bn[3]); 498 auto U2 = cast(BigInt*) &*(ws_bn[4]); 499 auto S2 = cast(BigInt*) &*(ws_bn[5]); 500 501 auto H = cast(BigInt*) &*(ws_bn[6]); 502 auto r = cast(BigInt*) &*(ws_bn[7]); 503 *U2 = BigInt(0); 504 curveSqr(rhs_z2, &rhs.m_coord_z); 505 curveMult(U1, &m_coord_x, rhs_z2); 506 auto mult_0 = curveMult(&rhs.m_coord_z, rhs_z2); 507 curveMult(S1, &m_coord_y, &mult_0); 508 509 curveSqr(lhs_z2, &m_coord_z); 510 curveMult(U2, &rhs.m_coord_x, lhs_z2); 511 auto mult_1 = curveMult(&m_coord_z, lhs_z2); 512 curveMult(S2, &rhs.m_coord_y, &mult_1); 513 514 *H = U2.dup; 515 *H -= *U1; 516 517 if (H.isNegative()) 518 *H += *p; 519 520 *r = S2.dup; 521 *r -= *S1; 522 if (r.isNegative()) 523 *r += *p; 524 525 if (H.isZero()) 526 { 527 if (r.isZero()) 528 { 529 mult2(ws_bn); 530 return; 531 } 532 533 this.swap( PointGFp(m_curve) ); // setting myself to zero 534 return; 535 } 536 537 curveSqr(U2, H); 538 539 curveMult(S2, U2, H); 540 541 *U2 = curveMult(U1, U2); 542 543 curveSqr(&m_coord_x, r); 544 m_coord_x -= *S2; 545 m_coord_x -= (*U2 << 1); 546 while (m_coord_x.isNegative()) 547 m_coord_x += *p; 548 549 *U2 -= m_coord_x; 550 if (U2.isNegative()) 551 *U2 += *p; 552 553 curveMult(&m_coord_y, r, U2); 554 m_coord_y -= curveMult(S1, S2); 555 if (m_coord_y.isNegative()) 556 m_coord_y += *p; 557 558 auto mult_3 = curveMult(&m_coord_z, rhs_z); 559 curveMult(&m_coord_z, &mult_3, H); 560 } 561 562 563 /** 564 * Point doubling 565 * Params: 566 * workspace = temp space, at least 9 elements 567 */ 568 void mult2(ref Vector!(RefCounted!BigInt) ws_bn) 569 { 570 if (isZero()) 571 return; 572 else if (m_coord_y.isZero()) 573 { 574 this = PointGFp(m_curve); // setting myself to zero 575 return; 576 } 577 const BigInt* p = &m_curve.getP(); 578 logTrace(""); 579 auto y_2 = cast(BigInt*) &*(ws_bn[0]); 580 auto S = cast(BigInt*) &*(ws_bn[1]); 581 auto z4 = cast(BigInt*) &*(ws_bn[2]); 582 auto a_z4 = cast(BigInt*) &*(ws_bn[3]); 583 auto M = cast(BigInt*) &*(ws_bn[4]); 584 auto U = cast(BigInt*) &*(ws_bn[5]); 585 auto x = cast(BigInt*) &*(ws_bn[6]); 586 auto y = cast(BigInt*) &*(ws_bn[7]); 587 auto z = cast(BigInt*) &*(ws_bn[8]); 588 589 curveSqr(y_2, &m_coord_y); 590 591 curveMult(S, &m_coord_x, y_2); 592 *S <<= 2; // * 4 593 while (*S >= *p) 594 *S -= *p; 595 596 auto sqr_1 = cast(BigInt) curveSqr(&m_coord_z); 597 curveSqr(z4, &sqr_1); 598 auto a_rep = m_curve.getARep().dup; 599 curveMult(a_z4, &a_rep, z4); 600 601 *M = curveSqr(&m_coord_x); 602 *M *= 3; 603 *M += *a_z4; 604 while (*M >= *p) 605 *M -= *p; 606 607 curveSqr(x, M); 608 *x -= (*S << 1); 609 while (x.isNegative()) 610 *x += *p; 611 612 curveSqr(U, y_2); 613 *U <<= 3; 614 while (*U >= *p) 615 *U -= *p; 616 617 *S -= *x; 618 while (S.isNegative()) 619 *S += *p; 620 621 curveMult(y, M, S); 622 *y -= *U; 623 if (y.isNegative()) 624 *y += *p; 625 626 curveMult(z, &m_coord_y, &m_coord_z); 627 *z <<= 1; 628 if (*z >= *p) 629 *z -= *p; 630 631 m_coord_x = (*x).dup; 632 m_coord_y = (*y).dup; 633 m_coord_z = (*z).dup; 634 635 } 636 public: 637 // relational operators 638 int opCmp(const ref PointGFp rhs) const 639 { 640 if (this == rhs) return 0; 641 else return -1; 642 } 643 644 // arithmetic operators 645 PointGFp opUnary(string op)() const 646 if (op == "-") 647 { 648 PointGFp ret = this.dup; 649 return ret.negate().dup; 650 } 651 652 PointGFp opBinary(string op)(auto const ref PointGFp rhs) const 653 if (op == "+") 654 { 655 PointGFp ret = this.dup; 656 ret += rhs; 657 return ret; 658 } 659 660 PointGFp opBinary(string op)(auto const ref PointGFp rhs) const 661 if (op == "-") 662 { 663 PointGFp ret = this.dup; 664 ret -= rhs; 665 return ret; 666 } 667 668 PointGFp opBinary(string op)(auto const ref PointGFp point) const 669 if (op == "*") 670 { 671 PointGFp ret = this.dup; 672 ret *= point; 673 return ret; 674 } 675 676 @disable this(this); 677 678 public Vector!char toVector() const { 679 Vector!char ret; 680 ret ~= "m_curve: "; 681 ret ~= m_curve.toVector()[]; 682 ret ~= "\nm_coord_x: "; 683 ret ~= m_coord_x.toVector()[]; 684 ret ~= "\nm_coord_y: "; 685 ret ~= m_coord_y.toVector()[]; 686 ret ~= "\nm_coord_z: "; 687 ret ~= m_coord_z.toVector()[]; 688 ret ~= "\nm_ws: "; 689 ret ~= m_ws.ptr[0 .. m_ws.length].to!string; 690 return ret.move; 691 } 692 693 public string toString() const { 694 return toVector()[].idup; 695 } 696 697 public PointGFp move() { 698 return PointGFp(&this); 699 } 700 701 CurveGFp m_curve; 702 BigInt m_coord_x, m_coord_y, m_coord_z; 703 SecureVector!word m_ws; // workspace for Montgomery 704 @property ref SecureVector!word m_ws_ref() { return m_ws; } 705 @property SecureVector!word m_ws_const() const { return m_ws.dup; } 706 alias mutable = SecureVector!word*; 707 } 708 709 // encoding and decoding 710 SecureVector!ubyte EC2OSP(const ref PointGFp point, ubyte format) 711 { 712 if (point.isZero()) 713 return SecureVector!ubyte(1); // single 0 ubyte 714 715 const size_t p_bytes = point.getCurve().getP().bytes(); 716 717 BigInt x = point.getAffineX(); 718 BigInt y = point.getAffineY(); 719 720 SecureVector!ubyte bX = BigInt.encode1363(x, p_bytes); 721 SecureVector!ubyte bY = BigInt.encode1363(y, p_bytes); 722 723 if (format == PointGFp.UNCOMPRESSED) 724 { 725 SecureVector!ubyte result; 726 result.pushBack(0x04); 727 728 result ~= bX[]; 729 result ~= bY[]; 730 731 return result.move(); 732 } 733 else if (format == PointGFp.COMPRESSED) 734 { 735 SecureVector!ubyte result; 736 result.pushBack(0x02 | cast(ubyte)(y.getBit(0))); 737 738 result ~= bX[]; 739 740 return result.move(); 741 } 742 else if (format == PointGFp.HYBRID) 743 { 744 SecureVector!ubyte result; 745 result.pushBack(0x06 | cast(ubyte)(y.getBit(0))); 746 747 result ~= bX[]; 748 result ~= bY[]; 749 750 return result.move(); 751 } 752 else 753 throw new InvalidArgument("EC2OSP illegal point encoding"); 754 } 755 756 PointGFp OS2ECP()(const(ubyte)* data, size_t data_len, auto const ref CurveGFp curve) 757 { 758 if (data_len <= 1) { 759 return PointGFp(curve); // return zero 760 } 761 const ubyte pc = data[0]; 762 BigInt x, y; 763 764 if (pc == 2 || pc == 3) 765 { 766 //compressed form 767 x = BigInt.decode(&data[1], data_len - 1); 768 769 const bool y_mod_2 = ((pc & 0x01) == 1); 770 y = decompressPoint(y_mod_2, &x, curve); 771 } 772 else if (pc == 4) 773 { 774 const size_t l = (data_len - 1) / 2; 775 776 // uncompressed form 777 x = BigInt.decode(&data[1], l); 778 y = BigInt.decode(&data[l+1], l); 779 } 780 else if (pc == 6 || pc == 7) 781 { 782 const size_t l = (data_len - 1) / 2; 783 784 // hybrid form 785 x = BigInt.decode(&data[1], l); 786 y = BigInt.decode(&data[l+1], l); 787 788 const bool y_mod_2 = ((pc & 0x01) == 1); 789 790 if (decompressPoint(y_mod_2, &x, curve) != y) 791 throw new IllegalPoint("OS2ECP: Decoding error in hybrid format"); 792 } 793 else 794 throw new InvalidArgument("OS2ECP: Unknown format type " ~ to!string(pc)); 795 PointGFp result = PointGFp(curve, &x, &y); 796 if (!result.onTheCurve()) 797 throw new IllegalPoint("OS2ECP: Decoded point was not on the curve"); 798 return result.move(); 799 } 800 801 PointGFp OS2ECP(Alloc)(auto const ref Vector!( ubyte, Alloc ) data, auto const ref CurveGFp curve) 802 { return OS2ECP(data.ptr, data.length, curve); } 803 804 private: 805 806 BigInt decompressPoint(bool yMod2, 807 BigInt* x, 808 const ref CurveGFp curve) 809 { 810 BigInt xpow3 = *x * x; 811 xpow3 *= x; 812 const BigInt* p = &curve.getP(); 813 814 BigInt g = curve.getA() * x; 815 g += xpow3; 816 g += curve.getB(); 817 g = g % (*p); 818 819 BigInt z = ressol(&g, p); 820 821 if (z < 0) 822 throw new IllegalPoint("error during EC point decompression"); 823 824 if (z.getBit(0) != yMod2) 825 z = *p - z; 826 return z; 827 }