Message Boards Message Boards

Computational implementation of the German Enigma Machine

POSTED BY: Ali Hashmi
10 Replies
POSTED BY: Moderation Team

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 – 1

This 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 BY: Dan O'Leary

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 BY: Henrik Schachner
Posted 7 years ago

On the Enigma machine: Charles Stevens made the attached cdf. Its outstanding.Taken from this discussion

POSTED BY: Hans Milton

Thanks Hans for pointing it out. Indeed that is a lot of work put in by the author !

POSTED BY: Ali Hashmi

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 BY: Henrik Schachner

Thanks a lot Henrik. What you are proposing is quite interesting. let me look at your code !

POSTED BY: Ali Hashmi

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 BY: Sander Huisman

Hi Sander,

sounds very promising - great! I will try. Thank you very much and best regards -- Henrik

POSTED BY: Henrik Schachner
POSTED BY: Henrik Schachner
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract