Matematica Discreta Lezione del giorno 11 maggio 2009 Crittografia.

Matematica Discreta

Lezione del giorno 11 maggio 2009 Crittografia.

E’ la scienza che studia la possibilità che un soggetto A (mittente) spedisca un messaggio ad un utente B (destinatario) attraverso un canale di comunicazione non sicuro, in modo che per un soggetto C (intruso), che sia in grado di intercettare il messaggio, sia “difficile” conoscere le informazioni in esso contenuto.

Anticamente il concetto di ”messaggio” era ristretto ad un messaggio di tipo “testuale”, cioè costituito da caratteri alfabetici.

Poiché il messaggio può sempre essere suddiviso in “blocchi” (che poi il destinatario dovrà

“incollare” per riottenere l’intera informazione originale) potremo anche in certi casi identificare il concetto di messaggio con il singolo carattere alfabetico.

In un sistema crittografico il messaggio originale (detto messaggio in chiaro) prima di essere trasmesso dal mittente A viene opportunamente modificato (è la cosiddetta cifratura che trasforma il messaggio in chiaro in un messaggio cifrato); è il messaggio cifrato che viene trasmesso lungo il canale di comunicazione: quando il destinatario B lo riceve, ne effettua una opportuna modifica (è la cosiddetta decifratura) che dovrebbe dare come risultato il messaggio in chiaro originale.

Se vogliamo formalizzare la struttura di un sistema crittografico, servendoci della teoria degli insiemi, possiamo dire che si possono individuare un insieme finito X dei messaggi in chiaro, un insieme finito Y dei messaggi cifrati (spesso come insiemi X,Y saranno uguali), una funzione di cifratura f : X  Y (che trasforma ogni messaggio in chiaro xX in un messaggio cifrato y=f(x)X) e in una funzione di decifratura g : Y  X (che ritrasforma il messaggio cifrato y=f(x)Y nel messaggio in chiaro x=g(y)X).

Dal punto di vista insiemistico, la proprietà della funzione di decifratura g si traduce nel fatto che per ogni messaggio in chiaro xX si deve avere g(f(x))=x, dunque la composizione gf deve coincidere con la funzione identica i

dell’insieme X.

Da ciò segue subito che la funzione f di cifratura è iniettiva: se infatti per assurdo esistessero x

,x

X tali che x

≠x

, f(x

)=f(x

), applicando g ad ambo i membri si avrebbe g(f(x

))=g(f(x

)) da cui x

=x

, contraddizione.

Essendo f iniettiva, ed essendo X,Y finiti, si deduce che la cardinalità di X è  della cardinalità di Y.

Ovviamente se X=Y la funzione di cifratura f sarà anche surgettiva (essendo X,Y finiti) ossia biunivoca, e la funzione di decifratura g non sarà altro che la funzione inversa f

.

Vedremo dagli esempi che la funzione di cifratura e la funzione di decifratura si servono di elementi ausiliari (detti rispettivamente chiavi di cifratura e chiavi di decifratura) che sono utilizzati nella trasformazione di un messaggio in chiaro in messaggio cifrato e nella ritrasformazione di un messaggio cifrato nel messaggio in chiaro da cui esso proveniva.

Il sistema crittografico di Cesare.

E’ un sistema crittografico molto semplice (ma poco sicuro) che pare fosse utilizzato dagli antichi Romani.

Supponiamo che l’insieme dei messaggi in chiaro X e quello dei messaggi cifrati Y coincidano entrambi con l’insieme delle 21 lettere dell’alfabeto italiano:

X = Y = {A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U,V,Z}

Fissiamo un numero intero a tale che 0a20 (è la chiave di cifratura, detta offset) e definiamo la funzione di cifratura f : X  Y nel modo seguente: disponiamo in modo “circolare” gli elementi di X (in modo che la lettera successiva alla Z sia la A), e per ogni messaggio in chiaro x X (dunque x è una delle 21 lettere dell’alfabeto) definiamo il messaggio cifrato y=f(x) uguale a quella lettera che si trova (a partire dalla lettera x) spostandosi di a posizioni lungo l’alfabeto in verso orario.

