Introduzione alla crittografia simmetrica

Archivio articoli e recensioni

Introduzione alla crittografia simmetrica

Messaggioda ikir » mer ago 23, 2006 10:44 am

Pubblicato su iksnetv3 il 25 06/01/20 05 12:51 by sHaDy

Introduzione alla crittografia simmetrica


01 Introduzione

Chiunque ha minime conoscenze di crittografia sa bene che la crittografia
moderna (ovvero la crittografia digitale) si divide in due grosse aree:

1. Algoritmi simmetrici o a chiave privata
2. Algoritmi asimmetrici o a chiave pubblica

Con questo doc non voglio scatenare guerre di religione su quale tipo di
crittografia sia più efficiente ma voglio solamente soffermarmi sugli algoritmi simmetrici (probabilmente i più semplici da comprendere) spiegandone in modo più o meno dettagliato le caratteristiche ed il funzionamento con particolare attenzione ai due algoritmi simmetrici più conosciuti (e badate bene che conosciuto è diverso da sicuro come avrò modo di ribadire in seguito) ovvero DES e IDEA. Buona lettura.


02 Parentesi 1: Matematica di Boole e operatori

Prima di proseguire nel nostro cammino mi vedo costretto ad aprire una piccola parentesi sulla matematica di Boole e il sistema binario. Do per scontato che tutti sappiano cosa sia il sistema binario (o in base 2), quello che mi interessa spiegare, infatti, sono gli operatori logici ovvero gli operatori che si applicano a simboli binari (assieme agli operatori comuni come + , - ecc..).


1. NOT

NOT inverte i valori binari. In pratica se applichiamo NOT a 0 esso diventerà 1 e viceversa.

NOT 1 = 0
NOT 0 = 1
NOT 11001 = 00110
NOT 01010 = 10101


2. OR

OR viene applicato tra due valori e restituisce come risultato 1 a meno che
entrambi i valori in ingresso siano 0.

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

Se abbiamo sequenze lunghe si esegue da cifra a cifra:

1010001 OR
1110101 =
----------
1110101

Se i due valori non hanno la stessa lunghezza basta aggiungere degli zeri
a sinistra:

101010 OR 1100 = 101010 OR 001100

101010 OR
001100 =
---------
101110


3. XOR

Lo XOR o OR esclusivo è simile all'OR ma con la differenza che restituisce 0 anche nel caso in cui entrambi i valori siano entrambi 1.

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Per numeri a più cifre si procede come con l'OR:

1100011100 XOR
0000111001 =
-------------
1100100101

Ovviamente dato un numero binario 'x':

x XOR x = 0


4. NOR

Il NOR è l'opposto dell'OR.

0 NOR 0 = 1
0 NOR 1 = 0
1 NOR 0 = 0
1 NOR 1 = 0


5. AND

AND da come risultato 0 a meno che entrambi i valori siano 1.

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

11001010 AND
00011000 =
------------
00001000


6. NAND

E' il contrario dell'AND: restituisce sempre 1 a meno che entrambi i valori
non siano 1.

0 NAND 0 = 1
0 NAND 1 = 1
1 NAND 0 = 1
1 NAND 1 = 0


7. ROR e ROL

ROR fa scorrere di un tot di posizioni a destra il bit di una sequenza (se i
bit escono dalla sequenza rientrano dalla parte opposta). ROL fa la stessa
cosa ma a sinistra. ROR e ROL hanno 2 parametri: la stringa di bit e lo
spostamento da effettuare.

ROR 110010, 2 = 101100
ROL 001010, 3 = 010001


8. SHIFT

E' un operatore analogo al precedente ma questa volta i bit che escono
vengono persi e dalla parte opposta entrano degli 0. Si può SHIFTARE a destra
(SHR) o a sinistra (SHL).

SHR 110011, 3 = 000110
SHL 001010, 4 = 100000

03 Parentesi 2: Operazioni modulari

Eh sì, non abbiamo ancora finito con la matematica. Ma non temete, questo
è l'ultimo paragrafo dedicato a tale argomento. Un Modulo (Mod) restituisce
il resto di una divisione:

