|
Enigma Home Page
The first methods
|
IntroductionIn late 1932, Rejewski reconstructed the Enigma machine. During 1933, Polish cryptanalysts were able to read Enigma messages by reconstructing the daily key. This page is dedicated to the final step in reconstructing the daily key: determining the Ringstellung. Previous steps have already established the Walzenlage (rotor order), the Steckers (plugboard), and the message keys. Adding knowledge of the Ringstellung provides all the information needed to decrypt the day's entire traffic. One unknown remains, the Grundstellung, which can also be determined, even though it is not essential. The PrincipleAnalysis of two months of trafficRejewski was able to crack Enigma thanks to information provided by the French, notably, two monthly key tables. After cracking Enigma, the two key tables made it possible to decrypt two months' worth of traffic. Analyzing these decrypted messages yielded valuable insights. Notably, many messages began with "AN," which introduced the intended recipient. The procedure usedThe procedure is simple: one simply attempts to decrypt a message—assumed to start with "AN"—using every possible rotor position (26 × 26 × 26 = 17,576). If a match is found, the decryption of the next four letters is tested. If the result is a word (or the beginning of a word) that could logically follow "AN," there is a high probability that the absolute position (relative to the rotor cores, which contains the rotor wiring) of the message's start has been found. Then, the Ringstellung is deduced using the following formula: Ringstellung = Message_key – Absolute_Position – [1, 1, 1]NOTE! It is rare to find a successful decryption on the very first test. A message might not begin with "AN," and the middle rotor may turn over. In practice, several ciphertexts would be tested. GrundstellungAt first glance, one might think that the Grundstellung can be determined in the same way as the Ringstellung, by testing all 17,576 rotor positions. In fact, the search can be reduced to just 26 × 26 = 676 tests. This is because the "Grill" method allows us to determine the absolute position of the right-hand rotor. Furthermore, if "Catalogue F" has been compiled, the absolute positions of the other two rotors are also known. In this latter case, calculating the Grundstellung takes less than a minute, using the same formula (albeit inverted): Grundstellung = Ringstellung + Absolute_position + [1,1,1] ImplementationManual methodJust for fun, I tested (partially) Rejewski’s method. I used Dirk Rijmenants’ simulator of Enigma, which is very realistic. I spent fifteen minutes typing "AN" at various rotor positions. I then calculated how long it would have taken me to test every initial position (17,576). A quick calculation suggested it would take half a day... for just a single test run (one "AN" pair and the beginning of one ciphertext). Optimizations: I soon switched from typing "AN" to typing only "A." I would note the position and move on. Furthermore, I disregarded "double stepping." Later, I would revisit the noted positions to test the letter "N"; if the result was correct, I would type the next four letters and record the outcome. I also went back to the Grundstellung corresponding to the double-stepping instances I had ignored during the first stage. As you can see, searching for the "A"s and the other letters separately could be done in parallel by two different people! For reference, during the first stage, I managed to type about 1,000 "A"s in 10 minutes. Bear in mind that an Enigma machine is not a computer keyboard! Note: It is not possible to test multiple cryptograms simultaneously. This is because pressing a key advances the rotors and (occasionally) causes a "double-stepping" action, skipping positions that would otherwise need to be tested. To avoid these issues, Polish cryptanalysts may have modified the rotors to disable automatic advancement, thereby foreshadowing the Cyclometer. Computer ProgramTo search for the absolute rotor positions, I created a small program that tests all 17,576 starting positions and checks, for each one, whether it correctly decrypts the beginning of the ciphertext. The inputs are the Walzenlage, the Steckers and the start of the ciphertext. The program displays the position and the decrypted first nine letters if the first two decrypted letters match "AN" (a different plaintext, such as a message key, can be specified). Additionally, the message key (in the example: XXX) must be known in order to deduce the Ringstellung. $ python3 scan_grund.py -c VHBIPFDQX -W I,II,III -s AQ:ED:RF:TG:YH:OL Walzen. Ring Grund plain-text cryptogram ======================================== I,II,III ZZZ CRZ ANGTRLFJT VHBIPFDQX I,II,III ZZZ DDG ANLBDCCMG VHBIPFDQX I,II,III ZZZ ENK ANXBSGSOS VHBIPFDQX I,II,III ZZZ FAO ANPEDXUHI VHBIPFDQX I,II,III ZZZ FXC ANQCFVFXQ VHBIPFDQX I,II,III ZZZ GZF ANKHLAIKG VHBIPFDQX I,II,III ZZZ HCB ANSXIHGGF VHBIPFDQX I,II,III ZZZ HEX ANRCJAUHG VHBIPFDQX I,II,III ZZZ HMK ANMBBACVB VHBIPFDQX I,II,III ZZZ HOY ANQBMWNCR VHBIPFDQX I,II,III ZZZ IFX ANRCJAUHG VHBIPFDQX I,II,III ZZZ LST ANHSWIBXN VHBIPFDQX I,II,III ZZZ LZT ANXMCIAXZ VHBIPFDQX I,II,III ZZZ MRH ANWFYDBXV VHBIPFDQX I,II,III ZZZ NIZ ANFTTRBWT VHBIPFDQX I,II,III ZZZ OSF ANHKONLXC VHBIPFDQX I,II,III ZZZ SXJ ANUCWSWNH VHBIPFDQX I,II,III ZZZ TBM ANGENERAL VHBIPFDQX I,II,III ZZZ UAV ANJBBLHXE VHBIPFDQX I,II,III ZZZ UIF ANOYCGOPB VHBIPFDQX I,II,III ZZZ UIQ ANLNMTMLD VHBIPFDQX I,II,III ZZZ UMC ANNRFJYXW VHBIPFDQX I,II,III ZZZ VZK ANOBNMFPF VHBIPFDQX I,II,III ZZZ YCA ANNJQJUIK VHBIPFDQX I,II,III ZZZ ZSM ANRTFHZDA VHBIPFDQX I,II,III ZZZ ZZY ANJTXDNCQ VHBIPFDQXIt is observed that the prefix ANGENERAL appears at the TBM position. From this, the Ringstellung is deduced: DVK. Ringstellung = Message_key – Absolute_Position – [1,1,1] Ringstellung = [X,X,X] – [T,B,M] – [1,1,1] = [D,V,K]NOTE! We were very lucky in the previous example: the message did indeed begin with "AN," and no rotor turnover occurred during the decryption of the beginning of the cryptogram. In practice, if the attempt fails, other message beginnings must be tested. Similarly, the day's Grundstellung can be determined from an indicator pair (e.g., JHZTUA) and a message key (e.g., XXX). $ python3 scan_grund.py -c JHZTUA -W I,II,III -s AQ:ED:RF:TG:YH:OL -p XXX Walzen. Ring Grund plain-text cryptogram ======================================== I,II,III ZZZ QOE XXXXXX JHZTUAThe Grundstellung is therefore equal to: Grundstellung = Ringstellung + Absolute_position + [1,1,1] Grundstellung = [D,V,K] + [Q,O,E] + [1,1,1] = [3,21,10]+[16,14,4]+[1,1,1] = [20,10,15] Grundstellung = [U,K,P]As a reminder, the complete key is: Walzenlage : I-II-III Ringstellung : DVK Steckers : AQ,ED,RF,TG,YH,OL Grundstellung : UKP References
|