Per esempio se la chiave di cifratura è a=3 e se x=D allora f(D)=G (la lettera G si trova 3 posizioni più avanti rispetto alla lettera D). Ovviamente non ha molto senso scegliere l’offset a=0, in quanto la cifratura di ogni lettera la lascerebbe invariata.

La funzione di decifratura g : Y  X utilizza la stessa chiave a, ed è ovviamente definita nel modo seguente: dato il messaggio cifrato y=f(x) (quindi y è una delle 21 lettere dell’alfabeto) si definisce g(y) uguale a quella lettera che si trova (a partire dalla lettera y) spostandosi di a posizioni lungo l’alfabeto in verso antiorario: ovviamente g(y) coinciderebbe con il messaggio in chiaro originale x.

Per rendere operativamente più semplice la cifratura, il mittente scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso destra di a posizioni (se a è la chiave di cifratura) sempre pensando ad una struttura “circolare”: sotto ogni lettera x si trova la sua cifratura f(x).

Per esempio nel caso a=3:

A B C D E F G H I L M N O P Q R S T U V Z

D E F G H I L M N O P Q R S T U V Z A B C

In questo caso, per cifrare il testo in chiaro “ATTACCATESUBITO” applicando ad ogni lettera del testo la funzione f di cifratura, si ottiene il seguente testo cifrato (da trasmettere lungo il canale di comunicazione):

“DZZDFFDZHVAENZR”

Analogamente, per rendere operativamente più semplice la decifratura, il destinatario scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso sinistra di a posizioni: sotto ogni lettera y si trova la sua decifratura g(y).

Nel nostro caso (con a=3):

A B C D E F G H I L M N O P Q R S T U V Z

U V Z A B C D E F G H I L M N O P Q R S T

Decifrando il testo ricevuto “DZZDFFDZHVAENZR” (lettera per lettera) si riottiene il testo originale “ATTACCATESUBITO”.

Nel sistema crittografico di Cesare la chiave di cifratura coincide con quella di decifratura, e ovviamente deve essere concordata in anticipo fra il mittente e il destinatario: invece di scegliere il numero intero a tale che 0a20, i 2 utenti potrebbero in modo equivalente assegnare ad ogni lettera dell’alfabeto un valore numerico progressivo da 0 a 20 (A=0, B=1, C=2,…., Z=20), poi scegliere come chiave una delle 21 lettere dell’alfabeto e definire il valore dell’offset a uguale al valore numerico della lettera scelta (nell’esempio precedente i 2 utenti avrebbero concordato la chiave D, perché a=3 è il valore numerico della lettera D).

Il sistema di Cesare è poco sicuro: l’intruso che intercetti il messaggio cifrato, potrebbe cercare di risalire al messaggio in chiaro con il metodo della “forza bruta”, provando a decifrare il messaggio con tutte le possibili chiavi (che sono in tutto 21) fino ad ottenere un messaggio che abbia un senso compiuto.

Il sistema crittografico di Cesare fa parte dei cosiddetti sistemi a sostituzione monoalfabetica (ogni lettera dell’alfabeto viene cifrata con un’altra lettera, ma sempre con la stessa lettera, anche se la lettera originale appare in diverse posizioni nel testo in chiaro).

Nell’esempio precedente la lettera A, che si trova in 2 posizioni diverse nel messaggio in chiaro

“ATTACCATESUBITO” viene cifrata sempre con la lettera D.

Per rendere più difficile l’uso della “forza bruta” da parte dell’intruso, si può utilizzare una variante del sistema di Cesare, in cui il numero di chiavi è molto più grande.

