CHAPTER 1

Introduction and Overview

Elliptic curves have a rich and beautiful history, having been studied by mathematicians for over a hundred years. They have been used to solve a diverse range of problems. One example is the congruent number problem that asks for a classification of the positive integers occurring as the area of some right-angled triangle, the lengths of whose sides are rational numbers. Another example is proving Fermat’s Last Theorem which states that the equation xn + yn = zn has no nonzero integer solutions for x, y and z when the integer n is greater than 2.

In 1985, Neal Koblitz and Victor Miller independently proposed using elliptic curves to design public-key cryptographic systems. Since then an abundance of research has been published on the security and efficient implementation of elliptic curve cryptography. In the late 1990’s, elliptic curve systems started receiving commercial acceptance when accredited standards organizations specified elliptic curve protocols, and private companies included these protocols in their security products.

The purpose of this chapter is to explain the advantages of public-key cryptography over traditional symmetric-key cryptography, and, in particular, to expound the virtues of elliptic curve cryptography. The exposition is at an introductory level. We provide more detailed treatments of the security and efficient implementation of elliptic curve systems in subsequent chapters.

We begin in §1.1 with a statement of the fundamental goals of cryptography and a description of the essential differences between symmetric-key cryptography and public-key cryptography. In §1.2, we review the RSA, discrete logarithm, and elliptic curve families of public-key systems. These systems are compared in §1.3 in which we explain the potential benefits offered by elliptic curve cryptography. A roadmap for the remainder of this book is provided in §1.4. Finally, §1.5 contains references to the cryptographic literature.

2 1. Introduction and Overview

1.1Cryptography basics

Cryptography is about the design and analysis of mathematical techniques that enable secure communications in the presence of malicious adversaries.

Basic communications model

In Figure 1.1, entities A (Alice) and B (Bob) are communicating over an unsecured channel. We assume that all communications take place in the presence of an adversary E (Eve) whose objective is to defeat any security services being provided to A and B.

unsecured channel

A

B

E

Figure 1.1. Basic communications model.

For example, A and B could be two people communicating over a cellular telephone network, and E is attempting to eavesdrop on their conversation. Or, A could be the

˜

web browser of an individual A who is in the process of purchasing a product from

˜

an online store B represented by its web site B. In this scenario, the communications channel is the Internet. An adversary E could attempt to read the traffic from A to B

˜ ˜

thus learning A’s credit card information, or could attempt to impersonate either A or

˜

B in the transaction. As a third example, consider the situation where A is sending an email message to B over the Internet. An adversary E could attempt to read the message, modify selected portions, or impersonate A by sending her own messages to B. Finally, consider the scenario where A is a smart card that is in the process

˜

of authenticating its holder A to the mainframe computer B at the headquarters of a

˜

bank. Here, E could attempt to monitor the communications in order to obtain A’s

˜

account information, or could try to impersonate A in order to withdraw funds from

˜

A’s account. It should be evident from these examples that a communicating entity is not necessarily a human, but could be a computer, smart card, or software module acting on behalf of an individual or an organization such as a store or a bank.

Security goals

Careful examination of the scenarios outlined above reveals the following fundamental objectives of secure communications:

1.Confidentiality: keeping data secret from all but those authorized to see it—messages sent by A to B should not be readable by E.

1.1. Cryptography basics

3

2.Data integrity: ensuring that data has not been altered by unauthorized means— B should be able to detect when data sent by A has been modified by E.

3.Data origin authentication: corroborating the source of data—B should be able to verify that data purportedly sent by A indeed originated with A.

4.Entity authentication: corroborating the identity of an entity—B should be convinced of the identity of the other communicating entity.

5.Non-repudiation: preventing an entity from denying previous commitments or actions—when B receives a message purportedly from A, not only is B convinced that the message originated with A, but B can convince a neutral third party of this; thus A cannot deny having sent the message to B.

