Теория связи в секретных системах

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

Исторический контекст

До публикации «Теории связи в секретных системах» криптография развивалась преимущественно как эмпирическая дисциплина, основанная на интуиции и практическом опыте. Во время Второй мировой войны Клод Шеннон работал в Bell Labs над системами связи и шифрования, включая проект SIGSALY — систему засекреченной голосовой связи, использовавшуюся для переговоров между союзниками. В 1945 году он подготовил секретный отчёт «A Mathematical Theory of Cryptography» (Математическая теория криптографии), который после рассекречивания был переработан и опубликован в 1949 году в журнале Bell System Technical Journal.

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

Основные понятия и определения

Шеннон ввёл ряд фундаментальных понятий, которые стали общепринятыми в криптографии:

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

Классификация шифров

Шеннон предложил классификацию криптографических систем по нескольким признакам:

По типу преобразования

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

По способу использования ключа

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

По степени секретности

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

Математическая модель криптосистемы

Шеннон формализовал криптографическую систему как кортеж из пяти множеств и отображений:

1. M — множество возможных открытых текстов.
2. C — множество возможных шифротекстов.
3. K — множество возможных ключей.
4. E: M × K → C — функция шифрования.
5. D: C × K → M — функция дешифрования, обратная E для каждого ключа.

Для каждой пары (m, k) существует единственный шифротекст c = E(m, k), и для каждого (c, k) — единственный открытый текст m = D(c, k). Предполагается, что распределения вероятностей на M и K известны перехватчику, но не конкретные значения.

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

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

Теорема о совершенной секретности

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

P(m|c) = P(m)

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

Теорема о расстоянии единственности

Для шифра замены с ключом длины n и открытым текстом на естественном языке (например, английском) расстояние единственности вычисляется по формуле:

N₀ = H(K) / D

где H(K) — энтропия ключа, D — избыточность языка (разница между максимальной и реальной энтропией на символ). Для английского языка избыточность составляет около 1,2 бит на символ, поэтому для шифра простой замены с 26 буквами расстояние единственности составляет примерно 25–30 символов.

Применение и влияние

Работа Шеннона оказала огромное влияние на развитие криптографии и смежных областей:

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

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

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

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

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

• Работа Шеннона долгое время оставалась засекреченной, так как была написана в рамках военных исследований. Публикация в открытой печати стала возможной только после окончания Второй мировой войны.
• Шеннон использовал понятие «энтропия» не только для ключей, но и для открытых текстов, оценивая избыточность естественных языков. Например, он показал, что английский язык имеет избыточность около 50%, что означает, что половину букв в осмысленном тексте можно угадать.
• Термин «расстояние единственности» (unicity distance) был введён именно Шенноном и до сих пор используется в криптоанализе.
• Статья «Теория связи в секретных системах» входит в число наиболее цитируемых работ в области криптографии, наряду с «Новыми направлениями в криптографии» Диффи и Хеллмана (1976).

Источники

• Shannon, C. E. (1949). Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4), 656–715.
• Шеннон, К. (1963). Работы по теории информации и кибернетике. М.: Издательство иностранной литературы.
• Goldreich, O. (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press.
• Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.