LA BOMBA DI TURING E BLENTCHEY PARKricerca.mat.uniroma3.it/.../critto09/seminari/BOMBA.pdf ·...
Transcript of LA BOMBA DI TURING E BLENTCHEY PARKricerca.mat.uniroma3.it/.../critto09/seminari/BOMBA.pdf ·...
12/05/2009
1
Piergiorgio Spalletta
La Bomba di Turing e Bletchley Park
Bletchley Park, anche nota come Stazione X,
è una proprietà situata a Bletchley, un paese
a circa 75 km a Nord-Ovest di Londra.
Durante la Seconda guerra mondiale,
Bletchley Park fu il sito dell'unità principale
di Crittoanalisi del Regno Unito.
I migliori matematici, fisici, linguisti, studiosi di statistica, campioni di scacchi
provenienti da ogni parte del mondo furono assoldati dal governo inglese per un totale di
3000 persone con lo scopo di decrittare le comunicazioni dell’asse.
Il lavoro di queste persone era coperto da segreto di stato ed è stato importantissimo per
la riuscita della guerra.
Dopo trent’anni dalla fine della guerra questi studiosi hanno avuto il permesso di poter
raccontare al mondo cosa è successo a Bletchley Park.
12/05/2009
2
Prima dello scoppio della guerra i decrittatori polacchi
grazie al lavoro di Marian Adam Rejewski avevano messo a
punto una macchina in grado di poter decrittare i messaggi
di Enigma chiamandola BOMBA.
Durante la guerra i tedeschi avevano cambiato il settaggio di Enigma
mediante l’ introduzione di nuove misure per aumentare la sicurezza della
macchina:
Due nuovi scambiatori.
Numero di cavetti del pannello a prese multiple passò da sei a dieci.
I materiali dei polacchi vengono trasferiti a Bletchley Park per proseguire gli studi al
fine di violare la nuova versione di Enigma.
Il 4 settembre del 1939 il giovane matematico inglese Alan Turing mise piede a
Bletchley Park quando era ricercatore presso il King’s Collage di Cambridge.
Poco appassionato al latino e alle Sacre Scritture,
preferiva le letture riguardanti la teoria della
Relatività, i calcoli astronomici, la chimica, o il gioco
degli scacchi.
Nel 1931 venne ammesso al King's College dell'Università di Cambridge dove studiò
meccanica quantistica, logica e la teoria della probabilità (dimostrò separatamente il
teorema del limite centrale, già dimostrato nel 1922 dal matematico Lindeberg).
Alan Mathison Turing (Londra, 23 giugno 1912 –
Wilmslow, 7 giugno 1954) è stato un matematico e
logico britannico. Considerato uno dei padri
dell'informatica, introdusse la macchina ideale ed il test
che portano il suo nome.
12/05/2009
3
Turing grazie all’aiuto del matematico Wenchelman e di altri ricercatori mise in piedi
una macchina in grado di decrittare le comunicazioni di Enigma.
La macchina era grande quanto un
armadio e pesava una tonnellata e mezza e
prese il nome di Bomba.
Grazie alla “bomba” le forze alleate erano
in grado di decrittare le comunicazioni
dell’asse.
Eseguiva una ricerca esaustiva tra tutte le
possibili combinazioni dell'Enigma.
•Confronto del testo in chiaro detto Crib e con la corrispondente porzione di testo cifrato
•Per posizionare correttamente il Crib sul suo testo cifrato si sfruttava la proprietà della
macchina Enigma di non cifrare mai un carattere con se stesso.
W E T T E R V O R H E R S A G E B I S K A Y AQ F ZWRW I V T Y R E S X B F OGK U HQ BAISEZ
Se una lettera è cifrata con se
stessa si procede spostando il
crib di una posizione e si fa un
nuovo confronto
W E T T E R VO R HE RSAGE B I S K A Y AQF Z WRW I V T Y R E SXBFOG KU HQ B A ISEZ
WE TTERVORHERS AGEB I S KA Y AQFZWRWIVTY RE S XBFOGKUHQ B A I S E Z
Configurazione corretta!!!
1 2 3 4 5 6 7 8 9 ... ...23W E T T E R V O R H E R S A G E B I S K A Y AR W I V T Y R E S X B F O G K U H Q B A I S E
Trovata la combinazione accettabile si numerano le varie coppie formate
12/05/2009
4
In questo menu è possibile notare che AGK così come AEIT formano un ciclo, questo
ciclo è alla base del lavoro degli inglesi.
Il menù si costruisce collegando una lettera del testo cifrato con la corrispondete lettera del
crib e indicando con un numero la posizione corrente della corrispondenza trovata.
Prendiamo in esame il loop E-A-I-T:
1)E supponiamo che sia scambiata dallo stecker in K, K verrà cifrata dai rotori in v1 e v1 infine scambiata in A
2)A: è scambiata dallo stecker in v1 (come da passo 1), v1 cifrata in v2 quindi scambiata in I
3)I: scambiata in v2 cifrata in v3 scambiata in T
4)T è scambiata in v3, v3 sarà cifrata in v4 e se v4 non corrisponde a K la nostra ipotesi iniziale sarebbe errata e, di conseguenza, la corrente configurazione dei rotori sarebbe da scartare e ne dovremmo provare una differente.
12/05/2009
5
Fila inferiore ad ogni rivoluzione completa
della seconda fila.
Fila superiore di tamburi veloce.
Fila media che ruotava ad ogni
rivoluzione completa della prima fila.
•La Bomba era una macchina capace di cercare la
combinazione corretta dei rotori tra tutte
le combinazioni possibili.
•Divisa in tre batterie ciascuna contenente dodici colonne
di tre tamburi ciascuna.
•Ogni tamburo rappresentava un rotore, quindi ogni
tripletta una intera macchina enigma.
• Nella fila veloce di tamburi entravano 26 fili (uno per ogni lettere dell’alfabeto), ed
eseguiva la permutazione del primo rotore.
• La prima fila era collegata con la seconda che eseguiva la permutazione del secondo rotore
• la seconda fila era collegata con la terza che eseguiva la permutazione del terzo rotore
quindi lo scambio del riflettore e nuovamente la permutazione del terzo rotore.
• Dal terzo rotore il segnale elettrico tornava indietro e subiva nuovamente le permutazioni
del secondo e del primo rotore, infine usciva dal primo tamburo.
12/05/2009
6
La tavola diagonale e si basava sul principio di reciprocità dello stecker: se A è scambiato
con B, B è sempre stato scambiato con A.
La tavola diagonale aveva come ingresso 26 cavi (ognuno per ogni lettera dell'alfabeto),
ciascun cavo contenente 26 fili anch'essi corrispondenti ad una lettera dell'alfabeto.
Se il filo b del cavo A è collegato con il filo a del cavo B vuol dire che la A è scambiata
dallo stecker con B e viceversa.
Per impostare la bomba con tavola diagonale abbiamo bisogno semplicemente di una coppia
crib-cifrato e per rendere leggibili gli schemi utilizziamo un alfabeto di 8 lettere (A..H)
1 2 3 4 5 6 7 8 9B E A C H H E A DE D B G E A H D B
Menu
corrispondente
12/05/2009
7
• Ogni riga si riferisce ad una tripletta di tamburi diversa, esclusa le ultime due che si
riferiscono alla stessa tripletta ma con velocità differenti dei tamburi.
• La prima colonna (TAMBURO) indica il tamburo che deve essere posizionato come indicato
dalla quarta colonna (LETTERA INIZIALE).
• La seconda (CAVI CONNESSI) indica quali cavi della tavola diagonale la tripletta deve collegare, i
due cavi collegati sono indicati dalla coppia corrispondente all'indice indicato dalla terza
colonna (POSIZIONE) nel crib-cifrato.
La bomba veniva configurata nel seguente modo:
Sul cavo corrispondente alla lettera più frequente era posto un registro di test, in
grado di contare il numero di fili in cui c'era corrente (fili vivi).
12/05/2009
8
Una volta configurata, la bomba era messa in funzione quindi si faceva fluire corrente
su ciascun filo, se il registro di test contava più fili vivi allora la configurazione era da
scartare.
La disposizione dei rotori non andava bene perché se fluisce corrente nel filo b del cavo
A (ovvero nel filo a del cavo B), vuol dire che A e B sono scambiate dallo stecker, e una
lettera può essere scambiata solo ed esclusivamente con solamente un'altra, perciò se il
registro contava più fili vivi, voleva dire che non si aveva uno scambio univoco,
quindi una disposizione dei rotori non valida.
Gli Stop
Una configurazione era corretta se:
• Il registro di test contava un solo filo vivo,configurazione corretta e ipotesi iniziale
corretta
• Il registro di test contava un solo filo morto, configurazione corretta e ipotesi
iniziale errata
Nel 1941 fu intercettato e decodificato un messaggio radio
che annunciava entro una certa data il bombardamento
di Coventry, una città sulla costa inglese. Churchill si
trovò di fronte a un delicato dilemma: dando l'ordine di
evacuazione alla città, avrebbe fatto capire ai tedeschi che
i loro messaggi crittografati non erano più segreti per gli
inglesi. Morirono circa 2000 persone per salvaguardare la
segretezza della bomba.
12/05/2009
9
Il lavoro dei 3.000 studiosi non fu mai reso noto come meritava per evidenti
motivi di segretezza, e probabilmente oggi possiamo affermare che lì si svolse
una delle battaglie più importanti per le sorti del mondo, una battaglia di
intelletti, di tentativi, di coraggio, e di grandissima passione.
Alan Turing la cui storia terminò drammaticamente appena 9 anni dopo la fine
della guerra quando si suicidò mangiando una mela avvelenata la quale
successivamente divenne il simbolo di una nota marca di computer.
Grazie dell’ attenzione