Recent Changes - Search:
Main /

Metodo Di Crittografia AES

La cifratura attraverso il metodo AES e' di tipo simmetrico. E' oggi tra i sistemi piu' usati al mondo di crittografia.

AES permette di scegliere una chiave (un numero) che puo' essere a scelta dell'utilizzatore o a 128 bit, o 192 bit o 256 bit; per questo motivo si divide in AES-128, AES-192 e AES-256.

Prima di cominciare

Anticipo che il sistema AES lavora solo a blocchi di 128 bit, se il vostro messaggio da cifrare non e' lungo un multiplo esatto di 128 bit, va modificato. Il vantaggio di utilizzare blocchi fissi permette di spezzare il lavoro in blocchi, ogni blocco può essere elaborato in parallelo; quindi, avendo piu' elaboratori a disposizione, si puo' risparmiare molto tempo dando un blocco in pasto ad un elaboratore diverso.

I sistemi per modificare il messaggio in modo che sia un multiplo esatto di 128 bit sono vari. Devono garantire che non sia banale decifrare il messaggio, ad esempio aggiungere tutti zeri alla fine del messaggio non e' una buona idea, e dovrebbero mantenere tutti i vantaggi del sistema AES intatti.

Tra i sistemi piu' utilizzati per portare la lunghezza del messaggio di partenza a un multiplo di 128 bit c'e' il sistema CBC che pero' rende il sistema AES non piu' parallelizzabile. Questo perche' il CBC sfrutta il risultato di cifratura di un blocco di 128bit per modificare il successivo e cosi' via fino ad ottenere tutti blocchi da 128 bit. E' il piu' usato perche' e' molto semplice, ma se avete problemi di velocita' evitatelo.

Al contrario il sistema CTR per portare la lunghezza del messaggio ad un multiplo di 128 bit puo' essere parallelizzato. E' piu' difficile da implementare, ma vi risparmiera' molto tempo se potete parallelizzare.

Termini

Siccome tutto il sistema fa operazioni numeriche con massimo blocchetti di 8bit alla volta, tutto il sistema deve trasformare le operazioni in modo che i numeri non superino mai gli 8bit. Tecnicamente si dice che di lavora in un campo finito ` P_(2^8) `. Per esempio noi quando facciamo un'addizione tipo 9+3=12 aggiungiamo una cifra al numero, in un campo finito non si posso aggiungere cifre. In un campo finito i numeri non sono su una retta, ma su un cerchio e quindi si può scrivere 9+3=2.

Per questo motivo i termini utilizzati vanno rivisti:

Numeri a 8 bit (byte)

Un numero formato da 8 bit si chiama byte.

Addizione

L' Addizione e' la funzione XOR (bit a bit)

Moltiplicazione

La moltiplicazione e' una funzione complicatissima, si trasforma il numeri binari in polinomi, si moltiplicano, poi si dividono per ` x^8 + x^4 +x^3 +x +1 ` e si utilizza come risultato il resto della divisione. La spiegazione della divisione fra polinomi e' qui. Esempio:

` 01010111 * 10000011 = (x^6 + x^4 + x^2 + x +1) * (x^7 + x +1) = x^13 + x^11 + x^9 + x^8 + x^6 + x^5 +x^4 +x^3 +1 `

` ( x^13 + x^11 + x^9 + x^8 + x^6 + x^5 +x^4 +x^3 +1) : (x^8 + x^4 +x^3 +x +1) = x^5 + x^3` , con il resto ` x^7 + x^6 + 1 `

quindi:

` 01010111 * 10000011 = x^7 + x^6 + 1 = 11000001 `

Si potevano trovare altre strade per fare una moltiplicazione in un campo finito, ma questo metodo garantisce delle proprieta' che vengono sfruttate dal sistema AES. Se i coefficienti del resto sono negativi o positivi non cambia nulla.

Usando la notazione esadecimale, per rappresentare i bit in maniera piu' stringata, abbiamo:

` {57} * {83} = {c1} `

xtime()

