Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
python implementation of ecdsa calculations, demonstrating how to recover a private key from two signatures with identical 'r', and demonstrating how to find the public key from a signature and message, or from two signatures.
from __future__ import print_function, division
By Willem Hengeveld <>
ecdsa implementation in python
demonstrating several 'unconventional' calculations,
like finding a public key from a signature,
and finding a private key from 2 signatures with identical 'r'
# (gcd,c,d) = GCD(a, b) ===> a*c+b*d==gcd
def GCD(a, b):
prevx, x = 1, 0
prevy, y = 0, 1
while b:
q = a//b
x, prevx = prevx - q*x, x
y, prevy = prevy - q*y, y
a, b = b, a%b
return a, prevx, prevy
def modinv(x, m):
(gcd, c, d) = GCD(x,m)
return c
def samefield(a,b):
determine if a uses the same field
if a.field!=b.field:
raise Exception("field mismatch")
return True
class FiniteField:
FiniteField implements a value modulus a number.
class Value:
represent a value in the FiniteField
this class forwards all operations to the FiniteField class
def __init__(self, field, value):
self.field = field
self.value = int(value)
# Value * int
def __add__(self, rhs): return self.field.add(self, self.field.value(rhs))
def __sub__(self, rhs): return self.field.sub(self, self.field.value(rhs))
def __mul__(self, rhs): return self.field.mul(self, self.field.value(rhs))
def __div__(self, rhs): return self.field.div(self, self.field.value(rhs))
def __truediv__(self, rhs): return self.__div__(rhs)
def __floordiv__(self, rhs): return self.__div__(rhs)
def __pow__(self, rhs): return self.field.pow(self, rhs)
# int * Value
def __radd__(self, lhs): return self.field.add(self.field.value(lhs), self)
def __rsub__(self, lhs): return self.field.sub(self.field.value(lhs), self)
def __rmul__(self, lhs): return self.field.mul(self.field.value(lhs), self)
def __rdiv__(self, lhs): return self.field.div(self.field.value(lhs), self)
def __rtruediv__(self, lhs): return self.__rdiv__(lhs)
def __rfloordiv__(self, lhs): return self.__rdiv__(lhs)
def __rpow__(self, lhs): return self.field.pow(self.field.value(lhs), self)
def __eq__(self, rhs): return self.field.eq(self, self.field.value(rhs))
def __ne__(self, rhs): return not (self==rhs)
def __str__(self): return "0x%x" % self.value
def __neg__(self): return self.field.neg(self)
def sqrt(self, flag): return self.field.sqrt(self, flag)
def inverse(self): return self.field.inverse(self)
def __nonzero__(self): return self.field.nonzero(self)
def __bool__(self): return self.__nonzero__() != 0
def __int__(self): return self.field.intvalue(self)
def __init__(self, p):
self.p = p
several basic operators
def add(self, lhs, rhs): return samefield(lhs, rhs) and self.value((lhs.value + rhs.value) % self.p)
def sub(self, lhs, rhs): return samefield(lhs, rhs) and self.value((lhs.value - rhs.value) % self.p)
def mul(self, lhs, rhs): return samefield(lhs, rhs) and self.value((lhs.value * rhs.value) % self.p)
def div(self, lhs, rhs): return samefield(lhs, rhs) and self.value((lhs.value * rhs.inverse()) % self.p)
def pow(self, lhs, rhs): return self.value(pow(lhs.value, int(rhs), self.p))
def eq(self, lhs, rhs): return (lhs.value-rhs.value) % self.p == 0
def neg(self, val): return self.value(self.p-val.value)
def sqrt(self, val, flag):
calculate the square root modulus p
if not val:
return val
sw = self.p % 8
if sw==3 or sw==7:
res = val**((self.p+1)//4)
elif sw==5:
x = val**((self.p+1)//4)
if x==1:
res = val**((self.p+3)//8)
res = (4*val)**((self.p-5)//8)*2*val
raise Exception("modsqrt non supported for (p%8)==1")
if res.value%2==flag:
return res
return -res
def inverse(self, value):
calculate the multiplicative inverse
return modinv(value.value, self.p)
def nonzero(self, x):
return 1 if not (x.value % self.p)==0 else 0
def value(self, x):
converts an integer or FinitField.Value to a value of this FiniteField.
return x if isinstance(x, FiniteField.Value) and x.field==self else FiniteField.Value(self, x)
def zero(self):
returns the additive identity value
meaning: a + 0 = a
return FiniteField.Value(self, 0)
def one(self):
returns the multiplicative identity value
meaning a * 1 = a
return FiniteField.Value(self, 1)
def intvalue(self, x):
return x.value % self.p
class EllipticCurve:
EllipticCurve implements a point on a elliptic curve
class Point:
represent a value in the EllipticCurve
this class forwards all operations to the EllipticCurve class
def __init__(self, curve, x, y):
self.curve = curve
self.x = x
self.y = y
# Point + Point
def __add__(self, rhs): return self.curve.add(self, rhs)
def __sub__(self, rhs): return self.curve.sub(self, rhs)
# Point * int or Point * Value
def __mul__(self, rhs): return self.curve.mul(self, rhs)
def __div__(self, rhs): return self.curve.div(self, rhs)
def __truediv__(self, rhs): return self.__div__(rhs)
def __floordiv__(self, rhs): return self.__div__(rhs)
def __eq__(self, rhs): return self.curve.eq(self, rhs)
def __ne__(self, rhs): return not (self==rhs)
def __str__(self): return "(%s,%s)" % (self.x, self.y)
def __neg__(self): return self.curve.neg(self)
def __nonzero__(self): return self.curve.nonzero(self)
def __bool__(self): return self.__nonzero__() != 0
def isoncurve(self):
return self.curve.isoncurve(self)
def __init__(self, field, a, b):
self.field = field
self.a = field.value(a)
self.b = field.value(b)
def add(self, p, q):
perform elliptic curve addition
if not p: return q
if not q: return p
# calculate the slope of the intersection line
if p==q:
if p.y==0:
l = (3* p.x**2 + self.a) // (2* p.y)
elif p.x==q.x:
l = (p.y-q.y)//(p.x-q.x)
# calculate the intersection point
x = l**2 - ( p.x + q.x )
y = l*(p.x-x)-p.y
return self.point(x,y)
# subtraction is : a - b = a + -b
def sub(self, lhs, rhs): return lhs + -rhs
# scalar multiplication is implemented like repeated addition
def mul(self, pt, scalar):
scalar = int(scalar)
accumulator =
shifter = pt
while scalar != 0:
bit = scalar % 2
if bit:
accumulator += shifter
shifter += shifter
scalar //= 2
return accumulator
def div(self, pt, scalar):
scalar division: P / a = P * (1/a)
scalar is assumed to be of type FiniteField(grouporder)
return pt * (1//scalar)
def eq(self, lhs, rhs): return lhs.x==rhs.x and lhs.y==rhs.y
def neg(self, pt):
return self.point(pt.x, -pt.y)
def nonzero(self, pt):
return 1 if pt.x or pt.y else 0
def zero(self):
Return the additive identity point ( aka '0' )
P + 0 = P
return self.point(,
def point(self, x, y):
construct a point from 2 values
return EllipticCurve.Point(self, self.field.value(x), self.field.value(y))
def isoncurve(self, p):
verifies if a point is on the curve
return not p or (p.y**2 == p.x**3 + self.a*p.x + self.b)
def decompress(self, x, flag):
calculate the y coordinate given only the x value.
there are 2 possible solutions, use 'flag' to select.
x = self.field.value(x)
ysquare = x**3 + self.a*x+self.b
return self.point(x, ysquare.sqrt(flag))
class ECDSA:
Digital Signature Algorithm using Elliptic Curves
def __init__(self, ec, G, n): = ec
self.G = G
self.GFn = FiniteField(n)
def calcpub(self, privkey):
calculate the public key for private key x
return G*x
return self.G * self.GFn.value(privkey)
def sign(self, message, privkey, secret):
sign the message using private key and sign secret
for signsecret k, message m, privatekey x
return (G*k, (m+x*r)/k)
m = self.GFn.value(message)
x = self.GFn.value(privkey)
k = self.GFn.value(secret)
R = self.G * k
r = self.GFn.value(R.x)
s = (m + x*r) // k
return (r, s)
def verify(self, message, pubkey, rnum, snum):
Verify the signature
for message m, pubkey Y, signature (r,s)
r = xcoord(R)
verify that : G*m+Y*r=R*s
this is true because: { Y=G*x, and R=G*k, s=(m+x*r)/k }
G*m+G*x*r = G*k*(m+x*r)/k ->
G*(m+x*r) = G*(m+x*r)
several ways to do the verification:
r == xcoord[ G*(m/s) + Y*(r/s) ] <<< the standard way
R * s == G*m + Y*r
r == xcoord[ (G*m + Y*r)/s) ]
m = self.GFn.value(message)
r = self.GFn.value(rnum)
s = self.GFn.value(snum)
R = self.G * (m//s) + pubkey * (r//s)
# alternative methods of verifying
#RORG =, 0)
#RR = self.G * m + pubkey * r
#print("#1: %s .. %s" % (RR, RORG*s))
#print("#2: %s .. %s" % (RR*(1//s), r))
#print("#3: %s .. %s" % (R, r))
return R.x == r
def findpk(self, message, rnum, snum, flag):
find pubkey Y from message m, signature (r,s)
Y = (R*s-G*m)/r
note that there are 2 pubkeys related to a signature
m = self.GFn.value(message)
r = self.GFn.value(rnum)
s = self.GFn.value(snum)
R =, flag)
#return (R*s - self.G * m)*(1//r)
return R*(s//r) - self.G * (m//r)
def findpk2(self, r1, s1, r2, s2, flag1, flag2):
find pubkey Y from 2 different signature on the same message
sigs: (r1,s1) and (r2,s2)
returns (R1*s1-R2*s2)/(r1-r2)
R1 =, flag1)
R2 =, flag2)
rdiff = self.GFn.value(r1-r2)
return (R1*s1-R2*s2)*(1//rdiff)
def crack2(self, r, s1, s2, m1, m2):
find signsecret and privkey from duplicate 'r'
signature (r,s1) for message m1
and signature (r,s2) for message m2
s1 = (m1 + x*r)/k
s2 = (m2 + x*r)/k
subtract -> (s1-s2) = (m1-m2)/k -> k = (m1-m2)/(s1-s2)
-> privkey = (s1*k-m1)/r .. or (s2*k-m2)/r
sdelta = self.GFn.value(s1-s2)
mdelta = self.GFn.value(m1-m2)
secret = mdelta // sdelta
x1 = self.crack1(r, s1, m1, secret)
x2 = self.crack1(r, s2, m2, secret)
if x1 != x2:
print("x1=%s" % x1)
print("x2=%s" % x2)
return (secret, x1)
def crack1(self, rnum, snum, message, signsecret):
find privkey, given signsecret k, message m, signature (r,s)
x = (s*k-m)/r
m = self.GFn.value(message)
r = self.GFn.value(rnum)
s = self.GFn.value(snum)
k = self.GFn.value(signsecret)
return (s*k-m)//r
def secp256k1():
create the secp256k1 curve
GFp = FiniteField(2**256 - 2**32 - 977)
ec = EllipticCurve(GFp, 0, 7)
generator = ec.point( 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 )
grouporder = 2**256 - 432420386565659656852420866394968145599
return ECDSA(ec, generator, grouporder)
def verifytest(calced, expected, descr):
verifytest is used to verify test results
if type(calced)!=type(expected):
if type(expected)==str:
calced = "%s" % calced
if calced!=expected:
print("ERROR in %s: got %s, expected %s" % (descr, calced, expected))
def test_gfp():
gfp = FiniteField(37)
verifytest(gfp.value(2)**16, "0x9", "<2>^16")
verifytest(2**gfp.value(16), "0x9", "2^<16>")
verifytest(gfp.value(1)//4, "0x1c", "<1>/4")
verifytest(1//gfp.value(4), "0x1c", "1/<4>")
verifytest(gfp.value(1)==38, "True", "<1>==38")
verifytest(1==gfp.value(38), "True", "1==<38>")
verifytest(gfp.value(1)!=38, "False", "<1>!=38")
verifytest(gfp.value(16)*16, "0x22", "<16>*16")
verifytest(16*gfp.value(16), "0x22", "16*<16>")
def test_ec():
GFp = FiniteField(2**256 - 2**32 - 977)
GFn = FiniteField(2**256 - 432420386565659656852420866394968145599)
ec = EllipticCurve(GFp, 0, 7)
G = ec.point( 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 )
verifytest(G.isoncurve(), True, "oncurve")
a = 901283019823
b = 100980987879
P = G*a
Q = G*b
verifytest(G*a+G*b, G*(a+b), "p(a+b)=pa+pb")
verifytest((P+Q)*a, P*a+Q*a, "(p+q)a=pa+qa")
verifytest(P//GFn.value(a), G, "P/a")
def test_dsa():
dsa = secp256k1()
priv = 0x1234
pubkey = dsa.calcpub(priv)
signsecret1 = 0x1111
signsecret2 = 0x2222
msg1 = 0x1234123412341234123412341234123412341234123412341234123412341234
(r1,s1) = dsa.sign(msg1, priv, signsecret1)
check1 = dsa.verify(msg1, pubkey, r1, s1)
verifytest(pubkey, "(0x37a4aef1f8423ca076e4b7d99a8cabff40ddb8231f2a9f01081f15d7fa65c1ba,0xb96ced90a1b8f9b43a18fc900ff55af2be0e94b90a434fca5b9e226b835024cd)", "pubkey")
verifytest(priv, dsa.crack1(r1, s1, msg1, signsecret1), "crack1")
verifytest(r1, "0x7592aab5d43618dda13fba71e3993cd7517a712d3da49664c06ee1bd3d1f70af", "r1")
verifytest(s1, "0x8e578a508331374bcbb1618ea3a8c9c63d49e9d42e0ed605b8c74910cfa50c11", "s1")
verifytest(check1, True, "verify1")
msg2 = 0x1111111111111111111111111111111111111111111111111111111111111111
(r2,s2) = dsa.sign(msg2, priv, signsecret1)
check2 = dsa.verify(msg2, pubkey, r2, s2)
verifytest(r2, "0x7592aab5d43618dda13fba71e3993cd7517a712d3da49664c06ee1bd3d1f70af", "r2")
verifytest(s2, "0x351a200607d9aae72e3fb30fe41cf92dcd0b22117f57123df005974290d9429b", "s2")
verifytest(check2, True, "verify2")
verifytest(r1, r2, "rvalues")
(crackedsecret, crackedprivkey) = dsa.crack2(r1, s1, s2, msg1, msg2)
verifytest(crackedsecret, signsecret1, "crackedsecret")
verifytest(crackedprivkey, "0x%x" % priv, "crackedpriv")
Note that we can find public keys, which can validate a signature, but did not sign it!
for flag in range(2):
pk1 = dsa.findpk(msg1, r1, s1, flag)
check1 = dsa.verify(msg1, pk1, r1, s1)
print("%d -> %s pk1=%s" % (flag, check1, pk1))
pk2 = dsa.findpk(msg2, r2, s2, flag)
check2 = dsa.verify(msg2, pk2, r2, s2)
print("%d -> %s pk2=%s" % (flag, check2, pk2))
only one of these 4 verifies our msg correctly
(r3,s3) = dsa.sign(msg1, priv, signsecret2)
for flag1 in range(2):
for flag2 in range(2):
pk = dsa.findpk2(r1,s1,r3,s3,flag1,flag2)
check1 = dsa.verify(msg1, pk, r1,s1)
check3 = dsa.verify(msg1, pk, r3,s3)
print("%d,%d : %s %s -> %s" % (flag1, flag2, check1, check3, pk))
def test_crack():
Demonstrate cracking an actual bitcoin key, see
pk=(0xdbd0c61532279cf72981c3584fc32216e0127699635c2789f549e0730c059b81, 0xae133016a69c21e23f1859a95f06d52b7bf149a8f2fe4e8535c8a829b449c5ff)
# k:0x7a1a7e52797fc8caaa435d2a4dace39158504bf204fbe19f14dbb427faee50ae
# x:0xc477f9f65c22cce20657faa5b2d1d8122336f851a508a1ed04e479c34985bf96
E = secp256k1()
k, x = E.crack2(r, s1, s2, m1, m2)
print("k = %s" % k)
print("x = %s" % x)
def main():
if __name__ == '__main__':
Copy link

nikos-glikis commented Sep 22, 2014


Does this work ok ? I see that the checks fail, I also try to use it with my inputs, to recover the private key and it fails, I get something completely different.

Is this finished ?


Copy link

nlitsme commented Oct 1, 2014

Sorry, there was a bug in my addition algorithm. now it works.

This is the expected output:

0 -> True pk1=(0x37a4aef1f8423ca076e4b7d99a8cabff40ddb8231f2a9f01081f15d7fa65c1ba,0xb96ced90a1b8f9b43a18fc900ff55af2be0e94b90a434fca5b9e226b835024cd)
0 -> True pk2=(0x37a4aef1f8423ca076e4b7d99a8cabff40ddb8231f2a9f01081f15d7fa65c1ba,0xb96ced90a1b8f9b43a18fc900ff55af2be0e94b90a434fca5b9e226b835024cd)
1 -> True pk1=(0x801a2d71fcbf555b34c2ef3544b66b8bac22aee354556e6d5871150cd2c13544,0x587113fa995e2c1e64c2c1c21613b2e75243cc10426541511af75baab5336fd)
1 -> True pk2=(0x95d6c559869bdf7397cab3fc11375e8d4d0b3ee79de3f6889e89e34ffa3ac73e,0x4dbd71f7dd41db42350cafc6a592ada7480f1aed6ed5fd2811f4cda1b617111b)
0,0 : True True -> (0x37a4aef1f8423ca076e4b7d99a8cabff40ddb8231f2a9f01081f15d7fa65c1ba,0xb96ced90a1b8f9b43a18fc900ff55af2be0e94b90a434fca5b9e226b835024cd)
0,1 : False False -> (0xe18efe92f62073d0b32d57364093d98a432258d828c7c646770ecd5a09d6e103,0xf46caaf6e768e82cdb62507c0060787f0105b0a277ff889ec423a814ad107856)
1,0 : False False -> (0xe18efe92f62073d0b32d57364093d98a432258d828c7c646770ecd5a09d6e103,0xb935509189717d3249daf83ff9f8780fefa4f5d880077613bdc57ea52ef83d9)
1,1 : False False -> (0x37a4aef1f8423ca076e4b7d99a8cabff40ddb8231f2a9f01081f15d7fa65c1ba,0x4693126f5e47064bc5e7036ff00aa50d41f16b46f5bcb035a461dd937cafd762)

Copy link

tor888 commented Dec 28, 2014

It be work if my wallet encrypted and do not have output transactions?

Copy link

PRINCEHR commented Nov 25, 2019


Copy link

nlitsme commented Jan 11, 2021

I added a description of how to get the m1 and m2 values here:

Copy link

nlitsme commented Jan 11, 2021

And update the script to work with python3

Copy link

nlitsme commented Jan 11, 2021

corrected an incorrect 'gcd' implementation, now the script works with the real world example from

Copy link

nlitsme commented Jan 11, 2021

And the latest update: using bool and int operators to get a bit more readable code.

Copy link

nlitsme commented Mar 3, 2021

I made a new repository: doing the above, and more in javascript.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment