Hyperelliptic Cryptosystems

J. Cryptology (1989) 1:139-150 Journal of Cryptology © 1989 International Association for Cryptologic Research Hyperelliptic Cryptosystems Neal Koblitz Department of Mathematics GN-50, University of Washington, Seattle, WA 98195, U.S.A. Abstract. In this paper we discuss a source of finite abelian groups suitable for cryptosystems based on the presumed intractability of the discrete logarithm problem for these groups. They are the jacobians of hyperelliptic curves defined over finite fields. Special attention is given to curves defined over the field of two elements. Explicit formulas and examples are given, and the problem of finding groups of almost prime order is discussed. Key words. Cryptosystem, Public key, Discrete logarithm, Hyperelliptic curve, Jacobian. 1. Introduction In a finite abelian group, if an element was obtained as a multiple of another known element (the "base"), the discrete logarithm problem consists in finding the integer that was multiplied by the base to get the element. Whenever we have a finite abelian group for which the discrete log problem appears to be intractable, we can construct various public key cryptosystems in which taking large multiples of a group element is the trapdoor function. Such cryptosystems were first constructed from the multi- plicative group of a finite field. However, because certain special techniques are available for attacking the discrete log problem in that case (especially when the field has characteristic 2, see [t3]), it is worthwhile to study other sources of finite abelian groups. In [8] we described how the group of points on an elliptic curve can be used to construct public key cryptosystems. The purpose of the present article is to discuss the more general class of groups obtained from the j acobians of hyperelliptic curves. These jacobian varieties seem to be a rich source of finite abelian groups for which, so far as is known, the discrete log problem is intractable. We pay special attention to the case when the ground field has characteristic 2, because arithmetic over such fields is particularly amenable to efficient implementation, and because it is in that case that the multiplicative group of the field does not provide secure cryptosystems unless the size of the field is extremely large, as explained in [13]. After giving the basic definitions of the group elements and the group addition in Section 2, we describe an algorithm for addition in Section 3. In Sections 2 and 1 Date received: February 4, 1988. Date revised: September 28, 1988. 139 140 N. Kobtitz 3 we follow [2], with the addition of some minor modifications and clarifications. In particular, we treat a more general equation for the hyperelliptic curve, which enables us to include the case of characteristic 2. We next describe how to determine the number of F~,-points on the jacobian for varying n, and discuss the problem of finding n for which the group has "almost prime" order. If the jacobian has a certain irreducibility property, the latter problem is a natural analog of the Mersenne number problem of elementary number theory. For groups of"almost prime" order we expect the discrete log problem to be intractable. In Section 5 we describe how such public key cryptosystems as the Diffie- Hetlman key exchange can be carried over to these jacobians. We briefly discuss the generation of the random group elements that are needed in such cryptosystems. Finally, we give a procedure which in many cases simplifies the computation of large multiples of group elements. 2. The Groups Let K be an arbitrary field, and let /£ denote its algebraic closure. We define a hyperell iptic curve C o f 9enus 9 over K to be an equation of the form v 2 + h(u)v = f(u), where h(u) is a polynomial of degree at most 9 and f (u ) is a monic polynomial of degree 29 + 1. Here f and h have coefficients in K, and we require that the curve have no singular points (u, v), i.e., that there be no values u, v e .K which satisfy v 2 + h(u)v = f (u) and also both of the partial derivative equations 2v + h(u) = 0 and h'(u)v - f ' (u ) = 0 (where the derivative of a polynomial is defined over an arbitrary field by means of the usual formulas). Throughout this section we assume that the curve C has been fixed. Let L be a field containing K. By an L-point P ~ C we mean either the symbol oo or else a solution u = x e L, v = y ~ L of the equation v 2 + h(u)v = f(u). The latter is called a "finite" point and is denoted Px.y- If a is an automorphism of L over K, we let P~ denote P~l~.~y) and set oo ~ = oo. We now introduce the jacobian of the curve C, using the notion of a "divisor" on C. The reader interested only in the algorithms may skip to the beginning of Section 3, at which point we regard a divisor explicitly as merely a pair of polynomials. On the other hand, the reader who wants a treatment of the theory of algebraic curves that is more thorough than the discussion below is referred to [5]. A divisor is a finite formal sum of/~-points D = ~ miP i. We define the degree of D to be the integer ~ m~. The divisors form an additive group D, in which the divisors of degree 0 form a subgroup D °. Given D = ~ miPi e D, we define D + = ~,,, > o miPi (the "positive part" of D), we say that D __ 0 if D = D +, and we set D°= D - (deg D)oo. Thus, D + > 0 and D ° e D °. Given two divisors D I = ~ rn~P i and Dz = ~n iP i in D °, we define g.c.d. (DI,D2)~ D ° to be (~min(mi, ni)Pi) °, i.e., min(mi, ni)P~ - (~ min(m~, n0)oo. Given a finite point P = Px, y e C, we define its "opposite" P to be P = (x, -y - h(x)), i.e., the unique other point with the same u-coordinate x. IfP = ~, then we define P = oo. Let p(u, v) be a polynomial with coefficients in/£, considered as a function on C. Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Hyperelliptic Cryptosystems 141 Since V 2 = f (u ) - - h(u)v on C, we may replace higher powers of v by lower powers to obtain an equivalent "reduced" polynomial of the form p-(u, v) = a(u) - b(u)v. We define the order of p(u, v) at a point P e C, denoted ordp p, as follows: (1) Assume P = Px.y is a finite point. Write p in the form (u - x)r°(ao(u) - bo(u)v), where (u -x ) does not divide both ao and bo; let r = r o if P ~ P and r = 2r o if P = P. Then order., p is equal to r if ao(x) - bo(x)y # O, and if ao(x) - bo(x)y = 0 it is equal to r plus the exponent of the highest power of (u - x) which divides ao(u) 2 + h(u)ao(u)bo(u) - f(u)bo(u) 2. (2) If P = oo, then ord~ p = -max(2 deg a, 29 + 1 + 2 deg b). Here in (1) (assume with ro = 0) the idea is that with v = a(u)/b(u) the value u = x should be an (ordpx." p)-th root of v z + h(u)v - f (u) = (a 2 + hab - fb2) /b 2. In (2), if we think of u as approaching oo "with order 2," then v approaches oo "with order 29 + 1" (since v 2 = u 2g+1 + lower-order terms), and Jord~ Pl is the order at which a(u) - b(u)v approaches co; thus, we say that the order of vanishing o fp at infinity is the negative of this value. To any p(u, v) such that ~ # 0 (i.e., p(u, v) is not divisible by v 2 + hv - f as polynomials in u and v), we associate the divisor (p) = ~(ord~, p)P. Here the summa- tion is over all points P on the curve (including oo) where p has nonzero order. This sum is clearly finite. We can also verify that (p) s D °. As an example, if p(u, v) = u - x, then (u - x) = Px.y +/~,y - 200, where y is one of the two solutions of y: + h(x)y = f(x). By a rational function on C we mean a ratio of the form p(u, v)/q(u, v) with g ~ 0. To such a rational function we associate the divisor (p/q) = (p) - (q) e D °. A divisor of the form (p) - (q) is called principal; such divisors form a subgroup P of D °. The quotient group D° /P is called the jacobian J of the curve C. If D1, D2 e D °, we write D t ~ D 2 if D~ - - D 2 ~ P, i.e., if Dx and D 2 are equal when considered as elements of J. For example, for any /(-point P we have P - ~ ~ - (P - co), since P + P - 2oo = (u - x) (where x is the u-coordinate of P). In particular, in the case when P = P we have 2P ~ 2oo. It then follows that any D ~ D O can be modified by a principal divisor to obtain an equivalent D 1 ~ D of the form ~, miP~ - (~ m~)~, where the m~ > 0 and the P~ are finite points such that when P~ occurs in the sum, P~ does not occur, unless ~ = P, in which case the corresponding mi is at most 1. We say that a divisor D is "semireduced" when it is brought to the form D1. I fK is a perfect field (e.g., a finite field), we say that a divisor D = ~ m~Pi is defined over K (or is a "K-divisor") if D" = ~ m~P 7 is equal to D for all automorphisms a o f / ( over K. Notice that this does not mean that each P7 is equal to P~; tr may permute the points. We can show that a principal divisor is defined over K if and only if it is the divisor of a rational function that has coefficients in K. It follows from the R iemann-Roch theorem (see [5]) that every D ~ D O can be uniquely represented as an element of J (i.e., modulo P) by a semireduced divisor D~ = )-" m~P~ -- (~ m~)~ for which ~ m~ < 9. A divisor D~ with this property is called reduced. A semireduced divisor D = ~ miPx,,y, - (~', mi )~ can be uniquely represented as the g.c.d, of two principal divisors of functions of the form a(u) and b(u) - v (that Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 Administrator 线条 142 N. Koblitz is, D = g.c.d. ((a(u)), (b(u) -- v))), where a(u) = I-[(u - xi) m' and b(u) is the unique polynomial of degree < deg a such that b(xi) = Yt for each i and b(u) 2 + h(u)b(u) - f (u) is divisible by a(u). (If a(u) happens to have distinct roots, i.e., if all rni = 1, then the latter condition is redundant.) A divisor D represented in the form g.c.d. ((a(u)), (b(u) - v)) is abbreviated D = div(a, b). D is reduced if and only if deg a N g. For example, the divisor D = Px.y - oo is equal to div(a, b) with a(u) = u - x and b(u) = y. If h(u) = 0 (which is possible only if char K ¢ 2) and if y ¢ 0, then for the divisor D = 2Px.y - 20o we have a(u) = (u - x) 2 and b(u) = ( f+ y2)/2y, where f denotes the remainder off(u) modulo (u - x) 2. 3. The Algorithm From now on, a divisor D will be regarded simply as a pair of polynomials D = div(a, b) such that deg b < deg a and b 2 + hb - f i s divisible by a (here a, b, h, and f are polynomials in u). Such a divisor is called "semireduced." An element of our group J is an equivalence class of divisors. Every divisor is equivalent to a uniqhe "reduced" divisor, by which we mean a semireduced D = div(a, b) for which deg a _ g. If a, b, and c are three polynomials in u, then the notation b = c (mod a) means that b is equal to the residue of c modulo a, i.e., it is the unique polynomial b of degree < deg a such that a divides c - b. The algorithm for adding divisors D e J consists of two stages. Given D t = div(a 1, bt) and D2 = div(a2, b2), we first find a semireduced divisor D = div(a, b) such that D ,-~ D1 + D2. Next, we "reduce" D, i.e., we find a'(u) and b'(u) such that deg a' <_ g, deg b' < deg a', and D ~ div(a', b'). Our description of the two stages of the algorithm follows [2], except that we are working without the assumption in [2] that h(u) = 0 and char K ~ 2. We omit the proofofcorrectness of the algorithm, which is virtually identical to the proof in [2]. Thus, we wish to find the sum of div(a t , b 1) and div(a 2, b2) on the jacobian of the curve v 2 + hv = f , where a I, a 2, b t, b 2, h, and f are all polynomials in u. (Here h and f have coefficients in K, and a t, a 2, bt, and b2 may have coefficients in an extension field of K.) Stage I. Let d = d(u) be the g.c.d, of the three polynomials al(u), a2(u ), and bl(u) + b2(u) + h(u); and choose sl(u), s2(u), and s3(u) to be polynomials in u such that Set and d=stat +s2a2+s3(bt +b2+h) . (1) a = a la2 /d 2 b = (s lalb2 + s2a2bl + s3(blb2 + f ) ) /d (mod a). (2) Hyperelliptic Cryptosystems 143 We easily verify that d divides s la lb 2 + s2a2b 1 + s3(blb 2 + f ) , so that this expres- sion makes sense. We further derive the following identity of polynomials in u, v: (bl + b2 + h) (b - o) = (b 1 - v) (b 2 - v) + s 1 a 1 ( b2 + hb2 - f ) /d + s2 a2(b 2 + hbl - f ) /d , from which the correctness of the definition is proved, as in 12]. Special Cases. 1. If at and a 2 have no common factor, then d = t, we can take s 3 = 0, and so a = ala 2, b = stalb2 + s2a2bl (mod a). 2. When a 2 = a 1 and b2 = bl (i.e., we are doubl ing an element of J), we can take s 2 =0. (a) Assume char K=2 and h(u)=l . Then d=l , s l=s2=0, s3=l , and a=a 2, b=b 2+f (mOda) . (b) Assume char K = 2 and h(u) = u. Also assume that u does not divide a(u), which in this situation is equivalent to requiring that none of the P~ occurring in div(al, bl) = ~m,P i - (~m,)~ is equal to its opposite ~. (If P, -- P,, then 2P~ --, 2oo, as we saw.) Then d = i, s 1 = (al (0)) -1, s2 = O, s3 = (al (u)/al (0) + 1)/u, and a = a 2, b = (alb ~ + (al(u) + al(0))(b 2 + f)/u)/at(O) (mod a). For ex- ample, if D = P~,y - co = div(u - x, y) (here x and y are constants), then 23 = div(a, b) with a = u 2 + x 2 and b = ( f + yu + xy + y2)/x, where f is the linear polynomial in u that is obtained from f by replacing u 2 by x 2. Stage 2. Given D = div(a, b) with deg a > 9, the following procedure replaces D with an equivalent divisor D' = div(a', b') for which deg a' < deg a. By successively applying the procedure, we eventually obtain D" = div(a", b") for which D ~ D" and deg a" <. g. We set a' = ( f -- hb - b2)/a (3) and then b '=-h -b (moda ' ) . (4) We then show that div(a', b') ~ div(a, b) and deg a' < deg a (see [2]). This con- cludes the description of the algorithm. Remarks. 1. This algorithm is analogous to the procedure for adding classes of quadratic forms. For instance, in Stage 2 with h = 0, the reduction formulas (3) and (4) are similar to the following formulas for finding a quadratic form a 'X 2 + 2b 'XY + c 'Y 2 equivalent to the form aX 2 + 2bXY + cY 2 of discriminant 4 f= 4(b 2 - ac) .Assuminga > b, wereplace by _ 0 0 1 y to get aY 2 -- 2b(X + jY )Y + c(X + jy)2, i.e., a ' = c = (b 2 - f ) /a , b' = -b + jc = - b (mod c) with j chosen so that b' is the least nonnegative residue modulo c = a'. 2. In the case # = 1 (elliptic curves), the reduced divisors D = div(u - x, y) are in one-to-one correspondence with the points Px.y e C. The above algorithm is then easily seen to reduce to the usual formulas for the addit ion of points on an elliptic curve (see, e.g., [6]). 144 N. Koblitz Examples. Let K = F 2 be the field of two elements. For P ~ C we let po~ denote P*~, where a J is the automorphism of F2 given by x ~ x v. In certain cases there are simple formulas expressing 2kP in terms of pU) which give a short-cut in comput ing multiples of D = ~m~P~- (~m3oo. The formulas below all follow by repeated application of Stage 1 (special case 2(a)) and then Stage 2 of the algorithm. 1. C is given by v 2 + v = u 2a+~. Then: (a) for 9 = 1, (b) for 9 = 2, (c) for g = 3, (d) for e = 4, 2P = _p(2) ; 4P = -- p~4); 8P = 2P ~s) - p~6); 8P = - -P (6 ) . 2. C is given by v z + v = u 29+1 + u. Then: (a) for 9 = 1, 4P = -- P~*); (b) for 9 = 2, 16P = p~s); (c) for e = 4, 64P = - pCl 2). 3. C is given by v 2+v=u 5+u 3 ,g=2.Then 64P = - Ptl 2). 4. C is given by v 2+v=u 5+u 3+u,g=2.Then 8P = p(6). Remark. In Section 5 we give a general method for reducing the calculation of mP for m large to the computat ion of l inear combinations of pO~ with small coefficients. 4. Number of Points Let J be thejacobian of the hyperelliptic curve C given by an equation v 2 + h(u)v = f(u) with coefficients in K. Assume that K is a perfect field, and let L be an algebraic field extension of K. We let J (L) denote the set of L-points of J, i.e., the divisors D such that D ~ = D for all automorphisms a o f / ( over L. Since this invariance property is preserved under addition, J(L) is a subgroup of J = J(/(). In terms of the explicit representation of divisors in the form div(a, b) which we used in Section 3, an L-point of J is simply an element div(a, b) for which the polynomials a and b have coefficients in L. Hyperelliptic Cryptosystems 145 We assume that K = Fq is a finite field with q elements. It is easy to see that the abelian group J(L) is finite for any finite extension L = Fq.. We set iV. = #(a(Fq.)). A basic fact about the iV. is that there is a simple method for determining the sequence N1, N2 . . . . by counting the number of Fq.-solutions of the equation of C for the first 9 values n = 1 . . . . . 9, We now describe this method. Let M. = # (C(Fq.)) - q", where # (C(Fq.)) is the number of solutions u, v ~ Fq. of the equation v 2 + h(u)v = f(u). Associated with the curve C is a polynomial Z(T) of degree 29 with integer coefficients having the form Z(T) = T 2° + al T 29-1 + "" + ao_x T°+X + agT° + qaa_ 1 T °-1 + q2aa_ 2 T a-2 + " " + q°-la 1 T + qa g = I-[ ( (T - ~ j ) (T - ~) ) , (5) j=l where al . . . . . a o ~ Z and where ~ = q/~j (i.e., the roots are complex numbers of absolute value v/-q). The relationship between Z(T) and {M.} is the following power series identity (where Z(T) denotes the reciprocal polynomial T2°Z(1/T)): log(Z,(T)) = ~. M. T". .=i n Note that the first 9 values Mx . . . . . M 0 are enough to determine the coefficients of Z(T). Once Z(T) has been found, N. can be determined from the formula g N. = I-'[ I1 -- a;[2, (6) j=l where 11 denotes the usual complex absolute value. In particular, N~ = Z(1). Also observe from (6) that (q./2 _ 1)2o < N. < (q./2 + 1)20, i.e., N. is asymptotically of magnitude q.g. Here are the explicit formulas in the simplest cases 9 = 1 and 9 = 2. 9=I . I f~ isarooto fT2+M1T+q, thenN,=l l - - c t " ] 2. 9 = 2. We first find the number of Fq- and Fq2-solutions of v 2 + h(u)v = f(u), thereby determining M 1 and M2. The coefficients of Z(T) are given by a 1 = Mx, a2 = (M 2 + M2)/2. Next, let Vl and V2 be the two roots of the quadratic equation X 2 + a lX + (a 2 - 2q) = 0. Then ~j fo r j = 1, 2 is a root of the quadratic equation X 2 - - ~ jS --~ q = 0. Finally, N, = tl - ~t~t2]l - ~t~] 2. Examples. 1. Let K = F 2 and let C be given by v 2 + v = u 5 + u 3 (see Example 3 of Section 3). We find that the four roots of Z(T) are 146 N. Koblitz For n not divisible by 2 or 3 this leads to the formula N. = 22" + 2" + 1 + ( - 1)~"+l)/4J2("+1)/z(2" + 1) (7) (here [ ] denotes the greatest integer function), while if n is divisible by 2 or 3, then N, is a perfect square. For example, if n is divisible by t2, then N. = ((2i) "/z -- 1) 4. Similarly, for the curve v z + v = u 5 + u 3 + 1 over F2 the roots of Z(T) are given by (1 +_ i)((1 + i\f3)/2) and N, (n not divisible by 2 or 3) is given by N, = 22" + 2" + 1 -- (-1)~("+*)m2("+l)/z(2" + 1). (8) 2. Let K = Fz and C be given by v a + v = u 5 + u 3 + u (see Example 4 of Section 3). A similar computat ion leads to the formula N, = 22" - 2" + 1 (9) i fn is prime to 6. I fn is divisible by 2 but not by 3, then N. = (2" + 2 "/2 + 1)2; i fn is divisible by 3 but not by 2, then N, = (2" - 1)2; and if n is divisible by 6, then N, = (2 "/2 - I ) 4. R