La funzione xtime(), serve a moltiplicare un numero per 00000010 (in esadecimale è {02}).

Numeri a 32 bit (word)

In certi frangenti si lavora con 4 numeri di 8 bit, che fanno un sistema a 32 bit particolare. Un blocco di 4 numeri da 8 bit ciascuno e' chiamato word. Anche qui le formule sono diverse:

Addizione

L' Addizione e' la funzione XOR (bit a bit)

Moltiplicazione

La moltiplicazione' e' una funzione complicatissima, si trasforma il numeri binari in polinomi, si moltiplicano, poi si dividono per ` x^4 +1 ` e si utilizza come risultato il resto della divisione. La spiegazione della divisione fra polinomi e' qui. Bisogna fare attenzione che i coefficienti dei polinomi a 32 bit sono numeri a 8 bit e quindi il loro prodotto segue le regole dei prodotti a 8 bit viste qualche paragrafo prima. Esempio in esadecimale:

` {a3}{a2}{a1}{a0} * {b3}{b2}{b1}{b0} `

applicando l'algebra dei campi finiti corrisponde al prodotto matriciale, molto piu' facile da calcolare:

` [ ({a0},{a3},{a2},{a1}),({a1},{a0},{a3},{a2}),({a2},{a1},{a0},{a3}),({a3},{a2},{a1},{a0})] * [({b0}),({b1}),({b2}),({b3})] = [( {a0}*{b0} + {a3}*{b1}+{a2}*{b2}+{a1}*{b3} ),({a1}*{b0} + {a0}*{b1}+{a3}*{b2}+{a2}*{b3}),({a2}*{b0}+{a1}*{b1}+{a0}*{b2}+{a3}*{b3}),({a3}*{b0}+{a2}*{b1}+{a1}*{b2}+{a0}*{b3}) ] = `

` = [ ({18}+{70}+{3c}+{50}), ({a8}+{b8}+{8e}+{9e}),({63}+{09}+{43}+{2d}),({d3}+{c1}+{f1}+{e3}) ] = `

`= [ ({04}),({00}),({04}),({00}) ] = {00}{04}{00}{04} `

RotWord()

E' una rotazione che si puo' ottenere una rotazione dei 32bit di partenza con il prodotto per {01}{00}{00}{00}, cioè per x3. Abbiamo, infatti, la seguente proprieta':

` [ (00,01,00,00),(00,00,01,00),(00,00,00,01),(01,00,00,00)] * [(b_0),(b_1),(b_2),(b_3)] = [(b_1),(b_2),(b_3),(b_0)]`

che equivale a scrivere in esadecimale: {b3}{b2}{b1}{b0} * {01}{00}{00}{00} = {b0}{b3}{b2}{b1}

Algoritmo AES

Prima di tutto chiariamo che il sistema AES lavora sempre a pezzi da 128bit, cioe' prende 4 gruppi di 32bit alla volta (4 word). Ricordiamo che gruppo di 32 bit (word) e' costituito a sua volta da 4 blocchi da 8 bit (byte).

Il procedimento per cifrare e' sempre lo stesso: a seconda della lunghezza della chiave, cambia solamente il numero di cicli da iterare, con chiave a 128bit sono 10, con la chiave a 192bit sono 12, con la chiave a 256bit sono 14.

Per evitare confusioni mettiamo le variabili che ritroveremo spesso in tabella a seconda della lunghezza della chiave:

 NkNbNr
128 bit4410
192 bit6412
256 bit8414

Cifrare

Prima di cifrare bisogna espandere la chiave e creare delle funzioni particolari.

Vettore Rcon

Si crea il vettore Rcon, formato da word, lungo 176 elementi. Ogni elemento corrisponde alla seguente formula

` R c o n_i = {02}^(i-1){00}{00}{00} `

quindi:

` R c o n_1 = {00}{00}{00}{00} `

` R c o n_2 = {02}{00}{00}{00} `

` R c o n_3 = {04}{00}{00}{00} `

` R c o n_4 = {08}{00}{00}{00} `

` R c o n_5 = {10}{00}{00}{00} `

` R c o n_6 = {20}{00}{00}{00} `

` R c o n_7 = {40}{00}{00}{00} `

` R c o n_8 = {80}{00}{00}{00} `

` R c o n_9 = {1B}{00}{00}{00} `

e cosi' via... Ricordando la moltiplicazione fra byte.

Funzione SubByte()

Questa funzione opera su un byte, come ad esempio {2A}. La spiegazione e' complessa, ma si può vedere come un gioco dove si predono i due valori del byte la cifra a sinistra e' la riga, la cifra a destra e' la colonna e si trova il risultato nell'incrocio della tabella seguente:

 0123456789abcdef
0637c777bf26b6fc53001672bfed7ab76
1ca82c97dfa5947f0add4a2af9ca472c0
2b7fd9326363ff7cc34a5e5f171d83115
304c723c31896059a071280e2eb27b275
409832c1a1b6e5aa0523bd6b329e32f84
553d100ed20fcb15b6acbbe394a4c58cf
6d0efaafb434d338545f9027f503c9fa8
751a3408f929d38f5bcb6da2110fff3d2
8cd0c13ec5f974417c4a77e3d645d1973
960814fdc222a908846eeb814de5e0bdb
ae0323a0a4906245cc2d3ac629195e479
be7c8376d8dd54ea96c56f4ea657aae08
cba78252e1ca6b4c6e8dd741f4bbd8b8a
d703eb5664803f60e613557b986c11d9e
ee1f8981169d98e949b1e87e9ce5528df
f8ca1890dbfe6426841992d0fb054bb16

Quindi il il subByte di {53} è {ED}.

Funzione SubWord()

E' una funzione che applica la funzione SubByte() ai quatto byte di un word. Esempio: 

 Subword(cf 4f 3c 09) = 8a 84 eb 01

Espandere la chiave

Poi bisogna espandere la chiave di cifratura: il termine espandere significa che dobbiamo generare dei numeri. Per l'esattezza si generano [Numero di byte chiave * (Numero di cicli + 1)] byte. Il numero di cicli è 10, 12 o 14 a seconda se usiamo una chiave rispettivamente a 128, 192 o 256 bit. Quindi con chiave da 128 bit (16 byte) abbiamo una chiave espansa composta totalemente da 176 byte.

La chiave viene raggruppata in word, ricordiamo che ogni word e' composto da 32bit (4 byte, cioe' 4 * 8bit). La nuova chiave espansa è una serie di word messi in un vettore, dove i primi 4 word (oppure 6 o 8, a seconda della lunghezza della chiave), sono costituiti proprio da quelli della chiave di partenza. Indichiamo i primi numeri corrispondenti alla chiave con la variabile Nk, cioe' Nk potra' valere solo 4, 6 o 8 a seconda se abbiamo una chiave rispettivamente a 128bit, a 192bit oppure a 256bit.

I numeri dopo Nk-esimo word, i successivi sono generati facendo lo XOR tra il word precedente e il word Nk volte indietro nella sequenza, con qualche eccezione in alcune posizioni. Quindi la formula generale sarebbe:

` (K e y)_i = (K e y)_(i-1) cdot XOR cdot (K e y)_(i-N_k)`

solo che:

  • ogni elemento della chiave che e' nella posizione che e' multiplo di Nk, segue quest'altra formula (nota che Rcon[i/Nk] è un elemento del vettore Rcon):

` (K e y)_i = (K e y)_(i-k) cdot XOR cdot [ S u b W o r d(R o t W o r d((K e y)_(i-1))) cdot X O R cdot Rcon_(i/N_k) ] `

  • se usiamo una chiave a 256 bit il punto precedente vale ancora, ma invece della formula generale, quella generale diventa:

` (K e y)_i = S u b W o r d((K e y)_(i-1)) cdot XOR cdot (K e y)_(i-N_k)`

Per esempio la chiave: 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

