I find Elliptic Curve Cryptography (ECC) to be one of the most elegant pieces of applied mathematics I have come across in cryptography, because it takes a purely geometric object — the set of points on a curve — and turns it into a group that can carry a full public-key cryptosystem. I use ECC every day without necessarily thinking about it, since it underlies TLS connections, SSH keys, and most modern secure messaging apps. What draws me to it is the efficiency: ECC gives me the same security level as RSA using much smaller keys, because the underlying discrete logarithm problem on elliptic curves is far harder to attack than integer factorization is, per unit of key length.
History and Background
I trace the origin of elliptic curve cryptography to two independent proposals made in 1985 — one by Neal Koblitz and one by Victor Miller — both suggesting that the group structure of points on an elliptic curve over a finite field could be used to build discrete-logarithm-based cryptosystems, analogous to how Diffie-Hellman uses the multiplicative group of integers mod a prime. Elliptic curves themselves had been studied for over a century before that in the context of number theory, most famously connected to Fermat’s Last Theorem through the work of Wiles and Taylor decades later. Adoption of ECC accelerated through the 1990s and 2000s as NIST standardized several recommended curves, and it has since become the backbone of most modern digital signature and key exchange schemes, including ECDSA and ECDH.
Problem Statement
I want a way to build a public-key cryptosystem where key sizes stay small but security remains strong. Classical discrete-log or factoring-based systems like RSA and standard Diffie-Hellman need very large keys (2048+ bits) to stay secure, which is expensive on constrained devices. I want a mathematical group where the discrete logarithm problem is believed to be much harder to solve relative to the size of the group, so that smaller keys (256 bits, for example) can offer comparable or even superior security.
Core Concepts
- Elliptic curve — the set of points $(x,y)$ satisfying $y^2 = x^3 + ax + b$ over some field, together with a special “point at infinity” $\mathcal{O}$.
- Group law — a geometric rule for “adding” two points on the curve to get a third point, which makes the curve’s points form an abelian group.
- Base point (generator) $G$ — a publicly agreed point on the curve used to generate a cyclic subgroup.
- Scalar multiplication — computing $kP$, meaning adding point $P$ to itself $k$ times using the group law, which is the core operation in ECC.
- Elliptic Curve Discrete Logarithm Problem (ECDLP) — given $P$ and $Q = kP$, finding $k$ is computationally hard; this hardness underlies ECC’s security.
How It Works
I explain ECC key exchange (ECDH) step by step:
- Both parties agree on public domain parameters: a finite field, curve coefficients $a, b$, and a base point $G$ of large prime order $n$.
- Alice picks a private random integer $d_A$ and computes her public key $Q_A = d_A \cdot G$.
- Bob picks his private random integer $d_B$ and computes his public key $Q_B = d_B \cdot G$.
- Alice and Bob exchange their public keys $Q_A$ and $Q_B$ over an insecure channel.
- Alice computes the shared secret as $S = d_A \cdot Q_B$.
- Bob computes the shared secret as $S = d_B \cdot Q_A$.
- Because $d_A \cdot Q_B = d_A \cdot (d_B \cdot G) = d_B \cdot (d_A \cdot G) = d_B \cdot Q_A$, both arrive at the same point $S$, which they use to derive a shared symmetric key.
Working Principle
I understand the security here as resting entirely on the fact that scalar multiplication (computing $kP$ from $k$ and $P$) is easy — using efficient doubling-and-adding algorithms — but the reverse operation (finding $k$ from $P$ and $kP$) is believed to be computationally infeasible for well-chosen curves and large enough $n$. This asymmetry is exactly what a trapdoor-style cryptosystem needs: the legitimate parties compute forward multiplications, while an eavesdropper who only sees the public points $Q_A$ and $Q_B$ cannot efficiently recover the private scalars $d_A$ or $d_B$ to compute the shared secret themselves.
Mathematical Foundation
I define the elliptic curve over a finite field $\mathbb{F}_p$ (for prime $p > 3$) as the set of points satisfying:
$$ y^2 \equiv x^3 + ax + b \pmod{p}, \qquad 4a^3 + 27b^2 \not\equiv 0 \pmod p $$
The non-singularity condition $4a^3+27b^2 \neq 0$ ensures the curve has no repeated roots. For point addition, given $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ with $P \neq Q$:
$$ \lambda = \frac{y_2 – y_1}{x_2 – x_1} \pmod p $$
$$ x_3 = \lambda^2 – x_1 – x_2 \pmod p, \qquad y_3 = \lambda(x_1 – x_3) – y_1 \pmod p $$
For point doubling ($P = Q$):
$$ \lambda = \frac{3x_1^2 + a}{2y_1} \pmod p $$
with $x_3, y_3$ computed the same way as above. Scalar multiplication $kP$ is computed efficiently using the double-and-add method, which takes $O(\log k)$ point operations rather than $k-1$ additions:
$$ kP = \underbrace{P + P + \dots + P}_{k \text{ times}} \quad \text{computed in } O(\log k) $$
The security of ECDH and ECDSA rests on the assumed hardness of the ECDLP:
$$ \text{Given } P, Q = kP, \text{ find } k $$
with the best known general-purpose attacks (like Pollard’s rho) taking roughly $O(\sqrt{n})$ time for a group of order $n$, which is why a 256-bit curve gives comparable security to a much larger RSA modulus.
Diagrams
flowchart TD
P1[Choose curve params: p, a, b, G, n] --> P2[Alice picks private dA, computes QA = dA*G]
P1 --> P3[Bob picks private dB, computes QB = dB*G]
P2 --> X[Exchange QA and QB over public channel]
P3 --> X
X --> S1[Alice computes S = dA * QB]
X --> S2[Bob computes S = dB * QA]
S1 --> K[Shared secret S is identical]
S2 --> K
Pseudocode
Function PointAdd(P, Q, a, p):
if P == INFINITY: return Q
if Q == INFINITY: return P
if P.x == Q.x and P.y != Q.y: return INFINITY
if P == Q:
lambda = (3*P.x^2 + a) * inverseMod(2*P.y, p) mod p
else:
lambda = (Q.y - P.y) * inverseMod(Q.x - P.x, p) mod p
x3 = (lambda^2 - P.x - Q.x) mod p
y3 = (lambda*(P.x - x3) - P.y) mod p
return (x3, y3)
Function ScalarMultiply(k, P, a, p):
result = INFINITY
addend = P
while k > 0:
if k & 1:
result = PointAdd(result, addend, a, p)
addend = PointAdd(addend, addend, a, p)
k = k >> 1
return result
Function ECDH_KeyExchange():
dA = randomInt(1, n-1); QA = ScalarMultiply(dA, G, a, p)
dB = randomInt(1, n-1); QB = ScalarMultiply(dB, G, a, p)
sharedA = ScalarMultiply(dA, QB, a, p)
sharedB = ScalarMultiply(dB, QA, a, p)
assert sharedA == sharedB
return sharedA
Step-by-Step Example
I use a small toy curve for illustration: $y^2 = x^3 + 2x + 2 \pmod{17}$, with base point $G = (5, 1)$, which has order $n = 19$ on this curve. Suppose Alice picks $d_A = 6$ and computes $Q_A = 6G$. Using repeated point addition/doubling, this evaluates to $Q_A = (10, 6)$ on this curve. Suppose Bob picks $d_B = 11$ and computes $Q_B = 11G = (7, 6)$. They exchange $Q_A = (10,6)$ and $Q_B = (7,6)$. Alice computes $S = 6 \cdot Q_B = 6 \cdot (7,6)$, and Bob computes $S = 11 \cdot Q_A = 11 \cdot (10,6)$; both computations land on the same point, $S = (13, 7)$, which becomes their shared secret. (These particular coordinates come from the well-known toy example commonly used to teach ECC arithmetic over small fields.)
Time Complexity
I break this into two levels. A single point addition or doubling takes $O(1)$ modular operations (a constant number of multiplications, inversions, and additions modulo $p$). Scalar multiplication $kP$, using double-and-add, takes:
$$ T(k) = O(\log k) $$
point operations, each costing $O(\log^2 p)$ to $O(\log^3 p)$ bit operations depending on the multiplication algorithm used for modular arithmetic, giving an overall practical complexity around:
$$ T = O(\log k \cdot \log^2 p) $$
Space Complexity
I need to store curve parameters ($a$, $b$, $p$, $G$, $n$), and each point requires two field elements of size $O(\log p)$ bits. Overall space usage is:
$$ S = O(\log p) $$
per key, which is why ECC keys are so much smaller than RSA keys for comparable security.
Correctness Analysis
I consider the scheme correct because the group law on elliptic curves is associative and commutative — a well-established result from algebraic geometry — meaning scalar multiplication distributes properly: $d_A(d_B G) = (d_A d_B) G = d_B(d_A G)$. This guarantees Alice’s and Bob’s independently computed shared secrets are always identical, as long as both parties correctly implement the same curve parameters and group law. Security correctness (i.e., that an eavesdropper genuinely cannot recover the shared secret) relies on the conjectured hardness of ECDLP, which has held up well against decades of cryptanalysis for properly chosen curves.
Advantages
- Much smaller key sizes than RSA or classical Diffie-Hellman for equivalent security levels.
- Faster computations and lower power consumption, making it ideal for mobile and embedded devices.
- Well-studied and standardized (NIST P-256, Curve25519, secp256k1, etc.), with wide library support.
- Supports a full suite of cryptographic primitives: key exchange (ECDH), digital signatures (ECDSA, EdDSA).
Disadvantages
- Poorly chosen or backdoored curves can weaken security, as debated around some NIST curve parameter choices.
- Implementation bugs (e.g., improper point validation, weak random number generation) have historically led to real-world key recovery attacks.
- Vulnerable to quantum attacks via Shor’s algorithm, just like RSA, motivating a shift toward post-quantum cryptography.
- More mathematically complex to implement correctly compared to simpler modular exponentiation systems.
Applications
- TLS/SSL for secure web browsing (ECDHE key exchange).
- SSH key authentication (Ed25519 keys).
- Cryptocurrency wallets and transaction signing (Bitcoin and Ethereum use secp256k1 for ECDSA).
- Secure messaging protocols (Signal Protocol uses Curve25519 for key agreement).
- Smart cards and IoT devices where computational resources are limited.
Implementation in C
#include <stdio.h>
/* Toy elliptic curve: y^2 = x^3 + a*x + b (mod p) */
#define P 17
#define A 2
typedef struct {
int x, y;
int isInfinity;
} Point;
/* Modular inverse using Fermat's little theorem (p is prime) */
int mod_pow(int base, int exp, int mod) {
long long result = 1, b = base % mod;
while (exp > 0) {
if (exp & 1) result = (result * b) % mod;
b = (b * b) % mod;
exp >>= 1;
}
return (int)result;
}
int mod_inverse(int a, int mod) {
a = ((a % mod) + mod) % mod;
return mod_pow(a, mod - 2, mod);
}
Point point_add(Point p1, Point p2) {
Point r;
if (p1.isInfinity) return p2;
if (p2.isInfinity) return p1;
if (p1.x == p2.x && (p1.y + p2.y) % P == 0) {
r.isInfinity = 1;
return r;
}
int lambda;
if (p1.x == p2.x && p1.y == p2.y) {
/* point doubling */
int num = (3 * p1.x * p1.x + A) % P;
int den = mod_inverse((2 * p1.y) % P, P);
lambda = (num * den) % P;
} else {
/* point addition */
int num = ((p2.y - p1.y) % P + P) % P;
int den = mod_inverse(((p2.x - p1.x) % P + P) % P, P);
lambda = (num * den) % P;
}
int x3 = ((lambda * lambda - p1.x - p2.x) % P + P) % P;
int y3 = ((lambda * (p1.x - x3) - p1.y) % P + P) % P;
r.x = x3;
r.y = y3;
r.isInfinity = 0;
return r;
}
Point scalar_multiply(int k, Point p) {
Point result;
result.isInfinity = 1; /* point at infinity acts as identity */
Point addend = p;
while (k > 0) {
if (k & 1) {
result = point_add(result, addend);
}
addend = point_add(addend, addend);
k >>= 1;
}
return result;
}
int main() {
Point G = {5, 1, 0}; /* base point on y^2 = x^3 + 2x + 2 mod 17 */
int dA = 6;
int dB = 11;
Point QA = scalar_multiply(dA, G);
Point QB = scalar_multiply(dB, G);
printf("Alice's public key QA = (%d, %d)\n", QA.x, QA.y);
printf("Bob's public key QB = (%d, %d)\n", QB.x, QB.y);
Point sharedA = scalar_multiply(dA, QB);
Point sharedB = scalar_multiply(dB, QA);
printf("Alice computes shared secret: (%d, %d)\n", sharedA.x, sharedA.y);
printf("Bob computes shared secret: (%d, %d)\n", sharedB.x, sharedB.y);
return 0;
}
Sample Input and Output
Alice's public key QA = (10, 6)
Bob's public key QB = (7, 6)
Alice computes shared secret: (13, 7)
Bob computes shared secret: (13, 7)
Both parties independently arrive at the identical shared secret point, confirming the protocol works correctly.
Optimization Techniques
- Using Jacobian or projective coordinates avoids expensive modular inversions during intermediate point additions, only inverting once at the end.
- Choosing curves with efficient endomorphisms (like secp256k1’s GLV method) can speed up scalar multiplication significantly.
- Constant-time implementations of point addition and doubling prevent timing side-channel attacks that could leak the private scalar.
- Precomputing multiples of the base point $G$ speeds up repeated key generation operations.
Common Mistakes
- Using a weak or improperly validated curve, allowing invalid-curve attacks where an attacker sends a point not actually on the intended curve.
- Reusing random nonces in ECDSA signing, which famously leaks the private key (this happened in real-world Sony PlayStation 3 and some Bitcoin wallet incidents).
- Implementing modular inversion or point arithmetic without constant-time guarantees, exposing the implementation to timing attacks.
- Forgetting to check that a received public key point actually lies on the curve and is not the point at infinity, which can lead to serious vulnerabilities.
Further Reading
- Koblitz, N., “Elliptic Curve Cryptosystems,” Mathematics of Computation, 1987. https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/
- Miller, V., “Use of Elliptic Curves in Cryptography,” CRYPTO 1985. https://link.springer.com/chapter/10.1007/3-540-39799-X_31
- NIST, “Digital Signature Standard (DSS),” FIPS 186-5. https://csrc.nist.gov/publications/detail/fips/186/5/final
- Bernstein, D. J., “Curve25519: New Diffie-Hellman Speed Records,” PKC 2006. https://cr.yp.to/ecdh/curve25519-20060209.pdf
- Hankerson, D., Menezes, A., Vanstone, S., “Guide to Elliptic Curve Cryptography,” Springer, 2004. https://link.springer.com/book/10.1007/b97644
