Эмулятор «Бомбы» Тьюринга на Raspberry Pi и Arduino

7aa4cd5fa52f46bd930c44a8de30abc1.jpg«Энигма» — это серия немецких электромеханических роторных шифровальных машин, которые использовались с двадцатых годов прошлого века. В том числе время активной передачи зашифрованных на «Энигме» сообщений попадает на период Второй мировой войны. В связи с этим появилась огромная практическая ценность взлома шифрования «Энигмы».

Для взлома кодов «Энигмы» польское Бюро шифров разработало Криптологическую бомбу, с помощью которой осуществлялся взлом сообщений. Всего было создано шесть машин под шесть комбинаций роторов, которые имели ограниченную сферу применения из-за специфичности условий, предъявляемых к зашифрованному сообщению. Машины быстро потеряли смысл с вводом новых роторов, а создать ещё 54 «бомбы» у польской стороны не было ресурсов. После этого пришлось вернуться к ручным методам — листам Зыгальского. С учётом польских наработок была создана более совершенная Bombe, электромеханическая машина, которую чаще всего связывают с личностью Алана Тьюринга. Всего было построено порядка полутора сотен британских «бомб». После окончания Второй мировой войны почти все «Бомбы» были уничтожены по соображениям секретности.

Хотя в свободном обращении есть документация по устройству «бомб», успешные попытки воссоздать «Бомбу» можно пересчитать по пальцам одной руки. Это, к примеру, работоспособная реконструкция Bombe Rebuild Project команды любителей под руководством Джона Харпера. На создание реплики ушло 13 лет. Вчера в сети свой куда более скромный проект опубликовал любитель из Новой Зеландии. Это эмулятор из трёх роторов. В реальной «Бомбе» было 26 соединённых между собой троек.
В «Энигме» использовался полиалфавитный шифр, наиболее известным примером которого является шифр Вижинера. Можно вкратце описать принцип работы шифра как динамический шифр Цезаря, в котором глубина сдвига меняется по определённому алгоритму. Сердцы «Энигмы» — это три ротора, хотя позднее создавались и экземпляры с четырьмя. На каждом из роторов с двух сторон нанесены 26 контактов, соответствующие буквам алфавита. Электрические соединения дорожек между контактами не идут по прямой, они отличаются от ротора к ротору. Роторы можно вынимать, менять их расположение или вставлять другие роторы из набора. С января 1939 года в сухопутных войсках и авиации набор состоял из 5 роторов, что давало 60 комбинаций, а во флоте — 8 (336 комбинаций).

b762d9ed19984c30bd62c3bf495bd5ef.png

Дополнительной мерой является использование коммутационной панели. Электрические соединения проводами на панели спереди машины позволяют менять буквы по парам: A становится R, а R — A. Для чтения сообщения нужно знать положение роторов на шпинделе, какие роторы и отражатель из набора использовались, код шифрования (3 символа латинского алфавита) и положения проводов на коммутационной панели. В некоторых версиях вводились другие меры: отражатель тоже вращался, использовалось большее количество роторов и так далее.

1eb9584a73144c6595a535b5b9144a1a.jpg

После нажатия на клавишу ток проходил по электрическим дорожкам от клавиши, по контактам на коммутационной панели, через три ротора с различным положением дорожек, возвращался через отражатель и повторно через три ротора. Затем зажигалась лампочка на панели с соответствующей буквой шифра. Как минимум один ротор совершал движение, меняя шифр для шифрования следующей буквы. Роторы вращались подобно секундной, минутной и часовой стрелке в механических часах: быстрый правый ротор совершал полный оборот, а затем движение совершал средний. После полного оборота среднего движение совершал самый медленный левый.

«Бомба» помогала установить возможные настройки «Энигм» в немецких войсках. Она не выдавала готовые сообщения. Для завершения работы требовался всё тот же ручной труд. «Бомбы» помогали сократить число возможных решений до допустимого и доступного для обработки.

Чтобы расшифровывать сообщения требовались так называемые «подсказки». Осуществлялась атака на основе открытых текстов (known-plaintext attack): зашифрованный текст проверялся на возможность содержания знакомых слов и фраз. Нахождение «подсказок» требовало знания немецкого военного слэнга и стиля общения операторов связи. Немалую роль сыграла конструкция отражателя: буква никогда не могла быть зашифрована сама в себя. После выбора подсказки составлялось так называемое «меню», программа поиска возможных решений. Прогон «меню» прерывался остановками с решениями-кандидатами, которые затем проверялись. Обычно до нахождения правильного случалось много остановок с неправильными решениями.

Любитель из Новой Зеландии воссоздал «Бомбу». Вернее было бы сказать, что он воссоздал эмулятор одного из 26 блоков дешифровальной машины. Созданное устройство компактно — его можно поставить на стол. Вычисления выполняются на Raspberry Pi 2. Устойство даже не скрывает это: результат выводится до окончания движения роторов. Три барабана одинакового цвета (в оригинале они имели специальные цвета по выполняемой задаче) вращаются сугубо для косметического эффекта. Но они делают это очень убедительно и с той же скоростью, что и оригинал. За процессом приятно наблюдать.


В видеоролике запускается то самое «меню» с докладом о погоде, которое использовали для демонстрации реальной «Бомбы». Легко понять, почему: оно наглядно.

Проекту помогали руководитель команды по созданию полноценной реплики Джон Харпер и несколько других экспертов. Сначала любитель создал часы-бомбу — полнофункциональную версию машины для взлома «Энигмы», которую можно носить на запястье.

e5996de1fef64cbfa4d44ce8773958da.jpg

Внутри настольной «Бомбы» находится плата Raspeberry Pi 2, Arduino, свинцово-кислотный аккумулятор на 12 вольт и вольтметр. Эмулятор потребляет немало энергии и легко вытягивает по 1,5—2 ампера. Изначально софт для работы писался на Basic, но позднее его портировали на С++. Raspberry Pi 2 соединяется с Arduino и управляет тремя шаговыми электродвигателями. Arduino сообщает плате Raspeberry Pi 2 позицию двигателей в виде серии импульсов, чтобы их можно было остановить в нужный момент. На боку расположен жидкокристаллический дисплей, который играет роль механического индикатора оригинальной «Бомбы». Кнопки начала работы и прерывания расположены спереди как у реального образца.

c2d5a206fe2e4e54a85d12877708a493.jpg

Корпус выполнен из стали толщиной 0,8 мм, а барабаны в масштабе 3/4 — из обычных консервных банок. Все части устройства сделаны вручную. Масса составляет порядка 10 килограммов. Файлы с «меню» подгружаются с флэшки, которую можно вставить, открыв крышку сзади. Также сбоку расположен сетевой порт для мониторинга работы эмулятора. В работе устройство шумит двигателями, хотя громкость не сравнить с шумом реальной «Бомбы».

Автор обещает опубликовать исходный код программы устройства, хотя без существующего в единственном экземпляре «железа» его не на чем запускать. Остаётся пожелать автору не приносить его творение в школу и уж тем более не объяснять, что это такое.

Страница проекта с фотографиями
Онлайн-симулятор «Бомбы» Тьюринга

© Geektimes