<?php

namespace BlockIo;

class BlockKey
{
    public $k;

    public $a;

    public $b;

    public $p;

    public $n;

    public $G;

    public $networkPrefix;

    public $c = true; //compressed or not

    public function __construct()
    {
        $this->a = gmp_init('0', 10);
        $this->b = gmp_init('7', 10);
        $this->p = gmp_init('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F', 16);
        $this->n = gmp_init('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141', 16);

        $this->G = ['x' => gmp_init('55066263022277343669578718895168534326250603453777594175500187360389116729240'),
            'y' => gmp_init('32670510020758816978083085130507043184471273380659243275938904335757337482424')];

        $this->networkPrefix = '00';
    }

    public function toWif($network = 'BTC')
    {
        return $this->getWif($network);
    }

    /***
     * returns the private key under the Wallet Import Format
     *
     * @return String Base58
     * @throws \Exception
     */
    public function getWif($network = 'BTC')
    {
        if (! isset($this->k)) {
            throw new \Exception('No Private Key was defined');
        }

        $privKeyVersions = [];
        $privKeyVersion['BTC'] = '80';
        $privKeyVersion['BTCTEST'] = 'ef';
        $privKeyVersion['DOGE'] = '9e';
        $privKeyVersion['DOGETEST'] = 'f1';
        $privKeyVersion['LTC'] = 'b0';
        $privKeyVersion['LTCTEST'] = 'ef';

        $k = $this->k;
        $secretKey = $privKeyVersion[$network].$k;
        if ($this->c) {
            $secretKey .= '01';
        } // set the compression flag if we need it
        $firstSha256 = hash('sha256', hex2bin($secretKey));
        $secondSha256 = hash('sha256', hex2bin($firstSha256));
        $secretKey .= substr($secondSha256, 0, 8);

        return $this->base58_encode($secretKey);
    }

    /***
     * encode a hexadecimal string in Base58.
     *
     * @param String Hex $data
     * @param bool $littleEndian
     * @return String Base58
     * @throws \Exception
     */
    public function base58_encode($data, $littleEndian = true)
    {
        $res = '';
        $dataIntVal = gmp_init($data, 16);
        while (gmp_cmp($dataIntVal, gmp_init(0, 10)) > 0) {
            $qr = gmp_div_qr($dataIntVal, gmp_init(58, 10));
            $dataIntVal = $qr[0];
            $reminder = gmp_strval($qr[1]);
            if (! $this->base58_permutation($reminder)) {
                throw new \Exception('Something went wrong during base58 encoding');
            }
            $res .= $this->base58_permutation($reminder);
        }

        //get number of leading zeros
        $leading = '';
        $i = 0;
        while (substr($data, $i, 1) == '0') {
            if ($i != 0 && $i % 2) {
                $leading .= '1';
            }
            $i++;
        }

        if ($littleEndian) {
            return strrev($res.$leading);
        }

        return $res.$leading;
    }

    /***
     * Permutation table used for Base58 encoding and decoding.
     *
     * @param $char
     * @param bool $reverse
     * @return null
     */
    public function base58_permutation($char, $reverse = false)
    {
        $table = ['1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D',
            'E', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
            'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'm', 'n', 'o',
            'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
        ];

        if ($reverse) {
            $reversedTable = [];
            foreach ($table as $key => $element) {
                $reversedTable[$element] = $key;
            }

            if (isset($reversedTable[$char])) {
                return $reversedTable[$char];
            }

            return null;
        }

        if (isset($table[$char])) {
            return $table[$char];
        }

        return null;
    }

    public function getPublicKey()
    {
        return $this->getPubKey();
    }

    /***
     * returns the compressed DER encoded public key.
     *
     * @return String Hex
     */
    public function getPubKey()
    {
        $pubKey = '';

        if ($this->c) { // compressed
            $pubKey = $this->getPubKeyPoints();

            if (gmp_strval(gmp_mod(gmp_init($pubKey['y'], 16), gmp_init(2, 10))) == 0) {
                $pubKey = '02'.$pubKey['x'];
            }    //if $pubKey['y'] is even
            else {
                $pubKey = '03'.$pubKey['x'];
            }    //if $pubKey['y'] is odd
        } else { // uncompressed
            $pubKey = $this->getUncompressedPubKey();
        }

        return $pubKey;
    }

    /***
     * returns the X and Y point coordinates of the public key.
     *
     * @return Array Point
     * @throws \Exception
     */
    public function getPubKeyPoints()
    {
        $G = $this->G;
        $k = $this->k;

        if (! isset($this->k)) {
            throw new \Exception('No Private Key was defined');
        }

        $pubKey = $this->mulPoint($k,
            ['x' => $G['x'], 'y' => $G['y']]
        );

        $pubKey['x'] = gmp_strval($pubKey['x'], 16);
        $pubKey['y'] = gmp_strval($pubKey['y'], 16);

        while (strlen($pubKey['x']) < 64) {
            $pubKey['x'] = '0'.$pubKey['x'];
        }

        while (strlen($pubKey['y']) < 64) {
            $pubKey['y'] = '0'.$pubKey['y'];
        }

        return $pubKey;
    }

    /***
     * Computes the result of a point multiplication and returns the resulting point as an Array.
     *
     * @param String Hex $k
     * @param Array $pG
     * @param $base
     * @return Array Point
     * @throws \Exception
     */
    public function mulPoint($k, array $pG, $base = null)
    {
        //in order to calculate k*G
        if ($base == 16 || $base == null || is_resource($base)) {
            $k = gmp_init($k, 16);
        }
        if ($base == 10) {
            $k = gmp_init($k, 10);
        }
        $kBin = gmp_strval($k, 2);

        $lastPoint = $pG;
        for ($i = 1; $i < strlen($kBin); $i++) {
            if (substr($kBin, $i, 1) == 1) {
                $dPt = $this->doublePoint($lastPoint);
                $lastPoint = $this->addPoints($dPt, $pG);
            } else {
                $lastPoint = $this->doublePoint($lastPoint);
            }
        }
        if (! $this->validatePoint(gmp_strval($lastPoint['x'], 16), gmp_strval($lastPoint['y'], 16))) {
            throw new \Exception('The resulting point is not on the curve.');
        }

        return $lastPoint;
    }

    /***
     * Computes the result of a point addition and returns the resulting point as an Array.
     *
     * @param Array $pt
     * @return Array Point
     * @throws \Exception
     */
    public function doublePoint(array $pt)
    {
        $a = $this->a;
        $p = $this->p;

        $gcd = gmp_strval(gmp_gcd(gmp_mod(gmp_mul(gmp_init(2, 10), $pt['y']), $p), $p));
        if ($gcd != '1') {
            throw new \Exception('This library doesn\'t yet supports point at infinity. See https://github.com/BitcoinPHP/BitcoinECDSA.php/issues/9');
        }

        // SLOPE = (3 * ptX^2 + a )/( 2*ptY )
        // Equals (3 * ptX^2 + a ) * ( 2*ptY )^-1
        $slope = gmp_mod(
            gmp_mul(
                gmp_invert(
                    gmp_mod(
                        gmp_mul(
                            gmp_init(2, 10),
                            $pt['y']
                        ),
                        $p
                    ),
                    $p
                ),
                gmp_add(
                    gmp_mul(
                        gmp_init(3, 10),
                        gmp_pow($pt['x'], 2)
                    ),
                    $a
                )
            ),
            $p
        );

        // nPtX = slope^2 - 2 * ptX
        // Equals slope^2 - ptX - ptX
        $nPt = [];
        $nPt['x'] = gmp_mod(
            gmp_sub(
                gmp_sub(
                    gmp_pow($slope, 2),
                    $pt['x']
                ),
                $pt['x']
            ),
            $p
        );

        // nPtY = slope * (ptX - nPtx) - ptY
        $nPt['y'] = gmp_mod(
            gmp_sub(
                gmp_mul(
                    $slope,
                    gmp_sub(
                        $pt['x'],
                        $nPt['x']
                    )
                ),
                $pt['y']
            ),
            $p
        );

        return $nPt;
    }