Some applications may have other security objectives such as anonymity of the communicating entities or access control (the restriction of access to resources).

Adversarial model

In order to model realistic threats faced by A and B, we generally assume that the adversary E has considerable capabilities. In addition to being able to read all data transmitted over the channel, E can modify transmitted data and inject her own data. Moreover, E has significant computational resources at her disposal. Finally, complete descriptions of the communications protocols and any cryptographic mechanisms deployed (except for secret keying information) are known to E. The challenge to cryptographers is to design mechanisms to secure the communications in the face of such powerful adversaries.

Symmetric-key cryptography

Cryptographic systems can be broadly divided into two kinds. In symmetric-key schemes, depicted in Figure 1.2(a), the communicating entities first agree upon keying material that is both secret and authentic. Subsequently, they may use a symmetric-key encryption scheme such as the Data Encryption Standard (DES), RC4, or the Advanced Encryption Standard (AES) to achieve confidentiality. They may also use a message authentication code (MAC) algorithm such as HMAC to achieve data integrity and data origin authentication.

For example, if confidentiality were desired and the secret key shared by A and B were k, then A would encrypt a plaintext message m using an encryption function ENC and the key k and transmit the resulting ciphertext c = ENCk (m) to B. On receiving c, B would use the decryption function DEC and the same key k to recover m = DECk (c). If data integrity and data origin authentication were desired, then A and B would first agree upon a secret key k, after which A would compute the authentication tag t = MACk (m) of a plaintext message m using a MAC algorithm and the key k. A would then send m and t to B. On receiving m and t, B would use the MAC algorithm and the same key k to recompute the tag t = MACk (m) of m and accept the message as having originated from A if t = t .

4

1. Introduction and Overview

secret and authenticated channel

authenticated channel

unsecured channel

unsecured channel

A

B

A

B

E

E

(a) Symmetric-key cryptography

(b) Public-key cryptography

Figure 1.2. Symmetric-key versus public-key cryptography.

Key distribution and management The major advantage of symmetric-key cryptography is high efficiency; however, there are significant drawbacks to these systems. One primary drawback is the so-called key distribution problem—the requirement for a channel that is both secret and authenticated for the distribution of keying material. In some applications, this distribution may be conveniently done by using a physically secure channel such as a trusted courier. Another way is to use the services of an on-line trusted third-party who initially establishes secret keys with all the entities in a network and subsequently uses these keys to securely distribute keying material to communicating entities when required.1 Solutions such as these may be well-suited to environments where there is an accepted and trusted central authority, but are clearly impractical in applications such as email over the Internet.

A second drawback is the key management problem—in a network of N entities, each entity may have to maintain different keying material with each of the other N − 1 entities. This problem can be alleviated by using the services of an on-line trusted thirdparty that distributes keying material as required, thereby reducing the need for entities to securely store multiple keys. Again, however, such solutions are not practical in some scenarios. Finally, since keying material is shared between two (or more) entities, symmetric-key techniques cannot be used to devise elegant digital signature schemes that provide non-repudiation services. This is because it is impossible to distinguish between the actions taken by the different holders of a secret key.2

Public-key cryptography

The notion of public-key cryptography, depicted in Figure 1.2(b), was introduced in 1975 by Diffie, Hellman and Merkle to address the aforementioned shortcomings

1This approach of using a centralized third-party to distribute keys for symmetric-key algorithms to parties as they are needed is used by the Kerberos network authentication protocol for client/server applications.

2Digital signatures schemes can be designed using symmetric-key techniques; however, these schemes are generally impractical as they require the use of an on-line trusted third party or new keying material for each signature.

1.1. Cryptography basics

5

of symmetric-key cryptography. In contrast to symmetric-key schemes, public-key schemes require only that the communicating entities exchange keying material that is authentic (but not secret). Each entity selects a single key pair (e, d) consisting of a public key e, and a related private key d (that the entity keeps secret). The keys have the property that it is computationally infeasible to determine the private key solely from knowledge of the public key.

