23.2. Метод замены

Для примера используем буквы русского алфавита (без буквы «ё») плюс пробел, обозначаемый символом ‗. Для удобства приведем русский алфавит в виде таблицы, содержащей также номера букв.

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

Подстановкой называется взаимно однозначное отображение конечного множества M на себя. Это означает, что каждому элементу множества (например, символу алфавита) ставится в соответствие один и только один элемент этого же множества. Очевидно, для задания конкретной подстановки природа элементов не имеет значения, важно лишь их количество N (называемое степенью подстановки). Можно поэтому в качестве множества рассматривать множество целых чисел М = {1, 2, 3, ..., N}.

Любая подстановка может быть описана матрицей 2 ? N, в которой первая строка содержит числа 1, 2, …, N, а вторая строка состоит из тех же чисел, расположенных в порядке, определяемом подстановкой, например, если число i после подстановки получает значение ki, то можно записать

,

где .

Очевидно, если последовательно применить две подстановки S1 и S2, то их результат снова будет подстановкой, равной композиции (произведению) исходных подстановок S = S1 ? S2. Множество подстановок одинаковой степени образует группу относительно «умножения», определенного таким образом. Отсюда следует, что для каждой подстановки существует обратная операция. Нейтральным элементом группы подстановок служит тривиальная подстановка, оставляющая на месте все элементы множества.

Пусть открытый текст представляет собой фразу «открытый текст», а подстановка задана таблицей

.

Шифртекст имеет вид «тоцреоечаоыцпо». Очевидно, что ключом к этому шифру является сама подстановка S. Количество всевозможных подстановок для алфавита из N символов равно N!,что делает раскрытие ключа методом полного перебора проблематичным. На первый взгляд, криптостойкость такого шифра должна быть очень высокой. Однако недостатком шифра простой подстановки является то, что статистические свойства текста (частоты появления букв) при шифровании сохраняются, благодаря чему криптостойкость шифра на самом деле низка. Если в распоряжении дешифровальщика окажется достаточно длинный шифртекст (несколько десятков знаков), то шифр может быть взломан за несколько минут путем подсчета частот букв и сравнения с известными статистическими характеристиками русского (английского и т.д.) текста.