Домашнее задание 2. Дисковая машина для шифрования

 

Теперь я предлагаю тебе сделать механическое устройство для очень стойкого шифрования. Это будет практически одноразовый блокнот – если этим устройством пользоваться правильно и никогда не нарушать установленные принципы. Такое устройство для шифрования было создано в Германии между мировыми войнами и известно под кодовым названием «Энигма». Это была довольно компактная для тех времён электромеханическая машина, которая позволяла шифровать сообщения при помощи очень стойкого шифра. И только безалаберность немцев, допускавших ошибки и погрешности при её использовании, а также немного везения позволили полякам и затем англичанам взломать её.

Мы не будем делать полную копию немецкой «Энигмы», поскольку это не слишком‑то просто. Я опишу тебе принцип действия и дам чертежи простой бумажной версии. Ты сможешь сделать облегчённую модель, которой будет вполне достаточно для твоих нужд. Но, зная принципы, заложенные в эту машину, ты сможешь создать и более серьёзную модель. Так что давай с ней ознакомимся.

Я не буду рассказывать про то, как устроена немецкая шифровальная машина «Энигма», а лучше в списке литературы дам ссылки на книги, в которых это прекрасно описывается. Вместо этого сразу обратимся к принципам, на которых «Энигма» (и та машина, которую мы сделаем) работает. Вот они:

1. Использование машины представляет собой применение шифра простой одноалфавитной замены.

2. Машина состоит из нескольких роторов, то есть вращающихся дисков, каждый из которых представляет собой шифр одноалфавитной замены.

3. Нюанс заключается в том, что этот шифр меняется для каждой следующей буквы текста.

4. Количество таких различных шифров одноалфавитной замены можно сделать астрономически большим, так что в идеальном случае повторов не будет никогда, а потому это будет равносильно использованию одноразового блокнота.

5. У машины можно выбирать так называемое начальное состояние, которое определяет то, как роторы расположены относительно друг друга.

6. Также у машины есть отражатель, который позволяет сделать так, что шифрование и расшифровка производятся одним и тем же способом.

У настоящих роторных шифровальных машин есть ещё некоторые способы усложнения их шифров, но в нашей «маленькой» версии мы обойдёмся только несколькими роторами и отражателем.

Теперь давай немного изменим правила игры. Всё лето мы в своих шифрограммах использовали пробел. Но ты уже знаешь, что пробел – это плохой для шифрования символ, поскольку он очень часто встречается. Слишком часто. Мы удалим этот символ из наших текстов, тем более что в подавляющем большинстве случаев текст без пробелов можно легко восстановить: тыжеможешьсделатьэто?

Итак, пробела у нас больше нет, но 32 символа в нашем алфавите нужно сохранить, поскольку, как ты помнишь, это круглое число в двоичной системе счисления. Теперь мы разделим буквы «Ъ» и «Ь», так что алфавит будет выглядеть так:

А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

Ничего нового и удивительного.

Но почему нам надо оставить 32 символа? Всё просто. Буквы мы нанесем на бумажные диски (которые будут аналогами роторов), а это означает, что диски надо будет разделить на столько секторов, сколько используется букв. Разделить диск на 32 сектора очень просто: надо разделить диск пополам, потом каждую половину ещё раз пополам, потом ещё, ещё и ещё раз, то есть всего пять раз. Итого окажется 32 сектора. (Вспомни двоичную систему счисления и то, почему число 32 в ней является круглым!).

Общий вид дисковой машины для шифрования, которую я научу тебя делать, таков:

На первый взгляд – это какое‑то хаотичное переплетение непонятных линий. Но если ты немного присмотришься, то увидишь четыре бумажных диска, лежащие друг на друге, и все они находятся на подложке. Каждый диск разбит ровно на 32 сектора, и в каждом секторе написано по букве нашего нового алфавита. На изображении диски повернуты так, чтобы буквы в секторах на всех дисках находились ровно напротив друг друга. Жирные чёрные линии на рисунке показывают так называемую проводку. Это провода, идущие от буквы к букве через все диски. Наконец, лист, на котором лежат диски, представляет собой отражатель. Если ты приглядишься к нему, то поймёшь, почему он так называется. Всё просто: на отражателе все провода выходят из одной буквы, а входят в другую, то есть как бы отражаются.

Как шифровать при помощи этой машины? Алгоритм несложный. Например, тебе надо зашифровать букву «А». Ты ведёшь взглядом по линии, выходящей от буквы «А» на самом верхнем диске. На втором диске линия приходит к букве «В», далее на третьем диске к букве «Н» и на четвёртом диске к букве «М». Затем через отражатель провод возвращается к букве «Й» на четвёртом диске, затем идёт к букве «З» на третьем и «Ж» на втором диске, после чего возвращается на первый диск на букву «В». Это и будет шифром для буквы «А». Так можно зашифровать любую букву алфавита.

Как ты понимаешь, это очень простой шифр одноалфавитной замены. Он тем более простой, что является симметричным (за счёт отражателя). То есть если буква «А» шифруется при помощи буквы «В», то буква «В» шифруется при помощи буквы «А». И так с любой парой букв.

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

Всё просто. Всё настолько просто, что ты даже можешь придумать метод самостоятельно. Так что я рекомендую тебе подумать, прежде чем читать дальше. Обрати внимание на то, что диски могут вращаться относительно друг друга.

Итак, если твой метод основан на вращении дисков после шифрования каждой буквы, то твоя мысль верна. Всё действительно очень просто. Как только мы зашифровали букву, мы должны повернуть самый верхний диск на один сектор по часовой стрелке, и следующая буква будет шифроваться по совершенно иной проводке. Например, если во взаимном расположении дисков машины (для краткости будем называть это расположение «конфигурацией») на рисунке буква «А» шифровалась как «В», то при повороте верхнего диска на один сектор по часовой стрелке буква «А» станет шифроваться как «Щ». Если ещё раз так же повернуть верхний диск, то буква «А» будет шифроваться как «Ю». Таким образом, первоначальный текст «ААА» будет зашифрован как «ВЩЮ».

