import time, random
from gmpy2 import mpz, f_mod, powmod, invert
modulo = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
Gx = mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
PG = (Gx, Gy)
Z = (0, 0)
def add(P, Q, p=modulo):
Px, Py = P
Qx, Qy = Q
if P == Z:
return Q
elif Q == Z:
return P
elif Px == Qx:
if Py != Qy or Py == 0:
return Z
num = 3 * Px * Px
denom = 2 * Py
else:
num = Qy - Py
denom = Qx - Px
m = (num * invert(denom, p)) % p
x = (m * m - Px - Qx) % p
y = (m * (Px - x) - Py) % p
return (x, y)
def mul(k, P=PG):
R = Z
while k:
if k & 1:
R = add(R, P)
P = add(P, P)
k >>= 1
return R
def X2Y(X, y_parity, p=modulo):
X_cubed = powmod(X, 3, p)
tmp = (X_cubed + 7) % p
Y = powmod(tmp, (p + 1) // 4, p)
if y_parity == 1:
Y = (-Y) % p
return Y
def comparator(P, Pindex, DP_rarity, t, W, w, T):
if f_mod(P[0], DP_rarity) == 0:
T.append(P[0])
t.append(Pindex)
common_elements = set(T).intersection(W)
if common_elements:
match = common_elements.pop()
tT = t[T.index(match)]
wW = w[W.index(match)]
HEX = '%064x' % abs(tT - wW)
dec = int(HEX, 16)
total_time = time.time() - starttime
print(f"\n[+] total time: {total_time:.2f} sec")
print_status(time.ctime(), 'PUZZLE SOLVED')
print(f"\033[32m[+] Private key (hex) : {HEX} \033[0m")
log_solution(total_time, dec, HEX)
return True
return False
def search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper, lower):
t = [lower + random.randint(0, upper - lower) for _ in range(Nt)]
T = [mul(ti) for ti in t]
w = [random.randint(0, upper - lower) for _ in range(Nw)]
W = [add(W0, mul(wi)) for wi in w]
Hops, Hops_old = 0, 0
t0 = time.time()
solved = False
while not solved:
for k in range(Nt + Nw):
Hops += 1
if k < Nt:
pw = T[k][0] % hop_modulo
solved = comparator(T[k], t[k], DP_rarity, T, t, W, w)
if solved: break
t[k] += 1 << pw
T[k] = add(P[pw], T[k])
else:
k -= Nt
pw = W[k][0] % hop_modulo
solved = comparator(W[k], w[k], DP_rarity, W, w, T, t)
if solved: break
w[k] += 1 << pw
W[k] = add(P[pw], W[k])
t1 = time.time()
elapsed_time = t1 - starttime
if (t1 - t0) > 1:
hops_per_second = (Hops - Hops_old) / (t1 - t0)
hours, rem = divmod(elapsed_time, 3600)
minutes, seconds = divmod(rem, 60)
elapsed_time_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
print(f'[+] [Hops: {hops_per_second:.0f} h/s] [{elapsed_time_str}]', end='\r', flush=True)
t0 = t1
Hops_old = Hops
print('\r[+] Hops:', Hops)
print('[+] Average time to solve: %.2f sec' % ((time.time() - starttime)))
def print_status(t, message):
print(f"\033[?25l\033[01;33m[+]\033[32m KANGAROO: \033[01;33m{t}\033[0m {message}")
def print_puzzle_info(puzzle, lower, upper, X, Y):
print(f"[+] [Puzzle]: {puzzle}")
print(f"[+] [Lower range limit]: {hex(lower)}")
print(f"[+] [Upper range limit]: {hex(upper)}")
print(f"[+] [EC Point Coordinate X]: {hex(X)}")
print(f"[+] [EC Point Coordinate Y]: {hex(Y)}")
def log_solution(total_time, dec, HEX):
t = time.ctime()
dash_line = '-' * 140
with open("KEYFOUNDKEYFOUND.txt", "a") as file:
file.write(f"\n{dash_line}")
file.write("\n\nSOLVED " + t)
file.write(f"\nTotal Time: {total_time:.2f} sec")
file.write("\nPrivate Key (decimal): " + str(dec))
file.write("\nPrivate Key (hex): " + HEX)
file.write(f"\n{dash_line}")
t = time.ctime()
print_status(t, "")
# Configuration for the puzzle
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = 5
lower = 2 ** (puzzle - 1)
upper = (2 ** puzzle) - 1
DP_rarity = 1 << int(((puzzle - 2*kangaroo_power)/2 - 2))
hop_modulo = ((puzzle - 1) // 2) + kangaroo_power
Nt = Nw = 2**kangaroo_power
if len(compressed_public_key) == 66:
X = mpz(compressed_public_key[2:66], 16)
Y = X2Y(X, mpz(compressed_public_key[:2]) - 2)
else:
print("[error] pubkey len(66/130) invalid!")
W0 = (X, Y)
starttime = time.time()
print_puzzle_info(puzzle, lower, upper, X, Y)
Hops = 0
solved = False
random.seed()
P = [PG]
for k in range(255):
P.append(add(P[k], P[k]))
solved = search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper, lower)
