Криптография

№1. Ключом шифра, называемого «поворотная решетка», является трафарет, изготовленный из квадратного листа клетчатой бумаги размером n×n (n - четно). Некоторые из клеток вырезаются. Одна из сторон трафарета помечена. При наложении его на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз.

 

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

 

Найдите число различных ключей для произвольного четного числа n.

 

Решение:

 

Все клетки квадрата размера n × n разобьем на непересекающиеся группы по четыре клетки в каждой. Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата 6×6, причем клетки одной группы помечены одной и той же цифрой. Всего таких групп будет n*n/4 (целое, так как n - четное число). При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимно однозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из n*n/4 клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов 4 в степени n*n/4. В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп. Таким образом, число различных ключей шифра «поворотная решетка» при четных значениях n равно 4 в степени n*n/4.

 

 

 

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

 

В наш адрес поступило сообщение, зашифрованное с помощью шифра «Сцитала». Однако ее автор, заботясь о том, чтобы строчки были ровные, во время письма проводил горизонтальные линии, которые остались на полоске в виде черточек между буквами. Угол наклона этих черточек к краю ленты равен α, ширина полоски равна d, а ширина каждой строки равна h. Укажите, как, пользуясь имеющимися данными, прочитать текст.

 

Решение:

 

Рассмотрим один виток ленты на развертке цилиндра (разрез по горизонтальной линии). По условию высота CE, опущенная на сторону AD, равна d. Угол DAC равен (90−α)̊ . Отсюда AC равно d/ cos α. Так как высота строки равна h, то всего на одном витке n = d/(h · cos α) букв.Ответ: чтобы прочитать текст, надо разрезать ленту на участки по n = d/(h · cos α) букв и сложить их рядом.

 

 

 

 

 

 

 

 

 

 

 

№3. Ключом шифра, называемого «решеткой», является прямоугольный трафарет размера 6×10 клеток. В трафарете вырезаны 15 клеток так, что при наложении его на прямоугольный лист бумаги размером 6×10 клеток четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.

 

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

 

 

 

 

 

 

 

Решение:

 

Исходный текст состоит из 48 букв, следовательно, при зашифровании было использовано три положения решетки полностью и еще три буквы вписаны в четвертом положении. Значит, незаполненные 12 клеток совпадают с вырезами решетки в четвертом положении. Так как текст вписывается последовательно, то неизвестные нам три выреза могут располагаться только в первой строке таблицы и первых пяти клетках второй строки (до первого известного выреза).

 

Считаем, что трафарет лежит в четвертом положении. Учитывая, что в одну клетку листа нельзя вписать две буквы, получаем, что вырезы могут быть только в отмеченных знаком «?» местах трафарета («*» -места известных вырезов):

 

 

 

 

 

 

 

Очевидно, что из отмеченных в первой строке двух клеток вырезается только одна (так как они совмещаются поворотом). Получаем два возможных варианта решетки (либо первый «?», либо второй «?» в первой строке). Читаемый текст получается при втором варианте.

 

Ответ: ПОЛЬЗУЯСЬШИФРОМРЕШЕТКАНЕЛЬЗЯОСТАВЛЯТЬПУСТЫЕМЕСТА

 

 

 

№4. В таблице приведена переписка двух абонентов (Godzillы и Фунтика) в чате.

 

 

 

 

 

 

 

 

Фунтик отвечает Godzillе, для конспирации каждую букву заменяет другой буквой (при этом разные буквы заменяются разными, а одинаковые – одинаковыми). Восстановите зашифрованное сообщение и пароль.

 

Решение:

 

Отметим, что восстановить исходный текст короткого сообщения, зашифрованного с использованием такого шифра (называемого шифром простой замены) не так-то просто. Помогает здесь то, что в сообщении сохранена разбивка на слова, оставлены знаки препинания и заглавные буквы. Если обратить внимание на сочетание Яспар-Дюрюмгщмт и содержащееся в ответе Godzillы упоминание города Питера, то можно предположить, что речь идёт о Санкт-Петербурге. Составим таблицу соответствий:

 

 

 

 

 

В соответствии с этими заменами некоторые буквы в шифрованном тексте можно восстановить:

 

. .А.ТРА УЕ..А. . САНКТ-ПЕТЕРБУРГ НА ..Е НЕ.Е.. . ПАР... : БУРГУН...

 

Далее подбираем некоторые слова по смыслу. Весьма вероятно, что .А.ТРА - это ЗАВТРА, ПАР... - это ПАРОЛЬ. С учётом этих предположений сообщение примет вид:

 

. ЗАВТРА УЕЗ.А. В САНКТ-ПЕТЕРБУРГ НА .ВЕ НЕ.ЕЛ. . ПАРОЛЬ: БУРГУН... .

 

Затем по смыслу окончательно получаем искомое сообщение:

 

Я ЗАВТРА УЕЗЖАЮ В САНКТ-ПЕТЕРБУРГ НА ДВЕ НЕДЕЛИ. ПАРОЛЬ: БУРГУНДИЯ.