Read Implementing Elliptic Curve Cryptosystems text version

Implementing Elliptic Curve Cryptosystems - A Survey by Mario Schmitz, Massey University, February 2005 -

Abstract: In 1987 Neil Koblitz first suggested the use of Elliptic curves for Public Key Cryptosystems. This has triggered publications about ECC (Elliptic Curve Cryptography) in recent years as well as the appearance of first University textbooks about that topic. Some Mathematicians and Computer Scientists have focused their studies of Elliptic curves on efficiency and security of ECC. Questions arise about how to adapt existing algorithms to ECC, which curves are suitable, how to choose the underlying field structure, how to determine the group order efficiently, how to represent messages as points on a curve, etc... I will try to address some of these issues from a practical point of view using known result from the Mathematical theory, referring to other sources for most of the details and proofs.

Table of Content

i.

Abstract

ii.

Table of Content

1. Affine Plane vs. Projective Plane

2. Group Structure 2.1 Definitions 2.2 The Discrete Logarithm Problem 2.3 Field Characteristic 2.4 Summary

3. Group Order 3.1 Introduction 3.2 Pre-certified Curves 3.3 Random Curves

A. Group Law

References

1. Affine Plane vs. Projective Plane

Let K be an algebraically closed field.

Definition: An affine plane over K is defined by K × K , denoted by A 2 ( K ) . An affine Weierstrass equation1 for an Elliptic Curve over K is given by E : y 2 + a1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6

E = {( x, y ) K × K } {}

Definition:

The projective plane over K is the set of equivalence classes of K 3 \ {(0,0,0)} under the equivalence relation ( x1 , y1 , z1 ) ~ ( x 2 , y 2 , z 2 ) , when there exists a nonzero element K such that ( x1 , y1 , z1 ) = ( x 2 , y 2 , z 2 ) . A projective Weierstrass equation2 for an Elliptic curve over K is given by

E : y 2 z + a1 xyz + a 3 yz 2 = x 3 + a 2 x 2 z + a 4 xz 2 + a 6 z 3

(0,1,0) is the unique point at infinity and ( x, y ) a ( x, y,1) .

(see [Washington, 2003] for further details)

1 2

See Appendix A for variable changes and addition formulae See Appendix A for addition formulae

Under certain circumstances working in projective coordinates allows easier or faster computation. Some implementations allow choosing whether affine or projective coordinates should be used by setting environmental variables [Shamus Software Ltd, 2004]. Then, depending on the type of the implementation an optimal computing performance can be achieved. The following example illustrates advantages of projective coordinates considering an implementation in computer hardware and is adapted from [Menezes, 1993]. Let E be an Elliptic curve defined over a field K 2m 3, where m=155. Say, an inversion takes 10 multiplications in this implementation and assume that addition operations can be neglected in the following calculations. The reason is that an addition requires one clock cycle only (bitwise XOR-ing), whereas multiplication requires m clock cycles. Analysing the group law, working in affine coordinates, adding two distinct points on E(K) takes 2 field multiplications and 1 inversion. Doubling a point takes 3 multiplications and 1 inversion. In projective coordinates, the addition takes 13 field multiplications and the doubling takes 7 multiplications. Note that although the number of multiplications increases, the more expensive field inversions vanish. This becomes significant if computations of the form kP i.e., multiplying a point on E by an integer k K are required, as for instance for ElGamal public key cryptosystems. The computations of kP and kaP require m additions and 2m doublings on average for randomly chosen k, where m=155 in this case.

Example:

kP: 155 additions 310 doublings

affine coordinates:

155 12 + 310 13 = 5890 (multiplications) projective coordinates: 155 13 + 310 7 = 4185 (multiplications)

3

Field elements in characteristic 2 fields can be represented as bit vectors and can be stored in shift registers of length m allowing an easy implementation of arithmetic circuits. (see chapter 2 for details). m=155 has been chosen, because it represents a suitable field for ECC.

It might be desirable to swap between affine and projective coordinates during an algorithm. Then, when changing back to affine coordinates another field inversion is necessary (e.g. to recover ( x, y ) from ( x1 , y1 , z ) one has to multiply each coordinate by z -1 ). In the above example, working in projective coordinates is still cheaper. One drawback is the requirement for more memory in projective coordinates as more temporary results need to be saved. Thus, to achieve optimal performance, a detailed analysis of the problem and the constraints is required. Another issue when implementing Elliptic curves in computer programs might be the definition and handling of the identity element, namely the point of infinity. Although I could not find any specific examples, I assume that the projective plane gives the programmer a more natural way to deal with this element. Recall that the point at infinity is (0,1,0) in projective coordinates, easy to test and implement whereas in affine coordinates, K × K . This is still just another definition, but it adds further complexity.

2. Group Structure - The underlying field and suitable curves -

2.1 Definitions: 1.

For the following discussion I will distinguish between two different classes of finite fields, namely finite prime fields of the form K q with

q = p m where p is prime greater 2 and m is some positive integer and K 2m i.e., fields of characteristic 2.

2.

Let k be the characteristic of the underlying field. An Elliptic curve is called supersingular if E[k ] = {} i.e., the torsion subgroup contains the identity element only. In other words, there are no points of order k on the curve. There are efficient ways to determine whether an Elliptic curve is supersingular or not. I will only state two useful theorems here without proof: Theorem4: An Elliptic curve is supersingular if and only if # E ( K q ) 1(mod p ) Theorem5: If the characteristic of the underlying field is 2 or 3 then an Elliptic curve is supersingular if and only if its j-invariant is zero.

3.

The discrete logarithm problem (DLP) for Elliptic curves can be stated as follows: Let P and Q be points on an Elliptic curve E, defined over a field K, where Q=kP for some k K . Find k.

4 5

See [Washington, 2003, p.121] See [Enge, 1999, p.103]

2.2 The Discrete Logarithm Problem

The discrete logarithm problem for finite Abelian groups of Elliptic curves is believed to be harder than that for finite multiplicative groups. That is, a smaller field size can be used providing the same level of security. In general, attacks with subexponential time algorithms (e.g. Index Calculus) do not work for ECC when suitable group structures are chosen. Here are two counterexamples: 1. It is necessary to choose systems where the order of the points on the curve over the chosen field is prime or at least does not have small prime factors in order to resist attacks like the Pohlig-Hellmann method. If the order does contain small prime factors, these can be used to build a system of congruences with solution k which might be solved using the Chinese Remainder Theorem. 2. When supersingular curves are used it can be shown that the discrete logarithm problem can be attacked in probabilistic subexponential time complexity. [Menezes, 1993, chapter 5.2] In fact, the DLP for this type of Elliptic curves is equivalent to the DLP of finite fields. This does however not imply that supersingular curves are not suitable for ECC, it only means that the field must be chosen carefully.

To avoid the situation in example 1, one can generate a cyclic group with the desired property: - choose a group that has a large prime q in its order - choose a random point P that is divisible by q and let P=mq - Let Q=mP. Then Q will have order q If q has been chosen sufficiently large Q will generate a cyclic subgroup that resists the attack [Washington, 2003]. In practice however, other, more complicated methods have to precede this method to find such a group. (see chapter 3 for details).

Although supersingular are more tractable than non-supersingular curves, they provide faster encryption as well as an easier and faster way to determine the group order. The latter might help both the implementer and the intruder.

2.3 Field Characteristic

