Introduzione alla cifratura con DES

Novembre 2016

DES la cifratura a chiave segreta

Il 15 maggio 1973 il NBS (National Bureau of Standards, oggi chiamato NIST - National Institute of Standards and Technology) ha lanciato una gara nel Federal Register (l'equivalente negli USA della Gazzetta Ufficiale in Italia) per la creazione di un algoritmo di cifratura che rispondesse ai criteri seguenti:

Possedere un alto livello di sicurezza legato ad una chiave di piccole dimensioni che serva da cifratura e da decifratura;

Essere comprensibile;

Non dipendere dalla confidenzialità dell'algoritmo;

Essere adattabile ed economico;

Essere efficace e esportabile.

Alla fine del 1974, IBM propone «Lucifer», che, grazie alla NSA (National Security Agency), venne modificato il 23 novembre 1976 per dare vita al DES (Data Encryption Standard). Il DES è stato finalmente approvato nel 1978 dall'NBS. Il DES fu messo in norma dall'ANSI (American National Standard Institute) con il nome di ANSI X3.92, più conosciuto sotto la denominazione DEA (Data Encryption Algorithm).

Principio del DES

Si tratta di un sistema di cifratura simmetrica per blocchi di 64 bit, di cui 8 bit (un byte) servono da test di parità (per verificare l'integrità della chiave). Ogni bit di parità della chiave (1 ogni 8 bit) serve a testare un dei bit della chiave per parità dispari, cioè ogni bit di parità è sistemato in modo da avere un numero dispari di '1' nel gruppo degli 8 bit al quale appartiene. La chiave possiede quindi una lunghezza «utile» di 5 bit, il che significa che solo 56 bit servono in realtà all'algoritmo.

L'algoritmo consiste nell'effettuare delle combinazioni, delle sostituzioni e delle permutazioni tra il testo da cifrare e la chiave, facendo in modo che le operazioni possano farsi nei due sensi (per la decifratura). La combinazione tra sostituzioni e permutazioni è detta codice prodotto. La chiave è codificata a 64 bit e formata da 16 blocchi di 4 bit, generalmente abbreviati k1 a k16. Dato che «solo» 56 bit servono effettivamente a codificare, possono esisterne 256 (sia 7.2*1016) chiavi diverse.

L'algoritmo di DES

Le grandi linee dell'algoritmo sono le seguenti:

Frazionamento del testo in blocchi da 64 bit (8 byte);

Permutazione iniziale dei blocchi;

Divisione dei blocchi in due parti, sinistra e destra, detti S e D;

Tappe di permutazione e di sostituzione ripetute 16 volte (dette round);

Incollare le parti sinistra e destra poi permutazione iniziale inversa:

algoritmo di DES

Frazionamento del testo


Permutazione iniziale

In un primo tempo, ogni bit di un blocco è sottoposto alla permutazione iniziale, che può essere rappresentata dalla matrice di permutazione iniziale (sigla IP) seguente:


IP
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157


Questa matrice di permutazione indica, percorrendo la matrice da sinistra a destra poi dall'alto in basso, che il 58esimo bit del blocco del testo da 64 bit si trova in prima posizione, il 50esimo in seconda posizione e così via.

Scissione in blocchi da 32 bit

Una volta che la permutazione iniziale è realizzata, il blocco di 64 bit è scisso in due blocchi da 32 bit, siglati rispettivamente S e D (per sinistra e destra, con la sigla anglosassone L e R per Left and Right). Si nota S0 e D0 lo stato iniziale di questi due blocchi:


S0
585042342618102
605244362820124
625446383022146
645648403224168



D0
57494133251791
595143352719113
615345372921135
635547393123157



È interessante osservare che S0 contiene tutti i bit che possiedono una posizione pari nel messaggio iniziale, mentre D0contiene i bit di posizione dispari.

Round

I blocchi Sn e Dn sono sottoposti ad una serie di trasformazioni interattive dette round, esplicitate in questo schema, e i cui dettagli vengono forniti più in basso:
round

Funzione d'espansione

I 32 bit del blocco D0 sono estesi a 48 bit grazie ad una tabella (matrice) detta tabella d'espansione (sigla E), nella quale i 48 bit sono mischiati e 16 fra loro sono duplicati:


E
3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321



Così, l'ultimo bit di D0 (cioè il 7imobit del blocco d'origine) diventa il primo, il primo diventa il secondo, ecc. In più, i bit 1,4,5,8,9,12,13,16,17,20,21,24,25,28 e 29 di D0 (rispettivamente 57, 33, 25, l, 59, 35, 27, 3, 6l, 37, 29, 5, 63, 39, 31 e 7 del blocco d'origine) sono duplicati e disseminati nella matrice.

O esclusivo con la chiave

La matrice che risulta dai 48 bit è detta D'0 oppure E[D0]. L'algoritmo DES esegue quindi un O esclusivo tra la prima chiave K1 e E[D0]. Il risultato di questo O esclusivo è una matrice di 48 bit che chiameremo D0 per comodità (non si tratta dello stesso D0 dell'inizio).

Funzione di sostituzione

D0 e in seguito scisso in 8 blocchi da 6 bit, sigla D0i. Ciascuno di questi blocchi passa per delle funzioni di selezione (dette talvolta scatole di sostituzione o funzioni di compressione), siglate generalmente S i. I primi e gli ultimi bit di ogni D0i determinano (in codice binario) la linea della funzione di selezione, gli altri bit (rispettivamente2, 3, 4 e 5) determinano la colonna. Dato che la sezione della linea si fa su due bit, vi sono 4 possibilità (0,1,2,3). Dato che la sezione della linea si fa su 4 bit, vi sono 16 possibilità (da 0 a 15). Grazie a questa informazione, la funzione di selezione "seleziona" un valore codificato su 4 bit. Ecco la prima funzione di sostituzione, rappresentata da una matrice di 4 per 16:


S1
0123456789101112131415
01441312151183106125907
10157414213110612119538
24114813621115129731050
31512824917511314100613



Sia D01 uguale a 101110. I primi e gli ultimi bit danno 10, cioè 2 in codice binario. I bit 2, 3, 4 e 5 danno 0111, ovvero 7 in binario. Il risultato della funzione di selezione è quindi il valore situato nelle linea n° 2, nella colonna n° 7. Si tratta del valore 11, sia in binario 111. Ciascuno degli 8 blocchi di 6 bit è passato nella funzione di selezione corrispondente, che da a ognuno 8 valori di 4 bit ciascuno. Ecco le altre funzioni di selezione:


S2
0123456789101112131415
01518146113497213120510
13134715281412011069115
20147111041315812693215
31381013154211671205149



S3
0123456789101112131415
01009146315511312711428
11370934610285141211151
21364981530111212510147
31101306987415143115212




S4
0123456789101112131415
07131430691012851112415
11381156150347212110149
21069012117131513145284
331506101138 94511127214



S5
0123456789101112131415
02124171011685315130149
11411212471315015103986
24211110137815912563014
31181271142136150910453



S6
0123456789101112131415
01211015926801334147511
11015427129561131401138
29141552812370410113116
34321295151011141760813



S7
0123456789101112131415
04112141508133129751061
11301174911014351221586
21411131237141015680592
36111381410795015142312



S8
0123456789101112131415
01328461511110931450127
11151381037412561101492
17114191214206101315358
12114741081315129035611



Ogni blocco di 6 bit è poi sostituito con un blocco di 4 bit. Questi bit sono raggruppati per formare un blocco da 32 bit.

Permutazione

Il blocco di 32 bit ottenuto è infine sottoposto ad una permutazione P di cui vediamo la tabella:


P
167202129122817
11523265183110
282414322739
19133062211425

O esclusivo

L'insieme di questi risultati in uscita da P è sottoposto ad un O esclusivo con S0 di partenza (come indicato nel primo schema) per dare D1, mentre lo D0 iniziale da S1.

iterazione

L'insieme delle tappe precedenti (round) e reiterato 16 volte.

Permutazione iniziale inversa

Alla fine delle iterazioni, i due blocchi S16 e D16sono "reincollati", poi sottomessi alla permutazione iniziale inversa:


IP-1
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725



Il risultato in uscita è un testo codificato a 64 bit.

Generazione delle chiavi

Visto che l'algoritmo di DES presentato qui sopra è pubblico, tutta la sicurezza è basata sulla complessità delle chiavi di cifratura. L'algoritmo qui sotto mostra come ottenere, partendo da una chiave a 64 bit (composta da 64 caratteri alfanumerici qualunque), 8 chiavi diversificate di 48 bit da utilizzare nell'algoritmo di DES:

algoritmo di generazione di chiavi DES



In un primo tempo i bit di parità della chiave sono eliminati per ottenere una chiave di una lunghezza utile di 56 bit. La prima tappa consiste in una permutazione siglata CP-1 con la seguente matrice:


CP-1
57494133251791585042342618
10259514335271911360524436
635547393123157625446383022
1466153453729211352820124



Questa matrice può infatti essere scritta sotto forma di due matrici Si e Di (per sinistra e destra) composta ciascuna da 28 bit:


Si
5749413325179
1585042342618
1025951433527
1911360524436



Di
63554739312315
7625446383022
1466153453729
211352820124



Osserviamo come S0 e D0 il risultato di questa prima permutazione. Questi due blocchi subiscono poi una rotazione verso sinistra, in maniera che i bit in seconda posizione vadano in prima, quelli in terza in seconda, ecc. I bit in prima posizione passano invece all'ultima.

I due blocchi da 28 bit sono in seguito raggruppati in un blocco da 56 bit. Questo passa da una permutazione, detta CP-2, fornendo un blocco di 48 bit, che rappresenta la chiave Ki:


CP-2
14171124153281562110
23191242681672720132
415231374755304051453348
444939563453464250362932



Alcune iterazioni sull'algoritmo permettono di dare le 16 chiavi K1 a K16 usate nell'algoritmo di DES.

LS
124681012141517192123252728

TDES, un'alternativa al DES

Nel 1990 Eli Biham e Adi Shamir hanno messo a punto la criptanalisi differenziale che ricerca delle COPIE di testi in chiaro e di testi cifrati. Questo metodo funziona fino a un numero di round inferiore a 15, e nell'algoritmo qui sopra vi sono 16 round. In ogni caso, anche se in una chiave di 56 bit vi sono molteplici possibilità, numerosi processori permettono di calcolare più di 106 chiavi al secondo, così, se utilizzate parallelamente su un grande numero di terminali, danno la possibilità ad un grande organismo (uno stato ad esempio) di trovare la chiave corretta.

Una soluzione a breve termine può consistere nell'incatenare tre codificazioni DES attraverso due chiavi da 56 bit (il che equivale ad una chiave di 112 bit). Questo processo è chiamato Triplo DES, sigla TDES (a volte 3DEs o 3-DES):

Triple DES - 3DES



Il TDES permette di aumentare significativamente la sicurezza del DES, ma ha come inconveniente maggiore di chiedere più risorse per la cifratura e la decifratura. Distinguiamo solitamente diversi tipi di codificazione triplo DES:

DES-EEE3 : 3 codificazioni DES con 3 chiavi differenti;

DES-EDE3: una chiave diversa per ognuna delle 3 operazioni DES (cifratura, decifratura, cifratura);

DES-EEE2 e DES-EDE2: una chiave diversa per la seconda operazione (decifratura).


Nel 1997 il NIST lanciò una nuova consultazione di progetto per l'elaborazione dell'AES(Advanced Encryption Standard), un algoritmo di cifratura destinato a sostituire il DES. Il sistema di cifratura DES fu aggiornato ogni 5 anni. Nel 2000 all'ultima versione, dopo un processo di valutazione durato 3 anni, l'algoritmo elaborato congiuntamente da due candidati belgi, Vincent Rijmen e Joan Daemen fu scelto come nuovo standard dal NIST. Questo nuovo algoritmo battezzato RIJNDAEL dai suoi inventori, sostituirà da quel momento il DES.

Ulteriori informazioni

http://csrc.nist.gov/encryption/tkencryption.html - Specifiche degli algoritmi di DES di TDES e dell'AES (site du NIST) ;

RFC 2420 The PPP Triple-DES Encryption Protocol (3DESE)

Potrebbe anche interessarti :

Introduction to encryption with DES
Introduction to encryption with DES
Introducción al cifrado mediante DES
Introducción al cifrado mediante DES
Introduction au chiffrement avec DES
Introduction au chiffrement avec DES
Introdução à codificação DES
Introdução à codificação DES
Il documento intitolato « Introduzione alla cifratura con DES » da CCM (it.ccm.net) è reso disponibile sotto i termini della licenza Creative Commons. È possibile copiare, modificare delle copie di questa pagina, nelle condizioni previste dalla licenza, finché questa nota appaia chiaramente.