Il test di Friedman
Questo test si basa principalmente su alcuni semplici calcoli di probabilità e sul
concetto di indice di coincidenza. Per ogni lingua esistono tabelle con la frequenza di
ogni lettera dell’alfabeto, consideriamo ad esempio l’alfabeto inglese e denotiamo
con p1,...,p26la frequenza caratteristica di ogni lettera.
Consideriamo il solito testo cifrato abbastanza lungo, la probabilità che
in due posizioni qualsiasi si trovi la lettera di posizione con indice
, è
semplicemente ;
quindi in generale la probabilità che in due posizioni qualsiasi si trovi la stessa
lettera è data da
Se consideriamo un testo casuale in cui ogni lettera è equiprobabile cioè pi=1/26 la probabilità di cui
sopra sarà p=0,038,
molto inferiore rispetto ad un testo con significato in una qualche lingua (ad esempio in italiano questa p=0,075,
quasi il doppio).
Si denota con
si osserva che questo indice di coincidenza cresce al crescere dell’irregolarità del
testo e diminuisce fino a 0,038 quando tutte le lettere sono equiprobabili, inoltre
l’indice è invariante per i cifrari monoalfabetici mentre tende a decrescere per i
cifrari polialfabetici.
Ovviamente per un testo cifrato con Vigènere si avrà un indice “più
piccolo” rispetto a quello di un cifrario monoalfabetico, che dipenderà
dalla lunghezza della chiave e mi permetterà di calcolare quanto vale
=lunghezza
chiave.
Un modo analogo per descrivere l’indice di coincidenza è il seguente: supponiamo di avere a
disposizione n lettere,
di cui ni è il numero
di lettere -esime,
e di volere sapere quale è il numero di coppie possibili formate da lettere uguali; allora questo
sarà dato da:
.
Quindi considerando una delle prime definizioni di probabilità, e cioè il numero
di casi possibili fratto il numero di casi favorevoli, ne verrà che la probabilità di
scegliere a caso una coppia di lettere uguale è:
E questo per definizione, coincide con
=indice
di coincidenza.
Torniamo quindi al metodo per determinare la lunghezza l
della chiave: consideriamo una tabella in cui nella colonna i-esima
vengono scritte le lettere che occupano il posto i,l + i,2l + i
... (cioè tutte le lettere che sono cifrate con la stessa lettera della
parola chiave), uno studio di questo permetterà il calcolo di
e conseguentemente
di .
Osserviamo che ogni colonna corrisponde ad un cifrario monoalfabetico e quindi la
probabilità di trovare una coppia di lettere uguali nella stessa colonna è di
0,075 mentre per colonne diverse scende, supponiamo al minimo e cioè
0,038.
Sia poi
il numero di lettere del testo cifrato, allora ogni colonna ha
lettere; scegliamo a
caso una lettera tra
possibilità, questa mi identifica la colonna di appartenenza in cui avrò
modi
per scegliere una seconda lettera, cioè il numero di coppie di lettere nella stessa
colonna è:
e rispettivamente il numero di coppie che sono in colonne diverse è
Quindi il numero di coppie di lettere uguali è:
A=NU*0,075+ND*0,038 e di
conseguenza la probabilità (intesa come in precedenza) che una coppia casuale
contenga due lettere uguali è
Ma allora poichè per definizione
e per quanto visto sopra:
ne viene che
Questo numero non sarà sicuramente un intero ma fornirà un ordine
di grandezza che mi permetterà di stabilire quale, tra le possibili
determinate con metodo di Kasiski è quella esatta; così facendo avrò determinato
con
una sicurezza piuttosto elevata.