4.2. Domain parameters

179

4.2.3Determining the number of points on an elliptic curve

As discussed in the introduction to §4.2, the order #E(Fq ) of an elliptic curve E used in a cryptographic protocol should satisfy some constraints imposed by security considerations. Thus, determining the number of points on an elliptic curve is an important ingredient of domain parameter generation. A na¨ıve algorithm for point counting is to find, for each x Fq , the number of solutions y Fq to the Weierstrass equation for E. This method is clearly infeasible for field sizes of cryptographic interest. In practice, one of the following three techniques is employed for selecting an elliptic curve of known order.

Subfield curves Let q = pld , where d > 1. One selects an elliptic curve E defined over F pl , counts the number of points in E(F pl ) using a na¨ıve method, and then easily determines #E(Fq ) using Theorem 3.11. The group used for the cryptographic application is E(Fq ). Since the elliptic curve E is defined over a proper subfield F pl of Fq , it is called a subfield curve. For example, Koblitz curves studied in §3.4 are subfield curves with p = 2 and l = 1. Since #E(F plc ) divides #E(Fq ) for all divisors c of d and an elliptic curve of prime or almost-prime order is desirable, l should be small (preferably l = 1) and d should be prime.

The complex-multiplication (CM) method In this method, one first selects an order

N that meets the required security constraints, and then constructs an elliptic curve with that order. For elliptic curves over prime fields, the CM method is also called the AtkinMorain method; for binary fields it is called the Lay-Zimmer method. The CM method

is very efficient provided that the finite field order q and the elliptic curve order N =

8

q + 1 − t are selected so that the complex multiplication field Q( t2 − 4q) has small class number. Cryptographically suitable curves over 160-bit fields can be generated in one minute on a workstation. In particular, the CM method is much faster than the best algorithms known for counting the points on randomly selected elliptic curves over prime fields and OEFs. For elliptic curves over binary fields, the CM method has been superseded by faster point counting algorithms (see below).

Since the ECDLP is not known to be any easier for elliptic curves having small class number, elliptic curves generated using the CM method appear to offer the same level of security as those generated randomly.

Point counting In 1985, Schoof presented the first polynomial-time algorithm for computing #E(Fq ) for an arbitrary elliptic curve E. The algorithm computes

#E(Fq ) mod l for small prime numbers l, and then determines #E(Fq ) using the Chinese Remainder Theorem. It is inefficient in practice for values of q of practical interest, but was subsequently improved by several people including Atkin and Elkies resulting in the so-called Schoof-Elkies-Atkin (SEA) algorithm. The SEA algorithm, which is the best algorithm known for counting the points on arbitrary elliptic curves over prime fields or OEFs, takes a few minutes for values of q of practical interest. Since it can

180 4. Cryptographic Protocols

very quickly determine the number of points modulo small primes l, it can be used in an early-abort strategy to quickly eliminate candidate curves whose orders are divisible by a small prime number.

In 1999, Satoh proposed a fundamentally new method for counting the number of points over finite fields of small characteristic. Variants of Satoh’s method, including the Satoh-Skjernaa-Taguchi (SST) and the Arithmetic Geometric Mean (AGM) algorithms, are extremely fast for the binary field case and can find cryptographically suitable elliptic curves over F2163 in just a few seconds on a workstation.

4.3Key pairs

An elliptic curve key pair is associated with a particular set of domain parameters D = (q, FR, S, a, b, P, n, h). The public key is a randomly selected point Q in the group P generated by P. The corresponding private key is d = logP Q. The entity A generating the key pair must have the assurance that the domain parameters are valid (see §4.2). The association between domain parameters and a public key must be verifiable by all entities who may subsequently use A’s public key. In practice, this association can be achieved by cryptographic means (e.g., a certification authority generates a certificate attesting to this association) or by context (e.g., all entities use the same domain parameters).

Algorithm 4.24 Key pair generation

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h).

OUTPUT: Public key Q, private key d.

1.Select d R [1, n − 1].

2.Compute Q = d P.

3.Return(Q, d).

Observe that the problem of computing a private key d from the public key Q is precisely the elliptic curve discrete logarithm problem. Hence it is crucial that the domain parameters D be selected so that the ECDLP is intractable. Furthermore, it is important that the numbers d generated be “random” in the sense that the probability of any particular value being selected must be sufficiently small to preclude an adversary from gaining advantage through optimizing a search strategy based on such probability.

Public key validation

The purpose of public key validation is to verify that a public key possesses certain arithmetic properties. Successful execution demonstrates that an associated private key logically exists, although it does not demonstrate that someone has actually computed the private key nor that the claimed owner actually possesses it. Public key validation is

4.3. Key pairs

181

