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 263 distinct settings of the three rotors, and the three rotors could only be arranged in the machine 3!=6 ways. That meant there were only 105456 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 1030301 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:
He would use the lengths of the cycles (132;102-32;102-22-12) to look up the wheel order (II I III) and starting rotor positions in the card catalog. He would then use an Enigma to compute the un-steckered cycles:
By comparing the steckered cycles from the German traffic and the un-steckered cycles, the cryptanalyst can determine the steckers. In the example, the CF permutation has (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]