L14 Elliptic Curve Cryptosystems

Cyclic groups on elliptic curves. Elliptic Curve Diffie-Hellman. Implementation issues such as Double and Add, and point compression.

What is #E (the order of an elliptic curve group) and why does it matter?

#E is the number of points on the curve (including the point at infinity).

A large #E is essential for security - it determines the size of the key space and prevents attacks on ECDLP

How does Elliptic Curve Diffie-Hellman (ECDH) work?

• Both parties (Alice & Bob) agree on a public curve E, order #E, and generator G

• Alice picks private scalar a sends A = a·G

• Bob picks private scalar b, sends B = b·G.

• Both compute the shared secret

• Alice gets a·B = abG

• Bob gets b·A = abG

• An attacker seeing A and B cannot recover abG without solving ECDLP

Why is ECC preferred over RSA for equivalent security?

ECC achieves the same security level with much shorter keys.

For example, a 256-bit ECC key offers similar security to a 3072-bit RSA key → meaning smaller keys, faster operations, and less bandwidth

Why should you not generate your own elliptic curve for cryptography?

Curve parameters heavily affect both security and efficiency.

Poorly chosen curves can be vulnerable to various attacks on ECDLP.

Standard, vetted curves (e.g., P-256, Cruve25519) should always be used instead

What is projective coordinates and why is it used in EC implementations?

Instead of using (x, y), points are represented as (x, y, z).

This avoids the need for a modular inverse during point addition (which is expensive), making implementations faster