Pollard Rho Kangaroo Algorithm for 256 bits

[krashfire]

Hi, im hoping to get some advice on how i can fine tune, optimized or enhance my code further to calculate the 256 bit private key.

your advice is very much appreciated.

Code:

import random
from math import gcd

# Function to extract public key coordinates from hex string
def extract_public_key_coordinates(public_key):
    try:
        x, y = public_key.split(',')
        print("Public key coordinates extracted successfully.")
        return int(x, 16), y
    except ValueError:
        print("Error: Invalid public key format.")
        return None, None

# Function for Pollard's Rho factorization
def pollard_rho_factorization(n, limit=1000000):
    print("Performing Pollard's Rho factorization...")
    def f(x):
        return (x ** 2 + 1) % n

    x = random.randint(1, n - 1)
    y = x
    d = 1

    while d == 1:
        x = f(x)
        y = f(f(y))
        d = gcd(abs(x - y), n)

    return d if d != n else None

# Function to perform the Kangaroo algorithm with factors
def kangaroo_algorithm(g, h, n, factors, B):
    print("Performing Kangaroo algorithm...")
    P = 0
    Q = 0
    wild_kangaroos = [(random.randint(1, n - 1), random.randint(1, n - 1)) for _ in range(10)]  # Multiple parallel wild kangaroos
    wild_jump_size = random.randint(1, B // 10)  # Randomized wild kangaroo step size

    while True:
        for wild_x, wild_y in wild_kangaroos:
            u = wild_x
            v = wild_y
            for _ in range(wild_jump_size):
                u = (u * g) % n
                v = (v * h) % n
            d = gcd(u - v, n)
            if 1 < d < n:
                return d
            if d == 1:
                alpha = kangaroo_attack(P, Q, g, n, h, B)  # Using kangaroo_attack
                if alpha is not None:
                    return alpha
                P += B
                Q += B
            else:
                return d

# Simple Kangaroo Attack (Floyd's Cycle Detection Algorithm)
def kangaroo_attack(P, Q, g, n, h, B):
    print("Performing Kangaroo attack...")
    u = P
    v = Q
    u_iterations = 0
    v_iterations = 0

    while True:
        # Tame Kangaroo
        u = (u * g) % n
        u_iterations += 1

        # Wild Kangaroo
        v = (v * h) % n
        v_iterations += 1

        if u == v:
            # Collision detected, solve for alpha
            alpha = (P - Q) * pow(g, -1, n) % n  # Inverse of g modulo n
            return alpha

        if max(u_iterations, v_iterations) > B:
            # Maximum iterations reached without collision
            return None

if __name__ == "__main__":
    # Example usage
    public_key = "d6xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,3xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
    x, y_hex = extract_public_key_coordinates(public_key)

    if x is not None and y_hex is not None:
        # Convert y-coordinate from hex to integer
        try:
            y = int(y_hex, 16)
            print("Y-coordinate converted to integer successfully.")
        except ValueError:
            print("Error: Unable to convert y-coordinate to integer.")

        # Perform factorization using Pollard's Rho
        try:
            factors = [pollard_rho_factorization(number) for number in [x, y, x + y]]
            print("Factorization complete:", factors)
        except Exception as e:
            print("Error during factorization:", e)

        # Parameters for Kangaroo algorithm
        p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
        n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
        g = 55066263022277343669578718895168534326250603453777594175500187360389116729240
        h = y  # Use the integer value of y
        B = 2**42  # Adjust based on your system's memory constraints

        # Find private key using the Kangaroo algorithm with factors
        try:
            private_key = kangaroo_algorithm(g, h, n, factors, B)
            print("Private Key:", private_key)
        except Exception as e:
            print("Error during Kangaroo algorithm:", e)
    else:
        print("Error: Public key extraction failed.")

[COBRAS]

Imposible to dolve 256 bit

and in python imposible to solve 100 bit

[satashi_nokamato]

How do you set the range to search for the key? Also what is h and which y should we use in this line  "h = y  # Use the integer value of y" ?

[krashfire]

How do you set the range to search for the key? Also what is h and which y should we use in this line  "h = y  # Use the integer value of y" ?

Here's a simplified explanation of how the Kangaroo algorithm works in this context:

Tame Kangaroos: These kangaroos make small jumps and keep track of their positions as they move along the curve. They're responsible for exploring the region near the expected position of
𝑘
k and
𝑄
Q.

Wild Kangaroos: These kangaroos make large jumps and are used to cover a wider range of possible positions of
𝑘
k and
𝑄
Q.

Collision Detection: The algorithm looks for collisions, which occur when a tame kangaroo and a wild kangaroo land on the same point on the curve. This indicates a potential match for
𝑘
k and
𝑄
Q.

Private Key Extraction: Once a collision is detected, you can extract the private key
𝑘
k from the positions of the kangaroos at the collision point.

The key concept here is that you're not searching through a numerical range of
𝑘
k values linearly.

Instead, you're using kangaroos to explore the curve in a smart way, leveraging collisions to pinpoint the private key without exhaustively trying every possible
𝑘
k value.

h = y means the public key xy coordinates. in this part we are just using y.

[nomachine]

I have 205288 hops per second in python on single core my friend......

It will work from 1 - 256 bit . But it is impossible to solve any Puzzle above 50 with this for a lifetime.

Code:

import time
import os
import sys
import random
import gmpy2

if os.name == 'nt':
    os.system('cls')
else:
    os.system('clear')
t = time.ctime()
sys.stdout.write(f"\033[?25l")
sys.stdout.write(f"\033[01;33m[+] Kangaroo: {t}\n")
sys.stdout.flush()

modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

# Define Point class
class Point:
    def __init__(self, x=0, y=0):
        self.x = gmpy2.mpz(x)
        self.y = gmpy2.mpz(y)

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

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

def mul2(P, p=modulo):
    if P == Z:
        return Z
    m = gmpy2.f_mod(3 * P.x * P.x * gmpy2.invert(2 * P.y, p), p)
    x = gmpy2.f_mod(m * m - 2 * P.x, p)
    y = gmpy2.f_mod(m * (P.x - x) - P.y, p)
    return Point(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")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            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(
                "\n-------------------------------------------------------------------------------------------------------------------------------------------\n"
            )
        file.close()
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    modulo_val = P.x % DP_rarity
    if modulo_val == 0:
        A.append(gmpy2.mpz(P.x))
        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(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two):
    solved = False
    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)]
    print('[+] tame and wild herds are prepared')
    Hops, Hops_old = 0, 0
    t0 = time.time()  

    # Memoization dictionary
    memo = {}

    while not solved:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            if pw not in memo:
                memo[pw] = powers_of_two[pw]
            dt[k] = memo[pw]
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved: break
            t[k] += dt[k]
            T[k] = add(P[int(pw)], T[k])
        if solved: break
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            if pw not in memo:
                memo[pw] = powers_of_two[pw]
            dw[k] = memo[pw]
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved: break
            w[k] += dw[k]
            W[k] = add(P[int(pw)], W[k])
        if solved: break
        t1 = time.time()
        if (t1 - t0) > 5:
            print('\r[+] Hops: %.0f h/s' % ((Hops - Hops_old) / (t1 - t0)), end='', flush=True)
            t0 = t1
            Hops_old = Hops
    print('[+] Hops:', Hops)
    return 'sol. time: %.2f sec' % (time.time() - starttime)