espansa diventa: 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F D6 AA 74 FD D2 AF 72 FA DA A6 78 F1 D6 AB 76 FE B6 92 CF 0B 64 3D BD F1 BE 9B C5 00 68 30 B3 FE B6 FF 74 4E D2 C2 C9 BF 6C 59 0C BF 04 69 BF 41 47 F7 F7 BC 95 35 3E 03 F9 6C 32 BC FD 05 8D FD 3C AA A3 E8 A9 9F 9D EB 50 F3 AF 57 AD F6 22 AA 5E 39 0F 7D F7 A6 92 96 A7 55 3D C1 0A A3 1F 6B 14 F9 70 1A E3 5F E2 8C 44 0A DF 4D 4E A9 C0 26 47 43 87 35 A4 1C 65 B9 E0 16 BA F4 AE BF 7A D2 54 99 32 D1 F0 85 57 68 10 93 ED 9C BE 2C 97 4E 13 11 1D 7F E3 94 4A 17 F3 07 A7 8B 4D 2B 30 C5

Vediamo un altro esempio nel dettaglio. Chiave 8e 73 b0 f7 da 0e 64 52 c8 10 f3 2b 80 90 79 e5 62 f8 ea d2 52 2c 6b 7b.

  • K0 = 8e73b0f7
  • K1 = da0e6452
  • K2 = c810f32b
  • K3 = 809079e5
  • K4 = 62f8ead2
  • K5 = 522c6b7b
  • K6 = si prende la chiave precedente 522c6b7b, poi si applica rotWord ottendendo 2c6b7b52, poi si applica subword ottenendo 717f2100, poi si prende l'elemento ` Rcon_(i/N_k) ` che e' 01000000, facendo XOR con l'elemento Rcon si ottiene 707f2100. L'elemento ` Chiave_(i-N_k) ` e' 8e73b0f7. Facendo XOR con quest'ultimo abbiamo il risultato fe0c91f7 = fe0c91f7

Dividere in blocchi

Per cifrare si prendono i bit del messaggio e si dispongo a blocchi di 8bit in matrici 4x4, andando per colonna, non per riga; quindi il messaggio di input i blocchetti di 8 bit si dispongono secondo una matrice fatta cosi':

` [ (i n_1,i n_5,i n_9,i n_13),(i n_2,i n_6,i n_10,i n_14),( i n_3,i n_7,i n_11,i n_15),(i n_4,i n_8,i n_12,i n_16) ] `

Funzione AddRoundKey()

Preso un blocco, ad ogni byte del blocco è sommato (XOR) un byte della chiave espansa, in ordine. Se ogni blocco è di 16 byte, si sfruttano 16byte della chiave per blocco. Nessun byte della chiave espansa è usato più di una volta. Questa operazione è chiamata AddRoundKey.

Funzione MixColumns()

La funzione mixclomuns() fa il seguente prodotto matriciale:

` [ (i n_1,i n_5,i n_9,i n_13),(i n_2,i n_6,i n_10,i n_14),( i n_3,i n_7,i n_11,i n_15),(i n_4,i n_8,i n_12,i n_16) ] * [ ({03}), ({01}), ({01}), ({02}) ] `

Il vettore di destra e' lo stesso per tutti i blocchi.

Cifratura

A questo punto per ogni blocco si ripetono Nr (9 nel caso 128 bit) permutazioni uguali ed poi una differente. In questo modo ritorna 10 il numero di permutazioni necessarie, ma è reso tutto molto complicato. La sequenza di operazione da ripetere 9 volte e':

  1. SubBytes(blocco)
  2. ShiftRows(blocco)
  3. MixColumns(blocco)
  4. AddRoundKey(bloccoi, Chiavei)

vanno eseguite una dietro l'altra 9 volte (nel caso 128 bit).

Mentre per l'ultimo ciclo, il decimo nel caso di 128 bit, si esegue solo:

  1. SubBytes(blocco)
  2. ShiftRows(blocco)
  3. AddRoundKey(bloccoi, Chiavei)

(da completare)