CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Matching Bytes as Finite Field Elements
  • Polynomial Reduction
  • Addition
  • Multiplication

Was this helpful?

Export as PDF
  1. Symmetric Cryptography
  2. AES

Rijndael Finite Field

A first time reader might skip this section and go directly to the description of the round transformations, then come back later (it is mostly useful to understand the construction of the operation MC and SB).

Each byte in AES is viewed as an element of a binary finite field of 256 elements, where it can always be represented as a polynomial of degree at most 7 with coefficients inF2\mathbf{F}_2F2​. The construction of the finite field is made as the quotient ringF2[x]/f(x)\mathbf{F}_2[x]/f(x)F2​[x]/f(x), wherefffis an irreducible polynomial of degree 8 inF2[x]\mathbf F_2[x]F2​[x]so the ring becomes a field.

In AES, the choice forfffis

f(x)=x8+x4+x3+x+1.f(x) = x^8 + x^4 + x^3 + x + 1.f(x)=x8+x4+x3+x+1.

We can check with SageMath that it is irreducible:

F2 = GF(2)
K.<x> = F2[]
f = x^8 + x^4 + x^3 + x + 1
f.is_irreducible()
# True

Matching Bytes as Finite Field Elements

A byte bbb is composed of 8 bits (b7,…,b0)2(b_7, \ldots, b_0)_2(b7​,…,b0​)2​ and is matched to a polynomial as

b7x7+b7x6+⋯+b1x+b0.b_7x^7 + b_7 x^6 + \cdots + b_1 x + b_0.b7​x7+b7​x6+⋯+b1​x+b0​.

For instance, take the byte 3a whose binary decomposition is (0,0,1,1,1,0,1,0)2(0, 0, 1, 1, 1, 0, 1, 0)_2(0,0,1,1,1,0,1,0)2​ and becomes the polynomial

0⋅x7+0⋅x6+1⋅x5+1⋅x4+1⋅x3+0⋅x2+1⋅x+0=x5+x4+x3+x.0\cdot x^7 + 0\cdot x^6 + 1\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x + 0 = x^5 + x^4 + x^3 + x.0⋅x7+0⋅x6+1⋅x5+1⋅x4+1⋅x3+0⋅x2+1⋅x+0=x5+x4+x3+x.

Polynomial Reduction

Polynomials of degree 8 or more can always be reduced, using the fact that in the finite field, we have f(x)=0f(x) = 0f(x)=0 , so we have the relation

x8=x4+x3+x+1x^8 = x^4 + x^3 + x + 1x8=x4+x3+x+1

Why not x8=−x4−x3−x−1x^8 = - x^4 - x^3 - x - 1x8=−x4−x3−x−1? In fact, that's also true, but the coefficient are in F2\mathbf F_2F2​ so the additive inverse−1-1−1 of 111 is itself.

In SageMath, this reduction can be produced in one of the following methods.

Method 1: Remainder of an Euclidean division by fff

(x^8 + x^6 + x^4 + 1) % f
# x^6 + x^3 + x

Method 2: Image in the quotient ring F2[x]/f(x)\mathbf{F}_2[x]/f(x)F2​[x]/f(x)

R = K.quotient(f)
R(x^8 + x^6 + x^4 + 1)
# xbar^6 + xbar^3 + xbar

Method 3: Using the Finite Field class of SageMath directly.

F.<x> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
x^8 + x^6 + x^4 + 1
# x^6 + x^3 + x

On this page we use this last method. Also, this helper converts an element of the finite field to the hexadecimal representation of a byte, and could be useful in the examples:

def F_to_hex(a):
    return ZZ(a.integer_representation()).hex()

b = x^4 + x^3 + x + 1
F_to_hex(b)
# '1b'

Addition

The addition of two polynomials is done by adding the coefficients corresponding of each monomial:

∑i=07aixi+∑i=07bixi=∑i=07(ai+bi)xi.\sum_{i=0}^7 a_ix^i + \sum_{i=0}^7 b_ix^i = \sum_{i=0}^7(a_i + b_i)x^i.i=0∑7​ai​xi+i=0∑7​bi​xi=i=0∑7​(ai​+bi​)xi.

And as the addition of the coefficients is inF2\mathbf{F}_2F2​, it corresponds to the bitwise xor operation on the byte.

Multiplication

Letb7x7+⋯+b1x+b0b_7x^7 + \cdots + b_1x + b_0b7​x7+⋯+b1​x+b0​an element and we consider the multiplication byxxx:

x×(b7x7+⋯+b1x+b0)=b7x8+b6x7+⋯b1x2+b0x.x\times (b_7x^7 + \cdots + b_1x + b_0) = b_7x^8 + b_6x^7 + \cdots b_1 x^2 + b_0x.x×(b7​x7+⋯+b1​x+b0​)=b7​x8+b6​x7+⋯b1​x2+b0​x.

All coefficients are shifted to a monomial one degree higher. Then, there are two cases:

  • Ifb7b_7b7​is000, then we have a polynomial of degree at most 7 and we are done;

  • Ifb7b_7b7​is111, we can replacex8x^8x8byx4+x3+x+1x^4 + x^3 + x + 1x4+x3+x+1during the reduction phase:

x×(x7+b6x6+⋯+b1x+b0)=x8+b6x7+⋯b1x2+b0x=(x4+x3+x+1)+b6x7+⋯+b1x2+b0x\begin{align*} x\times (x^7 + b_6x^6 + \cdots + b_1x + b_0) & = x^8 + b_6x^7 + \cdots b_1 x^2 + b_0x \\ & = (x^4 + x^3 + x + 1) + b_6x^7 + \cdots + b_1x^2 + b_0x \end{align*}x×(x7+b6​x6+⋯+b1​x+b0​)​=x8+b6​x7+⋯b1​x2+b0​x=(x4+x3+x+1)+b6​x7+⋯+b1​x2+b0​x​

This can be used to implement a very efficient multiplication byxxxwith the byte representation:

  1. A bitwise shiftleft operation: (b << 1) & 0xff;

  2. Followed by a conditional addition with 1b if the top bit of bbb is 111.

Here an example in SageMath (we use the finite field construction of method 3):

b = x^7 + x^5 + x^4 + x^2 + 1
F_to_hex(b)
# 'b5'
(2*0xb5 & 0xff) ^^ 0x1b).hex() == F_to_hex(x*b)    # the xor in Sage is "^^"
# True

PreviousAESNextRound Transformations

Last updated 4 years ago

Was this helpful?

Multiplication of two polynomials is more complex (one example would be the , more efficient than the naive algorithm). For an implementation of AES, it is possible to only use the multiplication by xxx, whose byte representation is 02.

Karatsuba algorithm