Pairing Based Signature Scheme

[kiefer]

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)