Kangaroo search: 100%|█| 2/2 [00:00<00:00, 367.87 process/s
Private key found: 1099512414208
Validation failed: The private key is incorrect.
import multiprocessing
from multiprocessing import Process, Manager
from ecdsa import ellipticcurve, numbertheory
from tqdm import tqdm
# Define elliptic curve parameters for secp256k1
p = int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16)
a = 0
b = 7
Gx = int("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16)
Gy = int("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16)
G = ellipticcurve.Point(ellipticcurve.CurveFp(p, a, b), Gx, Gy)
n = int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
def compress_to_point(compressed_public_key):
prefix = int(compressed_public_key[:2], 16)
x = int(compressed_public_key[2:], 16)
y_squared = (x**3 + a*x + b) % p
y = numbertheory.square_root_mod_prime(y_squared, p)
if (prefix == 2 and y % 2 != 0) or (prefix == 3 and y % 2 == 0):
y = p - y
return ellipticcurve.Point(ellipticcurve.CurveFp(p, a, b), x, y)
def kangaroo_worker(start, end, PG, lower, upper, m, result_list, process_index):
n = upper - lower + 1
x_values = [0] * m
y_values = [0] * m
shared_memory = [0] * m
for i in range(start, end):
if (i - start) >= m:
break
x = (PG.x() * i) % n
x_values[i - start] = x
y_values[i - start] = i
for i in range(min(m, len(x_values))):
shared_memory[x_values[i] % m] = y_values[i]
x = 0
y = 0
while True:
x = (PG.x() * x) % n
y += 1
if shared_memory[x % m] != 0:
break
result_list[process_index] = lower + shared_memory[x % m] + y - 1
def kangaroo_algorithm(lower, upper, compressed_public_key):
PG = compress_to_point(compressed_public_key)
m = 2**20
num_processes = multiprocessing.cpu_count()
chunk_size = (upper - lower + 1) // num_processes
manager = multiprocessing.Manager()
result_list = manager.list([None] * num_processes)
processes = []
# Use tqdm to show progress
for i in tqdm(range(num_processes), desc="Kangaroo search", unit=" process"):
start = lower + i * chunk_size
end = min(lower + (i + 1) * chunk_size, upper + 1)
process = multiprocessing.Process(target=kangaroo_worker, args=(start, end, PG, lower, upper, m, result_list, i))
processes.append(process)
process.start()
for process in processes:
process.join()
for result in result_list:
if result is not None:
return result
return None
# Set the range for puzzle 40
lower = 2**39
upper = 2**40 - 1
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
private_key = kangaroo_algorithm(lower, upper, compressed_public_key)
print(f"Private key found: {private_key}")
# Validate the private key
if private_key is not None:
Q = compress_to_point(compressed_public_key)
computed_Q = G * private_key # Use the * operator for scalar multiplication
if computed_Q == Q:
print("Validation successful: The private key is correct.")
else:
print("Validation failed: The private key is incorrect.")
else:
print("Private key not found.")