#!/usr/bin/python
# by 57fe (fe57.org/forum/thread.php?board=4&thema=1#1)
#######################
# print() compatibility python 2/3
from __future__ import print_function
#######################
# settings
pow2pubkey = 32 # bits/order/pow2/exp key
pow2kangaroo = 3 # discriminator
Ntimeit = 10 # times for avg runtime
prngseed = 0 # 0,any
flag_debug = 0 # 0,1,2,3
#######################
# low order pubkeys
pubkeys = {
16: ('029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a', 0xc936)
, 24: ('036ea839d22847ee1dce3bfc5b11f6cf785b0682db58c35b63d1342eb221c3490c', 0xdc2a04)
, 32: ('0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69', 0xb862a62e)
, 33: ('02ed949eaca31df5e8be9bf46adc1dfae1734b8900dcc303606831372955c728da', False) #0x01abcd1234
, 40: ('03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4', 0xe9ae4933d6)
, 45: ('026ecabd2d22fdb737be21975ce9a694e108eb94f3649c586cc7461c8abf5da71a', 0x122fca143c05)
, 50: ('03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6', 0x022bd43c2e9354)
, 65: ('0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b', 0x01a838b13505b26867)
,105: ('03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b', False)
}
#######################
# import
import os
import sys
import time
import random
try:
# https://www.lfd.uci.edu/~gohlke/pythonlibs/
import gmpy2
except:
flag_gmpy2 = False
print("[warn] gmpy2 not found. raw python is slow!")
else:
flag_gmpy2 = True
try:
from coincurve import PrivateKey, PublicKey
from coincurve.utils import int_to_bytes, hex_to_bytes, bytes_to_int, bytes_to_hex, int_to_bytes_padded
except:
flag_coincurve = False
#print("[warn] coincurve not found. random pubkey not available!")
else:
flag_coincurve = True
if 0:
from multiprocessing import Pool
from multiprocessing import cpu_count
from multiprocessing import freeze_support
#######################
# python 2,3
#import sys
#import time
if sys.version_info[0] == 2:
from time import clock
else:
from time import perf_counter
from time import process_time
clock = time.perf_counter
xrange=range
raw_input=input
#######################
# secp256k1
#modulo = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1
modulo = 115792089237316195423570985008687907853269984665640564039457584007908834671663
order = 115792089237316195423570985008687907852837564279074904382605163141518161494337
#modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
#order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
#Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
#Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
class Point:
def __init__(self, x=0, y=0):
self.x = x
self.y = y
Gp = Point(Gx,Gy)
Zp = Point(0,0) # zero-point, infinite in real x,y - plane
#######################
# functions
# return (g, x, y) a*x + b*y = gcd(x, y)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def rev(b, n=modulo):
while b < 0:
b += n
g, x, _ = egcd(b, n)
if g == 1:
return x % n
def mul2(P, p=modulo):
R = Point()
if flag_gmpy2:
c = 3 * P.x * P.x * gmpy2.invert(2*P.y, p) % p
else:
c = 3 * P.x * P.x * rev(2*P.y, p) % p
R.x = (c*c - 2*P.x) % p
R.y = (c*(P.x - R.x) - P.y) % p
return R
# 1I, 3M
def add(P, Q, p=modulo):
R = Point()
dx = Q.x - P.x
dy = Q.y - P.y
if flag_gmpy2: # 1I, 1M
c = dy * gmpy2.invert(dx, p) % p
else:
c = dy * rev(dx, p) % p
R.x = (c*c - P.x - Q.x) % p # 1M
R.y = (c*(P.x - R.x) - P.y) % p # 1M
return R
def mulk(k, P=Gp, p=modulo):
if k == 0: return Zp
elif k == 1: return P
elif (k % 2 == 0):
return mulk(k/2, mul2(P, p), p)
else:
return add(P, mulk( (k-1)/2, mul2(P, p), p), p)
def newX2Y(X, y_parity):
p = modulo
Y = 3
tmp = 1
while Y:
if Y & 1:
tmp = tmp*X % p
Y >>= 1
X = X*X % p
X = (tmp+7) % p
Y = (p+1)//4
tmp = 1
while Y:
if Y & 1:
tmp = tmp*X % p
Y >>= 1
X = X*X % p
Y = tmp
if Y%2 != y_parity:
Y = -Y % p
return Y
def KANGAROO():
DP_rarity = 1 << ((pow2pubkey - 2*pow2kangaroo)//2 - 2)
if flag_debug > 0:
print("[DP_rarity] 1<<((pow2pub - 2*pow2k) -2) = 1<<((%s-2*%s)//2 -2) = %s" % (pow2pubkey,pow2kangaroo,DP_rarity))
jump_modulo = ((pow2pubkey-1) // 2) + pow2kangaroo
if flag_debug > 0:
print("[jump_modulo] (pow2pub-1)//2 + pow2k = (%s-1)//2 + %s = %s" % (pow2pubkey,pow2kangaroo,jump_modulo))
T, t, dt = [], [], []
W, w, dw = [], [], []
if flag_debug > 0:
print( '[t] 3<<(pow2pub-2) + rng(1,(1<<(pow2pub-1))) = 3<<(%s-2) + rng(1,(1<<(%s-1))) = %s + %s' %
( pow2pubkey, pow2pubkey
,3<<(pow2pubkey-2), random.randint(1, (1<<(pow2pubkey-1)))
)
)
for k in range(Nt):
t.append((3 << (pow2pubkey - 2)) + random.randint(1, (1 << (pow2pubkey - 1))))#-(1 << (pow2pubkey - 2)) )
T.append(mulk(t[k]))
dt.append(0)
for k in range(Nw):
w.append(random.randint(1, (1 << (pow2pubkey - 1))))
W.append(add(W0,mulk(w[k])))
dw.append(0)
print('[+] T+W ready')
n_jump = last_jump = 0
prvkey = False;
A, Ak, B, Bk = [], [], [], []
t0 = t1 = t2 = time.time()
while (1):
if flag_debug > 2: print('[new_loop] %s jumps'%n_jump)
for k in range(Nt):
if flag_debug > 2: print('[k/Nt] %s/%s'%(k+1,Nt))
n_jump += 1
pw = T[k].x % jump_modulo
pw = int(pw)
dt[k] = 1 << pw
if T[k].x % (DP_rarity) == 0:
A.append(T[k].x)
Ak.append(t[k])
if flag_debug > 1:
print('[tame] A=%s, B=%s'%(len(A),len(B)))
if flag_debug > 0:
save2file('tame.txt', 'a', '%064x %s\n'%(T[k].x,t[k]) )
result = list(set(A) & set(B))
if len(result) > 0:
sol_kt = A.index(result[0])
sol_kw = B.index(result[0])
prvkey = Ak[sol_kt] - Bk[sol_kw]
if prvkey: break
t[k] += dt[k]
T[k] = add(P[pw], T[k])
if prvkey: break
for k in range(Nw):
if flag_debug > 2: print('[k/Nw] %s/%s'%(k+1,Nw))
n_jump += 1
pw = W[k].x % jump_modulo
pw = int(pw)
dw[k] = 1 << pw
if W[k].x % (DP_rarity) == 0:
B.append(W[k].x)
Bk.append(w[k])
if flag_debug > 1:
print('[wild] A=%s, B=%s'%(len(A),len(B)))
if flag_debug > 0:
save2file('wild.txt', 'a', '%064x %s\n'%(W[k].x,w[k]) )
result = list(set(A) & set(B))
if len(result) > 0:
sol_kt = A.index(result[0])
sol_kw = B.index(result[0])
prvkey = Ak[sol_kt] - Bk[sol_kw]
if prvkey: break
w[k] += dw[k]
W[k] = add(P[pw], W[k])
if prvkey: break
t2 = time.time()
if (t2-t1) > 1:
if sys.version_info[0] == 2:
print('\r[~] %.1f j/s'%((n_jump-last_jump)/(t2-t1)), end='')
sys.stdout.flush()
else:
print('\r[~] %.1f j/s'%((n_jump-last_jump)/(t2-t1)), end='', flush=True )
t1 = t2
last_jump = n_jump
return prvkey, n_jump, (time.time()-t0)
def save2file(path, mode, data):
fp = open(path, mode)
if type(data) in (list,tuple,dict):
fp.writelines(data)
else:
#elif type(data) in (str,int):
fp.write(data)
fp.close()
def usage():
print('[usage] %s [bits] [pubkey]'%(sys.argv[0]))
print(' %s 32'%(sys.argv[0]))
print(' %s 32 %s'%(sys.argv[0],pubkeys[32][0]))
exit(-1)
#######################
#main
if __name__ == '__main__':
#print('[os] %s' % os.name)
if os.name == 'nt':
#freeze_support()
pass
print("[################################################]")
print("[# ECDSA Pollard-kangaroo PrivKey Recovery Tool #]")
print("[# based on code by 57fe 2019 #]")
print("[# singlecore #]");
#print("[# multicore #]");
print("[################################################]")
if len(sys.argv) > 1 and str(sys.argv[1]) in ('--help','-h','/?') :
usage()
print('[date] {}'.format(time.ctime()))
print("[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]")
if prngseed in (0,'0',False,'False','false',''):
prngseed = random.randint(1,2**32)
random.seed(prngseed)
print('[PRNGseed] %s' % prngseed)
if len(sys.argv) > 1 :
try:
pow2pubkey=int(sys.argv[1])
except:
usage()
if pow2pubkey < 1 or pow2pubkey > 256 :
print("[error] bits must be in range 1..256!")
usage()
print('[bits] 2^%s %s' % (pow2pubkey, '(warn: too big!)' if pow2pubkey>50 else ''))
if len(sys.argv) > 2 :
prvkey0 = False
pubkey0 = str(sys.argv[2])
print('[i] pubkey#%s loaded from argv2' % pow2pubkey)
elif flag_coincurve:
prvkey0 = random.randint(1,2**pow2pubkey)
pubkey0 = bytes_to_hex(PublicKey.from_secret(int_to_bytes_padded(prvkey0)).format(1))
#pubkey0 = bytes_to_hex(PublicKey.from_secret(int_to_bytes_padded(prvkey0)).format(0))
print('[i] pubkey#%s randomly generated' % pow2pubkey)
else:
pubkey0, prvkey0 = pubkeys[pow2pubkey]
print('[i] pubkey#%s loaded from default table' % pow2pubkey)
else:
print('[bits] 2^%s %s' % (pow2pubkey, '(warn: too big!)' if pow2pubkey>50 else ''))
pubkey0, prvkey0 = pubkeys[pow2pubkey]
print('[i] pubkey#%s loaded from default table' % pow2pubkey)
if prvkey0 not in (0,'0',False,'False','false',''):
print('[prvkey#%s] 0x%064x' % (pow2pubkey,prvkey0))
print('[pubkey#%s] %s' % (pow2pubkey,pubkey0))
#calc Y if pubkey is compress
if len(pubkey0)==130:
X = int(pubkey0[2:66], 16)
Y = int(pubkey0[66:],16)
print("[format] uncompressed")
elif len(pubkey0)==66:
X = int(pubkey0[2:66], 16)
Y = newX2Y(X,int(pubkey0[:2])-2)
print("[format] compressed")
else:
print("[error] pubkey len(66/130) invalid!")
usage()
print("[Xcoordinate] %064x" % X)
print("[Ycoordinate] %064x" % Y)
W0 = Point(X,Y)
print("[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]")
starttime = time.time()
P = [Gp]
for k in range(255): P.append(mul2(P[k]))
print('[+] P-table ready')
Nt = Nw = 2**pow2kangaroo
if flag_debug > 0:
print("[range(L..U)] 1..2^%s(0x%x)" % (pow2pubkey, 2**pow2pubkey))
print("[w=U-L] 0x%x ; w/2=0x%x" % (2**pow2pubkey, 2**(pow2pubkey-1)))
print("[pow2k] 2^%s: Nt=%s, Nw=%s" % (pow2kangaroo,Nt,Nw))
jumps_list = []
runtime_list = []
#timeit
for i in range(Ntimeit):
print("[~~~~~~~~~~~~~~~~~~~~~~~[%s]~~~~~~~~~~~~~~~~~~~~~~]"%(i+1))
if flag_debug > 0:
save2file('tame.txt', 'w', '')
save2file('wild.txt', 'w', '')
prvkey, n_jump, runtime = KANGAROO()
jumps_list.append(n_jump)
runtime_list.append(runtime)
print('')
print('[prvkeyX] %064x' % (prvkey) )
save2file('results.txt', 'a', ('%064x\n'%prvkey, '---------------\n'))
if prvkey0 not in (0,'0',False,'False','false',''):
print('[prvkey0] %064x' % (prvkey0))
if prvkey == prvkey0:
print('[double-check] success!')
else:
print('[double-check] failed!')
print('[jump] %s' % n_jump)
print('[time] %.1f sec' % runtime)
print("[################################################]")
if Ntimeit > 1:
M = sum(jumps_list)*1.0 / len(jumps_list)
print('[(avg)jump] %.0f' % (M) )
#D = sum((xi - M) ** 2 for xi in jumps_list)*1.0 / len(jumps_list)
#print('[(avg)jum2] %.1f +/- %.1f' % (M, (D/(len(jumps_list)-1))**0.5) )
print('[(avg)time] %.1f sec' % (sum(runtime for runtime in runtime_list)/Ntimeit) )
#print('[(avg)tim2] %.1f sec' % ((time.time()-starttime)/Ntimeit) )
else:
pass
print("[################################################]")
print('[date] {}'.format(time.ctime()))
#print('[exit] exit')
#print('');raw_input('Press ENTER to continue...');print('')
exit(0)
Addon needed
remove pubkeys = xxxxxx
add example
** with open("pubkeys.txt", "r") as m:
add = m.read().split()
for ad in add: ***
multi pubkeys at once check inside bit range
this script check only 1 pubkey in bit range
Any plans to release your changes? 