    /***
     * Computes the result of a point addition and returns the resulting point as an Array.
     *
     * @param Array $pt1
     * @param Array $pt2
     * @return Array Point
     * @throws \Exception
     */
    public function addPoints(array $pt1, array $pt2)
    {
        $p = $this->p;
        if (gmp_cmp($pt1['x'], $pt2['x']) == 0 && gmp_cmp($pt1['y'], $pt2['y']) == 0) { //if identical
            return $this->doublePoint($pt1);
        }

        $gcd = gmp_strval(gmp_gcd(gmp_sub($pt1['x'], $pt2['x']), $p));
        if ($gcd != '1') {
            throw new \Exception('This library doesn\'t yet supports point at infinity. See https://github.com/BitcoinPHP/BitcoinECDSA.php/issues/9');
        }

        // SLOPE = (pt1Y - pt2Y)/( pt1X - pt2X )
        // Equals (pt1Y - pt2Y) * ( pt1X - pt2X )^-1
        $slope = gmp_mod(
            gmp_mul(
                gmp_sub(
                    $pt1['y'],
                    $pt2['y']
                ),
                gmp_invert(
                    gmp_sub(
                        $pt1['x'],
                        $pt2['x']
                    ),
                    $p
                )
            ),
            $p
        );

        // nPtX = slope^2 - ptX1 - ptX2
        $nPt = [];
        $nPt['x'] = gmp_mod(
            gmp_sub(
                gmp_sub(
                    gmp_pow($slope, 2),
                    $pt1['x']
                ),
                $pt2['x']
            ),
            $p
        );

        // nPtX = slope * (ptX1 - nPtX) - ptY1
        $nPt['y'] = gmp_mod(
            gmp_sub(
                gmp_mul(
                    $slope,
                    gmp_sub(
                        $pt1['x'],
                        $nPt['x']
                    )
                ),
                $pt1['y']
            ),
            $p
        );

        return $nPt;
    }

    /***
     * Returns true if the point is on the curve and false if it isn't.
     *
     * @param $x
     * @param $y
     * @return bool
     */
    public function validatePoint($x, $y)
    {
        $a = $this->a;
        $b = $this->b;
        $p = $this->p;

        $x = gmp_init($x, 16);
        $y2 = gmp_mod(
            gmp_add(
                gmp_add(
                    gmp_powm($x, gmp_init(3, 10), $p),
                    gmp_mul($a, $x)
                ),
                $b
            ),
            $p
        );
        $y = gmp_mod(gmp_pow(gmp_init($y, 16), 2), $p);

        if (gmp_cmp($y2, $y) == 0) {
            return true;
        }

        return false;
    }

    /***
     * returns the uncompressed DER encoded public key.
     *
     * @return String Hex
     */
    public function getUncompressedPubKey()
    {
        $pubKey = $this->getPubKeyPoints();
        $uncompressedPubKey = '04'.$pubKey['x'].$pubKey['y'];

        return $uncompressedPubKey;
    }

    public function fromPassphrase($pp)
    {  // take a sha256 hash of the passphrase, and then set it as the private key

        $hashed = hash('sha256', hex2bin($pp));

        return $this->fromHex($hashed);

    }

    public function fromHex($pp)
    {

        $paddedpp = str_pad($pp, 64, '0', STR_PAD_LEFT);

        if (preg_match('/^[a-f0-9]{64}$/', $paddedpp) != 1) {
            throw new \Exception('Private Key must be hexadecimal and 64 characters long');
        }

        $this->setPrivateKey($paddedpp);

        return $this;

    }

    /***
     * set a private key.
     *
     * @param String Hex $k
     * @throws \Exception
     */
    private function setPrivateKey($k)
    { // enforce 64 char hex strings, so don't allow use of this directly

        //private key has to be passed as an hexadecimal number
        if (gmp_cmp(gmp_init($k, 16), gmp_sub($this->n, gmp_init(1, 10))) == 1) {
            throw new \Exception('Private Key is not in the 1,n-1 range');
        }
        $this->k = $k;
    }

    public function fromWif($pp)
    { // extract the private key from the key in Wallet Import Format

        // TODO validation

        if ($this->validateWifKey($pp) === false) {
            throw new \Exception('Invalid Private Key provided.');
        }

        $fullStr = $this->base58_decode($pp);
        $withoutVersion = substr($fullStr, 2);
        $withoutChecksumAndVersion = substr($withoutVersion, 0, 64);

        $this->setPrivateKey($withoutChecksumAndVersion);

        if (substr($withoutVersion, 64, 2) == '01') { // is compressed
            $this->c = true;
        } else { // is not compressed
            $this->c = false;
        }

        return $this;
    }

    /***
     * Tests if the Wif key (Wallet Import Format) is valid or not.
     *
     * @param String Base58 $wif
     * @return bool
     */
    public function validateWifKey($wif)
    {
        $key = $this->base58_decode($wif, true);
        $length = strlen($key);
        $firstSha256 = hash('sha256', hex2bin(substr($key, 0, $length - 8)));
        $secondSha256 = hash('sha256', hex2bin($firstSha256));
        if (substr($secondSha256, 0, 8) == substr($key, $length - 8, 8)) {
            return true;
        }

        return false;
    }

