1<?php 2 3/** 4 * Curves over y^2 = x^3 + a*x + b 5 * 6 * These are curves used in SEC 2 over prime fields: http://www.secg.org/SEC2-Ver-1.0.pdf 7 * The curve is a weierstrass curve with a[1], a[3] and a[2] set to 0. 8 * 9 * Uses Jacobian Coordinates for speed if able: 10 * 11 * https://en.wikipedia.org/wiki/Jacobian_curve 12 * https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates 13 * 14 * PHP version 5 and 7 15 * 16 * @author Jim Wigginton <terrafrost@php.net> 17 * @copyright 2017 Jim Wigginton 18 * @license http://www.opensource.org/licenses/mit-license.html MIT License 19 * @link http://pear.php.net/package/Math_BigInteger 20 */ 21 22namespace phpseclib3\Crypt\EC\BaseCurves; 23 24use phpseclib3\Common\Functions\Strings; 25use phpseclib3\Math\BigInteger; 26use phpseclib3\Math\Common\FiniteField\Integer; 27use phpseclib3\Math\PrimeField; 28use phpseclib3\Math\PrimeField\Integer as PrimeInteger; 29 30/** 31 * Curves over y^2 = x^3 + a*x + b 32 * 33 * @author Jim Wigginton <terrafrost@php.net> 34 */ 35class Prime extends Base 36{ 37 /** 38 * Prime Field Integer factory 39 * 40 * @var \phpseclib3\Math\PrimeFields 41 */ 42 protected $factory; 43 44 /** 45 * Cofficient for x^1 46 * 47 * @var object 48 */ 49 protected $a; 50 51 /** 52 * Cofficient for x^0 53 * 54 * @var object 55 */ 56 protected $b; 57 58 /** 59 * Base Point 60 * 61 * @var object 62 */ 63 protected $p; 64 65 /** 66 * The number one over the specified finite field 67 * 68 * @var object 69 */ 70 protected $one; 71 72 /** 73 * The number two over the specified finite field 74 * 75 * @var object 76 */ 77 protected $two; 78 79 /** 80 * The number three over the specified finite field 81 * 82 * @var object 83 */ 84 protected $three; 85 86 /** 87 * The number four over the specified finite field 88 * 89 * @var object 90 */ 91 protected $four; 92 93 /** 94 * The number eight over the specified finite field 95 * 96 * @var object 97 */ 98 protected $eight; 99 100 /** 101 * The modulo 102 * 103 * @var BigInteger 104 */ 105 protected $modulo; 106 107 /** 108 * The Order 109 * 110 * @var BigInteger 111 */ 112 protected $order; 113 114 /** 115 * Sets the modulo 116 */ 117 public function setModulo(BigInteger $modulo) 118 { 119 $this->modulo = $modulo; 120 $this->factory = new PrimeField($modulo); 121 $this->two = $this->factory->newInteger(new BigInteger(2)); 122 $this->three = $this->factory->newInteger(new BigInteger(3)); 123 // used by jacobian coordinates 124 $this->one = $this->factory->newInteger(new BigInteger(1)); 125 $this->four = $this->factory->newInteger(new BigInteger(4)); 126 $this->eight = $this->factory->newInteger(new BigInteger(8)); 127 } 128 129 /** 130 * Set coefficients a and b 131 */ 132 public function setCoefficients(BigInteger $a, BigInteger $b) 133 { 134 if (!isset($this->factory)) { 135 throw new \RuntimeException('setModulo needs to be called before this method'); 136 } 137 $this->a = $this->factory->newInteger($a); 138 $this->b = $this->factory->newInteger($b); 139 } 140 141 /** 142 * Set x and y coordinates for the base point 143 * 144 * @param BigInteger|PrimeInteger $x 145 * @param BigInteger|PrimeInteger $y 146 * @return PrimeInteger[] 147 */ 148 public function setBasePoint($x, $y) 149 { 150 switch (true) { 151 case !$x instanceof BigInteger && !$x instanceof PrimeInteger: 152 throw new \UnexpectedValueException('Argument 1 passed to Prime::setBasePoint() must be an instance of either BigInteger or PrimeField\Integer'); 153 case !$y instanceof BigInteger && !$y instanceof PrimeInteger: 154 throw new \UnexpectedValueException('Argument 2 passed to Prime::setBasePoint() must be an instance of either BigInteger or PrimeField\Integer'); 155 } 156 if (!isset($this->factory)) { 157 throw new \RuntimeException('setModulo needs to be called before this method'); 158 } 159 $this->p = [ 160 $x instanceof BigInteger ? $this->factory->newInteger($x) : $x, 161 $y instanceof BigInteger ? $this->factory->newInteger($y) : $y 162 ]; 163 } 164 165 /** 166 * Retrieve the base point as an array 167 * 168 * @return array 169 */ 170 public function getBasePoint() 171 { 172 if (!isset($this->factory)) { 173 throw new \RuntimeException('setModulo needs to be called before this method'); 174 } 175 /* 176 if (!isset($this->p)) { 177 throw new \RuntimeException('setBasePoint needs to be called before this method'); 178 } 179 */ 180 return $this->p; 181 } 182 183 /** 184 * Adds two "fresh" jacobian form on the curve 185 * 186 * @return FiniteField[] 187 */ 188 protected function jacobianAddPointMixedXY(array $p, array $q) 189 { 190 list($u1, $s1) = $p; 191 list($u2, $s2) = $q; 192 if ($u1->equals($u2)) { 193 if (!$s1->equals($s2)) { 194 return []; 195 } else { 196 return $this->doublePoint($p); 197 } 198 } 199 $h = $u2->subtract($u1); 200 $r = $s2->subtract($s1); 201 $h2 = $h->multiply($h); 202 $h3 = $h2->multiply($h); 203 $v = $u1->multiply($h2); 204 $x3 = $r->multiply($r)->subtract($h3)->subtract($v->multiply($this->two)); 205 $y3 = $r->multiply( 206 $v->subtract($x3) 207 )->subtract( 208 $s1->multiply($h3) 209 ); 210 return [$x3, $y3, $h]; 211 } 212 213 /** 214 * Adds one "fresh" jacobian form on the curve 215 * 216 * The second parameter should be the "fresh" one 217 * 218 * @return FiniteField[] 219 */ 220 protected function jacobianAddPointMixedX(array $p, array $q) 221 { 222 list($u1, $s1, $z1) = $p; 223 list($x2, $y2) = $q; 224 225 $z12 = $z1->multiply($z1); 226 227 $u2 = $x2->multiply($z12); 228 $s2 = $y2->multiply($z12->multiply($z1)); 229 if ($u1->equals($u2)) { 230 if (!$s1->equals($s2)) { 231 return []; 232 } else { 233 return $this->doublePoint($p); 234 } 235 } 236 $h = $u2->subtract($u1); 237 $r = $s2->subtract($s1); 238 $h2 = $h->multiply($h); 239 $h3 = $h2->multiply($h); 240 $v = $u1->multiply($h2); 241 $x3 = $r->multiply($r)->subtract($h3)->subtract($v->multiply($this->two)); 242 $y3 = $r->multiply( 243 $v->subtract($x3) 244 )->subtract( 245 $s1->multiply($h3) 246 ); 247 $z3 = $h->multiply($z1); 248 return [$x3, $y3, $z3]; 249 } 250 251 /** 252 * Adds two jacobian coordinates on the curve 253 * 254 * @return FiniteField[] 255 */ 256 protected function jacobianAddPoint(array $p, array $q) 257 { 258 list($x1, $y1, $z1) = $p; 259 list($x2, $y2, $z2) = $q; 260 261 $z12 = $z1->multiply($z1); 262 $z22 = $z2->multiply($z2); 263 264 $u1 = $x1->multiply($z22); 265 $u2 = $x2->multiply($z12); 266 $s1 = $y1->multiply($z22->multiply($z2)); 267 $s2 = $y2->multiply($z12->multiply($z1)); 268 if ($u1->equals($u2)) { 269 if (!$s1->equals($s2)) { 270 return []; 271 } else { 272 return $this->doublePoint($p); 273 } 274 } 275 $h = $u2->subtract($u1); 276 $r = $s2->subtract($s1); 277 $h2 = $h->multiply($h); 278 $h3 = $h2->multiply($h); 279 $v = $u1->multiply($h2); 280 $x3 = $r->multiply($r)->subtract($h3)->subtract($v->multiply($this->two)); 281 $y3 = $r->multiply( 282 $v->subtract($x3) 283 )->subtract( 284 $s1->multiply($h3) 285 ); 286 $z3 = $h->multiply($z1)->multiply($z2); 287 return [$x3, $y3, $z3]; 288 } 289 290 /** 291 * Adds two points on the curve 292 * 293 * @return FiniteField[] 294 */ 295 public function addPoint(array $p, array $q) 296 { 297 if (!isset($this->factory)) { 298 throw new \RuntimeException('setModulo needs to be called before this method'); 299 } 300 301 if (!count($p) || !count($q)) { 302 if (count($q)) { 303 return $q; 304 } 305 if (count($p)) { 306 return $p; 307 } 308 return []; 309 } 310 311 // use jacobian coordinates 312 if (isset($p[2]) && isset($q[2])) { 313 if (isset($p['fresh']) && isset($q['fresh'])) { 314 return $this->jacobianAddPointMixedXY($p, $q); 315 } 316 if (isset($p['fresh'])) { 317 return $this->jacobianAddPointMixedX($q, $p); 318 } 319 if (isset($q['fresh'])) { 320 return $this->jacobianAddPointMixedX($p, $q); 321 } 322 return $this->jacobianAddPoint($p, $q); 323 } 324 325 if (isset($p[2]) || isset($q[2])) { 326 throw new \RuntimeException('Affine coordinates need to be manually converted to Jacobi coordinates or vice versa'); 327 } 328 329 if ($p[0]->equals($q[0])) { 330 if (!$p[1]->equals($q[1])) { 331 return []; 332 } else { // eg. doublePoint 333 list($numerator, $denominator) = $this->doublePointHelper($p); 334 } 335 } else { 336 $numerator = $q[1]->subtract($p[1]); 337 $denominator = $q[0]->subtract($p[0]); 338 } 339 $slope = $numerator->divide($denominator); 340 $x = $slope->multiply($slope)->subtract($p[0])->subtract($q[0]); 341 $y = $slope->multiply($p[0]->subtract($x))->subtract($p[1]); 342 343 return [$x, $y]; 344 } 345 346 /** 347 * Returns the numerator and denominator of the slope 348 * 349 * @return FiniteField[] 350 */ 351 protected function doublePointHelper(array $p) 352 { 353 $numerator = $this->three->multiply($p[0])->multiply($p[0])->add($this->a); 354 $denominator = $this->two->multiply($p[1]); 355 return [$numerator, $denominator]; 356 } 357 358 /** 359 * Doubles a jacobian coordinate on the curve 360 * 361 * @return FiniteField[] 362 */ 363 protected function jacobianDoublePoint(array $p) 364 { 365 list($x, $y, $z) = $p; 366 $x2 = $x->multiply($x); 367 $y2 = $y->multiply($y); 368 $z2 = $z->multiply($z); 369 $s = $this->four->multiply($x)->multiply($y2); 370 $m1 = $this->three->multiply($x2); 371 $m2 = $this->a->multiply($z2->multiply($z2)); 372 $m = $m1->add($m2); 373 $x1 = $m->multiply($m)->subtract($this->two->multiply($s)); 374 $y1 = $m->multiply($s->subtract($x1))->subtract( 375 $this->eight->multiply($y2->multiply($y2)) 376 ); 377 $z1 = $this->two->multiply($y)->multiply($z); 378 return [$x1, $y1, $z1]; 379 } 380 381 /** 382 * Doubles a "fresh" jacobian coordinate on the curve 383 * 384 * @return FiniteField[] 385 */ 386 protected function jacobianDoublePointMixed(array $p) 387 { 388 list($x, $y) = $p; 389 $x2 = $x->multiply($x); 390 $y2 = $y->multiply($y); 391 $s = $this->four->multiply($x)->multiply($y2); 392 $m1 = $this->three->multiply($x2); 393 $m = $m1->add($this->a); 394 $x1 = $m->multiply($m)->subtract($this->two->multiply($s)); 395 $y1 = $m->multiply($s->subtract($x1))->subtract( 396 $this->eight->multiply($y2->multiply($y2)) 397 ); 398 $z1 = $this->two->multiply($y); 399 return [$x1, $y1, $z1]; 400 } 401 402 /** 403 * Doubles a point on a curve 404 * 405 * @return FiniteField[] 406 */ 407 public function doublePoint(array $p) 408 { 409 if (!isset($this->factory)) { 410 throw new \RuntimeException('setModulo needs to be called before this method'); 411 } 412 413 if (!count($p)) { 414 return []; 415 } 416 417 // use jacobian coordinates 418 if (isset($p[2])) { 419 if (isset($p['fresh'])) { 420 return $this->jacobianDoublePointMixed($p); 421 } 422 return $this->jacobianDoublePoint($p); 423 } 424 425 list($numerator, $denominator) = $this->doublePointHelper($p); 426 427 $slope = $numerator->divide($denominator); 428 429 $x = $slope->multiply($slope)->subtract($p[0])->subtract($p[0]); 430 $y = $slope->multiply($p[0]->subtract($x))->subtract($p[1]); 431 432 return [$x, $y]; 433 } 434 435 /** 436 * Returns the X coordinate and the derived Y coordinate 437 * 438 * @return array 439 */ 440 public function derivePoint($m) 441 { 442 $y = ord(Strings::shift($m)); 443 $x = new BigInteger($m, 256); 444 $xp = $this->convertInteger($x); 445 switch ($y) { 446 case 2: 447 $ypn = false; 448 break; 449 case 3: 450 $ypn = true; 451 break; 452 default: 453 throw new \RuntimeException('Coordinate not in recognized format'); 454 } 455 $temp = $xp->multiply($this->a); 456 $temp = $xp->multiply($xp)->multiply($xp)->add($temp); 457 $temp = $temp->add($this->b); 458 $b = $temp->squareRoot(); 459 if (!$b) { 460 throw new \RuntimeException('Unable to derive Y coordinate'); 461 } 462 $bn = $b->isOdd(); 463 $yp = $ypn == $bn ? $b : $b->negate(); 464 return [$xp, $yp]; 465 } 466 467 /** 468 * Tests whether or not the x / y values satisfy the equation 469 * 470 * @return boolean 471 */ 472 public function verifyPoint(array $p) 473 { 474 list($x, $y) = $p; 475 $lhs = $y->multiply($y); 476 $temp = $x->multiply($this->a); 477 $temp = $x->multiply($x)->multiply($x)->add($temp); 478 $rhs = $temp->add($this->b); 479 480 return $lhs->equals($rhs); 481 } 482 483 /** 484 * Returns the modulo 485 * 486 * @return BigInteger 487 */ 488 public function getModulo() 489 { 490 return $this->modulo; 491 } 492 493 /** 494 * Returns the a coefficient 495 * 496 * @return PrimeInteger 497 */ 498 public function getA() 499 { 500 return $this->a; 501 } 502 503 /** 504 * Returns the a coefficient 505 * 506 * @return PrimeInteger 507 */ 508 public function getB() 509 { 510 return $this->b; 511 } 512 513 /** 514 * Multiply and Add Points 515 * 516 * Adapted from: 517 * https://github.com/indutny/elliptic/blob/725bd91/lib/elliptic/curve/base.js#L125 518 * 519 * @return int[] 520 */ 521 public function multiplyAddPoints(array $points, array $scalars) 522 { 523 $length = count($points); 524 525 foreach ($points as &$point) { 526 $point = $this->convertToInternal($point); 527 } 528 529 $wnd = [$this->getNAFPoints($points[0], 7)]; 530 $wndWidth = [isset($points[0]['nafwidth']) ? $points[0]['nafwidth'] : 7]; 531 for ($i = 1; $i < $length; $i++) { 532 $wnd[] = $this->getNAFPoints($points[$i], 1); 533 $wndWidth[] = isset($points[$i]['nafwidth']) ? $points[$i]['nafwidth'] : 1; 534 } 535 536 $naf = []; 537 538 // comb all window NAFs 539 540 $max = 0; 541 for ($i = $length - 1; $i >= 1; $i -= 2) { 542 $a = $i - 1; 543 $b = $i; 544 if ($wndWidth[$a] != 1 || $wndWidth[$b] != 1) { 545 $naf[$a] = $scalars[$a]->getNAF($wndWidth[$a]); 546 $naf[$b] = $scalars[$b]->getNAF($wndWidth[$b]); 547 $max = max(count($naf[$a]), count($naf[$b]), $max); 548 continue; 549 } 550 551 $comb = [ 552 $points[$a], // 1 553 null, // 3 554 null, // 5 555 $points[$b] // 7 556 ]; 557 558 $comb[1] = $this->addPoint($points[$a], $points[$b]); 559 $comb[2] = $this->addPoint($points[$a], $this->negatePoint($points[$b])); 560 561 $index = [ 562 -3, /* -1 -1 */ 563 -1, /* -1 0 */ 564 -5, /* -1 1 */ 565 -7, /* 0 -1 */ 566 0, /* 0 -1 */ 567 7, /* 0 1 */ 568 5, /* 1 -1 */ 569 1, /* 1 0 */ 570 3 /* 1 1 */ 571 ]; 572 573 $jsf = self::getJSFPoints($scalars[$a], $scalars[$b]); 574 575 $max = max(count($jsf[0]), $max); 576 if ($max > 0) { 577 $naf[$a] = array_fill(0, $max, 0); 578 $naf[$b] = array_fill(0, $max, 0); 579 } else { 580 $naf[$a] = []; 581 $naf[$b] = []; 582 } 583 584 for ($j = 0; $j < $max; $j++) { 585 $ja = isset($jsf[0][$j]) ? $jsf[0][$j] : 0; 586 $jb = isset($jsf[1][$j]) ? $jsf[1][$j] : 0; 587 588 $naf[$a][$j] = $index[3 * ($ja + 1) + $jb + 1]; 589 $naf[$b][$j] = 0; 590 $wnd[$a] = $comb; 591 } 592 } 593 594 $acc = []; 595 $temp = [0, 0, 0, 0]; 596 for ($i = $max; $i >= 0; $i--) { 597 $k = 0; 598 while ($i >= 0) { 599 $zero = true; 600 for ($j = 0; $j < $length; $j++) { 601 $temp[$j] = isset($naf[$j][$i]) ? $naf[$j][$i] : 0; 602 if ($temp[$j] != 0) { 603 $zero = false; 604 } 605 } 606 if (!$zero) { 607 break; 608 } 609 $k++; 610 $i--; 611 } 612 613 if ($i >= 0) { 614 $k++; 615 } 616 while ($k--) { 617 $acc = $this->doublePoint($acc); 618 } 619 620 if ($i < 0) { 621 break; 622 } 623 624 for ($j = 0; $j < $length; $j++) { 625 $z = $temp[$j]; 626 $p = null; 627 if ($z == 0) { 628 continue; 629 } 630 $p = $z > 0 ? 631 $wnd[$j][($z - 1) >> 1] : 632 $this->negatePoint($wnd[$j][(-$z - 1) >> 1]); 633 $acc = $this->addPoint($acc, $p); 634 } 635 } 636 637 return $this->convertToAffine($acc); 638 } 639 640 /** 641 * Precomputes NAF points 642 * 643 * Adapted from: 644 * https://github.com/indutny/elliptic/blob/725bd91/lib/elliptic/curve/base.js#L351 645 * 646 * @return int[] 647 */ 648 private function getNAFPoints(array $point, $wnd) 649 { 650 if (isset($point['naf'])) { 651 return $point['naf']; 652 } 653 654 $res = [$point]; 655 $max = (1 << $wnd) - 1; 656 $dbl = $max == 1 ? null : $this->doublePoint($point); 657 for ($i = 1; $i < $max; $i++) { 658 $res[] = $this->addPoint($res[$i - 1], $dbl); 659 } 660 661 $point['naf'] = $res; 662 663 /* 664 $str = ''; 665 foreach ($res as $re) { 666 $re[0] = bin2hex($re[0]->toBytes()); 667 $re[1] = bin2hex($re[1]->toBytes()); 668 $str.= " ['$re[0]', '$re[1]'],\r\n"; 669 } 670 file_put_contents('temp.txt', $str); 671 exit; 672 */ 673 674 return $res; 675 } 676 677 /** 678 * Precomputes points in Joint Sparse Form 679 * 680 * Adapted from: 681 * https://github.com/indutny/elliptic/blob/725bd91/lib/elliptic/utils.js#L96 682 * 683 * @return int[] 684 */ 685 private static function getJSFPoints(Integer $k1, Integer $k2) 686 { 687 static $three; 688 if (!isset($three)) { 689 $three = new BigInteger(3); 690 } 691 692 $jsf = [[], []]; 693 $k1 = $k1->toBigInteger(); 694 $k2 = $k2->toBigInteger(); 695 $d1 = 0; 696 $d2 = 0; 697 698 while ($k1->compare(new BigInteger(-$d1)) > 0 || $k2->compare(new BigInteger(-$d2)) > 0) { 699 // first phase 700 $m14 = $k1->testBit(0) + 2 * $k1->testBit(1); 701 $m14 += $d1; 702 $m14 &= 3; 703 704 $m24 = $k2->testBit(0) + 2 * $k2->testBit(1); 705 $m24 += $d2; 706 $m24 &= 3; 707 708 if ($m14 == 3) { 709 $m14 = -1; 710 } 711 if ($m24 == 3) { 712 $m24 = -1; 713 } 714 715 $u1 = 0; 716 if ($m14 & 1) { // if $m14 is odd 717 $m8 = $k1->testBit(0) + 2 * $k1->testBit(1) + 4 * $k1->testBit(2); 718 $m8 += $d1; 719 $m8 &= 7; 720 $u1 = ($m8 == 3 || $m8 == 5) && $m24 == 2 ? -$m14 : $m14; 721 } 722 $jsf[0][] = $u1; 723 724 $u2 = 0; 725 if ($m24 & 1) { // if $m24 is odd 726 $m8 = $k2->testBit(0) + 2 * $k2->testBit(1) + 4 * $k2->testBit(2); 727 $m8 += $d2; 728 $m8 &= 7; 729 $u2 = ($m8 == 3 || $m8 == 5) && $m14 == 2 ? -$m24 : $m24; 730 } 731 $jsf[1][] = $u2; 732 733 // second phase 734 if (2 * $d1 == $u1 + 1) { 735 $d1 = 1 - $d1; 736 } 737 if (2 * $d2 == $u2 + 1) { 738 $d2 = 1 - $d2; 739 } 740 $k1 = $k1->bitwise_rightShift(1); 741 $k2 = $k2->bitwise_rightShift(1); 742 } 743 744 return $jsf; 745 } 746 747 /** 748 * Returns the affine point 749 * 750 * A Jacobian Coordinate is of the form (x, y, z). 751 * To convert a Jacobian Coordinate to an Affine Point 752 * you do (x / z^2, y / z^3) 753 * 754 * @return \phpseclib3\Math\PrimeField\Integer[] 755 */ 756 public function convertToAffine(array $p) 757 { 758 if (!isset($p[2])) { 759 return $p; 760 } 761 list($x, $y, $z) = $p; 762 $z = $this->one->divide($z); 763 $z2 = $z->multiply($z); 764 return [ 765 $x->multiply($z2), 766 $y->multiply($z2)->multiply($z) 767 ]; 768 } 769 770 /** 771 * Converts an affine point to a jacobian coordinate 772 * 773 * @return \phpseclib3\Math\PrimeField\Integer[] 774 */ 775 public function convertToInternal(array $p) 776 { 777 if (isset($p[2])) { 778 return $p; 779 } 780 781 $p[2] = clone $this->one; 782 $p['fresh'] = true; 783 return $p; 784 } 785} 786