import time
import os
import sys
import random
import gmpy2
from math import log2, sqrt, log
from secrets import randbelow

if os.name=='nt':os.system('cls')
else:os.system('clear')
t=time.ctime()
sys.stdout.write(f"\033[?25l")
sys.stdout.write(f"\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):
    Z = (0, 0)
    if P == Z:
        return Q
    if Q == Z:
        return P
   
    Px, Py = P
    Qx, Qy = Q

    if Px == Qx:
        if Py == Qy:
            # Use double formula
            inv_2Py = gmpy2.invert((Py << 1) % modulo, modulo)
            m = (3 * Px * Px * inv_2Py) % modulo
        else:
            return Z
    else:
        inv_diff_x = gmpy2.invert(Qx - Px, modulo)
        m = ((Qy - Py) * inv_diff_x) % modulo

    x = (m * m - Px - Qx) % modulo
    y = (m * (Px - x) - Py) % modulo
   
    return (x, y)

def mul(k, P=PG):
    R = (0, 0)
    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 = gmpy2.powmod(X, 3, p)
    X_squared = gmpy2.powmod(X, 2, p)
    tmp = gmpy2.f_mod(X_cubed + 7, p)
    Y = gmpy2.powmod(tmp, gmpy2.f_div(gmpy2.add(p, 1), 4), p)
    if y_parity == 1:
        Y = gmpy2.f_mod(-Y, p)
    return Y

def generate_powers_of_two(hop_modulo):
    return [gmpy2.mpz(1 << pw) for pw in range(hop_modulo)]

def handle_solution(solution):
    HEX = "%064x" % abs(solution) 
    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("\n\nSOLVED " + t)
        file.write("\nPrivate Key (decimal): " + str(dec))
        file.write("\nPrivate Key (hex): " + HEX)
        file.write(f"\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
    t_values = [lower_range_limit + randbelow(upper_range_limit - lower_range_limit) for _ in range(Nt)]
    T = [mul(ti) for ti in t_values]
    dt = [gmpy2.mpz(0) for _ in range(Nt)]
    w_values = [randbelow(upper_range_limit - lower_range_limit) for _ in range(Nw)]
    W = [add(W0, mul(wk)) for wk in w_values]
    dw = [gmpy2.mpz(0) for _ in range(Nw)]
    print('[+] Tame and wild herds prepared.')   
    Hops, Hops_old = 0, 0
    tame_dps = {}
    wild_dps = {}
    last_print_time = time.time()
    while not solved:
        for k in range(Nt):
            Hops += 1
            pw = int(T[k][0] % hop_modulo) 
            dt[k] = powers_of_two[pw]
            if T[k][0] % DP_rarity == 0:
                x = T[k][0]
                if x in wild_dps:
                    solution = wild_dps[x] - t_values[k]
                    solved = handle_solution(solution)
                    return solved
                tame_dps[x] = t_values[k]
            t_values[k] += dt[k]
            T[k] = add(P[pw], T[k])       
        for k in range(Nw):
            Hops += 1
            pw = int(W[k][0] % hop_modulo) 
            dw[k] = powers_of_two[pw]
            if W[k][0] % DP_rarity == 0: 
                x = W[k][0]
                if x in tame_dps:
                    solution = w_values[k] - tame_dps[x]
                    solved = handle_solution(solution)
                    return solved
                wild_dps[x] = w_values[k]
            w_values[k] += dw[k]
            W[k] = add(P[pw], W[k])

        current_time = time.time()
        elapsed_time = current_time - starttime
        if current_time - last_print_time >= 5:
            time_since_last = current_time - last_print_time
            hops_since_last = Hops - Hops_old
            hops_per_second = hops_since_last / time_since_last if time_since_last > 0 else 0
            last_print_time = current_time
            Hops_old = Hops           
            hours, rem = divmod(elapsed_time, 3600)
            minutes, seconds = divmod(rem, 60)
            elapsed_time_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
            hops = f'{log2(Hops):.2f}' if Hops > 0 else '0.00'
            print(f'[+] [Hops: 2^{hops} <-> {hops_per_second:.0f} h/s] [{elapsed_time_str}]', end='\r', flush=True)
   
    print('\r[+] Hops:', Hops)
    print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)))

# Configuration for the puzzle
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = puzzle // 5
lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (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(puzzle ** 2):
    P.append(add(P[-1], P[-1]))
print('[+] P-table prepared')

# Start kangaroo search
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:x})")
print(f"[+] Expected Hops: 2^{log2(2.13 * sqrt(1 << (puzzle-1))):.2f} ({int(2.13 * sqrt(1 << (puzzle-1)))})")

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")