Но это не всё, конечно же. Ясно, что раз секторов на диске всего 32, то один диск позволяет использовать тридцать два алфавита замены. Если вращать только верхний диск, то фактически это будет использование шифра многоалфавитной замены с длиной ключа в 32 символа. Это достаточно много, но легко подлежит взлому, как ты уже знаешь из занятий второй недели. Поэтому нужны новые вращающиеся диски. Но они вращаются тогда, когда предыдущий диск делает полный оборот. То есть когда верхний диск делает полный оборот, второй диск поворачивается по часовой стрелке на один сектор.

Так тоже получается шифр многоалфавитной замены, но каждый новый диск умножает длину ключа на количество секторов на нём, то есть на 32. На представленной схеме четыре диска, а потому общая длина ключа, которым можно зашифровать послание, равняется 1048576. Представь себе: более миллиона символов, причём эти замены в основном случайны. Другими словами, для посланий, длина которых меньше миллиона букв, используется одноразовый блокнот (это не совсем так, но для простоты можно считать именно так, особенно если не нарушать правил шифрования).

Но и это ещё не всё. Если каждый раз начинать с одной и той же позиции взаимного расположения дисков, то ни к чему хорошему это не приведёт. Это всё равно как для одноразового блокнота дважды использовать один и тот же ключ. Но и тут спасает возможность вращения дисков. Мы же можем выставлять произвольную начальную конфигурацию, выбирая одну из миллиона. Мы можем каждый день выбирать новую конфигурацию, и этого хватит на всю жизнь. Начальная конфигурация определяется тем, какие буквы стоят друг напротив друга на дисках. Для этого на отражателе нужно выбрать начальный сектор, который лучше всего пометить стрелкой (на моём рисунке этого не сделано). Соответственно, начальная конфигурация зависит от того, какие буквы на дисках расположены напротив стрелки, начиная с верхнего диска. Можно, например, сказать, что начальная конфигурация на рисунке – «АААА», если стрелку на отражателе нарисовать напротив того сектора, где расположена буква «А» на самом нижнем диске.

Итак, правила шифрования:

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

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

3. Таким образом, ключ дня используется в шифровке ключей для каждого конкретного сообщения, а сообщения шифруются при помощи своих индивидуальных ключей. Ключ в этом случае – просто взаимное расположение дисков. Если ты сделаешь машину, состоящую из другого количества дисков (это возможно), то, соответственно, количество первых букв сообщения, определяющих ключ, будет равно количеству дисков.

4. Затем для шифрования используется метод многоалфавитной замены, когда диски вращаются относительно друг друга при каждом новом выборе буквы.

5. После зашифровки сообщения машина возвращается в начальную конфигурацию, выбранную на этот день.

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

7. Никогда не используй для ключей сообщений какие‑то слова или повторяющиеся буквы. Каждый раз это должны быть случайные наборы букв. Чтобы получать такие наборы, пользуйся методом с пятью монетками, который был описан в главе об одноразовом блокноте.

Вот и всё. Рекомендую тебе обдумать написанное и сделать такую машину для своих секретных нужд. Ты вполне можешь использовать другой способ соединения проводки, а не перерисовывать схему выше. В приложении к этой книге ты найдёшь шаблоны для распечатки на бумаге и создания своей машины.

Дерзай!

 

Заключение

 

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

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

Кроме всего прочего, ты всегда можешь написать мне письмо по адресу электронной почты: roman.dushkin@gmail.com, чтобы обсудить прочитанное, узнать, что делать дальше, и, если интересно, получить новые задачи и загадки.

Всего доброго!

 

Список литературы

 

Сначала несколько художественных книг, где рассказывается про то, как ловкие главные герои взломали шифры:

1. Жюль Верн. Путешествие к центру Земли. Довольно интересная книга автора многочисленных приключенческих и научно‑фантастических романов XIX века, сюжет которой рассказывает о путешествии трёх отважных героев под землёй. Примечательна первая глава, в которой главный герой разгадывает зашифрованный манускрипт, ставший причиной их дальнейших приключений.

2. Артур Конан Дойль. Пляшущие человечки. Рассказ из цикла про Шерлока Холмса, частного детектива и просто прекрасного человека. Фабула рассказа заключается в расшифровывании Шерлоком Холмсом таинственных надписей, сделанных при помощи замысловатого шифра подстановки без пробелов. В рассказе описывается метод подбора ключевых слов.

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

 

Теперь несколько научно‑популярных книг:

4. Дэвид Кан. Взломщики кодов. Популяризаторская книга о криптографии, о том, как она начиналась, как развивалась, каких успехов достигла. Много рассказывается о том, как взламывались те или иные системы шифрования, в том числе и немецкая шифровальная машина «Энигма».

5. Саймон Сингх. Книга шифров. Тайная история шифров и их расшифровки. Занятная книга о криптографии, в которой приводится уйма интересных историй и познавательных описаний систем шифрования. Чтение несложное, книга популярная и простая.

6. Роберт Чёрчхаус. Коды и шифры, Юлий Цезарь, «Энигма» и Интернет. Ещё одна книга с историческими очерками о криптографии, как всё начиналось и куда пришло на современном этапе. Написана достаточно легко и вполне интересна.

Если же ты, прочитав эти книги, поймёшь, что хочешь продолжения, то напиши мне письмо на электронную почту, и я дам дальнейшие рекомендации.