|
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. A prerequisite, which might seem surprising, was the discovery of the message keys. At first glance, one might assume this was the final step before reading the messages. Reading two months of trafficRejewski was able to crack Enigma thanks to information provided by the French, specifically, Enigma operating manuals describing encryption procedures and 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. Furthermore, the Poles realized that the message keys were not random. Note: The Enigma manuals did not explicitly forbid the use of stereotyped message keys. However, using the same key twice on the same day was explicitly prohibited. Message keys are not randomDecryption revealed that most message keys were not random:
Using cyclesTheoryWhen examining the procedure Rejewski used to recover the right-hand rotor's wiring, it becomes clear that the first step was to determine the Enigma permutations for the six rotor positions following the Grundstellung (initial setting) A, B, C, D, E, F (see Rejewski's break of Enigma). Reconstructing the message keys begins with the same steps used to crack Enigma.
The problem is that there is a vast number of possible solutions. However, by making assumptions about certain message keys, one can easily find the compositions and ultimately deduce the complete set of message keys. A complete exampleA complete keyI am inventing an Enigma key to create the following examples.
Some indicators extracted from trafficAmong the most frequent:RED-YNX (10 copies) RGJ-YJW UMQ-XGZ WMX-KGU EEE-SND GAO-WHQ XVC-LBN ZAV-DHO UBT-XZIAmong the least frequent: YFB-FQP KAV-JHO Cycle reconstructions (from all indicators)Composition AD (1-4) [TOVRYFPGWKJ] [QN] [UXLZDIMHABC] [SE] Composition BE (2-5) [KCLPXENFQ] [VBZR] [UOWDYISAH] [GJTM] Composition CF (3-6) [XUFRHTIMJWGED] [QZAYSKCNLBPVO] Initial hypothesisThe indicator RED-YNX is the most frequent; it is possible that it corresponds to the key AAA (then A=R, A=E, A=D, A=Y, A=N, A=X). Based on this hypothesis, one can deduce (see Rejewski's break of Enigma) a large part of the permutations A, B, C, D, E, F. Method: Start with the pair (AR), then take the subsequent letters from the 3rd cycle ([UX...ABC]) in right-to-left order and pair them with the subsequent letters from the 1st cycle ([TO...KJ]) in left-to-right order: (AR)(BV)(CO) etc. Here are the results of the deductions:
Permutation A: (AR)(BV)(CO)(UT)(XJ)(LK)(ZW)(DG)(IP)(MF)(HY)
we have (QE)(NS) or (QS)(NE).
Permutation B: (AE)(HX)(UP)(OL)(WC)(DK)(YQ)(IF)(SN) ?????
Permutation C: (AD)(YE)(SG)(KW)(CJ)(NM)(LI)(BT)(PH)(VR)(OF)(QU)(ZX)
Permutation D: (AY)(BR)(CV)(UO)(XT)(LJ)(ZK)(DW)(IG)(MP)(HF)
we have (QE)(NS) or (QS)(NE).
Permutation E: (AN) (HE)(UX)(OP)(WL)(DC)(YK)(IQ)(SF) ?????
Permutation F: (AX)(YD)(SE)(KG)(CW)(NJ)(LM)(BI)(PT)(VH)(OR)(QF)(ZU)
Other deductionsNext, we use these permutations to try to decipher the indicators. RGJ-YJW A?C-A?C Perhaps ABC? UMQ-XGZ T?U-T?U Perhaps TZU (letters on a single line)? WMX-KGU Z?Z-Z?Z Perhaps ZZZ? Note: this is consistent with the previous hypothesis. EEE-SND (Q/N)AY-(S/Q)AY We deduce the key QAY (it is a diagonal) furthermore, we deduce the transpositions (EQ)(NS) for permutation A and (QS)(NE) for permutation D GAO-WHQ DEF-DEF Beyond a doubt (alphabetical sequence) XVC-LBN J?J-J?J Perhaps JJJ? ZAV-DHO WER-WER Beyond a doubt (segment of a line) UBT-XZI T?B-T?B Perhaps TGB? (a diagonal) All these deductions allow us to validate the initial hypothesis and complete the permutations. All permutations are complete except B and E. We will try to complete them: If we have TZU, we have the transposition (ZM) belonging to permutation B. We deduce: (ZM)(GB)(JV)(TR). We can thus complete the key for the 1st indicator: ABC-A?C, the key for the 6th indicator: JJJ-J?J, and finally the key for the last indicator: TGB-T?B. This information allows us to complete permutation E: (JB)(TV)(MR)(GZ). Final resulThe 6 permutations A through F. Permutation A: (AR)(BV)(CO)(UT)(XJ)(LK)(ZW)(DG)(IP)(MF)(HY)(EQ)(NS) Permutation B: (AE)(HX)(UP)(OL)(WC)(DK)(YQ)(IF)(SN)(ZM)(GB)(JV)(TR) Permutation C: (AD)(YE)(SG)(KW)(CJ)(NM)(LI)(BT)(PH)(VR)(OF)(QU)(ZX) Permutation D: (AY)(BR)(CV)(UO)(XT)(LJ)(ZK)(DW)(IG)(MP)(HF)(QS)(NE) Permutation E: (AN)(HE)(UX)(OP)(WL)(DC)(YK)(IQ)(SF)(JB)(TV)(MR)(GZ) Permutation F: (AX)(YD)(SE)(KG)(CW)(NJ)(LM)(BI)(PT)(VH)(OR)(QF)(ZU)It is now possible to decipher all indicators, including the less frequent ones: YFBFQP == HIT-HIT KAVJHO == LER-LER Improvement of security rules by the GermansGerman cryptological services noticed the operators' bad habits. They subsequently banned the use of three identical letters. However, operators still did not use random keys, and the Poles noticed that certain letters appeared more frequently than others in the message keys. These frequency differences were exploited to continue guessing the message keys. Yet, security procedures improved further, eventually resulting in keys that appeared truly random. This effort had a counter-intuitive result: to avoid repeating the same letter within a message key, operators began avoiding ANY repetition. Keys of the type XXy, XyX, or yXX were no longer used. The Poles developed a method to exploit this phenomenon (see Rejewski's report). Note: The practice just described persisted at least until the outbreak of the war. Indeed, an analysis of a key from December 1939 shows that no message key contains the same letter twice. References
|