Come si può facilmente immaginare sono molte le situazioni in cui la comunicazione tra un mittente e un destinatario deve poter essere adeguatamente protetta da possibili intercettazioni di terzi non autorizzati, e questo indipendentemente dalla tecnologia utilizzata per comunicare. Gli esempi attuali sono veramente tanti: Internet, telefonia, paytv, eccetera. La soluzione generale è una sola: l'uso della crittografia. Ovviamente i crittosistemi (o cifrari) utilizzati, sia attualmente che nel passato, sono tantissimi, ognuno con le sue caratteristiche peculiari, e ciò si riflette in una storia della crittografia interessante e a tratti molto affascinante.
Normalmente quando si presenta la crittografia in termini generali si finisce sempre per citare il "cifrario perfetto", chiamato stringa monouso (in inglese one time pad) o cifrario di Vernam, dal matematico che lo ha proposto per primo all'inizio del novecento. Tipicamente si cita e basta, aggiungendo ben pochi commenti, in quanto si tratta di un metodo assolutamente impraticabile. Il suo valore è puramente teorico e che io sappia non ha nessuna applicazione pratica. La questione però secondo me è affascinante e merita un po' di più della semplice citazione.
In generale un crittosistema si può definire come una struttura costituita da un insieme finito M di possibili messaggi (costruiti su un certo alfabeto), un insieme finito K di possibili chiavi di cifratura di lunghezza fissata, e da due funzioni E (encryption) e D (decryption), entrambe dipendenti dalla scelta della chiave, che vanno da M a M e sono l'una l'inversa dell'altra. Ad essere precisi questa è la definizione di un crittosistema simmetrico (a chiave singola) visto che si dà per scontato che la stessa chiave K parametrizza sia la funzione di cifratura E che la sua inversa D, ma questo per il nostro discorso mi sembra abbastanza ininfluente, quello che conta è la funzione di cifratura, ovvero il passaggio dal testo in chiaro P (plaintext) a quello cifrato C (ciphertext). La domanda è: sotto quali condizioni il crittosistema si può considerare perfetto? E, prima ancora, che significa dire che è perfetto? Sottolineo il fatto che i crittosistemi in uso quotidianamente dalle più svariate tecnologie di comunicazione non sono mai perfetti, cioè sono tutti in varia misura attaccabili. E' chiaro che questo è un argomento di principio, in quanto la domanda molto più pratica è: quanto è difficile attaccarli? E l'ovvia risposta è che per molti di essi (praticamente per tutti quelli attualmente utilizzati) è veramente molto difficile farlo, sebbene in teoria non impossibile.
In un cifrario perfetto il testo cifrato non dovrebbe dare più informazioni sul testo in chiaro di quanto non sia già noto, e lo stesso dovrebbe valere per la chiave (almeno nel caso della cifratura simmetrica). In altre parole, l'incertezza sul testo in chiaro dovrebbe essere la stessa sia prima che dopo aver conosciuto il suo corrispondente testo cifrato. Detto questo consideriamo un insieme finito di simboli (alfabeto) con cui costruire messaggi, e consideriamo lo spazio finito di messaggi di lunghezza prefissata. E' abbastanza facile immaginare che ad ognuno di essi è possibile in linea di principio associare una certa probabilità, data ad esempio dalla frequenza con cui quel messaggio si può presentare nella conversazione tra mittente e destinatario (ovviamente questo dipenderà dal tipo di linguaggio utilizzato e da quello che tipicamente si dicono le due parti in comunicazione). Per quanto riguarda la chiave di cifratura essa varierà in un suo spazio in modo del tutto casuale e del tutto indipendente. Adesso a partire da un certo messaggio scelto immaginiamo di costruire tutti i possibili testi cifrati corrispondenti facendo variare la chiave di cifratura su tutti i valori possibili. Se facciamo la stessa cosa su un qualunque altro messaggio scelto cosa otteniamo? Se il cifrario è perfetto dobbiamo ottenere lo stesso insieme di testi cifrati. Questo in pratica ci garantisce la seguente importante proprietà: se abbiamo davanti un testo cifrato questo potrebbe essere con eguale probabilità il risultato della cifratura di uno qualunque tra tutti i messaggi possibili. Quindi seppure la distribuzione di probabilità dei messaggi in chiaro è ragionevolmente non costante (alcuni messaggi saranno sicuramente più probabili di altri), la distribuzione di probabilità dei messaggi cifrati al variare del messaggio e della chiave è rigorosamente piatta.
Purtroppo però questa equiprobabilità dei testi cifrati si può ottenere solo ad una condizione molto "scomoda". E' necessario infatti avere un numero di chiavi pari almeno al numero totale dei messaggi in chiaro definibili. Se così non fosse, dato un testo cifrato non sarebbe possibile invertirlo in uno qualunque dei testi in chiaro scegliendo un'opportuna chiave, esisterebbero cioè uno o più testi in chiaro che non vengono mandati in quel testo cifrato da nessuna delle chiavi. E' evidente che questo significa che il testo cifrato fornisce indicazioni sul corrispondente testo in chiaro. Esprimendo la questione in termini un po' più tecnici significherebbe dire che la probabilità del testo in chiaro condizionata dalla conoscenza del testo cifrato è diversa dalla semplice probabilità del testo in chiaro. Ma se è necessario che il numero delle chiavi eguagli il numero dei messaggi possibili dobbiamo avere chiavi lunghe quanto i messaggi (sotto l'ovvia ipotesi che l'alfabeto con cui costruisco i messaggi e le chiavi sia lo stesso, un tale alfabeto nel caso delle implementazioni di un criptosistema al computer è costituito semplicemente da soli due simboli, 0 e 1). Ovviamente la chiave può essere utilizzata una volta sola altrimenti si viola la condizione di perfezione.
Un algoritmo di cifratura basato su una sostituzione polialfabetica che abbia le seguenti tre caratteristiche: 1. chiave realmente random; 2. chiave della stessa lunghezza del testo in chiaro; 3. chiave utilizzata una volta sola; è completamente sicuro. Di fatto non è tanto importante l'algoritmo impiegato (che tipicamente è un semplice XOR tra il messaggio e la chiave espressi in bit, e ha la comodità di essere simmetrico, ovvero l'operazione di cifratura è identica a quella di decifratura), quanto le caratteristiche della chiave; le ipotesi fatte su di essa sono molto forti e difficili da realizzare nella pratica, e anche inutili (se ho un canale sicuro che mi permette di scambiare una chiave lunga quanto il messaggio che devo trasmettere tanto vale farci passare direttamente il messaggio).
Si noti che un cifrario così definito è effettivamente inattaccabile. Quando il messaggio viene unito alla chiave, esso perde ogni correlazione interna e quindi ogni tipologia di attacco statistico fallisce, visto che il messaggio cifrato non ha nessuna correlazione statistica con il messaggio non cifrato. Anche lo stesso attacco a forza bruta è destinato a fallire, dato che se anche si provassero tutte le possibili chiavi, si otterrebbero tanti potenziali messaggi decifrati quante sono le chiavi utilizzate; tuttavia non ci sarebbe modo di distinguere l'unico messaggio originale tra tutti i possibili messaggi in chiaro ottenuti.
In un cifrario perfetto il testo cifrato non dovrebbe dare più informazioni sul testo in chiaro di quanto non sia già noto, e lo stesso dovrebbe valere per la chiave (almeno nel caso della cifratura simmetrica). In altre parole, l'incertezza sul testo in chiaro dovrebbe essere la stessa sia prima che dopo aver conosciuto il suo corrispondente testo cifrato. Detto questo consideriamo un insieme finito di simboli (alfabeto) con cui costruire messaggi, e consideriamo lo spazio finito di messaggi di lunghezza prefissata. E' abbastanza facile immaginare che ad ognuno di essi è possibile in linea di principio associare una certa probabilità, data ad esempio dalla frequenza con cui quel messaggio si può presentare nella conversazione tra mittente e destinatario (ovviamente questo dipenderà dal tipo di linguaggio utilizzato e da quello che tipicamente si dicono le due parti in comunicazione). Per quanto riguarda la chiave di cifratura essa varierà in un suo spazio in modo del tutto casuale e del tutto indipendente. Adesso a partire da un certo messaggio scelto immaginiamo di costruire tutti i possibili testi cifrati corrispondenti facendo variare la chiave di cifratura su tutti i valori possibili. Se facciamo la stessa cosa su un qualunque altro messaggio scelto cosa otteniamo? Se il cifrario è perfetto dobbiamo ottenere lo stesso insieme di testi cifrati. Questo in pratica ci garantisce la seguente importante proprietà: se abbiamo davanti un testo cifrato questo potrebbe essere con eguale probabilità il risultato della cifratura di uno qualunque tra tutti i messaggi possibili. Quindi seppure la distribuzione di probabilità dei messaggi in chiaro è ragionevolmente non costante (alcuni messaggi saranno sicuramente più probabili di altri), la distribuzione di probabilità dei messaggi cifrati al variare del messaggio e della chiave è rigorosamente piatta.
Purtroppo però questa equiprobabilità dei testi cifrati si può ottenere solo ad una condizione molto "scomoda". E' necessario infatti avere un numero di chiavi pari almeno al numero totale dei messaggi in chiaro definibili. Se così non fosse, dato un testo cifrato non sarebbe possibile invertirlo in uno qualunque dei testi in chiaro scegliendo un'opportuna chiave, esisterebbero cioè uno o più testi in chiaro che non vengono mandati in quel testo cifrato da nessuna delle chiavi. E' evidente che questo significa che il testo cifrato fornisce indicazioni sul corrispondente testo in chiaro. Esprimendo la questione in termini un po' più tecnici significherebbe dire che la probabilità del testo in chiaro condizionata dalla conoscenza del testo cifrato è diversa dalla semplice probabilità del testo in chiaro. Ma se è necessario che il numero delle chiavi eguagli il numero dei messaggi possibili dobbiamo avere chiavi lunghe quanto i messaggi (sotto l'ovvia ipotesi che l'alfabeto con cui costruisco i messaggi e le chiavi sia lo stesso, un tale alfabeto nel caso delle implementazioni di un criptosistema al computer è costituito semplicemente da soli due simboli, 0 e 1). Ovviamente la chiave può essere utilizzata una volta sola altrimenti si viola la condizione di perfezione.
Un algoritmo di cifratura basato su una sostituzione polialfabetica che abbia le seguenti tre caratteristiche: 1. chiave realmente random; 2. chiave della stessa lunghezza del testo in chiaro; 3. chiave utilizzata una volta sola; è completamente sicuro. Di fatto non è tanto importante l'algoritmo impiegato (che tipicamente è un semplice XOR tra il messaggio e la chiave espressi in bit, e ha la comodità di essere simmetrico, ovvero l'operazione di cifratura è identica a quella di decifratura), quanto le caratteristiche della chiave; le ipotesi fatte su di essa sono molto forti e difficili da realizzare nella pratica, e anche inutili (se ho un canale sicuro che mi permette di scambiare una chiave lunga quanto il messaggio che devo trasmettere tanto vale farci passare direttamente il messaggio).
Si noti che un cifrario così definito è effettivamente inattaccabile. Quando il messaggio viene unito alla chiave, esso perde ogni correlazione interna e quindi ogni tipologia di attacco statistico fallisce, visto che il messaggio cifrato non ha nessuna correlazione statistica con il messaggio non cifrato. Anche lo stesso attacco a forza bruta è destinato a fallire, dato che se anche si provassero tutte le possibili chiavi, si otterrebbero tanti potenziali messaggi decifrati quante sono le chiavi utilizzate; tuttavia non ci sarebbe modo di distinguere l'unico messaggio originale tra tutti i possibili messaggi in chiaro ottenuti.
