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 (NIST256p)[Try SECP256k1][Try P-512p]:
ECDSA: Revealing the private key, if nonce known (NIST256p) |
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:
# Bill Buchanan # Code here: https://asecuritysite.com/encryption/ecd2 import ecdsa import random import libnum import hashlib import sys G = ecdsa.NIST256p.generator order = G.order() priv = random.randrange(1,order) Public_key = ecdsa.ecdsa.Public_key(G, G * priv) Private_key = ecdsa.ecdsa.Private_key(Public_key, priv) k = random.randrange(1, pow(2,127)) msg="Hello" if (len(sys.argv)>1): msg=(sys.argv[1]) m = int(hashlib.sha256(msg.encode()).hexdigest(),base=16) sig = Private_key.sign(m, k) print ("Message 1: ",msg) print ("Sig 1 r,s: ",sig.r,sig.s) r_inv = libnum.invmod(sig.r, order) s = sig.s try_private_key = (r_inv * ((k * s) - m)) % order print ("\nKey: ",priv) print ("\nFound Key: ",try_private_key) 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=115792089210356248762697446949407573530086143415290314195533631308867097853951, a=-3, b=41058363725152142129326129780047268409114441015993725554835256314039467401291, h=1) Order: 115792089210356248762697446949407573529996955224135760342422259061068512044369 Gx: 48439561293906451759052585252797914202762949526041747995844080717082404635286 Gy: 36134250956749795798585127919587881956611106672985015071877198253568414405109 Message 1: hello Sig 1 r,s: 1170312626394593925973620872602628938397551345821443157871662902653118148247 98920306919086669850676149319737373388275973461744811504858576128073568088944 Found Key: 55219887114802052325574040582890243487194088440633646676360451595484919438404 Key: 55219887114802052325574040582890243487194088440633646676360451595484919438404 The private key has been found 55219887114802052325574040582890243487194088440633646676360451595484919438404
Presentation
Quick Doodle
And here is a quick doodle: