Criptografia Simmetrica [Guide Security

pc-facile.com

http://www.pc-facile.com/guide/criptografia_simmetrica/192.htm

Generale: hydra 20 Dicembre 04 @ 00:01 am

10. DES

Il DES è un algoritmo a blocchi, cioè agisce sul testo in chiaro in blocchi di 64 bit e restituisce testo cifrato in blocchi della stessa dimensione. Il DES risulta essere una permutazione dei 264 possibili arrangiamenti dei 64 bit, ognuno dei quali può essere 0 o 1. Ogni blocco è diviso in due blocchi di 32 bit ciascuno, un blocco sinistro L e un blocco destro R. (Questa divisione è utilizzata solo in alcune operazioni).

Esempio:
Fai che M sia il testo in chiaro
M = 0123456789ABCDEF

Dove M è un numero esadecimale (base 16). Riscrivendo M in formato binario otteniamo:
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
L = 0000 0001 0010 0011 0100 0101 0110 0111
R = 1000 1001 1010 1011 1100 1101 1110 1111

Il DES opera su blocchi di 64 bit usando una chiave di 56 bit. La chiave è in realtà memorizzata a 64 bit, ma l'ottavo bit di ogni byte non viene utilizzato. Noi li utilizzeremo tutti, ma come vedrete gli otto ottavi bit della chiave verranno eliminati quando creiamo le sottochiavi.

Esempio:
Fai che K sia la chiave esadecimale
K = 133457799BBCDFF1

Riscrivendo in formato binario:
K = 0001 0011 0011 0100 0101 0111 0111 1001 1001 1011 1011 1100 1101 1111 1111 0001

Il DES procede come segue:

1. Crea 16 sottochiavi ognuna di 48 bit
La chiave a 64 bit è permutata secondo la tabella PC-1. Visto che il primo numero della tabella è '57' questo significa che il 57° bit della chiave originale K diventa il primo bit della chiave permutata K+. Il 49° bit della chiave originale diventa il secondo della chiave permutata e così via. Notare che solo 56 bit della chiave originale vengono utilizzati nella chiave permutata.

PC-1

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
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

Esempio:
Dalla chiave originale a 64 bit
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

Otteniamo la permutazione a 56 bit:
K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

Poi dividiamo la chiave nelle due metà, destra e sinistra, C0 e D0, dove ogni metà è di 28 bit.
Esempio:
Dalla chiave permutata K+, otteniamo
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111

Dove C0 e D0 sono definiti e noi creiamo 16 blocchi Cn e Dn, 1 <= n <= 16. Ogni coppia di blocchi Cn e Dn è formata dalla coppia precedente Cn-1 e Dn-1, rispettivamente, per n = 1, 2, ..., 16, utilizzando il seguente schema di shift a sinistra del blocco precedente. Per effettuare uno shift a sinistra muovere ogni bit di una posizione a sinistra eccetto per il primo bit che viene messo in coda in fondo al blocco.

Numero Numero di shift
Iterazione a sinistra

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

Questo signigfica, ad esempio, che C3 e D3 sono ottenuti da C2 e D2, rispettivamente, da due shift verso sinistra, e C16 e D16 sono ottenuti da C15 e D15, rispettivamente, da uno shift verso sinistra.
Esempio:
Dalla coppia originale C0 e D0 otteniamo:

C0 = 1111000011001100101010101111
D0 = 0101010101100110011110001111

C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110

C2 = 1100001100110010101010111111
D2 = 0101010110011001111000111101

C3 = 0000110011001010101011111111
D3 = 0101011001100111100011110101

C4 = 0011001100101010101111111100
D4 = 0101100110011110001111010101

C5 = 1100110010101010111111110000
D5 = 0110011001111000111101010101

C6 = 0011001010101011111111000011
D6 = 1001100111100011110101010101

C7 = 1100101010101111111100001100
D7 = 0110011110001111010101010110

C8 = 0010101010111111110000110011
D8 = 1001111000111101010101011001

C9 = 0101010101111111100001100110
D9 = 0011110001111010101010110011

C10 = 0101010111111110000110011001
D10 = 1111000111101010101011001100

C11 = 0101011111111000011001100101
D11 = 1100011110101010101100110011

C12 = 0101111111100001100110010101
D12 = 0001111010101010110011001111

C13 = 0111111110000110011001010101
D13 = 0111101010101011001100111100

C14 = 1111111000011001100101010101
D14 = 1110101010101100110011110001

C15 = 1111100001100110010101010111
D15 = 1010101010110011001111000111

C16 = 1111000011001100101010101111
D16 = 0101010101100110011110001111

Adesso formiamo le chiavi Kn, per 1 <= n <= 16, applicando la seguente tabella delle permutazioni su ognuna delle paia di chiavi concatenate CnDn. Ogni paio è composta da 56 bit ma PC-2 ne usa soltanto 48 di questi.

PC-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

Di conseguenza il 1° bit di Kn è il 14° bit di CnDn, te il 2° il 17° e così via dicendo fino al 48° bit di Kn che è il 32° bit di CnDn.
Esempio:
Per la prima chiave abbiamo:
C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110

Che, dopo la permutazione PC-2, diventa:
K1 = 000110 110000 001011 101111 111111 000111 000001 110010

Per le altre chiavi abbiamo

K2 = 011110 011010 111011 011001 110110 111100 100111 100101
K3 = 010101 011111 110010 001010 010000 101100 111110 011001
K4 = 011100 101010 110111 010110 110110 110011 010100 011101
K5 = 011111 001110 110000 000111 111010 110101 001110 101000
K6 = 011000 111010 010100 111110 010100 000111 101100 101111
K7 = 111011 001000 010010 110111 111101 100001 100010 111100
K8 = 111101 111000 101000 111010 110000 010011 101111 111011
K9 = 111000 001101 101111 101011 111011 011110 011110 000001
K10 = 101100 011111 001101 000111 101110 100100 011001 001111
K11 = 001000 010101 111111 010011 110111 101101 001110 000110
K12 = 011101 010111 000111 110101 100101 000110 011111 101001
K13 = 100101 111100 010111 010001 111110 101011 101001 000001
K14 = 010111 110100 001110 110111 111100 101110 011100 111010
K15 = 101111 111001 000110 001101 001111 010011 111100 001010
K16 = 110010 110011 110110 001011 000011 100001 011111 110101

2. Codifica del messaggio
Avviene una permutazione iniziale IP di 64 bit del messaggio M. Questo ricombina i bit secondo la tabella che segue.

IP

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

Esempio:
Applicando la permutazione iniziale al testo M, otteniamo
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

Qui il 58° bit di M è "1", che diventa il 1° bit di IP. Il 50° bit di M è "1", che diventa il 2° bit di IP. Il 7° bit di M è "0", che diventa l'ultimo bit di IP.
Poi dividiamo il blocco permutato IP in una metà sinistra L0 di 32 bit, e una metà destra R0 di 32 bit.
Esempio:
Da IP, otteniamo che L0 e R0

L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0 = 1111 0000 1010 1010 1111 0000 1010 1010

Adesso procediamo a 16 iterazioni, 1 <= n <= 16, usando la funzione f che opera su due blocchi - un blocco dati di 32 bit e una chiave Kn di 48 bit - per ottenere un blocco di 32 bit. Per ogni n da 1 a 16 calcoliamo:
Ln = Rn-1
Rn = Ln-1 + f(Rn-1,Kn)

Questo risulta in un blocco finale, n = 16, di L16R16. In altre parole, in ogni iterazione prendiamo i 32 bit di destra del precedente risultato e li usiamo come i 32 bit di sinistra dell'iterazione in corse. Per ottenere i 32 bit di destra dell'iterazione in corso procediamo ad un'addizione XOR dei 32 bit di sinistra dell'iterazione precedente con il calcolo di f.
Esempio:
Per n = 1, abbiamo

K1 = 000110 110000 001011 101111 111111 000111 000001 110010
L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010
R1 = L0 + f(R0,K1)

Rimane da spiegare come opera la funzione f.
Per calcolare f, prima espandiamo ogni blocco Rn-1 da 32 bit a 48 bit. Questo è ottenuto utilizzando una tabella di selezione che ripete alcuni bit in Rn-1. Denomineremo l'utilizzo di questa tablle la funzione E. Quindi E(Rn-1) ha un input di blocchi di 32 bit e un output di blocchi di 48 bit.

Tabella di selezione E

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

Esempio:
Calcoliamo E(R0) da R0 nel modo seguente:
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101

(Nota: ogni blocco di 4 bit originali è stato espanso a 6 bit.)
Il passaggio seguente di f è un'addizione XOR tra l'output di E(Rn-1) e la chiave Kn:
Kn + E(Rn-1)

Esempio:
Per K1 , E(R0), abbiamo
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
K1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111.

Non abbiamo finito di calcolare la funzione f. Fino a questo punto abbiamo espanso Rn-1 da 32 bit a 48 bit usando la taballa di selezione e operando un'addizione XOR tra il risultato e la chiave Kn. Abbiamo adesso 48 bit, o otto gruppi di 6 bit. Faremo qualcosa di strano con ognuno di questi gruppi di 6 bit: li useremo come indirizzi in tablle chiamate "S boxes".
Ogni gruppo di 6 bit ci fornirà un indirizzo in una diversa S box.
All'indirizzo indicato ci sarà un gruppo di 4 bit: questi sostituiranno i sei originali. Il risultato sarà che gli otto gruppi di 6 bit saranno trasformati in otto gruppi di 4 bit per un totale di 32 bit.

Scriviamo il risultato precedente, di 48 bit, in questo formato:
Kn + E(Rn-1) = B1B2B3B4B5B6B7B8
Dove ogni Bi è un gruppo di 6 bit. Calcoliamo
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
Dove Si(Bi) si riferisce all'output della i° S box.
La tabella che determina S1 è mostrata qui sotto:

S1

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

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

Se S1 è la funzione definita in questa tabella e B è il blocco di 6 bit, allora S1(B) è calcolato nel modo che segue:
I primi e gli ultimi bit di B rappresentano in base 2 un numero decimale tra 0 e 3 (binario tra 00 e 11). Questo numero è i. I 4 bit centrali di B rappresentano in base 2 un numero decimale tra 0 e 15 (binario tra 0000 e 1111). Questo numero è j. Cerca nella tabella il numero nella i° riga e j° colonna. E' un numero tra 0 e 15 ed è rappresentato da un blocco di 4 bit. Questo blocco è l'output S1(B) di S1 per l'input B.
Esempio:
Dato un blocco di input B = 011011

Il primo bit "0" e l'ultimo bit "1" combinati formano "01": cioè indicano la riga 1.
I quattro bit centrali "1101" sono l'equvalente del numero decimale 13: cioè indicano la colonna 13.
La riga 1 e colonna 13 indicano il numero 5 (binario 0101).
Quindi S1(011011) = 0101

Le tabelle che definiscono le funzioni S1,...,S8 sono le seguenti:

S1

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

S2

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

S3

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

S4

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

S5

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

S6

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

S7

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

S8

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

Esempio:
Per il primo round otteniamo come output delle 8 S boxes:

K1 + E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111

L'ultima fase nel calcolo di f è quello di fare una permutazione P dell'output delle S boxes per ottenre il valore finale di f:

f = P(S1(B1)S2(B2)...S8(B8))

La permutazione P è definita nella tabella seguente.
P da un output di 32 bit da un input a 32 bit permutando i bit dell'input.

P

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

Esempio:
Dall'output delle otto S boxes:
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111

Otteniamo

f = 0010 0011 0100 1010 1010 1001 1011 1011
R1 = L0 + f(R0 , K1 )
= 1100 1100 0000 0000 1100 1100 1111 1111
+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100

Nel round successivo avremo L2 = R1, che è il blocco ache abbiamo calcolatoe dobbiamo calcolare R2 = L1 + f(R1, K2), e così via per 16 round (iterazioni). Alla fine del sedicesimo roundavremo il blocco L16 e R16. Invertiamo l'ordine dei due blocchi in un blocco a 64 bit R16L16

E infine applichiamo la permutazione finale IP-1 definita dalla tabella seguente:

IP-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

Esempio:
Al sedicesimo round di queste permutazioni otteniamo
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1010 0100 1100 1101 1001 1001 0101

Invertiamo l'ordine dei due blocchi e applichiamo la permutazione finale su
R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100

IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101

Che in formato esadecimale è:
85E813540F0AB405.

Quindi:
M = 0123456789ABCDEF
C = 85E813540F0AB405

La decriptazione è semplicemente l'inverso della criptazione seguendo i passi spiegati sopra ma invertendo l'ordine in cui sono applicate le chiavi.