Dalla crittografia ad Enigma

.

Qualche giorno fa ho visto in Tv il film “The imitation game” https://it.wikipedia.org/wiki/The_Imitation_Game , affascinato dalla trama ho voluto approfondire l’argomento e ne è uscito questo articolo.

Partiamo dalla base della cifratura, Il cifrario di Leon Battista Alberti, https://it.wikipedia.org/wiki/Disco_cifrante pensato appositamente per il Vaticano per l’invio di messaggi dati a corrieri, era composto da una coppia di cerchi concentrici di cui il cerchio esterno fisso, mentre quello interno mobile. Sul cerchio più esterno si trovavano i numeri da 1 a 4 e le lettere dell’alfabeto, ad esclusione delle lettere H, J, Q, W e Y che per la loro bassa frequenza di utilizzo avrebbero sicuramente indebolito il cifrario.

Nel cerchio esterno quindi abbiamo 24 caselle con i numeri da 1 a 4 e le lettere dell’alfabeto in ordine, mentre nel disco interno, mobile, abbiamo 24 caselle contenenti le lettere dell’alfabeto in disordine che rappresentano il testo cifrato (vedi figura 1).

Funzionamento: Si sceglie una lettera maiuscola dell’anello esterno come indice fisso. In questo esempio all’indice B viene inizialmente sottoposta la s del cerchio mobile. Per indicare il cambio dell’alfabeto si cifra uno dei quattro numeri.

ora la codifica sarà

A questo punto la presenza della z, che cifra il numero 2, segnala la necessità di spostare i dischi portando la z sotto la B.

La cifratura continuerà così:

Il testo trasmesso sarà pertanto syamynpfaz zmh&fohmef altro aiuto è la  
eliminazione delle doppie e degli spazi tra le parole della frase criptata per 
rendere ancora più sicuro il messaggio.

In seguito gli studi di Leon Battista Alberti furono ripresi da altri studiosi, che, con alterne fortune, cercarono di perfezionare il più possibile la geniale intuizione dei cifrari polialfabetici.

LE MACCHINE CIFRANTI

I cifrari polialfabetici sono alla base delle più famose macchine cifranti. La più famosa macchina crittografica mai costruita è Enigma. Tale dispositivo elettromeccanico era la macchina cifrante realizzata e utilizzata dal Terzo Reich negli anni precedenti e durante il secondo Conflitto Mondiale. Il fine di questa macchina era elevare il livello di sicurezza e rendere il significato dei messaggi non intelligibile a persone non autorizzate, la macchina veniva adoperata per “mascherare” un messaggio che un operatore telegrafico mandava ad un altro, cifrandone il contenuto. Quando un operatore utilizzava la macchina, digitava le lettere che costituivano il messaggio sulla tastiera e i meccanismi interni della stessa attraverso l’accensione della 

lettera equivalente trasformavano quel testo da trasmettere in un altro apparentemente incomprensibile. La decodifica la fa la stessa macchina a disposizione del ricevente. La trattazione parte dal funzionamento base della macchina, per passare alla realtà storica dell’utilizzo, fino ai diversi miglioramenti tecnici apportati e gli esperienti escogitati per risolvere i problemi da essi derivanti. Gli inventori di tale 

macchina furono Arthur Scherbius e Richard Ritter nel 1918. Il primo, Ingegnere Elettrico, mise in pratica le conoscenze acquisite presso l’Università di Hannover e realizzò con Ritter una riproduzione elettromeccanica del disco cifrante di Leon Battista Alberti.

FUNZIONAMENTO DI ENIGMA

https://youtu.be/EVvrSjah9t0

La macchina ha principi di costruzione modulari, quindi nel tempo rivelò la possibilità di montaggi alternativi e di conseguenza diversi funzionamenti. La versione base del dispositivo era costituita da tre gruppi di componenti collegati tra loro con fili elettrici:

