Абсолютно стойкий шифр — шифр, характеризующийся тем, что криптоаналитик принципиально не сможет извлечь статистическую информацию относительно выбираемых ключей из перехватываемого шифротекста.
Математически понятие абсолютно стойкого шифра было введено Клодом Шенноном в 1945 году в работе «Математическая теория криптографии».
Вспомогательные понятия
Пусть и — алфавиты открытого и шифрованного текста такие, что .
Шифрование задаётся инъективным отображением , дешифрование — отображением .
— наборы правил шифрования и дешифрования.
Максимальное число возможных отображений равно количеству размещений из по (числу способов выбрать подмножества размером в множестве , учитывая порядок элементов).
Возникновение очередного символа , выбор ключа (то есть выбор отображения ), получение шифротекста реализуются с некоторыми вероятностями:
— распределение вероятностей для открытого текста,
— распределение вероятностей для комбинации номеров отображений,
— распределение вероятностей для шифротекста, где
— декартовы степени множеств , — количество символов в открытом тексте.
Будем считать, что случайные величины, соответствующие появлению открытого текста и ключа , независимыми. Тогда:
, где сумма ведётся по всем и таким, что .
— множества правил шифрования и дешифрования (декартовы степени множеств ).
Учитывая, что не каждая комбинация символов длины из алфавита может появиться в открытом тексте, введём: .
Шифр замены с неограниченным ключом — семейство шифров , где — представляет собой совокупность , при этом .
Длина ключа шифра замены с неограниченным ключом совпадает с размером открытого текста .
Пусть — конечное множество некоторых ключей (некоторых наборов натуральных чисел). Длина ключа из может быть меньше . Для каждого ключа из можно задать правило детерминированного построения ключевого потока . Полученный таким образом набор ключевых потоков для всех ключей из обозначим . Например, для ключа в качестве ключевого потока можно взять периодическое повторение этого ключа . Заметим, что .
Шифр замены с ограниченным ключом — семейство шифров , где есть та же совокупность, что и для определённого выше шифра с неограниченным ключом, в которой вместо и используется множество и распределение .
Формальное определение
Пусть — вероятность, что было зашифровано сообщение при регистрации шифротекста . Шифр называется абсолютно стойким, если выполнено:
.
Другими словами, апостериорное распределение вероятностей совпадает с априорным распределением . В терминах теории информации это означает, что условная энтропия сообщения при известном шифрованном тексте равна безусловной. Знание шифротекста не даёт криптоаналитику никакого полезного знания для получения (расшифровка возможна только полным перебором).
Основные свойства
Никакой шифр с ограниченным ключом не является совершенным.
Условная вероятность для шифра с ограниченным ключом:
, где .
Покажем, что для совершенного шифра верно: . Действительно, если бы при некоторых и , то . Так как , то ( по определению абсолютной стойкости), что противоречит определению шифра с ограниченным ключом.
Теперь можно утверждать, что для совершенного шифра , так как для любого фиксированного существует ключ такой, что . Но это неравенство невозможно , так как множество конечно, а неограниченно возрастает при росте , ведь .
Если шифр совершенный, то .
Если провести рассуждения, аналогичные доказательству предыдущего свойства, но вместо множества использовать , то также получим: . Но в этом случае у нас нет ограничения на мощность множества . По первому свойству неравенство будет выполняться и при .
Теорема Шеннона
Формулировка
Шифр с неограниченным ключом , у которого является совершенным тогда и только тогда, когда:
, где , то есть для любого и любого существует только один ключ такой, что ;
, то есть ключи должны быть равновероятны.
Доказательство
Так как , то из следует, что при следует .
Занумеруем ключи следующим образом при фиксированном : . Получим:
.
Используем ту же нумерацию, что и в предыдущем пункте, считая фиксированным. Применяя :
. Применяя и :
. Получили определение абсолютной стойкости.
Общий вид
Исходя из теоремы Шеннона, правило шифрования шифра замены при , у которого , можно представить в виде латинского квадрата:
| | | |
---|
| | | |
---|
| | | |
---|
| | | |
---|
При равновероятном использовании система будет обладать абсолютной стойкостью. Практической реализацией такой системы, например, является шифр Вернама.
Замечание
Существуют абсолютно стойкие шифры, для которых количество символов в алфавите открытого текста меньше . Например:
| | |
---|
| | |
---|
| | |
---|
| | |
---|
| | |
---|
| | |
---|
| | |
---|
Абсолютная стойкость данного шифра легко проверяется по определению по формуле: .
Этот шифр остаётся абсолютно стойким для любого распределения .
См. также
Литература