Pairing Based Signature Scheme

During the sage coding sprint of ECC11 we worked on a simple pairing based signature scheme. We propose to implement functionality, roughly following these lines in the future (more secure ;)):

import md5

x = 2^128+108 #2^26+39
r = x^2 - x + 1
t = x^2 - x + 1
q = Integer(1/3*(x-1)^2*(x^2-x+1)+x^3)

_.<x> = GF(q)[]
F.<a>=GF(q^2, 'z', modulus=x^2+1)
E=EllipticCurve(F,[0,20])

P = E.random_point()
Q = E.random_point()
c = Integer((q^2+1-t^2+2*q)/(r^2))
P = c*P
Q = c*Q

m = 'hallo'
hash = md5.md5(m)
n = hash.hexdigest()

n = Integer(n, 16)
sec = 15
pub = Q*sec

sig = ((1/(n+sec)) % r)*P

v = (n*Q+pub)

vrfy = sig.weil_pairing(v, r)
vrfy2 = P.weil_pairing(Q, r)

if (vrfy == vrfy2) : 
    print("Signature is valid :)")
else :
    print("Signature is NOT valid :(")

For choosing x you can try something like:

for i in range(-1000,1000):
    x = 2^128+i
    r = x^2 - x + 1
    t = x^2 - x + 1
    q = 1/3*(x-1)^2*(x^2-x+1)+x^3
    q = ceil(q)
    if ((q%4) == 3) :
        if (is_prime(q)) :
            print(q,i)

CC: @sagetrac-karzdorf

Component: cryptography

Keywords: pairing, signature, ecc2011

Author: kiefer, karzdorf, edward knapp

Issue created by migration from https://trac.sagemath.org/ticket/11803

sagemath / sage

Pairing Based Signature Scheme #11803