I saggi pubblicati su Tangram

Tre aneddoti crittografici: uno, Kasiski

Tangram, anno VII n° 22 (dicembre 2009)

Dopo alcuni numeri di pausa riprendiamo e concludiamo la nostra breve serie di escursioni nella storia della crittografia "classica". Dopo aver visto con un certo dettaglio le tecniche messe a punto ed usate dai crittologi rinascimentali, in questa e nelle prossime puntate compiremo un balzo di tre secoli in avanti per occuparci di alcuni personaggi dell'800 che, in modi diversi, hanno lasciato un'impronta particolare nella storia della crittologia. Incontreremo così un decrittatore incompreso, un crittologo passato alla storia senza merito ed uno cui si deve un crittogramma ancora indecrittato che forse nasconde la posizione di un tesoro dal valore incalcolabile.

Cominciamo in questo numero di Tangram col fare la conoscenza di un signore che, probabilmente senza saperlo, ha rivoluzionato la storia della crittografia classica ma al quale la vita non concesse la fama che si sarebbe meritato, assegnandogli solo un tardivo riconoscimento postumo.

Risolvere il cifrario impenetrabile

In passato ci siamo occupati con grande dettaglio dei cosiddetti cifrari a sostituzione polialfabetica, grande scoperta dei crittologi del tardo Rinascimento; e parlandone notammo come per circa trecento anni essi furono ritenuti assolutamente indecrittabili, ossia totalmente sicuri ed impenetrabili all'analisi. Ciò non era vero, ma la cosa si scoprì molto tardi: fu infatti solo nel 1863 che venne infine pubblicato un metodo generale per attaccarli con successo. L'autore di questo metodo, il quale minò alla base quella che per tre secoli era stata ritenuta una solida certezza, era un oramai anziano ufficiale di fanteria prussiano chiamato Friedrich Wilhelm Kasiski.

Crittologo dilettante (preparò il suo lavoro mentre era al comando di un battaglione della riserva, avendo lasciato il servizio attivo una decina d'anni prima col grado di maggiore), Kasiski pubblicò nel 1863 a Berlino il libro “Die Geheimschriften un die Dechiffrir-kunst” in cui riportava i frutti delle sue analisi crittografiche, dedicandolo al conte Albrecht von Roon, ministro della guerra prussiano. Nel testo, di sole 95 pagine, era per la prima volta correttamente esposto nelle sue linee generali un valido metodo d'attacco ai crittogrammi ottenuti mediante cifrari a sostituzione polialfabetica sul tipo del Vigenère che abbiamo visto in passato. Per ironia della sorte questo risultato, di importanza fondamentale, non fu affatto notato o apprezzato dai contemporanei di Kasiski; il quale dedicò gli ultimi suoi anni nientemeno che all'antropologia (sempre da dilettante, ed anche in questo caso con qualche buon risultato) e non si dedicò più alla crittografia che, senza saperlo, aveva profondamente rivoluzionato.

Ma come è fatto l'attacco proposto da Kasiski? Si tratta di un vero e proprio capolavoro di… enigmistica applicata, e come tutte le cose geniali è piuttosto semplice da spiegare e da comprendere, una volta che qualcun altro ci sia arrivato prima di noi! Vediamolo dunque brevemente.

Tutto si basa sull'osservazione, di capitale importanza, che qua e là nel testo dei crittogrammi polialfabetici compaiono piuttosto frequentemente varie ripetizioni di un medesimo gruppo di tre o più lettere. Ora queste ripetizioni possono ovviamente essere solo dettate dal caso, ma più probabilmente saranno invece provocate dal fenomeno sistematico della coincidenza tra lettere del testo chiaro e lettere della chiave. In altre parole dal fatto che, in quei punti del testo, il medesimo segmento di chiave ha cifrato lo stesso gruppo di lettere chiare fornendo quindi come risultato un identica sequenza di lettere cifrate.

Capito questo fatto fondamentale, il resto segue con ferrea conseguenzialità. La prima considerazione riguarda il fatto che la distanza fra questi gruppi ripetuti è in relazione diretta con la lunghezza della chiave (ne è un multiplo intero), e quindi è un importante indizio per ricavare, mediante analisi successive e con qualche congettura da verificare successivamente, la effettiva lunghezza della chiave.

Questa è a sua volta un’informazione fondamentale perché, una volta che sia stata stabilita con ragionevole certezza, ci dice quanti sono gli alfabeti cifranti utilizzati e ci apre la via ad una semplice analisi finalizzata ad identificarli. Nel metodo di Kasiski infatti la lunghezza della chiave viene utilizzata per scindere il crittogramma in tanti sotto-crittogrammi diversi, tanti quanti sono appunto le lettere della chiave, in modo che ciascuno di essi sia stato ottenuto mediante la medesima lettera cifrante. Ciò corrisponde in pratica a dividere il crittogramma originale in tanti crittogrammi monoalfabetici, i quali possono essere decrittati separatamente l'uno dall'altro utilizzando il semplice strumento dell’analisi delle frequenze che abbiamo visto in passato, il quale viene tipicamente impiegato proprio a questo scopo.

L'analisi di Kasiski tende dunque a scomporre un complesso cifrario polialfabetico nelle sue molteplici componenti monoalfabetiche elementari, facili da decrittare separatamente. Nelle sue linee concettuali tale approccio assomiglia a quello della cosiddetta Analisi di Fourier che si usa in matematica ed in fisica, grazie al quale una forma d'onda complessa può essere scomposta nella somma delle sue semplici formanti sinusoidali le quali possono poi essere studiate singolarmente con maggior facilità usando strumenti standard.

Un esempio pratico

Nelle figure vediamo un semplice esempio di come si procede: ovviamente il testo e la chiave sono stati scelti a bella posta per evidenziare i gruppi ripetuti, ma nella pratica le coincidenze saltano sempre fuori se il testo è abbastanza lungo e la chiave abbastanza corta. Da notare che in questo esempio le parole sono state separate mediante spazi bianchi inseriti per chiarezza: essi ovviamente vanno ignorati e quindi non partecipano ai conteggi.

Osserviamo dunque il crittogramma di Figura 1, nel quale sono evidenziati diversi gruppi ripetuti. Analizzandoli con più attenzione notiamo che la distanza fra i due gruppi "LHIWGE" è di dodici caratteri, quella fra i due gruppi "MRM" è di diciotto caratteri e quella fra i due lunghissimi gruppi "CZ...ZT" è di cinquantaquattro caratteri. Da queste informazioni non ci vuole molto per ricavare la lunghezza della chiave: essa dovrà essere infatti il massimo comun divisore di 12, 18 e 54, ossia sei caratteri.

Occorre adesso creare i sei crittogrammi elementari in questo modo: il primo è formato prendendo ogni sesta lettera del crittogramma originale a partire dalla prima; il secondo è formato da ogni sesta lettera a partire dalla seconda; e così via fino al sesto crittogramma elementare, che sarà formato da ogni sesta lettera a partire dalla sesta. Ciascuno di questi crittogrammi elementari, per come è stato costruito, gode della proprietà che tutte le sue lettere sono state cifrate con la medesima lettera della chiave: quindi sono, di fatto, dei semplici cifrari monoalfabetici. A ciascuno di essi andrà quindi applicata la normale analisi di frequenze standard che abbiamo già visto in passato, che consiste nell'identificare per prime le lettere più frequenti e da queste inferire le altre.

Certo il lavoro è lunghetto ma concettualmente non difficile. Un po' di cura ed esperienza, poi, lo rendono assai più facile di quanto possa sembrare. Ad esempio nel caso in esame non può sfuggire a nessuno, credo, l'estrema lunghezza del gruppo "CZ...ZT" comune a due parole; supponendo (come in effetti è) che esso rappresenti la radice "CRITTOGRA" delle parole "CRITTOGRAMMA" e "CRITTOGRAFIA" si giunge alla corretta soluzione in un tempo assai breve. Osserviamo in generale che le probabilità di successo sono ovviamente tanto maggiori quanto più il crittogramma è lungo, in quanto l’analisi di frequenza funziona bene solo con testi di qualche decina di lettere almeno.

Il pericolo maggiore che si corre effettuando l'analisi col metodo di Kasiski è comunque quello di farsi fuorviare da falsi indizi, che possono sempre capitare per caso. Ad esempio, sempre nell’esempio di figura 1, notiamo il gruppo "MG" comune a due parole della seconda riga: esso è realmente un prodotto del caso, e ciò è un fatto piuttosto comune nei gruppi di sole due lettere. In effetti gruppi così corti non dovrebbero ordinariamente essere presi in considerazione, in quanto troppo spesso risultano essere semplici artefatti casuali. Nel caso specifico basta però notare che la sua distanza (sedici caratteri) non concorda con le altre trovate, per poter senz'altro confermare che esso è in effetti un falso positivo.

Una notevole conseguenza pratica dell'analisi descritta da Kasiski è stata la conferma teorica alla convinzione empirica, già nota ai crittologi del sei-settecento, che le chiavi lunghe fossero migliori delle chiavi corte in quanto generassero crittogrammi più robusti. Il perché è adesso evidente: a parità di testo chiaro, una chiave lunga viene ripetuta un minor numero di volte nella cifratura, e così dà meno adito a generare quelle coincidenze su cui si basa il metodo di Kasiski per determinarne la lunghezza.

Questa considerazione tra l'altro fu ripresa scientificamente agli inizi del XX secolo da Gilbert Vernam, il quale la portò alle sue estreme conseguenze giungendo così alla conclusione che la chiave migliore in assoluto è quella… lunga quanto il messaggio da cifrare! La cosa è meno ridicola di quanto sembri, in quanto si può dimostrare matematicamente che un cifrario del genere, a patto che la chiave non abbia alcun ordine interno (ad esempio sia generata in maniera casuale) e venga cambiata ad ogni messaggio, è l'unico assolutamente indecifrabile non solo in linea pratica ma anche in linea teorica.

Tale concetto di chiave lunghissima e non riutilizzabile è stato in effetti applicato consapevolmente nelle macchine cifranti comparse fra le due guerre: in esse infatti si sfruttava un meccanismo odometro, sul tipo di quelli da orologeria, proprio per generare "vermi" lunghissimi e caotici, composti da migliaia di lettere senza alcun ordine, da usare come chiave di un cifrario polialfabetico. Un esempio oramai famoso di questo sistema fu la temibile macchina Enigma usata dai tedeschi durante la seconda guerra mondiale, la quale non a torto fu ritenuta straordinariamente difficile da forzare.

Ma lui non seppe mai…

Quante feconde conseguenze nel metodo di analisi proposto dal nostro crittologo dilettante! Eppure egli non seppe mai di aver rivoluzionato la storia della crittografia, e non sospettò neppure che sarebbe passato alla storia per la sua “piccola” scoperta.

Per una sorta di legge del contrappasso, il nostro prossimo aneddoto biografico sarà invece dedicato ad un crittologo anch’egli dilettante che però, inversamente da Kasiski, ebbe da vivo una grande ma assolutamente immeritata fama grazie ad un cifrario di cui non fu autore ma che ancora oggi si chiama col suo nome.

TT DPKRQMTLHIWGE P T OXXRLHIWGE NWN KNI DQ TMGDP I TZTDFZRM BN NPIIKO FV CZBTEWGZTMXI SMGZL KOVHSNMRM EE CMGWEE Z XOALEOMRM B DZKUUXNEQ CZBTEWGZTFTKI IW EDAO ZXLLBIDB

Figura 1a: Un crittogramma come questo, ottenuto mediante un cifrario polialfabetico (tipo Vigenère), mostra spesso ripetizioni di gruppi di lettere nel testo. Ciò non è dovuto al caso ma al ripetersi ciclico della chiave, specie se questa è troppo breve. È proprio facendo leva su tale osservazione che Kasiski riuscì a trovare un metodo generale per forzare i cifrari di questo tipo, che erano stati ritenuti assolutamente impenetrabili per circa tre secoli. In figura vediamo un esempio in cui tali gruppi sono frequenti e molto ampi, per colpa di una chiave troppo corta applicata ad un testo ricco di parole simili.

LA DECRITTAZIONE E L OPERAZIONE CON CUI SI TENDE A TRADURRE IN IT ALIAITALIAITA L I AITALIAITA LIA ITA LI AITAL I AITALIAI TA

CHIARO UN CRITTOGRAMMA SENZA CONOSCERE LE REGOLE O POSSEDERE I LIAITA LI AITALIAITALI AITAL IAITALIAI TA LIAITA L IAITALIAI T

DOCUMENTI CRITTOGRAFICI AD ESSO RELATIVI ALIAITALI AITALIAITALIA IT ALIA ITALIAIT

Figura 1b: Vediamo perché nel crittogramma di figura 1a troviamo tante ripetizioni. Il testo (un brano tratto dal volume "Crittografia" di Mario Zanotti del 1928) è cifrato con un Vigenère avente per chiave la parola "ITALIA". Questa è certamente troppo corta per generare un "verme" affidabile: ed infatti si verifica in più occorrenze che desinenze o radici uguali in parole diverse vengano cifrate con la medesima successione di caratteri del "verme", producendo come risultato successioni di caratteri uguali nel cifrato. Dalla posizione relativa di questi gruppi comuni è facile risalire alla probabile lunghezza della chiave; una volta nota questa, è possibile scomporre il crittogramma polialfabetico in tanti sotto-crittogrammi monoalfabetici da risolvere facilmente mediante analisi di frequenza.

Ultima modifica: 10 gennaio 2011
Visitatori dal 23 ottobre 2005: 97,327

Torna alla Pagina dei saggi pubblicati su Tangram
Vai alla Pagina dei Commenti