DES

Il sistema DES cifra una stringa x di 64 bit in una stringa y di ancora 64 bit utilizzando una chiave k di 56 bit. Cioè:

Formalmente possiamo scrivere:

DES: {0,1}⁶⁴×{0,1}⁵⁶®{0,1}⁶⁴

La chiave k in realtà è memorizzata sfruttando 64 bit, dove l'ottavo, il 16-esimo, ... , il 64-esimo, sono i bit di parità per i sette bit precedenti. Possiamo immaginare i 64 bit della chiave k divisi in 8 byte, dove per ognuno di questi l'ottavo bit definisce la parità del byte. Tuttavia concretamente ci sono solo 56 bit su cui può variare la chiave.

La struttura del DES è la seguente:

Dove IP è una permutazione di 64 bit detta permutazione iniziale; le sedici iterazioni che trasformano la stringa in input sono uguali nel senso che la funzione che le realizza è sempre la stessa (vedremo più avanti che l'unica cosa che cambia ad ogni iterazione è la chiave che viene utilizzata); "scambio" effettua uno scambio sulla stringa prodotta come output della 16-esima iterazione, in particolare scambia i 32 bit più a sinistra con i 32 bit più a destra); IP^-1 è la permutazione inversa della permutazione iniziale; la schedulazione delle chiavi, sfruttando la sola chiave k, produce le chiavi k₁, k₂, ..., k₁₆ di 48 bit ciascuna, per le iterazioni da 1 a 16.

Più precisamente l'algoritmo di cifratura procede nel seguente modo:

Passo 1: Sia x un testo in chiaro di 64 bit: l'algoritmo costruisce una stringa binaria x₀ permutando la stringa iniziale mediante la permutazione iniziale fissata IP:

x₀=IP(x)=L₀R₀

dove L₀ e R₀ sono due stringhe binarie che comprendono rispettivamente i primi e gli ultimi 32 bit della stringa originaria x₀.

Passo 2: Effettua 16 iterazioni (detti anche round). Per 1 £ i £ 16 l'input della i-esima iterazione è una stringa di 64 bit divisa in due parti, L_i-1 e R_i-1, ognuna di 32 bit (chiamate rispettivamente parte sinistra e parte destra della stringa). I valori di output L_i e R_i sono prodotti in accordo alla seguente regola:

L_i=R_i-1 e R_i=L_i-1Åf(R_i-1, k_i)

L'operatore Å denota la funzione xor bit a bit delle due stringhe di bit, ed f è una funzione che, data la chiave k_i e la sottostringa R_i-1, produce una stringa lunga 32 bit. Descriveremo f in dettaglio successivamente. k₁, k₂, ..., k₁₆ sono le chiavi prodotte dal processo di schedulazione. All'i-esima iterazione verrà usata la sola chiave k_i.

Passo 3: L'output dell'algoritmo è ottenuto applicando la permutazione IP^-1 a R₁₆L₁₆. Si noti l'ordine inverso delle ultime due stringhe di bit R₁₆ e L₁₆ dovuto allo scambio di 32 bit.

Per maggiori informazioni consultare il sito:

http://udsab.dia.unisa.it/ads.dir/corso-security/www/CORSO-9900/des/index.html