its a bit mumbled up , wanted your perspective , and not working also as intended , be gentle:
maybe speed up your Python.
What are you trying to do? It looks like you made some changes to the Python Kangaroo I posted 4 months ago that worked fine (sort of). What are the theoretical bases for your changes though? Some things to consider:
1. I stated several times the code is just for learning purposes. It has its own limitations and had some bugs as well, in edge-cases.
2. Python is very slow, even when using GMP.
3. Kangaroo with only 2 kang types takes longer to solve.
4. Kangaroo that doesn't take advantage of curve symmetry takes longer to solve.
5. Once you change jump tables, alpha, etc. you should
really, really know what you're doing, and why. Point doublings (kang == jump_point) are not supported, for private reasons (that code was shrinked down from a larger implementation, I never need to bother with point doublings in any of my algorithms).
Thanks for the input and insight , kang == jump point , enlighten me please.
import time
import os
import sys
import gmpy2
from secrets import randbelow
from math import log2, sqrt, log
os.system("cls||clear")
t = time.ctime()
sys.stdout.write(f"\033[?25l\033[01;33m[+] Kangaroo: {t}\n")
sys.stdout.flush()
modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
PG = (Gx, Gy)
def add(P, Q):
if P == (0, 0): return Q
if Q == (0, 0): return P
Px, Py = P
Qx, Qy = Q
if Px == Qx:
if Py == Qy:
inv_den = gmpy2.invert(Py << 1, modulo)
m = (3 * Px * Px * inv_den) % modulo
else:
return (0, 0)
else:
inv_dx = gmpy2.invert(Qx - Px, modulo)
m = ((Qy - Py) * inv_dx) % modulo
x = (m * m - Px - Qx) % modulo
y = (m * (Px - x) - Py) % modulo
return (x, y)
def mul(k, P=PG):
R0, R1 = (0, 0), P
for i in reversed(range(k.bit_length())):
if (k >> i) & 1:
R0, R1 = add(R0, R1), add(R1, R1)
else:
R1, R0 = add(R0, R1), add(R0, R0)
return R0
def X2Y(X, y_parity, p=modulo):
X3_7 = (pow(X, 3, p) + 7) % p
if gmpy2.jacobi(X3_7, p) != 1:
return None
Y = gmpy2.powmod(X3_7, (p + 1) >> 2, p)
return Y if (Y & 1) == y_parity else (p - Y)
def generate_powers_of_two(hop_modulo):
return [1 << pw for pw in range(hop_modulo)]
def handle_solution(solution):
HEX = f"{abs(solution):064x}"
dec = int(HEX, 16)
print(f"\n\033[32m[+] PUZZLE SOLVED \033[0m")
print(f"\033[32m[+] Private key (dec): {dec} \033[0m")
with open("KEYFOUNDKEYFOUND.txt", "a") as file:
file.write(f"\n\nSOLVED {t}\nPrivate Key (decimal): {dec}\nPrivate Key (hex): {HEX}\n{'-' * 100}\n")
return True
def search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two):
solved = False
rand_range = upper_range_limit - lower_range_limit
t_values = [lower_range_limit + randbelow(rand_range) for _ in range(Nt)]
w_values = [randbelow(rand_range) for _ in range(Nw)]
T = [mul(ti) for ti in t_values]
W = [add(W0, mul(wk)) for wk in w_values]
dt = [0] * Nt
dw = [0] * Nw
tame_dps, wild_dps = {}, {}
print('[+] Tame and wild herds prepared')
last_print_time = starttime = time.time()
Hops, Hops_old = 0, 0
while not solved:
current_time = time.time()
for k, Tk in enumerate(T):
Hops += 1
Tk_x = Tk[0]
pw = Tk_x % hop_modulo
dt[k] = powers_of_two[pw]
if Tk_x % DP_rarity == 0:
wild_value = wild_dps.get(Tk_x)
if wild_value is not None:
return handle_solution(wild_value - t_values[k])
tame_dps[Tk_x] = t_values[k]
t_values[k] += dt[k]
T[k] = add(P[pw], Tk)
for k, Wk in enumerate(W):
Hops += 1
Wk_x = Wk[0]
pw = Wk_x % hop_modulo
dw[k] = powers_of_two[pw]
if Wk_x % DP_rarity == 0:
tame_value = tame_dps.get(Wk_x)
if tame_value is not None:
return handle_solution(w_values[k] - tame_value)
wild_dps[Wk_x] = w_values[k]
w_values[k] += dw[k]
W[k] = add(P[pw], Wk)
if current_time - last_print_time >= 5:
elapsed_time = current_time - starttime
hops_since_last = Hops - Hops_old
hops_per_second = hops_since_last (current_time - last_print_time)
last_print_time = current_time
Hops_old = Hops
elapsed_time_str = time.strftime('%H:%M:%S', time.gmtime(elapsed_time))
hops_log = f'{log2(Hops):.2f}' if Hops > 0 else '0.00'
print(f'[+] [Hops: 2^{hops_log} <-> {hops_per_second:.0f} h/s] [{elapsed_time_str}]',
end='\r', flush=True)
print('\r[+] Hops:', Hops)
print(f'[+] Average time to solve: {time.time() - starttime:.2f} sec')
# Configuration
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = puzzle/ 5
lower_range_limit, upper_range_limit = 2**(puzzle-1), (2**puzzle) - 1
DP_rarity = 1 << ((puzzle - 1)/ 2 - 2)/ 2 + 2
hop_modulo = round(log(2**puzzle)+5)
Nt = Nw = 2**kangaroo_power
powers_of_two = generate_powers_of_two(hop_modulo)
if len(compressed_public_key) == 66:
X = gmpy2.mpz(int(compressed_public_key[2:66], 16))
Y = X2Y(X, int(compressed_public_key[:2]) - 2)
else:
print("[error] Public key length invalid!")
sys.exit(1)
W0 = (X, Y)
P = [PG]
for _ in range(int(puzzle ** 1.1)):
P.append(mul(2, P[-1]))
print('[+] P-table prepared')
starttime = time.time()
print(f"[+] Puzzle: {puzzle}")
print(f"[+] Lower range limit: {lower_range_limit}")
print(f"[+] Upper range limit: {upper_range_limit}")
print(f"[+] DP: 2^{int(log2(DP_rarity))} ({DP_rarity:d})")
print(f"[+] Expected Hops: 2^{log2(2 * sqrt(1 << puzzle)):.2f} ({int(2 * sqrt(1 << puzzle))})")
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two)
print(f"[+] Total time: {time.time() - starttime:.2f} seconds")
- Kangaroo: Fri Feb 7 22:00:56 2025
- P-table prepared
- Puzzle: 40
- Lower range limit: 549755813888
- Upper range limit: 1099511627775
- DP: 2^10(400)
- Expected Hops: 2^21.00 (2097152)
- Tame and wild herds prepared.
- [Hops: 2^20.59 <-> 316085 h/s] [00:00:05]
- PUZZLE SOLVED
- Private key (dec): 1003651412950
- Total time: 5.21 seconds
You can also try my script for learning process.
But I won't give you false hope that this script can solve anything above 60 soon. It's simply beyond the reach of python's capabilities.
