Математика и криптография

Кстати, задачка для вдумчивого читателя и неназойливых размышлений на досуге. Конечно же, для английского языка тоже есть таблица частоты проявления символов. Можно составить новую таблицу двухбуквенной кодировки при помощи двенадцати символов, в которой будут учтены частоты встречаемости букв как в русском, так и в английском языке. Например, буква «E» встречается в английском языке чаще всего, за ней на втором месте стоит буква «T», так что резонно код «ET» отдать пробелу. А вот буква «X» встречается очень редко, равно как и буква «Y», так что код «YX» отдаётся букве «Ъ». И так далее.

Неделя 6. Шифрование дырявой матрицей

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

Для такого шифрования необходимо подготовить набор ключей. Каждый ключ представляет собой квадратную матрицу, в которой прорезаны отверстия. Другими словами, ключ — это квадратный лист картона, разделённый на знакоместа. В нем продырявлена ровно четверть знакомест. При этом отверстия сделаны таким образом, что при повороте квадрата на 90, 180 и 270 градусов их наложения друг на друга не происходит. Например, вот изображение ключа для перемешивания сообщения из 100 символов:

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

В прорезях пишется текст, который надо перемешать. Как только первые 25 символов текста записаны, ключ поворачивается на 90 градусов так, чтобы в верхнем левом углу теперь стояла цифра 2, и в прорези записываются следующие 25 символов перемешиваемого текста — и так далее до окончательного заполнения матрицы. Если в перемешиваемом тексте менее 100 символов, то остаток заполняется какой-нибудь буквой (например, наиболее часто используемой; но лучше подобрать сообщение так, чтобы в конце оставалось как можно меньше неиспользованных знакомест: заполнение их символами-пустышками повышает риск раскрытия — поразмыслите, почему так).

Самое важное в квадратном ключе заключается в том, чтобы при его повороте на 90, 180 и 270 градусов отверстия ни разу не совпадали. Вам необходимо будет потренироваться в создании таких ключей (кто-нибудь из читателей, умудрённых в математике, может составить систему уравнений и решить её; иной читатель, умудрённый в программировании, разработает программу для генерации подобных матриц). При этом желательно, чтобы отверстия были равномерно распределены по площади ключа, поскольку слишком отчётливые группировки опять снижают криптостойкость. Лучше всего сделать ключ, похожий на изображенный выше — отверстия не должны соприкасаться сторонами друг с другом. Понятно, что длина стороны такого ключа должна быть чётным числом.

Вот, что необходимо сделать на этой неделе:

1. Разработать свой вариант ключа размером не менее 10 × 10 для перемешивания сообщения из 100 символов.

2. Нарисовать разработанный ключ в каком-либо графическом редакторе (что-то типа MS Visio).

3. Распечатать ключ в двух экземплярах, заламинировать их оба при помощи скотча, а затем в скотче прорезать отверстия. Всё это надо сделать очень аккуратно.

4. Подготовить шифрограмму длиной не более 100 символов (лучше ровно 100, но точно не менее 90).

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

6. Отправить письмо, вложив в него один экземпляр ключа.

Ребёнок должен будет самостоятельно догадаться, как использовать ключ. Это упражнение призвано пробудить в нём желание сделать собственный ключ (или даже несколько ключей).

Неделя 7. Древние и кзотические алфавиты

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