Hi, i am currently exploring methods to find private key. i have already gone through several methods and some had been adjusted for 256 bit keys. some work really good, others are just not able to solve in a reasonable amount of time.
i had done up this code.
first script is to generate smooth numbers and its exponents.
import random
import math
import multiprocessing as mp
import torch
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
import time
from decimal import Decimal, getcontext
# Set decimal precision
getcontext().prec = 1000 # Adjust precision as needed
# Define your public key coordinates here
pub_key_x = 0x123abc
pub_key_y = 0x456def
print("Definitions loaded.")
# Function to generate a prime factor base
def generate_factor_base(limit):
print("Generating factor base...")
primes = []
num = 2
try:
while len(primes) < limit:
if all(num % i != 0 for i in range(2, int(num**0.5) + 1)):
primes.append(num)
num += 1
print("Factor base generated.")
return primes
except Exception as e:
print(f"Error in factor base generation: {e}")
return []
# Precompute the factor base
factor_base_size = 150 # Adjusted for secp256k1
factor_base = generate_factor_base(factor_base_size)
if not factor_base:
exit(1)
print("Factor base precomputed.")
# Function to find smooth numbers in a range
def find_smooth_numbers(start, end, stop_index=1000000):
print(f"Finding smooth numbers in range {start}-{end}...")
smooth_numbers = []
device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
print(f"Using {device} for finding smooth numbers.")
# Read the last line from the file to get the stop index
try:
with open('smooth_numbers.txt', 'r') as file:
lines = file.readlines()
if lines:
last_line = lines[-1]
stop_index = int(last_line.split(',')[0].split(':')[1].strip())
print(f"Resuming from stop index: {stop_index}")
else:
print("No previous smooth numbers found in the file.")
except Exception as e:
print(f"Error reading last line of smooth_numbers.txt: {e}")
def write_smooth_numbers(smooth_numbers):
try:
with open('smooth_numbers.txt', 'a') as file: # Open file in append mode
for num, exps in smooth_numbers:
file.write(f"Number: {num}, Exponents: {exps}\n")
except Exception as e:
print(f"Error writing smooth numbers: {e}")
for num in range(max(start, stop_index + 1), end + 1):
exps = []
num_tensor = torch.tensor(num, device=device)
for p in factor_base:
count = 0
while num_tensor % p == 0:
count += 1
num_tensor //= p
exps.append(count)
if num_tensor == 1:
smooth_numbers.append((num, exps))
print(f"Smooth number found: {num} with exponents {exps}")
write_smooth_numbers([(num, exps)])
# Introduce a short sleep interval to reduce CPU load
time.sleep(0.001) # Sleep for 1 millisecond
print(f"Found {len(smooth_numbers)} smooth numbers in range {start}-{end}.")
return smooth_numbers
# Function for multiprocessing
def process_range(args):
start, end, G, n = args
smooth_nums = find_smooth_numbers(start, end)
if not smooth_nums:
return [] # Return an empty list if no smooth numbers found
else:
return smooth_nums
# Use freeze_support for multiprocessing
if __name__ == '__main__':
mp.freeze_support()
# Parameters for secp256k1 curve and public key
n = secp256k1.q
G = secp256k1.G
pub_key = Point(pub_key_x, pub_key_y, curve=secp256k1)
print("Parameters set.")
print("Calculating private key...")
# Split the range into chunks for multiprocessing
num_chunks = mp.cpu_count()
chunk_size = (n // num_chunks) + 1
ranges = [(i, min(i + chunk_size - 1, n), G, n) for i in range(1, n + 1, chunk_size)]
# Perform multiprocessing
with mp.Pool(processes=num_chunks) as pool:
try:
results = pool.map(process_range, ranges)
print("Multiprocessing completed.")
except Exception as e:
print(f"Error in multiprocessing: {e}")
results = []
# Combine results from multiprocessing
logs = []
for logs_chunk in results:
if logs_chunk:
logs.extend(logs_chunk)
# Define the file name for private keys
private_key_file = 'private_keys.txt'
# Function to write private keys to a file
def write_private_keys(file_name, private_keys):
try:
with open(file_name, 'w') as file:
for key in private_keys:
file.write(f"{key}\n")
print(f"Private keys written to {file_name}.")
except Exception as e:
print(f"Error writing private keys to {file_name}: {e}")
# Write private keys to the file
write_private_keys(private_key_file, private_keys)
2nd script is to solve via kangaroo method and taking the exponents to create a table so it can find the private key faster.
import random
import math
import multiprocessing as mp
import torch
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
import time
from decimal import Decimal, getcontext
# Set decimal precision
getcontext().prec = 1000 # Adjust precision as needed
# Define the generator point G for secp256k1 curve
G = Point(
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
curve=secp256k1
)
# Define your public key coordinates here
pub_key_x = 0x1233xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
pub_key_y = 0xab123
# Function to load smooth numbers from file
def load_smooth_numbers(file_path):
smooth_numbers = []
try:
with open(file_path, 'r') as file:
for line in file:
if line.startswith('Number:'):
number = int(line.split(':')[1].split(',')[0].strip())
exponents = []
for exp in line.split(':')[2].strip().strip('[').strip(']').split(','):
exponents.append(int(exp.strip()))
smooth_numbers.append({'number': number, 'exponents': exponents})
except FileNotFoundError:
print(f"Error: File '{file_path}' not found.")
except Exception as e:
print(f"Error occurred while loading the file: {e}")
return smooth_numbers
file_path = 'smooth_numbers.txt'
smooth_numbers_data = load_smooth_numbers(file_path)
if smooth_numbers_data:
for smooth_number in smooth_numbers_data:
print(f"Smooth Number: {smooth_number['number']}, Exponents: {smooth_number['exponents']}")
else:
print("No smooth numbers found or error occurred while loading the file.")
# Function to calculate weighted steps for smooth numbers
def calculate_weighted_steps(smooth_numbers):
weighted_steps = {}
for item in smooth_numbers:
num, exps = item['number'], item['exponents']
exps = [int(x) for x in exps] # Convert string exponents to integers
weight = sum(exps) # Using the sum of exponents as the weight
if weight not in weighted_steps:
weighted_steps[weight] = []
weighted_steps[weight].append(num)
return weighted_steps
# Function to adjust kangaroo steps dynamically based on smooth number weights
def dynamic_kangaroo_steps(weighted_steps, target_weight):
target_weight_tuple = (target_weight,) # Convert target_weight to a tuple
if target_weight_tuple in weighted_steps: # Check if the tuple is in weighted_steps
return weighted_steps[target_weight_tuple] # Use target_weight_tuple as key
else:
# Find the nearest weight to the target weight
nearest_weight = min(weighted_steps.keys(), key=lambda x: abs(x - target_weight))
return weighted_steps[nearest_weight] # Return the steps for the nearest weight
# Function to calculate private keys using Kangaroo algorithm
def kangaroo(sorted_smooth_numbers, lookup_table, collision_distance):
print("Calculating private key using Kangaroo algorithm...")
private_keys = []
num_kangaroos = 5 # Number of kangaroos
kangaroo_steps = 1000 # Number of steps for each kangaroo
# Calculate weighted steps for smooth numbers
weighted_steps = calculate_weighted_steps(sorted_smooth_numbers)
for k in range(num_kangaroos):
if k == 0:
tame_pos, wild_pos = tame_start, wild_start
else:
tame_pos, wild_pos = sorted_smooth_numbers[k]['number'], sorted_smooth_numbers[-(k+1)]['number']
for step in range(kangaroo_steps):
# Calculate the step for the wild kangaroo using the lookup table and smooth numbers
target_weight = abs(wild_pos - pub_key_x) % collision_distance
target = dynamic_kangaroo_steps(weighted_steps, target_weight)
if isinstance(target, list):
target = tuple(target) # Convert list to tuple if needed
if target in lookup_table:
step = lookup_table[target]
wild_pos += step
tame_pos += 1
if tame_pos == wild_pos:
# Private key found
private_key = (wild_pos - tame_start) * G.x # Define G as the generator point for secp256k1
private_keys.append(private_key)
print(f"Private key found: {private_key}")
break
return private_keys
# Main code
while True:
if smooth_numbers_data:
print("Loaded smooth numbers. Starting Kangaroo algorithm...")
# Define the parameters for the Kangaroo algorithm
collision_distance = 10 # Static collision distance for all kangaroos
# Define and populate the lookup_table
lookup_table = {tuple(num['exponents']): num['number'] for num in smooth_numbers_data}
# Initialize the starting points for tame and wild kangaroos
if smooth_numbers_data:
tame_start, wild_start = smooth_numbers_data[0]['number'], smooth_numbers_data[-1]['number']
else:
tame_start, wild_start = 2, 1000 # Default starting points if no smooth numbers are loaded
# Sort the loaded smooth numbers in ascending order
sorted_smooth_numbers = sorted(smooth_numbers_data, key=lambda x: x['number'])
# Calculate private keys using the Kangaroo algorithm
private_keys = kangaroo(sorted_smooth_numbers, lookup_table, collision_distance)
if private_keys:
print("Private keys:", private_keys)
break # Exit loop if private keys are found
else:
print("No private keys found. Reloading smooth numbers file and retrying...")
smooth_numbers_data = load_smooth_numbers(file_path)
else:
print("No smooth numbers loaded. Exiting.")
break # Exit loop if no smooth numbers are loaded initially
my question is, is there a better method i could have done implementing index calculus without solving for linear just finding smooth numbers and its exponents, create a table and have kangaroo decipher the private key?
Basically, is my method sound?
your advice are much appreciated.
