Игра в имитацию: что же тут происходит?

Ростислав Бородин
1526
0

В недавно вышедшем на российские экраны байопике Алана Тьюринга отец компьютеров бьется над невероятно важной задачей — расшифровкой немецкой шифровальной машины Энигма. Опустим кинематографические подробности и разберемся в самом интересном: что же происходит в фильме с точки зрения программиста?

Давайте сначала пройдемся по краткой истории шифров: самый первый известный человечеству шифр был придуман для передачи сообщений еще до наступления нашей эры Гаем Юлием Цезарем. В нем каждый символ «открытого текста» (т.е. того, что мы прячем) заменялся на отстающий в алфавите на фиксированное число символов, например, на 3:

Cezar.JPG

В общем случае шифр, в котором каждая буква однозначно заменяется на другую букву, называется моноалфавитным шифром. Чтобы расшифровать такое сообщение, достаточно иметь таблицу с исходной заменой или…применить частотный анализ. В каждом языке в тексте одни буквы встречаются реже, а другие чаще. Если сообщение достаточно большое, то можно проанализировать, какие буквы в шифровке встречаются чаще, а затем сравнить это с таблицей частотности нужного языка. Результат будет примерным, но полученный открытый текст станет хоть и сложно, но читаемым. Далее можно исправить ошибки и получить правильную замену для каждой буквы.

Шифр Цезаря (шифр сдвига, код Цезаря или сдвиг Цезаря)

Здесь относительная частота — количество раз, которое буква встретилась в тексте, деленное на размер текста.

А в чем же проблема с Энигмой и зачем понадобился этот шкаф весом две тонны? Проблема с возможностью подбора ключа (искомой перестановки букв) решается полиалфавитными шифрами: мы для n-ой буквы открытого текста используем n-ый шифр. В общем случае такой шифр взломать невозможно. Например, подобная схема когда-то использовалась для связи между президентами государств.

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

Идеально — невзламываемый шифр! Но есть одна проблема: это дикую последовательностью единиц и нулей на каждый день надо как-то передать за океан, например, в большом чемодане. Но нельзя же разослать такие чемоданы по всем станциям на весь период времени. Поэтому на практике в полиалфавитных шифрах используется ограниченное количество моноалфавитных. Первая буква заменяется по первой схеме, вторая по второй, третья по третьей, четвертая по четвертой, а вот пятая снова по первой и так по кругу. Шифр занимает совсем мало, но он по-прежнему почти неперебираем: подсчет количества комбинаций я оставлю пытливому читателю…

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

Хотите сделать свою шифровальную машину с помощью компьютера и языка программирования С++? Не проблема!

Будем использовать простой полиалфавитный шифр, определяемый ключом, который введет пользователь: http://pastebin.com/RxgAhFk7

А на на курсе С++ мы занимаемся шифровкой не только текстов, но и картинок и даже аудиофайлов: их точно также можно шифровать по тому же алгоритму. Хотите подробнее разобраться в программировании и работе с шифрами? Приходите на наши занятия по программированию!