PUZZLE SOLVED: Wed Oct 11 12:13:21 2023, total time: 13.47 sec
- WIF: -0000000000000000000000000000000000000000000000000022bd43c2e9354
nice catching again nomachine, is this programmable for 120th and up
Yes.
It takes about 3 minutes to start solving Puzzle 130 on my 12 Core - but will start.
Here is code for Puzzle130
import sys
import os
import time
import random
import hashlib
import gmpy2
from gmpy2 import mpz
from functools import lru_cache
import multiprocessing
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)
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 = "\r[+] [Pindex]: {}".format(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
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"\033[32m[+] PUZZLE SOLVED: {t}, total time: {total_time:.2f} sec, Core: {core_number+1:02} \033[0m")
print(f"\033[32m[+] WIF: \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(difference))
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
@lru_cache(maxsize=None)
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 = 130
compressed_public_key = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852" # Puzzle 130
lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (2 ** puzzle) - 1
kangaroo_power = puzzle // 8
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)
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
# 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' #Puzzle 50 seed - 10-18s
constant_prefix = b'\xbc\x9b'
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
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
# 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()
I put only 2 bytes as a constant - the rest will be randomized through all CPU cores, since we don't know what the seed for 130 is. . .
constant_prefix =
b'\xbc\x9b' constant_prefix =
b'' is all random
ON the smaller puzzles it is easy to guess what the seed is. You need to restart and restart app and you will find out which is the fastest seed by repetition. The script will show exactly which seed and which core hit the WIF. You can experiment with different ones as you like.