15 Mod 4 = 3

In quanto 3 è il resto di 15/4. Preciso che lavoriamo con numeri interi e
non decimali perciò 15/4 è uguale a 3 e non a 3.75. In matematica il modulo serve se ci troviamo di fronte a insiemi limitati. Ad esempio mettiamo di avere un insieme di numeri interi da 0 a 100 (quindi con elementi non infiniti). In un insieme simile non possiamo certo svolgere liberamente tutte le normali operazioni che svolgeremo nell'insieme dei numeri interi ma guardate qua:

60 + 60 = 120

120 non è un elemento facente parte dell'insieme quindi ci troviamo di
fronte a un problema ed è a questo punto che ci vengono incontro le operazioni
modulari. Le operazioni modulari sono operazioni modulari, sottrazioni
modulari, moltiplicazioni modulari ecc... e si indicano come le normali
operazioni ma con un cerchietto attorno: ad esempio le addizioni modulari
sono indicate con (+), le moltiplicazioni con (*) ecc... Ma come funzionano?
Il funzionamento è analogo a quello delle normali operazioni ma questa il
risultato è in modulo M dove M è l'elemento limite dell' insieme. In pratica
nel nostro esempio di prima:

60 + 60 = 120

ma

60 (+) 60 = (60 + 60) Mod 100 = 20

04 Algoritmi simmetrici

Per dare una definizione molto grezza di crittografia simmetrica si può
affermare che essa comprende quegli algoritmi nei quali, per crittare,
viene utilizzata una sola chiave. Perciò anche per Cesare, Vigènere,
Playfair ecc... si parla di crittografia simmetrica. Da questo capiamo
che anche per i moderni algoritmi digitali la sostanza è la stessa anche
se questi ultimi compiono centinaia di operazioni su uno stesso blocco di
testo. Uno schema del funzionamento della crittografia simmetrica può
essere il seguente:

Codice: Seleziona tutto

           +---------+           Canale sicuro
           | CHIAVE |------------------------------------------.
           +---------+                                                     |
            |                                                                  |
            '------>+-----------+                                       |
                      |Crittazione|----->Messaggio cifrato    |
 Messaggio--->+-----------+                      |                |
                                                               |                |
             +--------------+                             |                |
             |Decrittazione|<-------Invio--------'               |
             +--------------+<----------------------------------'
                    |                               
                    |                               
                    '---->Messaggio



Per spiegare lo schema facciamo un esempio con Alice, Bob ed Eva. Alice
cifra il messaggio con una certa chiave e invia il testo cifrato a Bob il
quale ha precedentemente ricevuto la chiave. Da questa spiegazione è facile
dedurre come si riveli necessario un canale di comunicazione sicuro per l'invio
della chiave altrimenti per Eva sarebbe sufficiente intercettare la chiave oltre
al testo cifrato. Appurato questo viene spontaneo chiedersi che me ne faccio
della crittografia se dispongo di un canale sicuro. Il problema è che questi
canali sicuri nella maggior parte dei casi non sono adatti all'invio di una
mole di dati superiore a quella di una chiave. Inoltre è proprio lo scambio
della chiave a rappresentare il problema maggiore della crittografia simmetrica
visto che trovare un canale che presenti un'alta sicurezza non è cosa semplice.

05 Rete di Feistel

La classe di cifrari Feistel comprende la maggior parte dei cifrari simmetrici
odierni. Questi cifrari sono basati sulle reti Feistel la cui struttura è
illustrata qui sotto:
Codice: Seleziona tutto
    +--------+
    | CHIAVE |-----------------------------------.
    +--------+                                             |
                                                     ALGORITMO DI
         +--------------------------+          GENERAZIONE
      .--| BLOCCO PRINCIPALE |                  |
      |  +--------------------------+                 |
      |                               |                         |
  +------+                 +------+                     |     
  | L[0] |                   |  R[0] |<--f()<-Sottochiave(0)          Round 1
  +------+                 +------+                    |
      |                       /          |                     |
      |                     /            |                     |
      '-------XOR---------------'                     |
                   \    /                                    |
                    \  /                                     |
                      /                                      |
                    /  \                                     |
                   /    \                                    |
   +------+   /       \     +------+                 |
    | L[1] |--'           '---| R[1] |<--f()-Sottochiave(1)          Round 2
   +------+                  +------+
      |                         /     |
      |                        /      |
      '-------XOR-------------' 
                    \    /
                     \  /
                       /
                     /  \


                   [  ...  ]


   +------+                    +------+
   | L[n] |                      | R[n] |
   +------+                    +------+
          \                         /
           \                      /
         +-------------------+
         | TESTO CIFRATO |
         +-------------------+