# Configuration for the puzzle
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = 4  
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 = [], [], []

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 = Point(X,Y)
starttime = oldtime = time.time()

print(f"[+] [Puzzle]: {puzzle}")
print(f"[+] [Lower range limit]: {lower_range_limit}")
print(f"[+] [Upper range limit]: {upper_range_limit}")

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

Hops = 0

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

solved = False
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two)

print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)))

• Kangaroo: Thu May 16 13:33:48 2024
• [Puzzle]: 40
• [Lower range limit]: 549755813888
• [Upper range limit]: 1099511627775
• [Random seed]: 9b76a9623bd76fb8cc
• P-table prepared
• tame and wild herds are prepared
• Hops: 205288 h/s
• total time: 6.92 sec
• PUZZLE SOLVED: Thu May 16 13:33:55 2024
• Private key (dec) : 1003651412950
• Hops: 1416585
• Average time to solve: 6.92 sec

It needs to be converted into C++ or Rust so that it can solve problems up to puzzle 120.

[krashfire]

i have created twist attack on ecdsa secp256k1.

can read about Twist Attack on ECDSA SECP256k1 here. https://github.com/demining/Twist-Attack

It gets the partial private key correctly.

my issue now is how to write the code to get to the full private key. PM Me Bruhhh.... im lost.

Code:

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from fastecdsa.keys import gen_private_key, get_public_key
from sympy import mod_inverse

# Generate a private key
private_key = gen_private_key(secp256k1)

# Get the corresponding public key
public_key = get_public_key(private_key, secp256k1)

# Print the private key and its bit length
print("Original Private Key:", hex(private_key))
print("Private Key Bit Length:", private_key.bit_length())

# Print the public key coordinates (x, y)
print("Original Public Key (x, y):", public_key.x, public_key.y)

# Twist Attack
n = secp256k1.q  # Order of the curve
Gx, Gy = public_key.x, public_key.y

# Calculate the twist point
twist_x = Gx
twist_y = (-Gy) % secp256k1.p
print("twist_y:", hex(twist_y))

# Perform twist attack to find the partial private key
partial_private_key = (twist_y * mod_inverse(Gy, n)) % n

# Print the partial private key and its bit length
print("Partial Private Key:", hex(partial_private_key))
print("Partial Private Key Bit Length:", partial_private_key.bit_length())

[greenAlien]

I have 205288 hops per second in python on single core my friend......

It will work from 1 - 256 bit . But it is impossible to solve any Puzzle above 50 with this for a lifetime.

Code:

import time
import os
import sys
import random
import gmpy2

if os.name == 'nt':
    os.system('cls')
else:
    os.system('clear')
t = time.ctime()
sys.stdout.write(f"\033[?25l")
sys.stdout.write(f"\033[01;33m[+] Kangaroo: {t}\n")
sys.stdout.flush()

modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

# Define Point class
class Point:
    def __init__(self, x=0, y=0):
        self.x = gmpy2.mpz(x)
        self.y = gmpy2.mpz(y)

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

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

def mul2(P, p=modulo):
    if P == Z:
        return Z
    m = gmpy2.f_mod(3 * P.x * P.x * gmpy2.invert(2 * P.y, p), p)
    x = gmpy2.f_mod(m * m - 2 * P.x, p)
    y = gmpy2.f_mod(m * (P.x - x) - P.y, p)
    return Point(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")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            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(
                "\n-------------------------------------------------------------------------------------------------------------------------------------------\n"
            )
        file.close()
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    modulo_val = P.x % DP_rarity
    if modulo_val == 0:
        A.append(gmpy2.mpz(P.x))
        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(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two):
    solved = False
    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)]
    print('[+] tame and wild herds are prepared')
    Hops, Hops_old = 0, 0
    t0 = time.time()  

    # Memoization dictionary
    memo = {}

    while not solved:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            if pw not in memo:
                memo[pw] = powers_of_two[pw]
            dt[k] = memo[pw]
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved: break
            t[k] += dt[k]
            T[k] = add(P[int(pw)], T[k])
        if solved: break
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            if pw not in memo:
                memo[pw] = powers_of_two[pw]
            dw[k] = memo[pw]
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved: break
            w[k] += dw[k]
            W[k] = add(P[int(pw)], W[k])
        if solved: break
        t1 = time.time()
        if (t1 - t0) > 5:
            print('\r[+] Hops: %.0f h/s' % ((Hops - Hops_old) / (t1 - t0)), end='', flush=True)
            t0 = t1
            Hops_old = Hops
    print('[+] Hops:', Hops)
    return 'sol. time: %.2f sec' % (time.time() - starttime)

# Configuration for the puzzle
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = 4  
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 = [], [], []

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 = Point(X,Y)
starttime = oldtime = time.time()

print(f"[+] [Puzzle]: {puzzle}")
print(f"[+] [Lower range limit]: {lower_range_limit}")
print(f"[+] [Upper range limit]: {upper_range_limit}")

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

Hops = 0

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

solved = False
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two)

print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)))

• Kangaroo: Thu May 16 13:33:48 2024
• [Puzzle]: 40
• [Lower range limit]: 549755813888
• [Upper range limit]: 1099511627775
• [Random seed]: 9b76a9623bd76fb8cc
• P-table prepared
• tame and wild herds are prepared
• Hops: 205288 h/s
• total time: 6.92 sec
• PUZZLE SOLVED: Thu May 16 13:33:55 2024
• Private key (dec) : 1003651412950
• Hops: 1416585
• Average time to solve: 6.92 sec

It needs to be converted into C++ or Rust so that it can solve problems up to puzzle 120.

not a bad working code! Are you thinking on implementing multi threading? I know this is not comparable with GPU but its not bad at all Congrats!

[COBRAS]

i have created twist attack on ecdsa secp256k1.

can read about Twist Attack on ECDSA SECP256k1 here. https://github.com/demining/Twist-Attack

It gets the partial private key correctly.

my issue now is how to write the code to get to the full private key. PM Me Bruhhh.... im lost.

Code:

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from fastecdsa.keys import gen_private_key, get_public_key
from sympy import mod_inverse

# Generate a private key
private_key = gen_private_key(secp256k1)

# Get the corresponding public key
public_key = get_public_key(private_key, secp256k1)

# Print the private key and its bit length
print("Original Private Key:", hex(private_key))
print("Private Key Bit Length:", private_key.bit_length())

# Print the public key coordinates (x, y)
print("Original Public Key (x, y):", public_key.x, public_key.y)

# Twist Attack
n = secp256k1.q  # Order of the curve
Gx, Gy = public_key.x, public_key.y

# Calculate the twist point
twist_x = Gx
twist_y = (-Gy) % secp256k1.p
print("twist_y:", hex(twist_y))

# Perform twist attack to find the partial private key
partial_private_key = (twist_y * mod_inverse(Gy, n)) % n

# Print the partial private key and its bit length
print("Partial Private Key:", hex(partial_private_key))
print("Partial Private Key Bit Length:", partial_private_key.bit_length())

Explain were you see partial privkey correctly ?

I not see any parts of privkey in partial privkey

ps as I know twist attack and defining twist,-attack he is bla bla bla about special base point or public keys I not remember this exact, but in your dcrypt you have only one possible twist point but attack and defining use many this points

[nomachine]

not a bad working code! Are you thinking on implementing multi threading? I know this is not comparable with GPU but its not bad at all Congrats!

Here you go

Code:

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()

• KANGAROO: Sat Jun 15 21:22:34 2024
• [Tame and Wild herds are prepared]
• [P-table prepared]
• [Using 12 CPU cores for parallel search]
• [Puzzle: 40]
• [Lower range limit: 549755813888]
• [Upper range limit: 1099511627775]
• [Expected Hops: 2^20.64 (1631201)]
• [Random seed: 0932dc777428d6f3b9]
• [Hops: 2^22.21 <-> 2443414 h/s] [00:00:02]
• total time: 2.18 sec
• PUZZLE SOLVED: Sat Jun 15 21:22:36 2024
• Private key (dec) : 1003651412950
• Hops: 5254560
• Average time to solve: 2.18 sec

But I won't give you false hope that this script can solve anything above 50 soon. It's simply beyond the reach of python's capabilities.

You have to program in C++ yourself if the current scripts do not meet your needs.

[nomachine]

Here is Kangaroo C++ in one single file:

kangaroo.cpp

Code:

#include <gmp.h>
#include <gmpxx.h>
#include <chrono>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
#include <set>

using namespace std;

typedef array<mpz_class, 2> Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

auto starttime = chrono::high_resolution_clock::now();

Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& Px = P[0];
    const mpz_class& Py = P[1];
    const mpz_class& Qx = Q[0];
    const mpz_class& Qy = Q[1];
    if (Px == Qx && (Py != Qy || Py == 0)) return Z;
    mpz_class m, num, denom, inv;
    if (Px == Qx) {
        num = 3 * Px * Px;
        denom = 2 * Py;
    } else {
        num = Qy - Py;
        denom = Qx - Px;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    m = (num * inv) % p;
    mpz_class x = (m * m - Px - Qx) % p;
    if (x < 0) x += p;
    mpz_class y = (m * (Px - x) - Py) % p;
    if (y < 0) y += p;
    return {x, y};
}

Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) {
    Point R = Z;
    Point current = P;
    mpz_class k_copy = k;
    while (k_copy > 0) {
        if (k_copy % 2 == 1) {
            R = add(R, current, p);
        }
        current = add(current, current, p);
        k_copy >>= 1;
    }
    return R;
}

mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity,
                std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W,
                const std::vector<mpz_class>& w) {
    if (P[0] % DP_rarity == 0) {
        T.push_back(P);
        t.push_back(Pindex);
        std::set<mpz_class> T_set;
        for (const auto& tp : T) T_set.insert(tp[0]);
        for (const auto& match : W) {
            auto it = find(T.begin(), T.end(), match);
            if (it != T.end()) {
                int index = distance(T.begin(), it);
                mpz_class tP = t[index];
                mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))];
                mpz_class dec = abs(tP - wP);
                auto end = chrono::system_clock::now();
                time_t end_time = chrono::system_clock::to_time_t(end);
                cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time)
                     << "\r";
                cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m"
                     << endl;
                ofstream file("KEYFOUNDKEYFOUND.txt", ios::app);
                file << "\n" << string(140, '-') << endl;
                file << "SOLVED " << ctime(&end_time);
                file << "Private Key (decimal): " << dec << endl;
                file << "Private Key (hex): " << dec.get_str(16) << endl;
                file << string(140, '-') << endl;
                file.close();
                return true;
            }
        }
    }
    return false;
}

