I am attempting to verify a signed message in PHP.
To be clear, I am not looking to interface with JSON-RPC or any external service, which I both a) know works and b) successfully verifies the example signed message I am providing.
Additionally, I am well aware of the "message prefix" and message length issues. That is not where I'm having problems.
The issue appears to be stemming from, either the Signature class I'm using (included in-line below, with all unused bits removed for readability, but pulled from here: https://github.com/tuaris/CryptoCurrencyPHP/blob/master/Signature.class.php) or the GMP transformations to the R and S values extracted from the signature itself.
The only external library in use in my code is https://github.com/0xbb/php-sha3/blob/master/src/Sha3.php, which required a modification to line 334, to change 0x06 to 0x01, for keccak compatibility, which is what Ethereum uses. (I know this was a correct change on my part because keeping it as 0x01 when hashing the original message produces different results when hashing the same message with the web3 libraries.
Below is my code. I would be immensely grateful if someone were able to tell me where I've gone wrong.
<?php
use bb\Sha3\Sha3;
require_once('./Sha3.php');
$message = 'This is an example of a signed message.';
$signerAddress = '0xd4e01f608982ff53022e8c3ff43e145a192a9c4a';
$signedMessage = '0x6a65ed07a44715169177223ce508a2257f8167db452df0b2e37966b39350a61940e370616b3a0ea0f20adfa4661a7db10eeb583ca5a58ec8468e726eff4131a11c';
$signedMessageStrip = '6a65ed07a44715169177223ce508a2257f8167db452df0b2e37966b39350a61940e370616b3a0ea0f20adfa4661a7db10eeb583ca5a58ec8468e726eff4131a11c';
$prefix = "\x19Ethereum Signed Message:\n".strlen($message);
$stringToSign = $prefix.$message;
//\x19Ethereum Signed Message:\n39This is an example of a signed message.
$messageHex = Sha3::hash($stringToSign, 256); //this matches web3.sha() output for the given message and prefix.
$messageGmp = gmp_init("0x".$messageHex);
$r = substr($signedMessageStrip, 0,64);
$s = substr($signedMessageStrip, 64,64);
$v = substr($signedMessageStrip, 128,2);
$vChecksum = hexdec($v) - 27;
if($vChecksum !== 0 && $vChecksum !== 1) { echo "Invalid checksum.\n"; exit; }
$rGmp = gmp_init("0x".$r);
$sGmp = gmp_init("0x".$s);
$publicKey = Signature::recoverPublicKey($rGmp, $sGmp, $messageGmp, $vChecksum);
//the below line is where things are going wrong. The output hash of Sha3::hash($publicKey['x'].$publicKey['y'], 256) is not correct, according to stepping through similar processes using the web3 library, which generates different results, despite an earlier check that publicKey *is* correct. I cannot figure out what's going wrong.
$recovered = "0x".substr(Sha3::hash($publicKey['x'].$publicKey['y'], 256),24)."\n"; //convert to public address format
//$recovered = 0xf2517bd73c56d6d5a5409c4a1ee29c8f2d5438ff
if (strtolower($recovered) == strtolower($signerAddress)) { echo "Address recovered successfully.\n"; }
else { echo "Address NOT recovered successfully.\n"; }
?>
<?php
class SECp256k1 {
public $a;
public $b;
public $p;
public $n;
public $G;
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 = array('x' => gmp_init('55066263022277343669578718895168534326250603453777594175500187360389116729240'),
'y' => gmp_init('32670510020758816978083085130507043184471273380659243275938904335757337482424'));
}
}
class Signature {
public static function recoverPublicKey($R, $S, $hash, $recoveryFlags){
$secp256k1 = new SECp256k1();
$a = $secp256k1->a;
$b = $secp256k1->b;
$G = $secp256k1->G;
$n = $secp256k1->n;
$p = $secp256k1->p;
$isYEven = ($recoveryFlags & 1) != 0;
$isSecondKey = ($recoveryFlags & 2) != 0;
// PointMathGMP::mulPoint wants HEX String
$e = gmp_strval($hash, 16);
$s = gmp_strval($S, 16);
// Precalculate (p + 1) / 4 where p is the field order
// $p_over_four is GMP
static $p_over_four; // XXX just assuming only one curve/prime will be used
if (!$p_over_four) {
$p_over_four = gmp_div(gmp_add($p, 1), 4);
}
// 1.1 Compute x
// $x is GMP
if (!$isSecondKey) {
$x = $R;
} else {
$x = gmp_add($R, $n);
}
// 1.3 Convert x to point
// $alpha is GMP
$alpha = gmp_mod(gmp_add(gmp_add(gmp_pow($x, 3), gmp_mul($a, $x)), $b), $p);
// $beta is DEC String (INT)
$beta = gmp_strval(gmp_powm($alpha, $p_over_four, $p));
// If beta is even, but y isn't or vice versa, then convert it,
// otherwise we're done and y == beta.
if (PointMathGMP::isEvenNumber($beta) == $isYEven) {
// gmp_sub function will convert the DEC String "$beta" into a GMP
// $y is a GMP
$y = gmp_sub($p, $beta);
} else {
// $y is a GMP
$y = gmp_init($beta);
}
// 1.4 Check that nR is at infinity (implicitly done in construtor) -- Not reallly
// $Rpt is Array(GMP, GMP)
$Rpt = array('x' => $x, 'y' => $y);
// 1.6.1 Compute a candidate public key Q = r^-1 (sR - eG)
// $rInv is a HEX String
$rInv = gmp_strval(gmp_invert($R, $n), 16);
// $eGNeg is Array (GMP, GMP)
$eGNeg = PointMathGMP::negatePoint(PointMathGMP::mulPoint($e, $G, $a, $b, $p));
$sR = PointMathGMP::mulPoint($s, $Rpt, $a, $b, $p);
$sR_plus_eGNeg = PointMathGMP::addPoints($sR, $eGNeg, $a, $p);
// $Q is Array (GMP, GMP)
$Q = PointMathGMP::mulPoint($rInv, $sR_plus_eGNeg, $a, $b, $p);
// Q is the derrived public key
// $pubkey is Array (HEX String, HEX String)
// Ensure it's always 64 HEX Charaters
$pubKey['x'] = str_pad(gmp_strval($Q['x'], 16), 64, 0, STR_PAD_LEFT);
$pubKey['y'] = str_pad(gmp_strval($Q['y'], 16), 64, 0, STR_PAD_LEFT);
return $pubKey;
}
}
class PointMathGMP {
/***
* Computes the result of a point addition and returns the resulting point as an Array.
*
* @param Array $pt
* @return Array Point
* @throws \Exception
*/
public static function doublePoint(Array $pt, $a, $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 = array();
$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 static function addPoints(Array $pt1, Array $pt2, $a, $p)
{
if(gmp_cmp($pt1['x'], $pt2['x']) == 0 && gmp_cmp($pt1['y'], $pt2['y']) == 0) //if identical
{
return self::doublePoint($pt1, $a, $p);
}
$gcd = gmp_strval(gmp_gcd(gmp_sub($pt1['x'], $pt2['x']), $p));
if($gcd != '1')
{
throw new \Exception('This library doesn\'t yet support points 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 = array();
$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;
}
/***
* Computes the result of a point multiplication and returns the resulting point as an Array.
*
* @param String Hex $k
* @param Array $pG (GMP, GMP)
* @param $base (INT)
* @throws \Exception
* @return Array Point (GMP, GMP)
*/
public static function mulPoint($k, Array $pG, $a, $b, $p, $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 = self::doublePoint($lastPoint, $a, $p);
$lastPoint = self::addPoints($dPt, $pG, $a, $p);
}
else
{
$lastPoint = self::doublePoint($lastPoint, $a, $p);
}
}
if(!self::validatePoint(gmp_strval($lastPoint['x'], 16), gmp_strval($lastPoint['y'], 16), $a, $b, $p)){
throw new \Exception('The resulting point is not on the curve.');
}
return $lastPoint;
}
/***
* Returns true if the point is on the curve and false if it isn't.
*
* @param $x
* @param $y
* @return bool
*/
public static function validatePoint($x, $y, $a, $b, $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;
else
return false;
}
/***
* Returns Negated Point (Y).
*
* @param $point Array(GMP, GMP)
* @return Array(GMP, GMP)
*/
public static function negatePoint($point) {
return array('x' => $point['x'], 'y' => gmp_neg($point['y']));
}
// Checks is the given number (DEC String) is even
public static function isEvenNumber($number) {
return (((int)$number[strlen($number)-1]) & 1) == 0;
}
}
?>
Best Answer
After much head-banging (against the wall) and isolating the issue to the hashing of the resultant public key, (nicely summarized in my other question, here: Why doesn't my private key's public key generate the correct public address?), it turns out one must pass the bytes, not the hex-hash itself, of the public key to the keccak hashing algorithm.
$recovered = "0x".substr(Sha3::hash(hex2bin($publicKey['x'].$publicKey['y']), 256),24)