fork download
copy 
  1. import multiprocessing
  2. from multiprocessing import Process, Manager
  3. from ecdsa import ellipticcurve, numbertheory
  4. from tqdm import tqdm
  5.  
  6. # Define elliptic curve parameters for secp256k1
  7. p = int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16)
  8. a = 0
  9. b = 7
  10. Gx = int("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16)
  11. Gy = int("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16)
  12. G = ellipticcurve.Point(ellipticcurve.CurveFp(p, a, b), Gx, Gy)
  13. n = int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
  14.  
  15. def compress_to_point(compressed_public_key):
  16.     prefix = int(compressed_public_key[:2], 16)
  17.     x = int(compressed_public_key[2:], 16)
  18.     y_squared = (x**3 + a*x + b) % p
  19.     y = numbertheory.square_root_mod_prime(y_squared, p)
  20.     if (prefix == 2 and y % 2 != 0) or (prefix == 3 and y % 2 == 0):
  21.         y = p - y
  22.     return ellipticcurve.Point(ellipticcurve.CurveFp(p, a, b), x, y)
  23.  
  24. def kangaroo_worker(start, end, PG, lower, upper, m, result_list, process_index):
  25.     n = upper - lower + 1
  26.     x_values = [0] * m
  27.     y_values = [0] * m
  28.     shared_memory = [0] * m
  29.  
  30.     for i in range(start, end):
  31.         if (i - start) >= m:
  32.             break
  33.         x = (PG.x() * i) % n
  34.         x_values[i - start] = x
  35.         y_values[i - start] = i
  36.  
  37.     for i in range(min(m, len(x_values))):
  38.         shared_memory[x_values[i] % m] = y_values[i]
  39.  
  40.     x = 0
  41.     y = 0
  42.     while True:
  43.         x = (PG.x() * x) % n
  44.         y += 1
  45.         if shared_memory[x % m] != 0:
  46.             break
  47.  
  48.     result_list[process_index] = lower + shared_memory[x % m] + y - 1
  49.  
  50. def kangaroo_algorithm(lower, upper, compressed_public_key):
  51.     PG = compress_to_point(compressed_public_key)
  52.     m = 2**20
  53.     num_processes = multiprocessing.cpu_count()
  54.     chunk_size = (upper - lower + 1) // num_processes
  55.     manager = multiprocessing.Manager()
  56.     result_list = manager.list([None] * num_processes)
  57.     processes = []
  58.  
  59.     # Use tqdm to show progress
  60.     for i in tqdm(range(num_processes), desc="Kangaroo search", unit=" process"):
  61.         start = lower + i * chunk_size
  62.         end = min(lower + (i + 1) * chunk_size, upper + 1)
  63.         process = multiprocessing.Process(target=kangaroo_worker, args=(start, end, PG, lower, upper, m, result_list, i))
  64.         processes.append(process)
  65.         process.start()
  66.  
  67.     for process in processes:
  68.         process.join()
  69.  
  70.     for result in result_list:
  71.         if result is not None:
  72.             return result
  73.  
  74.     return None
  75.  
  76. # Set the range for puzzle 40
  77. lower = 2**39
  78. upper = 2**40 - 1
  79. compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
  80.  
  81. private_key = kangaroo_algorithm(lower, upper, compressed_public_key)
  82. print(f"Private key found: {private_key}")
  83.  
  84. # Validate the private key
  85. if private_key is not None:
  86.     Q = compress_to_point(compressed_public_key)
  87.     computed_Q = G * private_key  # Use the * operator for scalar multiplication
  88.     if computed_Q == Q:
  89.         print("Validation successful: The private key is correct.")
  90.     else:
  91.         print("Validation failed: The private key is incorrect.")
  92. else:
  93.     print("Private key not found.")
Success #stdin #stdout 0.02s 25772KB
comments (?)
stdin
copy 
Kangaroo search: 100%|█| 2/2 [00:00<00:00, 367.87 process/s
Private key found: 1099512414208
Validation failed: The private key is incorrect.
stdout
copy 
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.")
https://ideone.com/54UWwf
language:
PHP (php 7.3.5)
created:
48 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!