import hashlib
import secrets
import libnum

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)

q = E.order()

privateKey = secrets.randbelow(int(q))

pub = privateKey * G

print("Private Key :=> " + str(privateKey))

def sign(m, d, k = None):
   z = int.from_bytes(hashlib.sha256(m).digest(), 'big')
   
   if k == None:
      k = secrets.randbits(256)
   
   P = k * G
   x1 = int(P.xy()[0])

   r = int(x1 % q)
   s = int(pow(k, -1, q) * (z + r * d) % q)
   
   return (r, s, z)

def _forgeSignature(r, s, z, bits = 256):
   newR, newS, newZ = None, None, None

   R = E.lift_x(Integer(r))

   r_ = int(((int(pow(4, -1, q)) * int(2 ** bits - 1) * G) - (int(pow(4, -1, q)) * R)).xy()[0])
   s_ = int((-r_ * s * int(pow(r, -1, q)) * 4) % q)
   z_ = int(int(pow(4, -1, q)) * s_ * int(2 ** bits - 1 - int(pow(s, -1, q)) * z) % q)
   
   w_ = pow(s_, -1, q)
   
   u1_ = int(z_ * w_ % q)
   u2_ = int(r_ * w_ % q)
   
   if (u1_ * G + u2_ * pub).xy()[0] == r_:
      newR = r_
      newS = s_
      newZ = z_

   return newR, newS, newZ

def forgeSignature(r, s, z, bits = 256):
   newR, newS, newZ = _forgeSignature(r, s, z, bits)
   
   return newR, newS, newZ

nonce = secrets.randbelow(int(q))

print("\nNonce :=> " + str(nonce))

r1, s1, z1 = sign(b'Hello World 1', privateKey, nonce)

r2, s2, z2 = sign(b'Hello World 2', privateKey, nonce)

r1, s1, z1 = forgeSignature(r1, s1, z1)

r2, s2, z2 = forgeSignature(r2, s2, z2)

temp = libnum.invmod((s1 - s2), q)

recoveredK = ((z1 - z2) * temp) % q

print("\n\nRecovered K :=> " + str(recoveredK))

recoveredPriv = (libnum.invmod(r1, q) * ((s1 * recoveredK) - z1)) % q

print("\nRecovered PrivateKey :=> " + str(recoveredPriv))

if privateKey == recoveredPriv:
   print("\nSuccessfully Recovered")