Модель шифра перестановки

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

Пример 2.2. Приведем пример несимметричного шифра, который может рассматриваться как шифр простой замены.

Зафиксируем натуральное составное число т = pq, являющееся произведением двух простых чисел р, q, и выберем в качестве алфавита А кольцо Z_rn вычетов по модулю гп.

Определим в качестве открытого ключа натуральное число е такое, что НОД(е, (р — l)(g — 1)) = 1 и секретный ключ d, удовлетворяющий условию ed = 1 (mod (р - 1 )(q - 1)).

Открытый ключ индуцирует биективное отображение к множества Ъ_ш в себя следующим образом. Для любого а € Z_m определим

Данное отображение задает алгоритм зашифрования. Тогда обратное отображение к~¹ задается сравнением

Легко проверить, что выполнено сравнение

из которого следует, что отображение к^-1 определяет алгоритм расшифрования.

Описанную в данном примере шифрсхему принято называть схемой RSA, по первым буквам фамилий авторов — Rivest, Shamir, Adleman. Более подробное изложение данной схемы и ее анализ мы приводим в разделе 10.1. Как нами будет показано далее, задача определения обратного отображения к~^г является сложной и сводится к разложению числа т на простые сомножители.

Пусть Л — алфавит, которому принадлежат символы открытого текста. Зафиксируем некоторое натуральное число п и выберем в качестве множества X множество последовательностей из алфавита Л длины п, т.е.

Напомним, что перестановкой на множестве N — {1,2, ...,п} называется отображение ж, ставящее в соответствие вектору (1,...,п) вектор (яд,... , я_п), в котором 7Г1,...,7Г_П принимают все возможные значения от 1 до п. В наглядной форме перестановка 7г может быть записана в виде

Величину п принято называть степенью перестановки.

Действие перестановки я па элементе х = (ад,... ,х_п) € X может быть определено следующим образом:

т.е. перестановка ж переставляет местами элементы вектора х.

Обозначим символом S_n множество всех возможных перестановок на множестве N, а символом S_n(X) множество действий перестановок из S_n на множестве X.

Рассмотрим операцию композиции, определяемую равенством

Относительно введенной операции множество S_n(X) образует группу, которую называют группой перестановок, или симметрической группой см. [2, 4J.

При этом обратной к перестановке ж является перестановка я^-1 такая, что композиция я^-1 • ж(х) оставляет вектор х е X неизменным.

Определение 2.5. Шифр перестановки описывается алгебраической моделью

в которой множества X, Y определены равенством (2.1) и совпадают. Множество ключей К удовлетворяет условию К С S„(X), а алгоритмы зашифрования и расшифрования определены равенствами

для некоторой перестановки я € К.

Шифр перестановки является симметричным шифром, поскольку знание перестановки я позволяет эффективно вычислить обратную перестановку я~¹. Мы предлагаем читателю в качестве упражнения самостоятельно придумать алгоритм вычисления перестановки 7Г^-1.