import multiprocessing
import hashlib
import binascii
from Crypto.Util.number import long_to_bytes, bytes_to_long

start_hex = '0000000000000000000000000000000000000000000000000000000000000000'
end_hex = '0000000000000000000000000000000000000000000000000000000000000000'
start = int(start_hex, 16)
end = int(end_hex, 16)
num_parts = 4

def kangaroo(start, end, pubkeys):
    G = 2
    hash_size = 256
    max_iters = 2**32

    def H(x):
        if isinstance(x, bytes):
            return hashlib.sha256(x).digest()
        else:
            return hashlib.sha256(x.to_bytes((x.bit_length() + 7) // 8, byteorder='big')).digest()




    def kangaroo_algorithm(x1, x2, step):
        x = x1
        xs = set()
        for i in range(max_iters):
            x = (x + step) % end
            h = bytes_to_long(H(long_to_bytes(x)))
            if h in pubkeys:
                return x, pubkeys[h]
            xs.add(x)
            if len(xs) == hash_size:
                xs.clear()
                y = x2
                for j in range(i):
                    y = (y + step) % end
                    if y in xs:
                        return x, None
        return None, None

    step = end // hash_size
    x1 = start
    x2 = start + step
    private_key, public_key = kangaroo_algorithm(x1, x2, step)
    if private_key is not None:
        private_hex = hex(private_key)[2:]
        private_hex = '0' * (64 - len(private_hex)) + private_hex
        return (private_key, private_hex, public_key)
    else:
        return None

if __name__ == '__main__':
    pubkeys_file = 'pubkeys.txt'
    foundkeys_file = 'foundkeys.txt'

    with open(pubkeys_file, 'r') as f:
        pubkeys = {int(line.strip(), 16) for line in f}

    pool = multiprocessing.Pool(processes=num_parts)

    start_ranges = [start + i * ((end - start) // num_parts) for i in range(num_parts)]
    end_ranges = [start + (i + 1) * ((end - start) // num_parts) for i in range(num_parts)]
    args = [(start_ranges[i], end_ranges[i], pubkeys) for i in range(num_parts)]

    results = pool.starmap(kangaroo, args)
    foundkeys = [result for result in results if result is not None]

    with open(foundkeys_file, 'w') as f:
        for result in foundkeys:
            f.write(f"{result[0]}\n")
            print(f"Found private key: {result[1]} for public key: {result[2]}")

    print("Done.")