import time, random
import secp256k1 as ice

modulo = ice.N
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
PG = Gx, Gy
Z = ice.Zero

def to_bytes(point):
    x_bytes = point[0].to_bytes(32, byteorder='big')
    y_bytes = point[1].to_bytes(32, byteorder='big')
    return b'\x04' + x_bytes + y_bytes

def from_bytes(point_bytes):
    x = int.from_bytes(point_bytes[1:33], byteorder='big')
    y = int.from_bytes(point_bytes[33:65], byteorder='big')
    return x, y

def add(P, Q, p=modulo):
    if P == Z: return Q
    if Q == Z: return P
    Px, Py = P; Qx, Qy = Q
    if Px == Qx and (Py != Qy or Py == 0): return Z
    P_bytes = to_bytes(P)
    Q_bytes = to_bytes(Q)
    result_bytes = ice.point_addition(P_bytes, Q_bytes)
    result = from_bytes(result_bytes)   
    return result

def mul2(P, p=modulo):
    if P == Z: return Z
    P_bytes = to_bytes(P)
    result_bytes = ice.point_doubling(P_bytes)
    result = from_bytes(result_bytes)   
    return result

def mulk(k, P=PG, p=modulo):
    result = Z
    addend = P
    while k > 0:
        if k & 1: result = add(result, addend, p)
        addend = mul2(addend, p)
        k >>= 1
    return result

def X2Y(X, y_parity, p=modulo):
    X_hex = '%064x' % X
    is_even = (y_parity == 0)
    Y_bytes = ice.get_x_to_y(X_hex, is_even)
    Y = int.from_bytes(Y_bytes, byteorder='big')
    if Y >= p:
        Y = p - Y
    return Y

def comparator(P, Pindex, DP_rarity, t, W, w, T):
    if 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 = [mulk(ti) for ti in t]
    w = [random.randint(0, upper - lower) for _ in range(Nw)]
    W = [add(W0, mulk(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 -= Nw
                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, "")

puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = 5
lower = 2 ** (puzzle - 1)
upper = (2 ** puzzle) - 1

DP_rarity = 1 << ((puzzle - 2 * kangaroo_power) // 2 - 2)
hop_modulo = (puzzle - 1) // 2 + kangaroo_power

Nt = 2 ** kangaroo_power
Nw = 2 ** kangaroo_power

if len(compressed_public_key) == 66:
    X = int(compressed_public_key[2:66], 16)
    y_parity = int(compressed_public_key[:2]) - 2
    Y = X2Y(X, y_parity)
else:
    print("[error] pubkey len(66/130) invalid!")

W0 = (X, Y)
starttime = time.time()
print_puzzle_info(puzzle, lower, upper, X, Y)

t, W, w, T = [], [], [], []

random.seed()

P = [PG]
for k in range(255):
    P.append(mul2(P[k]))

solved = search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper, lower)