Pollard's kangaroo ECDLP solver

[marioantonini]

yes, my question was to understand exactly how long it takes for those who use kangaroo to find a priv key starting from the public one, with respect to the respective puzzles. For example

Puzzle 66 :   20000000000000000 -  3ffffffffffffffff
Puzzle 71 : 400000000000000000 - 7fffffffffffffffff
Puzzle 76 :  8000000000000000000 - fffffffffffffffffff
Puzzle 81:   100000000000000000000 to  1ffffffffffffffffffff

can someone who uses kangaroo give me an exact idea of ​​the times it takes with an nvidia tesla 100? Tnx

[1714485301]

1714485301

[1714485301]

1714485301

[1714485301]

1714485301

[nomachine]

Code:

import time
import os
import sys
import random
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
from multiprocessing import Pool, cpu_count

modulo = gmpy2.mpz(115792089237316195423570985008687907853269984665640564039457584007908834671663)
order = gmpy2.mpz(115792089237316195423570985008687907852837564279074904382605163141518161494337)
Gx = gmpy2.mpz(55066263022277343669578718895168534326250603453777594175500187360389116729240)
Gy = gmpy2.mpz(32670510020758816978083085130507043184471273380659243275938904335757337482424)

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

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

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y

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

P = compute_P_table()

os.system('clear')
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds is being prepared" + "\n")
sys.stdout.flush()

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)))
        print('total time: %.2f sec' % (time.time() - starttime))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference  # Convert to a hexadecimal string
        t = time.ctime()
        print('SOLVED:', t, difference)
        with open("KEYFOUNDKEYFOUND.txt", 'a') as file:
            file.write('\n\nSOLVED ' + t)
            file.write('\nPrivate Key (decimal): ' + str(difference))
            file.write('\nPrivate Key (hex): ' + HEX)
            file.write('\n-------------------------------------------------------------------------------------------------------------------------------------\n')
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message)
        sys.stdout.flush()
        return comparator(A, Ak, B, Bk)
    else:
        return False

# Memoization for ecmultiply
ecmultiply_memo = {}

def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))

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

def search(Nt, Nw, puzzle, kangoo_power, starttime):
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (1 << (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

puzzle = 50
compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
kangoo_power = 10 #For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2 ** kangoo_power
X = int(compressed_public_key, 16)
Y = X2Y(X % (2 ** 256), X >> 256)
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

for k in range(N_tests):
    buffer_size = 1024 * 1024 * 1024  # 1024 MB in bytes
    with open("tame.txt", 'w', buffering=buffer_size) as tame_file, open("wild.txt", 'w', buffering=buffer_size) as wild_file:
        tame_file.write('')
        wild_file.write('')

def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count)
    pool.close()
    pool.join()
    return results

if __name__ == '__main__':
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

Fri Sep  8 21:52:03 2023
P-table prepared
tame and wild herds is being prepared
Using 4 CPU cores for parallel search.
Public key: 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6 total time: 246.94 sec
SOLVED: Fri Sep  8 21:56:10 2023 -611140496167764

Puzzle 50 solved for 246 seconds....


SOLVED Fri Sep  8 21:56:10 2023
Private Key (decimal): -611140496167764
Private Key (hex): -0000000000000000000000000000000000000000000000000022bd43c2e9354
---------------------------------------------------------------------------------------------------------------

[ecdsa123]

in this example (python kangaroo parallel) :

with 4 cpu after changing little the code I have 73 second on laptop with Intel i5 for 2**50

you have "mismash" in code, you need clean code and rewrite

[nomachine]

in this example (python kangaroo parallel) :

with 4 cpu after changing little the code I have 73 second on laptop with Intel i5 for 2**50

you have "mismash" in code, you need clean code and rewrite

I updated the code to read and write "tame.txt &  "wild.txt" files faster with buffering.
Entered the coordinates X, Y to show at start...etc...

I still don't have a time under 100 seconds for 2**50.

Can you show me where the "mismash" in code is?

Thanks in advance!

Code:

import time
import os
import sys
import io
import random
import math
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
from multiprocessing import Pool, cpu_count

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


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y


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


def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y


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


P = compute_P_table()

os.system("clear")
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write("################################################" + "\n")
sys.stdout.write("Pollard-kangaroo PrivKey Recovery Tool multicore" + "\n")
sys.stdout.write("################################################" + "\n")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds kangaroos is being prepared" + "\n")
sys.stdout.flush()


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)))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference  # Convert to a hexadecimal string
        t = time.ctime()
        total_time = time.time() - starttime
        print("\033[01;33mSOLVED:", t, f"total time: {total_time:.2f} sec", HEX, "\n")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nSOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write("\nPrivate Key (decimal): " + str(difference))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------\n"
            )
        return True
    else:
        return False


