Elliptic-Curve Cryptography

Much cryptography, elliptic curve included, is based on the idea of a mathematical group. A group is a set of objects and a combining rule that takes two objects and produces a third. Examples of groups used in cryptography are:

• Adding pairs of integers modulo n, called the Z_n group.
• Multiplying pairs of nonzero integers modulo p, where p is prime, called the Z^*_p group.

With these, the group operation can be written in either additive or multiplicative form. In a multiplicative group, given x=y^z, we would say the logarithm base y of x is z. However, if we used additive instead of multiplicative notation, then x=z×y. Confusingly, mathematicians still refer to z as the discrete log of x. This distinction between additive and multiplicative notations is important because traditional cryptography uses groups with multiplicative notation, while ECC deals with additive notation.

If a group has two operations, and not just one, you call the set and its operations a "ring." For instance, both addition and multiplication work in Z^*_p, which is both a group and a ring. Finally, if division always works in the ring, so that every nonzero element in the ring has a multiplicative inverse ^-1 in the ring such that ×^-1=1, we call the ring a "field." Examples of familiar fields are the rational, real, and complex numbers. If the field has a finite number of elements, it is called a "finite field" or "Galois field." Elliptic curves in cryptography are formed using elements from Galois fields.

One familiar example of a Galois field is the ubiquitous Z^*_p, which happens to be a group, a ring, and also a field. When using Z^*_p as a Galois field, we often write GF(p) instead of Z^*_p. A less familiar example of a field is found in the polynomials

c_ixⁱ of degree n

where each coefficient c_i is an element from GF(p), and x is an indeterminate value. This polynomial field is built by extending the field GF(p), so it is called an extension field and is denoted by GF(pⁿ). For an example of how multiplication works in this field, see Figure 1. In GF(pⁿ), p is called the field characteristic, and n is called the extension degree.

Galois fields are used in cryptography to build elliptic curves. The connection is provided by the definition of an elliptic curve. Elliptic curves are defined as a combination of three things:

• The set of points (x,y) that satisfy the equation y²+a₁xy+a₃y=x³+a₂x²+a₄x+a₆, where x, y, and the coefficients a_i are all from GF(pⁿ).
• A special point O called the "point at infinity."

• A special addition operator that adds these points together.

We say that the m+1 points E={O,(x₁,y₁), (x₂,y₂),...,(x_m,y_m)} are the points on the elliptic curve, and the group E has order m+1. Within E, we can add two points together using the operator, so that (x_i,y_i)(x_j,y_j)=Cx_k,y_k). In other words, points on the elliptic curve are a group. The special point O is the group's additive identity -- it acts the way zero does in normal integer addition, giving (x_i,y_i)O=(x_i,y_i) for every point on the elliptic curve.

Pros and Cons of Elliptic-Curve Cryptography

Traditionally, cryptosystems such as the Digital Signature Algorithm (DSA), Diffie-Hellman key exchange (DH), or El Gamal encryption are implemented over the group Z^*_p. Each of these cryptosystems relies on the difficulty of taking discrete logarithms in Z^*_p for their security. In contrast, elliptic-curve cryptosystems replace Z^*_p with the elliptic curve group E. If a computer can perform addition in E faster than multiplication in Z^*_p, then a cryptosystem implemented over E should be proportionally faster than in Z^*_p. For some estimates, see "Elliptic Curves and Cryptography," by Aleksandar Jurisicand Alfred Menezes (DDJ, April 1997).

The potential speed increase is impressive. In Z^*_p, the fundamental cryptographic operation is exponentiation, and much effort has been spent to make this operation as fast as possible. In E, the fundamental cryptographic operation is multiplication, and the numbers we multiply are much smaller. According to the IEEE P1363 working group, the effort needed to crack a 254-bit EC system is about the same for a 2800bit Z^*_p system -- about 5.5×10²⁴ MIPS years. Since addition in either group is an O(n log₂3^1.585) to O(n²) process, we could expect an elliptic-curve cryptosystem to be43 to116 times faster than its traditional counterpart. However, since EC addition needs more computational steps than Z^*_p addition, the ratio theoretically drops from 43-116 to 4-10.

