Editing Cryptanalysis of the Enigma (section)

===Invariant cycle lengths and the card catalogue===
[[File:Cyclometer4.png|thumb|175px|[[Cyclometer]], devised in the mid-1930s by Rejewski to catalogue the [[cyclic permutation|cycle]] structure of [[Enigma machine|Enigma]] [[permutation]]s. 1: Rotor lid closed, 2: Rotor lid open, 3: Rheostat, 4: Glowlamps, 5: Switches, 6: Letters.]]

Rejewski realised that, although the letters in the cycle groups were changed by the plugboard, the number and lengths of the cycles were unaffected—in the example above, six cycle groups with lengths of 9, 9, 3, 3, 1, and 1. He described this invariant structure as the ''characteristic'' of the indicator setting.{{dubious|Characteristic|reason=see following dubious. Confuses characteristic with catalogue hash code.|date=May 2015}} There were only 105,456 possible rotor settings.<ref>105,456 is the number of possible rotor settings (17,576) multiplied by the six ''wheel orders'' that were possible at this time. {{Harvnb|Singh|1999|p=131}}</ref><ref>The characteristic does not make the rings disappear; the rings can make the card catalog fail because stepped entries won't be there (a factor of 6 if only single steps are considered). The characteristic allows the actual letters (and therefore the plugboard permutation) to be ignored. Furthermore, Rejewski's notion of characteristic may be different: it may be the cycles rather than the cycle lengths. See Rejewski July 1981, Annals of Hist Computing, 3, 3, pp 217–218.</ref> The Poles therefore set about creating a [[card catalog (cryptology)|''card catalogue'']] of these cycle patterns.<ref>{{Harvnb|Alexander|c. 1945|loc=Ch. II Para. 4}}</ref>

The cycle-length method would avoid using the grill. The card catalogue would index the cycle-length for all starting positions (except for turnovers that occurred while enciphering an indicator). The day's traffic would be examined to discover the cycles in the permutations. The card catalogue would be consulted to find the possible starting positions. There are roughly 1 million possible cycle-length combinations and only 105,456 starting positions.<!-- expect 1, but some structures had thousands. A turnover indicator would not be found. --> Having found a starting position, the Poles would use an Enigma double to determine the cycles at that starting position without a plugboard. The Poles would then compare those cycles to the cycles with the (unknown) plugboard and solve for the plugboard permutation (a simple substitution cipher).<!-- No solution implies not the right starting position. --> Then the Poles could find the remaining secret of the ring settings with the ANX method.<!-- Rejewski claims they developed a faster method, but could not remember it. -->

The problem was compiling the large card catalogue.

Rejewski, in 1934 or 1935, devised a machine to facilitate making the catalogue and called it a ''[[cyclometer]]''. This "comprised two sets of rotors... connected by wires through which electric current could run. Rotor N in the second set was three letters out of phase with respect to rotor N in the first set, whereas rotors L and M in the second set were always set the same way as rotors L and M in the first set".<ref>{{Harvnb|Rejewski|1984e|p=285}}</ref> Preparation of this catalogue, using the cyclometer, was, said Rejewski, "laborious and took over a year, but when it was ready, obtaining daily keys was a question of [some fifteen] minutes".<ref name=RejewskiAppxC242>{{Harvnb|Rejewski|1984c|p=242}}</ref>

However, on 1 November 1937, the Germans changed the Enigma [[reflector (cipher machine)|reflector]], necessitating the production of a new catalogue&mdash;"a task which [says Rejewski] consumed, on account of our greater experience, probably somewhat less than a year's time".<ref name=RejewskiAppxC242/>

This characteristics method stopped working for German naval Enigma messages on 1 May 1937, when the indicator procedure was changed to one involving special codebooks (see [[#German Navy 3-rotor Enigma|German Navy 3-rotor Enigma]] below).<ref name=MahonP13>{{Harvnb|Mahon|1945|p=13}}</ref> Worse still, on 15 September 1938 it stopped working for German Army and Luftwaffe messages because operators were then required to choose their own ''Grundstellung'' (initial rotor setting) for each message. Although German army message keys would still be double-enciphered, the day's keys would not be double-enciphered at the same initial setting, so the characteristic could no longer be found or exploited.