Matematica Discreta Lezione del 13/05/09

Matematica Discreta Lezione del 13/05/09

Abbiamo visto che 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: tale chiave consiste in un valore numerico a (offset) tale che 0a20 (l’offset rappresenta di quante posizioni in senso orario differisce la lettera cifrata dalla lettera in chiaro); ovviamente 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 della lezione precedente, con offset=3, i 2 utenti avrebbero concordato la chiave D, perché a=3 è il valore numerico della lettera D).

Abbiamo notato che il sistema di Cesare è attaccabile con il metodo della “forza bruta”, visto il numero ridotto delle possibili chiavi (in tutto 21).

Abbiamo anche introdotto una sua evoluzione, in cui la chiave è una permutazione delle 21 lettere dell’alfabeto (la cifratura di una lettera è la lettera che si trova, nella permutazione, nella stessa posizione della lettera in chiaro): il numero di chiavi possibili è molto alto (in tutto 21!) e rende impraticabile l’attacco con il sistema della forza bruta.

Tale sistema crittografico, come quello di Cesare, è un sistema a sostituzione monoalfabetica :ogni lettera x dell’alfabeto viene cifrata con una lettera y, ma la cifratura y di x é sempre la stessa, anche se la lettera x 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 .

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

Ecco un grafico dei valori percentuali delle frequenze delle lettere della lingua italiana (in ordine

decrescente):

Per esempio le vocali a, e sono le lettere statisticamente più frequenti (quasi il 12%

di frequenza); seguono la vocale i (poco oltre l’11%), la vocale o (circa il 10%), la consonante n (circa il 7%) e così via, fino alle consonanti q, z (le meno frequenti, con un valore di circa 0,5%).

Poiché ogni lettera del testo in chiaro ha sempre la stessa cifratura (indipendentemente dalla sua posizione), 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” (ogni lingua ha certi “vincoli” fra le lettere di una parola) 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 Vigenère è 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 della parola chiave che si trova sotto di essa.

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

“SEGRETO” :

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

S E G R E T O S E G R E T O S E G R E T O

S T V O R P O F I T N S T D E I C L I

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 seconda lettera P con chiave E (offset =4), ottenendo la cifratura T; si cifra la terza lettera P con chiave G (offset =16), ottenendo la cifratura V e così via. Come si vede una lettera del testo in chiaro può essere cifrata in modo diverso a secondo della sua posizione: la P in seconda posizione viene cifrata con T; la P in terza posizione viene cifrata con V.

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 (offset): 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

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 sembrava porre il sistema al riparo da attacchi basati sull’analisi statistica delle frequenze delle lettere, e per circa 3 secoli tale sistema fu praticamente inviolabile.

Però nell’800 vi furono dei tentativi di attacco 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 (in queste posizioni) è la stessa (perché la lettera chiave sottostante è la stessa): nell’esempio precedente (in cui la chiave é la parola “SEGRETO” di lunghezza k=7) nella scrittura della parola chiave ripetuta sotto il testo in chiaro la lettera chiave S si ritrova in posizione 1, 8, 15, 22 etc.. (cioè in posizioni a distanza multipla di 7); analogamente la lettera chiave G si ritrova in posizione 3, 10, 17, 24 etc.. (sempre in posizioni a distanza uguale a multipli di 7) e così via. Una lettera del testo in chiaro che si trovasse ripetuta, per esempio, nelle posizioni 1 e 15, sarebbe cifrata con la stessa lettera, dunque ritroveremmo la stessa lettera nel testo cifrato nelle posizioni 1 e 15.

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 quale 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=7, si esaminano nel testo cifrato le lettere in posizione 1, 8, 15, 22 etc…. (che sono tutte cifrate con la stessa lettera chiave), e a tali lettere si applicano i metodi statistici; poi si esaminano le lettere in posizione 2, 9, 16, 23, etc…. (anche queste tutte cifrate con il sistema di Cesare con la stessa lettera chiave) ed anche a tali lettere si applicano i metodi statistici e così via.

Una volta individuate alcune lettere del testo in chiaro e le loro cifrature, si può con facilità risalire alla conoscenza di alcune delle lettere della chiave.

Inoltre poiché spesso la parola chiave ha un senso compiuto (può essere anche un’intera frase di senso compiuto molto lunga) una volta trovate alcune sue lettere si possono fare ipotesi sulle altre lettere, sempre utilizzando considerazioni basate sui vincoli che la lingua del testo in chiaro pone nella struttura delle parole.

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 deve essere inoltre usata per cifrare

un solo messaggio 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 vincoli legati 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”:

La macchina possedeva una tastiera e un display sopra di essa: ogni volta che si batteva una lettera dalla tastiera, nel display si illuminava la sua cifratura (la macchina non era dotata di stampante, dunque il testo cifrato doveva essere annotato a mano lettera per lettera). Per realizzare la cifratura, nella macchina vi erano alcune ruote meccaniche (rotori) collegate fra loro ed un sistema elettrico:

ogni volta che si batteva una lettera sulla tastiera, la configurazione dei rotori e dei contatti elettrici produceva la lettera cifrata, e nello stesso tempo cambiava la configurazione della macchina;

dunque la stessa lettera, se presente più volte nel testo in chiaro, veniva cifrata in modo diverso (a secondo della configurazione in cui si trovava la macchina), e venivano evitate le debolezze dei sistemi a sostituzione monoalfabetica.

La macchina era fatta in modo che potesse servire anche per la decifratura: battendo una lettera sulla tastiera, nel display si illuminava la sua decifratura. Per fare ciò però le 2 macchine Enigma (quella usata per cifrare e quella usata per decifrare) dovevano avere la stessa configurazione iniziale (ottenuta posizionando opportunamente rotori e contatti elettrici): tale configurazione iniziale (concordata fra mittente e destinatario) era appunto la chiave (di cifratura e di decifratura).

Il problema dello scambio delle chiavi.

I sistemi crittografici fino ad ora illustrati (più o meno sicuri) sono sistemi a chiave simmetrica, nel senso che la chiave di cifratura e la chiave di decifratura coincidono.

Esistono anche sistemi sistemi a chiave asimmetrica, in cui la chiave di cifratura e la chiave di decifratura sono diverse.

In entrambi i casi però vi è un grande problema: quello dello scambio delle chiavi.

I 2 soggetti (mittente e destinatario) devono concordare sulle chiavi di cifratura e decifratura da usare, e (soprattutto se i 2 soggetti sono fisicamente distanti) la trasmissione di tali chiavi da un soggetto all’altro può comportare problemi di sicurezza (la trasmissione delle chiavi lungo un canale di comunicazione può essere intercettata da un intruso: è un circolo vizioso….).

Illustrereremo dapprima un metodo (molto macchinoso) per risolvere il problema.

Supponiamo che l’insieme dei messaggi in chiaro X coincida con l’insieme dei messaggi cifrati Y.

Il mittente A costruisce un sistema crittografico, con le funzioni di cifratura f

: X  X, e di decifratura g

: X  X tali che g

f

= i

.

Anche il destinatario B costruisce un sistema crittografico con le funzioni di cifratura f

: X  X, e di decifratura g

: X  X tali che g

f

= i

.

I due soggetti però non si comunicano le chiavi dei rispettivi sistemi, che tengono segrete.

Se il mittente vuole inviare un messaggio xX, applica la sua funzione f

e spedisce nel canale di comunicazione f

(x)=yX. Il destinatario riceve y, applica la sua funzione f

e rispedisce indietro nel canale f

(y)=zX. Il mittente riceve z, applica la sua funzione g

e spedisce nel canale di comunicazione g

(z)=tX. Notiamo che per ognuna delle 3 trasmissioni lungo il canale non vi è il problema dello scambio delle chiavi (perché le chiavi restano in possesso esclusivo del soggetto che ha costruito il suo sistema).

Come può il destinatario, che ha ricevuto alla fine t, riottenere il messaggio in chiaro x ? Supponiamo che i 2 sistemi crittografici di A e B soddisfino la condizione seguente:

g

f

=f

g

(*)

Allora se B applica al messaggio t la sua funzione g

ottiene:

g

(t) = g

(g

(z)) = g

(g

(f

(y))) = g

(f

(g

(y))) = g

(y) = g

(f

(x)) = x e riottiene il messaggio in chiaro x.

Tale sistema non è ovviamente pratico per trasmissioni in tempo reale, perché comporta la trasmissione di un messaggio attraverso un canale di comunicazione per ben 3 volte (e inoltre funziona solo se è verificata la condizione (*)). Vedremo in seguito come i sistemi crittografici a chiave pubblica risolvano il problema in modo efficiente.

Esempio.

Supponiamo che A, B usino entrambi sistemi crittografici di Cesare, e che A scelga un offset=3, mentre B scelga un offset=5 (chiavi che tengono segrete ognuno per sé).

La condizione (*) è in questo caso verificata: applicare prima f

e poi g

equivale ad operare sulle lettere uno shift verso destra di 5 posizioni e poi uno shift verso sinistra di 3 posizioni, cioè in totale uno shift verso destra di 2 posizioni; è facile verificare che lo stesso effetto si ottiene applicando prima g

e poi f

: quindi g

f

=f

g

.

Se il soggetto A vuole inviare il messaggio “CIAO”, applica la f

, ottenendo “FNDR”, e lo spedisce al soggetto B, il quale applica la f

ottenendo “MSIZ”, e lo rispedisce al soggetto A, il quale applica la g

, ottenendo “HPFT”, e lo spedisce al soggetto B. Infine il soggetto B, ricevuto il messaggio

“HPFT”, applica g

riottenendo il messaggio in chiaro “CIAO”.