vector<mpz_class> generate_powers_of_two(int hop_modulo) {
    vector<mpz_class> powers(hop_modulo);
    for (int pw = 0; pw < hop_modulo; ++pw) {
        powers[pw] = mpz_class(1) << pw;
    }
    return powers;
}

string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo,
              const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) {
    vector<Point> T(Nt, Z), W(Nw, Z);
    vector<mpz_class> t(Nt), w(Nw);

    gmp_randclass rand(gmp_randinit_default);

    for (int k = 0; k < Nt; ++k) {
        t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit);
        T[k] = mul(t[k]);
    }

    for (int k = 0; k < Nw; ++k) {
        w[k] = rand.get_z_range(upper_range_limit - lower_range_limit);
        W[k] = add(W0, mul(w[k]));
    }

    long long Hops = 0, Hops_old = 0;
    auto t0 = chrono::high_resolution_clock::now();
    vector<mpz_class> memo(hop_modulo);

    for (int pw = 0; pw < hop_modulo; ++pw) {
        memo[pw] = powers_of_two[pw];
    }

    bool solved = false;
    while (!solved) {
        for (int k = 0; k < (Nt + Nw); ++k) {
            ++Hops;
            if (k < Nt) {
                mpz_class pw = T[k][0] % hop_modulo;
                solved = comparator(T[k], t[k], DP_rarity, T, t, W, w);
                if (solved) break;
                t[k] += memo[pw.get_ui()];
                T[k] = add(P[pw.get_ui()], T[k], modulo);
            } else {
                int n = k - Nw;
                mpz_class pw = W[n][0] % hop_modulo;
                solved = comparator(W[n], w[n], DP_rarity, W, w, T, t);
                if (solved) break;
                w[n] += memo[pw.get_ui()];
                W[n] = add(P[pw.get_ui()], W[n], modulo);
            }
        }

        auto t1 = chrono::high_resolution_clock::now();
        double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count();
        if (elapsed_seconds > 1.0) {
            double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds;
            auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime);
            int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count();
            int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count();
            int seconds = (elapsed_time % chrono::minutes(1)).count();
            stringstream elapsed_time_str;
            elapsed_time_str << setfill('0') << setw(2) << hours << ":"
                             << setfill('0') << setw(2) << minutes << ":"
                             << setfill('0') << setw(2) << seconds;
            double p_2 = log2(Hops);
            cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) 
                 << hops_per_second << " h/s] ["
                 << elapsed_time_str.str() << "]" << flush;
            t0 = t1;
            Hops_old = Hops;
        }
    }

    cout << "\r[+] Hops: " << Hops << endl;
    auto end = chrono::high_resolution_clock::now();
    double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count();
    return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec";
}

int main() {
    int puzzle = 50;
    string compressed_public_key =
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6";
    int kangaroo_power = 6;
    mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1);
    mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;

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

    int Nt = 1 << kangaroo_power;
    int Nw = 1 << kangaroo_power;

    vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);

    mpz_class X, Y;
    if (compressed_public_key.length() == 66) {
        X = mpz_class(compressed_public_key.substr(2), 16);
        Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2);
    } else {
        cout << "[error] pubkey len(66/130) invalid!" << endl;
        return 1;
    }

    Point W0 = {X, Y};
    auto starttime = chrono::high_resolution_clock::now();
    time_t currentTime = time(nullptr);
    cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(&currentTime) << "\033[0m" << "\r";
    cout << "[+] [Puzzle]: " << puzzle << endl;
    cout << "[+] [Lower range limit]: " << lower_range_limit << endl;
    cout << "[+] [Upper range limit]: " << upper_range_limit << endl;
    cout << "[+] [EC Point Coordinate X]: " << X << endl;
    cout << "[+] [EC Point Coordinate Y]: " << Y << endl;
    mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1));
    double log_expected_hops = log2(expected_hops.get_d());
    cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) 
            << log_expected_hops << " (" << expected_hops << ")]" << endl;

    vector<Point> P = {PG};
    P.reserve(256);
    for (int k = 0; k < 255; ++k) {
        P.push_back(add(P[k], P[k]));
    }

    unsigned long seed = static_cast<unsigned long>(time(nullptr));
    gmp_randclass rand(gmp_randinit_default);
    rand.seed(seed);

    search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);

    cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;

    return 0;
}

Build command:

Code:

g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -lgmp -lgmpxx 

#./kangaroo

