Карточный каталог Реевского для взлома шифра "Энигма"

Введение

Каталог карт, или "каталог характеристик", в криптографии — это система, разработанная польским криптологом и математиком Марианом Реевским из Бюро шифров, и впервые завершенная примерно в 1935 или 1936 году для облегчения дешифровки немецких шифров "Энигма".

История

Польское бюро шифрования использовало теорию перестановок, чтобы начать взламывать шифр «Энигмы» в конце 1932 года. Бюро пришло к выводу, что перестановки двойного ключа машины «Энигма» (см. «Гриль» (криптология)) формируют циклы, и эти циклы можно было использовать для взлома шифра. Благодаря немецким ключам шифрования, предоставленным французским шпионом, Бюро смогло реконструировать «Энигму» и начать расшифровывать немецкие сообщения. В то время немцы использовали только 6 штекеров, и польский метод «гриль» был осуществим. 1 августа 1936 года немцы начали использовать 8 штекеров, и это изменение сделало метод «гриль» менее эффективным. Бюро потребовался усовершенствованный метод для взлома немецкого шифра. Хотя штекеры и меняли буквы в цикле двойного ключа, они не меняли количество циклов или их длину. Штекерами можно было пренебречь. Игнорируя промежуточные переключения ключей, машина «Энигма» имела только 26³ различных настроек трех роторов, а три ротора можно было расположить в машине всего 1 = 3! = 6 способами. Это означало, что существовало лишь ограниченное число возможных перестановок двойного ключа. Бюро приступило к определению и каталогизации характеристик каждой из этих вероятных перестановок. Каждая буква ключа могла иметь одно из 13 = 101 возможных значений, а 3 буквы ключа означали, что существовало множество возможных ключей. В среднем, ключ находил одну настройку роторов, но мог найти и несколько возможных настроек. Польский криптоаналитик мог собрать достаточно трафика, чтобы определить все циклы в суточном ключе. Обычно это требовало около 60 сообщений. Результат мог быть следующим: он использовал длины циклов (132;102 32;102 22 12) для поиска порядка колес (II I III) и начальных позиций ротора в картотеке. Затем он использовал «Энигму» для вычисления циклов без штекеров: сравнивая штекерные циклы из немецкого трафика и нештекерные циклы, криптоаналитик мог определить штекеры. В примере перестановка CF имеет (e)(z) и (e)(w). Это требует, чтобы буква e была нештекерной, а WZ – штекерной. Затем циклы можно было выровнять по e и WZ для определения других штекерных и нештекерных букв. (pjxroquctwzsy)(kvgledmanhfib)/(kxtcoigweh)
(sjxroqtcuzwpy)(kngledamvhifb)/(kxucofgzeh)
(! ! ! **! )( ! = ! !! ! ! )/( ! ! *= )
Где = – известная нештекерная буква, * – известная штекерная буква, а ! – недавно обнаруженный штекер. Повторение давало штекеры AM, FI, NV, PS, TU, WZ. Подготовка картотеки, с использованием циклометра, изобретенного Реевским примерно в 1934 или 1935 году, была трудоемкой задачей, занявшей более года. Но как только картотека была завершена, получение суточных ключей «Энигмы» занимало около пятнадцати минут. Когда немцы изменили «рефлектор» или «обратный барабан» машины «Энигма» 1 ноября 1937 года, Шифровальное бюро было вынуждено начать все сначала с новой картотекой: «задача, – пишет Реевский, – которая, учитывая наш опыт, вероятно, заняла несколько менее года».

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 1=3!=6 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:

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