The card catalog, or "catalog of characteristics," in cryptography, was a system designed by Polish Cipher Bureau mathematician-cryptologist Marian Rejewski, and first completed about 1935 or 1936, to facilitate decrypting German Enigma ciphers.[1]
The Polish Cipher Bureau used the theory of permutations to start breaking the Enigma cipher in late 1932. The Bureau recognized that the Enigma machine's doubled-key (see Grill (cryptology)) permutations formed cycles, and those cycles could be used to break the cipher. With German cipher keys provided by a French spy, the Bureau was able to reverse engineer the Enigma and start reading German messages. At the time, the Germans were using only 6 steckers, and the Polish grill method was feasible. On 1 August 1936, the Germans started using 8 steckers, and that change made the grill method less feasible. The Bureau needed an improved method to break the German cipher.
Although the steckers would change which letters were in a doubled-key's cycle, the steckers would not change the number of cycles or the length of those cycles. Steckers could be ignored. Ignoring the mid-key turnovers, the Enigma machine had only distinct settings of the three rotors, and the three rotors could only be arranged in the machine ways. That meant there were only likely doubled-key permutations. The Bureau set about determining and cataloging the characteristic of each of those likely permutations. Each letter of the key could be one of partition number 13 = 101 possible values, and the 3 letters of the key meant there were possible keys. On average, a key would find one setting of the rotors, but it might find several possible settings.
The Polish cryptanalyst could then collect enough traffic to determine all the cycles in a daily key. That usually took about 60 messages. The result might be:
\begin{align} AD&=tt{(pjxroquctwzsy)(kvgledmanhfib)}\\ BE&=tt{(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}\\ CF&=tt{(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}\\ \end{align}
\begin{align} AD&=tt{(sjxroqtcuzwpy)(kngledamvhifb)}\\ BE&=tt{(kxucofgzeh)(wnibpylrvs)(tjd)(aqm)}\\ CF&=tt{(ynxqudhsfa)(pkgrjbcolz)(tv)(im)(e)(w)}\\ \end{align}
(e)(z) and (e)(w). That requires that e is unsteckered and a W-Z stecker. The cycles can then be aligned on e and W-Z to determine other steckered and un-steckered letters.(pjxroquctwzsy)(kvgledmanhfib)/(kxtcoigweh)...
(sjxroqtcuzwpy)(kngledamvhifb)/(kxucofgzeh)...
(!_____!_!**!_)(_!__=_!!!_!!_)/(__!__!_*=_)...Where = is a known un-steckered letter, * is a known steckered letter, and ! is a newly discovered stecker.Repetition produces the steckers A-M, F-I, N-V, P-S, T-U, W-Z.
Preparation of the card catalog, using the cyclometer that Rejewski had invented about 1934 or 1935, was a laborious task that took over a year's time. But once the catalog was complete, obtaining Enigma daily keys was a matter of some fifteen minutes.[2] [3] When the Germans changed the Enigma machine's "reflector," or "reversing drum," on 1 November 1937, the Cipher Bureau was forced to start over again 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."[2]
On 15 September 1938 the Germans completely changed the procedure for enciphering message keys, rendering the card-catalog method useless. This spurred the invention of Rejewski's cryptologic bomb and Henryk Zygalski's "perforated sheets."[4]