    /***
     * Decode a Base58 encoded string and returns it's value as a hexadecimal string
     *
     * @param $encodedData
     * @param bool $littleEndian
     * @return String Hex
     */
    public function base58_decode($encodedData, $littleEndian = true)
    {
        $res = gmp_init(0, 10);
        $length = strlen($encodedData);
        if ($littleEndian) {
            $encodedData = strrev($encodedData);
        }

        for ($i = $length - 1; $i >= 0; $i--) {
            $res = gmp_add(
                gmp_mul(
                    $res,
                    gmp_init(58, 10)
                ),
                $this->base58_permutation(substr($encodedData, $i, 1), true)
            );
        }

        $res = gmp_strval($res, 16);
        $i = $length - 1;
        while (substr($encodedData, $i, 1) == '1') {
            $res = '00'.$res;
            $i--;
        }

        if (strlen($res) % 2 != 0) {
            $res = '0'.$res;
        }

        return $res;
    }

    /***
     * return the private key.
     *
     * @return String Hex
     */
    public function getPrivateKey()
    {
        return $this->k;
    }

    /***
     * Generate a new random private key.
     * The extra parameter can be some random data typed down by the user or mouse movements to add randomness.
     *
     * @param string $extra
     * @throws \Exception
     */
    public function generateRandomPrivateKey($extra = 'FSQF5356dsdsqdfEFEQ3fq4q6dq4s5d')
    {
        //private key has to be passed as an hexadecimal number
        do { //generate a new random private key until to find one that is valid
            $bytes = openssl_random_pseudo_bytes(256, $cStrong);
            $hex = bin2hex($bytes);
            $random = $hex.microtime(true).rand(100000000000, 1000000000000).$extra;
            $this->k = hash('sha256', $random);

            if (! $cStrong) {
                throw new \Exception('Your system is not able to generate strong enough random numbers');
            }

        } while (gmp_cmp(gmp_init($this->k, 16), gmp_sub($this->n, gmp_init(1, 10))) == 1);

        return $this;
    }

    public function String2Hex($string)
    {
        $hex = '';
        for ($i = 0; $i < strlen($string); $i++) {
            $hex .= dechex(ord($string[$i]));
        }

        return $hex;
    }

    public function sign($hash, $nonce = null)
    {
        return $this->signHash($hash, $nonce);
    }

    /***
     * Sign a hash with the private key that was set and returns a DER encoded signature
     *
     * @param $hash
     * @param null $nonce
     * @return string
     */
    public function signHash($hash, $nonce = null)
    {

        $points = $this->getSignatureHashPoints($hash, $nonce);

        $signature = '02'.dechex(strlen(hex2bin($points['R']))).$points['R'].'02'.dechex(strlen(hex2bin($points['S']))).$points['S'];
        $signature = '30'.dechex(strlen(hex2bin($signature))).$signature;

        return $signature;
    }

    /***
     * Sign a hash with the private key that was set and returns signatures as an array (R,S)
     *
     * @param $hash
     * @param null $nonce
     * @return Array
     * @throws \Exception
     */
    public function getSignatureHashPoints($hash, $nonce = null)
    {
        $n = $this->n;
        $k = $this->k;
        $counter = 0;
        $extra_entropy = '';
        $nonce_not_provided = is_null($nonce);

        if (empty($k)) {
            throw new \Exception('No Private Key was defined');
        }

        do {
            if ($nonce_not_provided) {
                // use a deterministic nonce

                if ($counter > 0) {
                    $extra_entropy = implode(array_reverse(str_split(sprintf('%064s', dechex($counter)), 2)));
                }

                $nonce = $this->deterministicGenerateK($hash, $this->k, $extra_entropy);
                $counter = $counter + 1;
            }

            //first part of the signature (R).

            $rPt = $this->mulPoint($nonce, $this->G);
            $R = gmp_strval($rPt['x'], 16);

            // fix DER encoding -- pad it so we don't confuse overflow with being negative
            if (strlen($R) % 2) {
                $R = '0'.$R;
            } elseif (hexdec(substr($R, 0, 1)) >= 8) {
                $R = '00'.$R;
            }

        } while ($nonce_not_provided && (strlen(hex2bin($R)) != 32 || hexdec(substr($R, 0, 1)) >= 128));

        //second part of the signature (S).
        //S = nonce^-1 (hash + privKey * R) mod p

        $S = gmp_strval(
            gmp_mod(
                gmp_mul(
                    gmp_invert(
                        gmp_init($nonce, 16),
                        $n
                    ),
                    gmp_add(
                        gmp_init($hash, 16),
                        gmp_mul(
                            gmp_init($k, 16),
                            gmp_init($R, 16)
                        )
                    )
                ),
                $n
            ),
            16
        );

        // implement BIP62

        $gmpS = gmp_init($S, 16);
        $N_OVER_TWO = gmp_div($this->n, 2);

        if (gmp_cmp($gmpS, $N_OVER_TWO) > 0) {
            $S = gmp_strval(gmp_sub($this->n, $gmpS), 16);
        }

        // fix DER encoding -- pad it so we don't confuse overflow with being negative
        if (strlen($S) % 2) {
            $S = '0'.$S;
        } elseif (hexdec(substr($S, 0, 1)) >= 8) {
            $S = '00'.$S;
        }

        return ['R' => $R, 'S' => $S];
    }