Come chiave di cifratura (e anche di decifratura) si fissa una permutazione delle lettere dell’alfabeto (quindi un modo di disporre ordinatamente le 21 lettere) e si definisce la funzione di cifratura f : X  Y nel modo seguente: per ogni messaggio in chiaro xX (dunque x è una delle 21 lettere dell’alfabeto) si definisce il messaggio cifrato y=f(x) uguale a quella lettera che si trova, nella permutazione fissata, nella stessa posizione della lettera x.

Dal punto di vista operativo, il mittente scrive, sotto la successione delle lettere dell’alfabeto, le lettere nella permutazione fissata: sotto ogni lettera x si trova la sua cifratura f(x).

Per esempio se la permutazione fissata come chiave é BFGTURSEIOLMZNCUDATHP:

A B C D E F G H I L M N O P Q R S T U V Z

B F G T U R S E I O L M Z N C U D A T H P

la cifratura del testo in chiaro “ATTACCATESUBITO” è “BAABGGBAUDTFIAZ”.

La funzione di decifratura g : Y  X si ottiene viceversa associando ad ogni lettera y (considerata nella permutazione) la lettera g(y) che si trova sopra di essa.

Anche in questo caso la chiave di cifratura (la permutazione fissata) coincide con quella di decifratura, e deve essere concordata in anticipo fra il mittente e il destinatario: ma il numero di chiavi possibili coincide con 21! (il numero delle possibili permutazioni di 21 lettere), e poiché tale numero è molto grande (ha 20 cifre in base 10) il metodo della “forza bruta” non è facilmente applicabile dall’intruso che cerca di “rompere” il sistema crittografico.

Anche tale sistema crittografico, come quello di Cesare, è un sistema a sostituzione monoalfabetica (ogni lettera dell’alfabeto viene cifrata con un’altra lettera, ma sempre con la stessa lettera, anche se la lettera originale appare in diverse posizioni nel testo in chiaro).

Tutti i sistemi a sostituzione monoalfabetica sono però vulnerabili ad un altro tipo di attacco, quello basato sull’analisi statistica delle frequenze delle lettere (nella lingua in cui è scritto il testo in chiaro).

Se un testo è scritto in una certa lingua (soprattutto se è molto lungo) il numero di occorrenze (in percentuale) di ogni lettera dell’alfabeto nel testo è in genere molto vicino ad un valore statistico che si conosce a priori.

Ecco i valori delle frequenze delle lettere in lingua italiana:

A: 9,651 %; B: 0,481 %; C: 3,469 %; D: 4,142 %; E: 12,791 %; F: 0,929 %; G: 1,9984 %; H:

0,517 %; I: 12,730 %; L: 5,809 %; M: 2,031 %; N: 7,690 %; O: 8,760 %; P: 3,018 %; Q:

0,350 %; R: 8,140 %; S: 4,835 %; T: 7,290 %; U: 2,685 %; V: 1,283 %; Z: 1,387 %

Poiché ogni lettera del testo in chiaro viene cifrata sempre con la stessa lettera, esaminando la frequenza delle lettere nel testo cifrato si potrebbe, con una certa approssimazione, fare delle ipotesi sulle lettere di cui esse sono la cifratura (soprattutto se il testo è molto lungo) e poi, attraverso altre considerazioni “linguistiche” (per esempio certe lettere sono seguite o precedute spesso da altre lettere) sarebbe possibile, anche per tentativi, risalire al testo in chiaro.

Il sistema crittografico di Vigenère

La vulnerabilità alle analisi statistiche dei sistemi crittografici a sostituzione monoalfabetica risiede dunque nel fatto che ogni lettera dell’alfabeto viene cifrata sempre con la stessa lettera, indipendentemente dalla sua posizione nel testo.

Il sistema crittografico di Vigenère (introdotto nel ‘500) pone rimedio a questo difetto, perché è un

sistema a sostituzione polialfabetica, nel senso che ogni lettera dell’alfabeto viene cifrata con una

lettera che però dipende dalla posizione della lettera stessa nel testo in chiaro.

