I would just like to open a technical discussion about K nonce in ECDSA SECP256k1.
There are mathematical methods to solve for k.
One common mathematical method is called the "Gauss's algorithm". This algorithm can solve for k given the values of r, s, z, and the public key. However, it involves some complex mathematical operations.
Another approach is to use the "Fermat's little theorem". This theorem states that if p is a prime number, then for any integer a, a raised to the power of p minus one is congruent to 1 modulo p, i.e., a^(p-1) = 1 (mod p). In the context of ECDSA, this means that if we have the values of r, s, and z, we can solve for k using the following formula:
k = (z / s)^(1/(p-1)) % p
where p is the order of the curve. However, this formula assumes that the curve order is known, and that s is not equal to 0. Am i right?
In any case, here is my python code for the Gaussian Algorithm
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)
And here for the Fermat's little theorem
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)
If there is anything i can do to optimise my program further. please do advise me. thank you.