Elliptic Curve Cryptography - Asymmetric Ciphers - Modern Cryptography: Applied Mathematics for Encryption and Informanion Security (2016)

Modern Cryptography: Applied Mathematics for Encryption and Informanion Security (2016)

PART III. Asymmetric Ciphers

Chapter 11. Elliptic Curve Cryptography

In this chapter we will cover the following:

image The basic math of elliptic curves

image Elliptic curve groups as a basis for cryptography

image ECC variations

The elliptic curve may be the most mathematically challenging algorithm that you will encounter in this book, or in any other introductory cryptography book. If you feel uncertain of your mathematical acumen, it might help to review Chapters 4 and particularly 5. Throughout this chapter, brief reminders cover key mathematical concepts to help you follow along. If your goal is a career related to cryptography, then you will at some point need to master this material. However, if you simply want to get a general overview of cryptography, with a primary focus on computer/network security, you will finish this chapter with a broad overview of elliptic curve cryptography.

Note

Because this topic is often difficult for many readers, this chapter (albeit a short one) has been devoted to just this topic. Furthermore, in some cases, key concepts are explained more than once with slightly different wording to try and aid your understanding.

Elliptic curve cryptography (ECC) is difficult for many people to learn because few people have prior exposure to the underlying mathematics. If you compare ECC to RSA, for example, the difficulty of ECC is quite clear. Most people were exposed to prime numbers, factoring numbers, raising a number to a certain power, and basic arithmetic in primary and secondary school. But far fewer people were exposed to elliptic curves and discrete logarithms in school.

General Overview

Elliptic curves have been studied, apart from cryptographic applications, for well over a century. As with other asymmetric algorithms, the mathematics have been a part of number theory and algebra long before being applied to cryptography. As you saw in Chapter 10, many asymmetric algorithms depend on algebraic groups. There are multiple ways to form finite groups, including elliptic curves, making them appropriate for cryptographic purposes.

There are two types of elliptic curve groups. The two most common (and the ones used in cryptography) are elliptic curve groups based on Fp, where p is prime, and those based on F2m. F, as you will see in this chapter, is the field being used. F is used because we are describing a field. ECC is an approach to public-key cryptography based on elliptic curves over finite fields.

Tip

Remember that a field is an algebraic system consisting of a set, an identity element for each operation, two operations, and their respective inverse operations. A finite field, also called a Galois field, is a field with a finite number of elements. That number is called the order of the field.

Using elliptic curves for cryptographic purposes was first described in 1985 by Victor Miller (IBM) and Neal Koblitz (University of Washington). The security of ECC is based on the fact that finding the discrete logarithm of a random or arbitrary elliptic curve element with respect to a publicly known base point is difficult to the point of being impractical to do.1

Note

Neal Koblitz is a mathematics professor at the University of Washington and a very well-known cryptographic researcher. In addition to his work on ECC, he has published extensively in mathematics and cryptography. Victor Miller is a mathematician with the Institute for Defense Analysis in Princeton. He has worked on compression algorithms, combinatorics, and various subtopics in the field of cryptography.

What Is an Elliptic Curve?

An elliptic curve is the set of points that satisfy a specific mathematical equation. Keep in mind that an elliptic curve is not the same thing as an ellipse and should not be confused with one. The equation for an elliptic curve looks something like this:

y2 = x3 + Ax + B

You can see this equation graphed in Figure 11-1. There are other ways to represent an elliptic curve, but Figure 11-1 is the most common and perhaps the easiest to understand.

Images

FIGURE 11-1 The graph of an elliptic curve

Note

An elliptic curve is not the same as an ellipse.

Another way to describe an elliptic curve is that it is simply the set of points that satisfy an equation that has two variables in the second degree and one variable in the third degree. Notice the horizontal symmetry in the graph in Figure 11-1. Any point on the curve can be reflected about the x-axis without changing the shape of the curve.

In his book Elliptic Curves: Number Theory and Cryptography, Professor Lawrence Washington of the University of Maryland describes an elliptic curve a bit more formally:

…an elliptic curve E is the graph of an equation of the form y2 = x3 + Ax + B, where A and B are constants. This will be referred to as the Weierstrass equation for an elliptic curve. We will need to specify what set A, B, x, and y belong to. Usually, they will be taken to be elements of a field, for example, the real numbers R, the complex numbers C, the rational numbers Q, one of the finite fields Fp (=Zp) for a prime p, or one of the finite fields Fq, where q = pk with k ≥ 1.2

Note

This chapter provides only an overview of elliptic curve cryptography. Washington’s book is an excellent source for more detail. There have been two editions of his book; I have both books and I highly recommend them. However, the book assumes a level of mathematical sophistication that this book does not.

