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

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

История возникновения концепции

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

1. Ключ должен быть случайным, равновероятно распределённым и использоваться только один раз.
2. Длина ключа должна быть не меньше длины сообщения.

Этот результат стал теоретической основой для шифров, которые сегодня называют абсолютно стойкими. Наиболее известным примером такого шифра является одноразовый блокнот (one-time pad), впервые описанный Гилбертом Вернамом в 1917 году, хотя его строгое математическое обоснование было дано именно Шенноном.

Классификация стойкости

В криптографии принято различать три основных типа стойкости:

Абсолютная стойкость (теоретико-информационная)

Основана на теории информации. Криптосистема считается абсолютно стойкой, если перехват шифротекста не уменьшает неопределённости относительно открытого текста. Математически это выражается равенством условной энтропии: \( H(M|C) = H(M) \), где \( M \) — открытый текст, \( C \) — шифротекст. Такая система не может быть взломана даже при бесконечных вычислительных ресурсах, но требует строгих ограничений на использование ключа.

Вычислительная стойкость

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

Доказуемая стойкость

Формальное доказательство того, что взлом криптосистемы эквивалентен решению некоторой сложной задачи. Однако такие доказательства обычно опираются на недоказанные гипотезы (например, P ≠ NP), поэтому на практике доказуемая стойкость — это разновидность вычислительной стойкости.

Условия достижения абсолютной стойкости

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

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

Примеры абсолютно стойких систем

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

Является классическим примером абсолютно стойкого шифра. Алгоритм: открытый текст \( M \) и ключ \( K \) представляются в виде битовых строк одинаковой длины. Шифротекст \( C \) вычисляется как \( C = M \oplus K \) (побитовое исключающее ИЛИ). Расшифрование выполняется аналогично: \( M = C \oplus K \). При соблюдении всех условий (случайный одноразовый ключ, длина ключа равна длине сообщения) шифр обеспечивает совершенную секретность. Одноразовые блокноты использовались в дипломатической и военной связи, в частности в «горячей линии» между Москвой и Вашингтоном в годы Холодной войны.

Шифры на основе квантового распределения ключей

Квантовая криптография, в частности протокол BB84, позволяет создать канал распределения ключей, защищённый законами квантовой механики. Любая попытка перехвата ключа неизбежно изменяет квантовое состояние и обнаруживается. Полученный таким образом ключ может быть использован в одноразовом блокноте, что даёт систему, абсолютно стойкую как с точки зрения теории информации, так и с точки зрения физики. Однако на практике такие системы требуют дорогостоящего оборудования и ограничены по дальности передачи.

Ограничения и критика

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

• Необходимость в защищённом канале для передачи ключа. Если ключ передаётся по незащищённому каналу, система становится уязвимой. Это создаёт замкнутый круг: для безопасной передачи ключа нужна другая защищённая система.
• Огромный объём ключевого материала. Для шифрования сообщения длиной в 1 гигабайт требуется ключ такого же размера. Генерация, хранение и передача таких объёмов случайных данных затруднительны в масштабных системах.
• Уязвимость к человеческому фактору. На практике ключи часто генерируются с помощью программных генераторов, которые могут быть неидеально случайными. Кроме того, ключи могут быть украдены, скопированы или переданы третьим лицам.
• Отсутствие аутентификации. Абсолютно стойкие шифры сами по себе не защищают от подмены сообщения. Если злоумышленник может изменить шифротекст, получатель расшифрует искажённое сообщение, не заметив подмены. Для аутентификации требуются дополнительные механизмы (например, коды аутентичности сообщений).

Значение в современной криптографии

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

Интересные факты

• В 1940-х годах советская разведка использовала одноразовые блокноты для шифрования сообщений, что делало их практически невзламываемыми для западных криптоаналитиков. Однако утечки информации происходили из-за предательства агентов, а не из-за взлома шифра.
• В 1950-х годах в Великобритании была разработана система шифрования «Стрела» (Arrow), основанная на одноразовых блокнотах, которая использовалась для связи с посольствами.
• Клод Шеннон в своей работе 1949 года также показал, что для достижения совершенной секретности ключ должен быть не только случайным, но и иметь энтропию, равную энтропии сообщения. Это означает, что никакое сжатие сообщения не позволяет уменьшить длину ключа.

Источники

• Шеннон К. «Теория связи в секретных системах» (1949).
• Менезес А., ван Орсхот П., Ванстон С. «Справочник по прикладной криптографии» (1996).
• Нильсен М., Чанг И. «Квантовые вычисления и квантовая информация» (2000).
• Брюс Шнайер. «Прикладная криптография» (1996).