Algoritmo AES

Introduzione

L'algoritmo Advanced Encryption Standard - AES è stato introdotto dal National Institute of Standards and Technology (NIST) [2] come algoritmo di crittografia simmetrico sostitutivo del DES, ormai obsoleto, e delle varianti attualmente in uso. Il NIST ha selezionato nel 2000 l'algoritmo Rijndael come algoritmo simmetrico di nuova generazione tra un elenco di candidati, ed è diventato ufficialmente uno standard nella primavera del 2001. Il Rijndael è stato sviluppato dal Dr. Joan Daemen e dal Dr. Vincent Rijmen, due crittografi belgi, ed ha superato gli altri algoritmi candidati grazie alla combinazione di caratteristiche positive, tra cui sicurezza e velocità [1].

Rijndael si è dimostrato essere abbastanza veloce, con una piccola richiesta di memoria e sicuro. Se si impiegasse un dispositivo in grado di rompere l'algoritmo DES in un secondo, ovvero provare in un secondo tutte le chiavi DES (255, pari a circa 3.6 1016 chiavi), dovrebbe impiegare 1.49 1014 anni per rompere l'algoritmo AES con chiavi da 128 bit.

L'AES può essere impiegato con chiavi di lunghezza pari a 128, 192 e 256 bit. Anche nella versione più corta, la sicurezza è superiore a quella del Triple-DES, che combina tre chiavi DES da 56 bit (112 bit). Nonostante non sia possibile prevedere il periodo di tempo in l'algoritmo AES rimarrà sicuro, il NIST prevede oltre 20 anni di impiego come standard crittografico.

Principi matematici

Campi Finiti

Un byte, indicato dalla sequenza di bit (b7,b6,b5,b4,b3,b2,b1,b0), può essere rappresentato come il seguente polinomio b(x):
b(x) = b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0
Ad esempio, il byte (01100011) corrisponde al polinomio:
b(x) = 0 x7 + 1 x6 + 1 x5 + 0 x4 + 0 x3 + 0 x2 + 1 x + 1 = x6 + x5 + x + 1
Inoltre, il byte può essere rappresentato attraverso la notazione esadecimale seguente: 0xhk. Un byte può assumere valori da 0 fino a 255, quindi viene rappresentato con due cifre esadecimali: ad esempio 01100011 = 0x63

Addizione

Dati due byte, la loro somma sarà un polinomio i cui coefficienti sono la somma modulo 2 dei coefficienti dei due addendi. La somma modulo 2 può viene effettuata con l'operazione xor

Dato il byte a = a7,a6,a5,a4,a3,a2,a1,a0 e b = b7,b6,b5,b4,b3,b2,b1,b0, la somma sarà c = a7 xor b7, a6 xor b6, a5 xor b5, a4 xor b4, a3 xor b3, a2 xor b2, a1 xor b1, a0 xor b0.

Anche la sottrazione tra due byte viene eseguita tramite l'operatore xor, quindi l'addizione e la sottrazione di due byte sono identiche e hanno lo stesso risultato.

Esempio

