Абсолютно стойкий шифр

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Математически понятие абсолютно стойкого шифра было введено Клодом Шенноном в 1945 году в работе «Математическая теория криптографии».

Вспомогательные понятия[править | править код]

Пусть и — алфавиты открытого и шифрованного текста такие, что .

Шифрование задаётся инъективным отображением , дешифрование — отображением .

— наборы правил шифрования и дешифрования.

Максимальное число возможных отображений равно количеству размещений из по (числу способов выбрать подмножества размером в множестве , учитывая порядок элементов).

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

распределение вероятностей для открытого текста,

— распределение вероятностей для комбинации номеров отображений,

— распределение вероятностей для шифротекста, где

декартовы степени множеств , — количество символов в открытом тексте.

Будем считать, что случайные величины, соответствующие появлению открытого текста и ключа , независимыми. Тогда:

, где сумма ведётся по всем и таким, что .

— множества правил шифрования и дешифрования (декартовы степени множеств ).

Учитывая, что не каждая комбинация символов длины из алфавита может появиться в открытом тексте, введём: .

Шифр замены с неограниченным ключомсемейство шифров , где — представляет собой совокупность , при этом .

Длина ключа шифра замены с неограниченным ключом совпадает с размером открытого текста .

Пусть — конечное множество некоторых ключей (некоторых наборов натуральных чисел). Длина ключа из может быть меньше . Для каждого ключа из можно задать правило детерминированного построения ключевого потока . Полученный таким образом набор ключевых потоков для всех ключей из обозначим . Например, для ключа в качестве ключевого потока можно взять периодическое повторение этого ключа . Заметим, что .

Шифр замены с ограниченным ключом — семейство шифров , где есть та же совокупность, что и для определённого выше шифра с неограниченным ключом, в которой вместо и используется множество и распределение .

Формальное определение[править | править код]

Пусть — вероятность, что было зашифровано сообщение при регистрации шифротекста . Шифр называется абсолютно стойким, если выполнено:

.

Другими словами, апостериорное распределение вероятностей совпадает с априорным распределением . В терминах теории информации это означает, что условная энтропия сообщения при известном шифрованном тексте равна безусловной. Знание шифротекста не даёт криптоаналитику никакого полезного знания для получения (расшифровка возможна только полным перебором).

Основные свойства[править | править код]

Никакой шифр с ограниченным ключом не является совершенным.

Если шифр совершенный, то .

Теорема Шеннона[править | править код]

Формулировка[править | править код]

Шифр с неограниченным ключом , у которого является совершенным тогда и только тогда, когда:

, где , то есть для любого и любого существует только один ключ такой, что ;

, то есть ключи должны быть равновероятны.

Доказательство[править | править код]

Так как , то из следует, что при следует .

Занумеруем ключи следующим образом при фиксированном : . Получим:

.

Используем ту же нумерацию, что и в предыдущем пункте, считая фиксированным. Применяя :

. Применяя и :

. Получили определение абсолютной стойкости.

Общий вид[править | править код]

Исходя из теоремы Шеннона, правило шифрования шифра замены при , у которого , можно представить в виде латинского квадрата:

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

Замечание[править | править код]

Существуют абсолютно стойкие шифры, для которых количество символов в алфавите открытого текста меньше . Например:

Абсолютная стойкость данного шифра легко проверяется по определению по формуле: .

Этот шифр остаётся абсолютно стойким для любого распределения .

См. также[править | править код]

Литература[править | править код]