import random
import sys

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 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")
        return 1
    else:
        print("invalid signature",r,x%n,hex(int(x%n)))
        return -1
    
def decom(e):
    e_arr = []

    for i in range(256):
        e_arr.append(e % 2**1)
        e = e >> 1

    e_arr.reverse()
    return e_arr

def create_table(t):
    table_i_0={}
    table_i_1={}
    
    for i in range(0,t):
        a1=random.randrange(1,n)
        a2=random.randrange(1,n)
        table_i_0[i]=(G*a1,a1)
        table_i_1[i]=(G*a2,a2)
    return table_i_0,table_i_1

def make_r_of_hash(hash_values,tableG_0,tableG_1,t):
    decomp_hash=decom(hash_values)
    e1=decomp_hash[0]
    #Round 1
    G10,k10=tableG_0[0]
    G11,k11=tableG_1[0]
    #Round 2
    R=(1-e1)*G10+e1*G11
    k=((1-e1)*k10+e1*k11)%n
    for i in range(1,t):
        Gi0,k1i=tableG_0[i]
        G1i,ki1=tableG_1[i]
        ei= decomp_hash[i]
        R=R+(1-ei)*Gi0+ei*G1i
        k=(k+(1-ei)*k1i+ei*ki1)%n
    return R,k    


def sign_transaction(privkey,message,rounds):
    z=message
    tableG_i_0,tableG_i_1=create_table(rounds)
    
    R,nonce=make_r_of_hash(z,tableG_i_0,tableG_i_1,rounds)
    r=R.xy()[0]
    r=int(r)
    s=(z+int(r)*privkey)*modinv(nonce,n)%n
    return int(r), int(s), int(z),nonce


  


pr=100
message= random.randrange(1,n)
rounds=10
r,s,z,nonce=sign_transaction(pr,message,rounds)
verify(r,s,z,pr*G)
print("trans #1")
print("nonce=",nonce)
print("r=",r)
print("s=",s)
print("z=",z)

pr=100
message= random.randrange(1,n)
rounds=4
r,s,z,nonce=sign_transaction(pr,message,rounds)
verify(r,s,z,pr*G)
print()
print("trans #2")
print("nonce=",nonce)
print("r=",r)
print("s=",s)
print("z=",z)