# 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

 

def verify(r, s, z, public_key, k):
    # Compute modular inverse of s
    w = modinv(s, n)
    
    # Compute u1 and u2
    u1 = z * w % n
    u2 = r * w % n
    
    # Compute R using the provided x-coordinate r
    R = E.lift_x(r)
    
    # Compute the candidate public key using the provided k value
    candidate_public_key = u1 * public_key + u2 * G
    
    # Check if the x-coordinate of the computed R matches that of the candidate public key
    if R[0] == candidate_public_key[0]:
        print("Signature matches")
        return True
    else:
        print("Invalid signature")
        return False

def verify(r, s, z, public_key, k):
    w = modinv(s, n)
    u1 = z * w % n
    u2 = r * w % n
    R = E.lift_x(r)
    # Compute the candidate public key using the known k value
    candidate_public_key = u1 * G + u2 * R
    if public_key == candidate_public_key:
        print("Signature matches")
        return True
    else:
        print("Invalid signature")
        return False

def find_k_bruteforce(r, s, z, pub):
    i = 1
    max_iterations = 1000  # Add a maximum iteration limit
    while i <= max_iterations:
        k = (r * i + z) * modinv(s, n) % n
        print("i=", i, "k==", hex(k))
        # Verify the signature using the candidate k
        if verify(r, s, z, pub, k):
            print("Found k:", hex(k))
            return k
        else:
            print(f"Attempt {i}: Incorrect k value {hex(k)}")
        i += 1  # Increment i for the next iteration
    raise Exception("Failed to find a valid k value within the maximum iterations")

 import random
import hashlib
from sage.crypto.util import ascii_to_bin
from sage.arith.misc import random_prime
from sage.crypto.util import ascii_to_bin
from sage.crypto.util import bin_to_ascii

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

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

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


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

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)
    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 calc_u(r, s, z):
    mod_s = modinv(s, n) % n
    u1 = mod_s * z % n
    u2 = mod_s * r % n
    print("u1 =", hex(u1), "n-u1 =", hex(n - u1))
    print("u2 =", hex(u2), "n-u2 =", hex(n - u2))
    return u1, u2
u1, u2 = calc_u(r, s, z)

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

    if (r % n) == (x % n):
        print(f"Signature k matches: {hex(k)} ")
        return True
    else:
        print(f"Signature k is invalid {hex(k)} ")
        return False

# Calculate the modular inverse of s (w = s^(-1) mod n)
g, x, y = egcd(s, n)
w = x % n

def find_k(r, s, z, pub):
    # Step 1: Calculate w = s^(-1) mod n
    w = int(modinv(s, n))
    
    # Step 2: Calculate u1 and u2
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    
    # Step 3: Recover the elliptic curve point R
    R = u1 * G + u2 * pub
    
    # Extract x-coordinate from R
    x_R, _ = R.xy()
    x_R = int(x_R)
    
    # Calculate k
    k = (x_R - z) * modinv(w, n) % n
    print("k:",k)
    
    return k

# Call the function to find k
k = find_k(r, s, z, pub1)
print("Found k:", hex(k))

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]))
print("Step 1: Calculate g, x, y using extended Euclidean algorithm")
print("g:", hex(g))
print("x:", hex(x))
print("y:", hex(y))
print("Step 2: Calculate w (modular inverse of s)")
print("Calculated w:", hex(w))
print()


def find_k_bruteforce(r, s, z, pub):
    i = 1
    while True:
        k_candidate = (r * i + z) * modinv(s, n) % n
        
        # Verify the signature using the candidate k
        if verify(r, s, z, pub, k_candidate):
            print("Found k:", hex(k_candidate))
            break
        else:
            print(f"Attempt {i}: Incorrect k value {hex(k_candidate)}")
        
        i += 1  # Increment the attempt counter

# Call the function to find k using brute force
find_k_bruteforce(r, s, z, pub1)

def find_private_key(r, s, z, k, pub):
    # Calculate w = s^(-1) mod n
    w = int(modinv(s, n))
    
    # Calculate u1 and u2
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    
    # Recover the elliptic curve point R
    R = u1 * G + u2 * pub
    
    # Extract x-coordinate from R
    x_R, _ = R.xy()
    x_R = int(x_R)
    
    # Calculate private key d
    d = (k * x_R - z) * modinv(r, n) % n
    
    return d

def find_private_key_bruteforce(r, s, z, k, pub, i):
    k_candidate = (r * i + z) * modinv(s, n) % n
    
    # Calculate private key d
    d = (k_candidate * r - z) * modinv(k_candidate, n) % n
    
    return d

# Call the function to find k using the formula-based approach
k_formula = find_k(r, s, z, pub1)
d_formula = find_private_key(r, s, z, k_formula, pub1)
print("Private key (formula-based):", hex(d_formula))

# Call the function to find k using brute force
k_bruteforce = find_k_bruteforce(r, s, z, pub1)
i_bruteforce = 1
d_bruteforce = find_private_key_bruteforce(r, s, z, k_bruteforce, pub1, i_bruteforce)
print(f"Private key (brute-force attempt {i_bruteforce}):", hex(d_bruteforce))

guessed_k_values = []
i = 1

while True:
    k = (r * i + z) * modinv(s, n) % n
    # Calculate R using the guessed k value
    guessed_R = k * G
    guessed_k_values.append((i, k, guessed_R))

    # Check if the guessed R value matches the original r value
    if guessed_R.xy()[0] == r:
        print(f"The correct k value ({k}) for iteration {i} is found.")
        # Calculate the private key using the correct k value
        d_bruteforce = find_private_key_bruteforce(r, s, z, k, pub1, i)
        print(f"Corresponding private key: {hex(d_bruteforce)}")
        break  # Exit the loop if the correct k is found

    i += 1  # Increment the iteration counter

 

import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

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

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

r=0x00fc5e2ab560be4649b85511940daf8302cf2e2e06bfd60a75c8bae5f832da289c
s=0x45c4c9d548699bbc5f3484a2d6d59ac07ea3328a1deb6b2bb9f2f8f0727be1de
z=0x6559f4e4b8d7824a641418b992f913411a1995fa35668c8c634b5a19a93a944c

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=int(mod_s*z%n)
    u2=int(mod_s*r%n)
    print("u1:",hex(u1) , "n-u1:",hex(n-u1))
    print("u2:",hex(u2) , "n-u2:",hex(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()

i = 1
u_matches = []
while True:
    k = (r * i + z) * modinv(s, n) % n
    print("Invalid nonce K:", hex(k))
    if k == u1:
        print("Match found for u1 at i =", i)
        u_matches.append(("u1", i))
    if k == u2:
        print("Match found for u2 at i =", i)
        u_matches.append(("u2", i))
    if k == (n - u1):
        print("Match found for n - u1 at i =", i)
        u_matches.append(("n - u1", i))
    if k == (n - u2):
        print("Match found for n - u2 at i =", i)
        u_matches.append(("n - u2", i))
    if len(u_matches) == 4:
        print("Matches found for u values:", u_matches)
        break  # Break the loop if matches for all u values are found
    i += 1

import ecdsa
from ecdsa.numbertheory import inverse_mod
import os
# Define the signature parameters
r = 0xXxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
s = 0xXxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
z = 0xabfe1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

# Define the file to store tried k values
k_file = 'tried_k.txt'

# Define the public key
public_key_hex = '02xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
public_key = bytes.fromhex(public_key_hex)

# Define the secp256k1 curve parameters
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x0000000000000000000000000000000000000000000000000000000000000000
b = 0x0000000000000000000000000000000000000000000000000000000000000007
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
curve = ecdsa.SECP256k1

# Define the helper functions
def mod_inv(a, n):
    """Return the modular inverse of a mod n."""
    return inverse_mod(a, n)

def mod_sqrt(a, p):
    """Return the modular square root of a mod p."""
    return pow(a, (p + 1) // 4, p)

# Define the signature point
R = ecdsa.ellipticcurve.Point(curve.curve, r, mod_sqrt((r**3 + a*r + b) % p, p), curve.generator.order())

# Define the function to find the value of k
def get_k(r, s, z):
    """Find the value of k given r, s, and z."""
    
# Load previously tried values of k
    if os.path.exists(k_file):
        with open(k_file, 'r') as f:
            for line in f:
                tried_k.add(int(line.strip()))

    k_candidates = []
    for j in range(1, 2**16):
        # Compute k = (z + j*order) / r
        k = (z + j * curve.generator.order()) * mod_inv(r, curve.generator.order()) % curve.generator.order()
        # Compute the signature point
        P = s * R + (-k % curve.generator.order()) * curve.generator
        # Check if the x-coordinate of the signature point matches r
        if P.x() == r:
            k_candidates.append(k)
        # Print progress message
        if j % 2 == 0:
            print(f"Processed {j} values of j...")
    return k_candidates

# Call the function to get the value of k
k_candidates = get_k(r, s, z)
print(k_candidates)

import ecdsa
import time
import os
from ecdsa import SigningKey, VerifyingKey, SECP256k1
from hashlib import sha256


def nonce_recovery(r, s, z, k_guess, public_key_bytes):
    public_key = VerifyingKey.from_string(public_key_bytes, curve=SECP256k1).to_string()[:32]
    private_key = SigningKey.from_string(public_key, curve=SECP256k1)
    
    # Load previous guesses from a file if it exists
    previous_guesses = set()
    if os.path.exists('previous_guesses.txt'):
        with open('previous_guesses.txt', 'r') as f:
            previous_guesses = set(int(line.strip()) for line in f)
    
    # Load the last guess from a file if it exists, otherwise use the supplied guess
    if os.path.exists('last_guess.txt'):
        with open('last_guess.txt', 'r') as f:
            k_guess = int(f.read())
    
    k_inv = pow(k_guess, -1, SECP256k1.order)
    r_inv = pow(r, -1, SECP256k1.order)
    s_inv = pow(s, -1, SECP256k1.order)
    x = ((z % SECP256k1.order) * s_inv) % SECP256k1.order
    k_guess = ((x * r_inv) % SECP256k1.order) - k_inv
    signature = (r, s)
    while True:
        # Check if the new guess has already been made before
        if k_guess in previous_guesses:
            k_guess += 1
            continue
        
        private_key = SigningKey.from_secret_exponent((k_guess % SECP256k1.order), curve=SECP256k1)
        test_signature = private_key.sign_digest(sha256(str(z).encode()).digest(), sigencode=ecdsa.util.sigencode_der)
        if test_signature == signature:
            return k_guess
        
        # Store the guess in the set of previous guesses
        previous_guesses.add(k_guess)
        
        # Store the last guess in a file
        with open('last_guess.txt', 'w') as f:
            f.write(str(k_guess))
            
        k_guess += 1
        
        # Print progress
        if k_guess % 5 == 0:
            print(f"Cracking: {k_guess}")
            
        # Sleep for a short time to avoid overwhelming the console
        time.sleep(0.01)

# Example usage:
r = 0x00e1dexxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
s = 0x1dd56xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
z = 0xabfe106fbxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
k_guess = 1000000000
public_key= bytes.fromhex('0245axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx')
result = nonce_recovery(r, s, z, k_guess, public_key)
print(result)