CRITTOGRAFIA

La necessità della crittografia è, al giorno d'oggi, evidente: una parte della comunicazione che avviene tra enti e individui deve essere riservata; si pensi per esempio a comunicazioni bancarie o militari. Inoltre la crittografia serve a proteggere il copyright di testi, software, o immagini per i quali si desidera mantenere il diritto d'autore.

Fin dall'antichità, anche se gli strumenti matematici necessari non erano ancora noti in modo esplicito, la crittografia ha utilizzato metodi basati sull'aritmetica modulare.

Uno dei primi codici crittografici conosciuti è il codice di Giulio Cesare.

Consideriamo per il momento l'alfabeto A={a,b,…,z} formato dalle 21 lettere minuscole della lingua italiana.

Un testo T è una successione finita di elementi di A. L'idea di Cesare era quella di sostituire ogni lettera in T con la lettera che la segue in A a tre passi di distanza; Immaginiamo che A sia scritto in cerchio: a un passo da z c'è a, a due passi da z c'è b, a tre passi c'è c…

Otteniamo così la seguente tavola di sostituzione:

In base a questa tavola il testo T = "domani parto" diventa C = "grpdqn sduzr".

T è il testo in chiaro e C è il testo cifrato.

Nella Tavola A viene creata una corrispondenza biunivoca tra l'alfabeto A e A stesso. Poiché A è finito, questo equivale a dire che a lettere diverse corrispondono lettere diverse.

La matematica ora interviene in modo fondamentale nel dare un modello aritmetico di questa idea importante: modello che si rivelerà capace di notevoli e utili generalizzazioni.

Ragioniamo ora modulo 21 (il numero dei simboli in A). Possiamo dare una corrispondenza biunivoca tra l'insieme delle 21 lettere e l'insieme Z₂₀ = {0,1,2,…,20}:

Sostituendo i numeri alle lettere nella Tavola A otteniamo la Tavola C:

Ora ogni lettera è un numero. Chiamiamo Cod₃ la funzione di codificazione:

la tavola C si esprime semplicemente, in aritmetica modulare, così:

Cod₃(h) = h+3 mod 21

L'indice in basso (il numero 3) è la chiave segreta.

Chi riceve il messaggio c e conosce la chiave segreta, applica la funzione di decodifica

Decod₃(c) = c-3 mod 21

La procedura per mettere in cifra un messaggio è allora la seguente:

Si prende il testo da inviare (per esempio "se lo sognano").

Si sceglie una chiave k, cioè un intero compreso tra 1 e 20 (per esempio k = 5).

Si trasforma il messaggio in una lista di numeri con la tavola B (nell'esempio si ottiene 16 4 9 12 16 12 6 11 0 11 12).

Si applica ad ogni numero la funzione di codifica Cod_k; questo equivale ad utilizzare una tavola come la C, con k al primo posto della seconda riga. (nell'esempio si somma 5 modulo 21 ad ogni intero che compone il messaggio e si ottiene il messaggio cifrato: 0 9 14 17 0 17 11 16 5 16 17).

[Domanda: vi siete chiesti perché la chiave 0 non viene considerata?]

Il problema di questo codice crittografico è che lo spazio delle chiavi è troppo piccolo: ci sono appena 20 chiavi utilizzabili. Chi intercetta il messaggio può facilmente decodificarlo provando tutte chiavi una dopo l'altra! Questo metodo di rottura del codice è detto ricerca esaustiva nello spazio delle chiavi; è un metodo di forza bruta che porta sempre al risultato voluto se lo spazio delle chiavi non è abbastanza grande. Ovviamente l'aggettivo "grande" ha significato molto diverso a seconda dei mezzi di calcolo di cui si dispone.

Una prima osservazione che si può fare è che la tavola C è semplicemente una permutazione dei ventuno numeri 0,1,2,…,20; è un loro particolare ordinamento. Per ottenere un codice di sostituzione monoalfabetica diverso dai 20 che abbiamo potremmo scrivere i numeri da 0 a 20 su ventuno carte, mescolarle ben bene, allinearle sulla tavola e poi scrivere la successione ottenuta nella seconda riga della tavola C. Ora la chiave è la tavola stessa. Per esempio una chiave può essere:

Le persone che intendono scambiarsi messaggi cifrati condividono la tavola D: la usano dall'alto in basso per cifrare e dal basso in alto per decifrare.

Esistono 21! (si legge ventuno fattoriale) permutazioni diverse su 21 lettere.

Il numero n! è uguale a n (n-1) (n-2)....2 1. Dunque abbiamo 21!=51.090.942.171.709.440.000 chiavi a disposizione: più di 51 miliardi di miliardi di chiavi! Se con un calcolatore impieghiamo un microsecondo per provare una chiave (eseguire cioè una permutazione) occorrerà più di un milione di anni per esaurire lo spazio delle chiavi!

Esistono però metodi statistici per rompere un codice di sostituzione monoalfabetica. Essi si basano sul fatto che ogni lettera appare in un certa lingua con una sua frequenza caratteristica. Per esempio la lettera più frequente in italiano è la 'a'; se nel messaggio intercettato si trova che il numero 4 appare con la maggiore frequenza si può provare a sostituirlo con la a. Così si fa con le altre lettere basandosi sulla frequenza con cui i simboli appaiono nel messaggio. Chi vuole capire bene questo metodo, divertendosi, può leggere il racconto di Edgar Allan Poe "Lo scarabeo d'oro", pubblicato nel 1843, nel quale Legrand scopre il tesoro del capitano Kidd decifrando un messaggio in codice trovato su duna pergamena.

Questo oceano di chiavi non serve dunque a nulla! Che fare?

Un passo in avanti decisivo venne fatto da Blaise de Vigenère (1523 – 1596). La chiave è adesso una parola chiave. Supponiamo che la parola chiave (segreta e condivisa soltanto da coloro che vogliono comunicare) sia "voce" e il testo in chiaro sia "se lo sognano" (come nell'esempio precedente). Si trasformano il testo e la chiave in sequenze di numeri, come prima:

"se lo sognano" = 16 4 9 12 16 12 6 11 0 11 12

"voce" = 19 12 2 4

Poi si ripete la chiave sotto il messaggio, quante volte basta:

Poi si somma modulo 21 ottenendo 14 16 11 16 14 3 8 15 19 2 14

Ritornando alle lettere si ha la sostituzione:

Osserviamo che accadono due cose fondamentali:

1. Una lettera del messaggio in chiaro può essere trasformata in lettere diverse nel testo cifrato; nel caso considerato la O diventa una volta S, una volta D e una volta Q; la N diventa una volta R e una volta C.
2. Lettere diverse del testo in chiaro possono essere trasformate in una stessa lettera; nell'esempio S e O vanno in Q; E ed O vanno in S.

E' evidente che questo tende a distruggere la corrispondenza tra le frequenze relative delle lettere nel testo in chiaro e quelle dei simboli nel messaggio cifrato (corrispondenza che era proprio il punto debole dei codici monoalfabetici).

Questa corrispondenza sarà tanto più debole quanto più lunga e casuale è la parola chiave. Nel caso in cui la parola chiave sia composte di lettere (o numeri) estratte a caso e sia lunga come il testo in chiaro, il messaggio cifrato apparirà completamente casuale, e nessun tipo di indagine effettuata su di esso riuscirà a far affiorare il messaggio originale.

Facciamo un esempio.

Consideriamo il testo in chiaro precedente "se lo sognano" = 16 4 9 12 16 12 6 11 0 11 12.

Costruiamo una parola chiave casuale lunga come il messaggio (11 lettere) estraendo 11 interi casuali compresi tra 0 e 20. Io ho ottenuto 17 12 14 0 4 20 15 6 14 2 3.

Sommiamo modulo 21 la chiave al testo in chiaro. Otteniamo:

Chi intercetta il testo cifrato "oscoznatqpr" non potrà mai risalire al messaggio originale "selosognano" perché, visto che la parola chiave è casuale, qualsiasi testo di 11 lettere ha la stessa probabilità di divenire il codice "oscoznatqpr".

I codici di Vigenère con parola chiave casuale lunga quanto il messaggio sono perfetti: chi legge il messaggio cifrato e non possiede nessuna informazione aggiuntiva non può in nessun modo ricostruire il testo in chiaro.

Osserviamo un punto debole: se la spia viene a sapere che il messaggio originale era "selosognano", può ricavare la parola chiave mediante differenza:

chiave = testo cifrato – testo in chiaro mod 21.

Affinché il codice sia inviolabile è dunque necessario e sufficiente cambiare la parola chiave ogni volta che si invia un messaggio.

[Domanda: visto che questi codici sono inviolabili, perché non consideriamo chiuso il discorso e ci limitiamo a usare questi?]

Il cifrario di Vigenère con parola chiave più corta del messaggio non è invece inattaccabile.

Fu l'ufficiale prussiano Friedrich Kasiski (1805-1881) il primo trovare un metodo per romperlo. Se la parola chiave è lunga m e formiamo m righe, mettendo a turno in ognuna di esse le lettere del messaggio cifrato otteniamo m codici di sostituzione monoalfabetica che si possono attaccare con il metodo statistico sopra descritto.

Se per esempio la chiave è lunga 3 ed il messaggio cifrato è c₁ c₂ c₃ c₄ …..c₁₀₀₀ scriviamo:

riga 1 : c₁ c₄ c₇ c₁₀ …c₉₉₇ c₁₀₀₀

riga 2 : c₂ c₅ c₈ c₁₁…c₉₉₈

riga 3 : c₃ c₆ c₉ c₁₂…c₉₉₉

Le lettere nella riga 1 sono state ottenute tutte con la medesima sostituzione, data dalla prima lettera della chiave. Le lettere nella riga 2 sono state ottenute tutte con la medesima sostituzione, data dalla seconda lettera della chiave, etc.

Il metodo di Kasiski per trovare la lunghezza della chive si basa sul fatto che occasionalmente ci saranno coppie uguali di lettere che si trovano ad una distanza che ่ un multiplo della lunghezza della parola chiave: ad esse corrisponderanno allora coppie uguali di lettere nel testo cifrato.

Vi sono anche algoritmi, facilmente implementabili su un computer, per determinare la lunghezza della parola chiave, se il messaggio è abbastanza lungo.

Esistono oggi metodi crittografici estremamente sicuri, come l'AES (Advanced Encryption Standard), posto che si cambi sempre la chiave.

Questo pone un problema apparentemente insolubile. La comunicazione C tra A e B sarเ sicura se, immediatamente prima di inviare C i due utenti (in genere macchine) A e B si scambiano una chiave nuova, mai usata prima. Ma come trasmettere K? Occorre prima condividere una chiave K₁, etc. etc...

Quello che rende possibile la crittografia moderna ่ l'esistenza di codici crittografici a chiave pubblica. Essi eliminano alla radice il problema dello scambio delle chiavi: le chiavi di cifratura sono note a tutti!