sulla matematica di Boole e il sistema binario. Do per scontato che tutti
sappiano cosa sia Per prima cosa viene scelta una chiave la quale genera un
dato numero n di sottochiavi. Il blocco di testo in chiaro che di norma ha
grandezza 2n (è quindi un numero pari) viene diviso in due sottoblocchi
chiamati L (left) e R (right). Si procede per iterazioni ed ogni iterazione è
detta round ed in ognuno di essi viene adoperata una differente sottochiave.
In ogni round R viene processato da una funzione f() che accetta in input
anche la sottochiave e viene fatto uno XOR tra l'output della funzione ed L.
Il risultato dello XOR diventerà la R e la R di partenza diventerà la L del
round successivo. Il procedimento fin qui illustrato viene ripetuto n volte
dopo di chè i sottoblocchi risultanti L[n] ed R[n] vengono messi assieme e si
ottiene il testo crittografato. Riassumiamo quanto detto:

Testo in chiaro = L[0] & R[0]

R[0] = L[1]
R[1] = f(R[0], key[0]) XOR L[0]
...
R[n-1] = L[n]
R[n] = f(R[n-1], key[n-1]) XOR L[n-1]
Testo cifrato = L[n] & R[n]

06 DES

L'algoritmo di crittografia simmetrica DES (Data Enctyption Standard) fu
realizzato nei laboratori dell'IBM nel 1975 ed è diventato molto presto uno
standard nelle operazioni commerciali che richiedono l'impiego di algoritmi
crittografici. E' un cifrario di Feistel a blocchi (ovvero che si basa essenzialmente su trasposizioni e sostituzioni su blocchi di testo). La fama
di questo algoritmo (anche chi non si occupa in alcun modo di crittografia ne avrà sentito parlare) potrebbe portare a pensare che sia estremamente sicuro ed inviolabile ma non è così anche perchè è diventato ormai vecchiotto. Il DES è stato utilizzato con successo in tutto il globo fino al 1998 anno in cui l'Electronic Frontier Foundation e la Cryptography Research completarono la costruzione di un elaboratore parallelo del costo di 250.000 dollari dedicato esclusivamente alla forzatura del DES. Attraverso questa macchina è stato possibile violare la sicurezza del DES attraverso un bruteforce in meno di 56 ore (il che è veramente poco). Per questo motivo, nonostante il DES sia ancora in voga, chiunque abbia un minimo di esperienza con crittografia e crittanalisi tende a sconsigliare l'utilizzo di tale algoritmo per operazioni che richiedono un grado di sicurezza elevato.

Il DES utilizza chiavi di 64 bit suddivisa in 8 bytes anche se la chiave
effettiva è di 56 bit visto che l'ultimo bit di ciascuno degli 8 bytes è un
parity bit la cui funzione è intercettare e interrompere eventuali errori di
trasmissione. Il DES opera su blocchi da 64 bit e si basa sull'utilizzo ciclico
di 16 reti di Feistel più due permutazioni (una iniziale ed una finale).
Riassumendo:

Numero di round = 16
Lunghezza chiave = 64 bit
Grandezza dei blocchi = 64 bit

<Parentesi: le permutazioni>

Una permutazione consiste nello scambiare l'ordine dei vari bit. Ad esempio:

Valore dei bit: 1 1 0 0 0 1
Permutazione: 6 3 4 1 2 5
Valore dopo
la Permutazione: 1 0 0 1 1 0

<Fine parentesi>

Dicevamo della generazione delle sottochiavi: il primo passo che il DES
compie è fare la permutazione della chiave di 64 bit scartando automaticamente
i bit di parità.

Prima della permutazione
Codice: Seleziona tutto
                                    +----+
  01 02 03 04 05 06 07 | 08 |
  09 10 11 12 13 14 15 | 16 |
  17 18 19 20 21 22 23 | 24 |
  25 26 27 28 29 30 31 | 32 |
  33 34 35 36 37 38 39 | 40 |----> Bit scartati
  41 42 43 44 45 46 47 | 48 |
  49 50 51 52 53 54 55 | 56 |
  57 58 59 60 61 62 63 | 64 |
                                    +----+

Dopo la permutazione
Codice: Seleziona tutto
  57 49 41 33 25 17 09
  01 58 50 42 34 26 18
  10 02 59 51 43 35 27
  19 11 03 60 52 44 36
  63 55 47 39 31 23 15
  07 62 54 46 38 30 22
  14 06 61 53 45 37 29
  21 13 05 28 20 12 04


A questo punto la chiave che è divenuta di 56 bit viene divisa in due parti
che chiameremo S[0] e D[0]:

Codice: Seleziona tutto
S]0] 57 49 41 33 25 17 09
       01 58 50 42 34 26 18
       10 02 59 51 43 35 27
       19 11 03 60 52 44 36

         
D[0] 63 55 47 39 31 23 15
        07 62 54 46 38 30 22
        14 06 61 53 45 37 29
        21 13 05 28 20 12 04

Da questo momento per ottenere le 16 sottochiavi bisogna effettuare 16 round (iterazioni). L'iterazione corrente la indicheremo con i. All'inizio
ovviamente avremo che:

i = 1

Ora spostiamo (o se preferite shiftiamo) a sinistra sia D che S di tot
posizioni a seconda dell'iterazione [i] in cui ci troviamo, secondo la
tabella che segue:
Codice: Seleziona tutto
Iterazioni   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
-------------------------------------------------------------
Left Shifts  1 1 2 2 2 2 2 2 1   2   2  2   2   2   2   1

Concateniamo nuovamente D[i] e S[i] ottenendo nuovamente 56 bit. Ora la nuova chiave è sottoposta a una nuova permutazione che prende 48 bit dei 56 e precisamente i bit di posizione:
Codice: Seleziona tutto
 14 17 11 24 01 05
 03 28 15 06 21 10
 23 19 12 04 26 08
 16 07 27 20 13 02
 41 52 31 37 47 55
 30 40 51 45 33 48
 44 49 39 56 34 53
 46 42 50 36 29 32

Mettiamo insieme i bit in quest'ordine per formare la nostra sottochiave
dell'iterazione i che chiameremo k[i]. Ovviamente a seconda ell'iterazione avremo:

i = 1 -> k[1]
i = 2 -> k[2]
i = 3 -> k[3]
i = 4 -> k[4]

E così via.

Ora che sappiamo come il DES genera le sottochiavi vediamo come elabora i blocchi di dati. Come già detto il DES lavora su blocchi di testo o più in generale di dati di 64 bit (se un blocco di dati ha una grandezza minore viene trasformato in un blocco da 64 bit). Innanzitutto il blocco di testoviene sottoposto a una permutazione detta permutazione iniziale (IP):
Codice: Seleziona tutto
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07

In questo modo il cinquantottesimo bit del blocco di dati in ingresso dopo
la permutazione prenderà la prima posizione e così via (questo per quelli
che non avessero ancora compreso bene il funzionamento di queste permutazioni). Ora si divide il blocco permutato in due parti che chiameremo L[0] e R[0]):
Codice: Seleziona tutto
L(0) 58 50 42 34 26 18 10 02
       60 52 44 36 28 20 12 04
       62 54 46 38 30 22 14 06
       64 56 48 40 32 24 16 08
       
R(0) 57 49 41 33 25 17  9 01
       59 51 43 35 27 19 11 03
       61 53 45 37 29 21 13 05
       63 55 47 39 31 23 15 07

Ora dobbiamo applicare le 16 sottochiavi prima trovate al blocco di dati
partendo da i = 1.

Si esegue una permutazione espansa sul sottoblocco R[i]. Una permutazione espansa è simile a una permutazione (i bit vengono traslati di posto) ma in più alcuni vengono ripetuti. Dai 32 bit di R[i] si passa così a 48 bit. La permutazione espansa la indicheremo con E.

R prima della permutazione (32bit)

57 49 41 33 25 17 9 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07

Permutazione espansa


32 01 02 03 04 05
04 05 06 07 08 09
08 09 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 01

Per farvi capire meglio come funzionano le permutazioni espanse vi faccio
notare come, ad esempio, il trentaduesimo bit di R[i] compare 2 volte dopo la permutazione:
Codice: Seleziona tutto
     57 49 41 33 25 17  9 01
     59 51 43 35 27 19 11 03
     61 53 45 37 29 21 13 05
                                       +--+
     63 55 47 39 31 23 15 |07|---------.
                                       +--+           |
                                          |              |
       .----------------------------------------'
       |                                  |         
    +--+                              |
    |32|01 02 03 04 05       |
    +--+                              |
     04 05 06 07 08 09       |
     08 09 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| 01    |
                         +--+        |
                           |            |
                           '----------'

Dopo la permutazione espansa, i dati ottenuti vengono combinati mediante
una funzione di somma binaria (XOR con quelli relativi della chiave
appositamente generata per il ciclo corrente:

E(R[i-1]) XOR key[i]

Ora dividiamo il risultato ottenuto in 8 blocchi di 6 bit ciascuno che indicheremo con B[j]che andrà da B[1]a B[8]. A questo punto entrano in
gioco le Substitution Boxes (o S-Boxes). Una S-Box è una funzione che
opera accettando in ingresso un blocchetto di bit di lunghezza fissata (ed eventualmente, un parametro extra sempre di lunghezza fissa), e restituisce in output un altro blocco di bit di lunghezza fissata, scelto tra un insieme di output interno alla S-Box. Se vogliamo possiamo definire le S-Box come delle tabella di sostituzione. Nel DES ci sono 8 S-Box che indicheremo come S[j]. Le 8 scatole sono queste:
Codice: Seleziona tutto
  S[1]

  14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07
  00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08
  04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00
  15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13

  S[2]

  15 01 08 14 06 11 03 04 09 07 02 13 12 00 05 10
  03 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05
  00 14 07 11 10 04 13 01 05 08 12 06 09 03 02 15
  13 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09

  S[3]

  10 00 09 14 06 03 15 05 01 13 12 07 11 04 02 08
  13 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01
  13 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07
  01 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12

  S[4]

  07 13 14 03 00 06 09 10 01 02 08 05 11 12 04 15
  13 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09
  10 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04
  03 15 00 06 10 01 13 08 09 04 05 11 12 07 02 14

  S[5]

  02 12 04 01 07 10 11 06 08 05 03 15 13 00 14 09
  14 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06
  04 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14
  11 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03

  S[6]

  12 01 10 15 09 02 06 08 00 13 03 04 14 07 05 11
  10 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08
  09 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06
  04 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13

  S[7]

  04 11 02 14 15 00 08 13 03 12 09 07 05 10 06 01
  13 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06
  01 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02
  06 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12

  S[8]

  13 02 08 04 06 15 11 01 10 09 03 14 05 00 12 07
  01 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02
  07 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08
  02 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11


Il funzionamento di queste S-Box è il seguente: tu gli dici il numero di
riga(da 0 a 3) e di colonna (da 0 a 15) e loro ti restituiscono il valore individuato da queste coordinate. Come vedete in ogni cella c'è un valore di 4 bit e alcuni valori si ripetono.

Prima di proseguire devo introdurre anche un'altra funzione: la funzione Z(). Questa funzione accetta come parametro B[j] e restituisce un valore a 4 bit sfruttando le S-Box precedentemente introdotte: dapprima prende il valore a 6 bit in ingresso poi prende il primo e l'ultimo bit di questo valore e li considera come un unico valore a 2 bit chiamato m mentre i restanti 4 li considera come un valore a 4 bit chiamato n. Infine passa alla S-Box m e n come coordinate(rispettivamente riga m e colonna n)e restituisce il valore ottenuto da queste coordinate. Esempio:

B[1] = 011101 = 28
m = 01 = 1
n = 1110 = 14
Codice: Seleziona tutto
         
Coordinate(m,n)---->Vengono passate a S(1)
                                       |
                                       |
                                       |
                        Otteniamo il valore 00

Dunque eravamo farmi al punto in cui avevamo gli otto blocchi di 6 bit ciascuno B[j]. Ora c'è un sottociclo per cui per ogni valore di j a partire da j = 1 B[j] viene passata alla funzione Z() descritta in precedenza. A questo punto:

B[j] = Z(B[j])

ora ho 8 sottoblocchi B[j] da 4 bit l'uno che andrò a riunire in un unico
blocco B da 32 bit. Ora applico a B il modulo di permutazione P qui sotto
indicato:
Codice: Seleziona tutto
  16 07 20 21
  29 12 28 17
  01 15 23 26
  05 18 31 10
  02 08 24 14
  32 27 03 09
  19 13 30 06
  22 11 04 25

Effettuo uno XOR tra il blocco così ottenuto e la metà sinistra del testo prodotto dal precedente round ottenendo la nuova metà destra:

R[i] = B XOR L[i-1]

La metà destra del round precedente invece diventa la metà sinistra del
nuovo round:

L[i] = R[i-1]

Una volta completati tutti i 16 round si riuniscono le 2 metà finali L[16] e R[16]. Il blocco così ottenuto viene processato dalla permutazione finale
(PF):
Codice: Seleziona tutto
  40 08 48 16 56 24 64 32
  39 07 47 15 55 23 63 31
  38 06 46 14 54 22 62 30
  37 05 45 13 53 21 61 29
  36 04 44 12 52 20 60 28
  35 03 43 11 51 19 59 27
  34 02 42 10 50 18 58 26
  33 01 41  9 49 17 57 25

Questa permutazione è, fondamentalmente, la IP invertita.

Quello che si ottiene dopo la PF è il testo cifrato. Per quanto riguarda la
decifratura il processo è il medesimo ma con le sottochiavi invertite partendo dalla k(16) e arrivando alla k(1)).