Confidentiality If entity A wishes to send entity B a confidential message m, she obtains an authentic copy of B’s public key eB , and uses the encryption function ENC of a public-key encryption scheme to compute the ciphertext c = ENCeB (m). A then transmits c to B, who uses the decryption function DEC and his private key dB to recover the plaintext: m = DECdB (c). The presumption is that an adversary with knowledge only of eB (but not of dB ) cannot decrypt c. Observe that there are no secrecy requirements on eB . It is essential only that A obtain an authentic copy of eB —otherwise A would encrypt m using the public key eE of some entity E purporting to be B, and m would be recoverable by E.

Non-repudiation Digital signature schemes can be devised for data origin authentication and data integrity, and to facilitate the provision of non-repudiation services. An entity A would use the signature generation algorithm SIGN of a digital signature scheme and her private key dA to compute the signature of a message: s = SIGNdA (m). Upon receiving m and s, an entity B who has an authentic copy of A’s public key eA uses a signature verification algorithm to confirm that s was indeed generated from m and dA. Since dA is presumably known only by A, B is assured that the message did indeed originate from A. Moreover, since verification requires only the non-secret quantities m and eA, the signature s for m can also be verified by a third party who could settle disputes if A denies having signed message m. Unlike handwritten signatures, A’s signature s depends on the message m being signed, preventing a forger from simply appending s to a different message m and claiming that A signed m . Even though there are no secrecy requirements on the public key eA, it is essential that verifiers should use an authentic copy of eA when verifying signatures purportedly generated by A.

In this way, public-key cryptography provides elegant solutions to the three problems with symmetric-key cryptography, namely key distribution, key management, and the provision of non-repudiation. It must be pointed out that, although the requirement for a secret channel for distributing keying material has been eliminated, implementing a public-key infrastructure (PKI) for distributing and managing public keys can be a formidable challenge in practice. Also, public-key operations are usually significantly slower than their symmetric-key counterparts. Hence, hybrid systems that benefit from the efficiency of symmetric-key algorithms and the functionality of public-key algorithms are often used.

The next section introduces three families of public-key cryptographic systems.

6 1. Introduction and Overview

1.2Public-key cryptography

In a public-key cryptographic scheme, a key pair is selected so that the problem of deriving the private key from the corresponding public key is equivalent to solving a computational problem that is believed to be intractable. Number-theoretic problems whose intractability form the basis for the security of commonly used public-key schemes are:

1.The integer factorization problem, whose hardness is essential for the security of RSA public-key encryption and signature schemes.

2.The discrete logarithm problem, whose hardness is essential for the security of the ElGamal public-key encryption and signature schemes and their variants such as the Digital Signature Algorithm (DSA).

3.The elliptic curve discrete logarithm problem, whose hardness is essential for the security of all elliptic curve cryptographic schemes.

In this section, we review the basic RSA, ElGamal, and elliptic curve public-key encryption and signature schemes. We emphasize that the schemes presented in this section are the basic “textbook” versions, and enhancements to the schemes are required (such as padding plaintext messages with random strings prior to encryption) before they can be considered to offer adequate protection against real attacks. Nevertheless, the basic schemes illustrate the main ideas behind the RSA, discrete logarithm, and elliptic curve families of public-key algorithms. Enhanced versions of the basic elliptic curve schemes are presented in Chapter 4.

1.2.1RSA systems

RSA, named after its inventors Rivest, Shamir and Adleman, was proposed in 1977 shortly after the discovery of public-key cryptography.

RSA key generation