Most textbooks assume in their treatments an Elliptic curve defined over a field of characteristic greater two. This has obvious advantages, since the general theory can be taught dealing with an Elliptic Curve in Weierstrass form, E : y 2 = x 3 + Ax + B without the loss of generality. The group law and thus most theorems and proofs can be introduced using this form which uses less complicated formulae than the equations over characteristic 2 fields. The same is true for most scientific publications sighted. Fields of characteristic 2 however have advantages when implementing Elliptic curves on Computers, particularly for hardware implementations. The arithmetic circuits can be built efficiently and relatively easy as the following illustrations, due to Menezes, show. Let K be a field of characteristic 2 i.e., K = F2m . If one views this field as a vector space of dimension m, the implementation becomes very simple. Let k K . Then there exists a set of m elements {k 0 , k1 ,..., k m -1} in K, such that each element can be uniquely written as

k = bi k i , where bi {0,1} and each k can be represented as a bit vector

i =0

m -1

(b0 , b1 ,..., bm -1 ) . In computer hardware such a bit vector is stored as a shift register of length m. Now arithmetic becomes straightforward. Adding is simply a bitwise XOR. Doubling is achieved by shifting to the left. If another basis is chosen,

, k 2 ,..., k 2 , then squaring is can be done by rotation. All these operations require one clock cycle only. A multiplication circuit is slightly more complicated and it takes m clock cycles to compute a product.

{k , k

2

2

m -1

}

Besides the characteristic of K, one has also to consider the parameter m. According to [IEEE, 2003], "The field typemay affect the security of the scheme, since the running time of general-purpose discrete logarithm methods varies based on the relative size of p and m." A third type of field, suitable for ECC is the odd characteristic extension field, not covered beyond mentioning here.

2.4 Summary

In general two questions should be asked when analyzing an implementation:

How can the fastest and easiest possible implementation be achieved? How secure would this implementation be?

A programmer might want to check the following:

·

E should not have multiple roots as the group would then be isomorphic to the real numbers under addition (triple root) or the real numbers under multiplication (double root). In other words, every implementation that uses randomly generated Elliptic curves should check their discriminants.

The order of E(K) should not contain small prime factors. Test for supersingularity if randomly generated Elliptic curves are used Which Field Characteristic suits the problem to be solved? Working in affine or in projective planes or in both? Analyze the tractability of the DLP after a group structure has been chosen

· · · · ·

3. Determining the Group Order

3.1 Introduction

In general, knowing the group order is crucial for Elliptic Curve Cryptosystems, since the difficulty of the discrete logarithm problem for Elliptic curves mainly depends on it. The order has to be sufficiently large to resist attacks like the Baby step, giant step method, and it must not contain small prime factors to resist attacks like the Pohlig-Hellman method. Sometimes it must be known publicly (Elliptic Curve Digital Signature Algorithm) and sometimes it is desirable to keep it secret, for instance to avoid the Pohlig-Hellman attack completely.

3.2 Pre-certified Curves

There are three methods to generate curves which provide a large prime group order. Using supersingular curves, the Complex Multiplication method for Elliptic curves, or using groups chosen over extension fields. [Enge, 1999].

3.3 Random Curves

In 1985 Rene Schoof published a deterministic algorithm for computing the number of points on Elliptic Curves over finite fields. In contrast to other algorithms, e.g. Baby Step, Giant Step, Schoof's Algorithm is computationally feasible for very large fields. Elkies and Atkins later refined this method to what is now referred to as the SEAAlgorithm (Schoof-Elkies-Atkins). Let E be an Elliptic Curve in Weierstrass form with no repeated roots defined over a finite field Fq with characterictic greater 3. The common strategy of these algorithms is to determine a < 2 q to compute # E ( Fq ) = q + 1 - a . Schoof uses the characteristic equation of the Frobenius Endomorphism on prime Torsion points on E to generate a system of congruences with solution a that can be solved using the Chinese Remainder Theorem. This method may become impractical due to the size of the polynomials involved in the calculations. Elkies and Atkin have overcome this problem by working with Isogenies and Eigenvalues of the Frobenius Map to reduce the degree of the polynomials involved. Using the SEA-Algorithm, in 1998 the record set by Morain was to calculate the number of points on E over a field with a 500-digit prime.

A. Group Law

1. Adding points on E : y 2 + a1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 for char(K)>2

y - y 2 y 2 - y1 1 2 x - x + a1 x - x - a 2 - x1 - x 2 2 1 1 2 x3 = 2 3 x 2 + 2a 2 x + a 4 - a1 y 3 x 2 + 2a 2 x + a 4 - a1 y + a1 - a 2 - 2x 2 y + a1 x + a3 2 y + a1 x + a 3 for P = Q y 0

for x1 x 2

y 2 - y1 x - x ( x1 - x3 ) - y1 - (a 1 x 3 + a 3 ) 2 1 y3 = 2 3x + 2a 2 x + a 4 - a1 y ( x - x ) - y - (a x + a ) 3 1 3 3 2 y + a1 x + a3

for x1 x 2

for P = Q y 0

otherwise, P + Q =

2. Reducing to Weierstrass form for char(K)>3

a x + a3 E : y 2 + a1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 y + 1 = x 3 + b2 x 2 + b4 x + b6 2 , where 2 a b2 = a 2 + 1 4 a1 a3 b4 = a 4 + 2 2 a b6 = a 6 + 3 4

Let

2

y1 = y +

Let

a1 x + a3 2 . Then, y1 = x 3 + b2 x 2 + b4 x + b6 2 b 2 3 x = x1 - 2 . Then, y1 = x1 + Ax1 + B , where 3 2 - b2 A= + b4 3 3 2 B = 27 b2 - 1 b2 b4 + b6 3

3. Adding points on E : y 2 + xy = x 3 + a 2 x 2 + a 6 for char(K)=2, non-supersingular

y + y 2 y + y 1 1 + 2 + a + x1 + x 2 2 x 2 + x1 x 2 + x1 2 x3 = 2 a6 x + 2 x for P = Q y 0

for x1 x 2

y 2 + y1 x + x ( x1 + x 3 ) + y 1 + x 3 1 y3 = 2 2 x + y x + x 2 + x 3 3 x

for P = Q y 0 for x1 x 2

otherwise, P + Q =

4. Adding points on E : y 2 + a 3 y = x 3 + a 4 x + a 6 for char(K)=2, supersingular

y + y 2 1 2 x + x + x1 + x 2 2 1 x3 = 2 x 2 + a 4 a 3 for P = Q y 0

for x1 x 2

y 2 + y1 x + x ( x1 + x 3 ) + y1 + a 3 2 1 y3 = 2 x + a 4 (x + x) + y + a 3 3 a3

for x1 x 2

for P = Q y 0

otherwise, P + Q =

References

Enge A.(1999). Elliptic curves and their applications to cryptography. An introduction. Kluwer Academic Publishers, Massachusetts1999.

IEEE (2003). IEEE P1363a /D12. Draft Standard Specifications for Public Key Cryptography. Institute of Electrical and Electronics Engineering.

Koblitz N. (1987). Elliptic curve cryptosystems. Mathematics of computation, Vol.48, No.177, p. 203-209.

Menezes A.J. (1993). Elliptic curve public key cryptosystems. Kluwer Academic Publishers, Massachusetts1993.

Mueller V. (1995). Ein Algorithmus zur Bestimmung der Punktzahl Elliptischer Kurven ueber endlichen Koerpern der Charakteristik grosser drei. Universitaet des Saarlandes, Saarbruecken 1995.

Shamus Software Ltd (2004). M.I.R.A.C.L. Retrieved December 2004 from ftp.computing.dcu.ie/pub/crypto/miracl.zip

Schoof R. (1985). Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of computation, Vol.44, No.170, p. 483-494.

Washington L.C. (2003). Elliptic curves. Number theory and cryptography. CRC Press LLC, Florida 2003.

Information

Implementing Elliptic Curve Cryptosystems

13 pages

Find more like this

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

72060


You might also be interested in

BETA
Microsoft Word - STA_KIEV.DOC