Crittoanalisi del cifrario di Vigenere col metodo dei minimi quadrati
Un metodo di cifratura come il cifrario di Vigenere, per secoli considerato sicuro e inattaccabile, può oggi essere forzato in una frazione di secondo con l'aiuto del computer!
Un buon esempio è il seguente metodo dei minimi quadrati: l'algoritmo fa uso di una ricerca esaustiva ma anche di una funzione di valutazione basata sul classico metodo dei minimi quadrati di Gauss: si tentano una dopo l'altra tutte le possibili lunghezze del verme n = 2, 3, 4, 5 ... fino a trovare la lunghezza più probabile in base al confronto tra il numero di presenze e quello previsto.
Una volta individuato il valore di n il messaggio cifrato viene spezzato su n colonne che si possono analizzare statisticamente; queste sono infatti cifrate con un codice di Cesare, dunque ci sono solo 26 ipotesi possibili; (p.es. spostamento di 3 A->D, B->E ...; spostamento di 6 A->G, B->H ...); queste 26 ipotesi vengono analizzate una per una e per ognuna viene calcolata la funzione di valutazione: per ogni lettera si calcola la differenza tra la frequenza relativa nel testo e quella prevista, e la si eleva al quadrato; sommando tutte le differenze quadratiche si ottiene una misura della differenza tra l'ipotesi e la tabella delle frequenze; alla fine si individua l'ipotesi per la quale questa differenza è minima, e quindi la lettera del verme.
Questo lavoro viene ripetuto per ogni colonna e alla fine si ottiene una ipotesi completa per il verme; se il verme è una parola o frase riconoscibile della lingua si è pressoché certi di aver forzato il messaggio; dopodiché si prova comunque a decifrare il messaggio.
Se il messaggio ha senso compiuto il gioco è fatto; se no si prova con un altro valore di n.
Da prove fatte il metodo è pressoché infallibile se la lunghezza del verme (chiave) è almeno venti volte inferiore a quella del testo cifrato. Per rapporti tra dieci e venti alcune lettere della chiave possono essere sbagliate, ma se si tratta di una parola di senso compiuto non ci vuole molto a completarla; persino per valori [di poco] inferiori a 10 il metodo riesce ancora ad azzeccare alcune lettere della chiave e il crittoanalista può ancora arrivare alla soluzione. Un fatto curioso è che spesso questo metodo fornisce la chiave corretta o in buona parte corretta anche usando la tabella delle frequenze di una lingua sbagliata; in effetti le lingue europee hanno distribuzioni di frequenza non molto dissimili.
Come è facilmente comprensibile, se il verme ha lunghezza paragonabile al testo e le n colonne contengono solo 2 o 3 o 4 o 5 caratteri non è più possibile fare confronti significativi con le tabelle di frequenza e il metodo cade.
Se poi il verme è lungo come il testo, si tratta in effetti di un Vernam, che è il cifrario sicuro e inattaccabile per eccellenza. E anche questo metodo non può che fallire in questo caso.
N.B. Questo articolo è presente per intero al seguente link:
http://www.liceofoscarini.it/studenti/crittografia/critto/critvigminquad.html
