Topic: Index Calculus Algorithm to find private key (Read 201 times)
Your Index Calculus Algorithm looks pretty good. As for how to increase efficiency, for large data sets it is necessary to manage core utilization with threads or processes. SymPy, which is supposed to be that powerful and elegant, memory use is higher than desired; Try some lighter alternatives. Variations in factor base and chunk size may be used as experiments to see which brings a better performance. Further, delves into improving speed by applying some modular mathematics optimizations. You can think about whether there are algorithmic tweaks and whether you need special libraries to assist in these tasks. By making improvements in this direction, your implementation can advance still further.
Your Index Calculus Algorithm looks pretty good. As for how to increase efficiency, for large data sets it is necessary to manage core utilization with threads or processes. SymPy, which is supposed to be that powerful and elegant, memory use is higher than desired; Try some lighter alternatives. Variations in factor base and chunk size may be used as experiments to see which brings a better performance. Further, delves into improving speed by applying some modular mathematics optimizations. You can think about whether there are algorithmic tweaks and whether you need special libraries to assist in these tasks. By making improvements in this direction, your implementation can advance still further.
thannk you so much. i will look into it.
Quote
How many operations alghorith take for 2**76 privkey ?
here, this code is for you guys who wanna try it on smaller values. you just need to adjust the values and curves accordingly.
https://github.com/david-r-cox/pyDLP
Can you show in practice what your code does with some small values?
the index calculus algorithm is only meant for exponential numbers. it cant be done with small values.
How many operations alghorith take for 2**76 privkey ?
Can you show in practice what your code does with some small values?
the index calculus algorithm is only meant for exponential numbers. it cant be done with small values.
Can you show in practice what your code does with some small values?
Hi everyone, i am wondering whether is there any other way or is there a better way i could have implemented in my Index Calculus Algorithm or is this the best optimization i could have done already? Would like some suggestions please. My code is as below.
from sympy import Matrix
import numpy as np
import multiprocessing as mp
# Define Montgomery power function for secp256k1
def montgomery_power(base, exp, mod):
res = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
res = (res * base) % mod
exp = exp >> 1
base = (base * base) % mod
return res
# Function to generate a prime factor base
def generate_factor_base(limit):
primes = []
num = 2
while len(primes) < limit:
if all(num % i != 0 for i in range(2, int(num**0.5) + 1)):
primes.append(num)
num += 1
return primes
# Precompute the factor base
factor_base_size = 100
factor_base = generate_factor_base(factor_base_size)
# Function to find smooth numbers in a range (optimized further)
def find_smooth_numbers(start, end):
smooth_numbers = []
for num in range(start, end + 1):
exps = []
for p in factor_base:
count = 0
while num % p == 0:
count += 1
num //= p
exps.append(count)
if num == 1:
smooth_numbers.append((num, exps))
return smooth_numbers
# Function to solve linear equations using Lanczos algorithms
def solve_linear_equations(smooth_nums, G, n):
A = Matrix([[f[1][i] for f in smooth_nums] for i in range(factor_base_size)]).T
B = Matrix([G**f[0] % n for f in smooth_nums])
X = A.LUsolve(B)
logs = [(p, int(X[i])) for i, p in enumerate(factor_base)]
return logs
# Function for multiprocessing
def process_range(args):
start, end, G, n = args
print(f"Processing range: {start}-{end}")
smooth_nums = find_smooth_numbers(start, end)
print(f"Found {len(smooth_nums)} smooth numbers in range {start}-{end}")
return solve_linear_equations(smooth_nums, G, n)
# Use freeze_support for multiprocessing
if __name__ == '__main__':
mp.freeze_support()
# Parameters for secp256k1 curve and public key
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
pub_key_x = 0x26597xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
pub_key_y = 0x158b6xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
pub_point = (pub_key_x, pub_key_y)
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), Gx, n) for i in range(1, n + 1, chunk_size)]
# Perform multiprocessing
with mp.Pool(processes=num_chunks) as pool:
logs_list = pool.map(process_range, ranges)
# Combine results from multiprocessing
logs = []
for logs_chunk in logs_list:
logs.extend(logs_chunk)
# Calculate private key using index calculus
d = 1
for p, a in logs:
while montgomery_power(pub_point[0], d * a, p) != 1:
d += 1
if d >= n:
break
print(f"Private Key (d): {d}")
Code:
from sympy import Matrix
import numpy as np
import multiprocessing as mp
# Define Montgomery power function for secp256k1
def montgomery_power(base, exp, mod):
res = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
res = (res * base) % mod
exp = exp >> 1
base = (base * base) % mod
return res
# Function to generate a prime factor base
def generate_factor_base(limit):
primes = []
num = 2
while len(primes) < limit:
if all(num % i != 0 for i in range(2, int(num**0.5) + 1)):
primes.append(num)
num += 1
return primes
# Precompute the factor base
factor_base_size = 100
factor_base = generate_factor_base(factor_base_size)
# Function to find smooth numbers in a range (optimized further)
def find_smooth_numbers(start, end):
smooth_numbers = []
for num in range(start, end + 1):
exps = []
for p in factor_base:
count = 0
while num % p == 0:
count += 1
num //= p
exps.append(count)
if num == 1:
smooth_numbers.append((num, exps))
return smooth_numbers
# Function to solve linear equations using Lanczos algorithms
def solve_linear_equations(smooth_nums, G, n):
A = Matrix([[f[1][i] for f in smooth_nums] for i in range(factor_base_size)]).T
B = Matrix([G**f[0] % n for f in smooth_nums])
X = A.LUsolve(B)
logs = [(p, int(X[i])) for i, p in enumerate(factor_base)]
return logs
# Function for multiprocessing
def process_range(args):
start, end, G, n = args
print(f"Processing range: {start}-{end}")
smooth_nums = find_smooth_numbers(start, end)
print(f"Found {len(smooth_nums)} smooth numbers in range {start}-{end}")
return solve_linear_equations(smooth_nums, G, n)
# Use freeze_support for multiprocessing
if __name__ == '__main__':
mp.freeze_support()
# Parameters for secp256k1 curve and public key
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
pub_key_x = 0x26597xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
pub_key_y = 0x158b6xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
pub_point = (pub_key_x, pub_key_y)
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), Gx, n) for i in range(1, n + 1, chunk_size)]
# Perform multiprocessing
with mp.Pool(processes=num_chunks) as pool:
logs_list = pool.map(process_range, ranges)
# Combine results from multiprocessing
logs = []
for logs_chunk in logs_list:
logs.extend(logs_chunk)
# Calculate private key using index calculus
d = 1
for p, a in logs:
while montgomery_power(pub_point[0], d * a, p) != 1:
d += 1
if d >= n:
break
print(f"Private Key (d): {d}")
Jump to: