Cracking ECDSA With a Leak of the Random Nonce

You must look after your private key. It is the thing that identifies your systems, your users, and, in fact, your company. A breach of…
Bill’s Crypto Notes

Recovering The Private Key in a ECDSA Signature Using A Single Random Nonce

You must look after your private key. It is the thing that identifies your systems, your users, and, in fact, your company. A breach of your private key can be one of the most costly things that a company can face in terms of a trust breach. And so, we are moving towards a world where we sign our transactions with your private key, and then prove them with our public key. This happens every time that a Bitcoin transaction happens, and where Bob signs a transfer to Bitcoins to Alice with his private key, and then everyone can prove it was Bob with his public key.

So my most often question that I am asked … “Can I crack the private key from the public key”? Well, the answer is always, “No”, unless there’s a weakness in the implementation. So, let’s look at an example.

The ECDSA signature method is the elliptic curve equivalent of the DSA method and is used extensively with Bitcoin methods. With this, we create a private key (priv) and then generate a public key, which is:

and where G is the base point on the elliptic curve, and where we add this point priv times (G+G+G … +G) to produce the public key. For the

Next, we create a random number (k) and produce the signature of:

The signature is then (r,s) and H(M) is the SHA-256 hash of the message (M), and converted into an integer value. The power of -1 is the inverse mod function.

But here is the problem … if the k value (the random value for each signature) is revealed for any of the signatures, an intruder can easily determine the private key using:

So here is a simple method of discovering the private key if the nonce (k) is revealed [here]:

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"
m = int(hashlib.sha256(msg.encode()).hexdigest(),base=16)
sig = Private_key.sign(m, k)
print ("Message: ",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:

Message 1:  HelloSig 1 r,s:  593959768481326541017764525105541307651350152825
24998402057489206301918547935 931000371115270625518254295970
46160404924326745421521936938198144828943875847

Found Key:  771513454648029815308255639593188551081446734040
10555471286970674632014063904

Key:  771513454648029815308255639593188551081446734040105554
71286970674632014063904

The private key has been found
771513454648029815308255639593188551081446734040105554712869
70674632014063904

The code is here:

Conclusions

Don’t store your nonce. Every time you sign something, there’s a risk of a leak of the nonce, so watch out!