Vai al contenuto

Crittografia e Decodifica – Parte 4: l’analisi delle frequenze e il cifrario polialfabetico

Nel precedente articolo ci siamo lasciati con un numero altissimo (più di 403 quadrilioni) che rappresentava il numero di chiavi possibili nel cifrario affine. Nonostante questo, però, anch’esso ha un punto debole, cioè l'”analisi delle frequenze“.

L’analisi delle frequenze

Esiste un metodo molto efficace per risolvere un messaggio cifrato. Questo metodo si basa sull’analisi delle frequenze con cui appare ogni lettera nei testi scritti in una determinata lingua.

figura 1: frequenza delle lettere nei testi scritti in italiano

Nella figura 1, ad esempio, possiamo vedere una buona approssimazione delle frequenze con cui ogni lettera appare nei testi scritti in italiano. Possiamo notare che la lettera E è quella più frequente (11,35%), mentre la W è la meno frequente (0% – non esistono W nei testi scritti in italiano).

In ordine dalla più frequente alla meno frequente sono:

Quindi, per risolvere un messaggio cifrato con un algoritmo a sostituzione, basta contare il numero delle volte con cui appare ogni carattere, e, nel caso si tratti di testo scritto in italiano, confrontarli con le frequenze viste nella figura 1.

Così, se per esempio la lettera più frequente è la J, la si sostituisce con la lettera E; e se la seconda lettera più frequente è, ad esempio, la I, la si sostituisce con la lettera A.

Quando usare l’analisi delle frequenze

Purtroppo, questa procedura non è sempre così scontata. L’analisi delle frequenze è efficace con testi molto lunghi. Infatti con testi come “Ciao, sono Andrea”, la frequenza di ogni lettera è molto relativa: di fatto la lettera E è presente soltanto una volta, e quelle più frequenti sono la A e la O.

Di conseguenza, l’analisi delle frequenze può essere usata se si sa la lingua con cui è stato scritto un testo, e se quest’ultimo ha almeno 100 caratteri.

Caratteri raggruppati

Si può avere una maggiore attendibilità studiando i raggruppamenti dei caratteri. Ad esempio, se fra le cinque lettere più frequenti ce né una che appare due volte di seguito, è molto più probabile che si tratti di una consonante, quindi della lettera N (prima consonante più frequente), o, al massimo, della lettera R.

Il cifrario polialfabetico

Il problema delle analisi delle frequenze può essere risolto con il “cifrario polialfabetico” (figura 2):

figura 2

Nella prima riga della figura 2 abbiamo l’alfabeto completo nel suo ordine originale; nella seconda riga c’è l’alfabeto spostato di tre posizioni in avanti; nell’ultima riga si trova l’alfabeto in chiave QWERTY, cioè in ordine come si trovano sulla tastiera del computer.

Proviamo a cifrare, ad esempio, la parola ALBERO, alternando con ogni carattere il tipo di alfabeto:

A -> diventa la prima lettera dell’alfabeto nella seconda riga: D
L -> diventa la dodicesima lettera dell’alfabeto in chiave QWERTY: S
B -> torno di nuovo sull’alfabeto della seconda riga: E
E -> di nuovo nell’alfabeto QWERTY: T
R -> alterno di nuovo: U
O -> e alterno ancora: G
Il risultato è DSETUG.

Grazie a questo cifrario, si crea una maggiore confusione, cosicché l’analisi delle frequenze perde gran parte della sua utilità.

Il quadrato di “de Vigenère”

Il più celebre cifrario polialfabetico è il “quadrato di de Vigenère” (o, più semplicemente, “quadrato di Vigenère), rappresentato qui sotto nella figura 3:

figura 3

Questo quadrato non è altro che una matrice, in questo caso 26 x 26, che permette di cifrare il messaggio in modo da creare maggiore confusione (ormai abbiamo capito che la confusione è l’ingrediente segreto per restare immuni dal cifrario affine).

Cifriamo ancora la parola ALBERO:

A -> diventa la prima lettera dell’alfabeto nella seconda riga: B
L -> diventa la dodicesima lettera dell’alfabeto nella terza riga: N
B -> scendo sul quarto alfabeto: E
E -> scendo ancora..: I
R -> ..e ancora..: W
O -> ..e ancora: U
Il risultato è BNEIWU.

Come si può notare, la frequenza delle lettere originali sparisce completamente.

Varianti del quadrato di Vigenère

Posso costruire un quadrato di Vigenère con chiavi differenti. Ad esempio con la parola NOVEMBRE (figura 4):

figura 4

Nelle ascisse (orizzontalmente) abbiamo l’alfabeto completo e in ordine, nelle ordinate (verticalmente) abbiamo la chiave (in questo caso NOVEMBRE).

Proviamo ora a decifrare la stringa NBYVQB seguendo questo procedimento:
1) scrivo un punto interrogativo per ogni carattere che compone la stringa, quindi in totale sono 6 punti interrogativi;
2) sotto di essi scrivo la chiave;
3) sotto scrivo la parola cifrata.

La prima lettera è nella riga della N. nella quale devo cercare la N. Vediamo che si trova nella prima posizione dell’alfabeto, di conseguenza è la lettera A.

La seconda lettera è nella riga della O, dove devo cercare la B. Si trova nella quattordicesima posizione, quella della lettera N.

Seguendo sempre lo stesso procedimento, la terza lettera la dobbiamo cercare nella riga della V, e dobbiamo trovare la Y. Si trova nella quarta posizione, corrispondente alla lettera D.

Più velocemente, riga E, lettera V = R
Riga M lettera Q = E
Riga B lettera B = A

Il risultato è ANDREA. 😀

Babbage e Krasinski

Nonostante questo metodo sembri infallibile, grazie al ((o meglio, per colpa del)) britannico Babbage, e poi al ((del)) prussiano Krasinski, alla fine del XIX secolo la cifratura polialfabetica aveva smesso di essere impenetrabile. Il loro metodo funzionava in questo modo:

Cifriamo, ad esempio, il messaggio IL BUE E IL CINGHIALE, in chiave BUFALO.

Ora, se ti va, crea la matrice in chiave BUFALO, e prova a cifrare questo messaggio. Io scrivo direttamente il risultato qui sotto:

IL BUE E IL CINGHIALE = JF GUP S JF HIYUICFLP

Ora, per maggiore chiarezza disponiamo tutto in questo modo per maggiore chiarezza (figura 5):

figura 5

Nel primo rigo si trova il messaggio in chiaro, nel secondo la chiave, e nel terzo il messaggio cifrato.

In questo modo è più facile notare che l’articolo determinativo “IL”, all’inizio e al centro del messaggio, viene cifrato nello stesso modo: “JF”. Questo avviene perché il numero di caratteri che li separa è uguale a un multiplo della lunghezza della chiave, cioè 6 caratteri.

Quindi il procedimento per decifrare il messaggio inizia con l’identificazione dei gruppi di caratteri uguali, e gli spazi che rimangono fra loro. Poi si cercano divisori comuni, e, se, ad esempio, il candidato più probabile è il numero 4 (4 caratteri: c1 c2 c3 c4), possiamo dare per scontato che il primo carattere (c1) è cifrato con un carattere dello stesso alfabeto del quinto carattere (c5), del nono (c9), e così via. Così anche il secondo carattere (c2) è cifrato con lo stesso alfabeto che si usa per il sesto carattere (c6), del decimo (c10), eccetera. Lo stesso procedimento vale anche per il terzo (c3) e il quarto carattere (c4).

Infine si passa all’analisi delle frequenze per tutti i caratteri del testo cifrati con lo stesso carattere della parola chiave. Quindi c1, c5, c9, c13…, poi c2, c6, c10, c14…, e così anche per i restanti caratteri (c3, c4).

Cifrario polialfabetico: GAME OVER

Siccome anche il cifrario polialfabetico perse la sua forza, si provò a cercare un altro metodo che cifrasse le informazioni. La ricerca di altri metodi di crittografia portò alla meccanizzazione. Ma questo è argomento del prossimo articolo.

<— IL CIFRARIO AFFINE /-/-/-/-/ CODICE MORSE, CIFRARIO ADFGVX E MACCHINA ENIGMA (da pubblicare) —>

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *