What Is an Elliptic Curve?
Forget "ellipse" — an elliptic curve has nothing to do with ellipses. It's simply the set of points (x, y) that satisfy a specific cubic equation:
That last condition just guarantees the curve has no repeated roots — no sharp cusps or self-intersections. Without it the curve would be "singular" and useless for cryptography, because the point-addition rule below would break down at the singular point.
Why cryptographers like this shape
Elliptic curves used in crypto are actually computed over a finite field (integers mod a prime p), not over real numbers — so the "smooth curve" picture is really just a scatter of discrete points. The geometric picture (lines, tangents) is only a visual aid for understanding the algebraic rule.
Properties of Elliptic Curves
Two structural facts about the curve make the whole cryptosystem work:
Symmetric about the x-axis
For every point (x, y) on the curve, the point (x, −y) is also on the curve. This symmetry is exactly what defines the "inverse" of a point in the group (see Section 04).
A line meets the curve at exactly 3 points
Any non-vertical straight line drawn through the curve intersects it at exactly three points (counting the point at infinity and tangency/multiplicity). This is the geometric engine behind point addition.
Trapdoor function
Given a secret "trapdoor" value t, certain operations become easy to compute forward but practically impossible to reverse without knowing t. ECC's trapdoor is point multiplication: computing kP (k copies of P added together) is fast, but recovering k from kP and P is (believed to be) extremely hard. This asymmetry — easy forward, hard backward — is the entire basis of public-key cryptography.
Groups & Group Properties
A group is a set G with a binary operation ("+") that satisfies four rules. Add a fifth rule and it becomes an abelian group (commutative group).
| Property | Rule | Meaning |
|---|---|---|
| Closure | a, b ∈ G ⟹ a+b ∈ G | Adding two group members always gives another group member — you never "fall out" of the set. |
| Associativity | (a+b)+c = a+(b+c) | Grouping doesn't matter when adding three or more elements. |
| Identity | ∃ 0 : a+0 = 0+a = a | There's a neutral element that changes nothing when added. |
| Inverse | ∀a ∃b : a+b = 0 | Every element has a "partner" that cancels it out back to identity. |
| Commutativity 5th rule | a+b = b+a | Order doesn't matter → makes it an abelian group. |
Mnemonic — Group Properties
"CAIIC" → wait, easier: CAII + Commute = Closure, Associativity, Identity, Inverse are the 4 group rules — think of your group of friends "CAII" who always show up (closure), don't care what order you meet them (associativity), have one leader who changes nothing (identity), and everyone has a rival who cancels them out (inverse). Add "+ Commute" (everyone can swap seats, a+b=b+a) and CAII becomes an abelian group.
Groups Over Elliptic Curves — Point Addition
We can define an abelian group directly on the points of an elliptic curve:
Draw a straight line through P and Q. Because a line hits the curve at exactly 3 points (Section 02), it crosses the curve at a third point, call it −R. Reflecting −R across the x-axis gives R, the actual sum P+Q. So in practice: P + Q = R, where R is the reflection of the line's third intersection point.
Point doubling (P + P = 2P) is the special case where the "line through P and Q" becomes the tangent line at P, since P and Q have merged into the same point.
Mnemonic — Point Addition Recipe
"Line it, Land it, Flip it" — draw a LINE through the two points you're adding, find where it LANDs a third time on the curve, then FLIP that point over the x-axis to get your answer. Three steps, three words, done.
Finite Fields (Fp)
Real ECC doesn't run on the real-number plane — it runs on a finite field: a set with a finite number of elements. The simplest example is the integers modulo a prime p, written Z/p, GF(p), or Fp.
Two operations
Fields define addition (+) and multiplication (·). Both are closed, associative, and commutative. Each has a unique identity element (0 for +, 1 for ·) and every element has a unique inverse.
Distributive law
Multiplication distributes over addition: x·(y+z) = x·y + x·z — exactly like ordinary arithmetic, just "wrapped around" modulo p.
Elliptic curves used for real cryptography sit over Fp (p > 3 prime) or F2m (binary/characteristic-2 fields). All the x, y coordinates and the constants a, b are computed mod p — every "point on the curve" is really just a pair of remainders.
Point Multiplication, Order & Base Points
Curve: y² ≡ x³ + 2x + 3 (mod 97). Take P = (3, 6). Now compute the multiples of P: P, 2P, 3P, 4P, 5P, … Because everything is mod 97 (a finite field), this sequence cannot grow forever — eventually it must repeat, cycling back around to the point at infinity O. This is called cyclic behavior.
Lagrange-style rule
The order of any subgroup always divides the order of the parent group. If the whole elliptic curve has N points and a subgroup has n points, then n | N (n is a divisor of N).
Algorithm — Finding a Base Point
Calculate N
Find the order N of the whole elliptic curve (total number of points on it, including O).
Choose subgroup order n
Pick n such that it is prime and divides N. (The algorithm only works correctly if n is prime.)
Compute the cofactor
h = N / n.
Pick a random point P
Any point on the curve.
Compute G = hP
If G = O, go back to step 4 and try a different P.
Done
Otherwise G is a generator of a subgroup of order n with cofactor h. G is your base point.
Mnemonic — Finding the Base Point
"Never Choose Coffee, Pick Good ones" → N: find order N → Choose prime n dividing N → Cofactor h=N/n → Pick random point P → Generator = hP (retry if O). "Never Choose Coffee, Pick Good ones" — sip your way through all 5 steps in order.
ECC as a Cryptosystem — The Discrete Log Problem
ECC systems were first proposed independently in 1985 by Neal Koblitz and Victor Miller. Both built on the same intuition as classic Diffie-Hellman, but swapped "exponentiation mod p" for "point multiplication on a curve."
Alice and Bob pick secret x, y from F={1,…,p−1}. They exchange gx mod p and gy mod p, then each computes k = gxy mod p. Eve must recover k from gx, gy without knowing x, y — the Discrete Logarithm Problem.
Same idea, but the "exponentiation" gx is replaced by "point multiplication" xP. Given Q = kP and P, finding k is the Elliptic Curve Discrete Logarithm Problem — believed to be harder than the classic DLP for equivalent key sizes.
ECC is mostly used as an extension/replacement for the underlying math of existing cryptosystems: Elliptic Curve Diffie-Hellman (ECDH) key exchange and the Elliptic Curve Digital Signature Algorithm (ECDSA).
The Generic ECC Procedure
Every public-key cryptosystem has one underlying "hard to reverse" math operation: RSA uses exponentiation; ECC uses point multiplication (repeated point addition).
Step 1 — Public parameters (agreed by everyone)
- The elliptic curve equation (values of a and b)
- A prime, p, defining the field Fp
- The elliptic group computed from the curve equation
- A base point B, taken from the elliptic group (analogous to the generator g in classic Diffie-Hellman)
Step 2 — Each user's key pair
Notice the shape: private key is a plain number, public key is that number multiplied into the base point. Recovering x from Q and B means solving the ECDLP.
ECC Encryption — the ElGamal Analog
Suppose Alice wants to send Bob an encrypted message M.
Agree on base point B
Both Alice and Bob already know the shared curve, field, and base point B.
Generate key pairs
Alice: private a, public PA = a·B. Bob: private b, public PB = b·B.
Encode the message
Alice encodes plaintext M onto a point PM in the elliptic group.
Pick random k
Alice chooses a random integer k from [1, p−1] — a fresh "session" value, used once.
Build the ciphertext pair
PC = [ (kB), (PM + kPB) ] — two points sent to Bob.
Bob decrypts
Bob computes b·(kB), then subtracts it from the second point: (PM + kPB) − b(kB) = PM + k(bB) − b(kB) = PM.
Decode
Bob decodes PM back into the original message M.
k(bB) and b(kB) are the same point, because scalar multiplication commutes: k·b = b·k. So (PM + kPB) − b(kB) leaves exactly PM — the "kb" terms cancel, exposing the message.
Comparison to classic ElGamal
Ciphertext = [ (kB), (PM + kPB) ] — a pair of curve points.
Ciphertext C = (gk mod p, mPBk mod p). Bob recovers m by dividing the second value by the first raised to his private key: m = mPBk / (gk)b = m.
Same structural idea — a "masking" value combined with a shared secret raised/multiplied by a random session number — just additive point notation instead of multiplicative exponent notation.
ECC Diffie-Hellman Key Exchange
Public: the elliptic curve and a point B=(x,y) on it. Secret: Alice's number a and Bob's number b.
Both generate key pairs
Alice: private a, public PA = a·B. Bob: private b, public PB = b·B.
Exchange public keys
Alice and Bob send each other PA and PB over the open channel.
Combine with own private key
Alice computes KAB = a(bB) = a·PB. Bob computes KAB = b(aB) = b·PA.
Same shared secret
Both land on KAB = abB, since scalar multiplication is commutative (ab = ba).
Mnemonic — ECDH in one line
"Swap the public, multiply by your own private, land on the same point." Alice computes a(bB), Bob computes b(aB) — different paths, same destination abB, because order of scalar multiplication never matters.
Why Use ECC? Security & Key Size
To analyze any cryptosystem, ask: how hard is the underlying math problem?
| Cryptosystem | Underlying Hard Problem |
|---|---|
| RSA | Integer Factorization |
| Diffie-Hellman | Discrete Logarithms (finite field) |
| ECC | Elliptic Curve Discrete Logarithm Problem (ECDLP) — believed strictly harder per bit |
Key size to protect a 128-bit AES key
| System | Required Key Size |
|---|---|
| RSA | 3072 bits |
| ECC | 256 bits |
"Just increase RSA's key length" — impractical
Because factoring difficulty grows sub-exponentially with key size, RSA needs huge keys to keep up. ECC's harder underlying problem means small keys already give strong security — a real advantage on constrained hardware.
Applications & Benefits of ECC
Where ECC shines
- Wireless communication devices
- Smart cards
- Web servers handling many concurrent encryption sessions
- Any application needing strong security without the power/storage/compute budget for RSA-sized keys
Benefits over classic cryptosystems
- Same guarantees: confidentiality, integrity, authentication, non-repudiation
- Much shorter key lengths for equivalent security
- Faster encryption, decryption, and signature verification
- Storage and bandwidth savings
Q = kP, where Q and P belong to a prime curve. Given k and P, computing Q is easy (just repeated point addition). Given Q and P, finding k is hard — the elliptic curve logarithm problem — provided k is large enough. ECC's security rests entirely on this asymmetry, and because it needs much smaller keys than factoring-based systems for the same security level, it offers a real computational edge.
Exam Tips & Tricks
Curve equation memorized cold
y² = x³ + ax + b, with 4a³+27b² ≠ 0 (nonsingular condition). This exact form shows up in MCQs.
Who invented ECC
Neal Koblitz and Victor Miller, independently, in 1985. A classic "who and when" exam question.
Identity element
The point at infinity, O, is the identity — NOT the origin (0,0). Don't mix them up.
RSA vs ECC key sizes
3072-bit RSA ≈ 256-bit ECC for the same (128-bit AES-equivalent) security level. Memorize this exact pair.
RSA's operation vs ECC's operation
RSA = exponentiation. ECC = point multiplication (repeated point addition). Diffie-Hellman = exponentiation too (discrete log in a finite field).
Order divides order
The order of a subgroup always divides the order of the parent elliptic curve group — a frequently tested fact.
Quick Reference — Everything at a Glance
| Topic | Key Point |
|---|---|
| Curve equation | y² = x³ + ax + b, with 4a³ + 27b² ≠ 0 (nonsingular) |
| Symmetry | Curve is symmetric about the x-axis |
| Line property | A straight line meets the curve at exactly 3 points |
| Trapdoor function | Easy forward (point multiplication), hard backward (recover scalar) given a secret trapdoor value |
| Group | Set + binary op with closure, associativity, identity, inverse; +commutativity = abelian group |
| EC group identity | Point at infinity, O |
| EC group inverse | Reflection of point across the x-axis |
| Point addition rule | Three aligned non-zero points P, Q, R sum to O; so P+Q = reflection of the line's 3rd intersection |
| Finite field | Set with finite elements, e.g. integers mod prime p (Z/p, GF(p), Fp) |
| Field operations | + and · both closed, associative, commutative; unique identities & inverses; distributive law holds |
| Cyclic subgroup | Subgroup whose elements repeat cyclically under repeated addition of a generator |
| Base point / generator | Point P that generates the cyclic subgroup |
| Order of P | Smallest positive n such that nP = O |
| Subgroup order rule | Order of subgroup divides order of parent group (n | N) |
| Finding base point algorithm | Find N → choose prime n | N → cofactor h=N/n → random P → G=hP (retry if O) |
| ECC inventors | Neal Koblitz & Victor Miller, 1985, independently |
| Underlying field for ECC | Fp (p>3 prime) or F2m (binary) |
| ECC as public-key system | Public key for encrypt/verify, private key for decrypt/sign — like RSA, Rabin, ElGamal |
| ECC extensions | ECDH (key exchange) and ECDSA (digital signatures) |
| RSA's hard operation | Exponentiation (integer factorization problem) |
| ECC's hard operation | Point multiplication (elliptic curve discrete log problem) |
| Generic ECC public params | Curve (a,b), prime p, elliptic group, base point B |
| Key pair generation | Private key x ∈ [1,p−1]; Public key Q = x·B |
| ECC ElGamal ciphertext | PC = [kB, PM+kPB]; decrypt via PM = second point − b(kB) |
| ECDH shared secret | KAB = abB = a(bB) = b(aB) |
| DLP vs ECDLP | Classic: recover x from gx mod p. Elliptic: recover k from kP — believed harder per bit |
| Security comparison | 128-bit AES ≈ 3072-bit RSA ≈ 256-bit ECC |
| Applications | Wireless devices, smart cards, busy web servers, constrained-resource systems |
| Benefits | Same security guarantees as RSA/DH with shorter keys, faster ops, storage/bandwidth savings |
| ECC "hard problem" summary | Q=kP: easy given k,P → find Q; hard given Q,P → find k (elliptic curve logarithm problem) |