Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Таким образом, буква А меняется местами с буквой С, буква В — с буквой А, а С — с буквой В. С добавлением коммутационной панели упрощенная трехбуквенная «Энигма» будет работать следующим образом:
На сколько больше шифров мы получим при, казалось бы, простом добавлении
В нашем примере 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 комбинаций расположения трех роторов.