Styjun

I have some code below that will be used to verify the authenticity of a message using javascript. The key pair generation using the elliptic curve secp256k1 is pretty straight forward however I am failing to understand why my signature implementation is not working (why the message is not being successfully verified). Here is my code:

https://pastebin.com/k1WT6apV

/**
* Signature Generation
*/
var g = bigInt('55066263022277343669578718895168534326250603453777594175500187360389116729240');
var n = bigInt('115792089237316195423570985008687907852837564279074904382605163141518161494337');
var p = bigInt('115792089237316195423570985008687907853269984665640564039457584007908834671663'); 
var k = bigInt.randBetween("1", n.subtract(1));
var r = bigInt("0");
var s = bigInt("0");
var privateKey = bigInt('5943918703142138746985297990399309008462887494775678462183405629775262082646');
var publicKey = bigInt(privateKey.multiply(g)).mod(p); 


while(s.equals("0"))
 while(r.equals("0"))
 k = bigInt.randBetween("1", n.subtract(1));
 while(bigInt(k).isPrime() == false)
 k = bigInt.randBetween("1", n.subtract(1));
 
 var xCoord = bigInt(k.multiply(g)).mod(p);
 r = xCoord.mod(n);
 
 var kInverse = k.modInv(n);
 var hashedMessage = bigInt(sha1('hello'),16); 
 s = bigInt(kInverse*(hashedMessage.add(privateKey.multiply(r)))).mod(n) 

var signatureParams = 
 "publicKey": publicKey.toString(),
 "r": r.toString(),
 "sign": s.toString()


/**
* Signature Verification
*/
var sInverse = bigInt(signatureParams.sign).modInv(n);
var publicKey = bigInt(signatureParams.publicKey);
var w = sInverse.mod(n);
var hashedMessage = bigInt(sha1('hello'),16);
var u1 = bigInt(hashedMessage.multiply(w)).mod(n);
var u2 = bigInt(bigInt(r).multiply(w)).mod(n);
var P = bigInt(u1.multiply(g)).add(u2.multiply(publicKey));
P == r

It can be tested easily using the browser console.
I have used an amalgamation of information from the following guides:

https://www.maximintegrated.com/en/app-notes/index.mvp/id/5767

http://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf

https://pdfs.semanticscholar.org/c06a/d6512775be1076e4abd43e3f2928729da776.pdf

What is wrong with my implementation? Am I missing something? Did I do something wrong?

EDIT:

After doing some revision I came up with the following:

var g = bigInt('55066263022277343669578718895168534326250603453777594175500187360389116729240');
var n = bigInt('115792089237316195423570985008687907852837564279074904382605163141518161494337');
var p = bigInt('115792089237316195423570985008687907853269984665640564039457584007908834671663'); 
var privateKey = bigInt('90436540941140970165633788406609967146985661161263948799654498545867952662296');
var publicKey = bigInt(privateKey.multiply(g)).mod(p);

var generateSignature = function(hashedMessage)
 hashedMessage = bigInt(hashedMessage,16);
 var k = bigInt.randBetween("1", n.subtract(1));
 var r = bigInt("0");
 var s = bigInt("0");
 while(s.equals("0"))
 r = bigInt("0");
 while(r.equals("0"))
 k = bigInt.randBetween("1", n.subtract(1));
 r = bigInt(bigInt(k.multiply(g)).mod(p)).mod(n);
 
 var kInverse = k.modInv(n); 
 var pr = privateKey.multiply(r);
 hashedMessage = hashedMessage.add(pr);
 kInverse = kInverse.multiply(hashedMessage);
 s = kInverse.mod(n);
 
 return [r.toString(),s.toString()];


var validateSignature = function(hashedMessage, signature)
 hashedMessage = bigInt(hashedMessage,16);
 var r = bigInt(signature[0]);
 var s = bigInt(signature[1]);
 var w = s.modInv(n);
 var u1 = bigInt(hashedMessage.multiply(w)).mod(n);
 var u2 = bigInt(r.multiply(w)).mod(n);
 var u1g = u1.multiply(g);
 var u2pu = u2.multiply(publicKey);
 var xCoord =u1g.add(u2pu);
 var v = xCoord.mod(n); 
 if(v.equals(r))
 return true;
 return false;

However it still fails to validate the signature. Hope it makes it a bit clearer.

part of your problem is that g is actually not a number but a point

this is a rough translation of what you wrote:

g = 55066263022277343669578718895168534326250603453777594175500187360389116729240
privateKey = 90436540941140970165633788406609967146985661161263948799654498545867952662296
k = <random number>
r = k*g%p%n
e = sha(m)

ki = k^-1%n
pr = privateKey*r
ki*e
s = ki%n

i wrote an implmentation of this however over the last few weeks something like this:

g = 
 x: 55066263022277343669578718895168534326250603453777594175500187360389116729240,
 y: 32670510020758816978083085130507043184471273380659243275938904335757337482424

k = <random number>
r = <random number>
e = sha(m)

privateKey = 90436540941140970165633788406609967146985661161263948799654498545867952662296
r = g * k
s = ((privateKey * r.x + e) * (k^-1%n)) % n
r = r.x

it might help you to understand how the point multiplication works check out these links:
https://github.com/Azero123/simple-js-ec-math

https://www.npmjs.com/package/simple-js-ec-math

https://eng.paxos.com/blockchain-101-foundational-math

also perhaps take a look at my simple-js-ecdsa implementation as well

just another note, you likely should not use sha1 as it is consider "officially insecure" and there are formulas for collisions using it. perhaps try sha2 or sha3