Topic: Nonce Recovery (Read 987 times)

 

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)