• KANGAROO: Wed Jul 17 20:26:11 2024
• [Puzzle]: 50
• [Lower range limit]: 562949953421312
• [Upper range limit]: 1125899906842623
• [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
• [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
• [Expected Hops: 2^25.50 (47453132)]
• [Hops: 2^24.81 <-> 460999 h/s] [00:01:04]
• PUZZLE SOLVED: Wed Jul 17 20:27:15 2024
• Private key (dec): 611140496167764
• Hops: 29560288
• Average time to solve: 64 sec

More than 460K hops per second on a single core.

[COBRAS]

Here is Kangaroo C++ in one single file:

kangaroo.cpp

Code:

#include <gmp.h>
#include <gmpxx.h>
#include <chrono>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
#include <set>

using namespace std;

typedef array<mpz_class, 2> Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

auto starttime = chrono::high_resolution_clock::now();

Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& Px = P[0];
    const mpz_class& Py = P[1];
    const mpz_class& Qx = Q[0];
    const mpz_class& Qy = Q[1];
    if (Px == Qx && (Py != Qy || Py == 0)) return Z;
    mpz_class m, num, denom, inv;
    if (Px == Qx) {
        num = 3 * Px * Px;
        denom = 2 * Py;
    } else {
        num = Qy - Py;
        denom = Qx - Px;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    m = (num * inv) % p;
    mpz_class x = (m * m - Px - Qx) % p;
    if (x < 0) x += p;
    mpz_class y = (m * (Px - x) - Py) % p;
    if (y < 0) y += p;
    return {x, y};
}

Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) {
    Point R = Z;
    Point current = P;
    mpz_class k_copy = k;
    while (k_copy > 0) {
        if (k_copy % 2 == 1) {
            R = add(R, current, p);
        }
        current = add(current, current, p);
        k_copy >>= 1;
    }
    return R;
}

mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity,
                std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W,
                const std::vector<mpz_class>& w) {
    if (P[0] % DP_rarity == 0) {
        T.push_back(P);
        t.push_back(Pindex);
        std::set<mpz_class> T_set;
        for (const auto& tp : T) T_set.insert(tp[0]);
        for (const auto& match : W) {
            auto it = find(T.begin(), T.end(), match);
            if (it != T.end()) {
                int index = distance(T.begin(), it);
                mpz_class tP = t[index];
                mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))];
                mpz_class dec = abs(tP - wP);
                auto end = chrono::system_clock::now();
                time_t end_time = chrono::system_clock::to_time_t(end);
                cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time)
                     << "\r";
                cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m"
                     << endl;
                ofstream file("KEYFOUNDKEYFOUND.txt", ios::app);
                file << "\n" << string(140, '-') << endl;
                file << "SOLVED " << ctime(&end_time);
                file << "Private Key (decimal): " << dec << endl;
                file << "Private Key (hex): " << dec.get_str(16) << endl;
                file << string(140, '-') << endl;
                file.close();
                return true;
            }
        }
    }
    return false;
}

vector<mpz_class> generate_powers_of_two(int hop_modulo) {
    vector<mpz_class> powers(hop_modulo);
    for (int pw = 0; pw < hop_modulo; ++pw) {
        powers[pw] = mpz_class(1) << pw;
    }
    return powers;
}

string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo,
              const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) {
    vector<Point> T(Nt, Z), W(Nw, Z);
    vector<mpz_class> t(Nt), w(Nw);

    gmp_randclass rand(gmp_randinit_default);

    for (int k = 0; k < Nt; ++k) {
        t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit);
        T[k] = mul(t[k]);
    }

    for (int k = 0; k < Nw; ++k) {
        w[k] = rand.get_z_range(upper_range_limit - lower_range_limit);
        W[k] = add(W0, mul(w[k]));
    }

    long long Hops = 0, Hops_old = 0;
    auto t0 = chrono::high_resolution_clock::now();
    vector<mpz_class> memo(hop_modulo);

    for (int pw = 0; pw < hop_modulo; ++pw) {
        memo[pw] = powers_of_two[pw];
    }

    bool solved = false;
    while (!solved) {
        for (int k = 0; k < (Nt + Nw); ++k) {
            ++Hops;
            if (k < Nt) {
                mpz_class pw = T[k][0] % hop_modulo;
                solved = comparator(T[k], t[k], DP_rarity, T, t, W, w);
                if (solved) break;
                t[k] += memo[pw.get_ui()];
                T[k] = add(P[pw.get_ui()], T[k], modulo);
            } else {
                int n = k - Nw;
                mpz_class pw = W[n][0] % hop_modulo;
                solved = comparator(W[n], w[n], DP_rarity, W, w, T, t);
                if (solved) break;
                w[n] += memo[pw.get_ui()];
                W[n] = add(P[pw.get_ui()], W[n], modulo);
            }
        }

        auto t1 = chrono::high_resolution_clock::now();
        double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count();
        if (elapsed_seconds > 1.0) {
            double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds;
            auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime);
            int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count();
            int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count();
            int seconds = (elapsed_time % chrono::minutes(1)).count();
            stringstream elapsed_time_str;
            elapsed_time_str << setfill('0') << setw(2) << hours << ":"
                             << setfill('0') << setw(2) << minutes << ":"
                             << setfill('0') << setw(2) << seconds;
            double p_2 = log2(Hops);
            cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) 
                 << hops_per_second << " h/s] ["
                 << elapsed_time_str.str() << "]" << flush;
            t0 = t1;
            Hops_old = Hops;
        }
    }

    cout << "\r[+] Hops: " << Hops << endl;
    auto end = chrono::high_resolution_clock::now();
    double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count();
    return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec";
}

int main() {
    int puzzle = 50;
    string compressed_public_key =
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6";
    int kangaroo_power = 6;
    mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1);
    mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;

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

    int Nt = 1 << kangaroo_power;
    int Nw = 1 << kangaroo_power;

    vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);

    mpz_class X, Y;
    if (compressed_public_key.length() == 66) {
        X = mpz_class(compressed_public_key.substr(2), 16);
        Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2);
    } else {
        cout << "[error] pubkey len(66/130) invalid!" << endl;
        return 1;
    }

    Point W0 = {X, Y};
    auto starttime = chrono::high_resolution_clock::now();
    time_t currentTime = time(nullptr);
    cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(&currentTime) << "\033[0m" << "\r";
    cout << "[+] [Puzzle]: " << puzzle << endl;
    cout << "[+] [Lower range limit]: " << lower_range_limit << endl;
    cout << "[+] [Upper range limit]: " << upper_range_limit << endl;
    cout << "[+] [EC Point Coordinate X]: " << X << endl;
    cout << "[+] [EC Point Coordinate Y]: " << Y << endl;
    mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1));
    double log_expected_hops = log2(expected_hops.get_d());
    cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) 
            << log_expected_hops << " (" << expected_hops << ")]" << endl;

    vector<Point> P = {PG};
    P.reserve(256);
    for (int k = 0; k < 255; ++k) {
        P.push_back(add(P[k], P[k]));
    }

    unsigned long seed = static_cast<unsigned long>(time(nullptr));
    gmp_randclass rand(gmp_randinit_default);
    rand.seed(seed);

    search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);

    cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;

    return 0;
}

