ECDSA: Revealing the private key, if nonce known (with NIST521p)[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 NIST521p [Try P-256][Try SECP256k1].
|
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.NIST521p.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=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, a=-3, b=1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984, h=1) Order: 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449 Gx: 2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846 Gy: 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784 Message 1: hello Sig 1 r,s: 3036358966884452640684242789151199853678170220249490787662473188173658214767291245779013808800732317244715901146641968975589456736672383449015240184527988122 2900735082899424915700512122975006896687099995336210275172106821507247016435893851627819794036617824674896029029669780593172634691257863107900690379576331312 Found Key: 6788071626213484131120274888414596877307544851534923414987673224430341913485379612345157814282563987594405037669355320465887882552556060765281655069971738444 Key: 6788071626213484131120274888414596877307544851534923414987673224430341913485379612345157814282563987594405037669355320465887882552556060765281655069971738444 The private key has been found 6788071626213484131120274888414596877307544851534923414987673224430341913485379612345157814282563987594405037669355320465887882552556060765281655069971738444
Presentation
Quick Doodle
And here is a quick doodle: