Card catalog (cryptology)
# Card catalog (cryptology)

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.

## History

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 $26^3$ 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:

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

He would use the lengths of the cycles $(13^2;10^2-3^2;10^2-2^2-1^2)$ 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:

    ${\begin{aligned}AD&={\texttt {(sjxroqtcuzwpy)(kngledamvhifb)}}\\BE&={\texttt {(kxucofgzeh)(wnibpylrvs)(tjd)(aqm)}}\\CF&={\texttt {(ynxqudhsfa)(pkgrjbcolz)(tv)(im)(e)(w)}}\\\end{aligned}}$

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.

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."

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."