Build command:

Code:

g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -lgmp -lgmpxx 

#./kangaroo

• KANGAROO: Wed Jul 17 20:26:11 2024
• [Puzzle]: 50
• [Lower range limit]: 562949953421312
• [Upper range limit]: 1125899906842623
• [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
• [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
• [Expected Hops: 2^25.50 (47453132)]
• [Hops: 2^24.81 <-> 460999 h/s] [00:01:04]
• PUZZLE SOLVED: Wed Jul 17 20:27:15 2024
• Private key (dec): 611140496167764
• Hops: 29560288
• Average time to solve: 64 sec

More than 460K hops per second on a single core.

Hi bro. Send me please info what you promise ?

[greenAlien]

Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.

I have tried to port your version but some libraries are missing for macOS thats a pity.

[nomachine]

Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.

I have tried to port your version but some libraries are missing for macOS thats a pity.

kangaroo.cpp

Code:

#include <gmp.h>
#include <gmpxx.h>
#include <chrono>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
#include <array>
#include <set>
#include <sstream>

using namespace std;

typedef array<mpz_class, 2> Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

auto starttime = chrono::high_resolution_clock::now();

Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& P0 = P[0];
    const mpz_class& P1 = P[1];
    const mpz_class& Q0 = Q[0];
    const mpz_class& Q1 = Q[1];
    mpz_class lmbda, num, denom, inv;
    if (P != Q) {
        num = Q1 - P1;
        denom = Q0 - P0;
    } else {
        if (P1 == 0) return Z;
        num = 3 * P0 * P0;
        denom = 2 * P1;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    lmbda = (num * inv) % p;
    mpz_class x = (lmbda * lmbda - P0 - Q0) % p;
    if (x < 0) x += p;
    mpz_class y = (lmbda * (P0 - x) - P1) % p;
    if (y < 0) y += p;
    return {x, y};
}

Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) {
    Point R = Z;
    Point current = P;
    mpz_class k_copy = k;
    while (k_copy > 0) {
        if (k_copy % 2 == 1) {
            R = add(R, current, p);
        }
        current = add(current, current, p);
        k_copy >>= 1;
    }
    return R;
}

mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity,
                std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W,
                const std::vector<mpz_class>& w) {
    mpz_class result;
    mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t());
   
    if (result != 0) return false;

    T.push_back(P);
    t.push_back(Pindex);

    // Create a set of Points from T for fast lookup
    std::set<Point> T_set(T.begin(), T.end());

    // Create a set of Points from W for quick existence check
    std::set<Point> W_set(W.begin(), W.end());

    // Iterate through W and check if each element is in T
    for (const auto& match : W_set) {
        if (T_set.find(match) != T_set.end()) {
            auto it = find(T.begin(), T.end(), match);
            int index = distance(T.begin(), it);
            mpz_class tP = t[index];
            mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))];
            mpz_class dec = abs(tP - wP);

            // Measure time once and reuse it
            auto end = chrono::system_clock::now();
            time_t end_time = chrono::system_clock::to_time_t(end);
            cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r";
            cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;

            // Open file once, write all data, and close it
            static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app);
            file << "\n" << string(140, '-') << endl;
            file << "SOLVED " << ctime(&end_time);
            file << "Private Key (decimal): " << dec << endl;
            file << "Private Key (hex): " << dec.get_str(16) << endl;
            file << string(140, '-') << endl;

            return true;
        }
    }

    return false;
}


vector<mpz_class> generate_powers_of_two(int hop_modulo) {
    vector<mpz_class> powers(hop_modulo);
    for (int pw = 0; pw < hop_modulo; ++pw) {
        powers[pw] = mpz_class(1) << pw;
    }
    return powers;
}

string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo,
              const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& 
powers_of_two) {
    vector<Point> T(Nt, Z), W(Nw, Z);
    vector<mpz_class> t(Nt), w(Nw);

    gmp_randclass rand(gmp_randinit_default);

    for (int k = 0; k < Nt; ++k) {
        t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit);
        T[k] = mul(t[k]);
    }

    for (int k = 0; k < Nw; ++k) {
        w[k] = rand.get_z_range(upper_range_limit - lower_range_limit);
        W[k] = add(W0, mul(w[k]));
    }

    long long Hops = 0, Hops_old = 0;
    auto t0 = chrono::high_resolution_clock::now();
    vector<mpz_class> memo(hop_modulo);

    for (int pw = 0; pw < hop_modulo; ++pw) {
        memo[pw] = powers_of_two[pw];
    }

    bool solved = false;
    while (!solved) {
        for (int k = 0; k < (Nt + Nw); ++k) {
            ++Hops;
            if (k < Nt) {
                mpz_class pw = T[k][0] % hop_modulo;
                solved = comparator(T[k], t[k], DP_rarity, T, t, W, w);
                if (solved) break;
                t[k] += memo[pw.get_ui()];
                T[k] = add(P[pw.get_ui()], T[k], modulo);
            } else {
                int n = k - Nw;
                mpz_class pw = W[n][0] % hop_modulo;
                solved = comparator(W[n], w[n], DP_rarity, W, w, T, t);
                if (solved) break;
                w[n] += memo[pw.get_ui()];
                W[n] = add(P[pw.get_ui()], W[n], modulo);
            }
        }

        auto t1 = chrono::high_resolution_clock::now();
        double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count();
        if (elapsed_seconds > 1.0) {
            double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds;
            auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime);
            int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count();
            int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count();
            int seconds = (elapsed_time % chrono::minutes(1)).count();
            stringstream elapsed_time_str;
            elapsed_time_str << setfill('0') << setw(2) << hours << ":"
                             << setfill('0') << setw(2) << minutes << ":"
                             << setfill('0') << setw(2) << seconds;
            double p_2 = log2(Hops);
            cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0)
                 << hops_per_second << " h/s] ["
                 << elapsed_time_str.str() << "]" << flush;
            t0 = t1;
            Hops_old = Hops;
        }
    }

    cout << "\r[+] Hops: " << Hops << endl;
    auto end = chrono::high_resolution_clock::now();
    double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count();
    return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec";
}

