Recovery function

[sc0Vu]

Recovery function

Go: https://github.com/ethereum/go-ethereum/tree/master/crypto/secp256k1

Js: https://github.com/indutny/elliptic/blob/master/lib/elliptic/ec/index.js#L193
https://github.com/ethereumjs/ethereumjs-util/blob/fde15dd0cc65885dc8731d1bd2facbba78fb39ac/index.js#L386

bitcoin: https://github.com/bitcoin-core/secp256k1/tree/master/src/modules/recovery

• signature recovery param
• signature recovery function
• more tests

[sc0Vu]

var recoveryParam = (kp.getY().isOdd() ? 1 : 0) |
                        (kpX.cmp(r) !== 0 ? 2 : 0);

// Use complement of `s`, if it is > `n / 2`
if (options.canonical && s.cmp(this.nh) > 0) {
  s = this.n.sub(s);
  recoveryParam ^= 1; // recoveryParam is recoveryParam XOR 1
}

s.v = s.recovery + 27 + (chainId * 2) + 8;

// from ec recovery
EC.prototype.recoverPubKey = function(msg, signature, j, enc) {
  assert((3 & j) === j, 'The recovery param is more than two bits');
  signature = new Signature(signature, enc);

  var n = this.n;
  var e = new BN(msg);
  var r = signature.r;
  var s = signature.s;

  // A set LSB signifies that the y-coordinate is odd
  var isYOdd = j & 1;
  var isSecondKey = j >> 1;
  if (r.cmp(this.curve.p.umod(this.curve.n)) >= 0 && isSecondKey)
    throw new Error('Unable to find sencond key candinate');

  // 1.1. Let x = r + jn.
  if (isSecondKey)
    r = this.curve.pointFromX(r.add(this.curve.n), isYOdd);
  else
    r = this.curve.pointFromX(r, isYOdd);

  var rInv = signature.r.invm(n);
  var s1 = n.sub(e).mul(rInv).umod(n);
  var s2 = s.mul(rInv).umod(n);

  // 1.6.1 Compute Q = r^-1 (sR -  eG)
  //               Q = r^-1 (sR + -eG)
  return this.g.mulAdd(s1, r, s2);
};

mulAdd

var points = [ this, p2 ];
var coeffs = [ k1, k2 ];

if (this.curve.endo)
  return this.curve._endoWnafMulAdd(points, coeffs); // goes here
else
  return this.curve._wnafMulAdd(1, points, coeffs, 2);

[digitaldonkey]

Finally I got it running https://github.com/digitaldonkey/ecverify

[sc0Vu]

@digitaldonkey Cool, I think elliptic-php is a good library also I didn't want to give up phpecc:!
By the way I had created an issue in phpecc: phpecc/phpecc#237.