from math import log2, sqrt

# Given puzzle number
puzzle = 130

# Calculate the expected hops
expected_hops = 2.2 * sqrt(2 ** (puzzle - 1))  # 2.2 * sqrt(2^(puzzle-1))
expected_hops_log2 = log2(expected_hops)

# Print the result
print(f"[+] [Expected Hops: 2^{expected_hops_log2:.2f} ({int(expected_hops)})]")

import time
import os
import sys
import random
import gmpy2
import multiprocessing
from math import log2, sqrt, log
from multiprocessing import Pool, cpu_count

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

modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
PG = (Gx, Gy)

Z = (0, 0)  # zero-point, infinite in real x, y - plane

def add(P, Q, p=modulo):
    Px, Py = P
    Qx, Qy = Q
    if P == Z:
        return Q
    elif Q == Z:
        return P
    elif Px == Qx and (Py != Qy or Py == 0):
        return Z
    elif Px == Qx:
        m = (3 * Px * Px) * gmpy2.invert(2 * Py, p) % p
    else:
        m = (Qy - Py) * gmpy2.invert(Qx - Px, p) % p
    
    x = (m * m - Px - Qx) % p
    y = (m * (Px - x) - Py) % p
    return (x, y)


def mul2(P, p=modulo):
    Px, Py = P
    if P == Z:
        return Z
    m = gmpy2.f_mod(3 * Px * Px * gmpy2.invert(2 * Py, p), p)
    x = gmpy2.f_mod(m * m - 2 * Px, p)
    y = gmpy2.f_mod(m * (Px - x) - Py, p)
    return (x, y)

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p), p)

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 comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        HEX = "%064x" % abs(Ak[sol_kt] - Bk[sol_kw])
        dec = int(HEX, 16)
        total_time = time.time() - starttime
        print('\n[+] total time: %.2f sec' % (total_time))
        t = time.ctime()
        print(f"\033[32m[+] PUZZLE SOLVED: {t} \033[0m")
        print(f"\033[32m[+] Private key (dec) : {dec} \033[0m")
        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(f"\nRandom seed: {seed}")
            file.write("\nPrivate Key (decimal): " + str(dec))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write(f"\n{dash_line}")
        file.close()
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    modulo_val = P[0] % DP_rarity
    if modulo_val == 0:
        A.append(gmpy2.mpz(P[0]))
        Ak.append(gmpy2.mpz(Pindex))
        return comparator(A, Ak, B, Bk)
    else:
        return False

# Generate a list of powers of two for faster access
def generate_powers_of_two(hop_modulo):
    return [gmpy2.mpz(1 << pw) for pw in range(hop_modulo)]

def search(thread_id, P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, result_queue, powers_of_two):
    t = [gmpy2.mpz(lower_range_limit + gmpy2.mpz(random.randint(0, upper_range_limit - lower_range_limit))) for _ in range(Nt)]
    T = [mulk(ti) for ti in t]
    dt = [gmpy2.mpz(0) for _ in range(Nt)]
    w = [gmpy2.mpz(random.randint(0, upper_range_limit - lower_range_limit)) for _ in range(Nw)]
    W = [add(W0, mulk(wk)) for wk in w]
    dw = [gmpy2.mpz(0) for _ in range(Nw)]
    Hops, Hops_old = 0, 0
    t0 = time.time()  
    # Memoization dictionary
    memo = {}
    solution_found = False  # Flag to control the loop
    while not solution_found:
        for k in range(Nt):
            Hops += 1
            pw = T[k][0] % hop_modulo
            if pw not in memo:
                memo[pw] = powers_of_two[pw]
            dt[k] = memo[pw]
            if check(T[k], t[k], DP_rarity, T, t, W, w):
                result_queue.put((thread_id, T[k], t[k], W[k], w[k]))
                solution_found = True  # Set flag to exit loop
                break  # Exit the for-loop
            t[k] += dt[k]
            T[k] = add(P[int(pw)], T[k])
        if solution_found:  # Break the while-loop if solution is found
            break
        for k in range(Nw):
            Hops += 1
            pw = W[k][0] % hop_modulo
            if pw not in memo:
                memo[pw] = powers_of_two[pw]
            dw[k] = memo[pw]
            if check(W[k], w[k], DP_rarity, W, w, T, t):
                result_queue.put((thread_id, T[k], t[k], W[k], w[k]))
                solution_found = True  # Set flag to exit loop
                break  # Exit the for-loop
            w[k] += dw[k]
            W[k] = add(P[int(pw)], W[k])
        if solution_found:  # Break the while-loop if solution is found
            break
        t1 = time.time()
        elapsed_time = t1 - starttime
        if t1 - t0 > 1 and thread_id == 0:
            hops_per_second = (Hops - Hops_old) / (t1 - t0) * cores
            hours, rem = divmod(elapsed_time, 3600)
            minutes, seconds = divmod(rem, 60)
            elapsed_time_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
            p_2 = f'{log2(Hops*cores):.2f}'
            print(f'[+] [Hops: 2^{p_2} <-> {hops_per_second:.0f} h/s] [{elapsed_time_str}]', end='\r', flush=True)
            t0 = t1
            Hops_old = Hops
    print('\r[+] Hops:', Hops* cores)
    print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)))

def main():
    result_queue = multiprocessing.Queue()
    processes = [
        multiprocessing.Process(target=search, args=(i, P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, result_queue, powers_of_two)) for i in range(cores)
    ]
    for p in processes:
        p.start()
    result = result_queue.get()
    for p in processes:
        p.terminate()

# Configuration for the puzzle
cores = cpu_count()
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = 3  
lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (2**puzzle) - 1

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

# Precompute powers of two for faster access
powers_of_two = generate_powers_of_two(hop_modulo)

T, t, dt = [], [], []
W, w, dw = [], [], []
A, Ak, B, Bk = [], [], [], []
print('[+] [Tame and Wild herds are prepared]')

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

W0 = (X,Y)
starttime = oldtime = time.time()

Hops = 0

P = [PG]
for k in range(255): 
    P.append(mul2(P[k]))  
print('[+] [P-table prepared]')

print(f"[+] [Using {cores} CPU cores for parallel search]")
print(f"[+] [Puzzle: {puzzle}]")
print(f"[+] [Lower range limit: {lower_range_limit}]")
print(f"[+] [Upper range limit: {upper_range_limit}]")
print(f"[+] [Expected Hops: 2^{log2(2.2 * sqrt(1 << (puzzle-1))):.2f} ({int(2.2 * sqrt(1 << (puzzle-1)))})]") 

#Random seed Config
seed = os.urandom(9).hex()
print(f"[+] [Random seed: {seed}]")
random.seed(seed)


if __name__ == '__main__':
    main()

#include <iostream>
#include <vector>
#include <iomanip>
#include <openssl/bn.h>
#include <openssl/ec.h>
#include <openssl/obj_mac.h>
#include <openssl/evp.h>
#include <openssl/rand.h>
#include <openssl/sha.h>
#include <openssl/ripemd.h>
#include <ctime>
#include <sstream>
#include <fstream>
#include <thread>
#include <mutex>

// Convert bytes to hex string
std::string bytesToHex(const std::vector<unsigned char>& bytes) {
    std::stringstream ss;
    for (unsigned char byte : bytes) {
        ss << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(byte);
    }
    return ss.str();
}

// Generate keys and check for match
void generateKeys(BIGNUM* minKeyBN, BIGNUM* range, const std::vector<unsigned char>& target_hash160_bytes, std::mutex& outputMutex) {
    BIGNUM* randomPrivateKey = BN_new();
    BN_CTX* ctx = BN_CTX_new();
    EC_KEY* ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
    const EC_GROUP* curve = EC_KEY_get0_group(ec_key);
    EC_POINT* public_key_point = EC_POINT_new(curve);

    std::vector<unsigned char> sha256_result(SHA256_DIGEST_LENGTH);
    std::vector<unsigned char> ripemd160_result(RIPEMD160_DIGEST_LENGTH);

    while (true) {
        // Generate a random number in the range [0, range)
        BN_rand_range(randomPrivateKey, range);

        // Add the minimum value to the generated random number
        BN_add(randomPrivateKey, randomPrivateKey, minKeyBN);

        // Convert private key to bytes
        int numBytes = BN_num_bytes(randomPrivateKey);
        std::vector<unsigned char> private_key_bytes(numBytes);
        BN_bn2bin(randomPrivateKey, private_key_bytes.data());

        // Calculate the public key
        EC_KEY_set_private_key(ec_key, randomPrivateKey);
        EC_POINT_mul(curve, public_key_point, randomPrivateKey, NULL, NULL, ctx);

        size_t public_key_length = EC_POINT_point2oct(curve, public_key_point, POINT_CONVERSION_COMPRESSED, NULL, 0, ctx);
        std::vector<unsigned char> public_key_bytes(public_key_length);
        EC_POINT_point2oct(curve, public_key_point, POINT_CONVERSION_COMPRESSED, public_key_bytes.data(), public_key_length, ctx);

        // Calculate the hashes
        SHA256(public_key_bytes.data(), public_key_bytes.size(), sha256_result.data());
        RIPEMD160(sha256_result.data(), sha256_result.size(), ripemd160_result.data());

        // Convert to hex string for comparison
        std::string calculated_hash160_hex = bytesToHex(ripemd160_result);

        {
            std::lock_guard<std::mutex> lock(outputMutex);
            std::cout << "\r\033[01;33m[+] Public Key Hash (Hash 160): " << calculated_hash160_hex << "\e[?25l";
            std::cout.flush();
        }

        if (ripemd160_result == target_hash160_bytes) {
            std::time_t currentTime;
            std::time(&currentTime);
            std::tm tmStruct = *std::localtime(&currentTime);
            std::stringstream timeStringStream;
            timeStringStream << std::put_time(&tmStruct, "%Y-%m-%d %H:%M:%S");
            std::string formattedTime = timeStringStream.str();

            {
                std::lock_guard<std::mutex> lock(outputMutex);
                std::cout << "\n\033[32m[+] PUZZLE SOLVED: " << formattedTime << "\033[0m" << std::endl;
                std::cout << "\r\033[32m[+] Target Public Key Hash (Hash160) found! Private Key: " << bytesToHex(private_key_bytes) << std::endl;
            }

            std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app);
            if (file.is_open()) {
                file << "\nPUZZLE SOLVED " << formattedTime;
                file << "\nPrivate Key (hex): " << bytesToHex(private_key_bytes);
                file << "\n-------------------------------------------------------------------------------------";
                file.close();
            }

            break;
        }
    }

    BN_free(randomPrivateKey);
    EC_POINT_free(public_key_point);
    EC_KEY_free(ec_key);
    BN_CTX_free(ctx);
}

