MAGK3

def GenerateCurve(k, z):
    #p + N + T
    p = 4 * z ** 2 + 1
    r1 = 4 * z ** 2 - 2 * z + 1
    r2 = 4 * z ** 2 + 2 * z + 1
    if r1 in Primes():
        r = r1
        T = 1 + 2 * z
    elif r2 in Primes():
        r = r2
        T = 1 - 2 * z
    #discr + j-inv
    D = 4 * p - T ** 2
    polynomHilb = hilbert_class_polynomial(-D)
    K = GF(p)
    j_invariants = polynomHilb.roots(K, multiplicities = False)
    j = j_invariants[0]
    #coefs
    A = K(3 * j / (1728 - j))
    B = K(2 * j / (1728 - j))
    #EC
    E = EllipticCurve(K, [A, B])
    if E.order() != r:
        return 0, 0, 0, 0, 0
    KK.<t> = GF(p**k)
    Ek = EllipticCurve(KK, [A, B])
    if gcd(Ek.order(), r**2) == 1:
        return 0, 0, 0, 0, 0
    return E, Ek, T, r, j

def CreatePoint(E, ord, flag):
    if flag == 0:
        point = E.random_point()
        while 1:
            if point.order() == ord:
                return point
            point = E.random_point()
    elif flag == 6:
        point = E.random_point()
        while 1:
            if point.order() == ord:
                return point
            else:
                point *= E.order() // ord ** 2
                if point.order() == ord:
                    return point
            point = E.random_point()

def CreateTorsionGroup(P1, P2, r):
    tors = list()
    for i in range(1, 3):
        j = list()
        for k in range(1, r):
            j.append(i * P1 + k * P2)
        tors.append(j)
    return tors

def Tate(EK, tors, k, r):
    R = tors[0][0]
    S = tors[0][1]
    T = tors[0][2]
    print("R = {}".format(R))
    print("S = {}".format(S))
    print("T = {}\n".format(T))
    RS = R + S
    RST1 = RS.tate_pairing(T, r, k)
    RT = R.tate_pairing(T, r, k)
    ST = S.tate_pairing(T, r, k)
    RST2 = RT * ST
    print("e(R + S, T) = {}".format(RST1))
    print("e(R,T) * e(S, T) = {}".format(RST2))
    if RST1 == RST2:
        print("Bilinear\n")
    P0 = EK([0, 1, 0])
    RP = R.tate_pairing(P0, r, k)
    PR = P0.tate_pairing(R, r, k)
    print("RP: {}".format(PR))
    print("PR: {}".format(RP))
    if RP == 1 and PR == 1:
        print("Non-degeneracy\n")
    Z = T.tate_pairing(T, r, k)
    print("Value: {}".format(Z))
    if Z == 1:
        print("Alternating")

def Weil(EK, tors, r):
    R = tors[0][1]
    S = tors[0][2]
    T = tors[0][3]
    print("R = {}".format(R))
    print("S = {}".format(S))
    print("T = {}\n".format(T))
    RS = R + S
    RST1 = RS.weil_pairing(T, r)
    RT = R.weil_pairing(T, r)
    ST = S.weil_pairing(T, r)
    RST2 = RT * ST
    print("e(R+S, T) = {}".format(RST1))
    print("e(R, T) * e(S, T) = {}".format(RST2))
    if RST1 == RST2:
        print("Bilinear\n")
    P0 = EK([0, 1, 0])
    RP = R.weil_pairing(P0, r)
    PR = P0.weil_pairing(R, r)
    print("RP: {}".format(PR))
    print("PR: {}".format(RP))
    if RP == 1 and PR == 1:
        print("Non-degeneracy")
    Z = T.weil_pairing(T, r)
    print("Value: {}".format(Z))
    if Z == 1:
        print("Alternating")

def Hash(message, i):
    s = 0
    for m in message:
        s = s + ord(m)
    return s % i

def func(mes, EK):
    p = int(EK.base_field().characteristic())
    A = int(EK.a4())
    B = int(EK.a6())
    for i in range(2, p):
        h = Hash(mes, i)
        t = kronecker_symbol(h**3 + A*h + B, p)
        if t == 1:
            var('y')
            x = h
            E = x**3 + A*x + B == y**2
            y_res = E.roots(ring = GF(p), multiplicities = False)
            yr = y_res[randint(0, p) % len(y_res)]
            try:
                P = EK([h, yr])
                return P
            except:
                continue
    P0 = EK([0,1,0])
    return P0


def CreateSign(mes, E, tors, r):
    print("Create signature for message: {}".format(mes))
    res = list()
    M = func(mes, E)
    a = randint(1, r - 1)
    res.append(a * M)
    P = tors[0][0]
    res.append(a * P)
    res.append(P)
    print("Signature = {}".format(res[0][0]))
    print("Key = {}".format(res[1]))
    return res


def CheckSS(mes, E, r, x, P, T):
    print("Check signature for message: {}".format(mes))
    p = E.base_field().characteristic()
    A = E.a4()
    B = E.a6()
    try:
        y = GF(p)(x ** 3 + A * x + B)
        y = GF(p)(sqrt(y))
        S = E([x, y, 1])
    except:
        y = GF(p)(x ** 3 + A * x + B)
        y = GF(p)(sqrt(y))
        y = GF(p)(-y)
        S = E([x, y, 1])
    M = func(mes, E)
    P1 = P.weil_pairing(S, r)
    P2 = T.weil_pairing(M, r)
    if P1 == P2 or P1 == P2^(-1):
        print("Right signature")
    else:
        print("Message was changed")

def main():
    k = 6
    z = 10
    E, Ek, T, r, j = GenerateCurve(k, z)
    print("z: {}" . format(z))
    print("E: {}" . format(E))
    print("Ek: {}" . format(Ek))
    print("T: {}" . format(T))
    print("r: {}" . format(r))
    print("j: {}" . format(j))

    #Points for torsion group
    P1 = CreatePoint(E, r, 0)
    P2 = CreatePoint(Ek, r, 6)
    print("P1: {}" . format(P1))
    print("P2: {}\n" . format(P2))

    P1 = Ek(list([P1[0], P1[1], P1[2]]))
    F.<t> = GF(Ek.base_field().characteristic()).extension(k)
    F = Ek.base_field()
    P2x = F(P2[0])
    P2y = F(P2[1])
    P2z = F(P2[2])
    P2 = Ek(list([P2x, P2y, P2z]))

    TorsGroup = CreateTorsionGroup(P1, Ek(P2), r)
    #print("Tors: {}\n" . format(TorsGroup))
    print("Tate pairing:")
    Tate(Ek, TorsGroup, k, r)
    print("Weil pairing:")
    Weil(Ek, TorsGroup, r)
    print("Short signature:")
    message = "Hello there"
    SSResult = CreateSign(message, Ek, TorsGroup, r)
    mess = "He"
    CheckSS(mess, Ek, r, SSResult[0][0], SSResult[2], SSResult[1])
#main
main()