Cyclometer

The cyclometer was a cryptologic device designed, "probably in 1934 or 1935," by Marian Rejewski of the Polish Cipher Bureau's German section (BS-4), to catalog the cycle structure of Enigma permutations, thereby facilitating the decryption of German Enigma ciphertext.^[1]

With Rejewski's later cryptologic bomb, it can be viewed as a predecessor to the Bombe that was to help break Enigma ciphers later in the war at Bletchley Park in England.

Using drawings made by Rejewski, Hal Evans and Tim Flack at the Department of Engineering, University of Cambridge, in 2019 constructed a working version of the cyclometer.^[2]

History

Example message

Enigma, an electro-mechanical rotor machine with scrambler comprising entry drum, three rotors, and reflector. This military model also has a plugboard.

Fede Weierud provides the procedure, secret settings, and results that were used in a 1950 German technical manual.^[3]^[4]

Daily key (shared secret):   Wheel Order  : II  I  III   Ringstellung : 24  18  22 (XMV)   Reflector    : A   Plugboard    : A-M, F-I, N-V, P-S, T-U, W-Z   Grundstellung: FOL  Operator chosen message key : ABL Enciphered starting with FOL: PKPJXI  Cleartext message to send and resulting cleartext:   Feindliche Infanteriekolonne beobachtet.   Anfang Südausgang Bärwalde.   Ende drei km ostwärts Neustadt.    FEIND LIQEI NFANT ERIEK    OLONN EBEOB AQTET XANFA    NGSUE DAUSG ANGBA ERWAL    DEXEN DEDRE IKMOS TWAER    TSNEU STADT  Resulting message:   1035 – 90 – 341 –    PKPJX IGCDS EAHUG WTQGR   KVLFG XUCAL XVYMI GMMNM   FDXTG NVHVR MMEVO UYFZS   LRHDR RXFJW CFHUH MUNZE   FRDIS IKBGP MYVXU Z

The first line of the message is not encrypted. The "1035" is the time, "90" is number of characters encrypted under the message key, and "341" is a system indicator that tells the recipient how the message was encrypted (i.e., using Enigma with a certain daily key). The first six letters in the body ("PKPJXI") are the doubled key ("ABLABL") encrypted using the daily key settings and starting the encryption at the ground setting/Grundstellung "FOL". The recipient would decipher the first six letters to recover the message key ("ABL"); he would then set the machine's rotors to "ABL" and decipher the remaining 90 characters. Notice that the Enigma does not have numerals, punctuation, or umlauts. Numbers were spelled out. Most spaces were ignored; an "X" was used for a period. Umlauts used their alternative spelling with a trailing "e". Some abbreviations were used: a "Q" was used for "CH".

Marian Rejewski

During Marian Rejewski's mathematics studies at Poznań University, the Polish Cipher Bureau recruited him and some other mathematics students, including Jerzy Różycki and Henryk Zygalski, to take a Bureau-sponsored course on cryptology. The Bureau later hired some of the students to work part-time at a temporary local Bureau office. After graduating from Poznań University, at the University of Göttingen Rejewski completed the first year of a two-year actuarial statistics course, then returned to Poznań. In September 1932 he, Różycki, and Zygalski went to Warsaw to work full-time for the Cipher Bureau.

In December 1932 Rejewski was tasked by the Cipher Bureau to work on the German Enigma cipher machine. The Bureau had attempted, but had failed, to break it. Within a few weeks, Rejewski managed to reconstruct the machine. The German Enigma message procedures used common, secret daily machine settings, but also required a cipher clerk to choose an individual three-letter message key. Thus, a clerk might choose "ABL" as the message key. The message key was used to set the initial position of the rotors when enciphering or deciphering the message.

