Вклад Соона Таттта в расшифровку немецких шифров во время Второй мировой войны.

Введение

Британский и канадский криптограф и математик.

Вторая мировая война

Вскоре после начала Второй мировой войны преподаватель Тютте, Патрик Дафф, предложил его для работы в правительственной школе кода и шифров в Блетчли-парке (BP). Он прошел собеседование и был отправлен на учебный курс в Лондон, прежде чем прибыть в Блетчли-Парк, где присоединился к исследовательскому отделу. Сначала он работал над шифром Хагелина, используемым итальянским флотом. Это была коммерчески доступная роторная шифровальная машина, поэтому механика шифрования была известна, а для дешифровки сообщений требовалось лишь определить настройку машины. Летом 1941 года Тютте был переведен на проект под названием "Fish" ("Рыба"). Разведданные показали, что немцы называли беспроводные телепринтерные системы передачи "Sägefisch" (пила). Это привело к тому, что британцы стали использовать кодовое название Fish для немецкой системы шифрования телепринтеров. Прозвище Tunny (тунец) было использовано для первого канала связи, отличного от азбуки Морзе, и впоследствии применялось к машинам Lorenz SZ и трафику, который они шифровали. В телеграфии использовался 5-битный Международный телеграфный алфавит № 2 (ITA2). Ничего не было известно о механизме шифрования, кроме того, что сообщениям предшествовал 12-буквенный индикатор, что указывало на 12-роторную шифровальную машину. Поэтому первым шагом было диагностировать машину, установив ее логическую структуру и, следовательно, принцип работы. Тютте сыграл ключевую роль в этом, и лишь незадолго до победы союзников в Европе в 1945 году Блетчли-Парк получил шифровальную машину Tunny Lorenz. Прорывы Тютте в конечном итоге привели к массовому дешифрованию сообщений, зашифрованных Tunny, между немецким верховным командованием (OKW) в Берлине и их армейскими подразделениями по всей оккупированной Европе, и внесли – возможно, решающий – вклад в поражение Германии. На своем учебном курсе Тютте обучили технике экзамена Касиски, заключающейся в записи ключа на клетчатой бумаге, начиная новую строку после определенного количества символов, которое, как предполагалось, было частотой повторения ключа. Если это число было верным, то в столбцах матрицы наблюдалось бы больше повторений последовательностей символов, чем можно было бы объяснить случайностью. Тютте знал, что в индикаторах Tunny использовалось 25 букв (без J) для 11 позиций и только 23 буквы для остальных. Поэтому он применил технику Касиски к первому импульсу ключевых символов, используя повторение 25 × 23 = 575. Он не заметил большого количества повторений в столбцах с этим периодом, но обнаружил это явление по диагонали. Поэтому он попробовал снова с периодом 574, что выявило повторения в столбцах. Узнав, что простые множители этого числа – 2, 7 и 41, он попробовал снова с периодом 41 и "получил прямоугольник из точек и крестов, изобилующий повторениями". Однако стало ясно, что первый импульс ключа был сложнее, чем тот, который генерируется одним колесом с 41 ключевым импульсом. Тютте назвал эту составляющую ключа (chi1). Он предположил, что существует еще одна составляющая, которая складывается по модулю 2 (XOR) с этой, и которая не всегда меняется с каждым новым символом, и что она является произведением колеса, которое он назвал (psi1). То же самое относилось к каждому из пяти импульсов (и). Таким образом, для одного символа весь ключ K состоял из двух компонентов:

Soon after the outbreak of the Second World War, Tutte's tutor, Patrick Duff, suggested him for war work at the Government Code and Cypher School at Bletchley Park (BP). He was interviewed and sent on a training course in London before going to Bletchley Park, where he joined the Research Section. At first, he worked on the Hagelin cipher that was being used by the Italian Navy. This was a rotor cipher machine that was available commercially, so the mechanics of enciphering was known, and decrypting messages only required working out how the machine was set up. In the summer of 1941, Tutte was transferred to work on a project called Fish. Intelligence information had revealed that the Germans called the wireless teleprinter transmission systems "Sägefisch" (sawfish). This led the British to use the code Fish for the German teleprinter cipher system. The nickname Tunny (tunafish) was used for the first non Morse link, and it was subsequently used for the Lorenz SZ machines and the traffic that they enciphered. Telegraphy used the 5 bit International Telegraphy Alphabet No. 2 (ITA2). Nothing was known about the mechanism of enciphering other than that messages were preceded by a 12 letter indicator, which implied a 12 wheel rotor cipher machine. The first step, therefore, had to be to diagnose the machine by establishing the logical structure and hence the functioning of the machine. Tutte played a pivotal role in achieving this, and it was not until shortly before the Allied victory in Europe in 1945, that Bletchley Park acquired a Tunny Lorenz cipher machine. Tutte's breakthroughs led eventually to bulk decrypting of Tunny enciphered messages between the German High Command (OKW) in Berlin and their army commands throughout occupied Europe and contributed—perhaps decisively—to the defeat of Germany. At his training course, Tutte had been taught the Kasiski examination technique of writing out a key on squared paper, starting a new row after a defined number of characters that was suspected of being the frequency of repetition of the key. If this number was correct, the columns of the matrix would show more repetitions of sequences of characters than chance alone. Tutte knew that the Tunny indicators used 25 letters (excluding J) for 11 of the positions, but only 23 letters for the other. He therefore tried Kasiski's technique on the first impulse of the key characters, using a repetition of 25 × 23 = 575. He did not observe a large number of column repetitions with this period, but he did observe the phenomenon on a diagonal. He therefore tried again with 574, which showed up repeats in the columns. Recognising that the prime factors of this number are 2, 7 and 41, he tried again with a period of 41 and "got a rectangle of dots and crosses that was replete with repetitions". It was clear, however, that the first impulse of the key was more complicated than that produced by a single wheel of 41 key impulses. Tutte called this component of the key (chi1). He figured that there was another component, which was XOR ed with this, that did not always change with each new character, and that this was the product of a wheel that he called (psi1). The same applied for each of the five impulses ( and ). So for a single character, the whole key K consisted of two components:

В Блетчли-парке импульсы "марки" обозначались "x", а импульсы "пробела" – "•". Например, буква "H" кодировалась как "••x•x". Вывод Тютте о компонентах chi и psi стал возможен благодаря тому, что точки с большей вероятностью следовали за точками, а кресты – за крестами. Это было следствием слабости в немецкой процедуре установки ключа, которую они позже устранили. После этого прорыва остальные члены исследовательского отдела присоединились к изучению других импульсов, и было установлено, что все пять колес chi сдвигались с каждым новым символом, а все пять колес psi двигались вместе под управлением двух колес mu или "моторов". В течение следующих двух месяцев Тютте и другие члены исследовательского отдела разработали полную логическую структуру машины, с набором колес, несущих кулачки, которые могли находиться либо в положении (поднятом), добавляя "x" к потоку ключевых символов, либо в альтернативном положении, добавляя "•". Диагностика работы машины Tunny таким образом была поистине выдающимся криптоаналитическим достижением, которое, в цитате к награждению Тютте орденом Канады, было описано как "один из величайших интеллектуальных подвигов Второй мировой войны".

Статистический метод Тютте

Для расшифровки сообщения Тунни требовалось знание не только логического функционирования машины, но и начальных позиций каждого ротора для конкретного сообщения. Велись поиски процесса, который бы обрабатывал шифротекст или ключ, чтобы получить распределение частот символов, отклоняющееся от равномерности, к которой стремился процесс шифрования. В июле 1942 года, находясь в командировке в Исследовательском отделе, Алан Тьюринг выяснил, что операция XOR над значениями последовательных символов в потоке шифротекста и ключа усиливает любые отклонения от равномерного распределения. Полученный поток (обозначаемый греческой буквой "дельта" Δ) назывался разностью, поскольку XOR эквивалентен вычитанию по модулю 2. Это дало возможность проникнуть в Tunny, потому что, хотя частотное распределение символов в шифротексте нельзя было отличить от случайного потока, это не относилось к версии шифротекста, из которой был удален компонент чи ключа. Это объяснялось тем, что если в открытом тексте встречался повторяющийся символ, а колеса пси не сдвигались, то дифференцированный символ пси был бы нулевым символом ("/" в Блетчли-Парке). При операции XOR с любым символом этот символ не оказывает влияния. Повторяющиеся символы в открытом тексте встречались чаще как из-за особенностей немецкого языка (EE, TT, LL и SS относительно распространены), так и потому, что телеграфисты часто повторяли символы сдвига цифр и сдвига букв, поскольку их потеря в обычном телеграфном сообщении могла привести к бессмыслице. Как указано в "Общем отчете о Тунни": "Тьюрингер ввел принцип, согласно которому ключ, дифференцированный на единицу (теперь называемый ΔΚ), может дать информацию, недоступную из обычного ключа. Этот принцип Δ стал фундаментальной основой почти всех статистических методов взлома и настройки колес. Суть этого метода заключалась в поиске начальных настроек компонента чи ключа путем последовательной проверки всех возможных положений его комбинации с шифротекстом и поиска признаков неравномерности, отражающих характеристики исходного открытого текста. Любые повторяющиеся символы в открытом тексте всегда генерировали •, и аналогично генерировали • всякий раз, когда колеса пси не сдвигались, и примерно в половине случаев, когда они сдвигались – около 70% в целом. Помимо применения дифференцирования к полным 5-битным символам кода ITA2, Тютте применил его к отдельным импульсам (битам). Необходимо было установить текущие настройки колес чи, чтобы можно было сгенерировать соответствующую последовательность символов этих колес. Генерация 22 миллионов символов со всех пяти колес чи была непрактичной, поэтому изначально она была ограничена 41 × 31 = 1271 символами с первых двух колес. После объяснения своих результатов Максу Ньюману, Ньюману было поручено разработать автоматизированный подход к сравнению шифротекста и ключа для выявления отклонений от случайности. Первая машина получила название Heath Robinson, но гораздо более быстрый компьютер Colossus, разработанный Томми Флауэрсом и использующий алгоритмы, написанные Тьютте и его коллегами, вскоре взял на себя задачу взлома кодов.

