Data Encryption Standard - Descrizione

Cifratura

I dati vengono scomposti in blocchi da 64 bit, a cui viene applicato l'algoritmo. Esso riceve in input i 64 bit del blocco dei dati, i 64 bit della chiave e produce in uscita 64 bit di dati criptati.

Permutazione iniziale

I dati vengono inizialmente permutati attraverso la seguente tabella:

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

Viene quindi costruito un altro blocco da 64 bit dove il primo bit è il bit 58 dell'input, il secondo bit è il bit 50 dell'input, il terzo corrisponde al 42, fino al 64 bit che corrisponde al bit 7 dell'input.
A questa tabella corrisponde una tabella di permutazione inversa che riporta i bit nel posto originale. La tabella inversa viene applicata ai dati prima di essere inviati in output.

Key Schedule

La funzione Key Schedule produce, a partire dalla chiave, 16 blocchi di dati da 48 bit. Sia Key la chiave di 64 bit. Si definisce una funzione KS che ha come input un numero n da 1 a 16 e il valore della chiave Key e in output produce un blocco di dati da 48 bit chiamato K. Dato il numero i, sia Ki = KS(i, Key) l'output relativo prodotto dalla funzione Key Schedule.
Dai 64 bit della chiave vengono scelti 56 bit suddivisi in due blocchi da 28 bit, attraverso la prima permutazione. Gli 8 bit restanti sono scartati, essendo utilizzati solo per il controllo di parità.
Il primo blocco da 28 bit (chiamato C) è costituito dai seguenti bit della chiave:

Permutazione 1: generazione del blocco C

57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36

Quindi il primo bit del blocco C corrisponde al bit 57 della chiave, il secondo al bit 49, il terzo al bit 41 e così fino al bit 28 del blocco C che corrisponde al bit 36 della chiave.
Il secondo blocco da 28 bit (chiamato D) è costituito dai seguenti bit della chiave:

Permutazione 1: generazione del blocco D

63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4

Il primo bit del blocco D corrisponde al bit 63 della chiave, il secondo al bit 55, il terzo al bit 47, fino al bit 28 del blocco D costituito dal bit 4 della chiave.
Una volta ottenuti i due blocchi C e D, viene effettuata per 16 volte una operazione di shift a sinistra di un certo numero di bit e una seconda permutazione che sceglie, dai 56 bit dei blocchi C e D, 48 bit che costituiscono l'output. I blocchi C e D, nella successiva iterazione subiscono un nuovo shift a sinistra e vengono selezionati 48 bit per l'output successivo. Le iterazioni totali sono 16 e ciascuna produce un output. Si indica con Ki l'output ottenuto dai blocchi Ci e Di nella i-esima iterazione.
La seconda permutazione crea il blocco K scegliendo i seguenti 48 bit dai blocchi C e D:

Permutazione 2

14 17 11 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 numero degli shift a sinistra effettuati indipendentemente sui blocchi C e D varia in base all'iterazione: la seguente tabella stabilisce il numero di bit da spostare in funzione dell'iterazione.

Numero di shift a sinistra

Iterazione numero bit
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
des_ks2.png

Funzione di cifratura f

La funzione f viene utilizzata per l'elaborazione dei dati. Riceve in input un blocco R da 32 bit e l'output della funzione Key Schedule Ki.
Innanzitutto il blocco R viene espanso attraverso una tabella di selezione che genera un blocco espanso da 48 bit. Viene utilizzato l'operazione xor tra questo blocco e l'output della funzione Key Schedule Ki, anch'esso da 48 bit.
Il risultato dell'operazione (48 bit) viene suddiviso in 8 blocchi da 6 bit ciascuno che vengono inviati a delle funzioni S1, S2, …, S16 che producono in output un blocco da 4 bit. Gli 8 blocchi da 4 bit generati vengono inviati ad una funzione di permutazione che produce un output da 32 bit.

Espansione del blocco R da 32 bit in 48 bit

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

Nell'espansione del blocco R, il primo bit dell'output corrisponde al bit 32 del blocco R, il secondo al primo bit, il terzo al secondo bit, fino al bit 48 dell'output che corrisponde al primo bit del blocco R.
I 48 bit espansi vengono suddivisi in 8 blocchi da 6 bit. Ogni blocco viene inviato ad una funzione S diversa, che produce in output un blocco da 4 bit. Le funzioni S vengono anche chiamate substitution boxes o S-boxes.
Ogni funzione S è costituita da una tabella. L'output viene generato in questo modo: siano b1, b2, b3, b4, b5, b6 i 6 bit in input. La tabella è costituita da 4 linee e 16 colonne. I bit b1 e b6 vengono considerati assieme come un unico numero a 2 bit, compreso tra 0 e 3, che viene usato per individuare una riga i. Gli altri bit da b2 a b5 vengono considerati come un unico numero a 4 bit, compreso tra 0 e 15 che viene usato per individuare una colonna j.
L'output è uguale al valore della tabella in corrispondenza dell'elemento alla riga i e colonna j. Tutti i valori nella tabella sono compresi tra 0 e 16, quindi il risultato sarà composto da 4 bit.
Di seguito è mostrata la tabella per la funzione S1:

S-Box 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
riga 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
riga 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
riga 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
riga 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Ad esempio, si suppone di avere in input il blocco da 6 bit 011011. Allora la riga sarà determinata dal primo e l'ultimo bit, ovvero 01 = 1. La colonna corrisponde al valore dei bit al centro, dal secondo al quinto, ovvero il valore 1101 = 13. Il valore di output sarà quello in corrispondenza della prima riga e della tredicesima colonna, ovvero 5. L'output sarà 0101 = 5.

La funzione di permutazione viene effettuata attraverso la seguente tabella:

Permutazione

16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25

La funzione di permutazione riceve in input 32 bit e produce un output di 32 bit tale che il primo bit dell'output sia il bit 16 dell'input, il secondo sia il bit 7, il terzo sia il bit 20, fino al bit 32 dell'output corrispondente al bit 25 dell'input.

des_sbox2.png

Dopo la permutazione iniziale, il blocco di dati da 64 bit viene suddiviso in due blocchi da 32 bit L e R. Nella prima delle 16 permutazioni, si generano altri due blocchi L' e R' in questo modo:
Il nuovo blocco L' è uguale al vecchio blocco R
L' = R
Il nuovo blocco R' è il risultato dell'operazione XOR tra il vecchio blocco L e l'output della funzione di cifratura f. Essa riceve in input il vecchio blocco R e il blocco K generato dalla funzione Key Schedule
R' = L xor f(R, K)
Nella iterazione i-esima, viene calcolato il valore di Ki tramite la funzione di Key Schedule e inviato assieme il blocco R alla funzione f il cui valore verrà combinato tramite l'operatore xor con il blocco L. L'output genererà il nuovo blocco R'.

des2.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License