A) una tastiera per immettere le lettere del testo in chiaro;

B) un’unità scambiatrice che cifra la lettera trasformandola nel corrispondente elemento del crittogramma mediante un sistema a dischi;

C) un visore con varie lampadine che illuminandosi indicano le lettere del corrispondente testo cifrato.

In pratica l’operatore preme il tasto corrispondente ad una lettera del testo in chiaro, la macchina elabora l’impulso elettrico ricevuto e fa illuminare la lampadina corrispondente alla lettera cifrata. La parte più importante della macchina è il singolo scambiatore, rappresentato da uno dei 3 dischi che formano l’unità scambiatrice di cui sopra.

Tale disco caratterizzato da 26 tacche conduttive in ingresso e 26 tacche conduttive in uscita, è attraversato da una fitta rete di fili interni che uniscono gli ingressi con le uscite.

Lo schema dei cablaggi interni dello scambiatore determina in pratica un alfabeto cifrante utilizzabile per una semplice cifratura a sostituzione in cui alla pressione

di un tasto corrisponde l’accensione di una lampadina indicante la lettera corrispondente.

Il passo successivo dell’idea di Scherbius prevedeva di far ruotare il disco dello scambiatore di una posizione dopo la cifratura di ogni singola lettera, in tal modo l’alfabeto cifrante cambia dopo ogni lettera trasformando la cifratura monoalfabetica in una polialfabetica. 

L’unità scambiatrice è formata da 3 dischi, essi sono collegati a due a due attraverso le 26 tacche conduttive, in più a monte della pila dei tre dischi c’è un disco fisso che a sua volta ha 26 tacche collegate ognuna con la tastiera e con un sistema di lampadine, mentre in fondo alla pila c’è un ultimo disco detto riflessore, in cui le tacche sono collegate a due a due mediante tredici fili interni. Ciò comporta che il circuito elettrico si chiude ogni volta che si batte una lettera della tastiera, così che attraverso i contatti elettrici dei vari dischi ogni lettera viene cifrata sette volte, visto che la funzione del riflessore è quella di riflettere indietro il segnale (vedi figura 8).

La disciplina di funzionamento degli altri dischi in termini di rotazione, era che il secondo compiva una rotazione parziale soltanto dopo che il primo aveva compiuto un intero giro, e allo stesso modo faceva il terzo basandosi sul secondo. In questo modo la macchina di Scherbius poteva disporre di 26x26x26 = 17576 procedure di sostituzione diverse.

INQUADRIAMO IL FUNZIONAMENTO DI ENIGMA

Il primo parametro da specificare è il posizionamento degli scambiatori secondo un certo assetto prima di iniziare la cifratura di un messaggio, tale settaggio rappresentava una vera e propria chiave (Figura 6). Per cifrare un messaggio un operatore Enigma posizionava gli scambiatori secondo la chiave giornaliera, digitava il messaggio sulla tastiera della macchina e spediva via radio il risultato al destinatario. Quest’ultimo digitava il messaggio cifrato sulla tastiera della sua macchina Enigma, sulla quale gli scambiatori erano sistemati secondo la stessa chiave giornaliera usata in precedenza, e otteneva il messaggio in chiaro. La semplicità con cui questa operazione era dovuta proprio all’introduzione del riflessore, questa era uno dei punti di rapida diffusione di tale sistema, l’uso cosi semplice lo rendeva adatto a chiunque. Il livello di sicurezza raggiunto con Enigma, non era dato dalla complessità della macchina, ma dall’elevato numero di combinazioni che un nemico avrebbe dovuto controllare per ottenere l’assetto iniziale. Infatti ipotizzando di provare una chiave al minuto ci sarebbero volute due settimane per scoprire la chiave di un solo giorno. Il tutto fu ancora migliorato attraverso due modifiche sostanziali, la prima modifica era circa gli scambiatori che furono costruiti in modo da essere rimovibili così da poterli sostituire con altri o scambiarli tra loro. Questo accorgimento aumentava il numero di chiavi di un fattore pari a 6, in quanto 3 elementi intercambiabili possono essere combinati in 6 modi diversi. La seconda evoluzione fu l’inserimento di un pannello a prese multiple tra la tastiera ed il primo rotore (vedi fig. 7).