To decrypt a Tunny message required knowledge not only of the logical functioning of the machine, but also the start positions of each rotor for the particular message. The search was on for a process that would manipulate the ciphertext or key to produce a frequency distribution of characters that departed from the uniformity that the enciphering process aimed to achieve. While on secondment to the Research Section in July 1942, Alan Turing worked out that the XOR combination of the values of successive characters in a stream of ciphertext and key emphasised any departures from a uniform distribution. The resultant stream (symbolised by the Greek letter "delta" Δ) was called the difference because XOR is the same as modulo 2 subtraction. The reason that this provided a way into Tunny was that although the frequency distribution of characters in the ciphertext could not be distinguished from a random stream, the same was not true for a version of the ciphertext from which the chi element of the key had been removed. This was the case because where the plaintext contained a repeated character and the psi wheels did not move on, the differenced psi character would be the null character ('/ ' at Bletchley Park). When XOR ed with any character, this character has no effect. Repeated characters in the plaintext were more frequent both because of the characteristics of German (EE, TT, LL and SS are relatively common), and because telegraphists frequently repeated the figures shift and letters shift characters as their loss in an ordinary telegraph message could lead to gibberish. To quote the General Report on Tunny:<blockquote>Turingery introduced the principle that the key differenced at one, now called ΔΚ, could yield information unobtainable from ordinary key. This Δ principle was to be the fundamental basis of nearly all statistical methods of wheel breaking and setting. The essence of this method was to find the initial settings of the chi component of the key by exhaustively trying all positions of its combination with the ciphertext, and looking for evidence of the non uniformity that reflected the characteristics of the original plaintext. Because any repeated characters in the plaintext would always generate •, and similarly would generate • whenever the psi wheels did not move on, and about half of the time when they did – some 70% overall. As well as applying differencing to the full 5 bit characters of the ITA2 code, Tutte applied it to the individual impulses (bits). The current chi wheel cam settings needed to have been established to allow the relevant sequence of characters of the chi wheels to be generated. It was totally impracticable to generate the 22 million characters from all five of the chi wheels, so it was initially limited to 41 × 31 = 1271 from the first two. After explaining his findings to Max Newman, Newman was given the job of developing an automated approach to comparing ciphertext and key to look for departures from randomness. The first machine was dubbed Heath Robinson, but the much faster Colossus computer, developed by Tommy Flowers and using algorithms written by Tutte and his colleagues, soon took over for breaking codes.

Личная жизнь и смерть

Помимо карьерных преимуществ работы в новом Университете Ватерлоо, Биллу и его жене Доротее пришлась по душе более сельская обстановка округа Ватерлоо. Они купили дом в близлежащей деревне Вест-Монтроуз, провинция Онтарио, где наслаждались пешими прогулками, проводили время в своем саду на реке Гранд и позволяли другим любоваться прекрасными пейзажами их участка. Они также прекрасно знали всех птиц, обитавших в их саду. Доротея, увлеченная гончарным делом, также любила пешие походы, а Билл организовывал туристические поездки. Даже под конец жизни Билл оставался любителем прогулок. После смерти жены в 1994 году он вернулся в Ньюмаркет (Суффолк), но затем вновь переехал в Ватерлоо в 2000 году, где скончался два года спустя. Он похоронен на кладбище Вест-Монтроуз Объединенной церкви.