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=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
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()

# Find the real mod n for k and K nonce
# Loop to search for k in hexadecimal
for i in range(0, n):
    k = (r * i + z) * modinv(s, n) % n
    R = E.lift_x(Integer(r))
    P = k * G
    print("K:", hex(P.xy()[0]))  # Print the x-coordinate of K in hexadecimal
    if hex(P.xy()[0]) == hex(r):
        print("Found real k:", hex(P.xy()[0]))  # Print the real k in hexadecimal
        break