    public function deterministicGenerateK($message, $key, $extra_entropy)
    { // key in hex, message as it is
        // RFC6979

        $hash = $message;

        $k = '0000000000000000000000000000000000000000000000000000000000000000';
        $v = '0101010101010101010101010101010101010101010101010101010101010101';

        $e = '';

        if (! is_null($extra_entropy)) {
            $e = $extra_entropy;
        }

        // step D
        $k = hash_hmac('sha256', hex2bin($v).hex2bin('00').hex2bin($key).hex2bin($hash).hex2bin($e), hex2bin($k));

        // step E
        $v = hash_hmac('sha256', hex2bin($v), hex2bin($k));

        // step F
        $k = hash_hmac('sha256', hex2bin($v).hex2bin('01').hex2bin($key).hex2bin($hash).hex2bin($e), hex2bin($k));

        // step G
        $v = hash_hmac('sha256', hex2bin($v), hex2bin($k));

        // H2b
        $h2b = hash_hmac('sha256', hex2bin($v), hex2bin($k));

        $tNum = gmp_init($h2b, 16);

        // step H3
        while (gmp_sign($tNum) <= 0 || gmp_cmp($tNum, $this->n) >= 0) {
            $k = hash_hmac('sha256', hex2bin($v).hex2bin('00'), hex2bin($k));
            $v = hash_hmac('sha256', hex2bin($v), hex2bin($k));

            $tNum = gmp_init($v, 16);
        }

        return gmp_strval($tNum, 16);
    }

    /***
     * Satoshi client's standard message signature implementation.
     *
     * @param $message
     * @param bool $compressed
     * @param null $nonce
     * @return string
     * @throws \Exception
     */
    public function signMessage($message, $compressed = true, $nonce = null)
    {

        $hash = $this->hash256("\x18Bitcoin Signed Message:\n".$this->numToVarIntString(strlen($message)).$message);
        $points = $this->getSignatureHashPoints(
            $hash,
            $nonce
        );

        $R = $points['R'];
        $S = $points['S'];

        while (strlen($R) < 64) {
            $R = '0'.$R;
        }

        while (strlen($S) < 64) {
            $S = '0'.$S;
        }

        $res = "\n-----BEGIN BITCOIN SIGNED MESSAGE-----\n";
        $res .= $message;
        $res .= "\n-----BEGIN SIGNATURE-----\n";
        if ($compressed == true) {
            $res .= $this->getAddress()."\n";
        } else {
            $res .= $this->getUncompressedAddress()."\n";
        }

        $finalFlag = 0;
        for ($i = 0; $i < 4; $i++) {
            $flag = 27;
            if ($compressed == true) {
                $flag += 4;
            }
            $flag += $i;

            $pubKeyPts = $this->getPubKeyPoints();

            $recoveredPubKey = $this->getPubKeyWithRS($flag, $R, $S, $hash);

            if ($this->getDerPubKeyWithPubKeyPoints($pubKeyPts, $compressed) == $recoveredPubKey) {
                $finalFlag = $flag;
            }
        }

        if ($finalFlag == 0) {
            throw new \Exception('Unable to get a valid signature flag.');
        }

        $res .= base64_encode(hex2bin(dechex($finalFlag).$R.$S));
        $res .= "\n-----END BITCOIN SIGNED MESSAGE-----";

        return $res;
    }

    /***
     * Bitcoin standard 256 bit hash function : double sha256
     *
     * @param $data
     * @return string
     */
    public function hash256($data)
    {
        return hash('sha256', hex2bin(hash('sha256', $data)));
    }

    /***
     * Convert a number to a compact Int
     * taken from https://github.com/scintill/php-bitcoin-signature-routines/blob/master/verifymessage.php
     *
     * @param $i
     * @return string
     * @throws \Exception
     */
    public function numToVarIntString($i)
    {
        if ($i < 0xFD) {
            return chr($i);
        } elseif ($i <= 0xFFFF) {
            return pack('Cv', 0xFD, $i);
        } elseif ($i <= 0xFFFFFFFF) {
            return pack('CV', 0xFE, $i);
        }
        throw new \Exception('int too large');
    }

