The majority of public-key crypto (RSA, D-H) use either integer or polynomial arithmetic with very large numbers/polynomials. It imposes a significant load in storing and processing keys and messages. An alternative is to use elliptic curves which offers same security with smaller bit sizes. Its newer, but not as well analysed.

- an elliptic curve is defined by an equation in two variables x & y, with coefficients
- consider a cubic elliptic curve of form
- y2 = x3 + ax + b
- where x,y,a,b are all real numbers
- also define zero point O

- consider set of points E(a,b) that satisfy
- have addition operation for elliptic curve
- Elliptic curve cryptography uses curves whose variables & coefficients are finite
- have two families commonly used:
- prime curves Ep(a,b) defined over Zp
- use integers modulo a prime
- best in software

- binary curves E2m(a,b) defined over GF(2n)
- use polynomials with binary coefficients
- best in hardware

- prime curves Ep(a,b) defined over Zp
- ECC addition is analog of modulo multiply
- ECC repeated addition is analog of modulo exponentiation
- need “hard” problem equiv to discrete log
- Q=kP, where Q,P belong to a prime curve
- is “easy” to compute Q given k,P
- but “hard” to find k given Q,P
- known as the elliptic curve logarithm problem

**ECC Diffie-Hellman:**

It can do key exchange analogous to D-H. Users select a suitable curve Eq(a,b) and select base point G=(x1,y1) with large order n s.t. nG=O. A & B select private keys nA<n, nB<n. It compute public keys: PA=nAG, PB=nBG

- compute shared key: K=nAPB, K=nBPA
- same since K=nAnBG

- attacker would need to find k, hard

**ECC Encryption/Decryption:**

There several alternatives, which will consider simplest. It must first encode any message M as a point on the elliptic curve Pm then select suitable curve & point G as in D-H. Each user chooses private key nA<n and computes public key PA=nAG to encrypt Pm : Cm={kG, Pm+kPb}, k random, decrypt Cm compute:

Pm+kPb–nB(kG) = Pm+k(nBG)–nB(kG) = Pm

**ECC Security:**

- Relies on elliptic curve logarithm problem
- fastest method is “Pollard rho method”
- compared to factoring, can use much smaller key sizes than with RSA etc
- for equivalent key lengths computations are roughly equivalent
- hence for similar security ECC offers significant computational advantages