I had made a little change in my code. im just hoping i could receive some advice on whether my method here is more efficient or sound?
originally, i had searh the k nonce using hexadecimal and after 6 weeks, i got the right nonce. i got really lucky by the way because i was told that 6 weeks was really fast. but.. im hoping to go faster.
so my question is, does doing the search in binary help to recover k nonce faster ?
if it does, please take a look at my code in sagemath, and see what i might have miss out or can improve to make it much better?
and while im here, i was told the u1 value some sort of give a "hint" on the k nonce. i realise that it just really is the real mod n of k nonce only but its not k nonce itself,
so my 3rd question is, after finding out the value of u1, how can i use this input to make the search for the k nonce faster?
import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [0, 7])
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)
#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")
r=0x
s=0x
z=0x
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.xy() == r
def search_k():
# Iterate to find the correct k in binary format
for i in range(1, 2**256):
k = (r * i + z) * modinv(s, n) % n
k_bin = format(k, '0256b') # Convert k to 256-bit binary format
print("Binary",k_bin)
if check_k(k):
print(f"Found correct k in binary format: {k_bin}")
private_key = (s * k - z) * modinv(r, n) % n
print(f"Private Key: {private_key}")
break
search_k()