Il sistema di Vigenere è una evoluzione del sistema di Cesare: nel sistema di Cesare si fissa come chiave (offset) una lettera dell’alfabeto con valore numerico a, con 0a20; ogni lettera x del testo in chiaro é cifrata con la lettera y che si trova (a partire dalla lettera x) spostandosi di a posizioni lungo l’alfabeto in verso orario (pensando sempre all’alfabeto con un struttura circolare).

Nel sistema di Vigenère la chiave è una parola composta da k lettere dell’alfabeto: poiché k è in genere minore del numero di lettere del testo in chiaro, per effettuare la cifratura si ripete più volte la chiave sotto il testo in chiaro fino a “coprire” tutte le lettere di quest’ultimo (anche in eccesso), e poi si cifra ogni lettera del testo in chiaro con il sistema di Cesare utilizzando come chiave la lettera sotto di essa.

Per esempio, se il testo in chiaro è “APPUNTAMENTOALLETRE”, e se la chiave è la parola

“ARTE” :

A P P U N T A M E N T O A L L E T R E

A R T E A R T E A R T E A R T E A R T E

A H L B N N T Q A F P S A D F I T L A

Nella prima riga vi è il testo in chiaro, nella seconda la chiave ripetuta più volte (fino a coprire il testo in chiaro), nella terza il testo cifrato: per esempio si cifra la prima lettera A con chiave A (offset a=0), ottenendo A; si cifra la seconda lettera P con chiave R (offset a=15), ottenendo H e così via. Come si vede una lettera del testo in chiaro può essere cifrata in modo diverso a secondo della sua posizione: al P in seconda posizione viene cifrata con H; la P in terza posizione viene cifrata con L.

Per semplificare la cifratura, si può utilizzare una matrice 21x21, composta da alfabeti ordinati e shiftati verso destra: la prima riga contiene le lettere dell’alfabeto nel loro ordine naturale; la seconda riga contiene le lettere shiftate di 1 posto verso destra (sempre pensando ad una struttura circolare); la terza riga contiene le lettere shiftate di 2 posti verso destra etc…. (vedere sotto la matrice).

Per cifrare una lettera del testo in chiaro basta individuare, nella prima riga, la colonna in cui si trova la lettera stessa, poi individuare, nella prima colonna, la riga in cui si trova la lettera che ha il ruolo della chiave: la cifratura sarà la lettera che si trova all’incrocio fra la colonna e la riga individuate.

Per esempio per cifrare la lettera T con la chiave R: si individua nella prima riga la colonna della T, si individua nella prima colonna la riga della R e si ottiene la cifratura N all’incrocio.

A B C D E F G H I L M N O P Q R S T U V Z

B C D E F G H I L M N O P Q R S T U V Z A

C D E F G H I L M N O P Q R S T U V Z A B

D E F G H I L M N O P Q R S T U V Z A B C

E F G H I L M N O P Q R S T U V Z A B C D

F G H I L M N O P Q R S T U V Z A B C D E

G H I L M N O P Q R S T U V Z A B C D E F

H I L M N O P Q R S T U V Z A B C D E F G

I L M N O P Q R S T U V Z A B C D E F G H

L M N O P Q R S T U V Z A B C D E F G H I

M N O P Q R S T U V Z A B C D E F G H I L

N O P Q R S T U V Z A B C D E F G H I L M

O P Q R S T U V Z A B C D E F G H I L M N

P Q R S T U V Z A B C D E F G H I L M N O

Q R S T U V Z A B C D E F G H I L M N O P

R S T U V Z A B C D E F G H I L M N O P Q

S T U V Z A B C D E F G H I L M N O P Q R

T U V Z A B C D E F G H I L M N O P Q R S U V Z A B C D E F G H I L M N O P Q R S T V Z A B C D E F G H I L M N O P Q R S T U Z A B C D E F G H I L M N O P Q R S T U V

