Sage Code for Generalization of Encodings into Hyperelliptic Curves

encoding2hecurve.sage

class EncodingValidationOfParameters():
    def __init__(self, q, u, w, g = 2, s=None):
        self.R = FiniteField(q,"a")
        self.a = self.R.gen()
        self.poly = PolynomialRing(self.R,"x")
        self.x = self.poly.gen()
        self.q = q
        self.u = self.value2Fq(u)
        self.w = self.value2Fq(w)
        self.s = s
        self.g = g # g=genus of the curve
        self.alpha_g = 2^(2*g-1)-1
        self.beta_g = 4*g^2+2*g
        self.gamma_g = (2*g^2+g)^2
        self.mg = self.valueOfMg()
        self.ng = self.valueOfNg()
        #verification of the parameters
        self._chekingOfParameters()
        self._checkingValueOfTheParameterS()
        self.coefs = self.coefficients()
        self.f = self.function()
        self._chekingIfCurveIsHyperelliptic()

    def __repr__(self):
        eq = "y^2="+str(self.f)
        return "Hyperelliptic curve defined by {} over finite field".format(eq)+""\
            +" F_{}/< {} >".format(self.R.characteristic(),
                                   str(self.R.modulus()).replace("x","a"))
    def function(self):
        g, R = self.g, self.R
        t0, tn = [R(self.coefs[0])], [self.x^(2*g+1)]
        poly_l = t0+[R(self.coefs[i])*self.x^(2*i-1) for i in range(1, g+1)]+tn
        return sum(poly_l)
        
    def valueOfMg(self):
        if self.g % 2 == 0: return (1/4)*self.alpha_g*self.beta_g
        else : return (1/2)*self.alpha_g*self.beta_g
        
    def valueOfNg(self):
        if self.g % 2 == 0: return (1/2)*(2*self.g^2+self.g)^2
        else : return (2*self.g^2+self.g)^2
        
    def coefficients(self):
        g, s, w, R = self.g, self.s, self.w, self.R
        coefs = [(R(s-(2*g^2+g))/R(2*g^2+g))*w^(2*g+1),
                (s*w^(2*g))/R(g), R((2*g-1)/3)*s*w^(2*g-2)]
        if g >= 3: coefs.append(s*w^2)
        if g == 4: coefs.insert(3, R(7/2)*s*w^4)
        if g == 5:
            coefs.insert(3, R(42/5)*s*w^6)
            coefs.insert(4, R(6)*s*w^4)
        return coefs[:]
        
    def value2Fq(self, value):
        import re
        search = re.compile("[a-zA-Z]+")
        if isinstance(value, str):
            return self.R(eval(search.sub("self.a",value).replace("^","**")))
        else: return self.R(value)
        
    def _chekingOfParameters(self):
        """ We check if the parameters  u,w,g,q satisfy the required conditions
        """
        p, g = self.R.characteristic(), self.g
        if (p% 2 == 0) or ((2*g^2+g)%p == 0):
            raise ValueError("The characteristic of F{}".format(self.q)+""\
                +" divise {}".format((2*g^2+g)))
        if (self.q%8 != 7):
            raise ValueError("q is different to 7 modulo 8".format(self.q))
        if self.w.is_zero() or self.u.is_zero(): raise ValueError("w = 0 or u = 0 in Fq ")
        if self.u.is_square(): raise ValueError("u is square in Fq")
        if self.g not in range(1,6): raise ValueError("The genus g out of range(1,5)")


    def _checkingValueOfTheParameterS(self):
        p, g = self.R.characteristic(), self.g
        alpha_g, beta_g, gamma_g = self.alpha_g, self.beta_g, self.gamma_g
        if self.s is None:
            if alpha_g % p == 0: self.s = gamma_g/beta_g
            else:
                delta_s = beta_g^2+4*alpha_g*gamma_g
                self.s = self.R((-beta_g+self.R(delta_s).square_root())/(2*alpha_g))
                
    def _chekingIfCurveIsHyperelliptic(self):
        """ We check if f(x) doesn't have a double root"""
        solution_f, solution_fprime = self.f.roots(), self.f.derivative().roots()
        f_roots = [root[0] for root in solution_f]
        fprime_roots = [root[0] for root in solution_fprime]
        if (set(f_roots) & set(fprime_roots)) != set():
            raise ValueError("The function f={}".format(self.f)+" has double roots")


class EncodingAndInvertGenusg(EncodingValidationOfParameters):
    def __init__(self, q, u, w, g=2, s = None):
        EncodingValidationOfParameters.__init__(self,q, u, w, g = g, s=s)
        
    def _quadraticCharacter(self, value):
        if self.R(value).is_zero(): return 0
        elif self.R(value).is_square(): return 1
        else: return -1
        
    def valuesNotInDomainOfTheEncoding(self):
        R, w, s, u, x = self.R, self.w, self.s, self.u, self.x
        roots = self.f(w*(u*x^2*(R(-self.mg)*s+R(-self.ng))+R(-1))).roots()
        return set([R(0)]) |  set([root[0] for root in roots if root !=[]])
        
    def encode(self, value):
        """ The encoding function psi(r)=(x,y)"""
        R, w, s, u, poly, a = self.R, self.w, self.s, self.u, self.poly, self.a
        r = self.value2Fq(value)
        if r in self.valuesNotInDomainOfTheEncoding():
            raise ValueError("The encoding function is not defined at r={}".format(r))
        v = w*(u*r^2*(R(-self.mg)*s+R(-self.ng))+R(-1))
        e = epsilon = self._quadraticCharacter(self.f(v))
        x = R((1+e)/2)*v+R((1-e)/2)*R(w*(-v+w)/(v+w))
        y = R(-e)*R(self.f(x)).square_root()
        return (x,y)
        
    def decode(self, point):
        """ The inverse of the encoding function"""
        x,y,ng,mg = self.value2Fq(point[0]), self.value2Fq(point[1]), self.ng,self.mg
        R, w, s, u, poly, a = self.R, self.w, self.s, self.u, self.poly, self.a
        if not (y^2-self.f(x)).is_zero():
            raise ValueError("The given value is not a point of the hyperelliptic curve")
        if not (u*w*(x+w)*(R(-ng)+R(-mg)*s)).is_square():
            raise Exception("u*w*(x+w)*(-ng-mg*s) is not a square in Fq")
        r1 = ((x+w)/(u*w*(R(-ng)+R(-mg)*s))).square_root()
        r2 = (R(2)*w/(u*(x+w)*(R(-ng)+R(-mg)*s))).square_root()
        return "The preimages of ({} , {}) by the encoding function".format(x,y)+""\
                +" are equal to ({} , {}) or ({} , {})".format(r1, R(-r1),r2, R(-r2))

#First example
q = 2^521-1
fe = EncodingAndInvertGenusg(q=q,u=3,w=5,g=2); print(fe)
pt = fe.encode(121); print("\n (x,y) = "+str(pt)+"\n")
dc = fe.decode(pt); print("\n"+str(dc)+"\n")
# Second example : we change the genus of the curve
ge = EncodingAndInvertGenusg(q=q,u=3,w=5,g=3); print(ge)
pt2 = ge.encode(121); print("\n (x,y) = "+str(pt2)+"\n")
dc2 = ge.decode(pt2); print("\n"+str(dc2)+"\n")