Расстояние единственности

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

Определение и математическая основа

Расстояние единственности (обозначается \( n_0 \)) определяется через избыточность языка и энтропию ключа. Для шифра, в котором ключ выбирается равновероятно из множества размером \( 2^{H(K)} \), а открытый текст имеет избыточность \( R \) (бит на символ), расстояние единственности вычисляется по формуле:

\[ n_0 = \frac{H(K)}{R} \]

где:

• \( H(K) \) — энтропия ключа (в битах);
• \( R \) — избыточность языка (разность между максимальной энтропией на символ и реальной энтропией).

Избыточность естественного языка (например, русского или английского) обусловлена его статистическими закономерностями: частотностью букв, сочетаний, грамматическими правилами. Для английского языка избыточность оценивается в 1,0–1,5 бита на символ (в зависимости от модели). Для русского — около 1,5–2,0 бит на символ.

Интерпретация

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

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

Примеры для различных шифров

Шифр простой замены (моноалфавитный)

Для английского алфавита (26 букв) число возможных ключей равно \( 26! \approx 2^{88} \). При избыточности английского языка 1,5 бит/символ расстояние единственности составляет:

\[ n_0 = \frac{88}{1,5} \approx 58,7 \text{ символов} \]

Это объясняет, почему классические шифры замены (например, шифр Цезаря) легко взламываются при длине сообщения около 50–60 символов.

Шифр Виженера

Для ключа длиной \( L \) символов (из 26 букв) энтропия ключа равна \( L \cdot \log_2 26 \approx 4,7L \) бит. Расстояние единственности:

\[ n_0 = \frac{4,7L}{1,5} \approx 3,13L \]

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

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

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

Практическое значение

Расстояние единственности используется для:

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

Критика и ограничения

Понятие расстояния единственности имеет ряд ограничений:

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

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

• Термин «расстояние единственности» (англ. unicity distance) ввёл Клод Шеннон в 1949 году. В оригинальной работе он также использовал понятие «точка единственности» (unicity point).
• Для шифра Энигмы (использовавшегося нацистской Германией во Второй мировой войне) расстояние единственности оценивалось в 20–30 символов, что позволяло союзникам взламывать сообщения при достаточном объёме перехватов.
• Современные симметричные шифры (например, AES) имеют расстояние единственности, многократно превышающее длину любого разумного сообщения, что делает атаку по шифротексту через полный перебор ключей единственным теоретическим методом.

Источники

• Shannon, C. E. (1949). «Communication Theory of Secrecy Systems». Bell System Technical Journal, 28(4), 656–715.
• Стинсон, Д. (2005). «Криптография: теория и практика». М.: ДМК Пресс.
• Шнайер, Б. (2002). «Прикладная криптография». М.: Триумф.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.