Not only should ECC be faster than traditional cryptosystems, but most cryptographers believe that calculating discrete logs in E is fundamentally harder than in Z^*_p. To calculate discrete logs in Z^*_p, the difficult job is to find a factor base for p. Once found, calculating a discrete log in Z^*_p is a fast and simple process. The group becomes broken for all future cryptographic work. In contrast, nobody knows how to find a factor base for elliptic-curve groups, nor do mathematicians believe any such algorithm would be tractable. Finding the discrete log of one element in E will not help find the logarithm of any other element. In fact, let #E denote group order of E, and let r be the largest prime factor of #E. Then the best known algorithms for finding discrete logs in E have complexity O(r/n), where n is the number of processors working on the problem.

Mathematics aside, the real strength of ECC comes from the small size of EC cryptographic keys. A mere 256 bits can represent a 255-bit EC public or private cryptographic key. To achieve equivalent security, a Z^*_p cryptosystem would need over 2800bits. Such a ten-fold savings in size can be crucial when designing smartcard or embedded security systems. Smaller keys need smaller amounts of secure storage for archiving, and need smaller arithmetic units for processing. Using ECC, digital certificates are smaller and cryptographic operations are faster. These time and space efficiencies are the reason that EC cryptography is spreading rapidly in e-commerce.

On the other hand, for each prime number p, there is only one group Z^*_p but a huge number of different elliptic curve groups E. In fact, when implementing an EC cryptosystem, the chief problem is actually picking which curve or family of curves you want to deal with. Different curves are suitable for different purposes, and because every application has different requirements, no elliptic curve can be optimal for all applications. In fact, a large portion of EC research involves finding particular families of curves that are computationally efficient. So how do you pick a curve for a particular application?

How to Pick an Elliptic Curve

There are two major curve families used in cryptography: binary curves constructed from GF(2^m), and prime curves constructed from GF(pⁿ), where p is a prime greater than 3 and n is usually 1. Binary curves are the best choice for hardware applications, where it takes remarkably few logic gates to create a powerful and incredibly fast cryptosystem. In software, prime curves are faster because the extended bit-fiddling operations needed by binary curves are not necessary. Here, I'll focus on prime curves, since it was a software-based project of mine that prompted this article.

In a prime field, a little algebra reduces the elliptic-curve equation from the form y²+a₁xy+a₃y=x³+a₂x²+a₄x+a₆ to the form y²=x³+Ax+B, where A,BGF(pⁿ) and 4A³+27B²0. Therefore, you need to pick four parameters A, B, p, and n to select a particular curve. If n>1, the extension polynomial must also be chosen (see Figure 2). Not all parameters are equally secure, nor do they result in curves with equally efficient operations. In fact, when selecting values for the curve parameters, efficiency and security are often traded off against each other, sometimes in surprising ways.

Not just any values of A, B, p, and n can be used for cryptography. If the order of the curve group happens to be exactly equal to p, the curve is called anomalous and is prone to subexponential discrete logarithm algorithms. Similarly, if the curve does not satisfy the Menezes-Okamoto-Vanstone (MOV) condition, or if the curve is supersingular, it is unsuitable for cryptography. Fortunately, the vast majority of curves are secure, and it is simple and fast to validate the security of a given curve.

As cryptographers, we need to assume that even if a cryptosystem is safe today, it may not be safe tomorrow. For instance, EC operations in a prime field are fastest when p3mod4 and A=0. Such curves are said to have complex multiplication discriminant 3 (CM3). Theoretically, these CM3 curves are just as secure as any other elliptic curve. A true paranoid would be worried, however, because given any finite field, mathematicians have shown that there are only six different CM3 curves. Although we may have millions of choices for B yielding millions of curves, each curve is isomorphic to one of just six different curves. Cryptographers already know how to attack certain specialized curves, such as the supersingular, MOV, or anomalous curves. CM3 curves are arguably a very restricted curve family, so they may be the next to fall to mathematical cryptanalysis. I am not implying that CM3 curves are insecure. They just seem like a good target for concerted mathematical attack over the next 10 to 20 years.

Another family of prime field curves with efficient computational properties are those that have n=1 and A-3modp. These curves aren't quite as algorithmically efficient as the CM3 curves, but there are a lot more of them. Depending on p, up to 1/2 of all curves can be rescaled to have this value for A. Therefore, any attempt to find an algorithm for fast discrete logs with these curves would have to be very general in application, weakening ECC in its entirety. It's very unlikely that any such attack is forthcoming.

These security considerations suggest selecting n=1 and A-3modp for long-lived, software-based ECC applications. For picking specific EC and cryptosystem parameters, there are only two guides: Make it fast and make it efficient.

Picking Cryptosystem Parameters

With the goal of speed in mind, Daniel Bailey and Christof Paar presented an interesting paper at the CRYPTO'98 conference. They suggested using primes of the form p=2ⁿ±c and extension polynomials of the form x^m- to form the elliptic curve's base field. That way, the base p modular reductions could be done rapidly using the Mohan-Adiga algorithm in Figure 3. Reducing polynomials modulo the monomial x^m- can also be accomplished very quickly using the identity

Using Bailey and Paar's techniques, I found that p=2³¹-1 with an extension of x⁷-(2²⁴+1) gave an EC group size of about 217 bits -- equivalent to using a 108-bit symmetric key. This field is also very efficient to work with on 32-bit processors. Unfortunately, ECC using primes of the form 2ⁿ-c for c>-1 has been patented, a fact unnoticed by many researchers. I did find other suitable fields, such as GF(2³¹+209) with extension x⁷-5, but none had the efficiency of GF(2³¹-1). The lesson to learn here is that you must always be aware of the intellectual property you are using.

Fortunately, the Mohan-Adiga algorithm is equally efficient with positive or negative values of c, and primes of the form p=2ⁿ+c with c>2 are still free for use. However, given the upcoming popularity of 64-bit processors, why limit our cryptosystem to efficiency on 32-bit CPUs? Instead, are there any GF(p) fields with suitable characteristics that enable fast computation?

When selecting EC parameters, you have to pick curves where you can quickly calculate the exact EC group order. Although algorithms are known for counting the elements of an arbitrary elliptic curve, the procedures are rather complicated and require O(ln⁸n) time. For two certain families of curves, it is much easier to find #E. In the first case, if p is small and n>1 in GF(pⁿ), you can use the relation between the base field and the extension field to quickly count the curve's points. In the second case, you look for curves with a known complex multiplication discriminant. CM3 curves, for instance, have complex multiplication discriminant 3, which means there is a simple formula for counting the elements. The P1363 draft describes simple algorithms for finding the CM discriminant of many curves. I used the techniques specified in the draft to find the group orders of my test curves.

Furthermore, I looked at primes for which Mohan-Adiga reduction is particularly efficient. Because c>2, maximum efficiency implies that the algorithm's bit shifting should be as fast as possible. Using a patient trial-and-error search, I found two potential candidates. The first was p=2²⁴⁸+81, where I found many curves with group sizes of 245 to 249 bits. Because 248 is divisible by 8, the right shifts required by the Mohan-Adiga algorithm could be implemented as byte-oriented memory moves. Unfortunately, using memory moves instead of bit shifts would only be possible if the storage pattern of the GF(p) integer matched the endianness of the CPU. Because I didn't want to maintain different large-integer libraries for different CPUs, I decided to pick another value for p. Finally, I selected p=2²⁵⁵+95 to serve as my base field.

The prime p=2²⁵⁵+95 has many computational advantages over other field characteristics.

• The prime p3mod4, which means that calculating square roots in GF(p) is simple and there is a good chance we can find a secure curve where A-3modp.

• Each element xGF(p) can be represented by a 256-bit array. This array is easily partitioned into 16-, 32-, or 64-bit words for big-integer libraries.

