:: Crittografia - Lezione del 6 marzo 2008 ::
Torna alla pagina di Crittografia
La macchina Enigma
La macchina Enigma è stata inventata nei primi anni del 1900, e basa il suo funzionamento su dei rotori.
Ogni rotore ha due lati, e sui lati sono segnate le 26 lettere dell'alfabeto. All'interno del rotore ci sono dei collegamenti elettrici che vanno da una lettera di un lato ad una lettera di un altro lato.
Ci sono tre di questi rotori, in fila, così che la corrente elettrica che parte dalla tastiera della macchina Enigma entra nel primo rotore nella lettera appropriata, attraversa i cavi del primo rotore fino alla seconda faccia, cambiando lettera, entra nel secondo rotore etc. fino ad uscire dal terzo rotore.
Ci sono state anche versioni con più rotori, ma il funzionamento è lo stesso.
Ma lasciamo stare i dettagli tecnici, che potete trovare un po' ovunque.
La cosa interessante è che il primo rotore ruota ad ogni pressione di un tasto sulla tastiera. Dopo aver fatto un giro completo (ovvero dopo 26 tasti premuti), esso fa compiere un passo al secondo rotore. Dopo 26 passi del secondo rotore, il terzo ne compie uno. (In realtà il funzionamento era leggermente diverso, ma non importa).
Questo vuol dire che ho 26 * 26 * 26 = 17576 alfabeti cifranti diversi, perché ho tre dischi con 26 lettere ciascuno. Ad ogni pressione di un tasto l'alfabeto cifrante muta.
La macchina Enigma veniva configurata mettendo i rotori in un certo ordine (ad esempio, il rotore 1 in posizione 3, il rotore 5 in posizione 1 e così via). Poi, ogni rotore veniva ruotato così da non cominciare con la lettera A, ma con un'altra lettera scelta da chi voleva crittare il messaggio (anche qui non entro nei dettagli storici).
Riassumendo:
- 3 rotori di 26 lettere ciascuno: 26 * 26 * 26 = 17576
- 3 rotori in 3 posizioni relative: 3! = 6 combinazioni
- scambiatore: inverto a caso 12 lettere
TOTALE: 10 milioni di miliardi di chiavi.
Ogni 17576 lettere premute, si tornava comunque all'alfabeto cifrante che aveva cifrato la prima lettera, ma ovviamente i messaggi trasmessi durante la guerra erano molto meno lunghi, non si inviavano dei libri interi, e quindi non c'era pericolo di ripetizione della stessa chiave all'interno di un messaggio.
Per poter tentare un attacco statistico basato sulla frequenza delle lettere, mi servono almeno 50 lettere cifrate con lo stesso alfabeto. Abbiamo appena visto che con Enigma lo stesso alfabeto si ripete dopo 17576 caratteri. Quindi, per avere 50 lettere con lo stesso alfabeto, devo avere un testo lungo almeno 50 * 17576 = 878800 caratteri. Tantino.
One-Time Pad
Questo è il cifrario perfetto.
Se è già stato inventato, noi che cosa studiamo a fare crittografia?
Il fatto è che è tanto valido quanto scomodo, ed ora vedremo perché.
Consiste nell'avere un messaggio cifrato con una chiave casuale lunga tanto quanto il messaggio, e per ogni messaggio diverso genero una chiave casuale diversa.
Se rispetto queste regole, nessuno riuscirà mai a capire che cosa sto dicendo.
Supponiamo di avere il testo in chiaro "messaggiosegreto".
Lo cifro con la chiave casuale LZQPSLEJTUNSZMTA, e ottengo il testo cifrato XDIHSRKRHMRYQQMO.
La cosa interessante è che dal testo cifrato XDIHSRKRHMRYQQMO posso risalire a qualsiasi testo in chiaro!
Infatti, se voglio decrittare, usando la chiave XQFQORRNOTRMQDNG avrei:
Testo cifrato: XDIHSRKRHMRYQQMO
Chiave: XQFQORRNOTRMQDNG
Testo in chiaro: ANDREATETTAMANZI
Il testo in chiaro è perfettamente plausibile, in italiano. Ciò vuol dire che non posso risalire al testo originale, perché una qualsiasi altra password potrebbe darmi un testo plausibile in italiano, ma anche in qualsiasi altra lingua.
Il problema è che se devo trasmettere una chiave lunga tanto quanto il messaggio, in modo parimenti segreto, allora tanto valeva inviare il messaggio stesso in modo segreto.
Poi, se uso la stessa chiave per più di un messaggio, allora posso cominciare ad attaccare i testi cifrati.
Ciò vuol dire che, anche se dal punto di vista teorico è stato dimostrato essere il cifrario perfetto, dal punto di vista pratico non lo è affatto. Anzi, la crittografia moderna cerca di ricavare cifrature difficili partendo da chiavi compatte, che sono più facilmente trasmissibili.
Cenni di probabilità
Cerchiamo ora di dare una veste matematica ai concetti di crittografia che abbiamo visto sinora.
La probabilità è la misura del grado di plausibilità di un'affermazione.
Un'affermazione è un evento, una proposizione verificabile.
La definizione classica di probabilità è N / M, dove N sono i casi favorevoli, ed M i casi possibili, che si devono escludere l'un l'altro. La probabilità che tirando 1 dado esca un 3, è 1/6, perché 1 è il numero di facce di un dado dove compare il 3, e 6 sono le facce del dado.
Due eventi mutuamente esclusivi sono 2 eventi per cui il verificarsi o meno di uno non influenza minimamente il verificarsi o meno dell'altro.
La probabilità che due eventi mutuamente esclusivi si verifichino è:
p(A ∪ B) = p(A) + p(B)
La probabilità di 2 eventi simultanei è data da:
p(A ∩ B) = p(A) + p(B) - p(A ∪ B)
La probabilità condizionata si ha invece quando un evento dipende dal verificarsi di un altro evento. Per esempio, la probabilità che Denis passi l'esame di Tettamanzi è condizionata dalla probabilità che Colui-Che-Porta-Jella lo abbia toccato.
Si scrive
p(A | B)
ed è calcolabile come
p(A) / p(B)
Ad esempio, la probabilità che esca il numero 6 da un tiro in cui so che è uscito un numero pari, è:
p(A | B) = p(A) / p (B) = (1/6) / (1/2) = 1 / 3
La sicurezza perfetta si può esprimere, in termini matematici, così:
M = messaggi
C = testi cifrati
p(M) = probabilità di osservare il messaggio M
p(C) = probabilità di osservare il messaggio cifrato c
M e C sono indipendenti.
=> p(M | C) = p(M), per tutti gli M e C possibili
Vuol dire che il cifrario perfetto è quello che, anche se guardi il messaggio cifrato, non sei in grado di dire nulla del cifrario. L'One-time pad è un cifrario perfetto perché M e C sono assolutamente indipendenti. Gli attacchi ad un cifrario si basano infatti sulla ricerca di una dipendenza tra i due eventi.
Torna alla pagina di Crittografia