int main() {
    int puzzle = 50;
    string compressed_public_key =
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6";
    int kangaroo_power = 6;
    mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1);
    mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;

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

    int Nt = 1 << kangaroo_power;
    int Nw = 1 << kangaroo_power;

    vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);

    mpz_class X, Y;
    if (compressed_public_key.length() == 66) {
        X = mpz_class(compressed_public_key.substr(2), 16);
        Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2);
    } else {
        cout << "[error] pubkey len(66/130) invalid!" << endl;
        return 1;
    }

    Point W0 = {X, Y};
    auto starttime = chrono::high_resolution_clock::now();
    time_t currentTime = time(nullptr);
    cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(&currentTime) << "\033[0m" << "\r";
    cout << "[+] [Puzzle]: " << puzzle << endl;
    cout << "[+] [Lower range limit]: " << lower_range_limit << endl;
    cout << "[+] [Upper range limit]: " << upper_range_limit << endl;
    cout << "[+] [EC Point Coordinate X]: " << X << endl;
    cout << "[+] [EC Point Coordinate Y]: " << Y << endl;
    mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1));
    double log_expected_hops = log2(expected_hops.get_d());
    cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2)
            << log_expected_hops << " (" << expected_hops << ")]" << endl;

    vector<Point> P = {PG};
    P.reserve(256);
    for (int k = 0; k < 255; ++k) {
        P.push_back(add(P[k], P[k]));
    }

    unsigned long seed = static_cast<unsigned long>(time(nullptr));
    gmp_randclass rand(gmp_randinit_default);
    rand.seed(seed);

    search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);

    cout << "\r[+] Average time to solve: " << 
chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;

    return 0;
}

Code:

clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx

nomachine@iMac Desktop % system_profiler SPSoftwareDataType
Software:

    System Software Overview:

      System Version: macOS 13.6.1 (22G313)
      Kernel Version: Darwin 22.6.0
      Boot Volume: macOS
      Boot Mode: Normal
      User Name: nomachine (nomachine)
      Secure Virtual Memory: Enabled
      System Integrity Protection: Enabled
      Time since boot: 1 day, 14 hours, 11 minutes

nomachine@iMac Desktop % nano kangaroo.cpp
nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx
nomachine@iMac Desktop % ./kangaroo

• KANGAROO: Tue Jul 23 08:50:41 2024
• [Puzzle]: 50
• [Lower range limit]: 562949953421312
• [Upper range limit]: 1125899906842623
• [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
• [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
• [Expected Hops: 2^25.50 (47453132)]
• [Hops: 2^24.82 <-> 469162 h/s] [00:01:03]
• PUZZLE SOLVED: Tue Jul 23 08:51:44 2024
• Private key (dec): 611140496167764
• Hops: 29560288
• Average time to solve: 63 sec

[greenAlien]

Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.

I have tried to port your version but some libraries are missing for macOS thats a pity.

kangaroo.cpp

Code:

#include <gmp.h>
#include <gmpxx.h>
#include <chrono>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
#include <array>
#include <set>
#include <sstream>

using namespace std;

typedef array<mpz_class, 2> Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

auto starttime = chrono::high_resolution_clock::now();

Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& P0 = P[0];
    const mpz_class& P1 = P[1];
    const mpz_class& Q0 = Q[0];
    const mpz_class& Q1 = Q[1];
    mpz_class lmbda, num, denom, inv;
    if (P != Q) {
        num = Q1 - P1;
        denom = Q0 - P0;
    } else {
        if (P1 == 0) return Z;
        num = 3 * P0 * P0;
        denom = 2 * P1;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    lmbda = (num * inv) % p;
    mpz_class x = (lmbda * lmbda - P0 - Q0) % p;
    if (x < 0) x += p;
    mpz_class y = (lmbda * (P0 - x) - P1) % p;
    if (y < 0) y += p;
    return {x, y};
}

Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) {
    Point R = Z;
    Point current = P;
    mpz_class k_copy = k;
    while (k_copy > 0) {
        if (k_copy % 2 == 1) {
            R = add(R, current, p);
        }
        current = add(current, current, p);
        k_copy >>= 1;
    }
    return R;
}

mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity,
                std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W,
                const std::vector<mpz_class>& w) {
    mpz_class result;
    mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t());
   
    if (result != 0) return false;

    T.push_back(P);
    t.push_back(Pindex);

    // Create a set of Points from T for fast lookup
    std::set<Point> T_set(T.begin(), T.end());

    // Create a set of Points from W for quick existence check
    std::set<Point> W_set(W.begin(), W.end());

    // Iterate through W and check if each element is in T
    for (const auto& match : W_set) {
        if (T_set.find(match) != T_set.end()) {
            auto it = find(T.begin(), T.end(), match);
            int index = distance(T.begin(), it);
            mpz_class tP = t[index];
            mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))];
            mpz_class dec = abs(tP - wP);

            // Measure time once and reuse it
            auto end = chrono::system_clock::now();
            time_t end_time = chrono::system_clock::to_time_t(end);
            cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r";
            cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;

            // Open file once, write all data, and close it
            static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app);
            file << "\n" << string(140, '-') << endl;
            file << "SOLVED " << ctime(&end_time);
            file << "Private Key (decimal): " << dec << endl;
            file << "Private Key (hex): " << dec.get_str(16) << endl;
            file << string(140, '-') << endl;

            return true;
        }
    }

    return false;
}