• The 256-bit array is ideal for O(nlog₂3^1.585) Karatsuba-Ofman multiplication, regardless of the native word size of the target CPU.

• The right shifts can be implemented as a 256-bit aligned memory move, followed by a 1-bit left shift. This operation is relatively endian independent, and can be accelerated in assembly language.

These advantages are tempered by two small disadvantages:

• Right-shifting 255 times requires two passes through the array holding the GF(p) large integer.

• Multiplication by c=95 is not particularly fast, although since c fits within a single byte, multiplying an element of GF(p) by c is a linear-time operation.

While sorting through various CM discriminants, I found that GF(2²⁵⁵+95) allows the construction of a curve that has complex multiplication by 1318, yielding a curve with a 254-bit prime factor of the group order. This is remarkably useful, since it means that 254 bits of our 256-bit operations are contributing to the cryptosystem's security. Calculating logs in this group is as difficult as brute force guessing a 127-bit symmetric key. It's been estimated that for data to remain secure for the next 20 years, the effective key size of an algorithm should be at least 90 bits. An effective key size of 127 bits is comfortably larger than this estimate. As an added bonus, the technique of point compression lets you represent the 510 bits of any EC point (x,y)E with exactly 256 bits, and, therefore, it fits evenly in any byte array.

I've implicitly assumed that the cryptosystem I'm building will have shared parameters for a group of users. They will all use the same curve, and hopefully all use the same base point. These shared-parameter cryptosystems are accepted in the cryptocommunity as secure; so much so that even the DSA allows them. However, they definitely present an attractive target for a cryptanalyst to attack, so it's important that any shared-parameter cryptosystem have some security wiggle room. In my case, if the complexity of taking discrete logs in the curve group was mathematically reduced by even a huge 2³², the cryptosystem will still be quite secure.

The specific curve and cryptoparameters I chose are in Figure 2. I managed to find a base point of appropriate order with an x-coordinate of two. This base point is nice for embedded systems, where secure memory holding cryptoparameters is a scarce resource. With this choice of base point, only the y-coordinate needs permanent secure storage. Alternatively, the y-coordinate could be generated in situ by selecting the smaller square root of z=x³+Ax+B. Since p3mod4, it is simple to calculate z=±(z^(p+1)/4)modp, and select the smaller root (in this case, the positive one). Therefore, of all the parameters in Figure 2, only B needs to be stored as a full-sized large integer. In fact, only one of B or g_y needs to be stored in secure memory. However, without B, it is impossible to determine if any given input coordinate really is on our elliptic curve. Therefore, it is probably more secure to keep B in memory, use it to generate g_y, and also use it to validate any other input EC point.

Real-World Comparisons

Cryptographic literature is full of theoretical calculations estimating how much faster EC algorithms should be over their traditional counterparts. Many of these comparisons are misleading because they do not compare security-equivalent cryptosystems, and implementing a cryptosystem usually requires a lot of CPU-dependent programming. To do a fair comparison, I decided to benchmark Certicom's Elliptic Curve Digital Signature Algorithm (ECDSA), implemented with my 255-bit curve, against the standard DSA algorithm at p=2048 bits, with a subgroup of q=256 bits. Theoretically, 255 EC bits are equal to more than 2800 Z^*_p bits, but a real programmer would stick to 2048 bits allowing the fastest possible use of Karatsuba-Ofman multiplication. Further, the DSA standard specifically forbids moduli greater than 1024 bits or subgroups larger than 160 bits, because DSA is based on the 160-bit SHA1 hash function (which itself provides only 80 effective bits of security). However, we are interested in raw speed comparisons, so signing and verifying longer hashes should only accentuate any speed difference.

The points on an elliptic curve actually have two different representations, each of which has very different computational characteristics. The normal (x,y) pairs we have been discussing, called "affine coordinates," are most commonly seen in discussions of curves over finite fields. There is another representation of the point, called "projective coordinates," where the triplet (x,y,z) satisfies the modified equation y²z=x³+Axz²+Bz³. We can translate between affine and projective coordinates using the relation (x,y)(x²,y³,) for any 0. By convention, we set =1 for equating the two. The reason for using projective coordinates over affine has to do with how the EC points are added together. Using affine coordinates, two to three field multiplications and one field inversion are needed to add EC points. Using projective coordinates, no field inversions and 11 to 16 field multiplications are needed to add EC points. If field inversion is a relatively slow operation, it may be faster to use projective coordinates despite the larger number of multiplications.