# Batch writing function
def batch_write_data_to_file(data, file_path, batch_size=5000):
    with open(file_path, "a", buffering=1024 * 1024 * 1024) as fp:
        for i in range(0, len(data), batch_size):
            batch = data[i : i + batch_size]
            fp.writelines(batch)


# Function to check and write data to file
def check(
    P, Pindex, DP_rarity, file2save, A, Ak, B, Bk, buffer_size=1024 * 1024 * 1024
):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        data_to_write = ["%064x %d\n" % (P.x, Pindex)]
        batch_write_data_to_file(data_to_write, file2save)  # Batch write data to file
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message + "\r")
        sys.stdout.flush()
        return comparator(A, Ak, B, Bk)
    else:
        return False


def save2file(path, mode, data, buffer_size=1024 * 1024 * 1024):
    with open(path, mode, encoding="utf-8") as fp:
        if isinstance(data, (list, tuple, dict, set)):
            for line in data:
                if isinstance(line, str):
                    fp.write(line)
                elif isinstance(line, int):
                    fp.write(str(line))
        elif isinstance(data, (str, int)):
            fp.write(str(data))


# Memoization for ecmultiply
ecmultiply_memo = {}


def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))


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


def search(Nt, Nw, puzzle, kangoo_power, starttime):
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])


puzzle = 50
compressed_public_key = (
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
)
kangoo_power = 11  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2**kangoo_power
# check format pubkey
if len(compressed_public_key) == 66:
    X = int(compressed_public_key[2:66], 16)
    # calculation Y from X if pubkey is compressed
    Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2)
else:
    print("[error] pubkey len(66/130) invalid!")

print(f"[Puzzle]: {puzzle}")
print("[Xcoordinate]: %064x" % X)
print("[Ycoordinate]: %064x" % Y)

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

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

for k in range(N_tests):
    # Create empty 'tame.txt' and 'wild.txt' files for each iteration
    save2file("tame.txt", "w", "")
    save2file("wild.txt", "w", "")


def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(
        search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count
    )
    pool.close()
    pool.join()
    return results


if __name__ == "__main__":
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

[ecdsa123]

Little explanation.
I have at the moment no time for writing for you all code. ( you should write thread in search def)
read carefullty the change implement by me

Code:

import sys
import io
import random
import math
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
from multiprocessing import Pool, cpu_count

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


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y


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


def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y


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


P = compute_P_table()

os.system("clear")
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write("################################################" + "\n")
sys.stdout.write("Pollard-kangaroo PrivKey Recovery Tool multicore" + "\n")
sys.stdout.write("################################################" + "\n")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds kangaroos is being prepared" + "\n")
sys.stdout.flush()


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)))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference  # Convert to a hexadecimal string
        t = time.ctime()
        total_time = time.time() - starttime
        print("\033[01;33mSOLVED:", t, f"total time: {total_time:.2f} sec", HEX, "\n")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nSOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write("\nPrivate Key (decimal): " + str(difference))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------\n"
            )

    return result

    """        
        return True
    else:
        return False
    """

# Batch writing function
def batch_write_data_to_file(data, file_path, batch_size=5000):
    with open(file_path, "a", buffering=1024 * 1024 * 1024) as fp:
        for i in range(0, len(data), batch_size):
            batch = data[i : i + batch_size]
            fp.writelines(batch)


# Function to check and write data to file
def check(
    P, Pindex, DP_rarity, file2save, A, Ak, B, Bk, buffer_size=1024 * 1024 * 1024
):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        data_to_write = ["%064x %d\n" % (P.x, Pindex)]
        ## YOU DONT USE TAME AND WILD IN SCRIPT! SO FOR WHAT IMPLEMENT IT? IT TAKING TIME AND MEMORY
        """
        batch_write_data_to_file(data_to_write, file2save)  # Batch write data to file
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message + "\r")
        sys.stdout.flush()
        """ 
        return comparator(A, Ak, B, Bk)
    else:
        return False


def save2file(path, mode, data, buffer_size=1024 * 1024 * 1024):
    with open(path, mode, encoding="utf-8") as fp:
        if isinstance(data, (list, tuple, dict, set)):
            for line in data:
                if isinstance(line, str):
                    fp.write(line)
                elif isinstance(line, int):
                    fp.write(str(line))
        elif isinstance(data, (str, int)):
            fp.write(str(data))


# Memoization for ecmultiply
ecmultiply_memo = {}


def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))


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


def search(Nt, Nw, puzzle, kangoo_power, starttime):
    # NOT NECESSARY - TAKING TIME AS MULTIPLY BY PROCESS -> THING AS MINIMALISED TIME FOR OPERATION -> BETTER JOIN FOR ALL PROCESSING Moved !
    """
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    """
    
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
        
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    
    #oldtime = time.time()  -> NOT USING TAKING TIME
    Hops, Hops_old = 0, 0
    #t0 = time.time()         -> NOT USING TAKING TIME
    oldtime = time.time()
    starttime = oldtime
    while True:
        # THIS FUNCTION CHANGE FOR THREAD
        
        #THREAD ONE
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        
        #THREAD 2    
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