07 3DES

Il 3DES o DES triplo rappresenta l'evoluzione del DES e si basa sulla
ripetizione del DES per 3 volte con un sistema di Encryption Decryption
Encryption (EDE). Il principale vantaggio sta nella lunghezza della chiave:
mentre il DES usa una chiave a 56 bit il 3DES ne una 2:

56 + 56 = 112bit

Il funzionamento è il seguente: prima il testo viene cifrato tramite la prima
chiave con poi viene decifrato con la seconda chiave e infine cifrato
nuovamente con la prima:
Codice: Seleziona tutto
 +-----------------+           +-----------+
 | Testo in chiaro |------->| Cifratura |<---- Chiave 1
 +-----------------+            |   (DES)   |     
                                      +-----------+
                                              |
                                              |
                                              |
                                      +------------+
                                       |Decifratura|<---- Chiave 2
                                       |   (DES)    |
                                      +------------+
                                              |
                                              |
                                              |
                                       +-----------+
                                        | Cifratura |<---- Chiave 1
                                        |   (DES)   |
                                       +-----------+

Non bisogna pensare che con il secondo passaggio (la decifratura con la
chiave 2) si ritorni al testo in chiaro poiché nel primo il testo
viene crittato con la chiave 1 quindi, anche il passaggio 2 critta
il messaggio. Questo algoritmo è, ovviamente, 3 volte più lento del DES.


08 IDEA

Inventato del 1991 l'IDEA (International Data Enctyption Algorithm) è un
cifrario simmetrico considerato abbastanza sicuro. l'IDEA come il DES è
un cifrario a blocchi che lavora con chiavi di 128 bit su blocchi di
testo di 64 bit. Compie 8 round e non 16 come nel DES. L'IDEA non rientra
nei cifrari Feistel anche se ha molte caratteristiche simili. L'IDEA usa
ben 52 sottochiavi da 16 bit e non fa uso di S-Box. Le operazioni di cui
fa uso sono:

