Quote from: Akito S. M. Hosana on Today at 05:45:07 PM

Can anyone solve, say, puzzle 50 in Python in 10 seconds? Tongue

Why does it have to be Puzzle 50? Of course I can — but I'll use a random seed.

Code:

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

os.system("clear")

# 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)
Z = Point(0, 0)

# Function to multiply a point by 2
def multiply_by_2(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)

# Function to add two points
def add_points(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)

# Function to calculate Y-coordinate from X-coordinate
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):
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

# 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)))
HEX = "%064x" % abs(Ak[sol_kt] - Bk[sol_kw])
dec = int(HEX, 16)
t = time.ctime()
pid = os.getpid() # Get the process ID
core_number = pid % cpu_count() # Calculate the CPU core number
total_time = time.time() - starttime
print(f"\n\033[32m[+] PUZZLE SOLVED: {t}, total time: {total_time:.2f} sec, Core: {core_number+1:02} \033[0m")
print(f"\033[32m[+] HEX: \033[32m {HEX} \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("\nPrivate Key (decimal): " + str(dec))
file.write("\nPrivate Key (hex): " + HEX)
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
def generate_powers_of_two(hop_modulo):
return [mpz(1 << pw) for pw in range(hop_modulo)]

t = time.ctime()
sys.stdout.write("\033[01;33m")
sys.stdout.write(f"[+] [Kangaroo]: {t}" + "\n")
sys.stdout.flush()

# Configuration for the puzzle
puzzle = 50
compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"
lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (2**puzzle) - 1

kangaroo_power = 6

Nt = Nw = (2 ** kangaroo_power // puzzle) * puzzle + 8
DP_rarity = 8 * puzzle
hop_modulo = (puzzle // 2) + 8

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

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)
print(f"[+] [Expected Hops: 2^{log2(2.2 * sqrt(1 << (puzzle-1))):.2f} ({int(2.2 * sqrt(1 << (puzzle-1)))})]")

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

Hops = 0

# Worker function for point search
def search_worker(
Nt, Nw, puzzle, kangaroo_power, starttime, lower_range_limit, upper_range_limit
):
global STOP_EVENT
pid = os.getpid()
core_number = pid % cpu_count()
#Random seed Config
#constant_prefix = b'' #back to no constant
constant_prefix = b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
prefix_length = len(constant_prefix)
length = 8
ending_length = length - prefix_length
with open("/dev/urandom", "rb") as urandom_file:
ending_bytes = urandom_file.read(ending_length)
random_bytes = constant_prefix + ending_bytes
print(f"[+] [Core]: {core_number+1:02}, [Random seed]: {random_bytes}")
random.seed(random_bytes)
t = [
mpz(
lower_range_limit
+ mpz(random.randint(0, 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(random.randint(0, upper_range_limit - lower_range_limit)) for _ in range(Nw)
]
W = [add_points(W0, mulk(wk)) for wk in w]
dw = [mpz(0) for _ in range(Nw)]

Hops, Hops_old = 0, 0
cores = cpu_count()
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] = powers_of_two[pw]
solved = check(T[k], t[k], DP_rarity, T, t, W, w)
if solved:
STOP_EVENT.set()
break
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()
break
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
t1 = time.time()
elapsed_time = t1 - starttime
if t1 - t0 > 1 and core_number == 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

# Main script
if __name__ == "__main__":
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()

Quote

[Kangaroo]: Mon May 5 10:14:12 2025
[Puzzle]: 50
[Lower range limit]: 562949953421312
[Upper range limit]: 1125899906842623
[Xcoordinate]: f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[Ycoordinate]: eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
[Expected Hops: 2^25.64 (52198446)]
[Using 12 CPU cores for parallel search]:
[Core]: 04, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 05, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 08, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 07, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 06, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 09, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 10, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 11, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 12, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 02, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 01, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Core]: 03, [Random seed]: b'\xbc\x9b\x8cd\xfc\xa1?\xcf'
[Hops: 2^24.44 <-> 1982097 h/s] [00:00:10]
PUZZLE SOLVED: Mon May 5 10:14:22 2025, total time: 10.73 sec, Core: 04
HEX: 00000000000000000000000000000000000000000000000000022bd43c2e9354