The following method searches for the private key used to sign a message with ECDSA. In this case we will generate two signatures, and then search for a private key. We will use the Lenstra–Lenstra–Lovász (LLL) method [paper] to crack the signature, and discover the private key used to sign the message.
ECDSA Crack using the Lenstra–Lenstra–Lovász (LLL) method |
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))\)
Coding
The coding based on [here] is:
import ecdsa import random import libnum import olll import hashlib import sys # https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/ G = ecdsa.NIST256p.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, pow(2,127)) k2 = random.randrange(1, pow(2,127)) msg1="Hello" msg2="Hello1" if (len(sys.argv)>1): msg1=(sys.argv[1]) if (len(sys.argv)>2): msg2=(sys.argv[2]) m1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16) m2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16) sig1 = Private_key.sign(m1, k1) sig2 = Private_key.sign(m2, k2) print ("\nMessage 1: ",msg1) print ("Message 2: ",msg2) print ("\nSig 1 r,s: ",sig1.r,sig1.s) print ("Sig 2 r,s: ",sig2.r,sig2.s) print ("\nk1: ",k1) print ("k2: ",k2) print ("Private key: ",priv) r1 = sig1.r s1_inv = libnum.invmod(sig1.s, order) r2 = sig2.r s2_inv = libnum.invmod(sig2.s, order) matrix = [[order, 0, 0, 0], [0, order, 0, 0], [r1*s1_inv, r2*s2_inv, (2**128) / order, 0], [m1*s1_inv, m2*s2_inv, 0, 2**128]] search_matrix = olll.reduction(matrix, 0.75) r1_inv = libnum.invmod(sig1.r, order) s1 = sig1.s for search_row in search_matrix: possible_k1 = search_row[0] try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key: print("\nThe private key has been found") print (try_private_key)
and code:
A sample run is:
Message 1: Hello Message 2: Hello1 Sig 1 r,s: 30864529403980946883075235082904731041525109106740550947442160626254097588726 22314838080500051638120122964157475982072760913585940854067991599846585285529 Sig 2 r,s: 25221150358322710448081674595307879895410147198806043505276947472521322819170 45601609211316335823522363774421170181270780079376184843815922382136427333457 k1: 130448706624946621843047105000705274127 k2: 151282695311633118004443620495519979855 Private key: 108415414175122594317778300263942938950777164532096484959120107468611561184303 The private key has been found 108415414175122594317778300263942938950777164532096484959120107468611561184303