PROTEZIONE LOGICA DEI DATI NEI SISTEMI DI COMUNICAZIONE a cura di Gianluca Di Tomassi

Cap 3

Data Encryption Standard (DES)

* Nota storica

Questo algoritmo crittografico è nato dall'esigenza di avere uno standard secondo cui sviluppare gli algoritmi di cifratura. Nel 1971 l' N.B.S. (National Bureau of Standards) su incarico del Governo degli Stati Uniti di America iniziò lo studio della sicurezza dei dati. Nel 1973 furono invitati alcuni progettisti ad interessarsi di sistemicrittografici per la protezione dei dati in una rete di trasmissione o all'interno di un sistema di elaborazione. Il progetto doveva essere economicamente attuabile e i dettagli dell'algoritmo dovevano essere resi pubblici. I risultati ottenuti non furono entusiasmanti tanto che l' invito venne rinnovato nel 1974. In questa occasione venne scelto un progetto dell'IBM. Da un lavoro di Horst Feistel ebbe inizio lo sviluppo di un Federal Data Encryption Standard (DES). Fu emesso nel 1975 e pubblicato nel 1977.

3.1 Algoritmo DES

Tale algoritmo è progettato per cifrare (decifrare) blocchi di dati di 64 bit di testo chiaro (cifrato) in un blocco di uguale lunghezza, tramite una chiave anch' essa di 64 bit. Il processo di decifratura usa la chiave di quello di cifratura, con la sequenza di bit alterata in modo che le due operazioni siano una l' inversa dell 'altra (algoritmo simmetrico).

[Torna inizio pagina]

3.1.1 Cifratura

Su un blocco in ingresso l'algoritmo opera una permutazione P, stabilita al momento di applicare il DES e quindi rimane uguale per ogni blocco in ingresso (può essere cambiata per motivi di sicurezza). Il blocco ottenuto viene scomposto in due parti, sottoposte poi ad un processo di elaborazione chiave-dipendente. Il blocco in uscita subisce una permutazione finale P-1,che è l'inversa della permutazione iniziale. L'elaborazione si basa su una funzione di cifratura F e una funzione key schedule KS.

Il processo di cifratura del DES viene schematizzato con un diagramma di flusso nella pagina seguente.

Indicando con i numeri da 1 a 64 i bit del blocco in ingresso una possibile permutazione iniziale è la seguente:

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4

62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8

57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3

61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

in questo modo il 58-esimo bit del blocco diventa il primo, il 50-esimo il secondo,... e il settimo diventa l'ultimo. Il blocco ottenuto si scompone in una parte sinistra L0 e destra R0 , ciascuna di 32 bit. L'elaborazione consiste in 16 iterazioni di un calcolo basato sulla funzione di cifratura F che opera su due blocchi, uno Rn di 32 bit, uno Kn di 48 bit e restituisce un blocco di 32 bit. Indichiamo con LnRn il blocco in ingresso all' n-esima iterazione, con Kn un blocco di 48 bit dei 64 bit della chiave KEY, ottenuto con uno schema di scorrimento. L' output di una iterazione con input LnRn è Ln+1Rn+1, definito come

Ln+1 = Rn

Rn+1 = Ln xor F( Rn,Kn+1 )

Xor è l'operazione di addizione bit a bit modulo 2. Il blocco Kn di 48 bit della chiave viene ottenuto tramite la funzione KS : sia n un intero compreso tra 1 e 16, allora

Kn = KS(n,KEY)

che è una selezione permutata dei bit di KEY. Dall' iterazione si ottiene un blocco di pre-output R16L16 il quale è sottoposto alla permutazione P-1

40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31

38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29

36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27

34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

In questo modo il 40-esimo bit di R16L16 diventa il primo, l'ottavo il secondo, fino ad arrivare all' ultimo che prima era il 25-esimo.

[Torna inizio pagina]

3.1.2 Decifratura

Per decifrare si applica lo stesso algoritmo ad un blocco di messaggio cifrato, usando ad ogni iterazione dell' elaborazione di decifratura lo stesso blocco di bit della chiave usata durante la cifratura.

Usando la stessa notazione risulta

Rn-1 = Ln

Ln-1 = Rn xor F(Ln ,Kn)

In questo caso R16L16 è il blocco di input, usando K16 come parte della chiave e L0R0 è il blocco di pre-output, usando K1.

[Torna inizio pagina]

3.2 La funzione di cifratura

La funzione di cifratura F(R,K) si può schematizzare nel seguente modo:

E è una funzione di espansione che riceve un blocco R di 32 bit e restituisce come output un blocco di 48 bit, secondo la seguente tabella:

32 1 2 3 4 5 4 5 6 7 8 9

8 9 10 11 12 13 12 13 14 15 16 17

16 17 18 19 20 21 20 21 22 23 24 25

24 25 26 27 28 29 28 29 30 31 32 1

I 48 bit così ottenuti sono sommati (xor) con i 48 bit di K. La sequenza ottenuta viene divisa in 8 blocchi Bi,ciascuno di 6 bit. Ognuno di questi è l' input di una funzione Si, che restituisce 4 bit come output. I risultati di queste funzioni sono ottenuti tramite tabelle di 4 righe (da 0 a 3) e 16 colonne (da 0 a 15). I valori di queste tabelle sono permutazioni dei numeri esprimibili con 4 bit (quelli restituiti da Si). Vediamo come determinare il valore restituito da Si(Bi) . Il primo ed ultimo bit di Bi rappresentano in base 2 un numero compreso tra 0 e 3, che individua la riga h. I quattro bit centrali rappresentano un valore tra 0 e 15 ed individuano la colonna k. Il valore di Si(Bi) è l'elemento della h-esima riga e k-esima colonna. Le primitive S1,S2,... ,S8 sono

S1

S2

S3

S4

S5

S6

S7

S8

Ad esempio se 011011 è l' input di S1

S1( 011011 ) = 0101 cioè 5

Dalle funzioni Si si ottengono 8 gruppi di 4 bit per un totale di 32 bit, sui quali si esegue la permutazione Pf

Riassumendo per calcolare F(R,K)

B1B2 ..B8 = K xor E(R)

F(R,K) = Pf( S1(B1) S2(B2) ... S8(B8) )

La scelta delle funzioni KS, S1,..,S8 è fondamentale per la robustezza della

cifratura che si ottiene.

[Torna inizio pagina]

3.3 Calcolo della chiavi di cifratura (Kn)

I bit 8,16,..,64 di key sono usati come bit di disparità. PC_1 e PC_2 sono due permutazioni. PC_1 è definita nel seguente modo

Il primo blocco di bit viene preso come C0 ed il secondo come D0. I blocchi Cn e Dn vengono ottenuti rispettivamente da Cn-1 e Dn-1 (n=1..16) tramite shift a sinistra

Iterazione nº 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Nº shift a sinistra 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

Ad esempio C3 e D3 sono ottenuti da C2 e D2 tramite due shift a sinistra, mentre C16 e D16 si ottengono da C15 e D15 con un solo shift.

La permutazione PC_2 è determinata da

14 17 1 24 1 5 3 28 15 6 21 10

23 19 12 4 26 8 16 7 27 20 13 2

41 52 31 37 47 55 30 40 51 45 33 48

44 49 39 56 34 53 46 42 50 36 29 32

Il flusso logico dell' algoritmo DES è:

Una caratteristica dell' algoritmo DES è la proprietà di complementarità: se si prende il complemento (inversione di bit) di un blocco di testo chiaro e il complemento di una chiave di cifratura, il risultato che si ottiene tramite il DES è il complemento del testo cifrato originale. Cioè se y è la codifica di x con chiave k

y = Ek(x)

allora _ _ _

y = Ek(x)

dove le soprallieature indicano la complementazione. Ciò è dovuto alla presenza di due operazioni di XOR, ma non rappresenta comunque una debolezza seria dell' algoritmo DES, in quanto il tempo occorrente per una ricerca esaustiva, nota una coppia testo chiaro-testo cifrato, rimane ancora molto elevato.

Si individuano alcune chiavi, note come chiavi deboli, il cui uso deve essere evitato. Ci sono inoltre chiavi semi-deboli, che sono considerate sempre in coppia e per ognuna di queste gli insiemi di sottochiavi Kn sono identici, ma in sequenza inversa : K1 di una chiave è uguale a K16 dell' altra è così via...

Il risultato della cifratura con una chiave della coppia, seguito dalla decifratura con l'altra chiave è la riproduzione del testo originale.

INDICE