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.





© 2000-2024 pc-facile.com