# DATA SETS AND IMPORTANT INFORMATION -> THINK ABOUT IT AS MINIMALISED OPERATION. 

puzzle = 50
compressed_public_key = (
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
)
kangoo_power = 10  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2**kangoo_power

# MOVED FROM SEARCH DEF
DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
hop_modulo = ((puzzle - 1) // 2) + kangoo_power
T, t, dt = [], [], []
W, w, dw = [], [], []

for k in range(Nt):
    t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
    T.append(mulk(t[k]))
    dt.append(0)
    
# check format pubkey
if len(compressed_public_key) == 66:
    X = int(compressed_public_key[2:66], 16)
    # calculation Y from X if pubkey is compressed
    Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2)
else:
    print("[error] pubkey len(66/130) invalid!")

print(f"[Puzzle]: {puzzle}")
print("[Xcoordinate]: %064x" % X)
print("[Ycoordinate]: %064x" % Y)

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

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

## YOU DONT USE TAME AND WILD IN SCRIPT! SO FOR WHAT IMPLEMENT IT? IT TAKING TIME AND MEMORY
"""
for k in range(N_tests):
    # Create empty 'tame.txt' and 'wild.txt' files for each iteration
    save2file("tame.txt", "w", "")
    save2file("wild.txt", "w", "")
"""

def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(
        search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count
    )
    pool.close()
    pool.join()
    return results


if __name__ == "__main__":
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

try now! -> in my solution i have prefoius impelement thread one and thread 2 for functionin search. do it !

Code:

################################################
Pollard-kangaroo PrivKey Recovery Tool multicore
################################################
Sun Sep 10 13:42:36 2023
P-table prepared
tame and wild herds kangaroos is being prepared
[Puzzle]: 50
[Xcoordinate]: f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[Ycoordinate]: eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
Using 4 CPU cores for parallel search.
SOLVED: Sun Sep 10 13:44:06 2023 total time: 89.33 sec -0000000000000000000000000000000000000000000000000022bd43c2e9354 

[citb0in]

anyone can answer, please? is there a well-known working and maintained version of Kangaroo that is capable to process keys >125 bit ?
I'm asking because the original version of JLP says:

This program is limited to a 125bit interval search.

If I understand correctly that means I cannot use it for trying to crack puzzles >125bit, right?

[ecdsa123]

anyone can answer, please? is there a well-known working and maintained version of Kangaroo that is capable to process keys >125 bit ?
I'm asking because the original version of JLP says:

This program is limited to a 125bit interval search.

If I understand correctly that means I cannot use it for trying to crack puzzles >125bit, right?

Code:

void Kangaroo::CreateJumpTable() {

#ifdef USE_SYMMETRY
  int jumpBit = rangePower / 2;
#else
  int jumpBit = rangePower / 2 + 1;
#endif

  if(jumpBit > 128) jumpBit = 128;
  int maxRetry = 100;
  bool ok = false;
  double distAvg;
  double maxAvg = pow(2.0,(double)jumpBit - 0.95);
  double minAvg = pow(2.0,(double)jumpBit - 1.05);
  //::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
  //::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
  
  // Kangaroo jumps
  // Constant seed for compatibilty of workfiles
  rseed(0x600DCAFE);

you have max setup : 128 bit as jumpBit if more  if(jumpBit > 128) jumpBit = 128;

[citb0in]

anyone can answer, please? is there a well-known working and maintained version of Kangaroo that is capable to process keys >125 bit ?
I'm asking because the original version of JLP says:

This program is limited to a 125bit interval search.

If I understand correctly that means I cannot use it for trying to crack puzzles >125bit, right?

Code:

void Kangaroo::CreateJumpTable() {

#ifdef USE_SYMMETRY
  int jumpBit = rangePower / 2;
#else
  int jumpBit = rangePower / 2 + 1;
#endif

  if(jumpBit > 128) jumpBit = 128;
  int maxRetry = 100;
  bool ok = false;
  double distAvg;
  double maxAvg = pow(2.0,(double)jumpBit - 0.95);
  double minAvg = pow(2.0,(double)jumpBit - 1.05);
  //::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
  //::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
  
  // Kangaroo jumps
  // Constant seed for compatibilty of workfiles
  rseed(0x600DCAFE);

you have max setup : 128 bit as jumpBit if more  if(jumpBit > 128) jumpBit = 128;

I appreciate your reply however I am not sure if understood. You mean I just need to adjust the Kangaroo.cpp and recompile it? You said 128 bits, cannot we adjust it to allow up to 160bits by replacing 128 by 160 ? Did JLP intensionally implement this restriction with 128bits? And why does he say 125bits while the C++ source code says 128bit ?

[ecdsa123]

you can search for privatekeys up to 256 bit, but program is limited to a 125bit interval search


interval search not means the range of privatekey but diff beetween start and end of privatekey.


Start range
End range
Key #1
Key #2

max different end_range-start_range < 2**128

[citb0in]

understood. Thank you for clarification @ecdsa123
I just ran a successful test with a 129bit key and it worked like a charm.

One more question related to Kangaroo program. Let's say I run Kangaroo and search for a 145bit key. I run it for 1 hour and then quit it because no key was found. Then I re-execute exactly the same command. Will the program iterate through the same values as it did on run first or is it theoretically possible that the 2nd run will find a key? My question basically is: does it behave like VanitySearch where it's theoretically possible to find a match each second regardless of what happened in the history and which range was scanned. Or does it behave more like BitCrack which searches in linear mode ?

[nomachine]

Little explanation.
I have at the moment no time for writing for you all code. ( you should write thread in search def)
read carefullty the change implement by me

Code:

import sys
import io
import random
import math
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
from multiprocessing import Pool, cpu_count

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


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y


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


def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y


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


P = compute_P_table()

os.system("clear")
t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write("################################################" + "\n")
sys.stdout.write("Pollard-kangaroo PrivKey Recovery Tool multicore" + "\n")
sys.stdout.write("################################################" + "\n")
sys.stdout.write(t + "\n")
sys.stdout.write("P-table prepared" + "\n")
sys.stdout.write("tame and wild herds kangaroos is being prepared" + "\n")
sys.stdout.flush()


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)))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference  # Convert to a hexadecimal string
        t = time.ctime()
        total_time = time.time() - starttime
        print("\033[01;33mSOLVED:", t, f"total time: {total_time:.2f} sec", HEX, "\n")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nSOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write("\nPrivate Key (decimal): " + str(difference))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------\n"
            )

    return result

    """        
        return True
    else:
        return False
    """