The operation used with the elliptic curve is addition (remember that, by definition, a group requires a set along with an operation). Thus elliptic curves form additive groups.

Review of the Definition of Groups in Algebra

A group is an algebraic system consisting of a set, an identity element, one operation, and its inverse operation. An abelian group, or commutative group, has an additional axiom a + b = b + a if the operation is addition, and ab = ba if the operation is multiplication. A cyclic group has elements that are all powers of one of its elements.

Basic Operations on Elliptic Curves

The members of the elliptic curve field are integer points on the elliptic curve. You can perform addition with points on an elliptic curve. Throughout this chapter, as well as in most of the literature on elliptic curves, two points are considered: P and Q. The negative of a point P = (xP,yP) is its reflection in the x-axis: the point –P is (xP,–yP). Notice that for each point P on an elliptic curve, the point –P is also on the curve. Suppose that P and Q are two distinct points on an elliptic curve, and assume that P is not merely the inverse of Q. To add the points P and Q, a line is drawn through the two points. This line will intersect the elliptic curve in exactly one more point, called –R. The point –R is reflected in the x-axis to the point R. The law for addition in an elliptic curve group is P + Q = R.

The line through P and –P is a vertical line that does not intersect the elliptic curve at a third point; thus the points P and –P cannot be added as previously. It is for this reason that the elliptic curve group includes the point at infinity O. By definition, P + (–P) = O. As a result of this equation, P + O = P in the elliptic curve group. O is called the additive identity of the elliptic curve group; all elliptic curves have an additive identity. Figure 11-2 shows a graph of an elliptic curve.

Images

FIGURE 11-2 P + (–P)

To add a point P to itself, a tangent line to the curve is drawn at the point P. If yP is not 0, then the tangent line intersects the elliptic curve at exactly one other point, –R. –R is reflected in the x-axis to R. This operation is called “doubling the point P” and is shown in Figure 11-3.

Images

FIGURE 11-3 Doubling the P

The tangent at P is always vertical if yP = 0.

If a point P is such that yP = 0, then the tangent line to the elliptic curve at P is vertical and does not intersect the elliptic curve at any other point. By definition, 2P = O for such a point P.

Recall that the field Fp uses the numbers from 0 to p – 1, and computations end by taking the remainder on division by p (i.e. the modulus operations). For example, in F23 the field is composed of integers from 0 to 22, and any operation within this field will result in an integer also between 0 and 22.

An elliptic curve with the underlying field of Fp can be formed by choosing the variables a and b within the field of Fp. The elliptic curve includes all points (x,y) that satisfy the elliptic curve equation modulo p (where x and y are numbers in Fp). For example: y2 mod p = x3 + ax + b mod p has an underlying field of Fp if a and b are in Fp.

Note

In some cases in this chapter, I use uppercase A and B, and in others, lowercase. In this situation, the case of the letters is irrelevant and you will see both used in the literature. So both are used here to acclimate you to this fact.

If x3 + ax + b contains no repeating factors, then the elliptic curve can be used to form a group. An elliptic curve group over Fp consists of the points on the corresponding elliptic curve, together with a special point O called the point at infinity. There are finitely many points on such an elliptic curve.

At the foundation of every cryptosystem is a hard mathematical problem that is computationally infeasible to solve. The discrete logarithm problem is the basis for the security of many cryptosystems including the ECC. More specifically, the ECC relies upon the difficulty of the elliptic curve discrete logarithm problem (ECDLP).

Recall that we examined two geometrically defined operations over certain elliptic curve groups: point addition and point doubling. By selecting a point in a elliptic curve group, you can double it to obtain the point 2P. After that, you can add the point P to the point 2P to obtain the point 3P. The determination of a point nP in this manner is referred to as scalar multiplication of a point. The ECDLP is based upon the intractability of scalar multiplication products.

In the multiplicative group Zp*, the discrete logarithm problem is this: given elements r and q of the group, and a prime p, find a number k such that r = qk mod p. If the elliptic curve group is described using multiplicative notation, then the elliptic curve discrete logarithm problem is this: given points P and Q in the group, find the number k such that kP = Q; in this case, k is called the discrete logarithm of Q to the base P. When the elliptic curve group is described using additive notation, the elliptic curve discrete logarithm problem is this: given points P and Q in the group, find a number k such that Pk = Q.

The following is a common example used in many textbooks, papers, and web pages. It uses rather small numbers that you can easily work with but makes the general point of how elliptic curve cryptography works. This is not adequate for cryptographic purposes; it is provided only to help you get a feel for how ECC works.

In the elliptic curve group defined by

y2 = x3 + 9x + 17 over F23

What is the discrete logarithm k of Q = (4,5) to the base P = (16,5)?

One way to find k is to compute multiples of P until Q is found. The first few multiples of P are

