The State of the Art of

Elliptic Curve Cryptography

Ernst Kani
Department of Mathematics and Statistics
Queen’s University
Kingston, Ontario

1Elliptic Curve Cryptography
Outline1. ECC: Advantages and Disadvantages
2. Discrete Logarithm (DL) Cyptosystems
3. Elliptic Curves (EC)
4. A Small Example
5. Attacks and their consquences
6. ECC System Setup
7. Elliptic Curves: Construction Methods

2

ECC: Advantages/Disadvantages
Advantages:• greater flexibility in choosing cryptographic system• no known subexponential time algorithm for ECDLP⇒ smaller key sizes (with the same security).
Current recommendation (according to A.K. Lenstra,E.R. Verheul): the minimum key size for ECC shouldbe 132 bits vs. 952 bits for RSA.
• As a result: greater speed, less storage ⇒ ECC canbe used in smart cards, cellular phones, pagers etc.

Disadvantages:• Hyperelliptic cryptosystems offer even smaller keysizes.
• ECC is mathematically more subtle than RSA orSDL ⇒ difficult to explain/justify to the client.

Main uses of ECC: key exchange, digital signature,authentication, (limited) message transmission, etc.

3DL - Cryptosystems
Basic Problem: Let G be an abstract (multiplicative) group (= a set with a multiplication operation ·).
Find a computer realization of G such that:
1) The operation “exponentiation” a → b := an canbe implemented as a quick, efficient algorithm;
2) The inverse operation (“discrete logarithm”), i.e.,(DLP) Given a and b ∈ G, find n (“= loga(b)”)
such thatb = an = a| · a{z· · · a},n timesis technically much harder and hence cannot be carried out in a reasonable amount of time.

Classical Examples:1) Let G = F×p = {1, . . . p − 1}, where p is a prime,with multiplication a · b = rem(ab, p).
2) (SDL) Take G = {1, g, g 2, . . . g q−1} ⊂ F×
p , a cyclic
subgroup of order q.
3) More generally, let G ⊂ F×
p , where Fp is any finite
field; here p is a power of a prime.

4A Sample Protocol:
The Diffie-Hellman Key Exchange (1976):
Public information: An element g ∈ F×
p of large
order q.
User A (Alice) picks a random integer a, sends B thenumber (public key) PA = g a.
User B (Bob) picks a random integer b, sends A thenumber (public key) PB = g b.
Then: A and B can both compute and use the common (secret) key SAB = (PA)b = (PB )a = g ab.
The Diffie-Hellman Problem (DHP): compute the secret key SAB from the data g, PA, PB .
The Diffie-Hellman Assumption: a spy (Eve) cannot
solve (DHP) in a reasonable amount of time.
Remarks: 1) (DLP) ⇒ (DHP).
2) “There is strong evidence” (Lenstra/Verheul) thatthe (DHP) is equivalent to the (DLP). In fact: this istrue for many orders q (Maurer/Wolf/Boneh, 1996).

5

Elliptic Curves
Elliptic curves: Let a, b ∈ Fp and consider
G = Ea,b(Fp) := {(x, y) ∈ Fp × Fp : y 2 = x3 + ax + b} ∪ {P∞}The group law: The multiplication in G is given by(x1, y1) ∗ (x2, y2) = (x3, y3)
wherex 3 = λ2 − x 1 − x 2y3 = λ(x1 − x3) − y1).

with λ =if x1 = x2
3x21 + ay2 − y1(or λ =x2 − x12y1).

Notes: 1) We usually write the group law additively, i.e. we write
P + Q in place of P ∗ Q and hence kP in place of P
∗ · · · ∗ P}.
| ∗ P {zk2) The extra point P∞ serves as the identity of the group law:
P∞ + P = P + P∞ = P, for all P ∈ E(Fp).

3) V. Miller and N. Koblitz (independently) first proposed in1986 the use of elliptic curves for cryptography.

Problem: How can we find an elliptic curve E/Fp which is suitable for implementing a DL-cryptosystem?

Questions: 1) How can we estimate/calculate #G?
2) How can we find a point of large order in G?

Theorem (Hasse, 1933): #E(Fp) ≈ p; more precisely,√| p + 1 − #E(Fp) | ≤ 2 p.
|{z}
trE

6

A Small Example
Consider the following elliptic curve E2,1 over F5:
y 2 = x3 + 2x + 1.

E = E2,1 :Then a quick calculation (exhaustive search) shows thatE(F5) = {|{z}P∞ , (0, 1), (1, 3), (3, 3), (3, 2), (1, 2), (0, 4)}.
| {z } | {z } | {z } | {z } | {z } | {z }P0P1P2P3P4P5P6For example, P4 = (3, 2) ∈ E(F5) because

33 + 2 · 3 + 1 = 34 ≡ 4 ≡ 22 (mod 5).
The above points Pi have been numbered in such way that
Pi + Pj = Pi+j (indices mod 7).
Thus, #E(F5) = 7, which satisfies the Hasse bound since√ .
|(5 + 1) − 7| = 1 ≤ 2 5 = 4.47.
Diffie-Hellman Key Exchange:
A chooses the secret key a = 2 and computes her public key
PA = 2P1 = P1 + P1 = P2 = (1, 3).
B chooses the secret key b = 3 and computes his public key
PB = 3P1 = P1 + P1 + P1 = P3 = (3, 3).
Thus, their common (secret key is:
SAB = P6 = (0, 4)

2PB = 2P3 = P6 (as computed by A)
3PA = 3P2 = P6 (as computed by B)

7

Attacks and their Consequences
General DL-Attacks:
SPH - due to Silver, Pohlig, Hellman (1978):the DLP for a group G of order n can be reduced to solving
the DLP for its subgroups of prime order p|n.
Pollard’s ρ and λ (or √Kangaroo) - due to Pollard(1978):each solves DLP in O( n) steps. (Parallizable!)
Consequence: work with a group G of sufficiently large prime
order q = #G.
Elliptic Curve Attacks:
MOV - due to Menezes, Okamoto, Vanstone (1993); cf. also Frey,Rück (1994): if(1)pr ≡ 1 (mod q),then the ECDLP can be reduced to the DLP in Fpr⇒ we can solve the ECDLP by using the (subexponential)
Index Calculus in Fpr .
Anomalous - due to Samaev (1998); Satoh, Araki (1998), Smart(1999): the ECDLP can be solved (using p-adic numbers) for
anomalous curves, i.e. those with #E(Fp) = p (⇔ trE = 1).
Consequence: For ECC, avoid:
1) anomalous curves;
2) primes q which satisfy (1) for small r; i.e. r << k 2/ log2 k,
where k = log2 p.

8Explicit Attacks:
Hardware attack estimate: In 1996, an attack against a 120bit EC sytem was proposed - using a machine running 75 independent Pollard ρ processors. (Estimated cost: $10 million,running time: 32 days.)
Software attack estimate (A.Lenstra, E.Verheul, 1999): Ona 109-bit EC system (p ≈ 2109), the ECDLP should take 18,000years on a current PC (or 1 year on 18,000 PC’s → “Power ofthe Internet”) by using Pollard’s ρ method. (PC = 450MHzPentium II processor).
RSA155 (= 512 bit RSA) was factored in August 1999 using
the NFS (Number Field Sieve). Run Time: 20 years on 1 PC
(64Mb memory) = 1 day on 7500 PC’s.
Note: RSA155 is still used on the Web (e.g. in the Secure
Socket Layer(SSL)), but cannot be considered to be secure.
Consequences: A.K.Lenstra, E.R.Verheul (Sep. 1999) propose
the following minimum key sizes (in bits):
Year RSASDLECqpwo (w)*2000 952 123 952 132 (132)2005 1149 131 1149 139 (147)2025 2174 158 2174 169 (202)2050 4047 193 1447 206 (272)*without (with) cryptoanalytic progress

9ECC Sytem Setup
System Setup: There are several choices to be made:• Selecting a finite field Fp (and a field representation)– e.g. p = prime or p = 2k .
• Selecting an elliptic curve E/Fp (+ a point P of order q)– random curve vs. a special curve etc. (see next page)• Selecting the elliptic curve representation– affine vs. projective coordinates, etc.)• Selecting a protocol (e.g. Diffie-Hellman, ECDSA) for task
Note: Some protocols require additional steps; e.g. ElGamaland others require message embedding m → Pm ∈ E(Fq ).
Selection criteria:• Security: of ECDLP, of protocol.
• Implementation requirements:– speed, storage, power consumption→ optimization of field/EC operations, of protocol.
• Platform dependence: speed and performance of primitives– e.g. on a Pentium PC, the time for multiplication is onlya small multiple of that for addition.
• Standards Compatibility: Public Key Infrastructure, Wassenaar Arrangement (Export).
Remark: S. Vanstone (Field Institute Conference, 1999) emphasizes that all these selection criteria must be considered simultaneously.

10EC Construction Methods
Method 1: Random elliptic curves E/Fp:– first choose a field Fp, then a point P = (x, y) ∈ Fp × Fp,– then choose (by varying the paramater a) an elliptic curve
Ea,b such that P is a point of suitable order q on Ea,b(Fp).
Note: in order to find ord(P ), first calculate #E(Fp) using
the Schoof-Elkies-Atkin (SEA) algorithm.
Method 2: CM elliptic curves E/Q:
– pick a CM elliptic curve E/Q (and a point P ∈ E(Q)),– then look for a prime p such that (E, P ) (mod p) has theright cryptographic properties.
Advantage: there is a “formula” for #E(Fp).
Example: E : y 2 = x3 − n2x is a CM-curve with point P =(Z 2/4, (Y 2 − X 2)Z/8), provided that (X, Y, Z) are the sides
of a right-angled triangle with area n. By Gauss (1777-1855):–if p ≡ 3 (mod 4), then #E(Fp) = p + 1 (do not use for ECC!)–if p ≡ 1 (mod 4), then there is an explicit formula.
Method 3: Koblitz (subfield) curves:– take p = pr0 (p0 small), choose E/Fp0 and view E over Fp.
Advantage: there is a simple formula (Artin, 1926) for #E(Fp)in terms of #E(Fp0 ) (which can be calculated quickly).
Method 4: Arbitrary elliptic curves E/Q (?):– similar to method 2 (formula for #E(Fp) via modular forms?)