# Batch writing function
def batch_write_data_to_file(data, file_path, batch_size=5000):
    with open(file_path, "a", buffering=1024 * 1024 * 1024) as fp:
        for i in range(0, len(data), batch_size):
            batch = data[i : i + batch_size]
            fp.writelines(batch)


# Function to check and write data to file
def check(
    P, Pindex, DP_rarity, file2save, A, Ak, B, Bk, buffer_size=1024 * 1024 * 1024
):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        data_to_write = ["%064x %d\n" % (P.x, Pindex)]
        ## YOU DONT USE TAME AND WILD IN SCRIPT! SO FOR WHAT IMPLEMENT IT? IT TAKING TIME AND MEMORY
        """
        batch_write_data_to_file(data_to_write, file2save)  # Batch write data to file
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message + "\r")
        sys.stdout.flush()
        """ 
        return comparator(A, Ak, B, Bk)
    else:
        return False


def save2file(path, mode, data, buffer_size=1024 * 1024 * 1024):
    with open(path, mode, encoding="utf-8") as fp:
        if isinstance(data, (list, tuple, dict, set)):
            for line in data:
                if isinstance(line, str):
                    fp.write(line)
                elif isinstance(line, int):
                    fp.write(str(line))
        elif isinstance(data, (str, int)):
            fp.write(str(data))


# Memoization for ecmultiply
ecmultiply_memo = {}


def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))


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


def search(Nt, Nw, puzzle, kangoo_power, starttime):
    # NOT NECESSARY - TAKING TIME AS MULTIPLY BY PROCESS -> THING AS MINIMALISED TIME FOR OPERATION -> BETTER JOIN FOR ALL PROCESSING Moved !
    """
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    """
    
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
        
    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    
    #oldtime = time.time()  -> NOT USING TAKING TIME
    Hops, Hops_old = 0, 0
    #t0 = time.time()         -> NOT USING TAKING TIME
    oldtime = time.time()
    starttime = oldtime
    while True:
        # THIS FUNCTION CHANGE FOR THREAD
        
        #THREAD ONE
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        
        #THREAD 2    
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return "sol. time: %.2f sec" % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

# DATA SETS AND IMPORTANT INFORMATION -> THINK ABOUT IT AS MINIMALISED OPERATION. 

puzzle = 50
compressed_public_key = (
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
)
kangoo_power = 10  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
Nt = Nw = 2**kangoo_power

# MOVED FROM SEARCH DEF
DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
hop_modulo = ((puzzle - 1) // 2) + kangoo_power
T, t, dt = [], [], []
W, w, dw = [], [], []

for k in range(Nt):
    t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
    T.append(mulk(t[k]))
    dt.append(0)
    
# check format pubkey
if len(compressed_public_key) == 66:
    X = int(compressed_public_key[2:66], 16)
    # calculation Y from X if pubkey is compressed
    Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2)