    /***
     * returns the compressed Bitcoin address generated from the private key.
     *
     * @param string $derPubKey
     * @return String Base58
     */
    public function getAddress($derPubKey = null)
    {
        return $this->getUncompressedAddress(true, $derPubKey);
    }

    /***
     * returns the uncompressed Bitcoin address generated from the private key if $compressed is false and
     * the compressed if $compressed is true.
     *
     * @param bool $compressed
     * @param string $derPubKey
     * @return String Base58
     * @throws \Exception
     */
    public function getUncompressedAddress($compressed = false, $derPubKey = null)
    {
        if ($derPubKey != null) {
            $address = $derPubKey;
        } else {
            if ($compressed) {
                $address = $this->getPubKey();
            } else {
                $address = $this->getUncompressedPubKey();
            }
        }

        $sha256 = hash('sha256', hex2bin($address));
        $ripem160 = hash('ripemd160', hex2bin($sha256));
        $address = $this->getNetworkPrefix().$ripem160;

        //checksum
        $sha256 = hash('sha256', hex2bin($address));
        $sha256 = hash('sha256', hex2bin($sha256));
        $address = $address.substr($sha256, 0, 8);
        $address = $this->base58_encode($address);

        if ($this->validateAddress($address)) {
            return $address;
        }

        throw new \Exception('the generated address seems not to be valid.');
    }

    /**
     * Returns the current network prefix, '00' = main network, '6f' = test network.
     *
     * @return string Hex
     */
    public function getNetworkPrefix()
    {
        return $this->networkPrefix;
    }

    /***
     * Set the network prefix, '00' = main network, '6f' = test network.
     *
     * @param String Hex $prefix
     */
    public function setNetworkPrefix($prefix)
    {
        $this->networkPrefix = $prefix;
    }

    /***
     * Tests if the address is valid or not.
     *
     * @param String Base58 $address
     * @return bool
     */
    public function validateAddress($address)
    {
        $address = hex2bin($this->base58_decode($address));
        if (strlen($address) != 25) {
            return false;
        }
        $checksum = substr($address, 21, 4);
        $rawAddress = substr($address, 0, 21);
        $sha256 = hash('sha256', $rawAddress);
        $sha256 = hash('sha256', hex2bin($sha256));

        if (substr(hex2bin($sha256), 0, 4) == $checksum) {
            return true;
        }

        return false;
    }

    /***
     * extract the public key from the signature and using the recovery flag.
     * see http://crypto.stackexchange.com/a/18106/10927
     * based on https://github.com/brainwallet/brainwallet.github.io/blob/master/js/bitcoinsig.js
     * possible public keys are r−1(sR−zG) and r−1(sR′−zG)
     * Recovery flag rules are :
     * binary number between 28 and 35 inclusive
     * if the flag is > 30 then the address is compressed.
     *
     * @param $flag
     * @param $R
     * @param $S
     * @param $hash
     * @return array
     */
    public function getPubKeyWithRS($flag, $R, $S, $hash)
    {

        $isCompressed = false;

        if ($flag < 27 || $flag >= 35) {
            return false;
        }

        if ($flag >= 31) { //if address is compressed
            $isCompressed = true;
            $flag -= 4;
        }

        $recid = $flag - 27;

        //step 1.1
        $x = null;
        $x = gmp_add(
            gmp_init($R, 16),
            gmp_mul(
                $this->n,
                gmp_div_q( //check if j is equal to 0 or to 1.
                    gmp_init($recid, 10),
                    gmp_init(2, 10)
                )
            )
        );

        //step 1.3
        $y = null;
        if ($flag % 2 == 1) { //check if y is even.
            $gmpY = $this->calculateYWithX(gmp_strval($x, 16), '02');
            if ($gmpY != null) {
                $y = gmp_init($gmpY, 16);
            }
        } else {
            $gmpY = $this->calculateYWithX(gmp_strval($x, 16), '03');
            if ($gmpY != null) {
                $y = gmp_init($gmpY, 16);
            }
        }

        if ($y == null) {
            return null;
        }

        $Rpt = ['x' => $x, 'y' => $y];

        //step 1.6.1
        //calculate r^-1 (S*Rpt - eG)

        $eG = $this->mulPoint($hash, $this->G);

        $eG['y'] = gmp_mod(gmp_neg($eG['y']), $this->p);

        $SR = $this->mulPoint($S, $Rpt);

        $pubKey = $this->mulPoint(
            gmp_strval(gmp_invert(gmp_init($R, 16), $this->n), 16),
            $this->addPoints(
                $SR,
                $eG
            )
        );

        $pubKey['x'] = gmp_strval($pubKey['x'], 16);
        $pubKey['y'] = gmp_strval($pubKey['y'], 16);

        while (strlen($pubKey['x']) < 64) {
            $pubKey['x'] = '0'.$pubKey['x'];
        }

        while (strlen($pubKey['y']) < 64) {
            $pubKey['y'] = '0'.$pubKey['y'];
        }

        $derPubKey = $this->getDerPubKeyWithPubKeyPoints($pubKey, $isCompressed);

        if ($this->checkSignaturePoints($derPubKey, $R, $S, $hash)) {
            return $derPubKey;
        }

        return false;

    }