int main() {
    if (OpenSSL_add_all_algorithms() != 1) {
        std::cerr << "OpenSSL initialization failed." << std::endl;
        return 1;
    }

    BIGNUM* minKeyBN = BN_new();
    BIGNUM* maxKeyBN = BN_new();
    BIGNUM* range = BN_new();

    // Configuration for the **Puzzle 20**
    BN_dec2bn(&minKeyBN, "524287");   // min range
    BN_dec2bn(&maxKeyBN, "1048575");  // max  range
    std::string target_hash160_hex = "b907c3a2a3b27789dfb509b730dd47703c272868";

    // Calculate the range (maxKey - minKey)
    BN_sub(range, maxKeyBN, minKeyBN);

    // Convert the target_hash160_hex string to bytes
    std::vector<unsigned char> target_hash160_bytes;
    for (size_t i = 0; i < target_hash160_hex.length(); i += 2) {
        std::string byteString = target_hash160_hex.substr(i, 2);
        unsigned char byte = static_cast<unsigned char>(std::stoul(byteString, nullptr, 16));
        target_hash160_bytes.push_back(byte);
    }

    unsigned int num_cores = std::thread::hardware_concurrency();
    const int numThreads = num_cores; // Adjust the number of threads as needed
    std::system("clear");
    time_t currentTime = std::time(nullptr);
    char* minKeyStr = BN_bn2dec(minKeyBN);
    char* maxKeyStr = BN_bn2dec(maxKeyBN);
    int minKeyBits = BN_num_bits(minKeyBN);
    int maxKeyBits = BN_num_bits(maxKeyBN);
    int numBits = std::max(minKeyBits, maxKeyBits);
    std::cout << "\r\033[01;33m[+] HASH160 Search by NoMachine" << "\n";
    std::cout << "\r\033[01;33m[+] " << SSLeay_version(SSLEAY_VERSION) << std::endl;
    std::cout << "\r\033[01;33m[+] " << std::ctime(&currentTime);  
    std::cout << "\r\033[01;33m[+] Puzzle: " << numBits << "\n";
    std::cout << "\r\033[01;33m[+] Lower range limit: " << minKeyStr << "\n";
    std::cout << "\r\033[01;33m[+] Upper range limit: " << maxKeyStr << "\n";
    std::cout << "\r\033[01;33m[+] Using " << num_cores << " CPU cores for parallel search\033[0m" << std::endl;
    OPENSSL_free(minKeyStr);
    OPENSSL_free(maxKeyStr);
    std::cout.flush();

    std::mutex outputMutex;
    std::vector<std::thread> threads;

    for (int i = 0; i < numThreads; i++) {
        threads.emplace_back(generateKeys, minKeyBN, range, target_hash160_bytes, std::ref(outputMutex));
    }

    for (std::thread& thread : threads) {
        thread.join();
    }

    // Cleanup
    BN_free(minKeyBN);
    BN_free(maxKeyBN);
    BN_free(range);

    return 0;
}

g++ -o puzzle puzzle.cpp -lssl -lcrypto -m64 -mssse3 -Wno-write-strings -pthread -ftree-vectorize -flto -Wall -Wextra -funroll-loops -finline-functions -O3

/opt/AMD/aocc-compiler-4.2.0/bin/clang++ -o puzzle puzzle.cpp -lssl -lcrypto -m64 -march=znver2 -mtune=znver2 -mfpmath=sse -mssse3 -msse3 -msse4 -msse4.1 -msse4.2 -msse4a -Wno-write-strings -pthread -ftree-vectorize -flto -Wall -Wextra -funroll-loops -finline-functions -O3

gcc -Q -march=native --help=target | grep -E '^\s+-.*(sse|march)'

./keyhunt -m bsgs -f 65.txt -b 65 -e -t 12 -l compress -q -S -k 4096