Шифры и шпионы

В сегодняшнем математическом уголке я рассмотрю тему, которую обсуждал на ежегодном детском научном лагере, организованном Национальным детским фондом. Фонд ищет детей и молодежь с научными интересами. Вы не должны быть чрезвычайно одаренными, но у вас должна быть «научная жилка». Очень хорошие школьные оценки не обязательны. Попробуйте, может вам понравится. Если вы ученик старших классов начальной школы или старшей школы – подайте заявку. Как правило, отчеты составляют родители или школа, но это не всегда так. Найдите сайт Фонда и все узнаете.

В школе все больше и больше говорят о «кодировании», имея в виду деятельность, ранее известную как «программирование». Это частая процедура педагогов-теоретиков. Они откапывают старые методы, дают им новое название, и «прогресс» делается сам собой. Есть несколько областей, где происходит такое циклическое явление.

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

Принадлежность к определенному сообществу также означает «общие символы», общие чтения, высказывания и притчи. Тот, кто безукоризненно выучил польский язык «в Щебжешине большая чаща, в камышах гудит жук» — тотчас же будет разоблачен как шпион чужой державы, если не ответит на вопрос, что делает дятел. Конечно он задыхается!

Это не просто шутка. В декабре 1944 года немцы с большими затратами начали последнее наступление в Арденнах. Они мобилизовали солдат, которые свободно говорили по-английски, чтобы дезорганизовать передвижение союзных войск, например, уводя их в неправильном направлении на перекрестках дорог. После минутного удивления американцы начали задавать солдатам подозрительные вопросы, ответы на которые были бы очевидны человеку из Техаса, Небраски или Джорджии и немыслимы тому, кто там не вырос. Незнание реалий привело прямо к расстрелу.

К точке. Рекомендую читателям книгу Лукаша Бадовского и Заслава Адамашека “Лаборатория в ящике стола – математика”. Это прекрасная книга, которая блестяще показывает, что математика действительно для чего-то полезна и что «математический эксперимент» — это не пустые слова. Он включает в себя, среди прочего описанная конструкция «картонной энигмы» — устройства, на создание которого нам потребуется всего пятнадцать минут и которое работает как серьезная шифровальная машина. Сама идея была настолько хорошо известна, упомянутые авторы прекрасно ее проработали, и я немного изменю ее и оберну в более математические одежды.

Шифровальные ножовки

На одной из улиц моего дачного поселка в пригороде Варшавы недавно разобрали мостовую из “трлинки” – шестиугольной тротуарной плитки. Ехать было неудобно, но душа математика радовалась. Покрыть плоскость правильными (то есть правильными) многоугольниками непросто. Это могут быть только треугольники, квадраты и правильные шестиугольники.

Может быть, я немного пошутил с этой душевной радостью, но шестиугольник — красивая фигура. Из него можно сделать довольно успешное шифровальное устройство. Геометрия поможет. Шестиугольник обладает вращательной симметрией — он перекрывает сам себя при повороте на кратность 60 градусов. Поле, помеченное, например, буквой А в левой верхней части рыс. 1 после поворота на этот угол она также попадет в поле А — и то же самое с другими буквами. Итак, давайте вырежем из сетки шесть квадратов, каждый с отдельной буквой. Полученную таким образом сетку положим на лист бумаги. В свободные шесть полей введем шесть букв текста, который хотим зашифровать. Повернем лист на 60 градусов. Появится шесть новых полей – введите следующие шесть букв нашего сообщения.

Рис. 1. Трлинки радости математика.

Справа рыс. 1 мы имеем текст, закодированный таким образом: «На станции стоит огромный тяжелый паровоз».

Теперь немного школьной математики пригодится. Сколькими способами можно расположить два числа друг относительно друга?

Что за глупый вопрос? На двоих: либо один впереди, либо другой.

Отлично. И три числа?

Также не сложно перечислить все настройки:

123, 132, 213, 231, 312, 321.

Ну это на четверых! Его еще можно четко прописать. Угадайте правило порядка, в котором я поставил:

1234, 1243, 1423, 4123, 1324, 1342,

1432, 4132, 2134, 2143, 2413, 4213,

2314, 2341, 2431, 4231, 3124, 3142,

3412, 4312, 3214, 3241, 3421, 4321

Когда цифр пять, мы получаем 120 возможных настроек. Давайте позвоним им перестановки. Количество возможных перестановок n чисел есть произведение 1 · 2 · 3 · … · n, называемое сильный и помечены восклицательным знаком: 3!=6, 4!=24, 5!=120. Для следующего числа 6 имеем 6!=720. Мы будем использовать это, чтобы усложнить наш шестиугольный шифровальный щит.

Выбираем перестановку чисел от 0 до 5, например 351042. Наш шестиугольный скремблирующий диск имеет черточку в среднем поле — чтобы его можно было поставить «в нулевое положение» — черточкой вверх, как на рис. 1. Ставим диск таким образом на лист бумаги, на котором нам предстоит писать наш отчет, но пишем его не сразу, а поворачиваем трижды на 60 градусов (т.е. на 180 градусов) и в пустые поля вписываем шесть букв. Возвращаемся в исходное положение. Поворачиваем циферблат пять раз на 60 градусов, то есть на пять «зубцов» нашего циферблата. Мы печатаем. Следующее положение шкалы — это положение, повернутое на 60 градусов вокруг нуля. Четвертая позиция — 0 градусов, это начальная позиция.

Вы понимаете, что произошло? У нас появилась дополнительная возможность – усложнить нашу «машину» более чем в семьсот раз! Итак, у нас есть две независимые позиции «автомата» — выбор сетки и выбор перестановки. Сетка может быть выбрана 66 = 46656 способами, перестановка 720. Это дает 33592320 возможностей. Более 33 миллионов шифров! Практически чуть меньше, т.к. некоторые сетки нельзя вырезать из бумаги.

В нижней части рыс. 1 мы имеем сообщение, закодированное таким образом: «Я посылаю вам четыре парашютных дивизии». Легко понять, что врагу нельзя дать знать об этом. Но поймет ли он что-нибудь из этого:

ТПОРОПВМАНВЕОРДИСЗ

ЙЙЛЬОАКВМДЕЙЧЕШ,

даже с подписью 351042?

Мы строим Enigma — немецкую шифровальную машину

Рис. 2. Пример первоначальной настройки нашей шифровальной машины.

Перестановки (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Как я уже упоминал, идеей создания такой картонной машины я обязан книге «Лаборатория в ящике стола — математика». Моя “конструкция” несколько отличается от той, которую дают ее авторы.

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

Выберем не любую перестановку, а такую, которая имеет циклы длины 2. Проще говоря, что-то вроде «Гадериполуки», описанной здесь несколько месяцев назад, но покрывающей все буквы алфавита. Условимся на 24 буквы – без ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Сколько таких перестановок? Это задача для выпускников средней школы (они должны уметь ее решать сразу). Сколько? Много? Несколько тысяч? Да:

1912098225024001185793365052108800000000 (даже не будем пытаться прочитать этот номер). Есть так много возможностей установить «нулевое» положение. И это может быть сложно.

Наша машина состоит из двух круглых дисков. На одном из них, который до сих пор стоит, написаны буквы. Это немного похоже на циферблат старого телефона, где вы набирали номер, поворачивая циферблат до упора. Rotary — второй с цветовой схемой. Проще всего надеть их на обычную пробку, используя булавку. Вместо пробки можно использовать тонкую доску или плотный картон. Лукаш Бадовски и Заслав Адамашек рекомендуют помещать оба диска в коробку для компакт-дисков.

Представим, что мы хотим закодировать слово ARMATY (Рис. 2 и 3). Установите прибор в нулевое положение (стрелка вверх). Буква А соответствует F. Поворачиваем внутреннюю схему на одну букву вправо. У нас есть буква R для кодирования, теперь она соответствует A. После следующего вращения мы видим, что буква M соответствует U. Следующее вращение (четвертая диаграмма) дает соответствие A – P. На пятом циферблате мы имеем T – А. Наконец (шестой круг) Д – Д Противник наверняка не догадается, что наши ФАПЭ будут для него опасны. А как “наши” будут читать депешу? У них должна быть одна и та же машина, одинаково «запрограммированная», то есть с одной и той же перестановкой. Шифр начинается с нулевой позиции. Таким образом, значение F равно A. Поверните циферблат по часовой стрелке. Буква А теперь ассоциируется с Р. Он поворачивает циферблат вправо и под буквой У находит М и т. д. Шифровальщик бежит к генералу: «Генерал, докладываю, пушки идут!».

Рис. 3. Принцип работы нашей бумажной Энигмы.

Рис. 3. Принцип работы нашей бумажной Энигмы.

Возможности даже такой примитивной Энигмы поражают. Мы можем выбрать другие выходные перестановки. Мы можем – и здесь возможностей еще больше – не на одну “засечку” регулярно, а в определенном, ежедневно меняющемся порядке, подобном шестиугольнику (например, сначала на три буквы, потом на семь, потом на восемь, на четыре… .. и др.).

Как можно догадаться?! И все же для польских математиков (Мариан Реевски, Хенрик зигальски, Ежи Ружицки) получилось. Информация, полученная таким образом, была бесценной. Раньше они имели не менее важный вклад в историю нашей обороны Вацлав Серпиньски i Станислав Мазуркевичкто нарушил кодекс русских войск в 1920 году. Перехваченный кабель дал Пилсудскому возможность совершить знаменитый маневр с реки Вепш.

Я помню Вацлава Серпинского (1882-1969). Он казался математиком, для которого внешний мир не существовал. О своем участии в победе в 1920 году он не мог говорить как по военным, так и… по политическим причинам (власти Польской Народной Республики не любили тех, кто защищал нас от Советского Союза).

Рис. 4. Перестановка (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Рис. 5. Красивое украшение, но не подходящее для шифрования. Слишком регулярно.

Задание 1. Na рыс. 4 у вас есть другая перестановка для создания Enigma. Скопируйте рисунок на ксерограф. Постройте машину, закодируйте свое имя и фамилию. Мой CWONUE JTRYGT. Если вам нужно сохранить свои заметки в секрете, используйте картонную Энигму.

Задание 2. Зашифруйте свое имя и фамилию одной из увиденных «машин», но (внимание!) с дополнительным усложнением: поворачиваем не на одну насечку вправо, а по схеме {1, 2, 3, 2, 1 , 2, 3 , 2, 1,….} – то есть сначала на один, потом на два, потом на три, потом на 2, потом снова на 1, потом на 2 и т.д., такой “вейвлет”. Убедитесь, что мое имя и фамилия будут зашифрованы как CZTTAK SDBITH. Теперь вы понимаете, насколько мощной была машина «Энигма»?

Решение задачи для выпускников средней школы. Сколько вариантов настройки Enigma (в этой версии, как описано в статье)? У нас 24 буквы. Выбираем первую пару букв – это можно сделать на

способы. Следующая пара может быть выбрана на

способы, далее

и т.д. После соответствующих вычислений (все числа надо перемножить) получим

151476660579404160000

Тогда разделите это число на 12! (12 факториал), потому что одни и те же пары могут быть получены в разном порядке. Так что в итоге получаем “всего”

316234143225,

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

Смотрите также: