Nonce Recovery

[krashfire]

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

Code:

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

Code:

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.

[sha420hashcollision]

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?

Of course the order of the curve is known, order is a public variable.
https://en.bitcoin.it/wiki/Secp256k1
You may be overthinking something.

[sha420hashcollision]

you can get the private key directly from the s value.
1) restore original s value that it was before mod n operation.
2) factor the restored value of s into two multipliers (one is multiplicative inverse of k, the other is z+r*privkey).
3) since we know z,r we can ((z+r*privkey)-z)/r and we get the private key.

the only problem is that we cannot factor numbers that are so large as pure s value before mod operation in reasonable time span yet.
quantum computers and Shor's algorithm could do the trick but that will not happen soon.

https://en.wikipedia.org/wiki/Discrete_logarithm#Comparison_with_integer_factorization
The crux of this heuristic is that even if you could come up with a method for solving them it would be incredibly computationally intensive and would likely cost more to break than the reward would hold.
So far they cannot get more than 100 qubits on a quantum computer which cannot break low bit RSA. Looks safe to me.

[Darkenman]

in this way it is waste the time (your time).

if you want to understand the curve you need understand the algorithm for sign transaction.

example in this way for understanding the real algorithm of sign transaction:

privatekey = 4
nonce = 6
message_hash=2

after signing : we have r,s,z (remember z == message_hash)
so:

Code:

r= 115780575977492633039504758427830329241728645270042306223540962614150928364886 
s= 115784413730767153834193500621449522112098284939719838943229029456606672741370 
z= 2

now you must : calculate u1,u2

Code:

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

result:

Code:

u1== 57446123528476574921383425882760106825160817048876048499830450377360758406696 n-u1 = 58345965708839620502187559125927801027676747230198855882774712764157403087641
u2== 43534513736538953981439636033653927220128577877318440066344968976418891145496 n-u2 = 72257575500777241442131348975033980632708986401756464316260194165099270348841

now generate :

Code:

for i in range(1,10):
    k=(r*i+z)*modinv(s,n)%n
    print("i=",i,"k==",k) 

result:

Code:

i= 1 k== 100980637265015528902823061916414034045289394926194488566175419353779649552192
i= 2 k== 28723061764238287460691712941380053412580408524438024249915225188680379203351
i= 3 k== 72257575500777241442131348975033980632708986401756464316260194165099270348847  -> this compare with n-u2
i= 4 k== 6
i= 5 k== 43534513736538953981439636033653927220128577877318440066344968976418891145502  -> this compare with u2
i= 6 k== 87069027473077907962879272067307854440257155754636880132689937952837782290998
i= 7 k== 14811451972300666520747923092273873807548169352880415816429743787738511942157
i= 8 k== 58345965708839620502187559125927801027676747230198855882774712764157403087653  -> this compare with n-u1
i= 9 k== 101880479445378574483627195159581728247805325107517295949119681740576294233149

and: 57446123528476574921383425882760106825160817048876048499830450377360758406696  as u1 -> is real mod n as

thos tricks and little maths -> can break all transactions:)

happy hunting

ps. IF any question ask ( of course for money)

I Am really Like you
How i can use it ?
I try with python and sage math but not working

[digaran]

Yo krash sup? Can you give me the rsz, or how do I extract them from a TX, do you have a script for that?

[digaran]

I tried this, and it has no advantage over a simple brute force algorithm, I can't tell if this can actually work, however even if it works, there is no scientific discovery behind it, you'd only be able to solve weakly generated keys and grab people's coins. If you want to work honestly and with honor, try to come up with something that works with elliptic curves, not finding k from transaction.

[krashfire]

@krashfire it works, but you need more knowledge -> write PM

the correct code

Code:

 

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