    public function getDerPubKeyWithPubKeyPoints($pubKey, $compressed = true)
    {
        if ($compressed == true) {
            return '04'.$pubKey['x'].$pubKey['y'];
        }
        if (gmp_strval(gmp_mod(gmp_init($pubKey['y'], 16), gmp_init(2, 10))) == 0) {
            $pubKey = '02'.$pubKey['x'];
        }    //if $pubKey['y'] is even
        else {
            $pubKey = '03'.$pubKey['x'];
        }    //if $pubKey['y'] is odd

        return $pubKey;

    }

    /***
     * Check signature with public key R & S values of the signature and the message hash.
     *
     * @param $pubKey
     * @param $R
     * @param $S
     * @param $hash
     * @return bool
     */
    public function checkSignaturePoints($pubKey, $R, $S, $hash)
    {
        $G = $this->G;

        $pubKeyPts = $this->getPubKeyPointsWithDerPubKey($pubKey);

        // S^-1* hash * G + S^-1 * R * Qa

        // S^-1* hash
        $exp1 = gmp_strval(
            gmp_mul(
                gmp_invert(
                    gmp_init($S, 16),
                    $this->n
                ),
                gmp_init($hash, 16)
            ),
            16
        );

        // S^-1* hash * G
        $exp1Pt = $this->mulPoint($exp1, $G);

        // S^-1 * R
        $exp2 = gmp_strval(
            gmp_mul(
                gmp_invert(
                    gmp_init($S, 16),
                    $this->n
                ),
                gmp_init($R, 16)
            ),
            16
        );
        // S^-1 * R * Qa

        $pubKeyPts['x'] = gmp_init($pubKeyPts['x'], 16);
        $pubKeyPts['y'] = gmp_init($pubKeyPts['y'], 16);

        $exp2Pt = $this->mulPoint($exp2, $pubKeyPts);

        $resultingPt = $this->addPoints($exp1Pt, $exp2Pt);

        $xRes = gmp_strval($resultingPt['x'], 16);

        while (strlen($xRes) < 64) {
            $xRes = '0'.$xRes;
        }

        if ($xRes == $R) {
            return true;
        }

        return false;
    }

    /***
     * returns the public key coordinates as an array.
     *
     * @param $derPubKey
     * @return array
     * @throws \Exception
     */
    public function getPubKeyPointsWithDerPubKey($derPubKey)
    {
        if (substr($derPubKey, 0, 2) == '04' && strlen($derPubKey) == 130) {
            //uncompressed der encoded public key
            $x = substr($derPubKey, 2, 64);
            $y = substr($derPubKey, 66, 64);

            return ['x' => $x, 'y' => $y];
        } elseif ((substr($derPubKey, 0, 2) == '02' || substr($derPubKey, 0, 2) == '03') && strlen($derPubKey) == 66) {
            //compressed der encoded public key
            $x = substr($derPubKey, 2, 64);
            $y = $this->calculateYWithX($x, substr($derPubKey, 0, 2));

            return ['x' => $x, 'y' => $y];
        }
        throw new \Exception('Invalid derPubKey format : '.$derPubKey);
    }

