Совершенная секретность

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

Определение и формальная модель

С математической точки зрения, совершенная секретность определяется через теорию вероятностей. Пусть:

• \( M \) — множество возможных открытых текстов,
• \( K \) — множество возможных ключей,
• \( C \) — множество возможных шифротекстов,
• \( E_k(m) \) — функция шифрования.

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

\[ P(M = m \mid C = c) = P(M = m) \]

где \( P(M = m) \) — априорная вероятность текста \( m \), а \( P(M = m \mid C = c) \) — апостериорная вероятность после перехвата \( c \). Иными словами, шифротекст не коррелирует с открытым текстом.

Эквивалентное условие, также выведенное Шенноном: для любого \( m \in M \) и \( c \in C \) существует ровно один ключ \( k \in K \), такой что \( E_k(m) = c \), при условии равномерного распределения ключей. Это означает, что количество возможных ключей должно быть не меньше количества возможных открытых текстов.

Теорема Шеннона

Клод Шеннон доказал, что необходимым и достаточным условием для достижения совершенной секретности является выполнение трёх требований:

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

Эти условия известны как «условия одноразового блокнота» (англ. one-time pad). Любая система, не удовлетворяющая хотя бы одному из них, не может быть совершенно секретной.

Примеры

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

Наиболее известный и практически реализуемый пример совершенной секретности — шифр Вернама, предложенный Гилбертом Вернамом в 1917 году. В нём открытый текст и ключ представляют собой битовые строки одинаковой длины. Шифротекст получается путём побитового сложения по модулю 2 (XOR) открытого текста с ключом:

\[ c = m \oplus k \]

При условии, что ключ \( k \) — истинно случайная последовательность, используемая только один раз, шифр Вернама является совершенно секретным. Дешифрование выполняется той же операцией: \( m = c \oplus k \).

Шифры с совершенной секретностью на других алфавитах

В общем случае, если открытый текст, ключ и шифротекст принадлежат некоторой конечной группе (например, кольцу вычетов по модулю \( n \)), то шифрование вида \( c = (m + k) \mod n \) также даёт совершенную секретность при случайном равномерном распределении ключа. Однако на практике наибольшее распространение получил бинарный вариант (XOR).

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

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

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

Из-за этих ограничений совершенная секретность используется в основном в дипломатической и военной связи (например, «горячая линия» Москва — Вашингтон), а также в некоторых системах с низкой пропускной способностью. В подавляющем большинстве современных криптосистем (AES, RSA, TLS) применяется вычислительная стойкость, основанная на сложности математических задач, а не на информационно-теоретической безопасности.

Связь с другими понятиями

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

Критика и альтернативы

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

В российском законодательстве понятие «совершенная секретность» не имеет специального правового статуса, однако использование криптографических средств регулируется Федеральным законом «О связи» и Федеральным законом «Об информации, информационных технологиях и о защите информации». Сертифицированные средства криптографической защиты информации (СКЗИ) в России, как правило, основываются на вычислительной стойкости, а не на совершенной секретности.

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

• В 1949 году Клод Шеннон в своей работе «Теория связи в секретных системах» впервые дал математическое доказательство того, что одноразовый блокнот является совершенно секретным. Эта работа считается основополагающей для современной криптографии.
• Во время холодной войны «горячая линия» между Москвой и Вашингтоном использовала одноразовые блокноты для шифрования сообщений. Ключи доставлялись дипломатической почтой.
• В 2017 году исследователи из Массачусетского технологического института (MIT) продемонстрировали систему квантового распределения ключей, которая, по их утверждению, приближается к совершенной секретности на практических расстояниях (до 500 км оптоволокна).
• Термин «совершенная секретность» иногда путают с «абсолютной безопасностью», но последнее понятие шире и включает в себя также защиту от физических атак, атак по побочным каналам и социальной инженерии.

Источники

• Шеннон К. Теория связи в секретных системах. — 1949.
• Вернам Г. Секретная система связи. — Патент США № 1 310 719, 1919.
• Мао В. Современная криптография: теория и практика. — М.: Вильямс, 2005.
• Менезес А., ван Орсхот П., Ванстон С. Прикладная криптография. — М.: Триумф, 2002.
• Федеральный закон «Об информации, информационных технологиях и о защите информации» от 27.07.2006 № 149-ФЗ.