Введение в криптографию
[an error occurred while processing this directive]

Шифры перестановки


Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется .

Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью таблицы

(6)

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

Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка

и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА. Попробуйте расшифровать сообщение НЧЕИУК, полученное в результате преобразования с помощью указанной выше подстановки.

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

Читатель, знакомый с методом математической индукции, может легко убедиться в том, что существует

(обозначается , читается `` факториал'') вариантов заполнения нижней строки таблицы (). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины , меньше либо равно (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!).

С увеличением числа значение растет очень быстро. Приведем таблицу значений для первых 10 натуральных чисел:

1 2 3 4 5 6 7 8 9 10

1 2 6 24 120 720 5040 40320 362880 3628800

При больших для приближенного вычисления можно пользоваться известной формулой Стирлинга

где .

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




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]