1.XOR
2.Moltiplicazione modulare
3.Addizione modulare

Passiamo alla spiegazione dell'algoritmo partendo dalla generazione
delle sottochiavi. Per prima cosa la chiave di 128 bit viene divisa in 8
sottochiavi da 16 bit. Ora si fa un ROL a destra sulla chiave ottenendo
una nuova chiave da 128 bit che verrà divisa in 8 chiavi da 16 bit Si
continua con questo procedimento fino a quando non si sono generate tutte le 52 sottochiavi che indicheremo con key[i] dove i è l'iterazione corrente.

Passiamo ora alla crittazione vera e propria: il blocco di dati da 64
bit viene diviso in 4 blocchi da 16 bit che chiameremo A,B,C,D. Ora
prendiamo in considerazione le 8 iterazioni: in ogni round avvengono
le seguenti operazioni:

01. Moltiplico A per key[6*i + 1]
02. Sommo a B key[6*i + 2]
03. Sommo a C key[6*i + 3]
04. Moltiplico D per key[6*i + 4]
05. Pongo E = A XOR C
06. Pongo F = B XOR D
07. Moltiplico E per key[6*i + 5]
08. Sommo E ad F
09. Moltiplico F per key[6*i + 6]
10. Aggiungo F ad E
11. Modifico A e C XORANDO i loro valori con F
12. Modifico B e D XORANDO i loro valori con E
13. Scambio le posizioni di B e C

(Ricordo che le operazioni di somma e moltiplicazione sono modulari)

Nell'ottavo round, però, il passaggio 13 non è presente. Se facciamo
i calcoli, però, notiamo che abbiamo usato solo 48 chiavi e non 52. Le restanti vengono adoperate per la trasformazione finale durante la quale viene moltiplicata A per key[49], a B viene sommata la key[50], a C viene
sommata la key[51] e infine C viene moltiplicata per key[52]. Ora A,B,C,D
vengono nuovamente concatenati e otteniamo il nostro chypertext. Per quanto riguarda la decrittazione il percorso è lo stesso ma le sottochiavi
sono generate in modo differente. Per le prime 4 chiavi avviene come
illustrato qui di seguito:

key_dec[1] = key[49]^(-1)
key_dec[2] = ~key[49]
key_dec[3] = ~key[49]
key_dec[4] = key[52]^(-1)

Il simbolo ~ indica l'inverso più uno. Ad esempio:

~1110001 = (NOT 1110001) + 1 = 0001110 + 1 = 1111

Le chiavi successive seguono il seguente andamento:

key_dec[5] = key[47]
key_dec[6] = key[48]
key_dec[7] = key[43]^(-1)
key_dec[8] = ~key[45]
key_dec[9] = ~key[44]
key_dec[10] = key[46]^(-1)

Un ultima cosa: abbiamo detto che l'IDEA usa tre operazioni: XOR, (+) e (*).
Le prime due sono tranquillamente invertibili mentre per la moltiplicazione
modulare ci sono un po' di problemi: se io moltiplico un numero per 0
ottengo come risultato 0 e questa operazione non è invertibile. La moltiplicazione modulare modulo M non è invertibile, a parte il caso in cui i due fattori siano primi relativi di M. Noi abbiamo sequenza di 16 bit che ci permettono di rappresentare numeri da 0 a 65536. Come facciamo? Intanto notiamo che 65537 è un numero primo. Se M è un numero primo allora la moltiplicazione modulare è sempre invertibile a meno che i due fattori nonsiano multipli di M (non è il nostro caso). Nell'IDEA lo 0 viene consideratoequivalente al 65536 e in questo modo l'operazione diventa di M = 63357 che è un numero primo.

http://shadyhack.altervista.org
Avatar utente
ikir

Admin
 
Messaggi: 10202
Iscritto il: mer gen 08, 2003 7:33 pm
Località: SYS:Prefs/

Torna a Articoli

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti