25 этюдов о шифрах

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

Подумайте сами:

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

2.4. Шифры замены и перестановки

В своей работе «Математическая теория секретной связи» Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в сложных шифрах в качестве типичных компонентов можно выделить шифры замены, шифры перестановки или их сочетания. Эти шифры можно считать как бы базовыми.

Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан-Дойля. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Понятно, что, увеличив алфавиты, т.е. объявив «части» буквами, можно любой шифр замены свести к замене букв. Теперь уже легко дать математическое описание шифра замены. Пусть X и Y — два алфавита открытого и соответственно шифрованного текстов, состоящие из одинакового числа символов. Пусть также g : X → Y — взаимно-однозначное отображение X в Y. Это значит, что каждой букве x алфавита X сопоставляется однозначно определенная буква y алфавита

Y, которую мы обозначаем символом g(x), причем разным буквам сопоставляются разные буквы. Тогда шифр замены действует так: открытый текст x₁x₂...x_n преобразуется в шифрованный текст g(x₁)g(x₂)...g(x

_n). К вопросу о вскрытии шифра замены мы вернемся в этюде 2.8.

Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным и древнейшим примером шифра перестановки является шифр «Сциталь». Обычно открытый текст разбивается на отрезки равной длины, и каждый отрезок шифруется (т.е. в нем переставляются буквы) независимо. Пусть, например, длина отрезков равна n и σ — взаимно-однозначное отображение множества {1,2, ..., n} в себя. Тогда шифр перестановки действует так: отрезок открытого текста x₁...x_n преобразуется в отрезок шифрованного текста x_σ(1)...x_σ(n).

Важной проблемой при практическом использовании шифров замены и перестановки является проблема удобного запоминания отображений g и σ. Ясно, что легко запоминать некоторые отображения: например, отображения «небольших» размеров, отображения, реализуемые каким-нибудь предметом (сциталь в шифре «Сциталь» и т.п.). Если же отображение «большого» размера, то процесс запоминания сильно усложняется. Например, широко известны биграммные шифры. В них преобразовывались биграммы (пары букв). Поскольку количество биграмм превышает 1000, то на практике биграммные шифры выглядят как специальные книжки.

Для облегчения запоминания отображений g и σ изобретались различные хитроумные способы. Правда, «расплатой» за это было упрощение используемых отображений и тем самым уменьшение стойкости шифров.

Популярным способом запоминания отображения σ, т.е. шифра перестановки, является следующий. Пусть, например, n=20. Берем прямоугольную таблицу размера 4x5, вписываем в нее открытый текст «по строкам», а шифрованный текст считываем «по столбцам». Возможны и более хитрые способы вписывания и считывания.

Подумайте сами:

1. Выпишите отображение g для шифра Цезаря.

2. Выпишите отображение σ для описанного шифра перестановки — прямоугольника 4×5.

2.5. Возможен ли абсолютно стойкий шифр

Да, и единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же длины, Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров. Мы не будем здесь останавливаться на этом подробно, но заинтересованному читателю рекомендуем изучить работу К. Шеннона, она указана в списке литературы.

Обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового открытого текста и n-битового ключа: y_i=x₁⊕k

_i, i=1, ..., n.

Здесь x₁, ..., x_n — открытый текст, k₁, ..., k_n — ключ, y₁, ..., y_n — шифрованный текст; символы складываются по таким правилам: 0⊕0=0, 0⊕1=1⊕0=1, 1⊕1=0.

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