KSS16.py 8.62 KB
 Emmanuel Thomé committed Apr 08, 2019 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 ``````import sage from exceptions import ValueError from sage.functions.log import log from sage.functions.other import ceil 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 class KSS16(EllipticCurve_finite_field): """ A Kachisa-Schaefer-Scott curve of embedding degree 16 """ def __init__(self, u, a=None): """ u is the seed such that p=P_KSS16(u), and a is the curve coefficient, s.t. y^2 = x^3 + a*x has a subgroup of order r=R_KSS16(u) (there are two possible choices for a: a, 1/a (a twist) but only one has order r) """ self._k = 16 # embedding degree self._b = 0 # second curve parameter is 0 because j=1728 self._D = 4 # 4, not 1, be careful with that # polynomials (will be needed later for polynomial selection) # P_KSS16 = (s^10 + 2*s^9 + 5*s^8 + 48*s^6 + 152*s^5 + 240*s^4 + 625*s^2 + 2398*s + 3125)/980 # R_KSS16 = (s^8 + 48*s^4 + 625)/61250 # 625 = 5^4, 61250 = 2*5^4*7^2 # T_KSS16 = (2*s^5 + 41*s + 35)/35 # C_KSS16 = (125/2) * (s^2 + 2*s + 5) # C such that P+1-T = C*R # Y_KSS16 = (1/70) * (s^5 + 5*s^4 + 38*s + 120) # Y such that T^2 - 4*P = -3*Y^2 # assert (P_KSS16+1-T_KSS16) == C_KSS16*R_KSS16 # assert (T_KSS16^2 + D_KSS16*Y_KSS16^2)/4 == P_KSS16 # sqrt(-1) mod P # BETA_KSS16 = (s^9-11*s^8-16*s^7-120*s^6-32*s^5-498*s^4-748*s^3-2740*s^2-3115*s-5651)/4018 # LAMB_KSS16 = (1/7)*(s^4 + 24) # sqrt(-1) mod R self.polynomial_p = [3125, 2398, 625, 0, 240, 152, 48, 0, 5, 2, 1] self.polynomial_p_denom = 980 self.polynomial_r = [625, 0, 0, 0, 48, 0, 0, 0, 1] self.polynomial_r_denom = 61250 # when u = 25, 45 mod 70, then P(u), T(u), (P+1-T)(u) are all integers, and 61250 | R(u) self.polynomial_c = [625, 250, 125] self.polynomial_c_denom = 2 self.polynomial_tr= [35, 41, 0, 0, 0, 2] self.polynomial_tr_denom= 35 # we need u = 25,45 mod 70 for T to be integer self.polynomial_y = [120, 38, 0, 0, 5, 1] self.polynomial_y_denom = 70 self.polynomial_beta = [-5651, -3115, -2740, -748, -498, -32, -120, -16, -11, 1] self.polynomial_beta_denom = 4018 # 2 * 7^2 * 41 self.polynomial_lamb = [24, 0, 0, 0, 1] self.polynomial_lamb_denom = 7 self._u = Integer(u) 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 # unfortunately beta has always denominator 41, computes modulo p: / instead of // self._beta = sum([Integer(self.polynomial_beta[i])*self._u**i for i in range(len(self.polynomial_beta))])/Integer(self.polynomial_beta_denom) # LAMB is an integer when u=25,45 mod 70, which should be the case for P, T, R to be integers. 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") # beta has denominator 41, reduces mod p: 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(KSS16,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 "KSS16 p"+str(self._pbits)+" (Kachisa-Schaefer-Scott k=16) curve with seed "+str(self._u)+"\n"+super(KSS16,self)._repr_() def u(self): return self._u `````` GUILLEVIC Aurore committed May 27, 2019 151 152 `````` def T(self): return self._u `````` Emmanuel Thomé committed Apr 08, 2019 153 154 155 156 157 158 159 160 161 162 `````` 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 `````` GUILLEVIC Aurore committed May 27, 2019 163 164 `````` def D(self): return self._D `````` Emmanuel Thomé committed Apr 08, 2019 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 `````` 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) ``````