Algebra and Cryptography

Every time Chrome opens an HTTPS connection (about 340 billion TLS handshakes per day at Cloudflare), it performs operations in abstract algebraic structures: residue rings for RSA-2048, the Curve25519 point group for ECDH, the GF(2^8) field for AES. Abstract algebra is not 'pure math in an ivory tower'; it is the foundation of digital security.

• TLS 1.3: ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) for key exchange-the group of points on curve X25519
• QR codes: Reed-Solomon codes over GF(256) allow data recovery at up to 30% damage
• Bitcoin: addresses are built via ECDSA on secp256k1, signatures are group operations over curve points

Предварительные знания

• Homological Algebra: Introduction

RSA via Rings: Z/nZ and Euler's Theorem

RSA operates in the ring **Z/nZ**, where n = p·q is a product of two large primes. The ring Z/nZ has n elements {0, 1, ..., n-1} with addition and multiplication mod n. **Euler's totient function:** φ(n) = (p-1)(q-1)-the count of invertible elements. The group of units **(Z/nZ)*** has order φ(n). **Euler's theorem:** If gcd(a, n) = 1, then a^{φ(n)} ≡ 1 (mod n). Encryption: c ≡ m^e (mod n), where e is the public exponent with gcd(e, φ(n)) = 1. Decryption: m ≡ c^d (mod n), where d ≡ e⁻¹ (mod φ(n)). Correctness: c^d = m^{ed} = m^{1+k·φ(n)} = m · (m^{φ(n)})^k ≡ m (mod n).

**Why 2048 bits?** RSA-1024 was broken in 2010 (RSA-768 factored). RSA-2048 requires roughly 10^{20} operations with the number field sieve-beyond current hardware. Shor's quantum algorithm factors n in O((log n)³), which is why post-quantum cryptography shifts to lattice-based problems (NTRU, Kyber).

Elliptic Curves: the Group Law

An **elliptic curve** over a field k: E: y² = x³ + ax + b, with nonzero discriminant Δ = -16(4a³ + 27b²) ≠ 0 (no singular points). The set E(k) = {(x, y) ∈ k² : y² = x³ + ax + b} ∪ {O} (O is the "point at infinity") forms an **abelian group** under point addition: **Geometric meaning:** P + Q is the reflection of the third intersection point of line PQ with the curve. The neutral element is O. **Formulas (P ≠ Q):** λ = (y_Q - y_P)/(x_Q - x_P), x_R = λ² - x_P - x_Q, y_R = λ(x_P - x_R) - y_P. **Doubling (P = Q):** λ = (3x_P² + a)/(2y_P). **ECDH:** Alice picks secret a, publishes A = aG. Bob picks secret b, publishes B = bG. Shared secret: K = aB = bA = abG. An eavesdropper sees G, A, B-but the elliptic curve discrete log problem is exponentially hard.

**Why elliptic curves beat RSA?** ECDH-256 provides the same security as RSA-3072 with keys 12x shorter. This matters for IoT, TLS handshakes, and Bitcoin (secp256k1). The best known ECDLP algorithm-Pollard's rho-has complexity O(√|E(𝔽_p)|), which grows exponentially with key length.

Reed-Solomon Codes and the Discrete Logarithm

A **Reed-Solomon code** RS(n, k) over GF(q): transmit k symbols, append n-k check symbols. Encoding evaluates a degree-(k-1) polynomial at n points of the field. Let α be a primitive element of GF(q), evaluation points: α⁰, α¹, ..., α^{n-1}. **Codeword:** c = (f(α⁰), f(α¹), ..., f(α^{n-1})), where f is the information polynomial of degree < k. Minimum Hamming distance: d_min = n - k + 1. The code corrects ⌊(n-k)/2⌋ errors. **Applications:** QR codes use RS(255, 223) over GF(256)-corrects up to 16 errors. Audio CDs use an interleaved RS code. Voyager used concatenated RS + convolutional coding. **Diffie-Hellman:** in the group Z*_p: Alice: a → g^a mod p. Bob: b → g^b mod p. Shared secret: g^{ab} mod p. The discrete log problem (DLP) in Z*_p is sub-exponential (GNFS), requiring keys ≥ 2048 bits.

**The algebraic foundation of security:** Every classical cryptosystem exploits a "one-way" algebraic structure: polynomial multiplication is easy, factoring is hard (RSA); scalar multiplication on a curve is easy, the discrete log is hard (ECDH). Post-quantum cryptography searches for new one-way functions in lattice and coding problems-again abstract algebra, now in the form of lattice theory and linear codes.

Key Ideas

• RSA: encryption in the ring Z/nZ, correctness via Euler's theorem a^{φ(n)} ≡ 1 (mod n)
• Elliptic curves: E(k) is an abelian group; ECDH security rests on the hardness of the discrete log problem
• Reed-Solomon codes: a polynomial over GF(q) evaluated at n points corrects ⌊(n-k)/2⌋ errors
• Diffie-Hellman: security = hardness of DLP in Z*_p or on an elliptic curve

Further Directions

Cryptography is applied algebra: group theory, rings, finite fields, and elliptic curves. The natural next step is linear codes over Galois fields (BCH, LDPC) and algebraic geometry as a source of new codes and cryptosystems.

• Linear Codes over GF(q) — Reed-Solomon codes are MDS codes over GF(q); the theory of linear codes is built on subspaces over finite fields
• Algebraic Geometry — Elliptic curves are the simplest algebraic varieties; curves over finite fields are the source of Goppa codes and cryptosystems

Вопросы для размышления

• Prove RSA correctness: if ed ≡ 1 (mod φ(n)) and gcd(m, n) = 1, then (m^e)^d ≡ m (mod n). Use Euler's theorem.
• Prove that the points of an elliptic curve form a group: verify associativity of the addition law (this is the most nontrivial property).
• Why can RS(n, k) over GF(q) not have d_min > n - k + 1? This is the Singleton bound. Use the linear independence of polynomial evaluations.

Связанные уроки

• crypto-04-algebraic-structures