An RSA key pair can be generated using Algorithm 1.1. The public key consists of a pair of integers (n, e) where the RSA modulus n is a product of two randomly generated (and secret) primes p and q of the same bitlength. The encryption exponent e is an integer satisfying 1 < e < φ and gcd(e, φ) = 1 where φ = ( p − 1)(q − 1). The private key d, also called the decryption exponent, is the integer satisfying 1 < d < φ and ed ≡ 1 (mod φ). It has been proven that the problem of determining the private key d from the public key (n, e) is computationally equivalent to the problem of determining the factors p and q of n; the latter is the integer factorization problem (IFP).

1.2. Public-key cryptography

7

Algorithm 1.1 RSA key pair generation

INPUT: Security parameter l.

OUTPUT: RSA public key (n, e) and private key d.

1.Randomly select two primes p and q of the same bitlength l/2.

2.Compute n = pq and φ = ( p − 1)(q − 1).

3.Select an arbitrary integer e with 1 < e < φ and gcd(e, φ) = 1.

4.Compute the integer d satisfying 1 < d < φ and ed ≡ 1 (mod φ).

5.Return(n, e, d).

RSA encryption scheme

RSA encryption and signature schemes use the fact that

med ≡ m (mod n)

(1.1)

for all integers m. The encryption and decryption procedures for the (basic) RSA public-key encryption scheme are presented as Algorithms 1.2 and 1.3. Decryption works because cd ≡ (me)d ≡ m (mod n), as derived from expression (1.1). The security relies on the difficulty of computing the plaintext m from the ciphertext c = me mod n and the public parameters n and e. This is the problem of finding eth roots modulo n and is assumed (but has not been proven) to be as difficult as the integer factorization problem.

Algorithm 1.2 Basic RSA encryption

INPUT: RSA public key (n, e), plaintext m [0, n − 1].

OUTPUT: Ciphertext c.

1.Compute c = me mod n.

2.Return(c).

Algorithm 1.3 Basic RSA decryption

INPUT: RSA public key (n, e), RSA private key d, ciphertext c.

OUTPUT: Plaintext m.

1.Compute m = cd mod n.

2.Return(m).

RSA signature scheme

The RSA signing and verifying procedures are shown in Algorithms 1.4 and 1.5. The signer of a message m first computes its message digest h = H (m) using a cryptographic hash function H , where h serves as a short fingerprint of m. Then, the signer

8 1. Introduction and Overview

uses his private key d to compute the eth root s of h modulo n: s = hd mod n. Note that se ≡ h (mod n) from expression (1.1). The signer transmits the message m and its signature s to a verifying party. This party then recomputes the message digest h = H (m), recovers a message digest h = se mod n from s, and accepts the signature as being valid for m provided that h = h . The security relies on the inability of a forger (who does not know the private key d) to compute eth roots modulo n.

Algorithm 1.4 Basic RSA signature generation

INPUT: RSA public key (n, e), RSA private key d, message m.

OUTPUT: Signature s.

1.Compute h = H (m) where H is a hash function.

2.Compute s = hd mod n.

3.Return(s).

Algorithm 1.5 Basic RSA signature verification

INPUT: RSA public key (n, e), message m, signature s.

OUTPUT: Acceptance or rejection of the signature.

1.Compute h = H (m).

2.Compute h = se mod n.

3.If h = h then return(“Accept the signature”); Else return(“Reject the signature”).

The computationally expensive step in any RSA operation is the modular exponentiation, e.g., computing me mod n in encryption and cd mod n in decryption. In order to increase the efficiency of encryption and signature verification, one can select a small encryption exponent e; in practice, e = 3 or e = 216 + 1 is commonly chosen. The decryption exponent d is of the same bitlength as n. Thus, RSA encryption and signature verification with small exponent e are significantly faster than RSA decryption and signature generation.

1.2.2Discrete logarithm systems

The first discrete logarithm (DL) system was the key agreement protocol proposed by Diffie and Hellman in 1976. In 1984, ElGamal described DL public-key encryption and signature schemes. Since then, many variants of these schemes have been proposed. Here we present the basic ElGamal public-key encryption scheme and the Digital Signature Algorithm (DSA).