Il mittente attraverso tale pannello poteva inserire alcuni cavi con degli spinotti in modo da scambiare due lettere prima dell’immissione nell’unità di scambio, il numero di scambi effettuabili erano sei su ventisei lettere, quindi le altre venti lettere restano non scambiate. Possiamo, quindi, cercare di fare un riepilogo circa la complessità computazionale di tale macchina, in termini di numero di combinazioni di chiavi che dovevano essere generate per operare un attacco a forza bruta: gli scambiatori (o rotori) potevano orientarsi ognuno in 26 modi, quindi tutti e tre generavano 26x26x26 = 17576 combinazioni; poi all’interno dell’unità cifratrice i tre scambiatori potevano essere inseriti in diverse posizioni reciproche, così riassumibili: 123, 132, 213, 231, 312, 321. Erano quindi ammesse 6 diverse posizioni reciproche dei rotori; infine con il pannello a prese multiple i possibili abbinamenti di 12 (6×2) lettere su 26 sono moltissimi (per l’esattezza 100.391.791.500). Quindi il numero totale di chiavi si ottiene moltiplicando tra loro le suddette possibilità:

17.576 x 6 x 100.391.791.500 = circa 10 milioni di miliardi.

Nonostante fosse formata da elementi semplici, dunque, la combinazione di questi ultimi produceva una macchina cifrante ad alta complessità computazionale con una complessità di costruzione non elevatissima. Inizialmente tale invenzione non ottenne una grande diffusione, il costo elevato e la non effettiva comprensione delle possibilità erano le cause principali. Alla fine i militari tedeschi per prevenire il vantaggio che la Regia Marina inglese ebbe dall’intercettazione delle loro comunicazioni cifrate durante la Prima Guerra Mondiale, decisero di adottare Enigma. Nel 1925 fu organizzata la produzione in serie e nei due decenni successivi le forze armate tedesche ebbero a disposizione ben 30000 esemplari.

I PRIMI TENTATIVI DI CRITTOANALISI: IL BIURO SZYFROW

La coalizione che vinse la Prima Grande Guerra si disinteressò delle comunicazioni degli sconfitti. L’attività di monitoraggio quasi si bloccò del tutto nel 1926, proprio in coincidenza dell’inizio dell’utilizzo di Enigma. Solo la Polonia, stretta tra Germania e Russia, si occupò di operare una costante e duratura azione di monitoraggio delle comunicazioni

della Germania. In particolare un ufficio chiamato Biuro Szyfrow, l’ufficio cifre polacco, si occupò dell’analisi dei messaggi e fu il primo gruppo di lavoro creato per fronteggiare la codifica operata con Enigma. Il lavoro ebbe pochi risultati incoraggianti, almeno all’inizio, fino al novembre del 1931, grazie ad un lavoro di spionaggio fu in grado di produrre una replica della versione militare di Enigma. L’inizio di un lavoro assai sfiancante in quanto la sicurezza offerta da Enigma era rappresentata non dalla macchina in se stessa, ma dall’elevatissimo numero di combinazioni da controllare per trovare la chiave giornaliera. Venne poi adottata una nuova chiave per ogni messaggio, detta chiave di messaggio. Tale chiave veniva trasmessa usando l’assetto indicato dalla chiave giornaliera e ripetuta due volte di seguito all’inizio del messaggio, ripetizione usata per decodificare Enigma da parte dei nemici. Quindi tale chiave di messaggio veniva usata per regolare il nuovo assetto della macchina per il singolo messaggio. Ad esempio se la chiave giornaliera era FBK e la chiave di messaggio VHB (entrambe indicano un orientamento degli scambiatori), l’operatore mittente avrebbe digitato VHBVHB come inizio del messaggio in chiaro. Cifrando il messaggio quelle lettere sarebbero diventate poniamo GHUBJE (da notare che la prima metà della stringa è diversa dalle seconda perché Enigma modificava automaticamente l’assetto degli scambiatori dopo ogni lettera). Dopo aver cifrato la chiave di messaggio l’operatore posizionava gli scambiatori su VHB e cifrava il messaggio vero e proprio. Il destinatario regolava la macchina su FBK, la chiave giornaliera, e decifrava le prime sei lettere del messaggio ricevuto, quindi ricavata la chiave di messaggio, posizionava gli scambiatori su VHB e poteva decifrare il testo. In seguito i responsabili del Biuro Szyfrow decisero di reclutare dei matematici per fare ricerca per decifrare i messaggi prodotti da Enigma. Scelsero tali matematici organizzando un corso di crittografia all’Università di Poznan, il più brillante era senza dubbio il giovane Marian Rejewski (figura 9).

Dopo un breve periodo di apprendistato Rejewski venne messo al lavoro su Enigma. La cosa sorprendente è che nel giro di tre mesi grazie alla leggerezza della doppia ripetizione della chiave di messaggio all’inizio della comunicazione si riuscì a venire a capo della decifratura dei primi messaggi. La principale ripetizione nei messaggi era la chiave di messaggio che veniva cifrata due volte di seguito all’inizio di ogni comunicazione. Questo significava che la prima e la quarta lettera erano legate strettamente alla posizione degli scambiatori, così come la seconda e la quinta e la terza e la sesta. Man mano che venivano intercettati nuovi messaggi Rejewski aveva materiale per completare una tabella delle corrispondenze. Grazie ad esse si riuscì a decriptare i messaggi in maniera semplice. Successivamente Rejewski riuscì a progettare, adattando alcune delle copie di Enigma a sua disposizione, un congegno che automatizzava la ricerca della chiave giornaliera controllando rapidamente le 17576 combinazioni per trovare le posizioni dei rotori degli scambiatori. Questi congegni erano chiamati “bombe” e, poiché gli scambiatori potevano essere posti in sei posizioni diverse occorrevano sei “bombe” che funzionavano in parallelo. Così come Enigma aveva rappresentato l’automazione del processo di cifratura, così le “bombe” di Rejewski rappresentavano l’automatismo della decifratura. Alla fine del 1938 i successi polacchi nel decifrare i messaggi Enigma subirono una pesante battuta d’arresto dovuta all’introduzione di nuove misure per aumentare la sicurezza della macchina. Infatti 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 decodifica di messaggi Enigma da parte dell’ufficio cifre polacco fu occasionale.

Con i nuovi scambiatori il numero delle combinazioni passava da 6 a 60 il che rendeva necessaria la costruzione di altre 54 “bombe”, cosa che risultava impossibile per il bilancio del Biuro Szyfrow. Inoltre con le aggiunte al pannello a prese multiple le lettere scambiate passavano da dodici a venti su ventisei portando il numero di possibili chiavi a 159 miliardi di miliardi. In seguito a causa del precipitare degli eventi quando la guerra divenne sempre più inevitabile al Biuro Szyfrow si decise di rivelare i progressi fatti su Enigma, fino ad allora segreti, così da permettere agli alleati più potenti e ricchi come Francia e Inghilterra, di tentare di proseguire il lavoro, impedendo ai tedeschi di scoprire i risultati ottenuti, così nacque il gruppo di crittoanalisti di Bletchley Park.

 BLETCHLEY PARK

Alla metà del 1939 gli studi di crittoanalisi furono spostati in Inghilterra presso una residenza nel Buckinghamshire che si chiamava Blechley Park. In tale località fu posta la sede della Government Code and Cypher School (GC&CS). 

L’organizzazione interna era basata sul singolo ufficio che si occupava di un certo argomento, quindi fu definita una divisione in “Capanne”. Ad ogni capanna corrispondeva un numero e un compito diverso, per esempio alla Capanna 6 competeva la decifrazione dei messaggi di Enigma. Il numero di persone impiegate in tale servizio passarono dai duecento del 1939 a circa settemila della fine del conflitto. Gli studi condotti presso la Capanna 6 furono di vitale importanza, basti pensare che durante la Battaglia d’Inghilterra i crittoanalisti furono spesso in grado di fornire ai comandi della RAF il luogo e il momento delle incursioni tedesche. Partendo dalle nozioni trasmesse dai crittoanalisti polacchi, i colleghi inglesi riuscirono a trovare altre falle che facilitassero la scoperta della chiave giornaliera, che denominarono “cillies”. Un “cilly” era una falla di Enigma non legata alla costruzione della macchina, ma agli utilizzi errati che se ne faceva. Molti operatori usavano come chiave di messaggio tre lettere adiacenti sulla tastiera, cosa che rendeva più semplice intuire la chiave stessa. Altri errori furono ad opera dei responsabili della compilazione dei cifrari che cercando di rendere le chiavi più difficili da prevedere, imposero delle limitazioni al numero di chiavi stesse. Stabilirono che nessuno scambiatore potesse occupare la stessa posizione per due giorni consecutivi e che ogni lettera non dovesse essere scambiata con quella che la precede e/o la segue. Queste disposizioni portarono ad una riduzione di oltre il cinquanta per cento del numero di posizionamenti degli scambiatori e ad una notevole facilitazione per i crittoanalisti inglesi. La situazione della crittoanalisi di Enigma si rese più critica a causa della continua evoluzione che ebbe la macchina nel suo utilizzo, ci fu un enorme sforzo da parte di tutti gli impiegati della CG&CS e tra questi l’impiegato che diede il contributo più significativo alla sconfitta di Enigma fu Alan Turing, più noto per i suoi studi sui problemi indecidibili e sul suo risolutore algoritmico universale, anticipazione teorica dei moderni calcolatori.

Turing ebbe la grande intuizione di fondare un nuovo metodo di crittoanalisi sul fatto che molti dei messaggi che venivano intercettati avevano una struttura piuttosto rigida e spesso capitava che messaggi che venivano trasmessi periodicamente (come ad esempio i bollettini meteorologici) avevano le stesse parole in posizioni fisse. Ad esempio le prime sei lettere del secondo rigo di alcuni tipi di messaggi corrispondevano alla parola “wetter” (tempo atmosferico). Questo costituiva ciò che in gergo dei crittoanalisti venne definito “crib”, cioè un frammento del testo in chiaro che può essere dedotto in base a considerazioni non crittoanalitiche. 

Turing si concentrò su un crib in particolare e anche in questo caso scoprì delle concatenazioni, che però riguardavano le lettere del testo in chiaro e del testo cifrato nell’ambito di un crib.

In figura 13 è mostrato un possibile crib e la sua concatenazione. Analizzando la concatenazione in figura è possibile individuare che nell’assetto “a”, Enigma cifra “w” come “E”, mentre nell’assetto “a+1”, Enigma cifra “e” come “T”, infine nell’assetto “a+3”, Enigma cifra “t” come “W”. A partire da questo semplice esempio Turing sviluppò tutte le implicazioni dei rapporti all’interno del ciclo e in base a questo progettò un circuito elettrico che collegava tre macchine Enigma con cavi posti tra l’input di una macchina e l’output della successiva seguendo lo schema logico mostrato in figura 14.

