1: <?php
   2: 
   3: namespace Liberty;
   4: 
   5: if (!extension_loaded('gmp')) {
   6:     throw new \Exception('GMP extension seems not to be installed');
   7: }
   8: 
   9: 
  10: /**
  11:  * Liberty Eliptic Curve Algorithm. (from BitcoinECDSA, Jan Moritz Lindemann). Require GMP.
  12:  * 
  13:  * Copyright (C) Jan Moritz Lindemann.
  14:  * 
  15:  * Copyright (C) Liberty Group <cryptolibertygroup@gmail.com>.
  16:  * 
  17:  * Unlicense. Public Domain. http://unlicense.org/ 
  18:  * This piece of software is provided without warranty of any kind, use it at your own risk.
  19:  *
  20:  * @category  Cryptocurrency
  21:  * @package   Liberty
  22:  * @license   http://unlicense.org Unlicense
  23:  * @version   1.0.0
  24:  * @since     2017-03-25
  25:  * @author    Liberty Group <cryptolibertygroup@gmail.com>, Jan Moritz Lindemann
  26:  */
  27: 
  28: 
  29: class LECDSA
  30: {
  31: 
  32:     public $k;
  33:     public $a;
  34:     public $b;
  35:     public $p;
  36:     public $n;
  37:     public $G;
  38:     public $networkPrefix;
  39: 
  40: 
  41: 
  42:     public function __construct()
  43:     {
  44:         $this->a = gmp_init('0', 10);
  45:         $this->b = gmp_init('7', 10);
  46:         $this->p = gmp_init('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F', 16);
  47:         $this->n = gmp_init('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141', 16);
  48: 
  49:         $this->G = [
  50:                     'x' => gmp_init('55066263022277343669578718895168534326250603453777594175500187360389116729240'),
  51:                     'y' => gmp_init('32670510020758816978083085130507043184471273380659243275938904335757337482424')
  52:                    ];
  53:         
  54:         // Prefix: 48 (0x30) Char 'L'
  55:         $this->networkPrefix = '30';
  56:     }
  57: 
  58: 
  59: 
  60: 
  61:     /***
  62:      * Convert a number to a compact Int
  63:      * taken from https://github.com/scintill/php-bitcoin-signature-routines/blob/master/verifymessage.php
  64:      *
  65:      * @param int $i
  66:      * @return string (bin)
  67:      * @throws \Exception
  68:      */
  69:     public function numToVarIntString($i) {
  70:         if ($i < 0xfd) {
  71:             return chr($i);
  72:         } else if ($i <= 0xffff) {
  73:             return pack('Cv', 0xfd, $i);
  74:         } else if ($i <= 0xffffffff) {
  75:             return pack('CV', 0xfe, $i);
  76:         } else {
  77:             throw new \Exception('int too large');
  78:         }
  79:     }
  80: 
  81: 
  82: 
  83: 
  84:     /***
  85:      * Set the network prefix, '00' = main network, '6f' = test network.
  86:      *
  87:      * @param string $prefix (hexa)
  88:      */
  89:     public function setNetworkPrefix($prefix)
  90:     {
  91:         $this->networkPrefix = $prefix;
  92:     }
  93: 
  94: 
  95: 
  96: 
  97:     /**
  98:      * Returns the current network prefix, '00' = main network, '6f' = test network.
  99:      *
 100:      * @return string (hexa)
 101:      */
 102:     public function getNetworkPrefix()
 103:     {
 104:         return $this->networkPrefix;
 105:     }
 106: 
 107: 
 108: 
 109:     /**
 110:      * Returns the current network prefix for WIF, '80' = main network, 'ef' = test network.
 111:      *
 112:      * @return string (hexa)
 113:      */
 114:     public function getPrivatePrefix(){
 115:         if($this->networkPrefix =='6f')
 116:             return 'ef';
 117:         else
 118:             return 'b0'; //80
 119:     }
 120: 
 121: 
 122: 
 123: 
 124:     /***
 125:      * Permutation table used for Base58 encoding and decoding.
 126:      *
 127:      * @param string $char
 128:      * @param bool $reverse
 129:      * @return string|null
 130:      */
 131:     public function base58_permutation($char, $reverse = false)
 132:     {
 133:         $table = [
 134:                   '1','2','3','4','5','6','7','8','9','A','B','C','D',
 135:                   'E','F','G','H','J','K','L','M','N','P','Q','R','S','T','U','V','W',
 136:                   'X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','m','n','o',
 137:                   'p','q','r','s','t','u','v','w','x','y','z'
 138:                  ];
 139: 
 140:         if($reverse)
 141:         {
 142:             $reversedTable = [];
 143:             foreach($table as $key => $element)
 144:             {
 145:                 $reversedTable[$element] = $key;
 146:             }
 147: 
 148:             if(isset($reversedTable[$char]))
 149:                 return $reversedTable[$char];
 150:             else
 151:                 return null;
 152:         }
 153: 
 154:         if(isset($table[$char]))
 155:             return $table[$char];
 156:         else
 157:             return null;
 158:     }
 159: 
 160: 
 161: 
 162: 
 163:     /***
 164:      * Bitcoin standard 256 bit hash function : double sha256
 165:      *
 166:      * @param string $data
 167:      * @return string (hexa)
 168:      */
 169:     public function hash256($data)
 170:     {
 171:         return hash('sha256', hex2bin(hash('sha256', $data)));
 172:     }
 173: 
 174: 
 175: 
 176: 
 177:     /**
 178:      * @param string $data
 179:      * @return string (hexa)
 180:      */
 181:     public function hash160($data)
 182:     {
 183:         return hash('ripemd160', hex2bin(hash('sha256', $data)));
 184:     }
 185: 
 186: 
 187: 
 188: 
 189:     /**
 190:      * Generates a random 256 bytes hexadecimal encoded string that is smaller than n
 191:      *
 192:      * @return string (hexa)
 193:      * @throws \Exception
 194:      */
 195:     public function generateRandom256BitsHexaString()
 196:     {
 197:         do
 198:         {
 199:             $bytes = openssl_random_pseudo_bytes(256, $cStrong);
 200:             $hex = bin2hex($bytes);
 201:             $random = $hex . microtime(true) . hash("sha256", microtime());
 202: 
 203:             if ($cStrong === false) {
 204:                 throw new \Exception('Your system is not able to generate strong enough random numbers');
 205:             }
 206:             $res = $this->hash256($random);
 207: 
 208:         } while(gmp_cmp(gmp_init($res, 16), gmp_sub($this->n, gmp_init(1, 10))) === 1); // make sure the generate string is smaller than n
 209: 
 210:         return $res;
 211:     }
 212: 
 213: 
 214: 
 215: 
 216:     /***
 217:      * encode a hexadecimal string in Base58.
 218:      *
 219:      * @param string $data (hexa)
 220:      * @param bool $littleEndian
 221:      * @return string (base58)
 222:      * @throws \Exception
 223:      */
 224:     public function base58_encode($data, $littleEndian = true)
 225:     {
 226:         $res = '';
 227:         $dataIntVal = gmp_init($data, 16);
 228:         while(gmp_cmp($dataIntVal, gmp_init(0, 10)) > 0)
 229:         {
 230:             $qr = gmp_div_qr($dataIntVal, gmp_init(58, 10));
 231:             $dataIntVal = $qr[0];
 232:             $reminder = gmp_strval($qr[1]);
 233:             if(!$this->base58_permutation($reminder))
 234:             {
 235:                 throw new \Exception('Something went wrong during base58 encoding');
 236:             }
 237:             $res .= $this->base58_permutation($reminder);
 238:         }
 239: 
 240:         //get number of leading zeros
 241:         $leading = '';
 242:         $i = 0;
 243:         while(substr($data, $i, 1) === '0')
 244:         {
 245:             if($i!== 0 && $i%2)
 246:             {
 247:                 $leading .= '1';
 248:             }
 249:             $i++;
 250:         }
 251: 
 252:         if($littleEndian)
 253:             return strrev($res . $leading);
 254:         else
 255:             return $res.$leading;
 256:     }
 257: 
 258: 
 259: 
 260: 
 261:     /***
 262:      * Decode a Base58 encoded string and returns it's value as a hexadecimal string
 263:      *
 264:      * @param string $encodedData (base58)
 265:      * @param bool $littleEndian
 266:      * @return string (hexa)
 267:      */
 268:     public function base58_decode($encodedData, $littleEndian = true)
 269:     {
 270:         $res = gmp_init(0, 10);
 271:         $length = strlen($encodedData);
 272:         if($littleEndian)
 273:         {
 274:             $encodedData = strrev($encodedData);
 275:         }
 276: 
 277:         for($i = $length - 1; $i >= 0; $i--)
 278:         {
 279:             $res = gmp_add(
 280:                            gmp_mul(
 281:                                    $res,
 282:                                    gmp_init(58, 10)
 283:                            ),
 284:                            $this->base58_permutation(substr($encodedData, $i, 1), true)
 285:                    );
 286:         }
 287: 
 288:         $res = gmp_strval($res, 16);
 289:         $i = $length - 1;
 290:         while(substr($encodedData, $i, 1) === '1')
 291:         {
 292:             $res = '00' . $res;
 293:             $i--;
 294:         }
 295: 
 296:         if(strlen($res)%2 !== 0)
 297:         {
 298:             $res = '0' . $res;
 299:         }
 300: 
 301:         return $res;
 302:     }
 303: 
 304: 
 305: 
 306: 
 307:     /***
 308:      * Computes the result of a point addition and returns the resulting point as an Array.
 309:      *
 310:      * @param Array $pt
 311:      * @return Array Point
 312:      * @throws \Exception
 313:      */
 314:     public function doublePoint(Array $pt)
 315:     {
 316:         $a = $this->a;
 317:         $p = $this->p;
 318: 
 319:         $gcd = gmp_strval(gmp_gcd(gmp_mod(gmp_mul(gmp_init(2, 10), $pt['y']), $p),$p));
 320:         if($gcd !== '1')
 321:         {
 322:             throw new \Exception('This library doesn\'t yet supports point at infinity. See https://github.com/BitcoinPHP/BitcoinECDSA.php/issues/9');
 323:         }
 324: 
 325:         // SLOPE = (3 * ptX^2 + a )/( 2*ptY )
 326:         // Equals (3 * ptX^2 + a ) * ( 2*ptY )^-1
 327:         $slope = gmp_mod(
 328:                          gmp_mul(
 329:                                  gmp_invert(
 330:                                             gmp_mod(
 331:                                                     gmp_mul(
 332:                                                             gmp_init(2, 10),
 333:                                                             $pt['y']
 334:                                                     ),
 335:                                                     $p
 336:                                             ),
 337:                                             $p
 338:                                  ),
 339:                                  gmp_add(
 340:                                          gmp_mul(
 341:                                                  gmp_init(3, 10),
 342:                                                  gmp_pow($pt['x'], 2)
 343:                                          ),
 344:                                          $a
 345:                                  )
 346:                          ),
 347:                          $p
 348:                 );
 349: 
 350:         // nPtX = slope^2 - 2 * ptX
 351:         // Equals slope^2 - ptX - ptX
 352:         $nPt = [];
 353:         $nPt['x'] = gmp_mod(
 354:                             gmp_sub(
 355:                                     gmp_sub(
 356:                                             gmp_pow($slope, 2),
 357:                                             $pt['x']
 358:                                     ),
 359:                                     $pt['x']
 360:                             ),
 361:                             $p
 362:                     );
 363: 
 364:         // nPtY = slope * (ptX - nPtx) - ptY
 365:         $nPt['y'] = gmp_mod(
 366:                             gmp_sub(
 367:                                     gmp_mul(
 368:                                             $slope,
 369:                                             gmp_sub(
 370:                                                     $pt['x'],
 371:                                                     $nPt['x']
 372:                                             )
 373:                                     ),
 374:                                     $pt['y']
 375:                             ),
 376:                             $p
 377:                     );
 378: 
 379:         return $nPt;
 380:     }
 381: 
 382: 
 383: 
 384: 
 385:     /***
 386:      * Computes the result of a point addition and returns the resulting point as an Array.
 387:      *
 388:      * @param Array $pt1
 389:      * @param Array $pt2
 390:      * @return Array Point
 391:      * @throws \Exception
 392:      */
 393:     public function addPoints(Array $pt1, Array $pt2)
 394:     {
 395:         $p = $this->p;
 396:         if(gmp_cmp($pt1['x'], $pt2['x']) === 0  && gmp_cmp($pt1['y'], $pt2['y']) === 0) //if identical
 397:         {
 398:             return $this->doublePoint($pt1);
 399:         }
 400: 
 401:         $gcd = gmp_strval(gmp_gcd(gmp_sub($pt1['x'], $pt2['x']), $p));
 402:         if($gcd !== '1')
 403:         {
 404:             throw new \Exception('This library doesn\'t yet supports point at infinity. See https://github.com/BitcoinPHP/BitcoinECDSA.php/issues/9');
 405:         }
 406: 
 407:         // SLOPE = (pt1Y - pt2Y)/( pt1X - pt2X )
 408:         // Equals (pt1Y - pt2Y) * ( pt1X - pt2X )^-1
 409:         $slope      = gmp_mod(
 410:                               gmp_mul(
 411:                                       gmp_sub(
 412:                                               $pt1['y'],
 413:                                               $pt2['y']
 414:                                       ),
 415:                                       gmp_invert(
 416:                                                  gmp_sub(
 417:                                                          $pt1['x'],
 418:                                                          $pt2['x']
 419:                                                  ),
 420:                                                  $p
 421:                                       )
 422:                               ),
 423:                               $p
 424:                       );
 425: 
 426:         // nPtX = slope^2 - ptX1 - ptX2
 427:         $nPt = [];
 428:         $nPt['x']   = gmp_mod(
 429:                               gmp_sub(
 430:                                       gmp_sub(
 431:                                               gmp_pow($slope, 2),
 432:                                               $pt1['x']
 433:                                       ),
 434:                                       $pt2['x']
 435:                               ),
 436:                               $p
 437:                       );
 438: 
 439:         // nPtX = slope * (ptX1 - nPtX) - ptY1
 440:         $nPt['y']   = gmp_mod(
 441:                               gmp_sub(
 442:                                       gmp_mul(
 443:                                               $slope,
 444:                                               gmp_sub(
 445:                                                       $pt1['x'],
 446:                                                       $nPt['x']
 447:                                               )
 448:                                       ),
 449:                                       $pt1['y']
 450:                               ),
 451:                               $p
 452:                       );
 453: 
 454:         return $nPt;
 455:     }
 456: 
 457: 
 458: 
 459: 
 460:     /***
 461:      * Computes the result of a point multiplication and returns the resulting point as an Array.
 462:      *
 463:      * @param string|resource $k (hexa|GMP|Other bases definded in base)
 464:      * @param Array $pG
 465:      * @param $base
 466:      * @throws \Exception
 467:      * @return Array Point
 468:      */
 469:     public function mulPoint($k, Array $pG, $base = null)
 470:     {
 471:         //in order to calculate k*G
 472:         if($base === 16 || $base === null || is_resource($base))
 473:             $k = gmp_init($k, 16);
 474:         if($base === 10)
 475:             $k = gmp_init($k, 10);
 476:         $kBin = gmp_strval($k, 2);
 477: 
 478:         $lastPoint = $pG;
 479:         for($i = 1; $i < strlen($kBin); $i++)
 480:         {
 481:             if(substr($kBin, $i, 1) === '1')
 482:             {
 483:                 $dPt = $this->doublePoint($lastPoint);
 484:                 $lastPoint = $this->addPoints($dPt, $pG);
 485:             }
 486:             else
 487:             {
 488:                 $lastPoint = $this->doublePoint($lastPoint);
 489:             }
 490:         }
 491:         if(!$this->validatePoint(gmp_strval($lastPoint['x'], 16), gmp_strval($lastPoint['y'], 16)))
 492:             throw new \Exception('The resulting point is not on the curve.');
 493:         return $lastPoint;
 494:     }
 495: 
 496: 
 497: 
 498: 
 499:     /***
 500:      * Calculates the square root of $a mod p and returns the 2 solutions as an array.
 501:      *
 502:      * @param resource $a (GMP)
 503:      * @return array|null
 504:      * @throws \Exception
 505:      */
 506:     public function sqrt($a)
 507:     {
 508:         $p = $this->p;
 509: 
 510:         if(gmp_legendre($a, $p) !== 1)
 511:         {
 512:             //no result
 513:             return null;
 514:         }
 515: 
 516:         if(gmp_strval(gmp_mod($p, gmp_init(4, 10)), 10) === '3')
 517:         {
 518:             $sqrt1 = gmp_powm(
 519:                             $a,
 520:                             gmp_div_q(
 521:                                 gmp_add($p, gmp_init(1, 10)),
 522:                                 gmp_init(4, 10)
 523:                             ),
 524:                             $p
 525:                     );
 526:             // there are always 2 results for a square root
 527:             // In an infinite number field you have -2^2 = 2^2 = 4
 528:             // In a finite number field you have a^2 = (p-a)^2
 529:             $sqrt2 = gmp_mod(gmp_sub($p, $sqrt1), $p);
 530:             return [$sqrt1, $sqrt2];
 531:         }
 532:         else
 533:         {
 534:             throw new \Exception('P % 4 != 3 , this isn\'t supported yet.');
 535:         }
 536:     }
 537: 
 538: 
 539: 
 540: 
 541:     /***
 542:      * Calculate the Y coordinates for a given X coordinate.
 543:      *
 544:      * @param string $x (hexa)
 545:      * @param null $derEvenOrOddCode
 546:      * @return array|null|String
 547:      */
 548:     public function calculateYWithX($x, $derEvenOrOddCode = null)
 549:     {
 550:         $a  = $this->a;
 551:         $b  = $this->b;
 552:         $p  = $this->p;
 553: 
 554:         $x  = gmp_init($x, 16);
 555:         $y2 = gmp_mod(
 556:                       gmp_add(
 557:                               gmp_add(
 558:                                       gmp_powm($x, gmp_init(3, 10), $p),
 559:                                       gmp_mul($a, $x)
 560:                               ),
 561:                               $b
 562:                       ),
 563:                       $p
 564:               );
 565: 
 566:         $y = $this->sqrt($y2);
 567: 
 568:         if($y === null) //if there is no result
 569:         {
 570:             return null;
 571:         }
 572: 
 573:         if($derEvenOrOddCode === null)
 574:         {
 575:             return $y;
 576:         }
 577: 
 578:         else if($derEvenOrOddCode === '02') // even
 579:         {
 580:             $resY = null;
 581:             if(gmp_strval(gmp_mod($y[0], gmp_init(2, 10)), 10) === '0')
 582:                 $resY = gmp_strval($y[0], 16);
 583:             if(gmp_strval(gmp_mod($y[1], gmp_init(2, 10)), 10) === '0')
 584:                 $resY = gmp_strval($y[1], 16);
 585:             if($resY !== null)
 586:             {
 587:                 while(strlen($resY) < 64)
 588:                 {
 589:                     $resY = '0' . $resY;
 590:                 }
 591:             }
 592:             return $resY;
 593:         }
 594:         else if($derEvenOrOddCode === '03') // odd
 595:         {
 596:             $resY = null;
 597:             if(gmp_strval(gmp_mod($y[0], gmp_init(2, 10)), 10) === '1')
 598:                 $resY = gmp_strval($y[0], 16);
 599:             if(gmp_strval(gmp_mod($y[1], gmp_init(2, 10)), 10) === '1')
 600:                 $resY = gmp_strval($y[1], 16);
 601:             if($resY !== null)
 602:             {
 603:                 while(strlen($resY) < 64)
 604:                 {
 605:                     $resY = '0' . $resY;
 606:                 }
 607:             }
 608:             return $resY;
 609:         }
 610: 
 611:         return null;
 612:     }
 613: 
 614: 
 615: 
 616: 
 617:     /***
 618:      * returns the public key coordinates as an array.
 619:      *
 620:      * @param string $derPubKey (hexa)
 621:      * @return array
 622:      * @throws \Exception
 623:      */
 624:     public function getPubKeyPointsWithDerPubKey($derPubKey)
 625:     {
 626:         if(substr($derPubKey, 0, 2) === '04' && strlen($derPubKey) === 130)
 627:         {
 628:             //uncompressed der encoded public key
 629:             $x = substr($derPubKey, 2, 64);
 630:             $y = substr($derPubKey, 66, 64);
 631:             return ['x' => $x, 'y' => $y];
 632:         }
 633:         else if((substr($derPubKey, 0, 2) === '02' || substr($derPubKey, 0, 2) === '03') && strlen($derPubKey) === 66)
 634:         {
 635:             //compressed der encoded public key
 636:             $x = substr($derPubKey, 2, 64);
 637:             $y = $this->calculateYWithX($x, substr($derPubKey, 0, 2));
 638:             return ['x' => $x, 'y' => $y];
 639:         }
 640:         else
 641:         {
 642:             throw new \Exception('Invalid derPubKey format : ' . $derPubKey);
 643:         }
 644:     }
 645: 
 646: 
 647: 
 648: 
 649:     /**
 650:      * @param array $pubKey (array <x:string, y:string>)
 651:      * @param bool $compressed
 652:      * @return string
 653:      */
 654:     public function getDerPubKeyWithPubKeyPoints($pubKey, $compressed = true)
 655:     {
 656:         if($compressed === false)
 657:         {
 658:             return '04' . $pubKey['x'] . $pubKey['y'];
 659:         }
 660:         else
 661:         {
 662:             if(gmp_strval(gmp_mod(gmp_init($pubKey['y'], 16), gmp_init(2, 10))) === '0')
 663:                 $pubKey = '02' . $pubKey['x'];  //if $pubKey['y'] is even
 664:             else
 665:                 $pubKey = '03' . $pubKey['x'];  //if $pubKey['y'] is odd
 666: 
 667:             return $pubKey;
 668:         }
 669:     }
 670: 
 671: 
 672: 
 673: 
 674:     /***
 675:      * Returns true if the point is on the curve and false if it isn't.
 676:      *
 677:      * @param string $x (hexa)
 678:      * @param string $y (hexa)
 679:      * @return bool
 680:      */
 681:     public function validatePoint($x, $y)
 682:     {
 683:         $a  = $this->a;
 684:         $b  = $this->b;
 685:         $p  = $this->p;
 686: 
 687:         $x  = gmp_init($x, 16);
 688:         $y2 = gmp_mod(
 689:                         gmp_add(
 690:                             gmp_add(
 691:                                 gmp_powm($x, gmp_init(3, 10), $p),
 692:                                 gmp_mul($a, $x)
 693:                             ),
 694:                             $b
 695:                         ),
 696:                         $p
 697:                     );
 698:         $y = gmp_mod(gmp_pow(gmp_init($y, 16), 2), $p);
 699: 
 700:         if(gmp_cmp($y2, $y) === 0)
 701:             return true;
 702:         else
 703:             return false;
 704:     }
 705: 
 706: 
 707: 
 708: 
 709: 
 710:     /***
 711:      * returns the X and Y point coordinates of the public key.
 712:      *
 713:      * @return Array Point
 714:      * @throws \Exception
 715:      */
 716:     public function getPubKeyPoints()
 717:     {
 718:         $G = $this->G;
 719:         $k = $this->k;
 720: 
 721:         if(!isset($this->k))
 722:         {
 723:             throw new \Exception('No Private Key was defined');
 724:         }
 725: 
 726:         $pubKey = $this->mulPoint(
 727:                                           $k,
 728:                                           ['x' => $G['x'], 'y' => $G['y']]
 729:                                  );
 730: 
 731:         $pubKey['x'] = gmp_strval($pubKey['x'], 16);
 732:         $pubKey['y'] = gmp_strval($pubKey['y'], 16);
 733: 
 734:         while(strlen($pubKey['x']) < 64)
 735:         {
 736:             $pubKey['x'] = '0' . $pubKey['x'];
 737:         }
 738: 
 739:         while(strlen($pubKey['y']) < 64)
 740:         {
 741:             $pubKey['y'] = '0' . $pubKey['y'];
 742:         }
 743: 
 744:         return $pubKey;
 745:     }
 746: 
 747: 
 748: 
 749: 
 750:     /***
 751:      * returns the uncompressed DER encoded public key.
 752:      *
 753:      * @param array $pubKeyPts (array <x:string, y:string>)
 754:      * @return string (hexa)
 755:      * @throws \Exception
 756:      */
 757:     public function getUncompressedPubKey(array $pubKeyPts = [])
 758:     {
 759:         if(empty($pubKeyPts))
 760:             $pubKeyPts = $this->getPubKeyPoints();
 761:         $uncompressedPubKey = '04' . $pubKeyPts['x'] . $pubKeyPts['y'];
 762: 
 763:         return $uncompressedPubKey;
 764:     }
 765: 
 766: 
 767: 
 768: 
 769:     /***
 770:      * returns the compressed DER encoded public key.
 771:      *
 772:      * @param array $pubKeyPts (array <x:string, y:string>)
 773:      * @return array|string
 774:      * @throws \Exception
 775:      */
 776:     public function getPubKey(array $pubKeyPts = [])
 777:     {
 778:         if(empty($pubKeyPts))
 779:             $pubKeyPts = $this->getPubKeyPoints();
 780: 
 781:         if(gmp_strval(gmp_mod(gmp_init($pubKeyPts['y'], 16), gmp_init(2, 10))) === '0')
 782:             $compressedPubKey = '02' . $pubKeyPts['x']; //if $pubKey['y'] is even
 783:         else
 784:             $compressedPubKey = '03' . $pubKeyPts['x']; //if $pubKey['y'] is odd
 785: 
 786:         return $compressedPubKey;
 787:     }
 788: 
 789: 
 790: 
 791: 
 792:     /***
 793:      * returns the uncompressed Bitcoin address generated from the private key if $compressed is false and
 794:      * the compressed if $compressed is true.
 795:      *
 796:      * @param bool $compressed
 797:      * @param string $derPubKey (hexa)
 798:      * @throws \Exception
 799:      * @return String Base58
 800:      */
 801:     public function getUncompressedAddress($compressed = false, $derPubKey = null)
 802:     {
 803:         if($derPubKey !== null)
 804:         {
 805:             if($compressed === true) {
 806:                 $address = $this->getPubKey($this->getPubKeyPointsWithDerPubKey($derPubKey));
 807:             }
 808:             else {
 809:                 $address = $this->getUncompressedPubKey($this->getPubKeyPointsWithDerPubKey($derPubKey));
 810:             }
 811:         }
 812:         else
 813:         {
 814:             if($compressed === true) {
 815:                 $address = $this->getPubKey();
 816:             }
 817:             else {
 818:                 $address = $this->getUncompressedPubKey();
 819:             }
 820:         }
 821: 
 822:         $address = $this->getNetworkPrefix() . $this->hash160(hex2bin($address));
 823: 
 824:         //checksum
 825:         $address = $address.substr($this->hash256(hex2bin($address)), 0, 8);
 826:         $address = $this->base58_encode($address);
 827: 
 828:         if($this->validateAddress($address))
 829:             return $address;
 830:         else
 831:             throw new \Exception('the generated address seems not to be valid.');
 832:     }
 833: 
 834: 
 835: 
 836: 
 837:     /***
 838:      * returns the compressed Bitcoin address generated from the private key.
 839:      *
 840:      * @param string $derPubKey (hexa)
 841:      * @return String (base58)
 842:      */
 843:     public function getAddress($derPubKey = null)
 844:     {
 845:         return $this->getUncompressedAddress(true, $derPubKey);
 846:     }
 847: 
 848: 
 849: 
 850: 
 851:     /***
 852:      * set a private key.
 853:      *
 854:      * @param string $k (hexa)
 855:      * @throws \Exception
 856:      */
 857:     public function setPrivateKey($k)
 858:     {
 859:         //private key has to be passed as an hexadecimal number
 860:         if(gmp_cmp(gmp_init($k, 16), gmp_sub($this->n, gmp_init(1, 10))) === 1)
 861:         {
 862:             throw new \Exception('Private Key is not in the 1,n-1 range');
 863:         }
 864:         $this->k = $k;
 865:     }
 866: 
 867:     /***
 868:      * return the private key.
 869:      *
 870:      * @return string (hexa)
 871:      */
 872:     public function getPrivateKey()
 873:     {
 874:         return $this->k;
 875:     }
 876: 
 877: 
 878: 
 879: 
 880: 
 881:     /***
 882:      * Generate a new random private key.
 883:      * The extra parameter can be some random data typed down by the user or mouse movements to add randomness.
 884:      *
 885:      * @param string $extra
 886:      * @throws \Exception
 887:      */
 888:     public function generateRandomPrivateKey()
 889:     {
 890:         $this->k    = $this->generateRandom256BitsHexaString();
 891:     }
 892: 
 893: 
 894: 
 895: 
 896: 
 897:     /***
 898:      * Tests if the address is valid or not.
 899:      *
 900:      * @param string $address (base58)
 901:      * @return bool
 902:      */
 903:     public function validateAddress($address)
 904:     {
 905:         $address    = hex2bin($this->base58_decode($address));
 906:         if(strlen($address) !== 25)
 907:             return false;
 908:         $checksum   = substr($address, 21, 4);
 909:         $rawAddress = substr($address, 0, 21);
 910: 
 911:         if(substr(hex2bin($this->hash256($rawAddress)), 0, 4) === $checksum)
 912:             return true;
 913:         else
 914:             return false;
 915:     }
 916: 
 917: 
 918: 
 919: 
 920: 
 921:     /***
 922:      * returns the private key under the Wallet Import Format
 923:      *
 924:      * @return string (base58)
 925:      * @throws \Exception
 926:      */
 927:     public function getWif($compressed = true)
 928:     {
 929:         if(!isset($this->k))
 930:         {
 931:             throw new \Exception('No Private Key was defined');
 932:         }
 933: 
 934:         $k          = $this->k;
 935:         
 936:         while(strlen($k) < 64)
 937:             $k = '0' . $k;
 938:         
 939:         $secretKey  =  $this->getPrivatePrefix() . $k;
 940:         
 941:         if($compressed) {
 942:             $secretKey .= '01';
 943:         }
 944:         
 945:         $secretKey .= substr($this->hash256(hex2bin($secretKey)), 0, 8);
 946: 
 947:         return $this->base58_encode($secretKey);
 948:     }
 949:     
 950: 
 951: 
 952: 
 953:     /***
 954:      * returns the private key under the Wallet Import Format for an uncompressed address
 955:      *
 956:      * @return string (base58)
 957:      * @throws \Exception
 958:      */
 959:     public function getUncompressedWif()
 960:     {
 961:         return $this->getWif(false);
 962:     }
 963: 
 964: 
 965: 
 966: 
 967:     /***
 968:      * Tests if the Wif key (Wallet Import Format) is valid or not.
 969:      *
 970:      * @param string $wif (base58)
 971:      * @return bool
 972:      */
 973:     public function validateWifKey($wif)
 974:     {
 975:         $key         = $this->base58_decode($wif, true);
 976:         $length      = strlen($key);
 977:         $checksum    = $this->hash256(hex2bin(substr($key, 0, $length - 8)));
 978:         if(substr($checksum, 0, 8) === substr($key, $length - 8, 8))
 979:             return true;
 980:         else
 981:             return false;
 982:     }
 983: 
 984: 
 985: 
 986:     /**
 987:      * @param string $wif (base58)
 988:      * @return bool
 989:      */
 990:     public function setPrivateKeyWithWif($wif)
 991:     {
 992:         if(!$this->validateWifKey($wif)) {
 993:             throw new \Exception('Invalid WIF');
 994:         }
 995: 
 996:         $key = $this->base58_decode($wif, true);
 997: 
 998:         $this->setPrivateKey(substr($key, 2, 64));
 999:     }
1000: 
1001: 
1002: 
1003: 
1004:     /***
1005:      * Sign a hash with the private key that was set and returns signatures as an array (R,S)
1006:      *
1007:      * @param string $hash (hexa)
1008:      * @param null $nonce
1009:      * @throws \Exception
1010:      * @return Array
1011:      */
1012:     public function getSignatureHashPoints($hash, $nonce = null)
1013:     {
1014:         $n = $this->n;
1015:         $k = $this->k;
1016: 
1017:         if(empty($k))
1018:         {
1019:             throw new \Exception('No Private Key was defined');
1020:         }
1021: 
1022:         if($nonce === null)
1023:         {
1024:             $nonce      = gmp_strval(
1025:                                      gmp_mod(
1026:                                              gmp_init($this->generateRandom256BitsHexaString(), 16),
1027:                                              $n),
1028:                                      16
1029:             );
1030:         }
1031: 
1032:         //first part of the signature (R).
1033: 
1034:         $rPt = $this->mulPoint($nonce, $this->G);
1035:         $R  = gmp_strval($rPt ['x'], 16);
1036: 
1037:         while(strlen($R) < 64)
1038:         {
1039:             $R = '0' . $R;
1040:         }
1041: 
1042:         //second part of the signature (S).
1043:         //S = nonce^-1 (hash + privKey * R) mod p
1044: 
1045: 
1046:         $S = gmp_mod(
1047:             gmp_mul(
1048:                 gmp_invert(
1049:                     gmp_init($nonce, 16),
1050:                     $n
1051:                 ),
1052:                 gmp_add(
1053:                     gmp_init($hash, 16),
1054:                     gmp_mul(
1055:                         gmp_init($k, 16),
1056:                         gmp_init($R, 16)
1057:                     )
1058:                 )
1059:             ),
1060:             $n
1061:         );
1062: 
1063:         //BIP 62, make sure we use the low-s value
1064:         if(gmp_cmp($S, gmp_div($n, 2)) === 1)
1065:         {
1066:             $S = gmp_sub($n, $S);
1067:         }
1068: 
1069:         $S = gmp_strval($S, 16);
1070: 
1071:         if(strlen($S)%2)
1072:         {
1073:             $S = '0' . $S;
1074:         }
1075: 
1076:         if(strlen($R)%2)
1077:         {
1078:             $R = '0' . $R;
1079:         }
1080: 
1081:         return ['R' => $R, 'S' => $S];
1082:     }
1083: 
1084: 
1085: 
1086: 
1087:     /***
1088:      * Sign a hash with the private key that was set and returns a DER encoded signature
1089:      *
1090:      * @param string $hash (hexa)
1091:      * @param null $nonce
1092:      * @return string
1093:      */
1094:     public function signHash($hash, $nonce = null)
1095:     {
1096:         $points = $this->getSignatureHashPoints($hash, $nonce);
1097: 
1098:         $signature = '02' . dechex(strlen(hex2bin($points['R']))) . $points['R'] . '02' . dechex(strlen(hex2bin($points['S']))) . $points['S'];
1099:         $signature = '30' . dechex(strlen(hex2bin($signature))) . $signature;
1100: 
1101:         return $signature;
1102:     }
1103:     
1104: 
1105: 
1106:     /***
1107:      * Signature implementation.
1108:      *
1109:      * @param string $message
1110:      * @param bool $onlySignature
1111:      * @param bool $compressed
1112:      * @param null $nonce
1113:      * @return string
1114:      * @throws \Exception
1115:      */
1116:     public function signMessage($message, $onlySignature = false, $compressed = false, $nonce = null)
1117:     {
1118: 
1119:         $hash   = $this->hash256("\x18Liberty Signed Message:\n" . $this->numToVarIntString(strlen($message)). $message);
1120:         $points = $this->getSignatureHashPoints($hash, $nonce);
1121: 
1122:         $R = $points['R'];
1123:         $S = $points['S'];
1124: 
1125:         while(strlen($R) < 64)
1126:             $R = '0' . $R;
1127: 
1128:         while(strlen($S) < 64)
1129:             $S = '0' . $S;
1130: 
1131:         $res = "\n-----BEGIN LIBERTY SIGNED MESSAGE-----\n";
1132:         $res .= $message;
1133:         $res .= "\n-----BEGIN SIGNATURE-----\n";
1134:         if($compressed === true)
1135:             $res .= $this->getAddress() . "\n";
1136:         else
1137:             $res .= $this->getUncompressedAddress() . "\n";
1138: 
1139:         $finalFlag = 0;
1140:         for($i = 0; $i < 4; $i++)
1141:         {
1142:             $flag = 27;
1143:             if($compressed === true)
1144:                 $flag += 4;
1145:             $flag += $i;
1146: 
1147:             $pubKeyPts = $this->getPubKeyPoints();
1148: 
1149:             $recoveredPubKey = $this->getPubKeyWithRS($flag, $R, $S, $hash);
1150: 
1151:             if($this->getDerPubKeyWithPubKeyPoints($pubKeyPts, $compressed) === $recoveredPubKey)
1152:             {
1153:                 $finalFlag = $flag;
1154:             }
1155:         }
1156: 
1157:         //echo "Final flag : " . dechex($finalFlag) . "\n";
1158:         if($finalFlag === 0)
1159:         {
1160:             throw new \Exception('Unable to get a valid signature flag.');
1161:         }
1162: 
1163:         $signature = base64_encode(hex2bin(dechex($finalFlag) . $R . $S));
1164: 
1165:         if($onlySignature) {
1166:             return $signature;
1167:         }
1168: 
1169:         $res .= $signature;
1170:         $res .= "\n-----END LIBERTY SIGNED MESSAGE-----";
1171: 
1172:         return $res;
1173:     }
1174: 
1175: 
1176: 
1177: 
1178: 
1179:     /***
1180:      * extract the public key from the signature and using the recovery flag.
1181:      * see http://crypto.stackexchange.com/a/18106/10927
1182:      * based on https://github.com/brainwallet/brainwallet.github.io/blob/master/js/bitcoinsig.js
1183:      * possible public keys are r−1(sR−zG) and r−1(sR′−zG)
1184:      * Recovery flag rules are :
1185:      * binary number between 28 and 35 inclusive
1186:      * if the flag is > 30 then the address is compressed.
1187:      *
1188:      * @param int $flag
1189:      * @param string $R (hexa)
1190:      * @param string $S (hexa)
1191:      * @param string $hash (hexa)
1192:      * @return array
1193:      */
1194:     public function getPubKeyWithRS($flag, $R, $S, $hash)
1195:     {
1196: 
1197:         $isCompressed = false;
1198: 
1199:         if ($flag < 27 || $flag >= 35)
1200:             return null;
1201: 
1202:         if($flag >= 31) //if address is compressed
1203:         {
1204:             $isCompressed = true;
1205:             $flag -= 4;
1206:         }
1207: 
1208:         $recid = $flag - 27;
1209: 
1210:         //step 1.1
1211:         $x = gmp_add(
1212:                      gmp_init($R, 16),
1213:                      gmp_mul(
1214:                              $this->n,
1215:                              gmp_div_q( //check if j is equal to 0 or to 1.
1216:                                         gmp_init($recid, 10),
1217:                                         gmp_init(2, 10)
1218:                              )
1219:                      )
1220:              );
1221: 
1222:         //step 1.3
1223:         $y = null;
1224:         if($flag % 2 === 1) //check if y is even.
1225:         {
1226:             $gmpY = $this->calculateYWithX(gmp_strval($x, 16), '02');
1227:             if($gmpY !== null)
1228:                 $y = gmp_init($gmpY, 16);
1229:         }
1230:         else
1231:         {
1232:             $gmpY = $this->calculateYWithX(gmp_strval($x, 16), '03');
1233:             if($gmpY !== null)
1234:                 $y = gmp_init($gmpY, 16);
1235:         }
1236: 
1237:         if($y === null)
1238:             return null;
1239: 
1240:         $Rpt = ['x' => $x, 'y' => $y];
1241: 
1242:         //step 1.6.1
1243:         //calculate r^-1 (S*Rpt - eG)
1244: 
1245:         $eG = $this->mulPoint($hash, $this->G);
1246: 
1247:         $eG['y'] = gmp_mod(gmp_neg($eG['y']), $this->p);
1248: 
1249:         $SR = $this->mulPoint($S, $Rpt);
1250: 
1251:         $pubKey = $this->mulPoint(
1252:                             gmp_strval(gmp_invert(gmp_init($R, 16), $this->n), 16),
1253:                             $this->addPoints(
1254:                                              $SR,
1255:                                              $eG
1256:                             )
1257:                   );
1258: 
1259:         $pubKey['x'] = gmp_strval($pubKey['x'], 16);
1260:         $pubKey['y'] = gmp_strval($pubKey['y'], 16);
1261: 
1262:         while(strlen($pubKey['x']) < 64)
1263:             $pubKey['x'] = '0' . $pubKey['x'];
1264: 
1265:         while(strlen($pubKey['y']) < 64)
1266:             $pubKey['y'] = '0' . $pubKey['y'];
1267: 
1268:         $derPubKey = $this->getDerPubKeyWithPubKeyPoints($pubKey, $isCompressed);
1269: 
1270: 
1271:         if($this->checkSignaturePoints($derPubKey, $R, $S, $hash))
1272:             return $derPubKey;
1273:         else
1274:             return null;
1275: 
1276:     }
1277: 
1278: 
1279: 
1280: 
1281: 
1282:     /***
1283:      * Check signature with public key R & S values of the signature and the message hash.
1284:      *
1285:      * @param string $pubKey (hexa)
1286:      * @param string $R (hexa)
1287:      * @param string $S (hexa)
1288:      * @param string $hash (hexa)
1289:      * @return bool
1290:      */
1291:     public function checkSignaturePoints($pubKey, $R, $S, $hash)
1292:     {
1293:         $G = $this->G;
1294: 
1295:         $pubKeyPts = $this->getPubKeyPointsWithDerPubKey($pubKey);
1296: 
1297:         // S^-1* hash * G + S^-1 * R * Qa
1298: 
1299:         // S^-1* hash
1300:         $exp1 =  gmp_strval(
1301:                             gmp_mul(
1302:                                     gmp_invert(
1303:                                                gmp_init($S, 16),
1304:                                                $this->n
1305:                                     ),
1306:                                     gmp_init($hash, 16)
1307:                             ),
1308:                             16
1309:                  );
1310: 
1311:         // S^-1* hash * G
1312:         $exp1Pt = $this->mulPoint($exp1, $G);
1313: 
1314: 
1315:         // S^-1 * R
1316:         $exp2 =  gmp_strval(
1317:                             gmp_mul(
1318:                                     gmp_invert(
1319:                                                gmp_init($S, 16),
1320:                                                 $this->n
1321:                                     ),
1322:                                     gmp_init($R, 16)
1323:                             ),
1324:                             16
1325:                  );
1326:         // S^-1 * R * Qa
1327: 
1328:         $pubKeyPts['x'] = gmp_init($pubKeyPts['x'], 16);
1329:         $pubKeyPts['y'] = gmp_init($pubKeyPts['y'], 16);
1330: 
1331:         $exp2Pt = $this->mulPoint($exp2,$pubKeyPts);
1332: 
1333:         $resultingPt = $this->addPoints($exp1Pt, $exp2Pt);
1334: 
1335:         $xRes = gmp_strval($resultingPt['x'], 16);
1336: 
1337:         while(strlen($xRes) < 64)
1338:             $xRes = '0' . $xRes;
1339: 
1340:         if(strtoupper($xRes) === strtoupper($R))
1341:             return true;
1342:         else
1343:             return false;
1344:     }
1345: 
1346: 
1347: 
1348: 
1349:     /***
1350:      * checkSignaturePoints wrapper for DER signatures
1351:      *
1352:      * @param string $pubKey (hexa)
1353:      * @param string $signature (hexa)
1354:      * @param string $hash (hexa)
1355:      * @return bool
1356:      */
1357:     public function checkDerSignature($pubKey, $signature, $hash)
1358:     {
1359:         $signature = hex2bin($signature);
1360:         if(bin2hex(substr($signature, 0, 1)) !== '30')
1361:             return false;
1362: 
1363:         $RLength = hexdec(bin2hex(substr($signature, 3, 1)));
1364:         $R = bin2hex(substr($signature, 4, $RLength));
1365: 
1366:         $SLength = hexdec(bin2hex(substr($signature, $RLength + 5, 1)));
1367:         $S = bin2hex(substr($signature, $RLength + 6, $SLength));
1368: 
1369:         //echo "\n\nsignature:\n";
1370:         //print_r(bin2hex($signature));
1371: 
1372:         //echo "\n\nR:\n";
1373:         //print_r($R);
1374:         //echo "\n\nS:\n";
1375:         //print_r($S);
1376: 
1377:         return $this->checkSignaturePoints($pubKey, $R, $S, $hash);
1378:     }
1379: 
1380: 
1381: 
1382: 
1383:     /***
1384:      * checks the signature of a bitcoin signed message.
1385:      *
1386:      * @param string $rawMessage
1387:      * @return bool
1388:      */
1389:     public function checkSignatureForRawMessage($rawMessage)
1390:     {
1391:         //recover message.
1392:         preg_match_all("#-----BEGIN LIBERTY SIGNED MESSAGE-----\n(.{0,})\n-----BEGIN SIGNATURE-----\n#USi", $rawMessage, $out);
1393:         $message = $out[1][0];
1394: 
1395:         preg_match_all("#\n-----BEGIN SIGNATURE-----\n(.{0,})\n(.{0,})\n-----END LIBERTY SIGNED MESSAGE-----#USi", $rawMessage, $out);
1396:         $address = $out[1][0];
1397:         $signature = $out[2][0];
1398: 
1399:         return $this->checkSignatureForMessage($address, $signature, $message);
1400:     }
1401: 
1402: 
1403: 
1404: 
1405: 
1406:     /***
1407:      * checks the signature of a bitcoin signed message.
1408:      *
1409:      * @param string $address (base58)
1410:      * @param string $encodedSignature (base64)
1411:      * @param string $message
1412:      * @return bool
1413:      */
1414:     public function checkSignatureForMessage($address, $encodedSignature, $message)
1415:     {
1416:         $hash = $this->hash256("\x18Liberty Signed Message:\n" . $this->numToVarIntString(strlen($message)) . $message);
1417: 
1418:         //recover flag
1419:         $signature = base64_decode($encodedSignature);
1420: 
1421:         $flag = hexdec(bin2hex(substr($signature, 0, 1)));
1422: 
1423:         $isCompressed = false;
1424:         if($flag >= 31 & $flag < 35) //if address is compressed
1425:         {
1426:             $isCompressed = true;
1427:         }
1428: 
1429:         $R = bin2hex(substr($signature, 1, 32));
1430:         $S = bin2hex(substr($signature, 33, 32));
1431: 
1432:         $derPubKey = $this->getPubKeyWithRS($flag, $R, $S, $hash);
1433: 
1434:         if($isCompressed === true)
1435:             $recoveredAddress = $this->getAddress($derPubKey);
1436:         else
1437:             $recoveredAddress = $this->getUncompressedAddress(false, $derPubKey);
1438: 
1439:         if($address === $recoveredAddress)
1440:             return true;
1441:         else
1442:             return false;
1443:     }
1444: }
1445: 
1446: 
1447: 
1448: