1C: Занятие 9. Задачи

Энигма — портативная шифровальная машина, использовавшаяся для шифрования и дешифрования секретных сообщений. Энигма использовалась в коммерческих целях, а также в военных и государственных службах во многих странах мира, но наибольшее распространение получила в нацистской Германии во время Второй мировой войны.

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

Энгима состоит из n последовательных роторов и коммутационной панели. Каждый ротор изначально установлен в одном из 26 положений. Ротор устанавливает биекцию (это значит что каждому символу ставится в соответствие другой символ (возможно, что тот же самый), причем никаким двум различным символам не ставится в соответствие один и тот же символ) между всеми символами алфавита, в результате чего для каждого символа появляется его шифр. После нажатия клавиши ротор поворачивается на один такт, а это значит, что теперь символ a шифруется шифром символа b с предыдущего такта, символ b шифром символа с и так далее. Символ z шифруется шифром символа a с предыдущего такта.

Рассмотрим Энигму для трех символов. Приведем пример работы одного ротора.

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

Соответственно, в случае нескольких последовательных роторов, на вход i -у ротору подается выход ( i - 1) -ого ротора. Шифром исходного элемента (который подавался на первый ротор) будет символ, получившийся на выходе последнего ротора. Все роторы в Энигме различны, однако их порядок можно менять (чтобы получить другой шифр).

Коммутационная панель позволяла перекоммутировать соединения между буквами клавиатуры до соединения с ротором. На панеле задавалось p различных пар букв, для каждой пары букв (А; B) при подаче на вход буквы А на выходе получалась буква B и наоборот. На следующем рисунке показана работа коммутационной панели с одним соединением на упрощенной Энигме из трех символов.

Таким образом буква a преобразуется в букву c , а буква с в букву a (то есть реализовано соединение ac ). Для буквы b соединений нет, поэтому она преобразовывается в себя. Трехбуквенная Энигма (с тремя роторами и коммутационной панелью на одно соединение) выглядит следующим образом

Рассмотрим Энигму, у которой алфавит содержит k символов, которая содержит n роторов и на коммутационной панели можно установить ровно p соединений. Сколько различных шифров может создавать эта машина?