Совершенная стойкость шифра. Требования, предъявляемые к ключам

 

Теория и многовековая практика позволили сформулировать ряд требований к ключам систем шифрования повышенной стойкости. Для пояснения этой проблемы введем в рассмотрение наряду с множествами X открытых сообщений и Y шифротекстов множество Z всех возможных ключей. Будем полагать, что секретная система находится в условиях атаки только шифрованного текста, т.е. в ситуации, когда криптоаналитик располагает только рядом различных криптограмм, на основании которых он должен восстановить примененный ключ z и, тем самым, нарушить функционирование системы (вплоть до ее разрушения). С позиций теории информации данная задача имеет, в принципе, решение тогда, когда средняя взаимная информация между ансамблями открытых текстов X и криптограмм Y положительна. Следовательно, для достижения неразрушимости системы, т.е. защищенности от несанкционированного доступа, необходимо обеспечить выполнение условия

.

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

либо .

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

,

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

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

– все ключи выбираются равновероятно и независимо от открытого текста

;

– любой фиксированный открытый текст преобразуется разными ключами и в различные криптограммы и , т.е.

.

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

Пример 10.2.1. Пусть рассматривается схема шифрования, в которой , т.е. , и , а . Преобразование сообщения в шифротекст осуществляется по правилу

,

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