An elliptic curve is defined by y² = x³ + ax + b. Points on the curve form a group under geometric addition. Scalar multiplication in this group is easy; reversing it (the discrete log) is hard. This one-way door gives us public-key cryptography with keys 10x shorter than RSA.
The curve equation
An elliptic curve over the reals is the set of points (x, y) satisfying y² = x³ + ax + b, plus a special "point at infinity" that acts as the identity element. The curve must be non-singular: 4a³ + 27b² ≠ 0.
Point addition geometrically
To add points P and Q: draw a line through them. It intersects the curve at a third point R. Reflect R across the x-axis to get P+Q. When P = Q, use the tangent line instead. This operation is associative and commutative, making the points a group.
Scheme
; Elliptic curve point addition over a finite field; Curve: y^2 = x^3 + ax + b (mod p); We use a = 0, b = 7 (secp256k1, Bitcoin's curve), small p for demo
(define p 97) ; small prime field
(define a 0)
(define b 7)
; Modular inverse via extended Euclidean algorithm
(define (mod-inv x m)
(define (egcd a b)
(if (= a 0)
(list b 01)
(let ((r (egcd (modulo b a) a)))
(list (car r)
(- (caddr r) (* (quotient b a) (cadr r)))
(cadr r)))))
(let ((r (egcd (modulo x m) m)))
(modulo (cadr r) m)))
; Point addition (points as lists (x y) or "inf")
(define (ec-add P Q)
(cond
((equal? P "inf") Q)
((equal? Q "inf") P)
((and (= (car P) (car Q))
(= (modulo (+ (cadr P) (cadr Q)) p) 0))
"inf")
(else
(let* ((x1 (car P)) (y1 (cadr P))
(x2 (car Q)) (y2 (cadr Q))
(s (if (and (= x1 x2) (= y1 y2))
(modulo (* (+ (* 3 x1 x1) a)
(mod-inv (* 2 y1) p)) p)
(modulo (* (- y2 y1)
(mod-inv (- x2 x1) p)) p)))
(x3 (modulo (- (* s s) x1 x2) p))
(y3 (modulo (- (* s (- x1 x3)) y1) p)))
(list x3 y3)))))
; Generator point on y^2 = x^3 + 7 (mod 97)
(define G (list 36))
; Verify G is on the curve
(display "G on curve? ")
(display (= (modulo (* 66) p)
(modulo (+ (* 333) 7) p)))
(newline)
; Add G + G
(define G2 (ec-add G G))
(display "2G = ") (display G2) (newline)
; Add G + 2G = 3G
(define G3 (ec-add G G2))
(display "3G = ") (display G3)
Python
# Elliptic curve arithmetic over a finite field# Curve: y^2 = x^3 + 7 (mod 97) โ tiny secp256k1
p = 97
a, b = 0, 7def mod_inv(x, m):
"""Extended Euclidean algorithm"""
g, x1, _ = extended_gcd(x % m, m)
return x1 % m
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
g, x1, y1 = extended_gcd(b % a, a)
return g, y1 - (b // a) * x1, x1
def ec_add(P, Q):
if P == "inf": return Q
if Q == "inf": return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and (y1 + y2) % p == 0:
return"inf"if P == Q:
s = (3 * x1 * x1 + a) * mod_inv(2 * y1, p) % p
else:
s = (y2 - y1) * mod_inv(x2 - x1, p) % p
x3 = (s * s - x1 - x2) % p
y3 = (s * (x1 - x3) - y1) % p
return (x3, y3)
G = (3, 6)
print(f"G on curve? {(6*6) % p == (3**3 + 7) % p}")
G2 = ec_add(G, G)
print(f"2G = {G2}")
G3 = ec_add(G, G2)
print(f"3G = {G3}")
Scalar multiplication
Scalar multiplication means adding a point to itself n times: nP = P + P + ... + P. Using double-and-add, this takes O(log n) steps. The reverse problem, finding n given P and nP, is the elliptic curve discrete logarithm problem (ECDLP). No efficient algorithm is known.
Scheme
; Scalar multiplication via double-and-add; nP = P added to itself n times
(define p 97)
(define a 0)
(define (mod-inv x m)
(define (egcd a b)
(if (= a 0)
(list b 01)
(let ((r (egcd (modulo b a) a)))
(list (car r)
(- (caddr r) (* (quotient b a) (cadr r)))
(cadr r)))))
(modulo (cadr (egcd (modulo x m) m)) m))
(define (ec-add P Q)
(cond
((equal? P "inf") Q)
((equal? Q "inf") P)
((and (= (car P) (car Q))
(= (modulo (+ (cadr P) (cadr Q)) p) 0))
"inf")
(else
(let* ((x1 (car P)) (y1 (cadr P))
(x2 (car Q)) (y2 (cadr Q))
(s (if (and (= x1 x2) (= y1 y2))
(modulo (* (+ (* 3 x1 x1) a)
(mod-inv (* 2 y1) p)) p)
(modulo (* (- y2 y1)
(mod-inv (- x2 x1) p)) p)))
(x3 (modulo (- (* s s) x1 x2) p))
(y3 (modulo (- (* s (- x1 x3)) y1) p)))
(list x3 y3)))))
; Double-and-add
(define (scalar-mult n P)
(cond
((= n 0) "inf")
((= n 1) P)
((even? n) (scalar-mult (/ n 2) (ec-add P P)))
(else (ec-add P (scalar-mult (- n 1) P)))))
(define G (list 36))
(display "5G = ") (display (scalar-mult 5 G)) (newline)
(display "10G = ") (display (scalar-mult 10 G)) (newline)
(display "20G = ") (display (scalar-mult 20 G))
ECDH key exchange
Elliptic Curve Diffie-Hellman works the same way as classical DH, but in the elliptic curve group. Alice picks secret a, publishes aG. Bob picks secret b, publishes bG. Both compute abG = baG. An eavesdropper sees G, aG, bG but cannot compute abG without solving ECDLP.
Scheme
; ECDH key exchange simulation; Same curve setup as above (y^2 = x^3 + 7 mod 97)
(define p 97)
(define a-coeff 0)
(define (mod-inv x m)
(define (egcd a b)
(if (= a 0) (list b 01)
(let ((r (egcd (modulo b a) a)))
(list (car r) (- (caddr r) (* (quotient b a) (cadr r))) (cadr r)))))
(modulo (cadr (egcd (modulo x m) m)) m))
(define (ec-add P Q)
(cond
((equal? P "inf") Q) ((equal? Q "inf") P)
((and (= (car P) (car Q)) (= (modulo (+ (cadr P) (cadr Q)) p) 0)) "inf")
(else
(let* ((x1 (car P)) (y1 (cadr P)) (x2 (car Q)) (y2 (cadr Q))
(s (if (and (= x1 x2) (= y1 y2))
(modulo (* (+ (* 3 x1 x1) a-coeff) (mod-inv (* 2 y1) p)) p)
(modulo (* (- y2 y1) (mod-inv (- x2 x1) p)) p)))
(x3 (modulo (- (* s s) x1 x2) p))
(y3 (modulo (- (* s (- x1 x3)) y1) p)))
(list x3 y3)))))
(define (scalar-mult n P)
(cond ((= n 0) "inf") ((= n 1) P)
((even? n) (scalar-mult (/ n 2) (ec-add P P)))
(else (ec-add P (scalar-mult (- n 1) P)))))
(define G (list 36))
; Alice's secret and public key
(define alice-secret 15)
(define alice-public (scalar-mult alice-secret G))
(display "Alice public (15G): ") (display alice-public) (newline)
; Bob's secret and public key
(define bob-secret 22)
(define bob-public (scalar-mult bob-secret G))
(display "Bob public (22G): ") (display bob-public) (newline)
; Shared secret: Alice computes a*bG, Bob computes b*aG
(define alice-shared (scalar-mult alice-secret bob-public))
(define bob-shared (scalar-mult bob-secret alice-public))
(display "Alice shared: ") (display alice-shared) (newline)
(display "Bob shared: ") (display bob-shared) (newline)
(display "Match? ") (display (equal? alice-shared bob-shared))
Why ECC is more efficient than RSA
A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key. Shorter keys mean faster computation, less bandwidth, and smaller certificates. The reason: the best known attack on ECDLP (Pollard's rho) runs in O(√n) time, while the best attack on RSA's factoring problem (number field sieve) runs in sub-exponential time. ECC's problem is harder per bit.
Elliptic-curve cryptography