|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.DES History
Hide minor edits - Show changes to output
Added line 57:
Changed line 59 from:
Come in Feistel, la decrittazione avviene eseguendo le fasi con le chiavi generate all'incontrario. to:
Come in Feistel, la decrittazione avviene eseguendo le fasi con le chiavi generate al contrario.
Changed lines 106-108 from:
Questo segmento di testo cifrato viene utilizzato anche per cifrare il segmento successivo. Prendo ancora il vettore '''IV''', ma stavolta, al posto degli '''s''' bit meno significativi di '''IV''', metto il primo segmento di testo cifrato che ho prodotto nel paragrafo qui sopra.
E poi vado avanti: DESsifico, ottengo 64 bit, di cui i primi '''s''' diventano il secondo segmento di testo cifrato, e che andranno anche a nutrire IV per la cifratura del prossimo segmento etc. to:
Questo segmento di testo cifrato viene utilizzato anche per cifrare il segmento successivo. Prendo ancora il vettore '''IV''', elimino gli '''s''' bit più significativi e aggiungo in coda gli '''s''' bit cifrati (in sostanza compio uno scorrimento a sinistra di '''s''' bit, aggiungendo il testo cifrato precedente).
E poi vado avanti: DESsifico il nuovo '''IV''', ottengo 64 bit, di cui i primi '''s''' diventano il secondo segmento di testo cifrato, e che andranno anche a nutrire IV per la cifratura del prossimo segmento etc.
Added lines 8-9:
Changed lines 50-56 from:
to:
\\
!!!!Immagine chiarificatrice
''Sito internet con immagini sul funzionamento di DES : '' http://www.amagri.it/crittologia/crittografia/algoritmi_crittografici/des/analisi_algoritmo.htm
\\
Changed line 148 from:
Siccome la chiave di 56 bit è [[ben minore di 64 * 2'^64^' bit -> CifrariABlocchi]], allora più blocchi porteranno allo stesso risultato, quando li si cifra: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato. to:
Siccome la chiave di 56 bit è [[ben minore di 64 * 2'^64^' bit -> CifrariABlocchi]], allora ci saranno chiavi diverse che, applicate allo stesso blocco, porteranno allo stesso risultato, sia in cifratura che in decifratura: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato.
Changed line 148 from:
Siccome la chiave di 56 bit è ben minore di 64 * 2'^64^' bit, allora più blocchi porteranno allo stesso risultato, quando li si cifra: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato. to:
Siccome la chiave di 56 bit è [[ben minore di 64 * 2'^64^' bit -> CifrariABlocchi]], allora più blocchi porteranno allo stesso risultato, quando li si cifra: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato.
Changed line 148 from:
Siccome la chiave di 56 bit è ben minore di 64 * 2^'64'^ bit, allora più blocchi porteranno allo stesso risultato, quando li si cifra: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato. to:
Siccome la chiave di 56 bit è ben minore di 64 * 2'^64^' bit, allora più blocchi porteranno allo stesso risultato, quando li si cifra: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato.
Added lines 122-148:
!! Double DES
È una modalità di utilizzo di DES, che prevede una doppia cifratura. In pratica:
E'_k2_'(E'_k1_'(M))
che vuol dire che cifro M con la prima chiave, e cifro il cifrato con la seconda chiave.
Il flusso delle informazioni è il seguente:
x -> DES -> y -> DES -> z
Utilizzando 2 chiavi, i bit totali che compongono la chiave devono quindi essere 56 * 2 = 112. Ci si aspetterebbe quindi che la crittanalisi di Double DES sia pesante il doppio rispetto a quella di DES, che si aggira, per la forza bruta, intorno a 2'^55^'.\\
E invece no: adesso vedremo che un attacco a forza bruta a Double DES richiede uno sforzo asintotico a 2'^56^', che rispetto al 2'^55^' del DES normale non giustifica affatto la chiave lunga il doppio.
!!!Attacco meet in the middle
x -> DES -> y -> DES -> z
Si tratta di un attacco '''known plaintext''', ovvero l'attaccante conosce il testo in chiaro ed anche il suo cifrato corrispondente: '''x''' e '''z''' in questo schema.
Si procede così:
* dato '''x''', calcolo tutte le possibili '''crittografie''' usando tutte le 2'^56^' chiavi possibili, e le salvo in una tabella
* dato '''z''', calcolo tutte le possibili '''decrittografie''' e le salvo in una tabella
* confronto le 2 tabelle per vedere le voci che coincidono
* scopro la password usando un'altra coppia di testo in chiaro / testo cifrato
Quello che si fa in pratica è provare a crittare in tutti i modi possibili il testo in chiaro '''x''' di cui dispongo. Crittare in tutti i modi possibili vuol dire provare a crittare '''x''' con tutte le 2'^56^' chiavi.\\
Poi, devo provare a decrittare '''z''', anche lui con tutte le 2'^56^' chiavi possibili. In pratica, cerco di arrivare ad '''y''' sia da sinistra che da destra.
Siccome la chiave di 56 bit è ben minore di 64 * 2^'64'^ bit, allora più blocchi porteranno allo stesso risultato, quando li si cifra: ecco perché ci sarà più di una coincidenza, e occorre una seconda coppia di testo in chiaro / testo cifrato.
Changed line 6 from:
%warning%%yellow%'''Mancano le IMMAGINI, che renderanno il tutto molto più chiaro (si spera...) to:
%warning%%white%'''Mancano le IMMAGINI, che renderanno il tutto molto più chiaro (si spera...)'''
Added lines 6-7:
%warning%%yellow%'''Mancano le IMMAGINI, che renderanno il tutto molto più chiaro (si spera...) Changed lines 78-121 from:
to:
!!Modi di utilizzo di DES
Il DES non si usa sempre allo stesso modo, ma sono stati inventati modi diversi per utilizzarlo.
!!!ECB = Electronic CodeBook
Si divide il testo in blocchi di 64 bit, e ogni blocco viene DESsificato con la stessa chiave. Se la lunghezza del testo non è multipla di 64 bit, si aggiungono bit per pareggiare.
Questo vuole anche dire che 2 blocchi uguali vengono cifrati allo stesso modo.
!!!CBC = Cipher Block Chaining
L'inpute che viene DESsificato non è il blocco in chiaro, ma è il prodotto dello '''XOR''' tra il blocco corrente e il blocco cifrato precedente.
Quando si cifra il primo blocco, ovviamente, non si ha a disposizione un blocco cifrato precedente. Si usa allora un '''vettore di inizializzazione''', detto '''IV''', che deve quindi fare parte della chiave.
!!!CFB = Cipher FeedBack
Anche qui non uso blocchi di 64 bit di testo in chiaro, ma uso un altro concetto detto '''segmento''' composto da un numero '''s''' di bit, con s < 64.
Anche qui si parte con un '''IV''' di 64 bit, che viene DESsificato e che produce un blocco cifrato di 64 bit.
Di questo blocco cifrato, prendo gli '''s''' bit più significativi, e ne faccio lo '''XOR''' con i primi '''s''' bit del testo in chiaro. Il prodotto di questo XOR è il primo '''segmento''' di testo cifrato, lungo quindi '''s''' bit.
Questo segmento di testo cifrato viene utilizzato anche per cifrare il segmento successivo. Prendo ancora il vettore '''IV''', ma stavolta, al posto degli '''s''' bit meno significativi di '''IV''', metto il primo segmento di testo cifrato che ho prodotto nel paragrafo qui sopra.
E poi vado avanti: DESsifico, ottengo 64 bit, di cui i primi '''s''' diventano il secondo segmento di testo cifrato, e che andranno anche a nutrire IV per la cifratura del prossimo segmento etc.
In genere si usa '''s = 8 bit''', così ho che 1 segmento corrisponde ad un byte.
!!!OFB = Output FeedBack
È uguale a CFB, con una differenza: gli '''s''' bit che userò al posto degli '''s''' bit meno significativi di '''IV''' nella prossima cifratura, NON sono il prodotto dello XOR tra gli '''s''' bit più significativi della DESsificazione precedente e il primo segmento di testo in chiaro, bensì sono direttamente gli '''s''' bit più significativi della DESsificazione.
Questo serve per non propagare errori di trasmissione.
!!!Counter
Questa è la modalità più interessante. C'è un contatore, che ad ogni passo deve produrre un valore a 64 bit.
'''QUESTO''' valore a 64 bit viene DESsificato, e al risultato della DESsificazione si '''XOR'''ano i 64 bit del testo in chiaro.
Questo procedimento ha degli ottimi vantaggi:
* Per decifrare un blocco, NON mi serve il blocco precedente. Posso quindi eseguire in parallelo le decifrature di diversi blocchi, sfruttando le CPU parallele etc.
* Se conosco prima il contatore, posso PRECALCOLARE l'output del DES per tot posizioni del contatore, così che quando più tardi mi arriva il blocco, devo solo fare lo XOR
* Posso accedere direttamente al blocco che voglio, senza dover dipendere dalla decrittatura di tutti i blocchi precedenti
* È sicuro quanto gli altri metodi
* È anche più semplice
Il contatore può essere realizzato in qualsiasi modo, purché sia un valore a 64 bit.
Added lines 1-78:
(:title Crittografia - DES:)
%titolo%''':: Crittografia - DES ::'''
[[Torna alla pagina di Crittografia -> Crittografia]]
Il DES è un crittosistema basato sulla rete di [[Feistel -> CifrariABlocchi]]. Usa un blocco di '''64 bit''' e una chiave di '''56 bit''', ed è abbastanza complicato!
In complesso i passaggi sono i seguenti:
# '''permutazione iniziale''' = si permuta il blocco di 64 bit
# '''16 fasi''' in stile Feistel
# '''preoutput''' = si scambiano la metà di SX e quella di DX
# '''permutazione finale''' = è l'inverso di quella iniziale.
!!!Permutazione iniziale
Scambia di posto i 64 bit del blocco, ed è una funzione invertibile. Infatti, la permutazione finale è l'inverso di quella iniziale.
!!!Fase
La '''sottochiave''' è composta da '''48 bit''', ricavati - vedremo poi - dalla chiave di 56 bit.
Il destino del blocco '''R''' è il seguente:
* viene espanso da 32 bit (metà di 64) a 48 bit, e viene messo in '''XOR''' con la chiave K.
* quello che esce viene dato in pasto ad una '''funzione di sostituzione''' che ottiene, dai 48 bit, ancora '''32bit'''.
* si permuta ancora secondo una tabella.
Poi, l'output di questo lavorìo viene '''XOR'''ato con il blocco L.
In pratica, la funzione '''F''' della rete di Feistel diviene in DES la sequenza di operazioni qui sopra.
!!!!Funzione di sostituzione
La funzione di sostituzione di cui abbiamo parlato cui sopra è realizzata tramite '''8 S-Box'''.
Ogni S-Box prende in input '''6 bit''' e ne restituisce '''4'''. Ecco perché passa da 48 bit a 32.
Una S-Box è composta da '''4 righe''' e '''16 colonne''', e '''non''' è una funzione lineare.
Il primo e l'ultimo bit dei 6 in ingresso scelgono la '''riga''', i 4 in mezzo scelgono la '''colonna'''. La cella della S-Box tramite riga e colonna contiene un numero a 4 bit (0 - 16).
!!!!Generazione della chiave
Abbiamo visto che si parte da una chiave a 56 bit, ma la sottochiave è di 48.
In realtà non è proprio così: si prende una chiave di 64 bit, e un bit ogni 8 viene scartato, ottenendone così 56. Questi 56 bit vengono divisi in '''2 parti''', ciascuna di '''28 bit'''.
Vengono fatte 2 copie di queste mezze chiavi, e ciascuna copia segue una strada diversa:
# la prima copia di mezze chiavi viene sottoposta a '''scorrimento circolare''' a sx o dx, di 1 o 2 bit, e viene mandata alla fase successiva
# la seconda copia viene sottoposta ad una tabella, che la riduce da 56 a 48 bit, e la fa entrare nella '''funzione di sostituzione'''
!!!Decrittazione
Come in Feistel, la decrittazione avviene eseguendo le fasi con le chiavi generate all'incontrario.
!!!Effetto valanga
Tutto questo macello produce un '''effetto valanga''', che vuol dire che da pochi bit di differenza - nel testo in chiaro o nella chiave - si producono molti bit di differenza nel testo cifrato.
!!!Numero di fasi
In generale si usano tante fasi perché, anche se una fase è relativamente debole, metterle una dopo l'altra aumenta notevolmente la robustezza dell'intero algoritmo. Nel caso di DES, le 16 fasi sono in grado di vanificare gli attacchi di '''analisi differenziale''' con known plain text.
!!!La funzione F
La funzione F serve per aumentare la [[confusione -> CifrariABlocchi]]. Deve essere il meno lineare possibile, sia che usi le S-Box sia che non le usi.
I criteri sono due: '''SAC''' e '''BIC'''.
* '''SAC''' = Strict Avalanche Criterion: se cambio un bit in input, i bit in output devono avere probabilità almeno 1/2 di cambiare
* '''BIC''' = Bit Independence Criterion: se cambio 1 bit in input, i bit di output devono cambiare l'uno indipendentemente dall'altro
La '''chiave''' deve contribuire anch'essa a soddisfare BIC e SAC.
!!!Le S-Box
Lo scopo di vita delle S-Box è quello di dare un aspetto il più casuale possibile al blocco in input. Se sono grosse, funzionano meglio, ma sono anche molto più difficili da realizzare e da implementare correttamente.
È stato inventato il criterio '''GA''' = Guaranteed Avalanche. Una S-Box soddisfa il '''GA di ordine γ''' se, per ogni bit in input che cambia, ci sono γ bit in output che cambiano. Un GA con γ tra 2 e 5 è considerato buono per la '''diffusione'''.
Ci sono 4 modi per inventare S-Box:
* generarle casualmente
* generarle casualmente, ma sottoporle a test
* crearle manualmente
* crearle matematicamente seguendo qualche algoritmo
''...continua...''
[[Torna alla pagina di Crittografia -> Crittografia]]
|
|
