Абсолютная криптостойкость

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

История

Концепция абсолютной криптостойкости была впервые строго сформулирована и математически обоснована американским инженером и математиком Клодом Шенноном в 1949 году в работе «Теория связи в секретных системах» (Communication Theory of Secrecy Systems). Шеннон ввёл понятие «совершенной секретности» (perfect secrecy) и доказал, что для её достижения необходимо выполнение ряда условий, в первую очередь — использование ключа, длина которого не меньше длины сообщения, причём ключ должен быть случайным, использоваться только один раз и храниться в тайне.

До работы Шеннона существовали практические шифры, которые интуитивно воспринимались как невзламываемые, однако теоретического обоснования их стойкости не было. Наиболее известным примером является шифр Вернама (одноразовый блокнот), запатентованный Гилбертом Вернамом в 1919 году. Вернам предложил метод, при котором открытый текст побитово складывается (по модулю 2) с ключом той же длины. Шеннон показал, что при соблюдении всех требований к ключу этот шифр является абсолютно стойким.

Условия абсолютной криптостойкости

Для достижения абсолютной криптостойкости (совершенной секретности) необходимо выполнение следующих условий:

1. Длина ключа не меньше длины сообщения. Ключ должен быть как минимум таким же длинным, как и само сообщение. Если ключ короче, появляется избыточность, которую теоретически может использовать противник.
2. Случайность ключа. Ключ должен быть сгенерирован истинно случайным образом, а не с помощью псевдослучайного генератора. Любая закономерность в ключе может быть использована для атаки.
3. Одноразовость ключа. Один и тот же ключ не может быть использован для шифрования двух и более сообщений. Повторное использование ключа (даже частичное) немедленно разрушает абсолютную стойкость и позволяет провести криптоанализ.
4. Секретность ключа. Ключ должен быть известен только отправителю и получателю. Любая утечка информации о ключе делает систему уязвимой.
5. Равномерное распределение ключей. Все возможные ключи данной длины должны быть равновероятны.

Математическое обоснование

Клод Шеннон определил совершенную секретность через понятие условной вероятности. Система является совершенно секретной, если для любого открытого текста \( M \) и любого шифротекста \( C \) выполняется равенство:

\[ P(M | C) = P(M) \]

Это означает, что знание шифротекста \( C \) не изменяет априорной вероятности открытого текста \( M \). Другими словами, шифротекст не даёт никакой информации об исходном сообщении.

Шеннон доказал, что необходимым условием для существования такой системы является то, что количество возможных ключей должно быть не меньше количества возможных сообщений. Для бинарных сообщений это эквивалентно условию, что длина ключа \( K \) не меньше длины сообщения \( M \): \( |K| \ge |M| \).

Примеры

Одноразовый блокнот (шифр Вернама)

Наиболее известный и практически реализуемый пример абсолютно стойкого шифра. Алгоритм:

1. Открытый текст преобразуется в бинарную последовательность (например, с помощью кода ASCII).
2. Генерируется истинно случайная бинарная последовательность (ключ) той же длины.
3. Шифротекст получается путём побитового сложения по модулю 2 (XOR) открытого текста и ключа: \( C = M \oplus K \).
4. Расшифрование производится повторным сложением шифротекста с тем же ключом: \( M = C \oplus K \).

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

Шифры с использованием «гаммы» (потоковые шифры)

В некоторых исторических системах, таких как советская «шифровальная лента» (одноразовые блокноты на бумажных носителях), использовался принцип, аналогичный шифру Вернама. Ключ представлял собой последовательность случайных чисел, напечатанную на бумаге. Такие системы использовались для связи высшего военного и государственного руководства, в частности, в «горячей линии» Москва — Вашингтон (1963 год).

Ограничения и практическое применение

Несмотря на теоретическую безупречность, абсолютная криптостойкость имеет фундаментальные практические ограничения:

• Проблема распределения ключей. Для связи с каждым корреспондентом необходимо заранее передать ключ, длина которого не меньше длины всех будущих сообщений. В современных коммуникационных сетях с миллионами пользователей это практически нереализуемо.
• Проблема хранения ключей. Ключи должны храниться в абсолютной тайне и быть защищены от кражи, утери или уничтожения. Для больших объёмов данных это требует огромных ресурсов.
• Проблема генерации ключей. Требуется источник истинной случайности, а не псевдослучайных чисел. Физические генераторы случайных чисел (основанные на радиоактивном распаде, тепловом шуме и т.д.) работают медленно и не всегда доступны.
• Проблема синхронизации. Отправитель и получатель должны иметь идентичные копии ключа и точно знать, какая его часть используется в данный момент.

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

Связь с квантовой криптографией

Квантовая криптография (в частности, квантовое распределение ключей, QKD) решает проблему безопасной передачи ключа для одноразового блокнота. Протоколы QKD, такие как BB84, позволяют двум сторонам сгенерировать общий секретный ключ, при этом любая попытка перехвата неизбежно изменяет квантовое состояние и обнаруживается. Таким образом, комбинация квантового распределения ключей и одноразового блокнота теоретически позволяет создать систему связи с абсолютной криптостойкостью, преодолев главное практическое ограничение — проблему распределения ключей. Однако на практике такие системы остаются дорогими, сложными и ограниченными по дальности связи.

Критика и альтернативные подходы

Некоторые исследователи критикуют термин «абсолютная криптостойкость» за его категоричность. Они указывают, что даже при соблюдении всех условий Шеннона, система может быть уязвима для атак, не связанных с математическим криптоанализом: социальная инженерия, физическое хищение ключей, внедрение «закладок» в генераторы случайных чисел, атаки по сторонним каналам (измерение времени выполнения, энергопотребления). Поэтому на практике безопасность любой системы, включая одноразовый блокнот, никогда не является абсолютной.

Альтернативой абсолютной стойкости является вычислительная стойкость, при которой сложность взлома шифра превосходит возможности существующих или предполагаемых вычислительных систем. Большинство современных криптосистем (RSA, AES, ECC) основаны именно на вычислительной стойкости.