The results of six test cases run over three slightly different CPUs are shown in Table 1. All the tests were compiled with egcs-1.1.1 under Linux-2.2.5/glibc-2.1.1. The large-integer library came from the GNU Privacy Guard (GnuPG) project (http://www.gnupg.org/), Version0.9.5. Hand-optimized assembler code was available and used for the major time-critical functions of the library. The table compares both the absolute and relative speeds of performing signature and verification operations between:

• The standard DSA with p/q values of1024/160 and2048/256.

• My ECDSA system in using either projective or affine coordinates.

• For each ECDSA coordinate representation, a trial using the Mohan-Adiga algorithm or GnuPG's standard modular reduction algorithm.

The CPU row shows the speed of DSA-1024 normalized to the fastest processor. Otherwise, the CPU time results are shown normalized to the speed of DSA-1024. The three processors are a:

• Celeron with 128K L2 cache at 450/75MHz core/bus frequency.
• P-II with 512K L2 cache at 266/66 MHz.

• Mobile P5 with 512K L2 cache at 166/66 MHz.

The first interesting result is that all the cryptosystems tested fit comfortably into the Celeron's relatively tiny 128-KBL2 cache. Across each CPU family, the relative speed of each operation was essentially constant and was simply a multiple of the CPU core frequency ratios; thus, it is clear that each cryptosystem occupies relatively little L2 cache.

The next interesting conclusion is that using the special modular reduction algorithm is no faster, and in some cases slower, than the GnuPG's modular reduction algorithm for arbitrary bases. Although the trials presented in Table 1 do not use forced function inlining for the Mohan-Adiga algorithm, my experiments with forced full inlining indicate function call overhead is responsible for only5 to 7 percent of the overall calculation time. It seems that using a special form for p does not seriously affect the speed of the EC cryptosystem for an optimized large-integer library.

With respect to comparing affine and projective coordinates, the projective coordinates are much faster to use than affine, giving an eight-fold increase in speed despite the large number of modular multiplications that the technique uses. Run-time profiles of the executables show a huge amount of time spent in the modular inversion step for the affine case, as expected. In the projective case, 90 percent of the computation is evenly split between large-integer multiplication, addition, and modular reduction, each of which is a highly optimized subroutine in its own right.

Testing ECDSA against DSA showed a surprising result: At its fastest, my ECDSA was between 25 and 80 percent slower than DSA-1024. Of course, at 1024 bits, DSA does not provide the security of a 254-bit EC scheme. Comparing apples to apples, ECDSA clocked well over twice as fast as the security-equivalent DSA-2048. Although interesting, this factor of two falls far short of the four- to eight-fold speedups often talked about in EC whitepapers.

Table 2

Conclusion

Software-based prime field elliptic-curve cryptosystems seem to be more efficient than traditional cryptosystems at high levels of security. The small sizes of their public and private keys are a definite advantage, although one that holds only if all ECC users agree on a common set of EC parameters. If EC parameters need to be negotiated on a message-to-message basis, the additional information needed to specify the exact elliptic curve may make the effective EC key size almost as large as a key in Z^*_p.

References

IEEE draft standard P1363: Standards for Public-Key Cryptography, available at http:// stdsbbs.ieee.org/groups/1363/index.html.

Koblitz, Neal. Algebraic Aspects of Cryptography. Springer-Verlag, 1998.

-- -- -- . A Course in Number Theory and Cryptography, Second Edition. Springer-Verlag, 1994.

Menezes, Alfred. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publications, 1993.

Menezes, Alfred, vanOorschot, Paul, and Vanstone, Scott. Handbook of Applied Cryptography. CRC Press, 1997.

DDJ