В XIX в. шифрование оказалось полезным не только для пересылки секретных сообщений. Появление телеграфа в первой трети века и затем, спустя 30 лет, развитие двусторонней телеграфной связи Томасом Альвой Эдисоном произвело революцию в коммуникации и, следовательно, изменило мир. Так как телеграф использовал электрические импульсы, нужен был метод для перевода текста сообщения на язык, который машина может воспроизвести и передать. Другими словами, необходимо было кодирование. Среди различных предложенных методов верх взяла система передачи букв точками и тире, придуманная американским художником и изобретателем Сэмюэлом Морзе. Азбуку Морзе можно считать предшественником кодов, которые многие десятилетия спустя неявно используются всеми нами для ввода данных в компьютеры и получения информации от них.
Азбука Морзе
Азбука Морзе использует комбинацию точек, тире и пробелов для представления букв алфавита, цифр и других символов. Таким образом, она переводит алфавит в набор знаков, которые могут быть выражены с помощью простых сигналов света, звука или электричества. Каждая точка соответствует единице времени продолжительностью около 1/25 доли секунды; каждое тире — три единицы времени (эквивалентно трем точкам). Длина пробелов между буквами — также три единицы времени, а пять единиц соответствуют пробелам между словами.
Сначала Морзе было отказано в патенте на этот код и в Соединенных Штатах, и в Европе. Лишь в 1843 г. он получил государственную субсидию для строительства телеграфной линии между Вашингтоном и Балтимором. В 1844 г. была произведена первая передача закодированного сообщения, и почти сразу была создана компания с целью охвата всей Северной Америки телеграфными линиями. К 1860 г., когда Наполеон III наградил Морзе орденом Почетного легиона, Соединенные Штаты и Европа уже были опутаны телеграфными проводами. К моменту смерти Морзе в 1872 г. в Америке было проложено более 300000 километров кабеля.
Сначала простое устройство, изобретенное в 1844 г. самим Морзе, использовалось для передачи и приема телеграфных сообщений. Оно состояло из телеграфного ключа, который служил для включения и отключения электрического тока, а также электромагнита, который получал поступающие сигналы. Каждый раз, когда нажимался ключ, — как правило, указательным или средним пальцем — возникал электрический контакт. Периодические импульсы, производимые нажатием телеграфного ключа, передавались по кабелю, состоящему из двух медных проводов.
Эти провода, поддерживаемые высокими деревянными «телеграфными» столбами, связывали различные телеграфные станции страны и часто тянулись на сотни километров.
* * *
НЕВЕРБАЛЬНАЯ КОММУНИКАЦИЯ
Так как Томас Альва Эдисон (1847–1931) плохо слышал, он общался со своей женой, Мэри Стиуэлл , с помощью азбуки Морзе. Во время ухаживания Эдисон сделал предложение, отстучав слова рукой, и она ответила тем же способом. Телеграфный код стал обычным средством общения для супругов. Даже когда они ходили в театр, Эдисон клал руку Мэри себе на колено, чтобы она могла «телеграфировать» ему диалоги актеров.
Первый телеграфный аппарат, изобретенный Сэмюэлом Морзе в 1844 г.
* * *
СИМФОНИЯ V-МАЖОР
Бетховен — еще один плохослышащий знаменитый человек, имя которого связано с телеграфом, хотя в данном случае лишь косвенно: первые четыре ноты Пятой Симфонии гениального композитора по ритму напоминают сообщение в азбуке Морзе: «точка точка точка тире».
В азбуке Морзе «точка точка точка тире» соответствуют букве V, первой букве английского слова «victory» («победа»). Поэтому на «Би-би-си» Пятая симфония Бетховена использовалась как позывные радиостанции перед началом всех трансляций для оккупированной Европы во время Второй мировой войны.
* * *
В приемном устройстве имелся электромагнит, представлявший собой катушку из медной проволоки, обмотанной вокруг железного сердечника. Когда катушка получала импульсы электрического тока, соответствующие точкам и тире, железный сердечник намагничивался и притягивал подвижную часть, также сделанную из железа. Она издавала характерный звук при ударе о магнит. Этот звук слышен как короткий «щелчок», если получена точка, и как более длительная нота — при получении тире. Первое время для отправки телеграммы с помощью такого устройства требовался человек-оператор, который настукивал кодированную версию сообщения на одном конце, и еще один человек получал и расшифровывал текст на другом конце.
Кодирование символов по азбуке Морзе производилось в соответствии со следующей таблицей:
Так, сообщение: «I love you» («Я тебя люблю») будет закодировано следующим образом:
Как уже говорилось ранее, азбука Морзе была в некотором смысле первым вариантом будущих цифровых систем связи. Чтобы продемонстрировать эту идею, мы легко можем преобразовать код Морзе в числа, заменяя каждую точку единицей, а каждое тире — нулем. Строки из нулей и единиц часто будут встречаться нам в следующих главах.
В XX в. благодаря изобретению радио традиционный телеграф заменила беспроводная связь. Телеграфисты недавнего прошлого стали радистами. Новая технология позволила обмениваться информацией с еще большей скоростью и в большем объеме.
Однако сообщения, посылаемые в виде электромагнитных волн, можно относительно легко перехватить. Это обеспечило криптоаналитиков большим количеством зашифрованного материала и помогло укрепить их позиции в борьбе с криптографами, потому что большинство шифров, используемых правительствами и тайными агентами, даже самые секретные, были основаны на известных алгоритмах. Так было и в случае с шифром Плейфера, изобретенным сэром Чарльзом Уитстоном и внедренным в практику госслужб Великобритании лордом Лайоном Плейфером. Шифр Плейфера был хитроумным вариантом шифра Полибия, но все-таки лишь вариантом. Подробнее о нем рассказано в Приложении.
* * *
СПАСИТЕ НАШИ ДУШИ, КОРАБЛЬ ИЛИ ЧТО-НИБУДЬ ЕЩЕ, НАЧИНАЮЩЕЕСЯ С БУКВЫ «S»
Самым известным сигналом в азбуке Морзе является SOS. Он был выбран группой европейских стран в качестве сигнала бедствия из-за простоты передачи (три точки, три тире, три точки) — эти буквы не являлись аббревиатурой. Тем не менее, вскоре появились альтернативные «расшифровки». Самым известным из этих «бэкронимов» является значение «Save Our Souls» («Спасите наши души»). Позже, так как сигнал часто использовали на море, популярным стало другое значение: «Save Our Ship» («Спасите наш корабль»).
* * *
Несмотря на изобретательность их создателей, расшифровка этих модифицированных шифров в конечном счете была вопросом времени и вычислительных мощностей. Криптографическая история Первой мировой войны прекрасно это иллюстрирует. Мы уже рассказали о слабости немецких дипломатических шифров во время инцидента с телеграммой Циммермана. Но оказалось, о чем сами немцы даже не подозревали, что другой их шифр, известный как ADFGVX и используемый для шифрования наиболее секретных сообщений, предназначенных для фронта, также был взломан вражескими криптоаналитиками, несмотря на то, что считался неуязвимым. Этот двойной провал немецких шифровальщиков Первой мировой войны привел к тому, что все стороны осознали необходимость разработки более надежных шифров. Этой цели можно было достигнуть, лишь сильно затруднив криптоанализ.
80 километров от Парижа
В июне 1918 г. германские войска готовились напасть на столицу Франции. Для союзников было крайне важно перехватить вражеские сообщения, чтобы выяснить, где именно произойдет вторжение. Немецкие сообщения, предназначенные для фронта, были зашифрованы шифром ADFGVX, который немецкие военные считали неуязвимым.
Наш интерес к этому шифру связан с тем, что он сочетает в себе алгоритмы подстановки и перестановочного шифрования. Это один из самых изощренных методов классической криптографии. Немцы начали использовать его в марте 1918 г., и как только французы узнали о его существовании, они отчаянно принялись за его взлом.
К счастью для них, в центральном шифровальном бюро работал талантливый криптоаналитик Жорж Панвэн. Он посвятил себя этой задаче, работая круглые сутки.
Ночью 2 июня 1918 г. Панвэну удалось расшифровать первое сообщение, зловещим содержанием которого был приказ фронту: «Ускорьте продвижение боевой техники. Даже в дневное время, лишь бы незаметно». В начале шифровки было указано, что она отправлена из местечка, расположенного между Мондидье и Компьень, в 80 километрах к северу от Парижа. Результат Панвэна позволил французам сорвать атаку и остановить продвижение немцев.
Как уже упоминалось, шифр ADFGVX состоит из двух частей: шифра подстановки и шифра перестановки. Первый шаг — подстановка — состоит в следующем: у нас имеется таблица размером 7 х 7, в которой первая строка и первый столбец содержат буквы ADFGVX (см. стр. 58). Остальные поля таблицы случайным образом заполняются 36 символами: 26 букв алфавита и цифры от 0 до 9. Расположение символов представляет собой ключ к шифру, и получателю, очевидно, нужна эта информация, чтобы понять содержание сообщения.
Мы будем использовать следующую таблицу:
Шифр сообщения состоит в замене каждого символа его координатами, выраженными группой букв ADFGVX. Первой координатой будет буква, соответствующая строке, а второй — соответствующая столбцу. Например, если мы хотим зашифровать цифру 4, мы должны написать DV. Сообщение Target is Paris («Цель — Париж») будет зашифровано следующим образом:
До сих пор мы использовали лишь простую подстановку, и частотного анализа было бы достаточно, чтобы расшифровать сообщение.
Однако этот шифр содержит второй шаг — перестановку. Она зависит от ключевого слова, о котором договорились отправитель и получатель. Этот шаг осуществляется следующим образом. Сначала мы построим таблицу с таким числом столбцов, сколько букв в ключевом слове, и заполним поля таблицы зашифрованным текстом.
Буквы ключевого слова пишут в верхнем ряду новой таблицы. В этом примере ключевое слово будет BETA. Построим таблицу, в которой первая строка состоит из букв ключевого слова и следующие строки содержат буквы, полученные после кодирования сообщения на этапе подстановки. Любые пустые ячейки заполняются цифрой ноль, которая, как видно из первой таблицы, имеет код AG.
Чтобы применить второй шаг к нашему сообщению «Цель — Париж», напомним сначала, что после подстановки оно выглядело так:
Используя ключевое слово BETA, мы получим следующую таблицу.
Применяя перестановочный шифр, изменим порядок столбцов, чтобы буквы ключевого слова были расположены в алфавитном порядке. Это даст нам следующую таблицу.
Зашифрованное послание получается, если брать буквы этой таблицы по столбцам. В нашем примере это будет:
AAXFAXGGFGVAFVXWXDVFFDGVFVA
Как мы видим, теперь сообщение состоит из вроде бы случайного набора букв A, D, F, G, V и X. Немцы выбрали эти шесть букв, потому что по звучанию в азбуке Морзе они сильно отличаются друг от друга, и получатель легко может отсеять возможные при передаче ошибки. Более того, поскольку сообщения состоят из шести букв, посылать такие телеграфные передачи могли даже неопытные операторы.
Если мы обратимся к таблице кодов Морзе в начале главы, то увидим следующие коды для каждой из букв шифра ADFGVX:
Чтобы расшифровать сообщение, получателю необходимо знать распределение букв и цифр в базисной таблице и ключевое слово.
Шифровальная машина «Энигма»
В 1919 г. немецкий инженер Артур Шербиус запатентовал машину для защищенной связи. Ее название, «Энигма», с тех пор стало синонимом военной тайны.
Несмотря на свою сложность, «Энигма», по сути, является улучшенной версией диска Альберти.
Благодаря относительной простоте использования и сложности выдаваемых шифров, система «Энигма» была выбрана германским правительством для шифрования большей части военных донесений в годы Второй мировой войны.
Именно поэтому расшифровка кодов «Энигмы» стала абсолютным приоритетом для правительств стран, воюющих с нацистской Германией. Когда это наконец удалось, сообщения, перехваченные и расшифрованные разведками союзников, оказались решающими для завершения военного конфликта. История расшифровки кода «Энигмы» — это захватывающая эпопея с участием отделов разведки Польши и Великобритании, а также гениального математика Алана Тьюринга, человека, считающегося отцом современной вычислительной техники. В результате работы по взлому кода «Энигмы» появился первый в мире компьютер, что можно считать самым значительным событием в долгой и яркой истории военного криптоанализа.
Слева: немецкие солдаты во время Второй мировой войны записывают сообщение, зашифрованное с помощью <<Энигмы». Справа: реплика четырехроторной «Энигмы».
«Энигма» представляла собой электромагнитное устройство, внешне похожее на пишущую машинку. Уникальной ее делало то, что ее механические части меняли положение после каждого нажатия клавиш, так что даже при нажатии подряд одной и той же буквы символ каждый раз кодировался по-новому.
На практике процесс шифрования был относительно прост. Сначала оператор устанавливал различные разъемы и роторы машины в соответствии с исходным положением, заданным справочником кодов, используемых на данный момент (эти справочники регулярно менялись). Затем он печатал первую букву открытого текста, и машина автоматически генерировала код, который появлялся на светящейся панели — это была первая буква зашифрованного сообщения.
Первое переключение ротора поворачивало его в одну из 26 возможных позиций. Каждое положение переключателя соответствовало новому шифру. После этого оператор вводил вторую букву и так далее. Чтобы расшифровать сообщение, достаточно было ввести зашифрованные символы в другую машину «Энигма» с теми же исходными параметрами, что и у машины, использованной для шифрования.
* * *
ТРАНШЕЙНЫЕ КОДЫ
В бою использовать сложные шифры, такие как ADFGVX, было очень трудно. Во время гражданской войны в Испании (1936–1939), например, применялся более простой шифр подстановки:
Как мы видим, несколько букв имеют более одного зашифрованного символа. Например, буква R может быть заменена на 28 или 54. Слово GUERRA («Война») будет зашифровано как 167427285453. Эти коды, которые фактически были шифром подстановки, получили название траншейных кодов и предназначались для особых целей.
Clave Violeta («фиолетовый ключ», слева) использовался 415-м батальоном 104-й бригады республиканцев и был перехвачен националистами. Примечание переводится как: «Шифры обязательно должны быть представлены в виде букв. Столбцы [строки] с пометкой (1) соответствуют алфавиту. Столбцы с пометкой (2) соответствуют их зашифрованным эквивалентам».
Для обеспечения более высокого уровня секретности националисты во главе с генералом Франко применили особое оружие — 30 машин «Энигма», присланных нацистскими союзниками.
Это было первое интенсивное использование в военных целях шифровальных устройств, которые Германия начала широко применять во время Второй мировой войны. Британцы пытались взломать код во время испанского конфликта, но безуспешно.
Телеграмма от 27 октября 1936 г. начальнику сектора Гэанада (республиканцу): «Ваша телеграмма, зашифрованная вчера… не подлежит расшифровке».
Зашифрованное сообщение республиканцев, перехваченное испанскими фашистами-фалангистами на Канарских островах.
* * *
На рисунке на следующей странице представлена упрощенная схема механизма «Энигмы», где для шифрования используются роторы с алфавитом из трех букв.
В результате каждый ротор имеет только три возможных позиции, а не 26, как в реальной машине.
Как мы видим, когда ротор машины «Энигма» находится в исходном положении, каждая буква открытого сообщения заменяется на другую, за исключением буквы А. После шифрования первой буквы ротор поворачивается на одну треть оборота.
В новой позиции буквам теперь соответствуют другие — не те, что в первом шифре.
Процесс завершается третьей буквой, после чего ротор возвращается в исходное положение и последовательность шифров повторяется.
Роторы стандартной машины «Энигма» имеют 26 позиций, по одной на каждую букву алфавита. Следовательно, с одним ротором можно применять 26 различных шифров. Таким образом, начальное положение ротора является ключевым.
Для увеличения количества возможных ключей дизайн «Энигмы» предусматривал до трех роторов, механически соединенных друг с другом. Когда первый ротор делал полный оборот, следующий переключался на одно положение, и так далее до полного оборота третьего ротора, что давало в общей сложности 26 х 26 х 26 = 17576 возможных шифров.
Кроме того, дизайн Шербиуса позволял изменять порядок переключателей, еще больше увеличивая количество шифров, как мы увидим ниже.
Трехроторная машина « Энигма » с частично открытым корпусом, позволяющим видеть коммутационную панель (спереди).
Кроме трех роторов «Энигма» также имела коммутационную панель, расположенную между первым ротором и клавиатурой. Коммутационная панель позволяла перекоммутировать соединения между буквами клавиатуры до соединения с ротором и таким образом добавляла значительное количество кодов к шифру. Стандартный дизайн «Энигмы» предусматривал шесть кабелей, которые могли соединять шесть пар букв. На следующем рисунке показана работа коммутационной панели, снова в упрощенной форме для трех букв и трех кабелей.
Таким образом, буква А меняется местами с буквой С, буква В — с буквой А, а С — с буквой В. С добавлением коммутационной панели упрощенная трехбуквенная «Энигма» будет работать следующим образом:
На сколько больше шифров мы получим при, казалось бы, простом добавлении коммутационной панели? Сначала посчитаем количество способов соединения шести пар букв, выбранных из 26 возможных. Число способов выбрать n пар букв из алфавита, содержащего N символов, определяется по формуле:
В нашем примере N = 26 и n = 6, что дает нам 100391791500 комбинаций.
Следовательно, общее количество шифров, возможных на машине «Энигма» с тремя роторами из 26 букв и коммутационной панелью с шестью кабелями, считается следующим образом.
1. Количество поворотов трех роторов дает 263 = 26∙26∙26 = 17 576 комбинаций.
2. Кроме того, три ротора (1, 2, 3) могут меняться друг с другом местами, например, 1–2—3, 1–3—2, 2–1—3, 2–3—1, 3–1—2, 3–2—1. Это дает нам дополнительные шесть комбинаций.
3. Наконец, мы подсчитали число способов соединять пары букв шестью кабелями на коммутационной панели, что дало нам 100391791500 дополнительных шифров.
Общее количество шифров получается умножением перечисленных результатови составляет 6 ∙ 17 576 ∙ 100 391 791 500 = 10 586 916 764 424 000. Таким образом, машина «Энигма» могла шифровать текст, используя более чем десять тысяч триллионов различных шифров. Германское правительство было в полной уверенности, что секретные коммуникации высшего уровня совершенно неуязвимы. И это было большой ошибкой.
Расшифровка кода «Энигмы»
Любой ключ кода «Энигмы» сначала указывал конфигурацию коммутационной панели, а именно возможные соединения шести пар букв, например, B/Z, F/Y, R/C, Т/Н, Е/О и L/J, что означало, что первый кабель менял местами буквы В и Z, итак далее. Во-вторых, ключ определял порядок роторов (например, 2–3—1). Наконец, ключ описывал исходную ориентацию роторов (например, буквы R, V, В показывали, какая буква находится в начальном положении, или начальные позиции).
Эти параметры были собраны в шифровальных книгах, которые тоже передавались в зашифрованном виде и могли меняться в установленные дни или при особых обстоятельствах. Например, некоторые ключи были зарезервированы для определенных типов сообщений.
Чтобы не повторять один и тот же шифр в течение одного дня, во время которого могли быть посланы тысячи сообщений, операторы «Энигмы» использовали гениальные трюки для выбора новых шифров в особых случаях, но без замены всей шифровальной книги. Так, оператор отправлял сообщение из шести букв, зашифрованное в соответствии с действующим в этот день кодом, представляющее собой новый набор начальных позиций для роторов, например, T-Y-J. (Для большей безопасности оператор шифровал эти три буквы два раза, поэтому и получалось шесть букв). Затем он шифровал настоящее сообщение в соответствии с этим новым ключом. Другой оператор получал сообщение, которое он не мог расшифровать с ключом этого дня, но он знал, что первые шесть букв на самом деле являлись инструкцией переставить роторы в другую позицию. Получатель делал это, оставляя коммутационную панель и порядок роторов без изменения, и затем мог правильно расшифровать сообщение.
Союзники получили первые ценные сведения относительно «Энигмы» в 1931 г. от немецкого шпиона Ганса-Тило Шмидта. Это были различные инструкции для работы с машиной. Контакт со Шмидтом установили французские спецслужбы, которые впоследствии поделились информацией с польскими коллегами. Польский криптоаналитический отдел, Biuro Szyfrow (шифровальное бюро), начал работу с документами Шмидта, а также добыл несколько машин «Энигма», украденных у немцев.
Не совсем обычный штрих для того времени: в польском отделе работало большое количество математиков. Среди них был талантливый 23-летний застенчивый молодой человек по имени Мариан Реевский. Он сразу же сосредоточил усилия на шести буквенных кодах в начале многих ежедневных сообщений, которыми обменивались немцы. Реевский предположил, что последние три буквы кода были новым шифром для первых трех, и поэтому понял, что четвертая, пятая и шестая буквы могли дать ключ для начальных позиций роторов.
На этой, казалось бы, незначительной гипотезе Реевский построил незаурядную систему умозаключений, которая привела к расшифровке кода «Энигмы».
Подробности этого процесса достаточно сложны, и мы не будем здесь их излагать, но после нескольких месяцев Реевский смог сократить количество возможных шифров с десяти тысяч триллионов до всего лишь 105 456, что соответствовало различным комбинациям расположения роторов и их начальных позиций. Для этого Реевский создал устройство, известное как Bombe («Бомба»), которое работало так же, как «Энигма», и могло имитировать любую из возможных позиций трех роторов для поиска ежедневного кода. Уже в 1934 г. сотрудники польского шифровального бюро взломали код «Энигмы» и могли расшифровать любое сообщение в течение 24 часов.
Хотя немцы не знали, что польские криптоаналитики расшифровали код «Энигмы», они продолжали совершенствовать систему, которая уже успешно работала на протяжении более чем десятилетия. В 1938 г. операторы «Энигмы» получили дополнительные два ротора к трем стандартным, и вскоре после этого были выпущены новые модели машин с десятью коммутационными кабелями.
Тогда число возможных шифров возросло до почти 159 квинтиллионов. Лишь добавление еще двух роторов увеличивало возможные комбинации их расположения с шести до 60: пять возможностей поместить любой из пяти роторов на первом месте, умноженные на четыре возможности поставить любой из четырех оставшихся роторов на второе место, умноженные на три возможности поставить любой из трех оставшихся роторов на третье место. Итого 5 x 4 x 3 = 60. Даже сумев расшифровать код, сотрудники польского бюро не имели средств, необходимых для анализа такого количества расположений роторов.
Некоторые версии машины « Энигма »
Британцы принимают эстафету
Обновление машин «Энигма» не было случайным: Германия уже начала агрессивную экспансию в Европу с аннексии Чехословакии и Австрии и планировала вторжение в Польшу. В 1939 г. в связи со вспыхнувшим в сердце Европы конфликтом и завоеванием их страны поляки передали все машины «Энигма» и сведения о них британским союзникам, которые в августе того же года решили объединить свои ранее рассредоточенные криптоаналитические отделы. Новым центром был выбран особняк, расположенный на окраине Лондона, в поместье Блетчли-Парк. В команду Блетчли-Парка был включен блестящий криптоаналитик, молодой кембриджский математик Алан Тьюринг. Он был мировым авторитетом в тогда еще только зарождавшейся теории вычислений и был открыт для работы на новых, революционных проектах. Расшифровка усовершенствованных машин «Энигма» оказалась серьезным импульсом для ускоренного развития теории вычислений.
Эксперты за работой в Блетчли-Парке, где был расшифрован код « Энигмы ».
Эксперты Блетчли-Парка сосредоточились на расшифровке коротких фрагментов зашифрованного текста, содержание которых они примерно знали. Например, благодаря «полевым» шпионам было известно, что немцы около шести вечера каждый день передавали кодированные сообщения о метеорологических условиях в различных точках вдоль линии фронта. Таким образом, можно было с достаточной степенью уверенности ожидать, что сообщение, перехваченное вскоре после этого часа, содержало зашифрованные версии таких слов, как «погода» и «дождь». Тьюринг изобрел электрическую систему, которая менее чем за пять часов позволяла воспроизвести все возможные 1054650 комбинаций расположения трех роторов.
В эту систему вводили зашифрованные символы, которые по их длине или другим признакам, возможно, соответствовали словам «погода» и «дождь».
Предположим, мы подозреваем, что зашифрованные символы FGRTY соответствуют слову BREAD («хлеб»). После введения шифровки в машину, если при каком-то положении роторов получалось слово BREAD, криптоаналитики знали, что найден ключ, соответствующий конфигурации начальных позиций роторов. Затем оператор вводил зашифрованный текст в настоящую машину «Энигма» с роторами, расположенными в соответствии с найденным ключом. Если машина показывала, например, расшифрованный текст DREAB, было ясно, что часть шифра связана с конфигурацией коммутационной панели и включает перестановку букв D и В. Таким образом криптоаналитики получали весь шифр. Секреты «Энигмы» постепенно раскрывались. В процессе разработки и совершенствования вышеупомянутых аналитических методов команда Блетчли-Парка построила первую в истории программируемую вычислительную машину, названную Colossus.
Colossus , предшественник современного компьютера, в Блетчли-Парке. Фотография, сделанная в 1943 г., показывает панель управления сложного устройства.
Другие шифры Второй мировой войны
Япония разработала две собственные системы шифрования: Purple («Пурпурный код») и JN-25. Первая из них предназначалась для дипломатической связи, а вторая — для военных сообщений. Оба шифра использовали механические устройства.
JN-25, например, работал на алгоритме подстановки, который переводил символы японского языка (порядка 30000 знаков) в ряд чисел, определенных случайными таблицами из пяти групп чисел. Несмотря на меры предосторожности, предпринятые в Японии, англичане и американцы взломали «Пурпурный код» и шифр JN-25. Сведения из расшифрованной переписки получили кодовое название «Мэджик» и оказали значительное влияние на военные конфликты в Тихом океане, в частности, на сражение в Коралловом море и у атолла Мидуэй в 1942 г. Сведения «Мэджик» были также использованы для планирования стратегических задач, таких как перехват и уничтожение самолета японского адмирала Ямамото год спустя.
* * *
БЛЕСТЯЩИЙ УМ
Алан Тьюринг (слева) родился в Англии в 1912 г. Даже в молодости он демонстрировал большие способности к математике и физике. В 1931 г. он поступил в Кембриджский университет, где увлекся работами логика Курта Гёделя по общей проблеме неполноты любой логической системы. За три года до того он опубликовал работу о теоретической возможности создания машины, способной выполнять вычислительные алгоритмы, такие как сложение, умножение и т. д.
Вдохновленный работами Гёделя, Тьюринг в 1937 г. развил свои идеи о доказательствах и вычислениях и сформулировал принцип «универсальной машины», способной выполнять любые мыслимые алгоритмические действия. Так появилась одна из основ современной информатики. За два года до того Тьюринг познакомился с крупным венгерским математиком Яношем фон Нейманом , который к тому времени жил в Соединенных Штатах и носил имя Джон. Фон Нейман , считающийся «вторым отцом» информатики, предложил Тьюрингу хорошо оплачиваемую и престижную работу в Принстоне. Однако Тьюринг предпочел богемную атмосферу Кембриджа и отклонил предложение.
В 1939 г., когда началась война, он присоединился к британской команде криптоаналитиков в Блетчли-Парке. За свою работу во время войны он был награжден Орденом Британской империи. Но Тьюринг был гомосексуалистом, что было запрещено законом в то время, и в результате приговора в 1952 г. потерял право работать на секретных проектах правительства. Глубоко подавленный, Алан Тьюринг покончил жизнь самоубийством 8 июня 1954 г., приняв цианистый калий.
Шифровальщики навахо
Хотя Соединенные Штаты умело использовали информацию, перехваченную у противника во время военных действий на Тихом океане, американские военные для собственной связи применяли несколько шифров, по сути похожих на те, о которых говорилось в начале книги. Алгоритмы шифрования были основаны непосредственно на природе слов. Эти шифры — чокто, команче, месквоки и прежде всего навахо — не были четко описаны в сложных руководствах и не были результатом работы отделов криптографии: это были просто подлинные языки индейцев.
Армия Соединенных Штатов включала радистов из этих племен в отделы шифровальщиков на фронте, чтобы они передавали сообщения на своих языках, на которых не говорили не только японцы, но и другие американские военные. Эти сообщения дополнительно шифровались простыми кодами, чтобы захваченные в плен солдаты не смогли их перевести. Такие радисты служили в американских отделах вплоть до Корейской войны.
Два шифровальщика навахо во время битвы за Бугенвиль в 1943 г.
Нововведения: шифр Хилла
Шифры, обсуждавшиеся прежде, в которых один символ заменялся другим по некоторому заранее установленному правилу, как мы уже видели, всегда уязвимы для криптоанализа.
В 1929 г. американский математик Лестер Хилл придумал, запатентовал и выставил на продажу — правда, без особого успеха — новую систему шифрования, в которой использовались и модульная арифметика, и линейная алгебра.
Как мы увидим ниже, матрицы являются очень полезным инструментом для шифрования сообщений, когда текст разбивается на пары букв и каждой букве ставится в соответствие числовое значение.
Чтобы зашифровать сообщение, мы будем использовать следующие матрицы:
с определителем, равным единице, то есть ad — Ьс = 1. Для расшифровки мы будем использовать обратную матрицу:
* * *
НЕМНОГО ЛИНЕЙНОЙ АЛГЕБРЫ
Матрица может быть определена как таблица, представляющая собой совокупность строк и столбцов. Например, матрица 2x2 имеет вид:
а матрица 2x1 записывается как:
Произведение этих двух матриц дает нам новую матрицу 2x1, называемую вектор-столбцом:
В случае матрицы 2x2 число ( аd — Ьс ) называется определителем матрицы.
* * *
Ограничение на значение определителя установлено для того, чтобы обратная матрица работала как инструмент расшифровки. Как правило, для алфавита из n символов необходимо, чтобы НОД определителя матрицы и числа n равнялся единице. Иначе нельзя гарантировать существование обратного элемента в модульной арифметике.
Продолжая пример, возьмем алфавит из 26 букв с символом пробела, который мы обозначим как @. Каждой букве мы поставим в соответствие число, как показано в следующей таблице:
Для получения значений от 0 до 26 мы будем работать по модулю 27.
Процесс шифрования и расшифровки текста происходит следующим образом: сначала мы определяем шифровальную матрицу с определителем 1.
Например, 
Матрицей для расшифровки будет обратная матрица 
Таким образом, А будет ключом шифра, А -1 — ключом для расшифровки.
Например, зашифруем сообщение BOY («мальчик»). Буквы сообщения группируются в пары: ВО У@. Их численными эквивалентами, согласно таблице, являются пары чисел (1, 14) и (24, 26). Умножим матрицу А на каждую пару чисел.
Зашифрованное 
что, согласно таблице, соответствует буквам (Q, Т).
Зашифрованное 
что соответствует буквам (V, О).
Сообщение BOY будет зашифровано как QTVO.
Обратная операция расшифровки выполняется при помощи матрицы:
Возьмем пару букв (Q, Т) и найдем их числовые эквиваленты из таблицы: (16, 19). Затем умножим их на A -1 и получим:
то же со второй парой (V, О) и ее численными значениями (21, 14) и получаем:
Таким образом, мы доказали, что расшифровка работает.
В этом примере мы рассматривали пары символов. Для большей безопасности можно группировать буквы по три или даже по четыре. Тогда расчеты будут проводиться с матрицами порядка 3 х 3 и 4 х 4 соответственно, что было бы чрезвычайно трудоемким процессом для вычислений вручную. Современные компьютеры позволяют работать с огромными матрицами и с обратными к ним.
У шифра Хилла есть существенный недостаток: имея даже небольшой фрагмент исходного текста, можно расшифровать все сообщение. Поиск идеального шифра был еще далек от завершения.