5.4. Elliptic curve cryptography 299 Alice computes QA = nAP = 2489(920, 303) = (593, 719) ∈ E(F3851), Bob computes QB = nBP = 2286(920, 303) = (3681, 612) ∈ E(F3851). However, rather than sending both coordinates, Alice sends only xA = 593 to Bob and Bob sends only xB = 3681 to Alice. Alice substitutes xB = 3681 into the equation for E and finds that y2 B = x3 B + 324xB + 1287 = 36813 + 324 · 3681 + 1287 = 997. (Recall that all calculations are performed in F3851.) Alice needs to compute a square root of 997 modulo 3851. This is not hard to do, especially for primes satisfying p ≡ 3 (mod 4), since Proposition 2.27 tells her that b(p+1)/4 is a square root of b modulo p. So Alice sets yB = 997(3851+1)/4 = 997963 ≡ 612 (mod 3851). It happens that she gets the same point QB = (xB, yB) = (3681, 612) that Bob used, and she computes nAQB = 2489(3681, 612) = (509, 1108). Similarly, Bob substitutes xA = 593 into the equation for E and takes a square root, y2 A = x3 A + 324xA + 1287 = 5933 + 324 · 593 + 1287 = 927, yA = 927(3851+1)/4 = 927963 ≡ 3132 (mod 3851). Bob then uses the point Q′ A = (593, 3132), which is not Alice’s point QA, to compute nBQ′ A = 2286(593, 3132) = (509, 2743). Bob and Alice end up with points that are negatives of one another in E(Fp), but that is all right, since their shared secret value is the x-coordinate x = 593, which is the same for both points. 5.4.2 Elliptic ElGamal public key cryptosystem It is easy to create a direct analogue of the ElGamal public key cryptosys- tem described in Section 2.4. Briefly, Alice and Bob agree to use a particular prime p, elliptic curve E, and point P ∈ E(Fp). Alice chooses a secret multi- plier nA and publishes the point QA = nAP as her public key. Bob’s plaintext is a point M ∈ E(Fp). He chooses an integer k to be his ephemeral key and computes C1 = kP and C2 = M + kQA. He sends the two points (C1, C2) to Alice, who computes C2 − nAC1 = (M + kQA) − nA(kP ) = M + k(nAP ) − nA(kP ) = M to recover the plaintext. The elliptic ElGamal public key cryptosystem is summarized in Table 5.6. In principle, the elliptic ElGamal cryptosystem works fine, but there are some practical difficulties.
300 5. Elliptic Curves and Cryptography Public Parameter Creation A trusted party chooses and publishes a (large) prime p, an elliptic curve E over Fp, and a point P in E(Fp). Alice Bob Key Creation Chooses a private key nA. Computes QA = nAP in E(Fp). Publishes the public key QA. Encryption Chooses plaintext M ∈ E(Fp). Chooses an ephemeral key k. Uses Alice’s public key QA to compute C1 = kP ∈ E(Fp). and C2 = M + kQA ∈ E(Fp). Sends ciphtertext (C1, C2) to Alice. Decryption Computes C2 − nAC1 ∈ E(Fp). This quantity is equal to M . Table 5.6: Elliptic ElGamal key creation, encryption, and decryption 1. There is no obvious way to attach plaintext messages to points in E(Fp). 2. The elliptic ElGamal cryptosystem has 4-to-1 message expansion, as compared to the 2-to-1 expansion ratio of ElGamal using Fp. (See Re- mark 2.9.) The reason that elliptic ElGamal has a 4-to-1 message expansion lies in the fact that the plaintext M is a single point in E(Fp). By Hasse’s theorem (Theorem 5.11) there are approximately p different points in E(Fp), hence only about p different plaintexts. However, the ciphertext (C1, C2) consists of four numbers modulo p, since each point in E(Fp) has two coordinates. Various methods have been proposed to solve these problems. The diffi- culty of associating plaintexts to points can be circumvented by choosing M randomly and using it as a mask for the actual plaintext. One such method, which also decreases message expansion, is described in Exercise 5.16. Another natural way to improve message expansion is to send only the x- coordinates of C1 and C2, as was suggested for Diffie–Hellman key exchange in Remark 5.20. Unfortunately, since Alice must compute the difference C2 − nAC1, she needs the correct values of both the x-and y-coordinates of C1 and C2. (Note that the points C2 − nAC1 and C2 + nAC1 are quite different!) However, the x-coordinate of a point determines the y-coordinate up to change of sign, so Bob can send one extra bit, for example
5.5. The evolution of public key cryptography 301 Extra bit = { 0 if 0 ≤ y < 1 2 p, 1 if 1 2 p < y < p (See Exercise 5.15.) In this way, Bob needs to send only the x-coordinates of C1 and C2, plus two extra bits. This idea is sometimes referred to as point compression. 5.5 The evolution of public key cryptography The invention of RSA in the late 1970s catapulted the problem of factoring large integers into prominence, leading to improved factorization methods such as the quadratic and number field sieves described in Section 3.7. In 1984, Hendrik Lenstra Jr. circulated a manuscript describing a new factorization method using elliptic curves. Lenstra’s algorithm [71], which we describe in Section 5.6, is an elliptic analogue of Pollard’s p − 1 factorization algorithm (Section 3.5) and exploits the fact that the number of points in E(Fp) varies as one chooses different elliptic curves. Although less efficient than sieve methods for the factorization problems that occur in cryptography, Lenstra’s algorithm helped introduce elliptic curves to the cryptographic community. The importance of factorization algorithms for cryptography is that they are used to break RSA and other similar cryptosystems. In 1985, Neal Koblitz and Victor Miller independently proposed using elliptic curves to create cryp- tosystems. They suggested that the elliptic curve discrete logarithm problem might be more difficult than the classical discrete logarithm problem modulo p. Thus Diffie–Hellman key exchange and the ElGamal public key cryptosystem, implemented using elliptic curves as described in Section 5.4, might require smaller keys and run more efficiently than RSA because one could use smaller numbers. Koblitz [62] and Miller [79] each published their ideas as academic papers, but neither of them pursued the commercial aspects of elliptic curve cryptog- raphy. Indeed, at the time, there was virtually no research on the ECDLP, so it was difficult to say with any confidence that the ECDLP was indeed significantly more difficult than the classical DLP. However, the potential of what became known as elliptic curve cryptography (ECC) was noted by Scott Vanstone and Ron Mullin, who had started a cryptographic company called Certicom in 1985. They joined with other researchers in both academia and the business world to promote ECC as an alternative to RSA and ElGamal. All was not smooth sailing. For example, during the late 1980s, various cryptographers proposed using so-called supersingular elliptic curves for added efficiency, but in 1990, the MOV algorithm (see Section 5.9.1) showed that supersingular curves are vulnerable to attack. Some saw this as an indictment of ECC as a whole, while others pointed out that RSA also has weak instances that must be avoided, e.g., RSA must avoid using numbers that can be easily factored by Pollard’s p − 1 method.
302 5. Elliptic Curves and Cryptography The purely mathematical question whether ECC provided a secure and efficient alternative to RSA was clouded by the fact that there were com- mercial and financial issues at stake. In order to be commercially successful, cryptographic methods must be standardized for use in areas such as commu- nications and banking. RSA had the initial lead, since it was invented first, but RSA was patented, and some companies resisted the idea that standards approved by trade groups or government bodies should mandate the use of a patented technology. ElGamal, after it was invented in 1985, provided a royalty-free alternative, so many standards specified ElGamal as an alterna- tive to RSA. In the meantime, ECC was growing in stature, but even as late as 1997, more than a decade after its introduction, leading experts indicated their doubts about the security of ECC.7 A major dilemma pervading the field of cryptography is that no one knows the actual difficulty of the supposedly hard problems on which it is based. Currently, the security of public key cryptosystems depends on the percep- tion and consensus of experts as to the difficulty of problems such as integer factorization and discrete logarithms. All that can be said is that “such-and- such a problem has been extensively studied for N years, and here is the fastest known method for solving it.” Proponents of factorization-based cryp- tosystems point to the fact that, in some sense, people have been trying to factor numbers since antiquity; but in truth, the modern theory of factoriza- tion requires high-speed computing devices and barely predates the invention of RSA. Serious study of the elliptic curve discrete logarithm problem started in the late 1980s, so modern factorization methods have a 10 to 15 year head start on ECDLP. In Chapter 6 we will describe a public key cryptosystems called NTRU whose security is based on certain hard problems in the theory of lattices. Lattices have been extensively investigated since the 19th century, but again the invention and analysis of modern computational algorithms is much more recent, having been initiated by fundamental work of Lenstra, Lenstra, and Lov´asz in the early 1980s. Lattices appeared as a tool for cryptanalysis during the 1980s and as a means of creating cryptosystems in the 1990s. RSA, the first public key cryptosystem, was patented by its inventors. The issue of patents in cryptography is fraught with controversy. One might argue that the RSA patent, which ran from 1983 to 2000, set back the use of cryptography by requiring users to pay licensing fees. However, it is also true that in order to build a company, an inventor needs investors willing to risk their money, and it is much easier to raise funds if there is an exclusive product to offer. Further, the fact that RSA was originally the “only game 7In 1997, the RSA corporation posted the following quote by RSA co-inventor Ron Rivest on its website: “But the security of cryptosystems based on elliptic curves is not well understood, due in large part to the abstruse nature of elliptic curves. . . . Over time, this may change, but for now trying to get an evaluation of the security of an elliptic-curve cryptosystem is a bit like trying to get an evaluation of some recently discovered Chaldean poetry. Until elliptic curves have been further studied and evaluated, I would advise against fielding any large-scale applications based on them.”
5.6. Lenstra’s elliptic curve factorization algorithm 303 in town” meant that it automatically received extensive scrutiny from the academic community, which helped to validate its security. The invention and eventual commercial implementation of ECC followed a different path. Since neither Koblitz nor Miller applied for a patent, the basic underlying idea of ECC became freely available for all to use. This led Cer- ticom and other companies to apply for patents giving improvements to the basic ECC idea. Some of these improvements were based on significant new research ideas, while others were less innovative and might almost be char- acterized as routine homework problems.8 Unfortunately, the United States Patents and Trademark Office (USPTO) does not have the expertise to effec- tively evaluate the flood of cryptographic patent applications that it receives. The result has been a significant amount of uncertainty in the marketplace as to which versions of ECC are free and which require licenses, even assuming that all of the issued patents can withstand a legal challenge. 5.6 Lenstra’s elliptic curve factorization algorithm Pollard’s p − 1 factorization method, which we discussed in Section 3.5, finds factors of N = pq by searching for a power aL with the property that aL ≡ 1 (mod p) and aL ≡ 1 (mod q). Fermat’s little theorem tells us that this is likely to work if p − 1 divides L and q − 1 does not divide L. So what we do is to take L = n! for some moderate value of n. Then we hope that p − 1 or q − 1, but not both, is a product of small primes, hence divides n!. Clearly Pollard’s method works well for some numbers, but not for all numbers. The determining factor is whether p − 1 or q − 1 is a product of small primes. What is it about the quantity p − 1 that makes it so important for Pollard’s method? The answer lies in Fermat’s little theorem. Intrinsically, p − 1 is important because there are p − 1 elements in F∗ p, so every element α of F∗ p satisfies αp−1 = 1. Now consider that last statement as it relates to the theme of this chapter, which is that the points and the addition law for an elliptic curve E(Fp) are very much analogous to the elements and the multiplication law for F∗ p. Hendrik Lenstra [71] made this analogy precise by devising a factorization algorithm that uses the group law on an elliptic curve E in place of multiplication modulo N . In order to describe Lenstra’s algorithm, we need to work with an elliptic curve modulo N , where the integer N is not prime, so the ring Z/N Z is not a field. However, suppose that we start with an equation 8For example, at the end of Section 5.4.2 we described how to save bandwidth in elliptic ElGamal by sending the x-coordinate and one additional bit to specify the y-coordinate. This idea is called “point compression” and is covered by US Patent 6,141,420.