else:
    print("[error] pubkey len(66/130) invalid!")

print(f"[Puzzle]: {puzzle}")
print("[Xcoordinate]: %064x" % X)
print("[Ycoordinate]: %064x" % Y)

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

Hops = 0
random.seed()

hops_list = []
N_tests = kangoo_power

## YOU DONT USE TAME AND WILD IN SCRIPT! SO FOR WHAT IMPLEMENT IT? IT TAKING TIME AND MEMORY
"""
for k in range(N_tests):
    # Create empty 'tame.txt' and 'wild.txt' files for each iteration
    save2file("tame.txt", "w", "")
    save2file("wild.txt", "w", "")
"""

def parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime):
    pool = Pool(process_count)
    results = pool.starmap(
        search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count
    )
    pool.close()
    pool.join()
    return results


if __name__ == "__main__":
    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search.")
    results = parallel_search(process_count, Nt, Nw, puzzle, kangoo_power, starttime)
    for result in results:
        print(result)

try now! -> in my solution i have prefoius impelement thread one and thread 2 for functionin search. do it !

Code:

################################################
Pollard-kangaroo PrivKey Recovery Tool multicore
################################################
Sun Sep 10 13:42:36 2023
P-table prepared
tame and wild herds kangaroos is being prepared
[Puzzle]: 50
[Xcoordinate]: f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[Ycoordinate]: eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
Using 4 CPU cores for parallel search.
SOLVED: Sun Sep 10 13:44:06 2023 total time: 89.33 sec -0000000000000000000000000000000000000000000000000022bd43c2e9354 

Thanks.

Here is the corrected one. The script was able to find  2**50 on my pc in 90 seconds.

Code:

import sys
import os
import time
import random
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
import multiprocessing
from multiprocessing import Pool, cpu_count

# Constants
modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y


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


def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R


@lru_cache(maxsize=None)
def X2Y(X, y_parity, p=modulo):
    Y = 3
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    X = (tmp + 7) % p

    Y = (p + 1) // 4
    tmp = 1
    while Y:
        if Y & 1:
            tmp = tmp * X % p
        Y >>= 1
        X = X * X % p

    Y = tmp

    if Y % 2 != y_parity:
        Y = -Y % p

    return Y


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


P = compute_P_table()

# Global event to signal all processes to stop
stop_event = multiprocessing.Event()


def comparator(A, Ak, B, Bk):
    global stop_event
    result = set(A).intersection(set(B))

    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference  # Convert to a hexadecimal string
        t = time.ctime()
        total_time = time.time() - starttime
        print("\033[01;33mSOLVED:", t, f"total time: {total_time:.2f} sec", HEX, "\n")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nSOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write("\nPrivate Key (decimal): " + str(difference))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------\n"
            )

        stop_event.set()  # Set the stop event to signal all processes


def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        # Print the public key
        message = "\rPublic key: {:064x}".format(P.x)
        sys.stdout.write("\033[01;33m")
        sys.stdout.write(message + "\r")
        sys.stdout.flush()
        return comparator(A, Ak, B, Bk)
    else:
        return False


ecmultiply_memo = {}


