Lecture 6 - Cryptography III

Elliptic curve basic definition

An elliptic curve is not a function but a geometric object: the set of points (x,y) satisfying an equation of the form y² = x³ + ax + b over a field.

Elliptic curve visual property

Over the real numbers, elliptic curves are symmetric across the x-axis and any non-horizontal line intersects them in exactly one or three points.

General elliptic curve definition

Defined by an equation where the x-degree is 3 and y-degree is 2; forms a smooth algebraic curve useful for group operations.

Elliptic curve addition rule

To compute A ⊕ B: draw line through points A and B; it intersects curve at C'; reflect C' across x-axis to get point C = A ⊕ B.

Elliptic curve geometric picture

Line through A and B meets curve at C'; reflection gives the group-sum point C.

Negative of point on EC

For P=(x,y), the negative −P is (x, −y).

Neutral element on EC

The point at infinity O acts as identity: P ⊕ O = P and P ⊕ (−P) = O.

EC group structure

The set E(F_p) union {O} with ⊕ forms an abelian group.

Finite-field elliptic curves

Elliptic curves used in crypto are defined over finite fields F_p, not ℝ.

EC equation over finite fields

Solve y² = x³ + ax + b in F_p; produces a finite set of points.

EC abelian group over F_p

Points + point-at-infinity still form abelian group under defined addition.

Cyclic subgroup requirement

Not all E(F_p) are cyclic; crypto chooses curves where group is cyclic or contains large prime-order cyclic subgroup.

Base point G

On standardized curves, G generates a large prime-order subgroup used for cryptography.

Big picture DLP

DLP appears in multiplicative finite fields (g^x = h) and elliptic curves ([x]G = Q); hard in both if parameters well chosen.

ECDLP definition

Given base point G and Q = [x]G, find scalar x; considered computationally hard.

Finite-field DLP parameters

Work in subgroup of F*_p of size q; public values p,g,h; secret x such that g^x ≡ h mod p.

Safe prime construction

Let p = 2q + 1; pick random u; set g = u^((p−1)/q) mod p such that g ≠ 1.

ECDLP parameters

Elliptic curve E(Fq), base G of prime order r, cofactor h; secret x ∈ Zr such that Q = [x]G.

Why ECC wins

Finite-field DLP has sub-exponential attacks; ECDLP best known attacks are exponential → ECC offers same security with far smaller keys.

ECC performance

256-bit ECC ≈ 3072-bit RSA; lower bandwidth, faster operations.

FF vs EC comparison

Finite field uses multiplication and exponentiation; EC uses point addition and scalar multiplication; both rely on discrete logs but attack surfaces differ.

Scalar multiplication in ECC

Compute [x]G via repeated doubling/addition; fast; hard to invert.

EC point addition formula

For P≠Q: λ = (yq − yp)/(xq − xp); xr = λ² − xp − xq; yr = λ(xp − xr) − y_p mod p.

EC point doubling formula

λ = (3xp² + a)/(2yp); then same formula structure for resulting point.

EC security insight

Computing nP is easy; given P and nP, finding n is hard (ECDLP).

EC small example

Curve y² = x³ + 2x + 3 over F_97; P=(3,6), Q=(10,21); P⊕Q=(49,34) mod 97.

Transition to RSA

Move from discrete-log–based systems to systems based on integer factorization hardness.

Euler phi motivation

Need to know number of invertible elements in Z_m to construct RSA decryption exponent; value given by Φ(m).

Phi function definition

Φ(m) counts integers in {0,…,m−1} relatively prime to m.

Phi example Φ(6)

gcd(1,6)=1 and gcd(5,6)=1 → Φ(6) = 2.

Phi example Φ(5)

All nonzero numbers mod 5 are coprime → Φ(5)=4.

Phi via prime factorization

If m = p₁^{e₁} p₂^{e₂} … pn^{en}, then Φ(m)=Π (pi^{ei} − pi^{ei−1}).

Phi example Φ(240)

240=2⁴⋅3⋅5 → Φ(240)=64.

Factorization importance

In RSA, computing Φ(N) is easy if you know p,q; hard without factoring → security relies on difficulty of factoring N.

Fermat’s Little Theorem

If p prime, a^p ≡ a mod p; equivalently a^{p−1} ≡ 1 mod p for a≠0.

FLT inverse formula

a^{-1} ≡ a^{p−2} mod p for prime p.

FLT inverse example

Inverse of 2 mod 7 is 2^{5}=32≡4 mod 7.

Euler’s theorem

For gcd(a,m)=1: a^{Φ(m)} ≡ 1 mod m; generalizes FLT.

Euler’s theorem example

m=12,a=5 → Φ(12)=4 → 5⁴=625≡1 mod 12.

FLT special case

Euler’s theorem reduces to FLT when m is prime (Φ(p)=p−1).

GCD motivation

In Z_m, a has inverse mod m iff gcd(a,m)=1; need fast gcd computation → Euclidean algorithm.

GCD intuition

gcd(a,b) is largest integer dividing both; geometric interpretation: largest segment that tiles both lengths.

Naive gcd methods

Enumerating divisors or repeated subtraction too slow; need Euclid’s remainder-based method.

Euclidean algorithm key fact

If a = bq + r, then gcd(a,b) = gcd(b,r); reduces problem size each step.

Euclidean algorithm procedure

Iteratively replace (a,b) with (b,r) until r=0; last nonzero remainder is gcd.

Euclidean algorithm example

gcd(252,105)=21 through repeated division steps.

Extended Euclidean purpose

Finding integers x,y such that ax + by = gcd(a,b); used to compute inverses modulo m.

Bezout identity

For any a,b not both zero, ∃ integers x,y s.t. ax + by = gcd(a,b).

Inverse via Bezout

If gcd(a,m)=1 then ax + my =1 → ax≡1 mod m → x is a^{-1} mod m.

Extended Euclid recursive idea

Compute gcd(b,r), express r = a − bq, back-substitute to get combination ax + by.

Inverse example mod 26

7^{-1} mod 26 found by Euclid + back-substitution → 15.

RSA motivation

Want reversible exponentiation m ↦ m^e mod n with decryption exponent d.

RSA modulus n

Choose primes p,q; let n=pq.

Phi(n) for RSA

Φ(n) = (p−1)(q−1).

Carmichael λ(n)

λ(n) = lcm(p−1,q−1); minimal exponent guaranteeing correctness.

CRT role

If a≡b mod n ⇔ a≡b mod p and mod q; used in RSA correctness proofs.

RSA correctness (Euler version)

If ed ≡ 1 mod Φ(n), then m^{ed} ≡ m mod n for all m.

RSA correctness (Carmichael version)

If ed ≡ 1 mod λ(n), then m^{ed} ≡ m mod n for all m; λ smaller so optimal.

Example showing λ suffices

n=15,p=3,q=5 → Φ(15)=8,λ(15)=4; e=3,d=3 mod 4; correctness still holds.

Choosing e

Valid e satisfies gcd(e,λ(n))=1 (same valid set as gcd(e,Φ(n))=1).

Key takeaway on λ(n)

λ(n) divides Φ(n); using λ produces minimal universal exponent; security from hardness of factoring n.