P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10)
6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5)

Since 9P = (4,5) = Q, the discrete logarithm of Q to the base P is k = 9.

In a real application, k would be large enough such that it would be infeasible to determine k in this manner. This is the essence of ECC. When implementing ECC in the real world, obviously we use larger fields—much larger.

Tip

If you are still struggling with the concepts of elliptic curves, the excellent online tutorial, “A (Relatively Easy to Understand) Primer on Elliptic Curve Cryptography,” does a good job of explaining these concepts. You might find that reviewing that tutorial and then rereading this section aids in your understanding. See http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/.

The Algorithm

In the preceding section we discussed elliptic curves in general; in this section we will discuss specific applications to cryptography. In cryptographic applications, the elliptic curve along with some distinguished point at infinity is used along with the group operation of the elliptic group theory to form an abelian group, with the point at infinity as the identity element. The structure of the group is inherited from the divisor group of the underlying algebraic variety.

For cryptographic purposes, we will restrict ourselves to numbers in a fixed range—only integers are allowed. You must also select a maximum value. If you select the maximum to be a prime number, the elliptic curve is called a “prime curve” and can be used for cryptographic applications.

To use ECC, all parties must agree on all the elements defining the elliptic curve—that is, the domain parameters of the scheme. The field is defined by p in the prime case and the pair of m and f in the binary case. To focus on the prime case (the simpler), the field is defined by some prime number p. The elliptic curve is defined by the constants A and B used in the equation

y2 = x3 + Ax + B

Finally, the cyclic subgroup is defined by its generator (that is, base point) G.

The elliptic curve is the points defined by the preceding equation, with an extra point O, which is called the “point at infinity”—keep in mind that point O is the identity element for this group.3

Given a point P = (x,y) and a positive integer n, you define [n]P = P + P + ... + P (n times). The order of a point P = (x,y) is the smallest positive integer n such that [n]P = O.

You denote by < P > the group generated by P. In other words, < P > = {O, P, P+P, P+P+P, …}.

Now that you have a group defined by an elliptic curve, the security of elliptic curve cryptography is provided by the ECDLP: given an elliptic curve C defined over Fθ and two points P, Q that are elements of the curve C, find an integer x such that Q = xP.

Discrete Logarithm Review

To understand discrete logarithms, keep in mind the definition of a logarithm: the number to which some base must be raised to get another number. Discrete logarithms ask this same question but do so in regard to a finite group. Put more formally, a discrete logarithm is some integer k that solves the equation xk = y, where both x and y are elements of a finite group. A discrete logarithm is, essentially, a logarithm within some finite group.

In the preceding section you saw basic math, specifically addition, within an elliptic curve. You can choose any two points on an elliptic curve and produce another point. The process is not particularly complicated. You first begin with two points P1 and P2. These are defined as

P1 = (x1, y1)

P2 = (x2, y2)

The curve itself is symbolized as E, given by the equation you already have seen: y2 = x3 + AX + B.

Now to define a new point, you call P3, draw a line (let’s call it L) through points P1 and P2. You can see that no matter where P1 and P2 are, this line L will intersect E (the elliptic curve) at a third point P3, as shown in Figure 11-4.

Images

FIGURE 11-4 Line intersecting curve E

You can reflect that across the x-axis (simply change the sign of the y coordinate) and you have P3.

As you already know, an elliptic curve is the set of points that satisfy a specific mathematical equation. The equation for an elliptic curve looks something like this:

y2 = x3 + ax + b

and some point at infinity. This means that choosing different values for a and b changes the elliptic curve.

The size of the elliptic curve determines the difficulty of finding the discrete logarithm, and thus the security of the implementation. The level of security afforded by an RSA-based system with a large modulus can be achieved with a much smaller elliptic curve group. This is one strong reason why ECC has generated so much interest.

The U.S. National Security Agency has endorsed ECC algorithms and allows their use for protecting information classified up to top secret with 384-bit keys, which is important because 384-bit keys are much smaller than RSA keys. ECC achieves a level of security at least equal to RSA, but with key sizes almost as small as symmetric algorithms such as AES.

ECC Variations

As you can see from the previous sections, elliptic curves form groups, and those groups can be used just as any other algebraic group. The practical implication of this is that you can adapt various algorithms to elliptic curve groups. There are many permutations of elliptic curve cryptography including the following:

image Elliptic Curve Diffie-Hellman (used for key exchange) (ECDH)

image Elliptic Curve Digital Signature Algorithm (ECDSA)

image Elliptic Curve MQV key agreement protocol

image Elliptic Curve Integrated Encryption Scheme (ECIES)

In this section we will take a closer look at two of these.

ECC Diffie-Hellman

Diffie-Hellman, which you studied in Chapter 10, is the oldest key exchange protocol. It is natural to modify for elliptic curves. Elliptic Curve Diffie-Hellman (ECDH) is a key exchange or key agreement protocol used to establish a shared secret over an insecure medium. That shared secret is then either used directly or as the basis to derive another key. In the case of ECDH, the public private key pairs are based on elliptic curves.

image Public: Elliptic curve and point (x,y) on curve

image Secret: Alice’s A and Bob’s B

image Alice computes A(B(x,y))

image Bob computes B(A(x,y))

image These are the same since AB = BA.

image Public: Curve y2 = x3 + 7x + b (mod 37) and point (2,5) ⇒ b = 3

image Alice’s secret: A = 4

image Bob’s secret: B = 7

image Alice sends Bob: 4(2,5) = (7,32)

image Bob sends Alice: 7(2,5) = (18,35)

image Alice computes: 4(18,35) = (22,1)

image Bob computes: 7(7,32) = (22,1)

Note

For more details consult NIST document 800-56A Revision 2, at http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf.

Elliptic Curve Digital Signature Algorithm

The Digital Signature Algorithm (DSA) was invented specifically for digitally signing messages. Of course, you can use any asymmetric algorithm to sign a message, but the DSA was designed for that purpose. As I mentioned, there is an elliptic curve variation on this algorithm.

To illustrate how this works, let’s again consider the fictitious Bob and Alice. First the two parties must agree on some parameters: the curve, denoted as E; the base point/generator of the elliptic curve, denoted as G; and the order of G (an integer), denoted by n. Now to sign a message, Alice takes the following steps:

1. Select a random integer k that is less than n (that is, k > 1; k < n).

2. Compute kG = (x1,y1) and r = x1 mod n. If r = 0 then go to step 1.

3. Compute k1 mod n.

4. Compute e = SHA-1(m). Most digital signature algorithms use a hash; in this case the hash is usually SHA-1. So this is stating that you compute the SHA-1 hash of the message.

5. Compute s = k–1{e + dA . r} mod n.

6. If s = 0, then go to step 1. In other words, keep repeating until s! = 0. This is not usually time-consuming and could happen on the first attempt.

7. Alice’s signature for the message m is (r, s).

In order for Bob to verify Alice’s signature (r,s), he will execute the following steps:

1. Verify that r and s are integers in [1,n – 1].

2. Compute e = SHA-1(m).

3. Compute w = s–1 mod n.

4. Compute u1 = ew mod n and u2 = rw mod n.

5. Compute (x1,y1) = u1G + u2 QA.

6. Compute v = x1 mod n.

7. Accept the signature if and only if v = r.

This is very much like the traditional DSA, except that it is using elliptic curve groups. ECDSA is quite secure.

Note

There have been a few reported breaches of ECDSA, but those were based on faulty implementations, not on the algorithm itself being insecure. For example, in March 2011, researchers published a paper with the IACR (International Association of Cryptological Research) demonstrating that it is possible to retrieve a TLS private key of a server using OpenSSL in a timing attack. OpenSSL authenticates with ECDSA over a binary field. However, the vulnerability was fixed in a subsequent release of OpenSSL and was an implementation issue, not a flaw in the algorithm.

Conclusions

In this chapter we have examined the use of elliptic curve groups for cryptography. This may be the most mathematically challenging chapter in this entire book. For most security applications, you need only be aware of the general description of the various elliptic curve algorithms. For those of you interested in pursuing cryptography in more depth, this chapter provides an introduction to this topic. Various resources have been suggested in this chapter that will give you more detail and depth on ECC.

Test Your Knowledge

1. Which of the following equations is most related to elliptic curve cryptography?

A. Me % n

B. P = Cd % n

C. Ce % n

D. y2 = x3 + Ax + B

2. Which ECC variation requires the use of SHA?

3. What is an algebraic group?

4. What is a discrete logarithm?

5. What kind of key does ECC DH product?

Answers

1. D

2. ECDSA

3. A group is an algebraic system consisting of a set, an identity element, one operation, and its inverse operation.

4. A discrete logarithm is some integer k that solves the equation xk = y, where both x and y are elements of a finite group.

5. Ephemeral key

Endnotes

1. For more information on ECC, read “Elliptic Curve Cryptography,” a paper by Vivek Kapoor, Vivek Sonny Abraham, and Ramesh Singh, at http://csis.bits-pilani.ac.in/faculty/murali/netsec-10/seminar/refs/abhishek3.pdf.

2. Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Second Edition (Chapman and Hall/CRC, 2008).

3. For more information on ECC, see the Guide to Elliptic Curve Cryptography by Darrel Hankerson, Alfred Menezes, and Scott Vanstone (Springer Professional Computing, 2004).