vector<mpz_class> generate_powers_of_two(int hop_modulo) {
    vector<mpz_class> powers(hop_modulo);
    for (int pw = 0; pw < hop_modulo; ++pw) {
        powers[pw] = mpz_class(1) << pw;
    }
    return powers;
}

string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo,
              const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& 
powers_of_two) {
    vector<Point> T(Nt, Z), W(Nw, Z);
    vector<mpz_class> t(Nt), w(Nw);

    gmp_randclass rand(gmp_randinit_default);

    for (int k = 0; k < Nt; ++k) {
        t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit);
        T[k] = mul(t[k]);
    }

    for (int k = 0; k < Nw; ++k) {
        w[k] = rand.get_z_range(upper_range_limit - lower_range_limit);
        W[k] = add(W0, mul(w[k]));
    }

    long long Hops = 0, Hops_old = 0;
    auto t0 = chrono::high_resolution_clock::now();
    vector<mpz_class> memo(hop_modulo);

    for (int pw = 0; pw < hop_modulo; ++pw) {
        memo[pw] = powers_of_two[pw];
    }

    bool solved = false;
    while (!solved) {
        for (int k = 0; k < (Nt + Nw); ++k) {
            ++Hops;
            if (k < Nt) {
                mpz_class pw = T[k][0] % hop_modulo;
                solved = comparator(T[k], t[k], DP_rarity, T, t, W, w);
                if (solved) break;
                t[k] += memo[pw.get_ui()];
                T[k] = add(P[pw.get_ui()], T[k], modulo);
            } else {
                int n = k - Nw;
                mpz_class pw = W[n][0] % hop_modulo;
                solved = comparator(W[n], w[n], DP_rarity, W, w, T, t);
                if (solved) break;
                w[n] += memo[pw.get_ui()];
                W[n] = add(P[pw.get_ui()], W[n], modulo);
            }
        }

        auto t1 = chrono::high_resolution_clock::now();
        double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count();
        if (elapsed_seconds > 1.0) {
            double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds;
            auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime);
            int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count();
            int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count();
            int seconds = (elapsed_time % chrono::minutes(1)).count();
            stringstream elapsed_time_str;
            elapsed_time_str << setfill('0') << setw(2) << hours << ":"
                             << setfill('0') << setw(2) << minutes << ":"
                             << setfill('0') << setw(2) << seconds;
            double p_2 = log2(Hops);
            cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0)
                 << hops_per_second << " h/s] ["
                 << elapsed_time_str.str() << "]" << flush;
            t0 = t1;
            Hops_old = Hops;
        }
    }

    cout << "\r[+] Hops: " << Hops << endl;
    auto end = chrono::high_resolution_clock::now();
    double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count();
    return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec";
}

int main() {
    int puzzle = 50;
    string compressed_public_key =
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6";
    int kangaroo_power = 6;
    mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1);
    mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;

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

    int Nt = 1 << kangaroo_power;
    int Nw = 1 << kangaroo_power;

    vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);

    mpz_class X, Y;
    if (compressed_public_key.length() == 66) {
        X = mpz_class(compressed_public_key.substr(2), 16);
        Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2);
    } else {
        cout << "[error] pubkey len(66/130) invalid!" << endl;
        return 1;
    }

    Point W0 = {X, Y};
    auto starttime = chrono::high_resolution_clock::now();
    time_t currentTime = time(nullptr);
    cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(&currentTime) << "\033[0m" << "\r";
    cout << "[+] [Puzzle]: " << puzzle << endl;
    cout << "[+] [Lower range limit]: " << lower_range_limit << endl;
    cout << "[+] [Upper range limit]: " << upper_range_limit << endl;
    cout << "[+] [EC Point Coordinate X]: " << X << endl;
    cout << "[+] [EC Point Coordinate Y]: " << Y << endl;
    mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1));
    double log_expected_hops = log2(expected_hops.get_d());
    cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2)
            << log_expected_hops << " (" << expected_hops << ")]" << endl;

    vector<Point> P = {PG};
    P.reserve(256);
    for (int k = 0; k < 255; ++k) {
        P.push_back(add(P[k], P[k]));
    }

    unsigned long seed = static_cast<unsigned long>(time(nullptr));
    gmp_randclass rand(gmp_randinit_default);
    rand.seed(seed);

    search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);

    cout << "\r[+] Average time to solve: " << 
chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;

    return 0;
}

Code:

clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx

nomachine@iMac Desktop % system_profiler SPSoftwareDataType
Software:

    System Software Overview:

      System Version: macOS 13.6.1 (22G313)
      Kernel Version: Darwin 22.6.0
      Boot Volume: macOS
      Boot Mode: Normal
      User Name: nomachine (nomachine)
      Secure Virtual Memory: Enabled
      System Integrity Protection: Enabled
      Time since boot: 1 day, 14 hours, 11 minutes

nomachine@iMac Desktop % nano kangaroo.cpp
nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx
nomachine@iMac Desktop % ./kangaroo

• KANGAROO: Tue Jul 23 08:50:41 2024
• [Puzzle]: 50
• [Lower range limit]: 562949953421312
• [Upper range limit]: 1125899906842623
• [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
• [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
• [Expected Hops: 2^25.50 (47453132)]
• [Hops: 2^24.82 <-> 469162 h/s] [00:01:03]
• PUZZLE SOLVED: Tue Jul 23 08:51:44 2024
• Private key (dec): 611140496167764
• Hops: 29560288
• Average time to solve: 63 sec

It works like a champ! I could solve it in 55 secs using a M1 Pro. I guess this is only using one thread, did you try with multithreading? The M processors are doing some voodoo magic when using multi threading