ECDSA: Revealing the private key, if nonce known (with SECP256k1)[ECDSA Home][Home]
With an ECDSA signature, we sign a message with a private key (\(priv\)) and prove the signature with the public key (\(pub\)). A random value (a nonce) is then used to randomize the signature. Each time we sign, we create a random nonce value and it will produce a different (but verifiable) signature. Overall the signer only has to reveal the elements of the signature and their public key, and not the nonce value. If the signer reveals just one nonce value by mistake, an intruder can discover the private key. In this case we will reveal the nonce value, and determine the private key. In this case we will use the BitCoin curve (SECP256k1) [Try P-256][Try P-512].
|
Theory
In ECDSA, Bob create a random private key (\(priv\)), and then a public key from:
\(pub= priv \times G\)
Next, in order to create a signature for a message of \(M\), he creates a random number (\(k\)) and generates the signature of:
\(r = k \cdot G\)
\(s = k^{-1} (H(M) + r \cdot priv)\)
The signature is then \((r,s)\) and where \(r\) is the x-co-ordinate of the point \(kG\). \(H(M)\) is the SHA-256 hash of the message (\(M\)), and converted into an integer value. If the \(k\) value is revealed for any of the signatures, an intruder can determine the private key using:
\(priv= r^{-1} \times ((k \cdot s) - H(M))\)
This works because:
\(s \cdot k = H(M) + r \cdot priv\)
and so:
\(r \cdot priv = s \cdot k - H(M)\)
and for \(priv\):
\(priv = r^{-1} (s \cdot k - H(M))\)
Here is some code which does a discovery of the private key, if the nonce (\(k\)) is revealed:
import ecdsa import random import libnum import hashlib import sys G = ecdsa.SECP256k1.generator order = G.order() print ("Curve detail") print (G.curve()) print ("Order:",order) print ("Gx:",G.x()) print ("Gy:",G.y()) priv = random.randrange(1,order) Public_key = ecdsa.ecdsa.Public_key(G, G * priv) Private_key = ecdsa.ecdsa.Private_key(Public_key, priv) k1 = random.randrange(1, 2**127) msg1="Hello" if (len(sys.argv)>1): msg1=(sys.argv[1]) m1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16) sig1 = Private_key.sign(m1, k1) print ("\nMessage 1: ",msg1) print ("Sig 1 r,s: ",sig1.r,sig1.s) r1_inv = libnum.invmod(sig1.r, order) s1 = sig1.s try_private_key = (r1_inv * ((k1 * s1) - m1)) % order print () print ("Found Key: ",try_private_key) print () print ("Key: ",priv) if (ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key): print("\nThe private key has been found") print (try_private_key)
A sample run is:
Curve detail CurveFp(p=115792089237316195423570985008687907853269984665640564039457584007908834671663, a=0, b=7, h=1) Order: 115792089237316195423570985008687907852837564279074904382605163141518161494337 Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240 Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424 Message 1: hello Sig 1 r,s: 31110256322898237264490243973699731757547476866639597679936653478826981616940 39826373609221276498318363598911660764943881869513002749160966300292770474312 Found Key: 95525957745036960168874600860927089941985475618074755510253043724286299804190 Key: 95525957745036960168874600860927089941985475618074755510253043724286299804190 The private key has been found 95525957745036960168874600860927089941985475618074755510253043724286299804190
Presentation
Quick Doodle
And here is a quick doodle: