1.4. Модели шифров
Одним из первых
ввел и исследовал математическую модель
шифра К. Шеннон [1,5,12]. Пусть
,
,
некоторые конечные множества,
соответственно множество открытых
текстов, множество ключей и множество
криптограмм. Задано отображение:
. (1.5)
Введенная тройка множеств , , с функцией (1.5) представляет собой алгебраическую модель шифра. При этом должны выполняться следующие условия:
- функция (1.5) сюрьективна (осуществляет отображение на );
- для любого
функция (1.5) инъективна (образы двух
различных элементов различны);
-
.
Выражение (1.5) представляет собой выражение шифрования. Выражение расшифрования имеет вид:
. (1.6)
Требование инъективности отображения (1.5) равносильно требованию возможности однозначного расшифрования криптограммы. Требование сюрьективности отображения (1.5) не играет существенной роли и оно обычно вводится для устранения некоторых технических, с точки зрения математики, неудобств, т.е. для упрощения изложения. Алгебраическая модель шифра отражает лишь функциональные свойства шифрования и расшифрования в классических (симметричных) системах шифрования. В этой модели открытый текст (криптограмма) является лишь элементом абстрактного множества ( ), не учитывающий особенностей языка и вообще говоря, не являющийся текстом в его привычном понимании.
Достаточно часто выражения для шифрования и расшифрования записываются в операторной форме:
,
,
,
,
, (1.7)
где
,
- операторы шифрования и расшифрования,
соответственно, на ключе
.
Использование операторной формы записи позволяет определить операторы комбинирования криптосистем. Наиболее часто на практике используется два типа оператора комбинирования криптосистем: взвешенное суммирование криптосистем; произведение криптосистем [1].
Взвешенной суммой криптосистем называется такая криптосистема, которая образована «взвешенным» суммирование нескольких криптосистем:
,
,
(1.8)
где
- криптографическое преобразование
-й
криптосистемы;
- вероятность выбора
-й
криптосистемы.
Операция, выраженная
приведенной выше формулой, состоит,
во-первых,
из
предварительного выбора криптосистем
с вероятностями
.
Этот выбор
по сути является частью ключа криптосистемы
.
После того
как этот выбор сделан,
криптосистемы
применяются в соответствии с их
алгоритмами.
Полный
ключ криптосистемы
должен
указывать,
какая из
криптосистем
выбрана
и с каким ключом используется выбранная
система.
На рис. 1.5 представлена обобщенная структурная схема комбинированной криптосистемы , образованной взвешенным суммированием криптосистем .
Рис. 1.5. Взвешенная сумма криптосистем
Второй способ
комбинирования криптосистем заключается
в образовании произведения криптосистем.
Произведением
криптосистем называется
такая криптосистема
,
для которой выполняется равенство:
. (1.9)
Строго говоря,
данное выражение справедливо только в
том случае, если область определения
(пространство открытых текстов)
криптосистемы
отождествляется с областью значений
(пространством криптограмм) системы
.
Тогда можно применить сначала криптосистему
,
а затем
криптосистему
к
результату шифрования (см. рис. 1.6).
Ключ криптосистемы
состоит как из ключей криптосистем
.
Произведение шифров используется
достаточно часто;
например,
после
подстановки применяют перестановку
или после перестановки
– шифр
Виженера;
или же
применяют шифр перестановки к тексту,
а затем зашифровывают результат с
помощью шифра замены, дробного шифра и
т.д.
Необходимо заметить,
что
произведение криптосистем,
вообще
говоря,
некоммутативно,
т.е.
не всегда
,
хотя в
частных случаях
(таких,
как
подстановка и перестановка)
коммутативность
имеет место.
Произведение
криптосистем представляет собой
ассоциативную операцию,
т.к. оно по
определению ассоциативно,
т.е.
.
Рис. 1.6. Произведение криптосистем
Важным свойством
криптосистем является транзитивность.
Транзитивными
криптосистемами
называют криптосистемы, для которых
выражение (1.5) разрешимо относительно
при любых парах
.
Транзитивные шифры для которых
называют минимальными.
Криптосистемы,
у которых
пространства
и
можно
отождествить
(этот случай
является очень частым)
называются
эндоморфными.
Эндоморфная
криптосистема
может
быть представлена как:
. (1.10)
Криптосистема , для которой справедливо соотношение:
. (1.11)
называется
идемпотентной.
Например,
простая
подстановка,
шифр
Виженера с периодом
являются идемпотентными.
Две
криптосистемы называются эквивалентными,
если обе они произвольный открытый
текст переводят в одну и ту же криптограмму.
Одно из важнейших предположений К.Шеннона при исследовании криптосистем состояло в том, что каждому возможному передаваемому сообщению (открытому тексту) соответствует априорная вероятность, определяемая вероятностным процессом получения сообщения. Аналогично, имеется и априорная вероятность использования различных ключей. Эти вероятностные распределения на множестве открытых текстов, и множестве ключей характеризуют априорные знания противника относительно используемого шифра. При этом К.Шеннон предполагал, что сам шифр известен противнику.
Вероятностной
моделью шифра
называется его алгебраическая модель
с заданными дискретными независимыми
вероятностными распределениями
,
на множествах
и
.
Естественно,
вероятностные распределения на
и
индуцируют вероятностное распределение
на
,
совместные распределения
,
,
и условные распределения
и
.
Используя вероятностную модель шифра К.Шеннон впервые сформулировал понятие совершенно стойкого шифра, которое легло в основу теории стойкости криптосистем [5,13].