import math, time, sys, os
from gmpy2 import mpz, powmod, invert, jacobi
import xxhash  
from sortedcontainers import SortedDict

# Clear screen and initialize
os.system("cls||clear")
t = time.ctime()
sys.stdout.write(f"\033[?25l\033[01;33m[+] BSGS: {t}\n")
sys.stdout.flush()

# Elliptic Curve Parameters (secp256k1)
modulo = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
PG = (Gx, Gy)

# Point Addition on Elliptic Curve
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_2Py = invert((Py << 1) % modulo, modulo)
            m = (3 * Px * Px * inv_2Py) % modulo
        else:
            return (0, 0)
    else:
        inv_diff_x = 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)

# Scalar Multiplication on Elliptic Curve
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

# Point Subtraction
def point_subtraction(P, Q):
    Q_neg = (Q[0], (-Q[1]) % modulo)
    return add(P, Q_neg)

# Compute Y from X using curve equation
def X2Y(X, y_parity, p=modulo):
    X3_7 = (pow(X, 3, p) + 7) % p
    if jacobi(X3_7, p) != 1:
        return None
    Y = powmod(X3_7, (p + 1) >> 2, p)
    return Y if (Y & 1) == y_parity else (p - Y)

# Convert point to compressed public key
def point_to_cpub(point):
    x, y = point
    y_parity = y & 1
    prefix = '02' if y_parity == 0 else '03'
    compressed_pubkey = prefix + format(x, '064x')
    return compressed_pubkey

# Hash a compressed public key using xxhash and store only the first 8 characters
def hash_cpub(cpub):
    return xxhash.xxh64(cpub.encode()).hexdigest()[:8]

# Main Script
if __name__ == "__main__":
    # Puzzle Parameters
    puzzle = 40
    start_range, end_range = 2**(puzzle-1), (2**puzzle) - 1
    puzzle_pubkey = '03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4'

    # Parse Public Key
    if len(puzzle_pubkey) != 66:
        print("[error] Public key length invalid!")
        sys.exit(1)
    prefix = puzzle_pubkey[:2]
    X = mpz(int(puzzle_pubkey[2:], 16))
    y_parity = int(prefix) - 2
    Y = X2Y(X, y_parity)
    if Y is None:
        print("[error] Invalid compressed public key!")
        sys.exit(1)
    P = (X, Y)  # Uncompressed public key

    # Precompute m and mP for BSGS
    m = int(math.floor(math.sqrt(end_range - start_range)))
    m_P = mul(m)

    # Create Baby Table with SortedDict
    print('[+] Creating babyTable...')
    baby_table = SortedDict()  
    Ps = (0, 0)  # Start with the point at infinity
    for i in range(m + 1):
        cpub = point_to_cpub(Ps)
        cpub_hash = hash_cpub(cpub)  # Use xxhash and store only 8 characters
        baby_table[cpub_hash] = i  # Store the hash as the key and index as the value
        Ps = add(Ps, PG)  # Incrementally add PG

    # BSGS Search
    print('[+] BSGS Search in progress')
    S = point_subtraction(P, mul(start_range))
    step = 0
    st = time.time()
    while step < (end_range - start_range):
        cpub = point_to_cpub(S)
        cpub_hash = hash_cpub(cpub)  # Hash the current compressed public key
        # Check if the hash exists in the baby_table
        if cpub_hash in baby_table:
            b = baby_table[cpub_hash]
            k = start_range + step + b
            if point_to_cpub(mul(k)) == puzzle_pubkey:
                print(f'[+] m={m} step={step} b={b}')
                print(f'[+] Key found: {k}')
                print("[+] Time Spent : {0:.2f} seconds".format(time.time() - st))
                sys.exit()
        S = point_subtraction(S, m_P)
        step += m

    print('[+] Key not found')
    print("[+] Time Spent : {0:.2f} seconds".format(time.time() - st))