    /***
     * Calculate the Y coordinates for a given X coordinate.
     *
     * @param $x
     * @param null $derEvenOrOddCode
     * @return array|null|String
     */
    public function calculateYWithX($x, $derEvenOrOddCode = null)
    {
        $a = $this->a;
        $b = $this->b;
        $p = $this->p;

        $x = gmp_init($x, 16);
        $y2 = gmp_mod(
            gmp_add(
                gmp_add(
                    gmp_powm($x, gmp_init(3, 10), $p),
                    gmp_mul($a, $x)
                ),
                $b
            ),
            $p
        );

        $y = $this->sqrt($y2);

        if (! $y) { //if there is no result
            return null;
        }

        if (! $derEvenOrOddCode) {
            return $y;
        } elseif ($derEvenOrOddCode == '02') { // even
            $resY = null;
            if (gmp_strval(gmp_mod($y[0], gmp_init(2, 10)), 10) == false) {
                $resY = gmp_strval($y[0], 16);
            }
            if (gmp_strval(gmp_mod($y[1], gmp_init(2, 10)), 10) == false) {
                $resY = gmp_strval($y[1], 16);
            }
            if ($resY) {
                while (strlen($resY) < 64) {
                    $resY = '0'.$resY;
                }
            }

            return $resY;
        } elseif ($derEvenOrOddCode == '03') { // odd
            $resY = null;
            if (gmp_strval(gmp_mod($y[0], gmp_init(2, 10)), 10) == true) {
                $resY = gmp_strval($y[0], 16);
            }
            if (gmp_strval(gmp_mod($y[1], gmp_init(2, 10)), 10) == true) {
                $resY = gmp_strval($y[1], 16);
            }
            if ($resY) {
                while (strlen($resY) < 64) {
                    $resY = '0'.$resY;
                }
            }

            return $resY;
        }

        return null;
    }

    /***
     * Calculates the square root of $a mod p and returns the 2 solutions as an array.
     *
     * @param $a
     * @return array|null
     * @throws \Exception
     */
    public function sqrt($a)
    {
        $p = $this->p;

        if (gmp_legendre($a, $p) != 1) {
            //no result
            return null;
        }

        if (gmp_strval(gmp_mod($p, gmp_init(4, 10)), 10) == 3) {
            $sqrt1 = gmp_powm(
                $a,
                gmp_div_q(
                    gmp_add($p, gmp_init(1, 10)),
                    gmp_init(4, 10)
                ),
                $p
            );
            // there are always 2 results for a square root
            // In an infinite number field you have -2^2 = 2^2 = 4
            // In a finite number field you have a^2 = (p-a)^2
            $sqrt2 = gmp_mod(gmp_sub($p, $sqrt1), $p);

            return [$sqrt1, $sqrt2];
        }
        throw new \Exception('P % 4 != 3 , this isn\'t supported yet.');
    }

    /***
     * checkSignaturePoints wrapper for DER signatures
     *
     * @param $pubKey
     * @param $signature
     * @param $hash
     * @return bool
     */
    public function checkDerSignature($pubKey, $signature, $hash)
    {
        $signature = hex2bin($signature);
        if (bin2hex(substr($signature, 0, 1)) != '30') {
            return false;
        }

        $RLength = hexdec(bin2hex(substr($signature, 3, 1)));
        $R = bin2hex(substr($signature, 4, $RLength));

        $SLength = hexdec(bin2hex(substr($signature, $RLength + 5, 1)));
        $S = bin2hex(substr($signature, $RLength + 6, $SLength));

        return $this->checkSignaturePoints($pubKey, $R, $S, $hash);
    }

    /***
     * checks the signature of a bitcoin signed message.
     *
     * @param $rawMessage
     * @return bool
     */
    public function checkSignatureForRawMessage($rawMessage)
    {
        //recover message.
        preg_match_all("#-----BEGIN BITCOIN SIGNED MESSAGE-----\n(.{0,})\n-----BEGIN SIGNATURE-----\n#USi", $rawMessage, $out);
        $message = $out[1][0];

        preg_match_all("#\n-----BEGIN SIGNATURE-----\n(.{0,})\n(.{0,})\n-----END BITCOIN SIGNED MESSAGE-----#USi", $rawMessage, $out);
        $address = $out[1][0];
        $signature = $out[2][0];

        return $this->checkSignatureForMessage($address, $signature, $message);
    }

    /***
     * checks the signature of a bitcoin signed message.
     *
     * @param $address
     * @param $encodedSignature
     * @param $message
     * @return bool
     */
    public function checkSignatureForMessage($address, $encodedSignature, $message)
    {
        $hash = $this->hash256("\x18Bitcoin Signed Message:\n".$this->numToVarIntString(strlen($message)).$message);

        //recover flag
        $signature = base64_decode($encodedSignature);

        $flag = hexdec(bin2hex(substr($signature, 0, 1)));

        $R = bin2hex(substr($signature, 1, 64));
        $S = bin2hex(substr($signature, 65, 64));

        $derPubKey = $this->getPubKeyWithRS($flag, $R, $S, $hash);

        $recoveredAddress = $this->getAddress($derPubKey);

        if ($address == $recoveredAddress) {
            return true;
        }

        return false;
    }
}
