Breaking The Enigma

Many years ago, the world was at war. The very best minds were focussed on out-smarting the "other side", all without the aid of our modern computational tools.

The key was in communication, and the Nazis had devised a simple and effective way to relay orders to the battlefront. They were using one of the most famous forms of electronic encryption: the Enigma.

Breaking this Enigma was a victory built on the tireless work of many people, not least of all the persecuted and brilliant Alan Turing.

In this talk we will learn how the enigma worked, and how it was broken.

Transcript

1. Turing Breaking)The)Enigma
2. Early&Life
3. Turing's)fond)of)the)football)field, for)geometric)problems)the) touchlines)yield
4. For,%of%course,%the%body%is%a% machine.%It%is%a%vastly%complex% machine,%many,%many%:mes%more% complicated%than%any%machine%ever% made%with%hands;%but%s:ll%a=er%all%a% machine
5. Personally*I*think*that*spirit*is*really* eternally*connected*with*ma5er*but* certainly*not*always*by*the*same* kind*of*body...
6. ...I#did#believe#it#possible#for#a#spirit# at#death#to#go#to#a#universe#en5rely# separate#from#our#own,#but#I#now# consider#that#ma;er#and#spirit#are#so# connected#that#this#would#be#a# contradic5on#in#terms
7. Theory'Of'Computa0on
8. Any$effec(vely$generated$theory$ capable$of$expressing$elementary$ arithme(c$cannot$be$both$ consistent$and$complete
9. The$behaviour$of$the$computer$at$ any$moment$is$determined$by$the$ symbols$which$he$is$observing,$and$ his$'state$of$mind'$at$that$moment...
10. ...We$will$also$suppose$that$the$ number$of$states$of$mind$which$ need$to$be$taken$into$account$is$ finite
11. A"machine"which"can"read"a" character"at"a"known"point,"and" op2onally"change"state
12. A"machine"which"can"write"a" character"at"a"known"point," op1onally"change"state
13. A"machine"which"can"move"to"any" known"point"on"a"tape
14. $automaton = new Automaton( 1, // initial state [2], // acceptable, final states new Rulebook([ new Rule(1, "a", 1), new Rule(1, "b", 2), new Rule(2, "b", 2), new Rule(2, "a", 1), ]) )
15. assertFalse( $automaton->hasAcceptableState() ); $automaton->readCharacter("a")->readCharacter("b"); assertTrue( $automaton->hasAcceptableState() );
16. github.com/turingphp
17. new Rulebook([ new Rule(1, "a", 1), new Rule(1, "b", 2), new Rule(2, "b", 2), new Rule(2, "a", 1), ]) Given&the&sequence&ababb: Start%in%state%1 Read%a%and%stay%in%state%1 Read%b%and%move%to%state%2 Read%a%and%move%to%state%1 Read%b%and%move%to%state%2 Read%b%and%stay%in%state%2
18. All#complex#machines#can#be# defined#in#terms#of#the#simplest# Determinis6c#Finite#Automaton
19. Understanding+Computa1on, by+Tom+Stuart
20. Enigma
23. $machine = new Machine( [ new Rotor( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "EKMFLGDQVZNTOWYHXUSPAIBRCJ", 0 ), new Rotor( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "AJDKSIRUXBLHWTMCQGZNPYFVOE", 0 ), new Rotor( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "BDFHJLCPRTXVZNYEIWGAKMUSQO", 0 ) ], new Reflector( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "FVPJIAOYEDRZXWGCTKUQSBNMHL" ) );
24. // first rotor new Rotor( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "EKMFLGDQVZNTOWYHXUSPAIBRCJ", 0 )
25. EKMFLG...IBRCJ-→-KMFLG...BRCJE
26. // second rotor new Rotor( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "AJDKSIRUXBLHWTMCQGZNPYFVOE", 0 )
27. // third rotor new Rotor( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "BDFHJLCPRTXVZNYEIWGAKMUSQO", 0 )
28. new Reflector( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "FVPJIAOYEDRZXWGCTKUQSBNMHL" )
29. And$the$return$trip: B"→"A"→"A"→"T So#we#press#A#and#T#lights#up...
30. A!→!K!→!L!→!V!→!B!→!A!→!A!→!T T!→!A!→!A!→!B!→!V!→!L!→!K!→!A
31. So#long#as#the#rotors#are#in#the#same# posi0on#at#the#start#of#each# message...
32. 5"x"4"x"3"x"26³"="1"054"560
33. 1.58%x%10²⁰%on%newer%models...
34. Bombe
35. No#le&er#can#produce#itself#as# output
36. Guess%a%phrase
37. Slide&the&phrase&along&the&coded& le1ers&un3l&there&are&no&conflicts
38. Brute&force*se,ngs
39. Bombe&could&a,empt&all& permuta0ons&in&20&minutes
40. Conclusion
41. Thanks @assertchris