especially important in Diffie-Hellman-based key establishment protocols where an entity A derives a shared secret k by combining her private key with a public key received from another entity B, and subsequently uses k in some symmetric-key protocol (e.g., encryption or message authentication). A dishonest B might select an invalid public key in such a way that the use of k reveals information about A’s private key.

Algorithm 4.25 Public key validation

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h), public key Q. OUTPUT: Acceptance or rejection of the validity of Q.

1.Verify that Q = ∞.

2.Verify that xQ and yQ are properly represented elements of Fq (e.g., integers in

the interval	[	0, q	− ]	m	is a prime field, and bit strings of length m bits if Fq
			1	if Fq
is a binary field of order 2					).

3.Verify that Q satisfies the elliptic curve equation defined by a and b.

4.Verify that n Q = ∞.

5.If any verification fails then return(“Invalid”); else return(“Valid”).

There may be much faster methods for verifying that n Q = ∞ than performing an expensive point multiplication n Q. For example, if h = 1 (which is usually the case for elliptic curves over prime fields that are used in practice), then the checks in steps 1, 2 and 3 of Algorithm 4.25 imply that n Q = ∞. In some protocols the check that n Q = ∞ may be omitted and either embedded in the protocol computations or replaced by the check that h Q = ∞. The latter check guarantees that Q is not in a small subgroup of E(Fq ) of order dividing h.

Algorithm 4.26 Embedded public key validation

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h), public key Q. OUTPUT: Acceptance or rejection of the (partial) validity of Q.

1.Verify that Q = ∞.

2.Verify that xQ and yQ are properly represented elements of Fq (e.g., integers in

the interval	[	0, q	− ]	m	is a prime field, and bit strings of length m bits if Fq
			1	if Fq
is a binary field of order 2					).

3.Verify that Q lies on the elliptic curve defined by a and b.

4.If any verification fails then return(“Invalid”); else return(“Valid”).

Small subgroup attacks

We illustrate the importance of the checks in public key validation by describing a small subgroup attack on a cryptographic protocol that is effective if some checks are not performed. Suppose that an entity A’s key pair (Q, d) is associated with domain parameters D = (q, FR, S, a, b, P, n, h). In the one-pass elliptic curve Diffie-Hellman

182 4. Cryptographic Protocols

(ECDH) protocol, a second entity B who has authentic copies of D and Q selects r R [1, n − 1] and sends R = r P to A. A then computes the point K = d R, while B computes the same point K = r Q. Both A and B derive a shared secret key k = KDF(K ), where KDF is some key derivation function. Note that this key establishment protocol only provides unilateral authentication (of A to B), which may be desirable in some applications such as the widely deployed SSL protocol where the server is authenticated to the client but not conversely. We suppose that A and B subsequently use the key k to authenticate messages for each other using a message authentication code algorithm MAC.

Suppose now that A omits the check that n Q = ∞ in public key validation (step 4 in Algorithm 4.25). Let l be a prime divisor of the cofactor h. In the small subgroup attack, B sends to A a point R of order l (instead of a point in the group P of order n). A computes K = d R and k = KDF(K ). Since R has order l, K also has order l (unless d ≡ 0 (mod l) in which case K = ∞). Thus K = dl R where dl = d mod l. Now, when A sends to B a message m and its authentication tag t = MACk (m), B can repeatedly

select l [0, l − 1] until t = MACk (m) where k = KDF(K ) and K = l R—then dl = l with high probability. The expected number of trials before B succeeds is l/2.

B can repeat the attack with different points R of pairwise relatively prime orders l1, l2, . . . , ls , and combine the results using the Chinese Remainder Theorem to obtain d mod l1l2 · · ·ls . If h is relatively large, then B can obtain significant information about A’s private key d, and can perhaps then deduce all of d by exhaustive search.

In practice, h is usually small (e.g., h = 1, 2 or 4) in which case the small subgroup attack described above can only determine a very small number of bits of d. We next describe an attack that extends the small subgroup attack to elliptic curves different from the one specified in the domain parameters.

Invalid-curve attacks

The main observation in invalid-curve attacks is that the usual formulae for adding points on an elliptic curve E defined over Fq do not involve the coefficient b (see §3.1.2). Thus, if E is any elliptic curve defined over Fq whose reduced Weierstrass equation differs from E’s only in the coefficient b, then the addition laws for E and E are the same. Such an elliptic curve E is called an invalid curve relative to E.

Suppose now that A does not perform public key validation on points it receives in the one-pass ECDH protocol. The attacker B selects an invalid curve E such that E (Fq ) contains a point R of small order l, and sends R to A. A computes K = d R and k = KDF(R). As with the small subgroup attack, when A sends B a message m and its tag t = MACk (m), B can determine dl = d mod l. By repeating the attack with points R (on perhaps different invalid curves) of relatively prime orders, B can eventually recover d.

The simplest way to prevent the invalid-curve attacks is to check that a received point does indeed lie on the legitimate elliptic curve.