""" Fotiadis-Konstantinou curve with k=8, rho=2 and D=4 From the papers https://eprint.iacr.org/2018/1017.pdf (for the curves) k = 8; D = 4; rho = 2; #quartic twists, V = [x, -1, 0, 0], x = 0 (mod 2) px = (x^8 + x^6 + 5*x^4 + x^2 + 4*x + 4)/4 rx = x^4 + 1 tx = x^4 + x + 2 yx = (x^3 - x^2)/2 #remove the /2 if you consider D=1 cx = (x^4+x^2)/4 beta = (x^6 - x^5 - 2*x^3 + 3*x^2 - 3*x - 2)/4 lamb = x^2 and https://eprint.iacr.org/2018/969.pdf https://eprint.iacr.org/2019/555.pdf (for pairing computation estimates) """ Rx = [1, 0, 0, 0, 1] # u^4 + 1 Rx_den = 1 Tx= [2, 1, 0, 0, 1] Tx_den = 1 Px = [4, 4, 1, 0, 5, 0, 1, 0, 1] Px_den = 4 Yx = [0, 0, -1, 1] Yx_den = 2 Cx = [0, 0, 1, 0, 1] Cx_den = 4 BETAx = [-2, -3, 3, -2, 0, -1, 1] BETAx_den = 4 LAMBx = [0,0,1] # x^2 mod r(x) = x^4+1 LAMBx_den = 1 import sage from exceptions import ValueError from sage.functions.log import log from sage.functions.other import ceil from sage.functions.other import sqrt from sage.arith.misc import XGCD, xgcd from sage.rings.integer import Integer from sage.rings.finite_rings.finite_field_constructor import FiniteField from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field from sage.schemes.elliptic_curves.constructor import EllipticCurve import PairingFriendlyCurve from PairingFriendlyCurve import get_curve_parameter_a_j1728, get_curve_generator_order_r_j1728 from PairingFriendlyCurve import print_parameters, print_parameters_for_RELIC class FK8D4(EllipticCurve_finite_field): """ A Fotiadis-Konstantinou curve of embedding degree k=8, D=4, rho=2 https://eprint.iacr.org/2018/1017 """ def __init__(self, u, a=None): """ u is the seed s.t. p=P(u), r=R(u), t=T(u) :param u : seed :param a : curve parameter in E: y^2 = x^3 + a*x (optional) """ self._k = 8 # embedding degree self._D = 4 # curve discriminant self._b = 0 self._u = Integer(u) # see bottom of file for formulas self.polynomial_r = [1, 0, 0, 0, 1] # u^4 + 1 self.polynomial_r_denom = Integer(1) self.polynomial_tr= [2, 1, 0, 0, 1] self.polynomial_tr_denom = Integer(1) self.polynomial_p = [4, 4, 1, 0, 5, 0, 1, 0, 1] self.polynomial_p_denom = Integer(4) self.polynomial_y = [0, 0, -1, 1] self.polynomial_y_denom = Integer(2) self.polynomial_c = [0, 0, 1, 0, 1] self.polynomial_c_denom = Integer(4) self.polynomial_beta = [-2, -3, 3, -2, 0, -1, 1] self.polynomial_beta_denom = Integer(4) self.polynomial_lamb = [0,0,1] # x^2 mod r(x) = x^4+1 self.polynomial_lamb_denom = Integer(1) self._p = sum([Integer(self.polynomial_p[i])*self._u**i for i in range(len(self.polynomial_p))])//self.polynomial_p_denom self._pbits = self._p.nbits() self._r = sum([Integer(self.polynomial_r[i])*self._u**i for i in range(len(self.polynomial_r))])//self.polynomial_r_denom self._c = sum([Integer(self.polynomial_c[i])*self._u**i for i in range(len(self.polynomial_c))])//self.polynomial_c_denom self._tr= sum([Integer(self.polynomial_tr[i])*self._u**i for i in range(len(self.polynomial_tr))])//self.polynomial_tr_denom if not self._c * self._r == self._p + 1 - self._tr: raise ValueError("Error: r*c != p+1-tr\nr={}\nc={}\np+1-tr={}\n".format(self._r,self._c,self._p+1-self._tr)) self._y = sum([Integer(self.polynomial_y[i])*self._u**i for i in range(len(self.polynomial_y))])//self.polynomial_y_denom # GLV parameter for fast scalar multiplication thanks to automorphism # psi: (x,y) -> (-x,i*y) = [lambda mod r]*(x,y) if (x,y) is of order r # where beta is a root of x^2+1 mod p, beta = sqrt(-1) mod p # and lambda is a root of x^2+1 mod r, lamb = sqrt(-1) mod r # there are two choices: beta, -beta, and the same for lamb: lamb, -lamb # arbitrarily the positive ones are chosen # if u is odd, beta has integer coefficients, # but if u is even, then beta has denomiator 2: use / instead of // if (self._u % 2) == 0: self._beta = sum([Integer(self.polynomial_beta[i])*self._u**i for i in range(len(self.polynomial_beta))])/self.polynomial_beta_denom else: self._beta = sum([Integer(self.polynomial_beta[i])*self._u**i for i in range(len(self.polynomial_beta))])//self.polynomial_beta_denom # lamb is always an integer self._lamb = sum([Integer(self.polynomial_lamb[i])*self._u**i for i in range(len(self.polynomial_lamb))])//self.polynomial_lamb_denom try: self._Fp = FiniteField(self._p) except ValueError as err: print("ValueError creating Fp: {}".format(err)) raise except: print("Error creating Fp") raise if not self._r.is_prime(): raise ValueError("Error r is not prime") # if u is even, beta has denominator 2, reduces mod p: if (self._u %2) == 0: self._beta = Integer(self._Fp(self._beta)) if ((self._beta**2 + 1) % self._p) != 0: raise ValueError("Error beta^2 + 1 != 0 mod p") if ((self._lamb**2 + 1) % self._r) != 0: raise ValueError("Error lamb^2 + 1 != 0 mod r") self._Fpz = PolynomialRing(self._Fp, names=('z',)) (self._z,) = self._Fpz._first_ngens(1) self._bp = self._Fp(0) # second curve parameter is 0 because j=1728 if a != None: try: a = Integer(a) except: raise self._a = a self._ap = self._Fp(a) else: # check that beta = U/V, where U=t/2, V = y self._a, self._ap = get_curve_parameter_a_j1728(self._tr, self._y, self._beta, self._p, self._Fp) # Now self._a is such that E: y^2 = x^3 + a*x has order r try: # this init function of super inherits from class EllipticCurve_generic defined in ell_generic.py # __init__ method inherited from ell_generic EllipticCurve_finite_field.__init__(self, self._Fp, [0,0,0,self._ap,0]) except ValueError as err: print("ValueError at EllipticCurve_finite_field.__init__: {}".format(err)) raise except: print("An error occupred when initialising the elliptic curve") raise self.order_checked = super(FK8D4,self).order() if self.order_checked != (self._p+1-self._tr): print("Error, wrong order") raise ValueError("Wrong curve order: this one is a twist") # computes a generator self._G = get_curve_generator_order_r_j1728(self) self._Gx = self._G[0] self._Gy = self._G[1] # adjust beta and lamb according to the curve # do we have (-x,beta*y) = lamb*(x,y)? if self([-self._Gx, self._Gy*self._beta]) != self._lamb*self._G: print("adjusting beta, lambda") if self([-self._Gx, self._Gy*(-self._beta)]) == self._lamb*self._G: self._beta = self._p-self._beta print("beta -> -beta") elif self([-self._Gx, self._Gy*self._beta]) == (-self._lamb)*self._G: self._lamb = -self._lamb print("lamb -> -lamb") elif self([-self._Gx, self._Gy*(-self._beta)]) == (-self._lamb)*self._G: self._beta = self._p-self._beta self._lamb = -self._lamb print("lamb -> -lamb") print("beta -> -beta") else: raise ValueError("Error while adjusting beta, lamb: compatibility not found") def _repr_(self): return "FK8D4 p"+str(self._pbits)+" (Fotiadis-Konstantinou k=8) curve with seed "+str(self._u)+"\n"+super(FK8D4,self)._repr_() def u(self): return self._u def T(self): return self._u def p(self): return self._p def r(self): return self._r def c(self): return self._c def tr(self): return self._tr def y(self): return self._y def D(self): return self._D def a(self): return self._a # Integer def ap(self): return self._ap # in Fp (finite field element) def b(self): return self._b # 0 def bp(self): return self._bp # 0 def beta(self): return self._beta def lamb(self): return self._lamb def k(self): return self._k def Fp(self): return self._Fp def Fpz(self): return self._Fpz, self._z def G(self): return self._G def print_parameters(self): PairingFriendlyCurve.print_parameters(self) def print_parameters_for_RELIC(self): PairingFriendlyCurve.print_parameters_for_RELIC(self)