Breve storia della crittografia
La Scitale spartana
L’arte dello scrivere-nascosto era già conosciuta ed utilizzata mille anni prima di Cristo. Le più antiche notizie sicure sono, però, probabilmente quelle sulla scitale spartana. Questa tecnica consisteva in questo. Dopo aver scelto un’asta, avente un certo diametro, le si avvolgeva attorno un nastro di cuoio. A questo punto si scriveva il messaggio partendo da un’estremità dell’asta verso l’altra, parallelamente all’asse. In seguito si svolgeva il nastro di cuoio e lo si inviava al destinatario. Questi, affinché potesse leggere correttamente il messaggio, doveva riavvolgere il nastro su un’altra asta di uguale diametro. Non era certamente ciò che noi oggi definiremmo un algoritmo sicuro, ma in base a quanto ci tramandano storici greci quali Plutarco, esso fu usato con successo per molti secoli. Si legge infatti nelle Vite parallele di Plutarco, che questo sistema era usato da Licurgo(?) (IX sec. a. C.) e da Lisandro. Quest’ultimo infatti, nel 404 a.C. circa, ricevette un corriere, pesto e insanguinato, dei cinque che avevano tentato l’attraversamento del territorio persiano. Il corriere porse la “cintura” a Lisandro, che l’avvolse intorno all’asticciola, di giusto diametro, ed apprese che il persiano Farnabazo progettava di attaccarlo. Ebbe così il tempo di prepararsi, e il nemico fu respinto. La scitale spartana è un esempio di cifrario a sostituzione, ottenuta manualmente, che aggiungeva alla sua efficacia tecniche steganografiche, infatti la striscia di cuoio poteva facilmente essere camuffata da cintura.
Il Codice Atbash
Certamente non furono solamente i Greci a utilizzare la crittografia, si hanno, infatti, notizie del fatto che anche Ebrei, Indiani, Cinesi utilizzavano con successo diverse tecniche crittografiche. Per esempio gli Ebrei inventarono il codice atbash, il cui nome deriva infatti dalle lettere dell’alfabeto ebraico (A = aleph, T = taw, B(a) = beth, SH = shin). Questo algoritmo fa parte della famiglia degli algoritmi simmetrici a sostituzione. Per cifrare un testo in chiaro si effettuava, infatti, la seguente sostituzione:
la prima lettera dell’alfabeto A la si sostituiva con l’ultima: la T; la seconda B con la penultima S. Da qui il nome dell’algoritmo. Per fare un esempio utilizzerò però le lettere dell’alfabeto inglese.
ALFABETO IN CHIARO a b c d e f g h i j k l m n o p q r s t u v w x y z
ALFABETO CIFRANTE Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
Quindi la frase in chiaro Attaccheremo Gerico domani all’alba diventa in cifra Zggzxxsvivnl Tvirxl wlnzmr zoo’zoyz.
Per quanto riguarda gli Indiani, invece, un’altra antica descrizione di cifratura si trova addirittura nel Kamasutra, opera del brahmino Vatsyayana, un erudito del IV sec. d.C., che utilizzò manoscritti risalenti al IV sec. a. C. Secondo il Kamasutra, una delle arti che le donne devono imparare è l’arte della scrittura in codice, utile, secondo il brahmino, per celare a occhi indiscreti la corrispondenza fra due amanti. Una delle tecniche raccomandate consiste nell’accoppiare a caso a due a due le lettere dell’alfabeto e nel sostituire ciascuna lettera del testo con quella a lei accoppiata.
Il cifrario di Cesare
Il primo uso sicuramente attestato della cifratura per sostituzione in ambito militare si trova, però, nei Commentarii de bello gallico di Caio Giulio Cesare (102-100 a. C. / 44 a. C.). Cesare racconta:
ibi ex captivis cognoscit, quae apud Ciceronem gerantur quantoque in periculo res sit. Tum cuidam ex equitibus Gallis magnis preamiis persuadet, uti Ciceronem epistulam deferat. Hanc Graecis conscriptam litteris mittit, ne intecepta epistula nostra ab hostibus consilia cognoscantur. (De bello gallico, V,48.2-4).
tradotto
Lì, apprende dai prigionieri quanto sta accadendo presso Cicerone e in quale pericolo si trovi. Allora convince con grandi ricompense un cavaliere dei Galli a portare una sua lettera a Cicerone. redige la missiva in caratteri greci perché se cada in mano nemica non riveli i nostri piani.
Qui come si evince dal testo, Cesare utilizzò caratteri greci al posto di quelli dell’alfabeto latino. Tale sistema era abbastanza sicuro, infatti, è del tutto improbabile che ci fosse, nei ranghi dell’esercito che assediava Cicerone, qualcuno che conoscesse il greco. A quel tempo il greco lo imparavano solo i rampolli delle più ricche famiglie romane, tramite un precettore greco e grazie a viaggi studio in Grecia. Questo non è l’unico caso accertato di uso di cifrari a trsposizione da parte di Cesare; si sa, infatti, che Cesare ricorreva spessissimo alle missive in cifra, anche per comunicare coi parenti. Sappiamo, in proposito che la cifratura era talmente tanto spesso utilizzata da Cesare, che Valerio Probo dedicò ai suoi cifrari un intero trattato, che purtroppo è andato perduto. Ma ci sono altre testimonianze, come quelle di Svetonio. Si legge infatti nelle Vite dei Cesari:
Extant et ad Ciceronem, item ad familiares domesticis de rebus, in quibus, si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset: quae si qui investigare et persequi velit, quartam elementorum litteram, id est D pro A et perinde reliquas commutet. (Vita di Cesare, 56)
tradotto
Restano quelle a Cicerone, così come quelle ai familiari sugli affari domestici, nelle quali, se doveva fare delle comunicazioni segrete, le scriveva in codice, cioè con l’ordine delle lettere così disposto che nessuna parola potesse essere ricostruita: se qualcuno avesse voluto capire il senso e decifrare, avrebbe dovuto cambiare la quarta lettera degli elementi, cioè D per A e così via per le rimanenti.
Ecco un esempio:
ALFABETO IN CHIARO a b c d e f g h i l m n o p q r s t u v z
ALFABETO CIFRANTE D E F G H I L M N O P Q R S T U V Z A B C
Quindi la frase in chiaro Veni Vidi Vici diventa in cifra Bhqn Bngn Bnfn.
La scacchiera di Polibio
Questo sistema ideato dallo storico greco Polibio di Megalopoli, in Arcadia, (201 -120 circa a. C.), prevede che ogni lettera dell’albabeto in chiaro, venga sostituita dalla coppia di numeri che individuano la sua posizione, quindi per esempio alfa viene cifrata con 11, pi viene cifrata con 41 e così via.
L’idea era che un messaggio potesse essere trasmesso tenendo diverse combinazioni di torce in ogni mano. La scacchiera ha altre importanti caratteristiche, e cioé la riduzione nel numero di caratteri diversi, la conversione in numeri e la riduzione di un simbolo in due parti che sono utilizzabili separatamente. Indipendentemente dalla tecnica, queste scacchiere formano la base per molti altri codici di cifratura come il Cifrario di Playfair.
Il Medioevo
Da Cesare fino all’alto medioevo, si continuò ad usare degli algoritmo di cifratura per sostituzione o per trasposizione; infatti tali algoritmi era ritenuti inviolabili dai dotti. Consideriamo, ad esempio, la cifratura di Cesare, essa prevede come abbiamo già detto, uno spostamento di 3 posizioni. Ma è chiaro che impiegando qualunque spostamento, compreso tra 1 e 20, si possono generare 20 diverse cifrature . Se invece di ricorrere al semplice spostamento, si ammette l’uso di qualunque alfabeto cifrante, ottenuto per riorganizzazione dell ‘alfabeto in chiaro, si può generare un numero molto più alto di cifrature . Per un gruppo di 21 lettere le possibili combinazioni sono circa 50.000.000.000.000.000.000 ognuna delle quali permette una diversa cifratura. A causa delle tumultuose vicende della storia europea nel periodo compreso tra IV e XI sec., non furono fatti passi avanti nel campo della crittografia. Ma mentre l’ europa era in piena decadenza, non molto lontano, dall ‘altra parte del Mediterraneo la civiltà araba era in piena fioritura. I suoi meriti, sono tanti, fra questi a noi interessano particolarmente quelli legati alla crittologia . Infatti, gli arabi non solo continuarono ad utilizzare, con profitto, i sistemi di cifratura, peraltro già utilizzati da secoli, ma contribuirono, in maniera fondamentale, allo sviluppo dell ‘altra branca della crittologia .: la crittanalisi . Mentre i crittografi mettevano a punto nuovi sistemi di cifratura, i crittoanalisti cercavano di individuare i loro punti deboli e capire i segreti che custodivano. E furono i crittoanalisti arabi a trovare il punto debole della sostituzione monoalfabetica, un sistema che resisteva da secoli ad ogni assalto. Alla base della crittoanalisi araba vi era la cosiddetta analisi delle frequenze. Cos’è? Si legge nel più antico trattato arabo sull’argomento, Sulla decifrazione dei messaggi cifrati dello studioso Abu Yusuf ibn Ishaq al-Kindi (IX sec. d.C.):
Un modo di svelare un messaggio crittato, se conosciamo la lingua dell’originale, consiste nel trovare un diverso testo in chiaro nella stessa lingua, abbastanza lungo da poterne calcolare la frequenza di ciascuna lettera. Chiamiamo “prima” quella che compare più spesso, “seconda” la successiva, e così via fino all ‘esaurimento di tutte le lettere del campione di testo in chiaro.
Esaminiamo poi il testo in cifra che vogliamo interpretare, ordinando in base alla frequenza anche i suoi simboli. Troviamo il simbolo più comune, rimpiazziamolo con la “prima” lettera dell’esempio in chiaro; il simbolo che lo segue per frequenze sia rimpiazzato dalla “seconda” lettera dell’esempio in chiaro, e così via fino ad aver preso in considerazione tutti i simboli che volevamo svelare.
Il Disco dell’Alberti
Queste tecniche innovative di crittoanalisi, messe a punto dagli arabi, vennero reintrodotte in Europa dove furono utilizzate con successo in molteplici campi, ma soprattutto in ambito diplomatico, governativo e commerciale. Ma come si suol dire, non c’ era niente di nuovo sotto il sole. Infatti si continuava ad utilizzare dei metodi di cifratura per sostituzione monoalfabetica. Chiunque inviava un messaggio in codice doveva rassegnarsi: se il messaggio fosse caduto in mani ostili, un abile decrittatore avrebbe potuto impadronirsi dei suoi segreti più preziosi.
Ma per fortuna, un uomo, un italiano dal multiforme ingegno, Leon Battista Alberti, vissuto nel XV secolo, in pieno Rinascimento, propose di usare al posto di un solo alfabeto due o più alfabeti cifranti e di sostituirli durante la cifratura, per confondere l’eventuale decrittatore. Tuttavia pur essendosi imbattuto nella più importante scoperta degli ultimi 10 secoli, nel campo delle scritture segrete, egli non riuscì a trasformare la sua geniale intuizione in un algoritmo ben definito. Sarà un diplomatico, Blaise de Vigenere, nato nel 1523, a mettere a frutto l’intuizione dell’Alberti.
Cifrario Vigenere
Blaise de Vigenere pubblicò nel 1586 un trattato di cifre nel quale proponeva tra gli altri un codice che ebbe grande fortuna e che è ricordato con il suo nome. Si tratta del più semplice codice di sostituzione polialfabetica, e proprio per la sua semplicità ha goduto per secoli di una fama immeritata, essendo molto più debole di altri codici polialfabetici precedenti come il disco dell’Alberti, o le cifre del Bellaso. Tale fortuna è durata fino a molti decenni dopo che era stato pubblicato un primo metodo di decrittazione: quello del Kasiski; e altri metodi di crittanalisi sono possibili.
Dal cifrario di Vigenere deriva peraltro il Cifrario Vernam, considerato il cifrario matematicamente inviolabile.
Il metodo si può considerare una generalizzazione del codice di Cesare; invece di spostare sempre dello stesso numero di posti la lettera da cifrare, questa viene spostata di un numero di posti variabile, determinato in base ad una parola chiave, da concordarsi tra mittente e destinatario, e da scriversi sotto il messaggio, carattere per carattere; la parola è detta verme, per il motivo che, essendo in genere molto più corta del messaggio, deve essere ripetuta molte volte sotto questo, come nel seguente esempio:
TESTO CHIARO : arrivanoirinforzi
VERME : vermevermevermeve
TESTO CIFRATO : vviuzvrfuvdrwavum
Il testo cifrato si ottiene spostando la lettera chiara di un numero fisso di caratteri, pari al numero ordinale della lettera corrispondente del verme. Di fatto si esegue una somma aritmetica tra l’ordinale del chiaro (A = 0, B = 1, C = 2 …) e quello del verme; se si supera l’ultima lettera, la Z, si ricomincia dalla A, secondo la logica delle aritmetiche finite.
Per semplificare questa operazione il Vigénère propose l’uso della seguente tavola quadrata, composta da alfabeti ordinati spostati. Volendo ad esempio cifrare la prima R di ARRIVANO si individuerà la colonna della R, quindi si scenderà lungo la colonna fino alla riga corrispondente della corrispondente lettera del verme (qui E); la lettera trovata all’incrocio è la lettera cifrata (qui V); la seconda R invece sarà cifrata con la lettera trovata sulla riga della R di VERME, e cioé con la I.
Il vantaggio rispetto ai cifrari monoalfabetici è evidente: la stessa lettera del testo chiaro non è sempre cifrata con la stessa lettera; e questo rende più difficile l’analisi statistica del testo cifrato e la decrittazione.
Chi riceve il messaggio per decifrarlo deve semplicemente usare il metodo inverso (sottrarre invece che sommare); riferendosi all’esempio precedente si avrà:
TESTO CIFRATO : vviuzvrfuvdrwavum
VERME : vermevermevermeve
TESTO CHIARO : arrivanoirinforzi
Crittanalisi del cifrario di Vigenere: il metodo Kasiski
Il cifrario di Vigénère è stato per secoli considerato inattaccabile, ma si tratta in verità di una cifra piuttosto debole; consideriamo infatti l’esempio seguente:
TESTO CHIARO : arrivanoirinforzi
VERME : vermevermevermeve
TESTO CIFRATO : vviuzvrfuvdrwavum
Le due R di ARRIVANO vengono cifrate la prima con una V la seconda con una I come deve essere in un cifrario polialfabetico. Ma le due A vengono invece cifrate con la stessa lettera, la V. Come mai? Il motivo è evidente: le due A si trovano a cinque caratteri di distanza l’una dall’altra e cinque è proprio la lunghezza del verme! Di fatto il codice di Vigenere si riduce qui a cinque codici di Cesare intercalati.
Il primo a rendersi conto di questa debolezza del codice di Vigenere fu il colonnello prussiano Friedrich Kasiski, che nel 1863 pubblicò un metodo di decrittazione della tavola di Vigenere.
L’attacco Kasiski si basa sull’osservazione che in un crittogramma alla Vigenere si trovano spesso sequenze identiche di caratteri a una certa distanza l’una dell’altra; questo avviene evidentemente per il motivo esposto sopra; se p.es. usando la chiave VERME come sopra si scrive due volte la preposizione DEL a 30 caratteri di distanza questa sarà cifrata in modo identico essendo 30 un multiplo della lunghezza del verme che è 5.
Se, allora, si individuano tutte le sequenze ripetute (e in un testo lungo o in più testi se ne troveranno molte), allora, è pressochè certo che il massimo comun divisore tra le distanze tra sequenze identiche è la lunghezza della chiave, o tutt’al più un suo multiplo.
Una volta individuata la lunghezza n del verme, il messaggio si riduce a n messaggi intercalati, tutti cifrati con un codice di Cesare ed è allora molto facile completarne la decrittazione.
Dopo Kasiski sono stati individuati altri metodi per forzare il cifrario di Vigenere e in generale i cifrari polialfabetici; ne presentiamo uno basato sul metodo dei minimi quadrati.
La conclusione è che la cifra di Vigenere è affidabile solo quando il verme è di lunghezza comparabile a quella del testo e viene cambiato molto spesso, cosa che comporta problemi pratici non indifferenti (trasmissione e cambiamento della chiave richiedono un canale di comunicazione assolutamente sicuro).
Crittanalisi del cifrario di Vigenere con il 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.
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 crittanalista 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 è intuibile, 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 matematicamente inattaccabile. E anche questo metodo non può che fallire in questo caso.
Il cifrario di Vernam
Il cifrario di Vigenere ha il suo tallone d’Achille nel fatto di essere un insieme di cifrari di Cesare intercalati a distanza fissa, cosa che ne rende possibile e anzi molto facile la crittanalisi, tanto più se la chiave è breve.
Ben diversa sarebbe però la situazione se la chiave avesse lunghezza infinita o, che in fondo è lo stesso, fosse lunga come il testo chiaro (o meglio come la somma di tutti i testi in chiaro).
È questa l’idea proposta da G. S. Vernam nel 1926 per il cifrario che porta il suo nome; viene generata una chiave del tutto casuale, e dunque imprevedibile, lunga come il testo; a questo punto il chiaro e la chiave vengono “sommati” proprio come nel cifrario di Vigenere. L’unica differenza è che nel Vernam si sommano non tanto gli ordinali delle lettere da cifrare ma i singoli bit che codificano la lettera nei codici usati nelle telecomunicazioni (allora il codice Baudot, oggi codice ASCII) con l’operazione logica XOR. Questa è simile all’addizione, ma ha il vantaggio di essere reversibile, e quindi verrà usata anche per decifrare.
In tal modo la debolezza del Vigenere è superata e anzi Claude Shannon, il padre della Teoria dell’Informazione, ha dimostrato nel 1949 che ogni cifrario teoricamente sicuro è un cifrario di Vernam e viceversa. Infatti se la chiave è totalmente casuale e lunga come il testo allora il testo cifrato non contiene alcuna informazione sul testo chiaro, ed è del tutto al sicuro dagli attacchi della crittanalisi statistica.
Per avere una sicurezza assoluta non si dovrebbe mai riutilizzare la stessa chiave; se si utilizza più volte la stessa chiave infatti questa torna ad essere più breve del messaggio, o meglio della somma di tutti i messaggi e il cifrario non è più perfetto. Per questo motivo questo tipo di cifrario viene detto a blocco monouso o onetime pad.
Perché allora non usiamo tutti questo cifrario? Il problema è che la chiave lunga come il testo deve essere preventivamente comunicata al destinatario in modo sicuro e qui il gatto si morde la coda, visto che non sempre è disponibile un canale sicuro di comunicazione.
I due corrispondenti dovrebbero incontrarsi periodicamente in luogo sicuro e generare una sequenza casuale lunghissima, sufficiente per un gran numero di messaggi, da utilizzare un po’ alla volta. Una volta esaurita la chiave dovranno incontrarsi di nuovo, rigenerare la chiave etc.etc.
Per semplificare le cose si potrebbe pensare di generare la chiave in modo pseudo-casuale, secondo una qualche regola nota e riproducibile dal destinatario; questa idea diede luogo nel periodo tra le due guerre mondiali a una generazione di macchine cifranti, tra le quali la macchina Lorenz usata dai tedeschi nella II guerra mondiale. Ma così il cifrario non è più assolutamente sicuro, perché la chiave non è più realmente lunga come il testo, la vera chiave è la regola generatrice!. Tanto è vero che la macchina Lorenz fu forzata dagli inglesi sin dal 1941.
Nonostante queste difficoltà il cifrario di Vernam sembra sia stato usato effettivamente negli anni della guerra fredda dai servizi segreti dell’Est e per il telefono rosso tra Washington e Mosca. Un cifrario di Vernam era anche quello trovato addosso al Che Guevara dopo la sua uccisione nel 1967.
La macchina cifrante Enigma
Nel 1918 un giovane inventore tedesco Arthur Scherbius fondò, insieme al suo amico Richard Ritter, la Scherbius & Ritter, una società che era impegnata in diversi campi. Qui Arthur, a capo del settore ricerca e sviluppo, portò a compimento un progetto che avrebbe messo fine al predominio della carta e penna in crittografia: il risultato dei suoi sforzi fu la macchina Enigma, che sarebbe passata alla storia come uno dei più temibili sistemi crittografici mai realizzati.
In cosa consisteva la macchina cifrante Enigma?
La versione base consisteva in tre componenti collegati da fili elettrici:
- una tastiera per immettere le lettere del testo in chiaro;
- un’unità; scambiatrice che cifra le lettere trasformandole nei corrispondenti elementi del crittogramma;
- un visore con lamapadine che, accendendosi, indicano le lettere da inserire nel crittogramma.
Per generare il crittogramma l’operatore preme il tasto corrispondente alla lettera da cifrare; l’impulso elettrico raggiunge l’unita scambiatrice, e dopo essere stato eleborato va ad illuminare il visore in modo corrispondente alla lettera crittata. Lo scambiatore o rotore non è altro che uno spesso disco di gomma attraversato da una complessa rete di fili elettrici, che entrano nello scambiatore in 26 punti e dopo un percorso con vari gominti escono da altri 26 punti. Ma con questo schema di base, lo scambiatore definisce una semplice cifratura per sostituzione monoalfabetica, che, come abbiamo visto, era già stata violata da secoli. Ma è a questo punto che entrò in gioco l’inventiva di Scherbius, egli, infatti, fece si che lo scambiatore ruotasse automaticamente di 1/26 di giro dopo la cifratura di ogni lettera, ciò permetteva l’utilizzo di 26 alfabeti cifranti.
Questo sistema fece si che una lettera, nel medesimo crittogramma, venisse cifrata sempre in maniera diversa; Enigma operava, in questo modo, una cifratura per sostituzione polialfabetica.
Tuttavia, così come era nel progetto iniziale, lo scambiatore aveva un difetto di base, dopo 26 pressioni consecutive, ad esempio, della lettera A, il disco torna alla posizione iniziale, e se si continuasse a premere lo stesso tasto, lo schema di cifratura si ripeterebbe tale e quale; e la ripetitività è la bestia nera di ogni algoritmo di crittografia, perché essa significa regolarità e struttura del crittogramma.
Per aumentare il grado di sicurezza della sua creatura, Scherbius introdusse altri due scambiatori, che ruotavano così: il primo compiva un giro completo dopo la pressione di 26 tasti, il secondo dopo 26 giri completi del primo e il terzo dopo 26 giri completi del secondo; il funzionamento è quindi simile a quello di un contatore meccanico, salvo il fatto che l’inizio del giro di ogni rotore è segreto. Con l’introduzione degli altri due rotori, Scherbius fece si che la sua macchina cifrante potesse utilizzare 26 x 26 x 26 = 17.576 alfabeti cifranti, e ridusse di molto la possibilità di ripetizioni. Ma andò oltre, infatti, inserì un ulteriore elemento, il riflessore. Esso, era simile al rotore solo che non ruotava; inoltre i fili entravano e uscivano dal medesimo lato. Quindi il segnale elettrico attraversava i tre rotori, passava dal riflessore, e riattraversava i tre rotori per un percorso diverso per riemergere nel visore.
L’Enigma si svela
Dopo aver discusso della struttura interna dell’Enigma, adesso è giunto il momento di parlare di come gli Alleati riuscirono a violare la sua cifra. Prima di tutto, occorre analizzare come, gli addetti alla cifra tedeschi erano soliti utilizzare Enigma per cifrare i messaggi. Ciò è molto importante poiché proprio l’uso inattento di questo dispositivo contribuì a svelarne i segreti.
Supponiamo, quindi, che un operatore volesse inviare un messaggio cifrato. Prima di tutto egli doveva regolare i tre rotori in una delle 17.576 configurazioni possibili. Infatti la macchina Enigma può essere assimilata a un algoritmo crittografico. In tal caso, l’assetto iniziale di Enigma forniva ulteriori precisazioni necessarie alla cifratura, ossia equivaleva all chiave. Di solito, la posizione iniziale era contenuta in un cifrario, che forniva giorno per giorno l’assetto corretto per l’Enigma. Una volta che il messaggio era stato cifrato e trasmesso, tutto quello che doveva fare il destinatario era inserire il testo cifrato nell’Enigma perché si potesse leggere il testo in chiaro. Questa semplicità delle operazioni di cifratura/decifratura era dovuta al riflettore. Infatti se si inseriva la lettera V ed essa veniva cifrata con B, allora bastava inserire la lettera B perché sul visore comparisse la lettera V.
Chiaramente si nota che la segretezza aveva due punti deboli, uno era la segretezza dei cifrari, l’altra era la macchina Enigma stessa, infatti qualora gli alleati fossero venuti a conoscenza della struttura interna dei rotori, l’unica cosa che rimaneva da fare era provare tutte le 17.576 combinazioni possibili, per decifrare il testo; ammettendo che fosse stato possibile analizzare un assetto al minuto per tutto il giorno e la notte, sarebbero bastate due settimane per violare Enigma.
Fu a causa di ciò che Scherbius introdusse alcune varianti al progetto. Innanzitutto, rese i rotori removobili e sostituibili. Per esempio il primo e il terzo potevano scambiarsi i posti. Dati tre elementi intercombiabili essi possono essere combinati in 6 modi differenti; e questo quindi aumentava di un fattore 6 il numero di chiavi disponibili. Un’altra cambiamento che apportò fu l’inserimento di un pannello a prese multiple tra la tastiera e il primo rotore. Il pannello permetteva al mittente di inserire alcuni cavi muniti di spinotti, che avevano l’effetto di scambiare due lettere prima della loro immissione nel rotore. L’operatore di Enigma disponeva di sei cavi, che gli davano la possibilità di scambiare sei coppie di lettere. Le altre quattordici lettere restavano non collegate e non scambiate.
Con questi uleriori accorgimenti il numero di possibili chiavi era salito vertiginosamente. Con un rapido calcolo:
- 26 x 26 x 26 (= 17.576 combinazioni dovute ai tre rotori ruotanti)
- 17.576 x 6 (= 105.456 le combinazioni possibili cosiderando che 3 rotori potevano esserescambiati di posto)
- 105.456 x 100.391.791.500 ( quest’ultimo fattore dovuto allo scambiatore a prese multiple; infatti i possibili abbinamenti di 12 (6 x 2) lettere su 26 sono moltissimi.)
in totale quindi si ottiene esattamente 10.586.916.764.424.000 (più di 10 milioni di miliardi) di combinazioni.
Supponendo che un crittoanalista volesse far breccia in Enigma, con un attacco brute force, supponedo anche che potesse esaminare una chiave al minuto, notte e giorno, impiegherebbe un tempo superiore all’eta’ dell’universo per analizzare tutte le possibili combinazioni.
Nel settembre 1932 l’Ufficio cifra polacco chiamò tre matematici, Marian Rejewski, Henryk Zygalski e Jerzy Rozicki, con il compito di cercare di forzare la macchina Enigma usata dai tedeschi e da questi ultimi considerata inattaccabile. Sorprendentemente l’inattaccabile Enigma fu forzata nel giro di tre mesi, un po’ per merito dei tre matematici, un po’ per l’incredibile leggerezza delle procedure di cifra tedesche. Le procedure erano le seguenti: ogni giorno la chiave (disposizione e posizione iniziale dei rotori) doveva essere cambiata in base a una serie di regole segrete basate sulla data corrente. Inoltre ogni messaggio conteneva una ulteriore chiave segreta composta di tre caratteri; questa chiave veniva trasmessa all’inizio del messaggio stesso e per maggiore sicurezza veniva trasmessa due volte di seguito.
Questa idea di trasmettere due volte di seguito i tre caratteri segreti si rivelò essere una cubitale leggerezza che fornì un grosso appiglio al crittanalista. Dal punto di vista matematico l’Enigma si riduce infatti a un prodotto di permutazioni. Ora il fatto che il primo e il quarto carattere di ogni messaggio siano uguali rese possibile a Rejewski di ricostruire la permutazione AD (quella tra il primo e il quarto carattere del messaggio) nel giro di pochi giorni avendo a disposizione ogni giorno molte decine di messaggi cifrati con l’Enigma.
Se, ad esempio, abbiamo tre messaggi che iniziano con queste sei lettere:
#1: SDF GHJ ...
#2: GHZ UJP ...
#3: UKJ QDO ...
siamo in grado di ricostruire un frammento della permutazione AD;
infatti in #1. S diventa G, in #2. G diventa U, e in #3 U diventa Q. Dunque la sequenza SGUQ è parte della permutazione AD.
Analogamente la permutazione BE (tra il secondo e il quinto carattere) deve contenere la sequenza KDHJ, e insomma con un centinaio di messaggi si possono ricostruire completamente le tre permutazioni AD BE CF.
Questa naturalmente non è ancora la soluzione del problema; le permutazioni AD BE CF sono legate alle permutazioni dei rotori da un sistema di equazioni con 5 incognite: le permutazioni R S C D I ( indicando con R = riflettore, S = terzo rotore, C = il secondo rotore, D = il primo rotore, I = ingresso). Questo è un sistema ancora troppo complesso per essere risolto in modo univoco; considerando però che i rotori S, C e R girano raramente, li si può considerare come un unico blocco riflettore Q = CSRS^-1C^-1, riducento il numero di incognite a 3. Con tre incognite il problema non è ancora risolvibile in modo generale ma si è ormai vicini alla meta.
Un aiuto decisivo venne nel dicembre 1932 quando l’ufficio cifra francese venne in possesso della struttura del disco iniziale I e la comunicò ai colleghi polacchi. Con ormai solo due incognite Rejewski fu in grado di ricostruire completamente la permutazione D (rotore a destra) e grazie al fatto che i tedeschi cambiavano periodicamente la disposizione dei rotori, riuscì a ricostruire una dopo l’altra tutte e tre le permutazioni dei tre rotori e quindi l’intera struttura interna della macchina Enigma.
Una volta ricostruita questa struttura usando ancora la teoria delle permutazioni Rejewski progettò un dispositivo elettro-meccanico: il ciclometro che permetteva di ricostruire velocemente la posizione iniziale dei rotori; in seguito furono usati anche fogli perforati e le bombe crittologiche.
In definitiva sin dal dicembre 1932 fu possibile decrittare un buon numero di messaggi cifrati; nel 1937 fu stimata al 75% la percentuale di messaggi Enigma forzati dall’ufficio cifra polacco.
Tra il 1938 e il 1939, i tedeschi cambiarono le regole di cifratura e aumentarono il numero di rotori da 3 a 5 così che il metodo dei polacchi perse buona parte della sua efficacia. In quel periodo, la decrittazione di messaggi Enigma da parte dell’ufficio cifra polacco fu occasionale. Il lavoro dei polacchi fu, peraltro, ripreso, durante la seconda guerra mondiale, dall’ufficio cifra inglese, che perfezionò e migliorò i metodi di decrittazione dell’Enigma. Il 25 luglio 1939, nell’imminenza dell’attacco tedesco alla Polonia, si tenne, a Varsavia, una riunione tra gli uffici cifra polacchi, francesi e inglesi, nella quale i polacchi misero a disposizione degli alleati i loro metodi per forzare Enigma.
Nello stesso anno gli inglesi avevano trasferito nel villaggio di Bletchley Park, a metà strada tra Oxford e Cambridge, la sede del loro servizio di decrittazione, noto con il nome di Ultra. È singolare che Rejewski, nel frattempo fuggito in Francia, non sia mai stato invitato a partecipare a questo progetto.
Partecipava invece attivamente a Ultra il matematico inglese Alan Turing (1912-1954), noto soprattutto come padre dell’Informatica teorica per la sua Macchina di Turing, che ideò nuove e più efficienti bombe crittologiche così che Enigma fu nuovamente e sistematicamente forzata. Nel 1942 si arrivò a decrittare più di 80000 messaggi cifrati tedeschi al mese.
Questa impresa restò per molti anni coperta dal segreto militare e solo a partire dagli anni ’70 cominciò ad emergere la vera storia dell’Enigma e della sua decrittazione. Non è inverosimile che non tutti i dettagli siano stati resi pubblici. In particolare il ruolo dei polacchi fu riconosciuto pubblicamente solo nel 1989 in un discorso a Danzica dell’allora Presidente USA George Bush.
Contrariamente a quello che si legge su alcuni libri e siti web, non hanno viceversa nulla a che fare con la disfatta dell’Enigma i Colossi, vere e proprie macchine calcolatrici programmabili che furono progettati specificamente per forzare la ben più sofisticata macchina di Lorenz usata dagli alti comandi tedeschi. L’aver forzato, sin dall’inizio della guerra, Enigma (nonchè altri cifrari tedeschi e giapponesi) fu un fattore di grande importanza per la vittoria degli Alleati nella II guerra mondiale.
Fonti
- www.crittologia.eu (a cura di Paolo Bonavoglia)
- David Kahn, The Codebreakers. The story of secret writing, Scribner, New York (1996)
- Simon Singh, Codici & Segreti, Rizzoli, Milano (1999)
- Albrecht Beutelspacher - Luigia Berardi, Crittologia. Come proteggere le informazioni riservate, Franco Angeli, Milano (1996)