11
|
9254 Views
|
10 Replies
|
23 Total Likes
View groups...
Share
GROUPS:

# Computational implementation of the German Enigma Machine

Posted 7 years ago
 Below is an implementation of the German Enigma Machine which the German forces used to communicate encrypted messages during WWII. The machine was an ingenious design. It used a series of rotors and an elaborate electromechanical coupling to encrypt messages in German. About the mechanism, the first rotor moved with each click of the keyboard; the second rotor moved once the first rotor completed 26 moves or one complete turn; and the third rotor once the first moved 26*26 steps (one can easily understand where this is going). Since the rotors could move during the encryption process the key to deciphering the text was the "key" or the initial state of the rotors. The code was finally broken by a team of cryptographers at Bletchley Park led by Alan Turing. Some believe this caused the war to shorten by a few years. A movie titled "The Imitation Game" was released in 2014 highlighting this code breaking feat. ClearAll@rotateWheel; SetAttributes[rotateWheel, HoldFirst]; rotateWheel[wheel_] := Block[{}, wheel = RotateLeft[wheel]];  The immediate block of code above enables me to make in-place modification i.e. to rotate and preserve the state of the rotors. EnigmaEncryption[string_, staterot1_, staterot2_, staterot3_] := Module[{count = 0, RotorIn, leftRotor, middleRotor, rightRotor, reflector, reflectorOutput, rotateMiddleCheck, rotateRightCheck, inputToNext, reverseOutput}, RotorIn = ToLowerCase@CharacterRange["A", "Z"]; {leftRotor, middleRotor, rightRotor} = MapThread[Function[{x, y}, (z \[Function] RotateLeft[z, First@Position[z, ToLowerCase@y] - 1])@ Characters@ToLowerCase[x]], {{"BDFHJLCPRTXVZNYEIWGAKMUSQO", "AJDKSIRUXBLHWTMCQGZNPYFVOE", "EKMFLGDQVZNTOWYHXUSPAIBRCJ"}, {staterot1, staterot2, staterot3}}]; reflector = Characters@ToLowerCase@"YRUHQSLDPXNGOKMIEBFZCWVJAT"; inputToNext[rotor_, input_] := First@Cases[Thread[{RotorIn, rotor}], {input, map_} :> map ]; reverseOutput[rotor_, input_] := First@Cases[Thread[{RotorIn, rotor}], {map_, input} :> map ]; rotateMiddleCheck := If[count~Mod~26 == 0, rotateWheel@middleRotor, middleRotor]; rotateRightCheck := If[count~Mod~676 == 0, rotateWheel@rightRotor, rightRotor]; StringJoin@Table[ If[FreeQ[input, Alternatives[" ", ",", "'", "?" ]], count += 1; reflectorOutput = Fold[inputToNext[#2, #1] &, input, {rotateWheel@leftRotor, rotateMiddleCheck, rotateRightCheck, reflector}]; Fold[reverseOutput[#2, #1] &, reflectorOutput, {rightRotor, middleRotor, leftRotor}], input] , {input, Characters@ToLowerCase@string}] ]  Now lets assume that the Germans encrypt a message with state "A", "A","A" for the three moving rotors: Style[text = EnigmaEncryption["this is the SS, Identify yourself, are you a German or are you Alan Turing?", "A", "A", "A"], {Bold, FontSize -> 24}]  uubf jw dif oo, jctjgmbn nbtqrang, pvs vsh o orgiya lq lyw svn ssui zcxuxs? If the cryptographers at Bletchley have the incorrect key "B","A","E" they will not be able to decipher the text (it will be gibberish). Style[EnigmaEncryption[text, "B", "A", "E"], {Bold, FontSize -> 24}]  pgyy yd gnu nw, etlisxnw fnkniizh, tgy wde u gqkabx ma foe alc aifb cmavmt? However, with the right key: Style[EnigmaEncryption[text, "A", "A", "A"], {Bold, FontSize -> 24}]  this is the ss, identify yourself, are you a german or are you alan turing? We can make a small animation of the rotor states. For visual purposes, blue represents the forward states of the system and red the backward state. the code below can be used to generate the animation sequence: list = (Rasterize@*Grid /@ Module[{out, states, mergedstates, rotorstates, riffle, first, last, text = text, textout = StringReplace[text[[1]], Alternatives[" ", ",", "'", "?"] :> ""]}, out = Characters@textout; states = Partition[text[[2, 1]], 7]; mergedstates = Table[Join[states[[i]], {out[[i]]}], {i, Length@states}]; rotorstates = text[[2, 2]]; riffle = MapAt[Reverse, (Partition[#, 4] & /@ mergedstates), {All, 2}]; riffle = Apply[Composition[Partition[#, 2] &, Riffle], riffle, {1}]; Do[{first, last} = Flatten@Position[rotorstates[[j, i]], #] & /@ riffle[[j, i]]; rotorstates[[j, i, first]] = Style[First@rotorstates[[j, i, first]], {Blue, Bold, Background -> LightBlue}]; rotorstates[[j, i, last]] = Style[First@rotorstates[[j, i, last]], {Red, Bold, Background -> LightRed}]; , {j, Length@riffle}, {i, 4}]; rotorstates ]); 
10 Replies
Sort By:
Posted 7 years ago
 Hi Ali,very nice, thanks for sharing! But I must say that the germans never ever would have encrypted some english text ...Anyway, your nice code and the fact that you are using just 3 rotors (i.e. there are only 17576 keys) gives me the chance of testing an old idea: An incredibly simple and direct brute force attack - just try all keys and look for english text as outcome, you do not even have to care about the correct key! I guess Alan Turing could not even have dreamed of such an insane approach! encText = "uubf jw dif oo, jctjgmbn nbtqrang, pvs vsh o orgiya lq lyw svn ssui zcxuxs?"; allKeys = Tuples[CharacterRange["A", "Z"], 3]; allEncodings = ParallelMap[EnigmaEncryption[encText, Sequence @@ #] &, allKeys]; bruteForce = ParallelMap[{#, LanguageIdentify[#]} &, allEncodings]; englishText = Select[bruteForce, Last[#] == Entity["Language", "English"] &]; This should work - but it does not work! I was prepared for some false positive findings (therefore I did not use a While construct), but not for so many (>9%)! Can anybody comment why LanguageIdentify is working so badly?!Best regards -- Henrik
Posted 7 years ago
 Thanks a lot Henrik. What you are proposing is quite interesting. let me look at your code !
Posted 7 years ago
 The problem is that LanguageIdentify, is a simple classifier that always gives an answer. It is the same as: Classify["Language"] What you can do: use the underlying classifier and ask for probabilities: Classify["Language"]["abcdefghijklmnopqrstuvwxyz", "TopProbabilities" -> 1] and then only accept if the probability is above a high percentage (e.g. 95%). Else, unidentified.
Posted 7 years ago
 Hi Sander,sounds very promising - great! I will try. Thank you very much and best regards -- Henrik
Posted 7 years ago
 On the Enigma machine: Charles Stevens made the attached cdf. Its outstanding.Taken from this discussion Attachments:
Posted 7 years ago
 Thanks Hans for pointing it out. Indeed that is a lot of work put in by the author !
Posted 17 days ago
 Three Polish mathematicians (Rejewski, Różycki, and Zygalski), working as cryptologists at the Polish Cipher Bureau, made the first break into the German military Enigma. They started regularly reading the messages in January 1933.The Polish method relied on the German key system that transmitted the three letter message setting, telling how to set the Enigma wheels, two times (double encipherment). For example, if the plain text message setting were RBG the sending operator would key in RBGRBG and might get PRUKAC as its cipher text.Because the Enigma wheels moved three places between the first and fourth letter (as well as the other pairs), Rejewski realized that with enough messages he could determine the message settings. The Poles develop methods to exploit this condition. One used sets of punched paper called Zygalski sheets. The other was an electromechanical method that simulated the Enigma; the Poles named it Bomba (after a desert they were eating when they conceived of the method).At the time, the three wheel Enigma had a choice of three wheels that could go into the machine in any order giving six possible configurations. They used six machines to test the possible combinations. Later, the Germans introduced two more wheels for the three wheel Enigma making sixty configurations. The Poles didn’t have enough of their machines.Turing went to Bletchley Park in late 1939 (well after the Polish success), learned of Polish methods, and became concerned that if the Germans changed the key system the Polish methods would stop working. In 1939-1940 he devised a method based on “cribs” (known or guessed plain text, which could match the cipher text) to significantly reduce the possible choices. The implementation of the method was an electromechanical computer called the Bombe, named after the Polish Bomba. Turing provided the logical design of the machine and Harold Keen provided the mechanical design. Keen’s company, British Tabulating Machine, produced more than 200 Bombes during the war. Gordon Welchman devised the “diagonal board” which further reduced the possible choices and made the Bombe more efficient.One question is the size of the encipherment space, i.e., how many possible combinations exist for the Enigma. The Cryptographic Mathematics of Enigma by Dr. A. Ray Miller, published by the US National Security Agency, provides the answer. Dr. Ray presents an analysis for the three wheel Enigma. I’ll briefly describe his theoretical and practical results.There are five elements that contribute to the encipherment space. 1. A plugboard, which could contain from zero to thirteen dual-wired cables 2. Three ordered wheels with 26 inputs and 26 outputs 3. Twenty-six ways for the operator to set each wheel 4. A moveable ring which sets the turnover position of the next rotor 5. A reflector that sends the signal back through the rotors.Dr. Miller calculates that there are about 3×10113 possible ways to set up this Enigma.The more interesting calculation is the number the cryptanalysts were likely to encounter when trying to determine the daily keys.Plugboard – assume 10 pairs – 150,738,274,937,250 Wheel order – choose 3 from 5 wheels and use them in any order – 60 Initial rotor positions – setting the wheels – 17,576 Notch setting – setting the turnover position of the left and middle wheel – 676 Reflector – only one choice with known wiring – 1This product is about 1×1023.Breaking Enigma didn’t rely on brute force, but mathematical analysis to significantly reduce the number of positions to test.
Posted 15 days ago
 Dan, thank you for this interesting overview! Breaking Enigma didn’t rely on brute force, but ... Yes, of course - it is the most stupid approach you can make! But when you have computational power at your fingertips, those pioneers could not event have dreamed of, this brute force attack was just too tempting. We are all "standing on the shoulders of giants".
Posted 15 days ago
 Hi Sander,an 7 years late answer - as this discussion comes up again: According to your advice (and for the sake of completeness), here is a working version of a most simple brute force attack: encText = "uubf jw dif oo, jctjgmbn nbtqrang, pvs vsh o orgiya lq lyw svn ssui zcxuxs?"; allKeys = Tuples[CharacterRange["A", "Z"], 3]; allEncodings = ParallelMap[EnigmaEncryption[encText, Sequence @@ #] &, allKeys]; bruteForce = ParallelMap[{#, Classify["Language"][#, "TopProbabilities" -> 1]} &, allEncodings]; englishText = Select[bruteForce, #[[2, 1, 1]] == Entity["Language", "English"] && #[[2, 1, 2]] > .9999 &] It is interesting to see, what else could be an English text with high probability. Again many thanks and best regards -- Henrik
Posted 21 hours ago
 -- you have earned Featured Contributor Badge Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!