Per comprendere come è fatto AES, potrebbe essere necessario descrivere parte della matematica su cui si fonda, quindi una visione sommaria di questo tipo di algebra è visibile nel file indicato di seguito: matematica astratta (approfondita), di seguito sono mostrati dei rimandi molto generici, per una buona comprensione è consigliato di passare per la risorsa sopra linkata.
AES fu pubblicato dalla National Institute of Standards and Technology (NITS) nel 2001. AES è un cifrario simmetrico a blocco che rimpiazzò DES.
Rimandi di Matematica astratta...
Tutte le operazioni in AES sono effettuate su un byte (8 bit). Le operazioni aritmetiche di addizione, moltiplicazione e divisione sono effettuate nel campo finito
In AES vogliamo lavorare con degli interi che corrispondano esattamente al numero di bit usati. Per questo vorremo lavorare con interi nel range
C'è un modo di definire campi finiti che contengono
Esisteranno un totale di
Se
Prima di tutto avremmo tre x:
Se 0 in prima posizione e 1 in tutte le altre:
Se 0 in prima posizione e in ultima posizione:
Se sono tutti 1:
E così via..
S sarà formato dai seguenti polinomi:
Con l'appropriata definizione delle operazioni aritmetiche, ogni insieme S è un campo finito.
Le appropriate definizioni consistono di:
- L'aritmetica seguita è quella ordinaria dell'aritmetica polinomiale che usa le regole dell'algebra tradizionale, con due aggiunte.
- L'aritmetica sui coefficienti è effettuata in modulo 2 (operazione XOR.
- Se la moltiplicazione produce un polinomio di grado maggiore di
Per esempio per costruire il campo finito della forma
Quindi:
Due valori uguali messi in XOR fanno 0.
(Lo XOR è uguale a 1, quando i due operandi sono diversi).
quindi:
Un polinomio in
AES usa l'aritmetica nel campo finito
Tutte i
La somma è definita come lo XOR, mentre la moltiplicazione è definita in modo che il prodotto tra due byte sia sempre un byte.
Avendo definito somma e prodotto, possiamo anche moltiplicazioni in matrici.
Moltiplicazione in
Per moltiplicare un byte
Avviene uno shift a sinistra di una posizione, ottenendo:
Se
altrimenti se
I byte sono interpretati come polinomi con coefficienti binari, ad esempio:
Struttura generale di AES...
La figura sopra mostra una vista generale di AES.
Il cifrario prende un blocco plaintext di 128 bit (o 16 bytes).
La lunghezza della chiave può essere di 16, 24 o 32 byte (128, 192 o 256 bit).
L'input per la crittazione e decrittazione è un singolo blocco di 128 bit.
Come si vede dall'immagine il blocco è poi disposto in una matrice 4 x 4 di byte, i byte sono indicati in FIPS PUB 197
Questo blocco è copiato in uno State array, che è modificato ad ogni passo della crittazione o decrittazione. Dopo il passo finale, lo State è copiato in una matrice di output. Allo stesso modo, la chiave è raffigurata come una matrice quadrata di byte.
I byte nella matrice sono ordinati per colonna. Per esempio, i primi quattro byte di un plaintext a 128 bit occupano la prima colonna della matrice, i secondi quattro byte la seconda e così via. Allo stesso modo i primi quattro byte della chiava espansa, che formano una word, occupano la prima colonna della matrice.
Il cifrario consiste di N round dove il numero di round dipende dalla lunghezza della chiave.
I primi N - 1 round eseguono quattro distinte funzioni di trasformazione:
- SubBytes
- ShiftRows
- MixColumns
- AddRoundKey
L'ultimo round contiene solo tre di queste trasformazioni e vi è una trasformazione iniziale (AddRoundKey) prima del primo round (round 0). Ogni trasformazione prende una o più matrici 4 x 4 e produce una matrice 4 x 4.
La figura sopra mostra che l'output di ogni round è una matrice 4 x 4.
L'ultima matrice di output è il messaggio cifrato.
Struttura dettagliata...
La figura sopra mostra il cifrario AES in dettaglio, indicando la sequenza delle trasformazioni in ogni round e mostrando la corrispondente funzione di decrittazione. Possiamo fare diversi commenti riguardo la struttura di AES:
- La struttura non è un cifario di Feistel. Nel cifrario di Feistel, metà del blocco dei dati è utilizzato per modificare l'altra metà del blocco e dopo le metà vengono scambiate. AES processa interamente il blocco come una singola matrice durante ogni round usando sostituzioni e permutazioni.
- La chiave fornita è espansa in un array di quarantaquattro word di 32 bit,
- Vi sono 4 stati per ogni round, uno di permutazione e tre di sostituzione:
- Substitute bytes: usa una S-box per effettuare sostituzioni byte-per-byte del blocco;
- ShiftRows: una semplice permutazione;
- MixColumns: una sostituzione che fa uso dell'aritmetica in
- AddRoundKey: XOR bit a bit del blocco corrente con una porzione della chiave espansa (roundKey o chiave di round).
- La struttura è semplice. Sia per la crittazione, che per la decrittazione, il cifrario comincia con una AddRoundKey, seguita da nove round cui ognuno include i quattro passi descritti nel punto precedente, seguiti da un decimo round con soli tre passi.
- Solo la AddRoundKey fa uso della chiave. Per questo motivo, il cifrario comincia e finisce con una AddRoundKey.
- La AddRoundKey è effettivamente una forma del Cifrario di Vernam e di per sé non sarebbe formidabile. Gli altri tre passi insieme forniscono confusione, diffusione e non linearità, ma da soli non fornirebbero alcuna sicurezza, poiché non utilizzano la chiave.
- Ogni passo è reversibile. Per Substitute Byte, ShiftRows, and MixColumns una funzione inversa è utilizzata nell'algoritmo di decrittazione. Invece per AddRoundKey, l'inverso è ottenuto facendo lo XOR della stessa chiave di round (round key) sul blocco risultante. Il blocco che verrà passato all'algoritmo di decrittazione è il blocco che ha utilizzato la chiave del round 10, in fase di decrittazione viene preso il blocco cifrato con quella chiave e viene applicato lo XOR utilizzando la chiave dello stesso round (10). Sarebbe come fare
- Come per la maggior parte dei cifrari a blocchi, l'algoritmo di decrittazione fa uso della chiave espansa in ordine inverso. In ogni caso, il processo di decrittazione non è identico al processo di crittazione. Questa è la conseguenza di una particolare struttura di AES.
- Una volta stabilito che tutti e quattro gli stadi sono reversibili è facile verificare che la decrittazione recupera il testo in chiaro.
- L'ultimo round sia della crittazione che della decrittazione consiste di solo tre stadi. Ancora, questo è una conseguenza della particolare struttura di AES ed è richiesto per rendere il cifrario reversibile.
La ShiftRows...
Come abbiamo detto il blocco di 128 bit è disposto in una matrice 4 x 4.
I byte sono disposti in colonna:
Quando avviene una ShiftRows, ciascuna riga viene shiftata di 1 a sinistra in maniera ciclica di 0, 1, 2 o 3 posizioni e questo dipende dalla riga corrente.
Guardando l'immagine della matrice sopra:
- la prima riga viene shiftata di 0
- la seconda viene shiftata di 1
- la terza viene shiftata di 2
- la quarta viene shiftata di 3
Il risultato è il seguente:
Lo shift è detto circolare, poiché quando viene effettuato a sinistra, il byte che si trova in prima posizione, scorre verso sinistra diventando l'ultimo.
La funzione inversa di ShiftRows effettua gli shift nella direzione opposta, quindi a destra.
La MixColumns...
Ogni byte di una certa colonna otterrà un nuovo valore in funzione di tutti e quattro i byte nella colonna corrente. In questa fase, ogni colonna del blocco dati viene trattata come un vettore di 4 byte, ciascuna colonna viene moltiplicata per una matrice fissa di trasformazione che è la seguente:
L'operazione è effettuata in
Ciascuna colonna viene moltiplicata per la matrice i cui valori sono fissati, ottenendo un nuovo blocco, in cui gli elementi delle colonne hanno valori differenti rispetto al blocco iniziale.
L'invero di questa funzione è implementata sfruttando la moltiplicazione del blocco per un'altra matrice con valori fissati che serve per invertire il procedimento. La matrice è la seguente:
Il procedimento applicato è lo stesso.
Poiché in 
La generazione delle chiavi di round (roundKey)...
L'espansione della chiave di AES prende in input una chiave di 16 byte e produce un array di 44 word (176 byte). Questo è sufficiente per avere quattro word da usare per ciascun round di AES (che sono 10 e 1 di AddRoundKey).
Il pseudocodice che segue descrive il funzionamento dell'espansione
KeyExpansion(byte key[16], word w[44]){
word temp;
for (i = 0; i < 4; i++){
w[i] = (key[4 * i], key[4 * i + 1], key[4 * i + 2], key[4 * i + 3]);
// Nota che la chiave è definita come byte e che la chiave espansa
// w è definita come word di 44 posizioni. Ciascuna word contiente 4 byte.
// In questa fase vengono copiati i byte della chiave nei byte delle word
// di w, quindi alla fine di questo processo 4/44 word saranno state riempite
// con i byte della chiave di 16 byte.
}
for(i = 4; i < 44; i++){
temp = w[i - 1];
if(i % 4 == 0)
temp = SubWord(RotWord(temp)) XOR Rcon[i/4];
w[i] = w[i - 4] XOR temp;
}
// La parte restante della chiave espansa (le altre 40 word) viene riempita
// con quattro word alla volta. Ogni word aggiunta w[i] dipende dalla word
// precedente w[i - 1] e la word di 4 posizioni prima w[i - 4].
// In tre casi su quattro è utilizzato il semplice operatore di XOR.
// Per le word che sono posizionate in un indice di w multiplo di 4,
// l'operazione è più complessa. Tale funzione complessa è indicata con 'g'
// Nella figura che sugue in basso.
}
c
Tale funzione g sfrutta altre sotto-funzioni, che sono:
- RotWord che effettua uno shift circolare a sinistra;
- SubWord effettua la sostituzione di un byte su ogni byte della word ricevuta in input usando la S-box;
- Il risultato delle prime due è messo in XOR con una costante di round Rcon[j].
La costante di round è una word in cui i tre byte più a destra sono sempre 0. Quindi l'effetto di una word messa in XOR con Rcon è semplicemente quello di applicare uno XOR sul byte più a sinistra della word. La costante di round è diversa per ogni round ed è definita come
Cerchiamo di capire meglio cosa succede...
Abbiamo le 4 word iniziali che non sono state altro che copiate dalla chiave fornita in input di 16 byte.
Per generare la word 4, viene utilizzata la funzione g. In particolare:
Prossimo argomento: operazioni sui cifrari a blocchi