An Introduction Algorithm to Decoding an Enigma
by Diana K.
Over the weekend, I watched the movie The Imitation Game about Alan Turing and the computer built to decode the Enigma. In the 1980s, while studying AI at UW-Parkside I was able to meet a friend of Alan Turing's who oversaw the Turing Institute. In addition to studying AI, I was interested in encryption as well and started understanding a Bazeries Cylinder like one used in The Da Vinci Code.
The Enigma is like a Bazeries Cylinder except that it has a plugboard which provides an additional transition. So, instead of a three-state transition as in a Bazeries Cylinder, there is a four-state transition provided by the plugboard. To give an Enigma example, consider the following morning message (assume it is written in German like in WWII):
In reading the message, it seems pretty simple, and one might have the ability to use a brute-force algorithm to break about 51 million combinations on a computer that ran at a processor speed of about 1 kHz. Actually, the solution could not be found within the timeline of 18 hours from the 6 a.m. broadcast.
What was a faster way? The faster way was found by talking with others who intercepted the encrypted messages and could tell that a specific person on the other side was typing the message. By realizing the same person was typing a daily weather report at 6 a.m. on the other side, one could have a set to compare. For example, the person would ably follow the same message format:
Then, taking the next step of comparing the actual message with the encrypted message, part of the state transition could be obtained. The weather report messages were deciphered by those who were able to use alternative methods to deliver the messages, but not the Enigma encoding and plugboard.
At a listening center, a group would have the decoded message:
And the encrypted message:
"Yop%Raebtep@Ayv!9v{WOSD%hf@g$sfuadq&q@qkg*znght,"What does this mean?
The thing to remember about the Enigma machine is that it had four-state transitions. So, if someone typed "T", the second-state transition could be "Z". When the letter "Z" is submitted to the plugboard, the next letter could be "B". The letter "B" is what would be sent via radio telegraph.
When the receiver would type the letter "B" on a similar Enigma machine, the internal transition would come out to "Z" via the one of the three wheels of the Bazeries Cylinder. And then the "Z" (Wheel 1) would come out to "B" (Wheel 2), then transition to "A" (Wheel 3), and finally transition "E" on the plugboard. So the state transition is: T-Z-B-A-E-T
The problem is coded for searching for a substring with T-?-??-???-????-T. Also, as other four-state substrings as added to compare and solve the algorithm, the "?" and "??" can be determined. However, it took a few substrings to use as a seed.
What is the algorithm? The algorithm starts with a state of either 1-4, like in Turing's state machine. Next, a substring is selected as "T-?-??-???-????-T". A method to solve the problem is to work backwards. So, what setting is needed on the plugboard to transition X (internal coded character) to "T"? The process compares various substrings in State 4, and the first backward solution is "T-?-??-???-B-T".
After the plugboard is solved, the next state is State 3 on the third wheel. The original search substring of "T-?-??-???-????-T" is now changed to "T-?-??-???-B-T". In a way, it is like a Keno game. In a Keno, after determining one set of numbers in a betting string, the process becomes cooperative to finding other solutions in an easier manner.
In State 3, when a substring message is found beginning with "B", a combination of trials is set to determine what possible settings from the plugboard to wheels 3, 2, and 1 could lead to a transition going backwards from "T-B-wheel 3 setting-wheel 2 setting-wheel 1 setting-T" from a set of sample words in the message.
The process is repeated backwards until the plugboard and wheels 1-3 are solved for State 1. Then the same method is used in State 2. When State 2 is solved, the same method is used in State 3. Which means the plugboard and three-wheel settings are determined. The solution would look something like this:
If one were to consider that there were 32 settings for three wheels and the plugboard, the combination is (25)4 (1,048,576) combinations.
However, by knowing two of the transitions, the combinations needed to be solved are: (25)2 (1,024) combinations.
This is a speed-up of 1,024 and allows a solution within an 18-hour time limit.
In Pascal-like pseudocode, the code would look like this:
Program breakEnigma; (* (c) 2022 Diana K. *) Var subCrypts: array[1..3,1..5] of string = (('T-?-??-???--X-T'), ('A-?-??-???-P-A'), ('C-?-??-???-Z-C'), ('Q-?-??-???-B-Q'), ('G-?-??-???-Q-G'); (* second set for state 2, third set for state 3 *) msg: string; i, j, k: integer; settings: array[0..3] of integer = (0, 0, 0, 0); maxWheel: array[0..3] = (32, 32, 32, 32); state: integer; completed: Boolean; function decrypt1(cryptMsg): Boolean; var i, j, k: integer; Tmp: string; Solved: Boolean; Begin Tmp := ''; Solved := true; For i := 1 to length(cryptMsg) Do begin j := (i mod 4); (* Plugboard *) Tmp[1] := chr(((ord(cryptMsg[i]) + setting[j]) mod maxWheel[j]); (* Wheel 3 *) Tmp[2] := chr(((ord(tmp[1]) + setting[(j + 1) mod 4]) mod maxWheel[(j + 1) mod 4]); (* Wheel 2 *) Tmp[3] := chr(((ord(tmp[2]) + setting[(j + 2) mod 4]) mod maxWheel[(j + 2) mod 4]); (* Wheel 1 *) Tmp[4] := chr(((ord(tmp[4]) + setting[(j + 3) mod 4]) mod maxWheel[(j + 3) mod 4]); Solved := solved and (cryptMsg[i] = tmp[4]); End; Decrypt1 := solved; End; Procedure solvePartialSubCrypt(state:integer; i:integer; settings:integer; subCrypts: string[][]); Var i, j, k: integer; Begin (* convert pseudocode lit to pascal like pseudocode *) (* a challenge to the reader, easy to do *) End; begin writeln('Program Break Enigma'); write('Enter Encrypted Message? '); readln(msg); writeln; writeln('..Starting Solving'); for state := 1 to 4 do begin for i := 4 downto 1 do solvePartialSubCrypt(state, i, settings, subCrypts); end; (* check work *) Completed := true; For state := 1 to 3 Do for j := 1 to 5 Do competed := completed and decrypt1(subCrypts[state, j]); (* show result *) If not completed Then writeln('A Solution was not found') Else writeln('A Solution was found'); Writeln; Writeln('Settings: \tPlugboard\tWheel 3\tWheel 2\tWheel 1'); Writeln('\t' + settings[0] + '\t' + settings[1] + '\t' + settings[2] + '\t' + settings[3]); Writeln Writeln('...Program Completed'); End.What is interesting about the Enigma is that even today with a laptop computer, it takes about one hour to break an Enigma code - faster than 18 hours, yet still long enough for a message to become invalid if a decision is made an hour later after decoding.
The primary advantage of encryption is not the method itself; the primary advantage of encryption is how long does it take an opponent to read your message, and can your opponent read your message in time, while the message time is still valid?
Code: breakEnigma.pas