# based on http://fe57.org/forum/thread.php?board=4&thema=1
import time, os, sys
from secrets import randbelow
import secp256k1 #https://github.com/iceland2k14/secp256k1
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()

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{'-' * 130}\n")
    return True

def search(W0, DP_rarity, Nw, Nt, hop_modulo, end, start, powers_of_two, P_table):
    solved = False
    rand_range = end - start
    t_values = [start + randbelow(rand_range) for _ in range(Nt)]
    w_values = [randbelow(rand_range) for _ in range(Nw)]
    T = [secp256k1.scalar_multiplication(ti) for ti in t_values]
    W = [secp256k1.point_addition(W0, secp256k1.scalar_multiplication(wk)) for wk in w_values]  
    dt = [0] * Nt
    dw = [0] * Nw
    tame_points, wild_points = {}, {}  
    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
            pub_t = secp256k1.point_to_cpub(Tk)[2:].zfill(64)
            pw = int(pub_t, 16) % hop_modulo
            dt[k] = powers_of_two[pw]          
            if int(pub_t, 16) & (DP_rarity - 1) == 0:  # DP check
                tame_points[pub_t] = t_values[k]
                if pub_t in wild_points:
                    return handle_solution(t_values[k] - wild_points[pub_t])        
            t_values[k] += dt[k]
            T[k] = secp256k1.point_addition(P_table[pw], Tk)
        for k, Wk in enumerate(W):
            Hops += 1
            pub_w = secp256k1.point_to_cpub(Wk)[2:].zfill(64)
            pw = int(pub_w, 16) % hop_modulo
            dw[k] = powers_of_two[pw]          
            if int(pub_w, 16) & (DP_rarity - 1) == 0:  # DP check
                wild_points[pub_w] = w_values[k]
                if pub_w in tame_points:
                    return handle_solution(tame_points[pub_w] - w_values[k])        
            w_values[k] += dw[k]
            W[k] = secp256k1.point_addition(P_table[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
start, end = 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)

P_table = []
pk = 1
for _ in range(255):
    P_table.append(secp256k1.scalar_multiplication(pk))
    pk *= 2    
print(f"[+] P-table prepared with {len(P_table)} points")

W0 = secp256k1.pub2upub(compressed_public_key)
starttime = time.time()

print(f"[+] Puzzle: {puzzle}")
print(f"[+] Lower range limit: {start}")
print(f"[+] Upper range limit: {end}")
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(W0, DP_rarity, Nw, Nt, hop_modulo, end, start, powers_of_two, P_table)
print(f"[+] Total time: {time.time() - starttime:.2f} seconds")