Questo schema realizzava un procedimento automatico di verifica attraverso la lampadina che si sarebbe accesa quando il corretto assetto fosse stato trovato. Si noti che in figura è rappresentato lo schema del circuito determinati i collegamenti imposti nei pannelli a prese multiple, cosa che al momento della crittoanalisi, risulta un dato non conosciuto, quindi il circuito doveva essere costruito in modo da annullare gli effetti del pannello a prese multiple, in quanto bisognava solo collegare l’output del primo gruppo di scambiatori con l’input del secondo gruppo in corrispondenza di L1. Poiché questo valore non era noto era necessario collegare le 26 uscite del primo gruppo con i 26 ingressi del secondo formando 26 circuiti, ciascuno dotato di una lampadina per evidenziarne la chiusura. Alla fine, scoperto il giusto orientamento degli scambiatori, uno dei circuiti si chiudeva causando l’accensione della lampadina. Ma fino ad ora non abbiamo ancora considerato la possibilità di scambio dei rotori. Ipotizziamo che gli scambiatori mutassero orientamento ogni secondo, per completare l’operazione di controllo di tutti gli orientamenti ci sarebbero volute cinque ore, in più per realizzare questo controllo ci sarebbe bisogno di un certo parallelismo. Quindi se i rotori utilizzati erano cinque e le macchine cifranti a disposizione ne contenevano tre con 60 combinazioni, si calcolò che per controllare tutte le disposizioni

erano necessari 60 gruppi di tre macchine da far lavorare in parallelo. Altro aspetto da considerare è che per determinare l’assetto del pannello a prese multiple bisognava operare a partire da crittogrammi parzialmente decifrati. Abbiamo tratteggiato le caratteristiche principali di quelle che furono dette le “bombe di Turing”, tali macchine ebbero un costo medio di 100000 sterline e furono completamente realizzate per la prima volta per l’inizio del 1940. Ogni bomba era composta da dodici gruppi di scambiatori Enigma collegati elettricamente. Il primo prototipo non funzionò molto bene e il completamento delle costruzione coincise con alcune notevoli variazioni nell’utilizzo di Enigma, principalmente si smise di ripetere le chiavi di messaggio, ciò portò alla costruzione di una versione migliorata delle bombe denominata “Agnus Dei”.

Tale versione di bomba di Turing aveva la possibilità di risalire ad una chiave giornaliera in una sessantina di minuti al massimo, ma il suo funzionamento non era completamente autonomo e indipendente dal personale che lo utilizzava. Il problema principale della macchina era il bisogno di partire da un “crib”, che però era solo su un’ipotesi che i crittoanalisti facevano, immaginando che una certa parola in chiaro potesse trovarsi in una certa posizione. Nell’ipotesi in cui ci fosse un errore nella predizione del crib, era possibile accorgersi di tale errore analizzando l’ipotetico testo in chiaro e il testo cifrato. Per capire il processo facciamo un esempio, nel crib seguente il testo in chiaro fa parte del crittogramma ma non si ha la sicurezza di averlo collegato alle lettere giuste.

La cosa che poteva aiutare a capire che la predizione era errata, era l’allineamento tra le lettere, il riflessore di Enigma non permetteva ad una lettera di essere cifrata come se stessa, quindi nell’esempio considerato ci deve essere un allineamento sbagliato, poiché si sovrappongono una “e” in chiaro e una “E” cifrata. Le cose non cambiano spostando la prima riga di una posizione a sinistra, ma effettuando lo spostamento verso destra si trova un allineamento ammissibile e che poteva quindi essere utilizzato per la ricerca automatica della chiave giornaliera.

BIBLIOGRAFIA

• Museo di Enigma del Prof. Tom Perera Ph. D. http://w1tp.com/enigma

• Marian Rejewski – An Application of the Theory of Permutations in Breaking the Enigma Cipher – 1977: http://www.impan.gov.pl/Great/Rejewski/article.html

• Vita di Alan Turing: http://www.turing.org.uk/

• On Enigma and a method for its decryption: http://www.cs.miami.edu/home/harald/enigma/