Groups, Rings, and Fields

In 1832 the 20-year-old Evariste Galois wrote down his mathematical ideas on the night before a duel that proved fatal. He died the next morning, but his theory of finite fields became the foundation of modern cryptography 150 years later. Every time AES encrypts a byte, it performs operations in the very algebraic structure Galois invented.

• **AES (Advanced Encryption Standard)** - every SubBytes operation computes the multiplicative inverse in GF(2^8), and MixColumns performs matrix multiplication over the same field. Billions of devices perform Galois field operations every second without even knowing it
• **Elliptic curves (ECC)** - ECDSA (signing Bitcoin transactions), ECDHE (TLS handshake in browsers) operate in the group of points on an elliptic curve over a finite field GF(p). The choice of group parameters determines security: the secp256k1 curve (Bitcoin) and P-256 (TLS) are concrete groups with proven properties
• **AES-GCM (authenticated encryption)** - Galois/Counter Mode computes the authentication tag through multiplication in GF(2^128). The name "Galois" in GCM is a direct reference to finite fields. Every HTTPS connection uses GCM for simultaneous encryption and integrity verification

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

• Number Theory for Cryptography

Galois Fields: Born the Night Before a Duel

On May 29, 1832, 20-year-old Evariste Galois spent the night writing mathematics. He knew he would fight a duel at dawn and feared he would not survive. He was right - he died the next day. In those frantic pages he described the theory of what we now call Galois fields: finite structures where addition and multiplication behave with perfect algebraic regularity. His work was ignored for decades. In 1954, when IBM needed arithmetic that computers could execute efficiently, Claude Shannon's work linked information theory to Galois fields. In 2001, when NIST standardized AES, they chose GF(2^8) as the arithmetic backbone - every byte of every AES operation runs through the field a 20-year-old described the night before he died.

Groups

A **group** is a fundamental algebraic structure: a set G with an operation * that satisfies exactly four axioms. These axioms are so general that they describe an enormous variety of mathematical objects - from integers to points on elliptic curves. In cryptography, groups are the arena where Diffie-Hellman, DSA, and all of elliptic-curve cryptography (ECC) operate.

Consider a concrete example: **Z_7* = {1, 2, 3, 4, 5, 6}** under multiplication modulo 7. Since 7 is prime, every nonzero element has an inverse. Check: 3 * 5 = 15 mod 7 = 1, so 3^(-1) = 5. Similarly: 2 * 4 = 8 mod 7 = 1, so 2^(-1) = 4. The identity element is 1. All four axioms hold.

**Cyclic groups and generators:** A group is **cyclic** if there exists an element g (a generator) whose powers produce all elements of the group: G = {g^0, g^1, g^2, ..., g^(n-1)}. In Z_7* the generator g=3 spans the entire group: - 3^1 = 3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1 (all mod 7) - All 6 elements are produced - so 3 is a generator. The **order of an element** is the smallest k such that g^k = e (the identity). - The order of 3 in Z_7* is 6 (a full cycle). - The order of 6 in Z_7* is 2, because 6^2 = 36 mod 7 = 1. **Lagrange's theorem:** the order of any element divides the order of the group. Z_7* has order 6, so element orders can only be 1, 2, 3, or 6.

Why are groups critical for cryptography? The **Diffie-Hellman** protocol operates in a cyclic group: security rests on the fact that computing g^a (exponentiation) is fast, while recovering a from g^a (the discrete logarithm problem) is computationally infeasible for large groups. **ECC** works in the group of points on an elliptic curve, where the analogous problem is even harder. Choosing the right group is choosing between security and performance of the cryptosystem.

Rings and Fields

A group has one operation. But in arithmetic we use two: addition and multiplication. A **ring** is an algebraic structure with two operations linked by the distributive law. A **field** is a ring in which every nonzero element has a multiplicative inverse. Fields are precisely the structure cryptography needs: within them one can add, subtract, multiply, and divide without restrictions.

The key difference between a ring and a field: in the ring Z_6 (integers modulo 6), element 2 has no multiplicative inverse, because 2 * k mod 6 never equals 1 for any integer k. The reason: gcd(2, 6) = 2, not 1. So Z_6 is a ring, but **not a field**. Z_7, on the other hand, is a field: 7 is prime, gcd(a, 7) = 1 for all a from 1 to 6, and every element is invertible.

**Why are fields more important than rings for cryptography?** Cryptography requires **invertible** operations. Encryption is a function E(x), and decryption is E^(-1)(y). If we work in a ring where some elements are non-invertible: - We cannot guarantee decryption of every message - Zero divisors appear: a * b = 0 even though a != 0 and b != 0 - An attacker can exploit non-invertibility for cryptanalysis In a **field** every operation (except division by 0) is invertible. This provides: - Guaranteed invertibility of encryption - Predictable arithmetic without "holes" - Rich algebraic structure for building cryptosystems Z_p (p prime), GF(2^8), GF(2^128) - all fields used in real-world cryptography.

An important fact: a finite field exists if and only if its number of elements equals p^n, where p is prime and n is a positive integer. There is no field with 6, 10, or 12 elements. But GF(2), GF(4), GF(8), GF(16), ... (powers of 2) and GF(3), GF(9), GF(27), ... (powers of 3) all exist. For each valid size the finite field is unique up to isomorphism - a clean result of Galois theory.

Finite Fields GF(p) and GF(2^n)

Finite fields are called **Galois fields** (GF) in honor of Evariste Galois. There are two types of finite fields critically important to cryptography: **GF(p)** - integers modulo a prime p, and **GF(p^n)** - extensions whose elements are represented as polynomials. In cryptography we most often encounter GF(p) for large primes p (RSA, Diffie-Hellman, ECC) and GF(2^n) - extensions over GF(2), where arithmetic reduces to bitwise operations (AES, GHASH).

GF(2^n) is more complex. Its elements are **polynomials of degree at most n-1 with coefficients from GF(2)** (i.e., coefficients are 0 or 1). For example, an element of GF(2^8) is a polynomial such as x^7 + x^4 + x^2 + 1, encoded as the byte 10010101. Adding two polynomials is XOR of coefficients, while multiplication is polynomial multiplication modulo an irreducible polynomial.

**The irreducible polynomial - the analogue of a prime number:** In GF(p) the modulus is the prime number p, which cannot be factored. In GF(2^n) the modulus is an **irreducible polynomial** of degree n, which cannot be factored into lower-degree polynomials over GF(2). Example: x^3 + x + 1 is irreducible over GF(2) because: - It has no roots in GF(2): substituting x=0: 0+0+1=1 (not zero), x=1: 1+1+1=1 (not zero) - It is not divisible by any degree-1 or degree-2 polynomial over GF(2) The choice of irreducible polynomial **does not affect security** - all fields GF(2^n) of the same size are isomorphic. But it does affect **performance**: for AES the polynomial x^8 + x^4 + x^3 + x + 1 was chosen because it enables an efficient hardware implementation.

Why is GF(2^n) ideal for computers? Addition is XOR (one processor instruction). Elements are n-bit integers that fit perfectly in registers. Multiplication is implemented via shifts and XOR. AES uses GF(2^8) because one field element is exactly one byte. AES-GCM uses GF(2^128) because one element is exactly one 128-bit block. Finite fields of characteristic 2 are the bridge between abstract algebra and processor architecture.

Operations in Finite Fields

Now that we understand the structure of GF(2^n), we will examine the operations in detail - using **GF(2^8)** as employed by AES. Each byte (0x00-0xFF) is a field element. AES uses the irreducible polynomial m(x) = x^8 + x^4 + x^3 + x + 1 (0x11B in hex). All AES transformations - SubBytes, MixColumns, and others - are arithmetic in GF(2^8).

**AES S-box: inversion in GF(2^8) + affine transformation** The most cryptographically significant operation in GF(2^8) is computing the multiplicative inverse. The AES S-box works in two steps: 1. **Inversion in GF(2^8):** byte b is replaced by b^(-1) (0 maps to 0) 2. **Affine transformation:** a linear transformation followed by a constant shift Why inversion specifically? - Maximum nonlinearity (minimum correlation with any linear function) - High algebraic degree - Provable resistance to differential and linear cryptanalysis - Without nonlinearity the AES S-box would be vulnerable Inversion is not a random choice. It is optimal with respect to a whole set of cryptographic criteria. An S-box built from a random table provides no such guarantees.

Operations in finite fields are not an abstraction - they are the working tools of modern cryptography. Every time a browser establishes an HTTPS connection, the processor executes millions of operations in GF(2^8) (AES) and GF(p) (ECDHE key exchange). The AES-NI instruction set in modern processors is a hardware implementation of GF(2^8) arithmetic. Abstract algebra invented by Galois in 1832 is literally etched into the silicon of modern processors.

Key Ideas

• **Group** - a set with an operation satisfying four axioms (closure, associativity, identity, inverse). Cyclic groups with generators are the basis of Diffie-Hellman and ECC, where security is built on the hardness of the discrete logarithm problem
• **Ring vs field:** a ring has two operations with distributivity; a field adds multiplicative invertibility for all nonzero elements. Cryptography needs fields - to guarantee the invertibility of encryption and the absence of zero divisors
• **GF(p) and GF(2^n):** two types of finite fields in cryptography. GF(p) - arithmetic mod prime p (RSA, ECC). GF(2^n) - polynomials over GF(2), where addition = XOR (AES, GCM). The irreducible polynomial plays the role of a prime number
• **Operations in GF(2^8):** addition via XOR, multiplication via xtime and reduction, inversion via exponentiation. The AES S-box is built on inversion in GF(2^8) - not by accident, but for provable nonlinearity. Galois theory, written down the night before a fatal duel, is literally etched into every modern processor via AES-NI

Related Topics

Algebraic structures are the mathematical foundation on which concrete cryptosystems and protocols are built:

• AES — AES is built entirely on GF(2^8) arithmetic: SubBytes uses multiplicative inversion, MixColumns performs multiplication by fixed elements. Understanding GF(2^8) algebra is necessary for analyzing the security of AES
• Mathematics of Elliptic Curves — ECC works in the group of points on an elliptic curve over a finite field GF(p). The group operation (point addition), group order, and generator are all applications of the concepts in this lesson to geometric objects
• Number Theory for Cryptography — Previous lesson: modular arithmetic, prime numbers, and Fermat's theorem - the tools on which the finite fields GF(p) are built. Fermat's little theorem gives a way to compute inverses
• RSA: Mathematics — RSA works in the ring Z_n (n = p*q, composite), not in a field. Understanding the difference between a ring and a field explains why RSA requires a special structure (product of two primes) and why factoring n breaks the system

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

• Why does cryptography work in finite fields rather than in infinite ones (real numbers, complex numbers)? What practical and theoretical advantages does finiteness provide?
• The AES S-box uses inversion in GF(2^8). If a different irreducible polynomial had been chosen (not x^8 + x^4 + x^3 + x + 1), would the cryptographic properties of the S-box change? Why or why not?
• RSA works in the ring Z_n (where n is composite), not in a field. What properties of a ring (as opposed to a field) make RSA possible? Hint: consider the role of zero divisors and non-invertible elements.

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

• crypto-03-number-theory — Modular arithmetic and Fermat's theorem underpin GF(p) construction
• crypto-14-aes — AES SubBytes and MixColumns are pure GF(2^8) arithmetic
• crypto-26-ecc-math — ECC groups live on elliptic curves over finite fields built here
• crypto-23-key-exchange — Diffie-Hellman operates in the cyclic groups defined in this lesson
• crypto-24-rsa-math — RSA uses a ring Z_n (not a field) - highlights the ring/field distinction
• ml-04
• nt-01