(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2

0 1 0 1 0 1 1 1 xor
1 0 0 0 0 0 1 1 =
------------------
1 1 0 1 0 1 0 0

11010100 = 1 x7 + 1 x6 + 0 x5 + 1 x4 + 0 x3 + 1 x2 + 0 x + 0 = x7 + x6 + x4 + x2
In notazione esadecimale: 0x57 + 0x83 = 0xd4

Moltiplicazione

La moltiplicazione viene effettuata tra le due rappresentazioni polinomiali modulo il seguente polinomio: x8 + x4 + x3 + x + 1. Notare che tale polinomio non può essere rappresentato con un solo byte, ma con due.
La moltiplicazione ha la proprietà distributiva rispetto all'associazione e 0x01 è l'elemento identità. Moltiplicando un generico polinomio b(x) = b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0 per x (rappresentazione polinomiale di 00000010, 0x02}) si ottiene: {{b7 x8 + b6 x7 + b5 x6 + b4 x5 + b3 x4 + b2 x3 + b1 x2 + b0 x, in rappresentazione binaria b7,b6,b5,b4,b3,b2,b1,b0,0. Una tale operazione può essere effettuata tramite uno shift a sinistra dei bit che compongono il byte e inserendo il valore 0 a destra.
Il risultato è un polinomio di grado 8, che deve essere ridotto tramite l'operazione di modulo. Per effettuarla si esegue la sottrazione con il polinomio x8 + x4 + x3 + x + 1, implementata attraverso l'operazione di xor.
Se il coefficiente b7 è nullo, allora il polinomio è già ridotto e non deve essere eseguita la sottrazione.
Questa operazione, composta da uno shift a sinistra e un eventuale sottrazione con il polinomio viene chiamata xtimes. Effettuando una ulteriore operazione xtimes al risultato precedente si ottiene il risultato della moltiplicazione b(x) x2. Si può ottenere la moltiplicazione per le varie potenze di x attraverso la ripetuta applicazione dell'operazione xtimes e in seguito usare la proprietà distributiva della moltiplicazione.

Esempio

Si suppone di voler effettuare il prodotto (0x57)(0x13). Nella rappresentazione polinomiale si ha: (x6 + x4 + x2 + x + 1)(x4 + x + 1).
Usando la proprietà distributiva della moltiplicazione allora il prodotto può essere scomposto così
(x6 + x4 + x2 + x + 1) x4 + (x6 + x4 + x2 + x + 1)*x + (x6 + x4 + x2 + x + 1)*1
In esadecimale si ha: (0x57)(0x13) = (0x57)(0x10) + (0x57)(0x02) + (0x57)(0x01).
Essendo 1 l'elemento identità per la moltiplicazione allora banalmente
(x6 + x4 + x2 + x + 1)*1 = (x6 + x4 + x2 + x + 1), quindi (0x57)(0x01) = 0x57.
(x6 + x4 + x2 + x + 1)x = si effettua l'operazione xtimes: in notazione binaria il polinomio è 01010111. Si effettua una shift a sinistra:
010101110, essendo b7 = 0 allora il polinomio è già di grado 7 e non deve essere effettuata la sottrazione. Il polinomio risultante è 10101110 = x7 + x5 + x3 + x2 + x che corrisponde a 0xae. Quindi (0x57)(0x02 = 0xae.
Si effettua nuovamente l'operazione xtimes: (0x57)(0x04) = (0x57)(0x02)(0x02) = (0xae)(0x02
(x7 + x5 + x3 + x2 + x)*x =
Si effettua lo shift a sinistra di 10101110 ottenendo 101011100. In questo caso b7 = 1, quindi si effettua la sottrazione tramite xor con il polinomio x8 + x4 + x3 + x + 1 = 100011011

1 0 1 0 1 1 1 0 0 xor
1 0 0 0 1 1 0 1 1 =
---------------------
0 0 1 0 0 0 1 1 1 = (01000111) = (0x47)

Proseguendo si effettua un nuovo spostamento a sinistra ottenendo (010001110) = (0x8e) che è un polinomio di grado 7, quindi già ridotto. (0x47)(0x02) = (x6 + x2 + x + 1)*x = (0x8e). Infine effettuando una ulteriore operazione xtimes applicata al polinomio (0x8e) si ottiene: (0x8e) = (10001110). Si esegue lo shift a sinistra 100011100 e si effettua la sottrazione per ridurre il polinomio:

1 0 0 0 1 1 1 0 0 xor
1 0 0 0 1 1 0 1 1 =
---------------------
0 0 0 0 0 0 1 1 1 = (00000111) = (0x07)

Ottenendo (0x8e)(0x02) = (0x07).
Quindi (0x57)(0x13) = (0x57)(0x10) + (0x57)(0x02) + {0x57)(0x01) = (0x07) + (0xae) + (0x57). La somma, effettuata attraverso l'operazione di xor risulta (0xfe).

Polinomi con elementi dei campi finiti

4 byte appartenenti al campo finito GF(28) possono essere utilizzati come coefficienti di un polinomio
a(x) = a3x3 + a2x2 + a1x + a0
I coefficienti [a0 a1 a2 a3] rappresentano in totale una word da 32 bit: ogni coefficiente è un byte e non un bit.

Addizione

Due polinomi a(x) = a3x3 + a2x2 + a1x + a0 e b(x) = b3x3 + b2x2 + b1x + b0, la loro somma è definita attraverso l'operazione xor dei coefficienti dei polinomi: c(x) = a(x) + b(x) = (a3 xor b3)x3 + (a2 xor b2)x2 + (a1 xor b1)x + (a0 xor b0).

Moltiplicazione

Dati coefficienti ai di a(x) e bj di b(x), sia ai bj il loro prodotto definito come sopra. Allora il prodotto dei due polinomi a(x)*b(x) viene definito come il polinomio di grado 6 seguente:
a(x)*b(x) = c6x6 + c5x5 + c4x4 + c3x3 + c2x2 + c1x + c0 dove:
c0 = a0*b0
c1 = a1*b0 + a0*b1
c2 = a2*b0 + a1*b1 + a0*b2
c3 = a3*b0 + a2*b1 + a1*b2 + a0*b3
c4 = a3*b1 + a2*b2 + a1*b3
c5 = a3*b2 + a2*b3
c6 = a3*b3
Il polinomio c(x), non rappresentando una word, deve essere ridotto attraverso l'operazione di modulo rispetto al seguente polinomio di grado 4:
x4 + 1

Sia d(x) = d3x3 + d2x2 + d1x + d0 il polinomio c(x) ridotto in modo che il coefficiente i-esimo del polinomio d(x), ovvero di è dato dalla sommatoria dei coefficienti ci mod 4 con i = 0,…,6:
d0 = c0 + c4 = a0*b0 + a3*b1 + a2*b2 + a1*b3
d1 = c1 + c5 = a1*b0 + a0*b1 + a3*b2 + a2*b3
d2 = c2 + c6 = a2*b0 + a1*b1 + a0*b2 + a3*b3
d3 = c3 = a3*b0 + a2*b1 + a1*b2 + a0*b3
L'operazione può essere rappresentata in modo equivalente con la moltiplicazione delle matrici:

(1)
\begin{align} \left[ \begin{array}{c} d_0 \\ d_1 \\ d_2 \\ d_3 \end{array} \right] = \left[ \begin{array}{cccc} a_0 & a_3 & a_2 & a_1 \\ a_1 & a_0 & a_3 & a_2 \\ a_2 & a_1 & a_0 & a_3 \\ a_3 & a_2 & a_1 & a_0 \end{array} \right] \left[ \begin{array}{c} b_0 \\ b_1 \\ b_2 \\ b_3 \end{array} \right] \end{align}

Per l'algoritmo AES viene scelto come polinomio a(x) il seguente:
a3 = 0x03 = 3
a2 = 0x01 = 1
a1 = 0x01 = 1
a0 = 0x02 = 2
a(x) = 3x3 + x2 + x + 2
Equivalente alla matrice

(2)
\begin{align} \left[ \begin{array}{cccc} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{array} \right] \end{align}

Utilizzando il polinomio a(x), i coefficienti di sono i seguenti:
d0 = (0x02)*b0 + (0x03)*b1 + b2 + b3
d1 = b0 + (0x02)*b1 + (0x03)*b2 + b3
d2 = b0 + b1 + (0x02)*b2 + (0x03)*b3
d3 = (0x03)*b0 + b1 + b2 + (0x02)*b3
Il polinomio a(x) possiede un polinomio inverso a-1(x):
a-13 = 0x0b = 11
a-12 = 0x0d = 13
a-11 = 0x09 = 9
a-10 = 0x0e = 14
a-1(x) = 11x3 + 13x2 + 9x + 14
Equivalente alla matrice

(3)
\begin{align} \left[ \begin{array}{cccc} 0e & 0b & 0d & 09 \\ 09 & 0e & 0b & 0d \\ 01 & 09 & 0e & 0b \\ 0b & 0d & 09 & 0e \end{array} \right] \end{align}

Ottenuto il polinomio d(x) dalla prima matrice, allora utilizzando la matrice inversa si riottengono i coefficienti di b(x):
b0 = (0x0e)*d0 + (0x0b)*d1 + (0x0d)*d2 + (0x09)*d3
b1 = (0x09)*d0 + (0x0e)*d1 + (0x0b)*d2 + (0x0d)*d3
b2 = (0x0d)*d0 + (0x09)*d1 + (0x0e)*d2 + (0x0b)*d3
b3 = (0x0b)*d0 + (0x0d)*d1 + (0x09)*d2 + (0x0e)*d3

Esempio:
Si suppone di avere il polinomio b(x) = (0x2c)*x3 + (0x1a)*x2 + (0xcd)*x + (0x0f)
b0 = 0x0f
b1 = 0xcd
b2 = 0x1a
b3 = 0x2c
Allora il polinomio d(x) avrà come coefficienti il risultato dell'operazione di moltiplicazione per la matrice corrispondente al polinomio a(x):
d0 = (0x02)*(0x0f) + (0x03)*(0xcd) + 0x1a + 0x2c = 0x1e + 0x4c + 0x1a + 0x2c = 0x64
d1 = 0x0f + (0x02)*(0xcd) + (0x03)*(0x1a) + 0x2c = 0x0f + 0x81 + 0x2e + 0x2c = 0x8c
d2 = 0x0f + 0xcd + (0x02)*(0x1a) + (0x03)*(0x2c) = 0x0f + 0xcd + 0x34 + 0x74 = 0x82
d3 = (0x03)*(0x0f) + 0xcd + 0x1a + (0x02)*(0x2c) = 0x11 + 0xcd + 0x1a + 0x58 = 0x9e
Il polinomio b(x) si riottiene a partire da d(x) effettuando la moltiplicazione per la matrice inversa:
b0 = (0x0e)*(0x64) + (0x0b)*(0x8c) + (0x0d)*(0x82) + (0x09)*(0x9e) = 0x4e + 0x83 + 0xc0 + 0x02 = 0x0f
b1 = (0x09)*(0x64) + (0x0e)*(0x8c) + (0x0b)*(0x82) + (0x0d)*(0x9e) = 0x69 + 0x09 + 0xe1 + 0x4c = 0xcd
b2 = (0x0d)*(0x64) + (0x09)*(0x8c) + (0x0e)*(0x82) + (0x0b)*(0x9e) = 0xe2 + 0x80 + 0x5d + 0x25 = 0x1a
b3 = (0x0b)*(0x64) + (0x0d)*(0x8c) + (0x09)*(0x82) + (0x0e)*(0x9e) = 0xa1 + 0x86 + 0xfe + 0xf5 = 0x2c

Descrizione

L'algoritmo AES opera su blocchi di byte di input, effettuando varie trasformazioni e operazioni, generando un corrispondente blocco di byte in output. I dati in ingresso vengono suddivisi in blocchi da 128 bit (16 byte). Ogni blocco in input da 128 bit viene trasformato di un blocco in output da 128 bit corrispondente. L'algoritmo utilizza per le elaborazioni un blocco da 128 bit aggiunto detto stato.
La chiave simmetrica può essere di 16 byte (128 bit), 24 bit (192 bit) o 32 byte (256 bit).
Inizialmente, il blocco di 128 bit di input viene copiato nel blocco dello stato. Successivamente viene effettuato un insieme di trasformazioni, detto round per un determinato numero di volte e infine lo stato viene copiato nel blocco di output. Il numero di round Nr dipende dalla lunghezza della chiave Nk:

Lunghezza chiave (Nk) Numero round (Nr)
128 bit 10
192 bit 12
256 bit 14

Un blocco di dati come quello di input, di output e dello stato viene rappresentato come una matrice di 16 byte composta da 4 righe e 4 colonne. Siano in0, … , in15 i byte del blocco di input:

in0 in4 in8 in12
in1 in5 in9 in13
in2 in6 in10 in14
in3 in7 in11 in15

e out0, …, out15 i byte del blocco di output

out0 out4 out8 out12
out1 out5 out9 out13
out2 out6 out10 out14
out3 out7 out11 out15

Il blocco dello stato è costituito dai byte sij dove i è l'indice della riga e j si riferisce alla colonna. L'elemento S23 è posizionato nella riga 2 e nella colonna 3 (le righe e le colonne vengono numerate da 0: gli indici i e j vanno da 0 a 3 compresi).

S00 S01 S02 S03
S10 S11 S12 S13
S20 S21 S22 S23
S30 S31 S32 S33

Un round è composto da 4 diverse trasformazioni, parametrizzate da un blocco di dati di 4 byte detto key schedule che viene generato dalla chiave.
Le 4 operazioni che vengono effettuate sono:

  • SubBytes: sostituzione dei byte dello stato attraverso una tabella di sostituzione detta SBox
  • ShiftRows: Spostamento delle righe dello stato
  • MixColums: Mescolamento dei dati nelle colonne dello stato
  • AddRoundKey: aggiunta della key schedule allo stato

In ogni round vengono effettuate queste operazioni, tranne nell'ultimo round dove non viene compiuta la trasformazione MixColumns.
L'algoritmo procede quindi effettuando un'iniziale operazione AddRoundKey, ripetendo per Nr-1 volte le 4 operazioni SubBytes, ShiftRows, MixColumn, AddRoundKey e infine compie l'ultimo round composto dalle operazioni SubBytes, ShiftRows, AddRoundKey. A questo punto nel blocco di dati dello stato sono presenti i byte che costituiscono l'output.
In pseudocodice si può schematizzare così:

state = in
AddRoundKey
round = 0
 
while(round<Nr)
{
      SubBytes
      ShiftRows
      MixColumns
      AddRoundKey
      round = round + 1
}
SubBytes
ShiftRows
AddRoundKey
 
out = state

Operazioni

SubBytes

L'operazione SubBytes consiste di una sostituzione dei byte dello stato attraverso una tabella di sostituzione (SBox). Esiste una corrispondente tabella di sostituzione inversa, che verrà utilizzata nella decifrazione dei dati.
La tabella di sostituzione viene generata in questo modo: dato un byte b7, b6, b5, b4, b3, b2, b1, b0 viene calcolato il byte sostitutivo b'7, b'6, b'5, b'4, b'3, b'2, b'1, b'0 attraverso le operazioni di prodotto e somma delle matrici seguenti:

(4)
\begin{align} \left[ \begin{array}{c} b'_0 \\ b'_1 \\ b'_2 \\ b'_3 \\ b'_4 \\ b'_5 \\ b'_6 \\ b'_7 \end{array} \right] = \left[ \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{array} \right] \left[ \begin{array}{c} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{array} \right] + \left[ \begin{array}{c} 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{array} \right] \end{align}

b'0 = b0 + b4 + b5 + b6 + b7 + 1
b'1 = b0 + b1 + b5 + b6 + b7 + 1
b'2 = b0 + b1 + b2 + b6 + b7 + 0
b'3 = b0 + b1 + b2 + b3 + b7 + 0
b'4 = b0 + b1 + b2 + b3 + b4 + 0
b'5 = b1 + b2 + b3 + b4 + b5 + 1
b'6 = b2 + b3 + b4 + b5 + b6 + 1
b'7 = b3 + b4 + b5 + b6 + b7 + 0
L'operatore + indicato è una operazione di xor, ovvero
b'0 = b0 + b4 + b5 + b6 + b7 + 1 = b0 xor b4 xor b5 xor b6 xor b7 xor 1

Esempio

Si considera il byte 0x53 = (01010011) quindi:
b'0 = 1
b'1 = 0
b'2 = 1
b'3 = 1
b'4 = 0
b'5 = 1
b'6 = 1
b'7 = 1
il byte 10110111 corrisponde a 0xed.

Tabella di sostituzione

Per semplicità viene fornita una tabella di sostituzione dove sono presenti tutti i valori di sostituzione dei 256 valori che può assumere un byte.

0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Un byte 0xNM viene sostituito con il valore presente nella tabella alla riga N e alla colonne M. Ad esempio, il byte 0x53 viene sostituito con il valore corrispondente alla riga 5 e colonna 3, ovvero 0xed. Allo stesso modo, il byte 0xaf viene sostituito 0x79, il byte 0xb7 in 0xa9, 0x11 in 0x82, ecc.

ShiftRows

L'operazione ShiftRows effettua uno shift (spostamento) ciclico a sinistra dei byte relativi alle ultime 3 righe dello stato, mentre la prima riga resta immutata. Il normale shift a sinistra di un byte provocherebbe la perdita del byte più a sinistra perché lo spostamento lo farebbe fuoriuscire dal blocco e lascerebbe un byte "vuoto" a destra. Lo shift ciclico di un byte a sinistra invece inserisce il byte che andrebbe perso al posto del byte vuoto. I byte che scomparirebbero all'estremità sinistra riappaiono all'estremità destra. La seconda riga viene spostata di un byte, la terza di due byte e la quarta e ultima di tre byte.
Se una riga è formata dai byte S0, S1, S2, S3 allora una shift a sinistra ciclico di un byte risulta nella riga S1, S2, S3, S0. Notare che il byte S0 è stato inserito a destra.
Dato il blocco dello stato seguente:

S00 S01 S02 S03
S10 S11 S12 S13
S20 S21 S22 S23
S30 S31 S32 S33

L'operazione ShiftRows lo trasforma nel seguente modo:

S00 S01 S02 S03
S11 S12 S13 S10
S22 S23 S20 S21
S33 S30 S31 S32

MixColumns

L'operazione MixColumns viene effettuata considerando separatamente ogni colonna della matrice dello stato, trattandola come un polinomio. Quest'ultimo viene moltiplicato per il polinomio a(x) = 3x3 + x2 + x + 2 riducendolo modulo x4 + 1.
Si considera la colonna c della matrice dello stato, costituita dai coefficienti S0C, S1C, S2C, S3C. Il polinomio risultante dalla moltiplicazione per a(x) è:

S'0C = (0x02)*S0C + (0x03)*S1C + S2C + S3C
S'1C = S0C + (0x02)*S1C + (0x03)*S2C + S3C
S'2C = S0C + S1C + (0x02)*S2C + (0x03)*S3C
S'3C = (0x03)*S0C + S1C + S2C + (0x02)*S3C
Il polinomio S'0C, S'1C, S'2C, S'3C diventa la nuova colonna c della matrice dello stato. L'operazione si ripete per tutte le 4 colonne.

AddRoundKey

L'operazione AddRoundKey considera singolarmente le colonne della matrice dello stato ed effettua una operazione xor byte per byte con un blocco di dati da 32 bit (word) detto Key Schedule generato da una apposita funzione detta Key Expansion. Ad ogni round la funzione genera 4 blocchi da 32 bit con i quali viene effettuato l'operazione di xor con le 4 colonne dello stato. Ad ogni operazione AddRoundKey sono necessari 4 blocchi da 32 bit, uno per colonna. Siano w0, w1, …, w4*(Nr+1) i blocchi generati: alla prima operazione AddRoundKey vengono utilizzati i blocchi {{w0, w1, w2, w3 mentre alla operazione AddRoundKey relativa al round i-esimo vengono utilizzati i blocchi {{w4*i, w4*i+1, w4*i+2, w4*i+3.

Key Expansion

La funzione Key Schedule genera a partire dalla chiave K di cifratura un totale di 4*(Nr+1) word. Ogni blocco di 4 word generato viene utilizzato per l'operazione AddRoundKey che effettua uno xor tra queste word e le colonne della matrice di stato (ogni colonna rappresenta una word). Ad ogni round viene effettuata una operazione AddRoundKey più una operazione AddRoundKey iniziale: essendo Nr il numero dei round, allora diventa chiaro perché sono necessari 4*(Nr+1) word.
La funzione Key Schedule utilizza due sottofunzioni chiamate RotWord e SubWord. La funzione RotWord riceve in input una word ed effettua uno shift ciclico a sinistra di un byte. La funzione SubWord riceve in input una word e effettua la sostituzione dei 4 byte che la compongono attraverso la tabella di sostituzione (SBox) utilizzata per la funzione SubBytes. In output viene generata una word composta dai 4 byte sostituiti.
Viene anche definita una funzione RCon(i) che riceve in input un valore i=1, …, n e genera una word definita come:
[xi-1 0x00 0x00 0x00]
dove tutti i byte della word tranne il primo sono nulli e quest'ultimo assume il valore di xi-1, secondo il sistema di elevamento a potenza descritto nella funzione xtimes. Il valore x viene considerato come un byte di valore 0x02, essendo un polinomio dove i coefficienti sono: 00000010 = 0x02
Per i=1 allora x1-1 = x0 = 0x01. Ad ogni incremento di i si effettua l'operazione xtimes:

i xi-1 i xi-1
1 00000001 0x01 11 01101100 0x6c
2 00000010 0x02 12 11011000 0xd8
3 00000100 0x04 13 10101011 0xab
4 00001000 0x08 14 01001101 0x4d
5 00010000 0x10 15 10011010 0x9a
6 00100000 0x20 16 00101111 0x2f
7 01000000 0x40 17 01011110 0x5e
8 10000000 0x80 18 10111100 0xbc
9 00011011 0x1b 19 01100011 0x63
10 00110110 0x36 20 11000110 0xc6

Quindi la word generata dalla funzione RCon per i=6 è [x5 0x00 0x00 0x00] = [0x20 0x00 0x00 0x00].

A partire dalla chiave di cifratura K, costituita da Nk word, vengono generate 4*(Nr+1) word che compongono i dati della Key Expansion. Le prime Nk word sono esattamente uguali alla chiave K. Le successive word vengono create attraverso il seguente algoritmo:
All'iterazione i-esima, la word wi viene generata come il risultato dell'operazione di xor tra la word precedente wi-1 e la word generata nella Nk iterazione precedente a i:
wi = wi-1 xor wi-Nk
Le word relative alle iterazioni i che sono multiple di Nk (se Nk = 4 allora per le word w4, w8, w12, ecc.) si procede in modo diverso: si considera la word immediatamente precedente wi-1, si effettuano le operazioni RotWord (rotazione) e SubWord (sostituzione). Poi si compie l'operazione xor tra la word risultante da queste due operazioni con la word generata dalla funzione RCon a cui viene passato come argomento il valore i/Nk. Infine, viene nuovamente compiuta una operazione xor tra la word risultante e quella generata nella Nk iterazione precedente:
wi = (SubWord(RotWord(wi-1)) xor RCon(i/Nk)) xor wi-Nk

Ad esempio, se Nk = 4 e la chiave è la seguente: [0x2b 0x7e 0x15 0x16] [0x28 0xae 0xd2 0xa6] [0xab 0xf7 0x15 0x88] [0x09 0xcf 0x4f 0x3c] allora le prime 4 word saranno identiche a quelle della chiave:
w0 = [0x2b 0x7e 0x15 0x16]
w1 = [0x28 0xae 0xd2 0xa6]
w2 = [0xab 0xf7 0x15 0x88]
w3 = [0x09 0xcf 0x4f 0x3c]
Si genera la word w4, corrispondente a i=4 in questo modo:
Si applica l'operazione RotWord(w3) = [0xcf 0x4f 0x3c 0x09] e successivamente l'operazione SubWord che sostituisce ogni byte attraverso la tabella SBox: 0xcf viene sostituito con 0x8a, 0x4f con 0x84, 0x3c con 0xeb e 0x09 con 0x01. La word risultante dopo le due operazioni è [0x8a 0x84 0xeb 0x01].
La funzione RCon(4/4) = RCon(1) restituisce la word [0x01 0x00 0x00 0x00]. Allora:
[0x8a 0x84 0xeb 0x01] xor [0x01 0x00 0x00 0x00] = [0x8b 0x84 0xeb 0x01]. Si effettua l'ultima operazione di xor tra quest'ultimo risultato e la word wi-Nk = w4-4 = w0 = [0x2b 0x7e 0x15 0x16] ottenendo:
w4 = [0x8b 0x84 0xeb 0x01] xor [0x2b 0x7e 0x15 0x16] = [0xa0 0xfa 0xfe 0x17]
Le word successive sono semplicemente risultanti dall'operazione xor tra la word precedente e quella Nk = 4 posizioni precedenti:
w5 = w4 xor w5-Nk = w4 xor w1 = [0xa0 0xfa 0xfe 0x17] xor [0x28 0xae 0xd2 0xa6] = [0x88 0x54 0x2c 0xb1]
w6 = w5 xor w2 = [0x88 0x54 0x2c 0xb1] xor [0xab 0xf7 0x15 0x88] = [0x23 0xa3 0x39 0x39]
w7 = w6 xor w3 = [0x23 0xa3 0x39 0x39] xor [0x09 0xcf 0x4f 0x3c] = [0x2a 0x6c 0x76 0x05]
Essendo i=8 un multiplo di 4, allora si ha:
w8 = (SubWord(RotWord(w7)) xor RCon(2)) xor w4 =
= (SubWord(RotWord([0x2a 0x6c 0x76 0x05])) xor [0x02 0x00 0x00 0x00]) xor [0xa0 0xfa 0xfe 0x17]
= (SubWord([0x6c 0x76 0x05 0x2a]) xor [0x02 0x00 0x00 0x00]) xor [0xa0 0xfa 0xfe 0x17]
= ([0x50 0x38 0x6b 0xe5] xor [0x02 0x00 0x00 0x00]) xor [0xa0 0xfa 0xfe 0x17]
= [0x52 0x38 0x6b 0xe5] xor [0xa0 0xfa 0xfe 0x17]
= [0xf2 0xc2 0x95 0xf2]
L'algoritmo prosegue fino a quando non ha generato 4*(Nr+1). Per Nk = 4 si ha Nr = 10, quindi l'ultima word è w44

Algoritmo inverso

L'algoritmo inverso prevede delle trasformazioni inverse da utilizzare per ricostruire l'input non cifrato attraverso la stessa chiave di cifratura. Le operazioni inverse sono chiamate InvShiftRows, InvSubBytes, InvMixColumns. In pseudocodice, l'algoritmo inverso effettua le seguenti operazioni:

state = in
AddRoundKey
round = N,,r-1,,
 
while(N,,r,,>1)
{
    InvShiftRows
    InvSubBytes
    AddRoundKey
    InvMixColumns
}
InvShiftRows
InvSubBytes
AddRoundKey
 
out = state

L'algoritmo inverso è analogo a quello descritto in precedenza: out e in sono rispettivamente il blocco di output e il blocco di input, mentre state è il blocco dello stato. Dopo un'iniziale chiamata all'operazione AddRoundKey, vengono effettuati Nr-1 round dove sono eseguite le 4 operazioni sullo stato. In seguito viene eseguito l'ultimo round, che consiste di 3 operazioni: non viene effettuata InvMixColumns. Al termine, lo stato conterrà i dati di output.

Operazioni Inverse

InvShiftRows

L'operazione InvShiftRows effettua uno shift (spostamento) ciclico a destra dei byte relativi alle ultime 3 righe dello stato, mentre la prima riga resta immutata. È l'operazione inversa di ShiftRows, che effettuava invece uno spostamento a sinistra. La seconda riga viene spostata di un byte, la terza di due byte e la quarta e ultima di tre byte.
Se una riga è formata dai byte S0, S1, S2, S3 allora una shift a sinistra ciclico di un byte risulta nella riga S3, S0, S1, S2. Dato il blocco dello stato seguente:

S00 S01 S02 S03
S10 S11 S12 S13
S20 S21 S22 S23
S30 S31 S32 S33

L'operazione ShiftRows lo trasforma nel seguente modo:

S00 S01 S02 S03
S13 S10 S11 S12
S22 S23 S20 S21
S31 S32 S33 S30

InvSubBytes

L'operazione InvSubBytes consiste nell'applicazione di una tabella di sostituzione (Substitution Box - SBox) inversa rispetto a quella impiegata nell'operazione SubBytes.

0 1 2 3 4 5 6 7 8 9 a b c d e f
0 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
1 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
2 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
3 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
4 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
5 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
6 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
7 d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
8 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
9 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
a 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
b fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
c 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
d 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
e a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
f 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d

Un byte 0xNM viene sostituito con il valore presente nella tabella alla riga N e alla colonne M.

Considerando ad esempio il byte 0x4f, usando la tabella di sostituzione dell'operazione SubBytes si ottiene il byte 0x0x84. Utilizzando la tabella inversa, al byte 0x84 corrisponde (linea 8, colonna 4) il byte 0x4f.

InvMixColumns

L'operazione InvMixColumns viene effettuata considerando separatamente ogni colonna della matrice dello stato, trattandola come un polinomio. Quest'ultimo viene moltiplicato per il polinomio a(x) = 11 x3 + 13 x2 + 9 x + 14 riducendolo modulo x4 + 1.
Si considera la colonna c della matrice dello stato, costituita dai coefficienti S0C, S1C, S2C, S3C. Il polinomio risultante dalla moltiplicazione per a(x) è:
S'0C = (0x0e)*S0C + (0x0b)*S1C + (0x0d)*S2C + (0x09)*S3C
S'1C = (0x09)*S0C + (0x0e)*S1C + (0x0b)*S2C + (0x0d)*S3C
S'2C = (0x0d)*S0C + (0x09)*S1C + (0x0e)*S2C + (0x03)*S3C
S'3C = (0x03)*S0C + (0x0d)*S1C + (0x09)*S2C + (0x0e)*S3C

Il polinomio S'0C, S'1C, S'2C, S'3C diventa la nuova colonna c della matrice dello stato. L'operazione si ripete per tutte le 4 colonne.

Bibliography
1. NIST, Advanced Encryption Standard (AES) Questions and Answers, http://www.nist.gov/public_affairs/releases/aesq&a.htm
2. NIST, FIPS PUB 197, "Advanced Encryption Standard", Sito web: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License