Title: Index Calculus Kangaroo Method to find 256 bit private key.
Post by: krashfire on May 07, 2024, 12:46:50 AM
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.
Title: Re: Index Calculus Kangaroo Method to find 256 bit private key.
Post by: COBRAS on May 07, 2024, 12:53:41 AM
Hello, this scrypt find privkey or not ?
I was try your previous scrypt and hi find for me only smoth numbers ...
Title: Re: Index Calculus Kangaroo Method to find 256 bit private key.
Post by: krashfire on May 07, 2024, 01:18:45 AM
Hello, this scrypt find privkey or not ?
I was try your previous scrypt and hi find for me only smoth numbers ...
this code is still in the experimental phase. i am not sure if it is sound. thats why i am here
|