CodeX
Published in

CodeX

AES: How the Most Advanced Encryption Actually Works

Image source: https://www.venafi.com/blog/what-are-best-use-cases-symmetric-vs-asymmetric-encryption

The Basics

Algorithm Overview

  • 10 rounds for a 128-bit key
  • 12 rounds for a 196-bit key
  • 14 rounds for a 256 bit key
  • subBytes()
  • shiftRows()
  • mixColumns()
  • addRoundKey()
function AESencrypt(plaintext, key) {

blocks := divideIntoBlocks(plaintext);
roundKeys = getRoundKeys(key)
for (block in blocks) { //first round
addRoundKey(roundKeys[0], block);
//intermediate rounds
for (8, 10 or 12 rounds) {
subBytes(block);
shiftRows(block);
mixColumns(block);
addRoundKey(roundKeys[..], block);
}
//last round
subBytes(block);
shiftRows(block);
addRoundKey(roundKeys[numRounds - 1], block);
} ciphertext := reassemble(blocks);
return ciphertext;
}

Mathematical Background

Addition/Subtraction

Multiplication

  • Multiply a(p) and b(p) like normal
  • Reduce the coefficients of the resulting polynomial modulo p.
  • Reduce the entire polynomial mod m(p). This is so our final answer stays less than pⁿ.
function gmul(a : byte, b : byte) {  p : byte = 0x00;

for (8 rounds) {
//if low bit of b is set
if ((b & 1) != 0) {
p = p ⊕ a;
}

//true if the high bit of a is set
h : bool = (a & 0x80) != 0;
a = a << 1; //shift left

if (h) {
a = a ⊕ 0x1B; //value of the polynomial m(p) (0x11B) with the high bit removed
}
b = b >> 1; //right shift return p; }
}

The Multiplicative Inverse/Division

What’s the point?

//multiply by 2 in GF(2^8)
function gmul2(a : byte) {
h : byte = a & 0x80; //high bit b : byte = a << 1; if (h == 0x80) b = b ⊕ 0x1b; return b; }//multiply by 3 in GF(2^8)
function gmul3(a : byte) {
return a ⊕ gmul2(a);}

Key Expansion

function rcon(value : unsigned int) {  c : byte = 1;

if (value == 0) return 0;
while (value != 1) {
c = gmul(c, 2);
value--;
}
return c;}

The Key Expansion Algorithm

  • Let K[0] thru K[N-1] represent the 32-bit words of the original key.
  • Let N equal the length of the original key in 32-bit words (4, 6, or 8 for a 128, 192 or 256-bit key respectively).
  • Let R equal the number of rounds (10, 12, or 15 for a 128, 192 or 256-bit key respectively).
  • Let W[0] thru W[4R-1] represent the 32-bit words comprising all of the round keys. Let’s call this the expanded key.
for (i from 0 to 4R - 1) {  //The first words (W[0] thru W[N-1]) are equal to the words of the original key.
//For a 128-bit key, this means that the first round key is equal to the original key.
if (0 < i < N) W[i] = K[i];
//Perform operations on the last word of each N-length cycle before XOR-ing.
else if (i >= N and i == 0 mod N)
W[i] = W[i-N] subWord(rotate(W[i-1])) rcon(i/N);
//For a 256-bit key length only.
else if (i >= N and N == 8 and i == 4 mod N)
W[i] = W[i-N] subWord(W[i-1]);
//Typical case
else W[i] = W[i-N] W[i-1];
}

An AES Round, Step-by-Step

subBytes()

shiftRows()

mixColumns()

addRoundKey()

Decryption

function AESdecrypt(ciphertext, key) {

blocks := divideIntoBlocks(ciphertext);
roundKeys = getRoundKeys(key)
for (block in blocks) { //first round
addRoundKey(roundKeys[numRounds - 1], block);
shiftRowsInv(block);
subBytesInv(block);
//intermediate rounds
for (8, 10 or 12 rounds) {
addRoundKey(roundKeys[..], block);
mixColumnsInv(block);
shiftRowsInv(block);
subBytesInv(block);
}
//last round
addRoundKey(roundKeys[0], block);
} plaintext := reassemble(blocks);
return plaintext;
}

SafeHouse

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store