def ecmultiply(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ecmultiply_memo:
            return ecmultiply_memo[k]
        else:
            result = ecmultiply(k // 2, mul2(P, p), p)
            ecmultiply_memo[k] = result
            return result
    else:
        return add(P, ecmultiply((k - 1) // 2, mul2(P, p), p))


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


def search(Nt, Nw, puzzle, kangoo_power, starttime):
    global stop_event
    for k in range(Nt):
        t.append((3 << (puzzle - 2)) + random.randint(1, (2 ** (puzzle - 1))))
        T.append(mulk(t[k]))
        dt.append(0)

    for k in range(Nw):
        w.append(random.randint(1, (1 << (puzzle - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)

    Hops, Hops_old = 0, 0

    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved:
                stop_event.set()  # Set the stop event to signal all processes
                return "sol. time: %.2f sec" % (
                    time.time() - starttime
                )  # Return solution time
                sys.stdout.write("\033[01;33m")
                sys.stdout.flush()
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved:
                stop_event.set()  # Set the stop event to signal all processes
                return "sol. time: %.2f sec" % (
                    time.time() - starttime
                )  # Return solution time
                sys.stdout.write("\033[01;33m")
                sys.stdout.flush()
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

        # Check the stop event and exit the loop if it's set
        if stop_event.is_set():
            sys.exit()  # Exit the script if a solution is found


# Main script
if __name__ == "__main__":
    os.system("clear")
    t = time.ctime()
    sys.stdout.write("\033[01;33m")
    sys.stdout.write("################################################" + "\n")
    sys.stdout.write("Pollard-kangaroo PrivKey Recovery Tool multicore" + "\n")
    sys.stdout.write("################################################" + "\n")
    sys.stdout.write(t + "\n")
    sys.stdout.flush()

    # Initialize constants and precompute table
    puzzle = 50
    kangoo_power = 10  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
    Nt = Nw = 2**kangoo_power
    DP_rarity = 1 << ((puzzle - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []

    compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50

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

    print(f"[Puzzle]: {puzzle}")
    print("[Xcoordinate]: %064x" % X)
    print("[Ycoordinate]: %064x" % Y)

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

    Hops = 0
    random.seed()

    hops_list = []

    process_count = cpu_count()  # Use all available CPU cores
    print(f"Using {process_count} CPU cores for parallel search")

    # Perform parallel search
    pool = Pool(process_count)
    results = pool.starmap(
        search, [(Nt, Nw, puzzle, kangoo_power, starttime)] * process_count
    )
    pool.close()
    pool.join()

    for result in results:
        print(result)

[ecdsa123]

if this part of code:

Code:

while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved:
                stop_event.set()  # Set the stop event to signal all processes
                return "sol. time: %.2f sec" % (
                    time.time() - starttime
                )  # Return solution time
                sys.stdout.write("\033[01;33m")
                sys.stdout.flush()
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved:
                stop_event.set()  # Set the stop event to signal all processes
                return "sol. time: %.2f sec" % (
                    time.time() - starttime
                )  # Return solution time
                sys.stdout.write("\033[01;33m")
                sys.stdout.flush()
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

you change for additional thread or multicore -> will be faster about  20-25 s

[nomachine]

if this part of code:

Code:

while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved:
                stop_event.set()  # Set the stop event to signal all processes
                return "sol. time: %.2f sec" % (
                    time.time() - starttime
                )  # Return solution time
                sys.stdout.write("\033[01;33m")
                sys.stdout.flush()
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved:
                stop_event.set()  # Set the stop event to signal all processes
                return "sol. time: %.2f sec" % (
                    time.time() - starttime
                )  # Return solution time
                sys.stdout.write("\033[01;33m")
                sys.stdout.flush()
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])

you change for additional thread or multicore -> will be faster about  20-25 s

 I have a better idea. TO insert all calculations and search in @numba.jit....To use Numba  to compile the performance-critical parts of code into machine code, which can significantly speed up computation.


p.s.
def add_numba(P, Q, p=modulo):
    <source elided>

@njit
^

This error may have been caused by the following argument(s):
- argument 0: Int value is too large: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- argument 2: Int value is too large: 115792089237316195423570985008687907853269984665640564039457584007908834671663

Numba does not support big int. It is essentially limited to integer types that are supported by numpy. The max integer width is currently limited to 64-bit.  

GMP is the best option for now.

Update :

Code:

import sys
import os
import time
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
import secp256k1 as ice
import multiprocessing
from multiprocessing import Pool, cpu_count

# Constants
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 = x
        self.y = y

PG = Point(GX, GY)
ZERO_POINT = Point(0, 0)

# Function to multiply a point by 2
def multiply_by_2(P, p=MODULO):
    c = gmpy2.f_mod(3 * P.x * P.x * gmpy2.powmod(2 * P.y, -1, p), p)
    R = Point()
    R.x = gmpy2.f_mod(c * c - 2 * P.x, p)
    R.y = gmpy2.f_mod(c * (P.x - R.x) - P.y, p)
    return R

# Function to add two points
def add_points(P, Q, p=MODULO):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = gmpy2.f_mod(dy * gmpy2.invert(dx, p), p)
    R = Point()
    R.x = gmpy2.f_mod(c * c - P.x - Q.x, p)
    R.y = gmpy2.f_mod(c * (P.x - R.x) - P.y, p)
    return R

# Function to calculate Y-coordinate from X-coordinate
@lru_cache(maxsize=None)
def x_to_y(X, y_parity, p=MODULO):
    Y = gmpy2.mpz(3)
    tmp = gmpy2.mpz(1)

    while Y > 0:
        if Y % 2 == 1:
            tmp = gmpy2.f_mod(tmp * X, p)
        Y >>= 1
        X = gmpy2.f_mod(X * X, p)

    X = gmpy2.f_mod(tmp + 7, p)

    Y = gmpy2.f_div(gmpy2.add(p, 1), 4)
    tmp = gmpy2.mpz(1)

    while Y > 0:
        if Y % 2 == 1:
            tmp = gmpy2.f_mod(tmp * X, p)
        Y >>= 1
        X = gmpy2.f_mod(X * X, p)

    Y = tmp

    if Y % 2 != y_parity:
        Y = gmpy2.f_mod(-Y, p)

    return Y

# Function to compute a table of points
def compute_point_table():
    points = [PG]
    for k in range(255):
        points.append(multiply_by_2(points[k]))
    return points

POINTS_TABLE = compute_point_table()

# Global event to signal all processes to stop
STOP_EVENT = multiprocessing.Event()

# Function to check and compare points for potential solutions
def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    check = gmpy2.f_mod(P.x, DP_rarity)
    if check == 0:
        message = f"\r[+] [Pindex]: {mpz(Pindex)}"
        messages = []
        messages.append(message)
        output = "\033[01;33m" + ''.join(messages) + "\r"
        sys.stdout.write(output)
        sys.stdout.flush()
        A.append(mpz(P.x))
        Ak.append(mpz(Pindex))
        return comparator(A, Ak, B, Bk)
    else:
        return False


# Function to compare two sets of points and find a common point
def comparator(A, Ak, B, Bk):
    global STOP_EVENT
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        difference = Ak[sol_kt] - Bk[sol_kw]
        HEX = "%064x" % difference
        wifc = ice.btc_pvk_to_wif("%064x" % mpz(difference))
        dec = int(ice.btc_wif_to_pvk_hex(wifc), 16)
        wifu = ice.btc_pvk_to_wif(HEX, False)  # Uncompressed
        uaddr = ice.privatekey_to_address(0, False, dec)  # Uncompressed
        caddr = ice.privatekey_to_address(0, True, dec)  # Compressed
        HASH160 = ice.privatekey_to_h160(0, True, dec).hex()
        t = time.ctime()
        total_time = time.time() - starttime
        print(f"\033[32m[+] PUZZLE SOLVED: {t}, total time: {total_time:.2f} sec \033[0m")
        print(f"\033[32m[+] WIF: \033[32m {wifc} \033[0m")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nPUZZLE SOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write('\nPrivate Key (dec): ' + str(dec))
            file.write('\nPrivate Key (hex): ' + HEX)
            file.write('\nPrivate Key Compressed: ' + wifc)
            file.write('\nPrivate Key Uncompressed: ' + wifu)
            file.write('\nPublic Address Compressed: ' + caddr)
            file.write('\nPublic Address Uncompressed: ' + uaddr)
            file.write('\nPublic Key Hash Compressed (Hash 160): ' + HASH160)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------\n"
            )

        STOP_EVENT.set()  # Set the stop event to signal all processes

# Memoization for point multiplication
ECMULTIPLY_MEMO = {}

# Function to multiply a point by a scalar
def ecmultiply(k, P=PG, p=MODULO):
    if k == 0:
        return ZERO_POINT
    elif k == 1:
        return P
    elif k % 2 == 0:
        if k in ECMULTIPLY_MEMO:
            return ECMULTIPLY_MEMO[k]
        else:
            result = ecmultiply(k // 2, multiply_by_2(P, p), p)
            ECMULTIPLY_MEMO[k] = result
            return result
    else:
        return add_points(P, ecmultiply((k - 1) // 2, multiply_by_2(P, p), p))

# Recursive function to multiply a point by a scalar
def mulk(k, P=PG, p=MODULO):
    if k == 0:
        return ZERO_POINT
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, multiply_by_2(P, p), p)
    else:
        return add_points(P, mulk((k - 1) // 2, multiply_by_2(P, p), p))

# Generate a list of powers of two for faster access
@lru_cache(maxsize=None)
def generate_powers_of_two(hop_modulo):
    return [mpz(1 << pw) for pw in range(hop_modulo)]

# Worker function for point search
def search_worker(
    Nt, Nw, puzzle, kangaroo_power, starttime, lower_range_limit, upper_range_limit
):
    global STOP_EVENT

    # Precompute random values
    random_state_t = gmpy2.random_state(hash(gmpy2.random_state()))
    random_state_w = gmpy2.random_state(hash(gmpy2.random_state()))

    t = [
        mpz(lower_range_limit + mpz(gmpy2.mpz_random(random_state_t, upper_range_limit - lower_range_limit)))
        for _ in range(Nt)
    ]
    T = [mulk(ti) for ti in t]
    dt = [mpz(0) for _ in range(Nt)]
    w = [
        mpz(gmpy2.mpz_random(random_state_w, upper_range_limit - lower_range_limit))
        for _ in range(Nt)
    ]
    W = [add_points(W0, mulk(wk)) for wk in w]
    dw = [mpz(0) for _ in range(Nw)]

    Hops, Hops_old = 0, 0

    oldtime = time.time()
    starttime = oldtime

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = powers_of_two[pw]
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved:
                STOP_EVENT.set()
                raise SystemExit
            t[k] = mpz(t[k]) + dt[k]  # Use mpz here
            T[k] = add_points(POINTS_TABLE[pw], T[k])

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = powers_of_two[pw]
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved:
                STOP_EVENT.set()
                raise SystemExit
            w[k] = mpz(w[k]) + dw[k]  # Use mpz here
            W[k] = add_points(POINTS_TABLE[pw], W[k])

        if STOP_EVENT.is_set():
            break


# Main script
if __name__ == "__main__":
    os.system("clear")
    t = time.ctime()
    sys.stdout.write("\033[01;33m")
    sys.stdout.write(f"[+] {t}" + "\n")
    sys.stdout.flush()
    # Configuration for the puzzle
    puzzle = 50
    compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"  # Puzzle 50
    kangaroo_power = 10  # For Puzzle 50-56 use 9 to 11, for Puzzle 60-80 use 14 to 16 / 24 cores or above preferred
    lower_range_limit = 2 ** (puzzle - 1)
    upper_range_limit = (2**puzzle) - 1

    Nt = Nw = 2**kangaroo_power
    DP_rarity = 1 << ((puzzle - 2 * kangaroo_power) // 2 - 2)
    hop_modulo = ((puzzle - 1) // 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 = mpz(compressed_public_key[2:66], 16)
        Y = x_to_y(X, mpz(compressed_public_key[:2]) - 2)
    else:
        print("[error] pubkey len(66/130) invalid!")

    print(f"[+] [Puzzle]: {puzzle}")
    print(f"[+] [Lower range limit]: {lower_range_limit}")
    print(f"[+] [Upper range limit]: {upper_range_limit}")
    print("[+] [Xcoordinate]: %064x" % X)
    print("[+] [Ycoordinate]: %064x" % Y)

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

    Hops = 0

    process_count = cpu_count()
    print(f"[+] Using {process_count} CPU cores for parallel search")

    # Create a pool of worker processes
    pool = Pool(process_count)
    results = pool.starmap(
        search_worker,
        [
            (
                Nt,
                Nw,
                puzzle,
                kangaroo_power,
                starttime,
                lower_range_limit,
                upper_range_limit,
            )
        ]
        * process_count,
    )
    pool.close()
    pool.join()

• Pollard-kangaroo PrivKey Recovery Tool multicore
• Mon Sep 11 12:15:07 2023
• [Puzzle]: 50
• [Xcoordinate]: f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
• [Ycoordinate]: eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
• Using 4 CPU cores for parallel search

SOLVED: Mon Sep 11 12:15:34 2023 total time: 26.36 sec -0000000000000000000000000000000000000000000000000022bd43c2e9354

This is my personal record with Python.

[tifosi87]

is there a way for search y coordinate square modulo p

[digaran]

is there a way for search y coordinate square modulo p

Why would you want that? Imagine you are searching for y coordinates.

Example :
X=
0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Y=
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Private key= 0x1
X= 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb
Y=
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Private key=
0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
X=
0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb
Y=
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Private key=
0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce

They all have the same y coordinates, are you sure you want to search for them?

[CY4NiDE]

understood. Thank you for clarification @ecdsa123
I just ran a successful test with a 129bit key and it worked like a charm.

One more question related to Kangaroo program. Let's say I run Kangaroo and search for a 145bit key. I run it for 1 hour and then quit it because no key was found. Then I re-execute exactly the same command. Will the program iterate through the same values as it did on run first or is it theoretically possible that the 2nd run will find a key? My question basically is: does it behave like VanitySearch where it's theoretically possible to find a match each second regardless of what happened in the history and which range was scanned. Or does it behave more like BitCrack which searches in linear mode ?

I have the same doubt!

[ecdsa123]

understood. Thank you for clarification @ecdsa123
I just ran a successful test with a 129bit key and it worked like a charm.

One more question related to Kangaroo program. Let's say I run Kangaroo and search for a 145bit key. I run it for 1 hour and then quit it because no key was found. Then I re-execute exactly the same command. Will the program iterate through the same values as it did on run first or is it theoretically possible that the 2nd run will find a key? My question basically is: does it behave like VanitySearch where it's theoretically possible to find a match each second regardless of what happened in the history and which range was scanned. Or does it behave more like BitCrack which searches in linear mode ?

I have the same doubt!

Answer: You are right. Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,

[citb0in]

One more question related to Kangaroo program. Let's say I run Kangaroo and search for a 145bit key. I run it for 1 hour and then quit it because no key was found. Then I re-execute exactly the same command. Will the program iterate through the same values as it did on run first or is it theoretically possible that the 2nd run will find a key? My question basically is: does it behave like VanitySearch where it's theoretically possible to find a match each second regardless of what happened in the history and which range was scanned. Or does it behave more like BitCrack which searches in linear mode ?

Answer: You are right. Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,

Thanks for your kind feedback.

[digaran]

Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,

Wait, what do you mean by this? You mean when we use kangaroo it will change searching methods? Or you mean when we set a different search range?

[citb0in]

Pollard rho will not iterate the same values. it means that second or third run command maybe will find the key,

Wait, what do you mean by this? You mean when we use kangaroo it will change searching methods? Or you mean when we set a different search range?

come on, such question from such a guy - really ? what's next ?