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}")

import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

E = EllipticCurve(GF(p), [0, 7])

G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8))   # Base point

r=0x
s=0x
z=0x

def egcd(a, b):

    if a == 0:

        return (b, 0, 1)

    else:

        g, y, x = egcd(b % a, a)

        return (g, x - (b // a) * y, y)
def modinv(a, m):

    g, x, y = egcd(a, m)

    if g != 1:

        raise Exception('modular inverse does not exist')

    else:

        return x % m
def make_public(r,s,z):
    R = E.lift_x(Integer(r))
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    #R=u1*G + u2*public_key
    #pub= R*modinv(u2,n) - u1*modinv(u2,n)%n
    u_n2=modinv(u2,n)%n
    u_n1=- u1*modinv(u2,n)%n
    
    pub=u_n1*G + u_n2*R
    pub2=u_n1*G + u_n2*(-R)
    return pub,pub2

def verify(r, s,z,public_key):
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    D=u1*G + u2*public_key
    x,y=D.xy()
    x=int(x)

    if (r % n) == (x % n):
        print( "signature matches")
         
    else:
        print("invalid signature")
        
def calc_u(r,s,z):
    mod_s= modinv(s,n)%n
    u1=mod_s*z%n
    u2=mod_s*r%n
    print("u1==",u1,"n-u1=",n-u1)
    print("u2==",u2,"n-u2=",n-u2)
    return u1,u2
u1, u2 = calc_u(r,s,z)
pub1,pub2=make_public(r,s,z)

print("public_key1",pub1)
print("pub1_x=",hex(pub1.xy()[0]))
print("public_key2",pub2)
print("pub2_x=",hex(pub2.xy()[0]))
verify(r,s,z,pub1)
verify(r,s,z,pub2)
print()

# Find the real mod n for k and K nonce
# Loop to search for k in hexadecimal
for i in range(0, n):
    k = (r * i + z) * modinv(s, n) % n
    R = E.lift_x(Integer(r))
    P = k * G
    print("K:", hex(P.xy()[0]))  # Print the x-coordinate of K in hexadecimal
    if hex(P.xy()[0]) == hex(r):
        print("Found real k:", hex(P.xy()[0]))  # Print the real k in hexadecimal
        break

import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

E = EllipticCurve(GF(p), [0, 7])

G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8))   # Base point

r=0x
s=0x
z=0x

def egcd(a, b):

    if a == 0:

        return (b, 0, 1)

    else:

        g, y, x = egcd(b % a, a)

        return (g, x - (b // a) * y, y)
def modinv(a, m):

    g, x, y = egcd(a, m)

    if g != 1:

        raise Exception('modular inverse does not exist')

    else:

        return x % m
def make_public(r,s,z):
    R = E.lift_x(Integer(r))
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    #R=u1*G + u2*public_key
    #pub= R*modinv(u2,n) - u1*modinv(u2,n)%n
    u_n2=modinv(u2,n)%n
    u_n1=- u1*modinv(u2,n)%n
    
    pub=u_n1*G + u_n2*R
    pub2=u_n1*G + u_n2*(-R)
    return pub,pub2

def verify(r, s,z,public_key):
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    D=u1*G + u2*public_key
    x,y=D.xy()
    x=int(x)

    if (r % n) == (x % n):
        print( "signature matches")
         
    else:
        print("invalid signature")
           
def calc_u(r,s,z):
    mod_s= modinv(s,n)%n
    u1=mod_s*z%n
    u2=mod_s*r%n
    print("u1==",u1,"n-u1=",n-u1)
    print("u2==",u2,"n-u2=",n-u2)
    return u1,u2
u1, u2 = calc_u(r,s,z)

pub1,pub2=make_public(r,s,z)
print("public_key1",pub1)
print("pub1_x=",hex(pub1.xy()[0]))
print("public_key2",pub2)
print("pub2_x=",hex(pub2.xy()[0]))
verify(r,s,z,pub1)
verify(r,s,z,pub2)
print()

# Find the real mod n for k and K nonce

for i in range(1, n):
    k = (r * i + z) * modinv(s, n) % n
    R = E.lift_x(Integer(r))
    K = k * G
    u1 = (modinv(s, n) * z) % n
    u2 = (modinv(s, n) * r) % n
    if K == (u1 * G + u2 * R):
        print("Found real k:", k)
        break

import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

E = EllipticCurve(GF(p), [0, 7])

G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8))

r=0x
s=0x
z=0x

def egcd(a, b):

    if a == 0:

        return (b, 0, 1)

    else:

        g, y, x = egcd(b % a, a)

        return (g, x - (b // a) * y, y)
def modinv(a, m):

    g, x, y = egcd(a, m)

    if g != 1:

        raise Exception('modular inverse does not exist')

    else:

        return x % m

def make_public(r,s,z):
    R = E.lift_x(Integer(r))
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    #R=u1*G + u2*public_key
    #pub= R*modinv(u2,n) - u1*modinv(u2,n)%n
    u_n2=modinv(u2,n)%n
    u_n1=- u1*modinv(u2,n)%n
    
    pub=u_n1*G + u_n2*R
    pub2=u_n1*G + u_n2*(-R)
    return pub,pub2

def verify(r, s,z,public_key):
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    D=u1*G + u2*public_key
    x,y=D.xy()
    x=int(x)

    if (r % n) == (x % n):
        print( "signature matches")
         
    else:
        print("invalid signature")

pub1,pub2=make_public(r,s,z)

print("public_key1",pub1)
print("pub1_x=",hex(pub1.xy()[0]))
print("public_key2",pub2)
print("pub2_x=",hex(pub2.xy()[0]))

verify(r,s,z,pub1)
verify(r,s,z,pub2)
print()

# Function to check if a point's x-coordinate matches r
def check_k(k):
    P = k * G
    return P.x() == r

# Iterate to find the correct k
for i in range(1, n):
    k = (r * i + z) * modinv(s, n) % n
    if check_k(k):
        print(f"Found correct k: {k}")
        private_key = (s * k - z) * modinv(r, n) % n
        print(f"Private Key: {private_key}")
        break