Implementing Advanced Encryption Standard from Scratch

1. Introduction/Why implement from scratch?

I have been working amongst these cryptographic tech for the past 5 years. The main focus in these years had always been the application of these cryptographic tools. Whether it was a hashing algorithm, signature scheme, encryption/decryption, zkvms etc. Although I used these tools frequently, I had not delved too deep into the mathematics behind them and I had a great interest in learning the wizardry behind these tools to broaden my knowledge. The first thing that I wanted to do was understand the symmetric cryptography and I came across AES. Simply reading the specification was not enough and was not too comprehensible for me. I then decided to implement all the components myself with the aim to understand the nitty gritty of all the small details that makes AES work. I did not want to use any cryptographic libraries, so the goal of this project was strictly understanding and correctness and not optimization.

2. A little background on AES

2.1 Why AES even exists?

AES was the new and advanced encryption standard designed to replace the previously existing Data Encryption Standard (DES). DES used a 56 bit length key and processed 64 bits of data at a time. With the growing computation power, this standard quickly became susceptible to brute force attacks. So, in 2001, AES was introduced, which operated in 128, 192, or 256 bits key sizes and a 128 bit block. So, it became computationally infeasible for computers to brute force. The bytes are not treated as integers but as elements of a finite field.

3. Mathematics behind AES

3.1 Integer Arithmetics

Addition, subtraction, multiplication and division are the arithmetic operations needed to explain the mathematics behind AES. Integer arithmetic includes these operations between two or more integer values.

\[\begin{aligned} 1 + 1 &= 2 \\ 2 \times 2 &= 4 \\ 3 - 1 &= 2 \\ 2 \div 2 &= 1 \end{aligned}\]

3.2 Modular Arithmetics

Modular arithmetic in a really simple term is dividing any given number with a number say p and taking the remainder of it.

\[\begin{aligned} 5\,\operatorname{mod}\,2 &= 1 \end{aligned}\]

Because, when dividing 5 by 2, the quotient is 2 and the remainder is 1, so 5 mod 2 is 1.

Modular arithmetic has a special property such that it keeps the result bounded within the value of the modulus.

In the above example, no matter what the value is, the remainder remains <2. Just like a wall clock, when the wall clock reaches 12, it wraps around to land on 1 then 2 and so on.

3.3 Finite fields

To understand finite fields, lets first take a look into fields.

3.3.1 Fields

Fields are sets of numbers which have two field operations, addition and multiplication, which need to satisfy these field axioms.

Addition axioms

Closure: If a and b are in the set, then a + b is also in the set.
Associativity: (a + b) + c = a + (b + c)
Commutativity: a + b = b + a
Additive Identity: For all a there exists an additive identity I such that a + I = a.
Additive Inverse: For all a there exists -a such that a + (-a) = I.

Multiplication axioms

Closure: If a and b are in the set, then a . b is also in the set.
Commutativity: a . b = b . a
Associativity: a . (b . c) = (a . b) . c
Multiplicative Identity: For all a there exists an identity element I such that a . I = a.
Multiplicative Inverse: For all a != 0 there exists a' such that a . a' = I.

Examples of fields:

Real numbers: All the numbers in the number line make up a field, they follow all the axioms. The additive identity is 0 and the multiplicative identity is 1. Every number also has its own set of additive and multiplicative inverses.
Set {0, 1, 2, 3, 4} mod 5.

Lets see how this is a field. All operations are done under mod 5, so any addition and multiplication operations are bounded under 5.

\[\begin{aligned} 3 + 4 &= 7\,\operatorname{mod}\,5 = 2 \\ 3 \times 4 &= 12\,\operatorname{mod}\,5 = 2 \end{aligned}\]

So, this satisfies the closure property. Similarly,

\[\begin{aligned} 3 + 4 &= 4 + 3 = 7\,\operatorname{mod}\,5 = 2 \\ 3 \times 4 &= 4 \times 3 = 12\,\operatorname{mod}\,5 = 2 \end{aligned}\]

So, this satisfies commutativity. Also,

\[\begin{aligned} 3 + (4 + 5) &= (3 + 4) + 5 = 12\,\operatorname{mod}\,5 = 2 \\ 3 \times (4 \times 5) &= (3 \times 4) \times 5 = 60\,\operatorname{mod}\,5 = 0 \end{aligned}\]

So, this satisfies associativity. Now, the set has multiplicative identity as 1 and additive identity 0.

Here, lets find out the inverses of the set.

Additive Inverse:

\[\begin{aligned} 1 + 4 &= 5\,\operatorname{mod}\,5 = 0 \\ 2 + 3 &= 5\,\operatorname{mod}\,5 = 0 \end{aligned}\]

And so on, so for every element there exists its additive inverse.

Multiplicative Inverse:

\[\begin{aligned} 1 \times 1 &= 1\,\operatorname{mod}\,5 = 1 \\ 2 \times 3 &= 6\,\operatorname{mod}\,5 = 1 \\ 4 \times 4 &= 16\,\operatorname{mod}\,5 = 1 \end{aligned}\]

Which means, this set satisfies all field axioms and hence is a field.

Examples of non-field sets:

Integers: Integers have additive inverses but not multiplicative inverses.

3.3.2 Prime fields

From the above example, a set of elements,

\[A = \{0, 1, 2, 3, 4\}\,\operatorname{mod}\,5\]

We can notice that the modulus is 5, which is a prime number. So a set

\[\{x \in \mathbb{Z} \mid 0 \le x \le p - 1,\; \text{where } p \text{ is prime}\}\,\operatorname{mod}\,p\]

is a prime field.

So, by extension, any field which is bounded is a finite field.

3.4 Polynomial Rings

Polynomial rings refers to an algebric structure formed by the group of polynomials with cofficients in another ring or field.

For example:

Polynomials under integer cofficients.

\[\begin{aligned} f(x) = x^2 + 3x - 3 \end{aligned}\]
Polynomials under field:

Lets consider a field {0, 1, 2, 3, 4} \operatorname{mod} 5.

Then these set of polynomials:

\[\begin{aligned} f(x) = x^2 + 4x + 1 \end{aligned}\]

3.5 Extension fields

An extension field is a field, which is made with a base field.

For example consider a field, {0, 1} \operatorname{mod} 2.

Now lets take the polynomials:

\[ f(x) = x \\ f(x) = 1 \\ f(x) = x + 1 \\ f(x) = 0 \]

Let us consider an irreducable polynomial:

\[ p(x) = x^2 + 1 \]

Then the extension field is the set of the above defined polynomials with cofficients from the field {0, 1} \operatorname{mod} 2 mod p(x).