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 :=> " + hex(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 _forgSignature(r, s, z, bits = 256):
   newR, newS, newZ = 0, 0, 0

   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 int(newR), int(newS), int(newZ)

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

def getk1(r1, s1, z1, r2, s2, z2, m):
   nr = (s2 * m * r1 + z1 * r2 - z2 * r1) % q
   dr = (s1 * r2 - s2 * r1) % q

   return (nr * pow(dr, q - 2, q)) % q

def getpvk(r1, s1, z1, r2, s2, z2, m):
   x1 = (s2 * z1 - s1 * z2 + m * s1 * s2) % q
   xi = pow(s1 * r2 - s2 * r1, q - 2, q) % q
   x = (x1 * xi) % q

   return x

while True:
   try:
      nonce1 = secrets.randbelow(int(q))

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

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

      r2, s2, z2 = forgeSignature(r1, s1, z1, 252)

      nonce1 = lift(mod((z1 + privateKey * Integer(r1)) * inverse_mod(s1, q), q))

      nonce2 = lift(mod((z2 + privateKey * Integer(r2)) * inverse_mod(s2, q), q))

      diff = (int(nonce2) - int(nonce1)) % q

      k = getk1(r1, s1, z1, r2, s2, z2, diff)
      x = getpvk(r1, s1, z1, r2, s2, z2, diff)

      print()

      print(f'Recovered Private Key :=> {hex(x)}')
      
      break;
   except:
      """"""