1.2. Public-key cryptography

9

DL key generation

In discrete logarithm systems, a key pair is associated with a set of public domain parameters ( p, q, g). Here, p is a prime, q is a prime divisor of p − 1, and g [1, p − 1] has order q (i.e., t = q is the smallest positive integer satisfying gt ≡ 1 (mod p)). A private key is an integer x that is selected uniformly at random from the interval [1, q − 1] (this operation is denoted x R [1, q − 1]), and the corresponding public key is y = gx mod p. The problem of determining x given domain parameters ( p, q, g) and y is the discrete logarithm problem (DLP). We summarize the DL domain parameter generation and key pair generation procedures in Algorithms 1.6 and 1.7, respectively.

Algorithm 1.6 DL domain parameter generation

INPUT: Security parameters l, t.

OUTPUT: DL domain parameters ( p, q, g).

1. Select a t-bit prime q and an l-bit prime p such that q divides p − 1.

2.Select an element g of order q:

2.1Select arbitrary h [1, p − 1] and compute g = h( p−1)/q mod p.

2.2If g = 1 then go to step 2.1.

3.Return( p, q, g).

Algorithm 1.7 DL key pair generation

INPUT: DL domain parameters ( p, q, g).

OUTPUT: Public key y and private key x.

1.Select x R [1, q − 1].

2.Compute y = gx mod p.

3.Return(y, x).

DL encryption scheme

We present the encryption and decryption procedures for the (basic) ElGamal publickey encryption scheme as Algorithms 1.8 and 1.9, respectively. If y is the intended recipient’s public key, then a plaintext m is encrypted by multiplying it by yk mod p where k is randomly selected by the sender. The sender transmits this product c2 = myk mod p and also c1 = gk mod p to the recipient who uses her private key to compute

c1x ≡ gkx ≡ yk (mod p)

and divides c2 by this quantity to recover m. An eavesdropper who wishes to recover m needs to calculate yk mod p. This task of computing yk mod p from the domain parameters ( p, q, g), y, and c1 = gk mod p is called the Diffie-Hellman problem (DHP).

10 1. Introduction and Overview

The DHP is assumed (and has been proven in some cases) to be as difficult as the discrete logarithm problem.

Algorithm 1.8 Basic ElGamal encryption

INPUT: DL domain parameters ( p, q, g), public key y, plaintext m [0, p − 1]. OUTPUT: Ciphertext (c1, c2).

1.Select k R [1, q − 1].

2.Compute c1 = gk mod p.

3.Compute c2 = m · yk mod p.

4.Return(c1, c2).

Algorithm 1.9 Basic ElGamal decryption

INPUT: DL domain parameters ( p, q, g), private key x, ciphertext (c1, c2). OUTPUT: Plaintext m.

1.Compute m = c2 · c1−x mod p.

2.Return(m).

DL signature scheme

The Digital Signature Algorithm (DSA) was proposed in 1991 by the U.S. National Institute of Standards and Technology (NIST) and was specified in a U.S. Government Federal Information Processing Standard (FIPS 186) called the Digital Signature Standard (DSS). We summarize the signing and verifying procedures in Algorithms 1.10 and 1.11, respectively.

An entity A with private key x signs a message by selecting a random integer k from the interval [1, q − 1], and computing T = gk mod p, r = T mod q and

s = k−1(h + xr ) mod q

(1.2)

where h = H (m) is the message digest. A’s signature on m is the pair (r, s). To verify the signature, an entity must check that (r, s) satisfies equation (1.2). Since the verifier knows neither A’s private key x nor k, this equation cannot be directly verified. Note, however, that equation (1.2) is equivalent to

k ≡ s−1(h + xr )	(mod q).	(1.3)
Raising g to both sides of (1.3) yields the equivalent congruence
T ≡ ghs−1 yrs−1	(mod p).
The verifier can therefore compute T and then check that r = T mod q.