Per decifrare si usa un metodo simile, ma costruendo una matrice in cui le righe contengono alfabeti shiftati verso sinistra.

Il fatto che nel sistema di Vigenére una lettera del testo in chiaro possa essere cifrata in modo diverso a secondo della sua posizione sembrerebbe porre il sistema al riparo da attacchi basati sull’analisi statistica delle frequenze delle lettere, e per circa 3 secoli tale sistema sembrò inattaccabile.

Però nell’800 vi furono dei tentativi di “rottura” di tale sistema che ebbero successo, e che si basano sulle considerazioni che seguono.

Se una lettera nel testo in chiaro si ripete 2 volte ad una distanza che è multipla della lunghezza k della parola chiave, allora la sua cifratura nel testo cifrato è la stessa (perché la lettera chiave sottostante è la stessa): nell’esempio precedente (in cui la chiave é la parola “ARTE” di lunghezza k=4) nella scrittura della parola chiave ripetuta sotto il testo in chiaro la lettera chiave A si ritrova in posizione 1, 5, 9, 13 etc.. (cioè in posizioni a distanza uguale a multipli di 4); analogamente la lettera chiave A si ritrova in posizione 2, 6, 10, 14 etc.. (sempre in posizioni a distanza uguale a multipli di 4) e così via.

Si potrebbe allora (soprattutto con un testo in chiaro molto lungo, in cui la ripetizione delle lettere è più frequente) esaminare quali lettere del testo cifrato si ripetono e a che distanza: un divisore di una di tali distanze potrebbe essere la lunghezza k della chiave. A questo punto, sperimentando con uno di tali valori possibili della lunghezza della chiave, si potrebbero tentare metodi statistici sulla frequenza delle lettere: per esempio se si sperimenta con il valore possibile k=4, si esaminano nel testo cifrato le lettere in posizione 1,5,9,13,17 etc…. (che sono tutte cifrate con il sistema di Cesare con la stessa lettera chiave), poi le lettere in posizione 2,6,10,14,18, etc…. (anche queste tutte cifrate con il sistema di Cesare con la stessa lettera chiave) e così via.

Inoltre poiché spesso la parola chiave ha un senso compiuto per ricordarla più facilmente (può essere anche un’intera frase molto lunga) una volta scoperta la sua lunghezza si possono fare ipotesi sulle sue lettere, sempre utilizzando considerazioni basate sulle proprietà della lingua del testo in chiaro.

Il sistema crittografico OTP (One Time Pad)

Ai difetti riscontrati nel sistema crittografico di Vigenére si può ovviare nel seguente modo: poiché uno dei punti deboli è la ripetizione della parola chiave sotto il testo in chiaro, si può usare una parola chiave lunga almeno quanto tutto il testo; tale chiave dovrebbe essere inoltre usata una sola volta e poi sostituita con un’altra (usarla per cifrare più messaggi porterebbe alla stessa vulnerabilità dovuta alla sua ripetizione sotto il testo); inoltre poiché un altro punto debole del sistema è il fatto che la chiave (se di senso compiuto) soddisfa certe proprietà legate alla lingua del testo, la parola chiave dovrebbe essere formata da lettere casuali.

Un sistema crittografico di questo tipo (sistema “One Time Pad”=”Blocco Monouso”) è chiamato

“sistema cifrario perfetto” e la sua assoluta sicurezza è comprovata da una dimostrazione matematica formale (dovuta a Shannon).

Ovviamente è un sistema abbastanza “scomodo” perché le chiavi sono molto lunghe, ed ognuna è usata per cifrare un solo messaggio: i 2 utenti (mittente e destinatario) devono concordare su un insieme di moltissime chiavi, tutte di grande lunghezza.

La macchina Enigma

Facciamo un piccolo cenno storico al sistema crittografico usato durante la II

Guerra Mondiale dai Nazisti per le loro comunicazioni militari.

Esso si basava su una macchina elettro-meccanica chiamata “Enigma”: