Matematica Discreta Lezione del giorno 5 maggio 2010

Matematica Discreta

Lezione del giorno 5 maggio 2010

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 messaggio in chiaro).

Nell’esempio precedente la lettera A, pur trovandosi 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.

Anche in questo sistema crittografico l’insieme X dei messaggi in chiaro e l’insieme Y dei messaggi cifrati coincidono con l’insieme delle lettere dell’alfabeto:

X = Y = {A,B,C,D,E,…..,U,V,Z}

Come chiave di cifratura (e anche di decifratura) si fissa una permutazione delle lettere dell’alfabeto (quindi un qualunque 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 che ha la lettera x nella successione alfabetica.

Dal punto di vista operativo, il mittente scrive, sotto la successione delle lettere dell’alfabeto, le lettere della permutazione (fissata come chiave di cifratura): 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 V D A Q H P

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

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 (per avere un’idea della sua grandezza si consideri che ha 20 cifre in base 10) il metodo della “forza bruta” non è praticamente applicabile dall’intruso che cerca di

“rompere” il sistema crittografico (il tempo di calcolo sarebbe troppo lungo).

Si pensi che anche con utilizzando al giorno d’oggi un computer, se esso riuscisse ad esaminare ognuna della possibili 21! chiavi in 1 miliardesimo di secondo, il tempo necessario per esaminarle tutte sarebbe superiore a 10

secondi (corrispondenti ad oltre 3000 anni).

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 .

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%) 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) pose 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: ricordiamo che nel sistema di Cesare

si fissa come chiave una lettera dell’alfabeto con valore numerico a (offset), 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 di cifratura (ed anche di decifratura) è una successione di k lettere dell’alfabeto, quindi, nel linguaggio del calcolo combinatorio, la chiave è una parola di lunghezza k sull’alfabeto delle lettere A,B,C,…Z (spesso è una parola di senso compiuto per ricordarla più facilmente).

In questo sistema l’insieme X dei messaggi in chiaro e l’insieme Y dei messaggi cifrati coincidono con l’insieme di tutte le parole di lunghezza k sull’alfabeto composto dalle lettere A,B,C,….,Z e da un carattere “speciale” # considerato come ultima lettera dopo la Z.

Il testo da spedire viene suddiviso in “blocchi” ognuno formato da k lettere: l’ultimo blocco (se ha lunghezza <k) viene completato con caratteri #.

La cifratura viene dunque fatta (in un modo che ora descriveremo) su ogni singolo blocco (considerato come elemento dell’insieme X dei messaggi in chiaro) ottenendo come messaggio cifrato ancora un blocco di k lettere : il destinatario riceve i blocchi, decifra ogni blocco e “incolla”

i blocchi ottenuti (cancellando eventuali caratteri speciali # nell’ultimo blocco) riottenendo il messaggio originale.

La funzione di cifratura f è definita nel modo seguente: se a

a

,….a

è il blocco da cifrare, e se b

b

…..b

è la chiave, la cifratura si ottiene cifrando ogni lettera a

del blocco con il sistema di Cesare utilizzando come chiave la lettera b

(i valori numerici dell’offset in questo caso variano da 0, attribuito alla lettera A, fino a 21, attribuito al carattere speciale #).

Dal punto di vista operativo, per facilitare la cifratura, si possono scrivere le lettere della chiave b

b

…..b

sotto quelle del blocco da cifrare a

a

,….a

, cifrando ogni singola lettera a

(con il sistema di Cesare) utilizzando come chiave la lettera b

sottostante: la lettera a

sarà trasformata in quella che si trova (in senso orario) in una posizione a distanza uguale al valore numerico della lettera b

. Per esempio, supponiamo che il testo il testo in chiaro sia “APPUNTAMENTOALLETRE”, e che la chiave sia la parola “SEGRETO” :

Poiché la parola chiave ha lunghezza k=7, suddividiamo il testo in blocchi di 7 lettere, completando l’ultimo blocco con i caratteri #:

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

Otteniamo 3 blocchi, ognuno da considerare come elemento dell’insieme X dei messaggi in chiaro.

Per effettuare la cifratura del primo blocco, scriviamo sotto le sue lettere le 7 lettere della chiave

“SEGRETO” e cifriamo ogni lettera del blocco con il sistema di Cesare utilizzando come chiave la lettera sottostante:

A P P U N T A S E G R E T O S T V N R O O

Nella terza riga vi è la cifratura del blocco: per esempio si cifra la seconda lettera P del blocco con il sistema di Cesare con chiave E (offset =4), ottenendo la cifratura T; si cifra la terza lettera P del blocco 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 invece cifrata

con V.

Nello stesso modo si procede per cifrare il secondo blocco:

M E N T O A L

S E G R E T O

E I T M S T #

e il terzo blocco:

L E T R E # # S E G R E T O

D I B I I S N

La funzione g di decifratura ovviamente opera in modo inverso, utilizzando la decifratura del sistema di Cesare sulle singole lettere dei blocchi cifrati: si riottengono così i 3 blocchi originari, che, incollati e con l’eliminazione dei caratteri # nell’ultimo blocco, danno il testo in chiaro originario.

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)

Alle debolezze riscontrate nel sistema crittografico di Vigenére si può ovviare nel seguente modo:

poiché uno dei punti deboli è l’uso ripetuto della parola chiave per decifrare i vari “blocchi” del

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 per decifrare i vari blocchi); 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” e in pratica non utilizzabile 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.