Choosing an individual message key was a security measure: it avoided having all the day's messages sent using the same polyalphabetic key, which would have made the messages vulnerable to a polyalphabetic attack. However, the sender needed to communicate the message key to the recipient in order for the latter to decipher the message. The message key was first encrypted using the day's Grundstellung (a secret initial position of the Enigma's rotors, e.g., "FOL").

Communications were sometimes garbled, and if the message key were garbled, the recipient would be unable to decrypt the message. Consequently the Germans took the precaution of sending the message key twice; if there was a garble, the recipient should be able to find the message key. Here the Germans committed a crucial error. Instead of sending the encrypted message key (e.g., "PKP") twice to get "PKP PKP", they doubled the message key (e.g., "ABL ABL"), encrypted the doubled key to get ("PKP JXI"), and sent the encrypted doubled key. That mistake allowed Rejewski to identify six sequential permutations of the Enigma and exploit the knowledge that they encrypted the same message key.

With the help of a commercial Enigma machine, German materials obtained by French spy Hans-Thilo Schmidt, and German cipher clerks who chose weak keys, Rejewski was able to reverse-engineer the wiring of the Enigma's rotors and reflector. The Cipher Bureau then built several Polish Enigma doubles that could be used to decrypt German messages.

Characteristic

The German procedure that sent an encrypted doubled key was the mistake that gave Rejewski a way in. Rejewski viewed the Enigma as permuting the plaintext letters into ciphertext. For each character position in a message, the machine used a different permutation.^[5] Let A B C D E F be the respective permutations for the first through sixth letters. Rejewski knew the first and fourth letters were the same, the second and fifth letters were the same, and third and sixth letters were the same. Rejewski could then examine the day's message traffic; with enough traffic he could piece together the composed permutations.

For example, for the daily key in a 1930 technical manual, then (with enough messages) Rejewski could find the following characteristics:

{\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{aligned}}

The notation is Cauchy's cycle notation. By examining the day's traffic, Rejewski would notice that if "p" were the first letter of the indicator, then "j" would be the fourth letter. On another indicator, "j" would be the first letter, and "x" would be the fourth letter. Rejewski would continue following the letters. Eventually, there would be a message whose first letter was "y" and the fourth letter would cycle back to "p". The same observations would be done for the second and fifth letters; usually there would be several cycles.

Grill method

Rejewski could use this cycle information and some sloppy habits of code clerks to figure out the individual permutations A B C D E F using the grill method, but that method was tedious. After using the grill, the Poles would know the rightmost rotor and its position, the plugboard connections, and Q (the permutation of the reflector and other two rotors). In order to get the daily key, the Poles would still have a lot of work to do, and that work could entail trying all possible orders and positions for the two left rotors to find the position for the Grundstellung. The Poles started using a Q-catalog to make part of the grill method easier; that catalog had 4,056 entries (26 × 26 × 6). To find the ring settings, the grill method could require trying 17,576 possibilities.

The grill method worked well until 1 October 1936, the day the Germans stopped using six steckers (plugboard connections) and started using five to eight steckers.^[6] More steckers could frustrate the grill method.

Cycle lengths

Instead of indexing the catalog by the actual cycles, the Poles hit upon indexing the catalog by the length of the cycles. Although the plugboard changed the identity of the letters in the permutation, the plugboard did not change the lengths of the cycles.

It turns out there are 101 possible patterns for the cycle lengths of an indicator permutation.^[7] With the three permutations in the characteristic, there are about one million possible cycle length combinations ( $1013 =1,030,301$ ). Consequently, the cycle lengths could be used as a hash function into a hash table of the 105,456 possible combinations. The Poles would look at the day's traffic, recover the characteristic of the indicator, and then look in the card catalog. The odds would be good that only one (or maybe a few) cards had those cycle lengths.

The result would be the appropriate rotor order and the positions of all the rotors without much work. The method was simpler than the grill method and would work when there were many steckers.

Recovering the plugboard

The catalog did not disclose the plugboard settings. For six plugs (steckers), there are about 100 billion possible arrangements.^[8] Trying them all out is infeasible. However, the cryptographer could find the characteristic for that rotor order without a plugboard, use that bare characteristic in a known plaintext attack, and then determine the plugboard settings by comparing them with the daily characteristic.^[9]

From some daily traffic, the cryptanalyst would calculate the characteristic.

{\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{aligned}}

In the grill method, the above characteristic would be solved for the individual permutations $A B C D E F$ and then a laborious search would be done. Instead, the characteristic's paired cycle lengths would be calculated:

AD: 13 BE: 10 3 CF: 10 2 1

Those lengths would be looked up in the card catalog, and an entry would be found that would state the wheel order (II, I, III) and the initial position of each wheel.

The card catalog did not include the actual characteristic: the cyclometer only indicated membership in a cycle; it did not specify the order of letters in a cycle. After finding a catalog entry, the cryptanalyst would then calculate the characteristic without steckers (just the catalog settings). The cryptanalyst can determine each of the individual permutations $A* B* C* D* E* F*$ by setting an Enigma to the given wheel order and initial positions. The cryptanalyst then presses a and holds it down; the corresponding lamp lights and is written down; without releasing the first letter, the cryptanalyst presses b and then releases the first letter; that keeps the machine from advancing the rotors and lights the lamp corresponding to b. After mapping out all of $A$ , the cryptanalyst can move on to $B$ and the other permutations. The cryptanalyst recovers the unsteckered characteristic:

{\begin{aligned}A^{*}D^{*}&={\texttt {(jxroqtcuzwpys)(kngledamvhifb)}}\\B^{*}E^{*}&={\texttt {(kxucofgzeh)(wnibpylrvs)(aqm)(dtj)}}\\C^{*}F^{*}&={\texttt {(colzpkgrjb)(ynxqudhsfa)(vt)(mi)(e)(w)}}\\\end{aligned}}

The two characteristics are then used to solve the stecker permutation $S$ .

For this example, there are six steckers, and they would affect 12 characters. Looking at the $CF$ cycles, the plugboard cycles (un)(fa) must transpose with the un-steckered cycles (vt)(mi). None of the letters are same, so all of those eight letters are steckered. Looking at the singleton cycles of $CF$ and $C*F*$ shows not only that "e" is not steckered, but also that "w" and "z" are steckered together.^[10] Thus ten of the twelve steckered letters are quickly identified. Most of the other 16 letters, such as "b", "d", "g", and "l", are probably not steckered. The cycle notation of $A*D*$ , $B*E*$ , and $C*F*$ can be rearranged to match the likely unsteckered characters. (The initial letter of a cycle's notation is not significant: within a cycle, the letters must keep the same sequence, but they may be rotated. For example, (dtj) is the same as (tjd) which is the same as jdt.)

{\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\A^{*}D^{*}&={\texttt {(sjxroqtcuzwpy)(kngledamvhifb)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\B^{*}E^{*}&={\texttt {(kxucofgzeh)(wnibpylrvs)(tjd)(aqm)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\C^{*}F^{*}&={\texttt {(ynxqudhsfa)(pkgrjbcolz)(tv)(im)(e)(w)}}\\\end{aligned}}

At this point, the potential steckers can be read from the differences in the first two lines; they can also be checked for interchange consistency. The result is

P-S T-U W-Z N-V A-M F-I

These steckers match the 1930 Enigma example.

The only remaining secret is the ring positions (Ringstellung).

Building the catalog

The cyclometer was used to prepare a catalog of the length and number of cycles in the "characteristics" for all 17,576 positions of the rotors for a given sequence of rotors. Since there were six such possible sequences, the resulting "catalog of characteristics," or "card catalog," comprised a total of (6) (17,576) = 105,456 entries.^[11]

The utility of the card catalog, writes Rejewski, was independent of the number of plug connections being used by the Germans on their Enigma machines (and of the reconstruction of message keys). Preparation of the catalog "was laborious and took over a year, but when it was ready... daily keys [could be obtained] within about fifteen minutes."^[12]

On November 1, 1937, however, the Germans changed the "reversing drum," or "reflector."^[13] This forced the Cipher Bureau to start anew with a new card catalog, "a task," writes Rejewski, "which consumed, on account of our greater experience, probably somewhat less than a year's time."^[14]

But then, on September 15, 1938, the Germans changed entirely the procedure for enciphering message keys, and as a result the card-catalog method became completely useless.^[14] This spurred the invention of Rejewski's cryptologic bomb and Zygalski's perforated sheets.^[15]

Notes

^ Marian Rejewski, "Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys...", p. 242.
^ Evans, Henry A.(2019): Recreation of the Polish Cyclometer and its role in breaking Enigma. MEng dissertation, University of Cambridge [1]
^ "Frode Weierud's CryptoCellar | Enigma Test Message from 1930". Archived from the original on 2014-10-30. Retrieved 2014-10-07., citing 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Directions for use of Keys on the Cypher Machine 'Enigma I'"]
^ Can be checked with a simulator. For example, http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Select Enigma I, choose reflector A (at the time, the Germans only had one reflector), setting the wheels ordering (II, I, III), set the rings (24, 13, 22), set the plugs (AM, FI, NV, PS, TU, WZ), activate the plugboard, and set the heels to the ground setting ("FOL"). Typing ABLABL in the input box should produce PKPJXI as the output.
^ The permutations would be determined by the plugboard, the rotor order, the rotor positions, and the reflector. The right rotor (and possibly other rotors) moved for each character encrypted, and that movement changed the permutation.
^ Rejewski 1981, p. 224
^ The characteristic is 26 letters, but the cycles in the characteristic must pair, so the question is how many patterns are there for 13 letters: the number of ways to partition 13 indistinguishable objects. See "a(n) = number of partitions of n (the partition numbers)" https://oeis.org/A000041; "Partition Function P(n)", stating "gives the number of ways of writing the integer $n$ as a sum of positive integers, where the order of addends is not considered significant," http://mathworld.wolfram.com/PartitionFunctionP.html; Partition (number theory)
^ Rejewski 1981, p. 216
^ Rejewski (1981, p. 225) states, "When all six card files were prepared, finding the daily key was an ordinary matter that took a mere 10 or 15 minutes. The drum positions were read off the card, the order of the drums was read from the box from which the card was retrieved, and permutation $S$ was obtained by comparing the letters in the cycles of the characteristic with the letters in the cycles of permutations $AD$ , $BE$ , $CF$ , which were found by typing them on the machine." Rejewski says they did not get the information from the card but rather got it from the double. That seems unlikely. The cyclometer would quickly provide the information, and the information could be on the card.
^ If "e" were steckered, it must be paired with "w" in one transposition and paired with "z" in another transposition — but "e" cannot be paired with two different letters, so "e" cannot be steckered.
^ Marian Rejewski, "The Mathematical Solution of the Enigma Cipher," pp. 284–87.
^ Marian Rejewski, "Summary of Our Methods...", p. 242.
^ Rejewski 1981, p. 225
^ ^a ^b Rejewski, "Summary of Our Methods...", p. 242.
^ Rejewski, "Summary of Our Methods...", pp. 242–43.

References

Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, edited and translated by Christopher Kasparek, Frederick, MD, University Publications of America, 1984, ISBN 0-89093-547-5.
Rejewski, Marian (July 1981), "How Polish Mathematicians Deciphered the Enigma", Annals of the History of Computing, 3 (3), IEEE: 213–234, doi:10.1109/MAHC.1981.10033, S2CID 15748167
Marian Rejewski, "Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods," Appendix C to Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, 1984, pp. 241–45.
Marian Rejewski, "The Mathematical Solution of the Enigma Cipher," Appendix E to Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, 1984, pp. 272–91.

External links

"Polish Enigma Double"
About the Enigma (National Security Agency) Archived 2004-04-14 at the Wayback Machine
"The Enigma Code Breach" by Jan Bury
The „Enigma” and the Intelligence
"Codebreaking and Secret Weapons in World War II" By Bill Momsen
A Brief History of Computing Technology, 1930 to 1939
Kuhl, Alex (October 2007), "Rejewski's Catalog" (PDF), Cryptologia, 31 (4), Taylor & Francis: 326–331, doi:10.1080/01611190701299487, S2CID 14254844, archived from the original (PDF) on 2015-07-24

[1] Marian Rejewski, "Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys...", p. 242.

[2] Evans, Henry A.(2019): Recreation of the Polish Cyclometer and its role in breaking Enigma. MEng dissertation, University of Cambridge [1]

[3] "Frode Weierud's CryptoCellar | Enigma Test Message from 1930". Archived from the original on 2014-10-30. Retrieved 2014-10-07., citing 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Directions for use of Keys on the Cypher Machine 'Enigma I'"]

[4] Can be checked with a simulator. For example, http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Select Enigma I, choose reflector A (at the time, the Germans only had one reflector), setting the wheels ordering (II, I, III), set the rings (24, 13, 22), set the plugs (AM, FI, NV, PS, TU, WZ), activate the plugboard, and set the heels to the ground setting ("FOL"). Typing ABLABL in the input box should produce PKPJXI as the output.

[5] The permutations would be determined by the plugboard, the rotor order, the rotor positions, and the reflector. The right rotor (and possibly other rotors) moved for each character encrypted, and that movement changed the permutation.

[6] Rejewski 1981, p. 224

[7] The characteristic is 26 letters, but the cycles in the characteristic must pair, so the question is how many patterns are there for 13 letters: the number of ways to partition 13 indistinguishable objects. See "a(n) = number of partitions of n (the partition numbers)" https://oeis.org/A000041; "Partition Function P(n)", stating "gives the number of ways of writing the integer $n$ as a sum of positive integers, where the order of addends is not considered significant," http://mathworld.wolfram.com/PartitionFunctionP.html; Partition (number theory)

[8] Rejewski 1981, p. 216

[9] Rejewski (1981, p. 225) states, "When all six card files were prepared, finding the daily key was an ordinary matter that took a mere 10 or 15 minutes. The drum positions were read off the card, the order of the drums was read from the box from which the card was retrieved, and permutation $S$ was obtained by comparing the letters in the cycles of the characteristic with the letters in the cycles of permutations $AD$ , $BE$ , $CF$ , which were found by typing them on the machine." Rejewski says they did not get the information from the card but rather got it from the double. That seems unlikely. The cyclometer would quickly provide the information, and the information could be on the card.

[10] If "e" were steckered, it must be paired with "w" in one transposition and paired with "z" in another transposition — but "e" cannot be paired with two different letters, so "e" cannot be steckered.

[11] Marian Rejewski, "The Mathematical Solution of the Enigma Cipher," pp. 284–87.

[12] Marian Rejewski, "Summary of Our Methods...", p. 242.

[13] Rejewski 1981, p. 225

[Rejewski_p._242-14] Rejewski, "Summary of Our Methods...", p. 242.

[15] Rejewski, "Summary of Our Methods...", pp. 242–43.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Polish Cipher Bureau
*Biuro Szyfrów*
Methods and technology
"ANX" Enigma "double" Grill Clock Cyclometer Card catalog Cryptologic bomb Zygalski sheets Lacida
Locations
Saxon Palace Kabaty Woods PC Bruno Cadix
Personnel
Chief Gwido Langer Deputy Chief Chief of Radio Intelligence Chief of German Section Maksymilian Ciężki German Section cryptologists Marian Rejewski Jerzy Różycki Henryk Zygalski Antoni Palluth Wiktor Michałowski Chief of Russian Section Jan Graliński Russian Section cryptologist Piotr Smoleński Others Jan Kowalewski Stanisław Leśniewski Stefan Mazurkiewicz Franciszek Pokorny Wacław Sierpiński
v t e