Теория информации и энтропия

В 1949 году Клод Шеннон - отец теории информации - математически доказал, что существует ровно один невзламываемый шифр. Не "трудный для взлома", а доказуемо, абсолютно, математически невозможный для взлома, даже при бесконечных вычислительных ресурсах. Этот шифр - One-Time Pad. Но Шеннон также доказал, почему мы не можем использовать его для всего - и это напряжение между совершенной безопасностью и практичностью движет всей современной криптографией.

• **Оценка надёжности паролей** - менеджеры паролей (1Password, Bitwarden) оценивают стойкость паролей через энтропию: "password123" имеет ~20 бит энтропии (взламывается за секунды), а случайные 20 символов - ~130 бит (неуязвимы для перебора). NIST рекомендует минимум 80 бит энтропии для паролей
• **Проект VENONA (1943-1980)** - АНБ и ЦРУ расшифровали тысячи сообщений советской разведки, потому что одноразовые блокноты были использованы повторно. Совершенный шифр, погубленный нарушением единственного правила, привёл к раскрытию атомных шпионов Клауса Фукса и Юлиуса Розенберга
• **Сжатие перед шифрованием** - протокол TLS и архиваторы (ZIP, 7z) сжимают данные перед шифрованием не только для экономии места: сжатие уменьшает избыточность, увеличивает расстояние единственности и затрудняет криптоанализ. Шеннон показал, что несжимаемые данные содержат максимум энтропии

Предварительные знания

• Groups, Rings, and Fields

Энтропия Шеннона

В 1948 году Клод Шеннон опубликовал работу "A Mathematical Theory of Communication", в которой впервые дал **математическое определение информации**. До Шеннона информация была интуитивным понятием. После него - точной величиной, измеряемой в битах. Идея: информация - это мера **неопределённости**. Чем более неожиданно событие, тем больше информации оно несёт. Если вам сообщили, что солнце взошло утром, вы не получили почти никакой информации (вероятность близка к 1). Но если вам сообщили, что вы выиграли в лотерею (вероятность 1/10000000), информации в этом сообщении очень много.

**Энтропия H(X)** - это *средняя* информация по всем возможным исходам случайной величины X. Формула: **H(X) = -sum(p(x) * log2(p(x)))** по всем x. Энтропия максимальна, когда все исходы равновероятны (максимальная неопределённость), и равна нулю, когда один исход имеет вероятность 1 (нет неопределённости). Для криптографии это ключевое: энтропия ключа показывает, **сколько бит реальной неопределённости** он содержит.

**Почему энтропия важна для криптографии:** - **Ключи:** 128-битный ключ AES имеет энтропию 128 бит, если каждый бит случаен. Но пароль "password123" из 88 бит (11 символов по 8 бит) имеет энтропию всего ~20 бит, потому что символы предсказуемы - **Генераторы случайных чисел:** если PRNG имеет seed с энтропией 32 бита, то весь его выход содержит не более 32 бит энтропии - неважно, сколько байт он сгенерирует - **Шифротекст:** хороший шифр производит выход с максимальной энтропией (~8 бит/байт). Если энтропия шифротекста ниже - шифр пропускает структуру открытого текста

Важный результат Шеннона: **энтропия - это нижняя граница сжатия**. Нельзя сжать данные до размера меньше их энтропии без потери информации. Английский текст (~1.3 бит/символ при 8 бит/символ в ASCII) можно сжать примерно в 6 раз. Случайные данные (8 бит/байт) сжать нельзя вообще. Для криптографии следствие прямое: **идеальный шифротекст неотличим от случайных данных и несжимаем**.

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

В 1949 году Шеннон опубликовал вторую революционную работу - "Communication Theory of Secrecy Systems". В ней он впервые применил математический аппарат теории информации к криптографии и сформулировал понятие **совершенной секретности (perfect secrecy)**. Определение строгое: шифр обладает совершенной секретностью, если для любого сообщения M и любого шифротекста C выполняется **P(M | C) = P(M)**. Другими словами, знание шифротекста **никак не меняет** вероятность того, что было зашифровано какое-либо конкретное сообщение.

Важно понимать, насколько это сильное утверждение. Совершенная секретность означает не "трудно взломать" и не "нужно много времени". Она означает, что **даже при бесконечных вычислительных ресурсах** противник не может извлечь ни бита информации о сообщении из шифротекста. Квантовый компьютер, все компьютеры на Земле, миллион лет работы - ничего не поможет. Это **информационно-теоретическая** безопасность, в отличие от **вычислительной** безопасности AES или RSA, которые полагаются на сложность конкретных математических задач.

**Теорема Шеннона о необходимых условиях совершенной секретности:** Для достижения совершенной секретности **необходимо**, чтобы: 1. **Пространство ключей >= пространство сообщений** - ключей должно быть не меньше, чем возможных сообщений. На практике: длина ключа >= длина сообщения 2. **Каждый ключ используется ровно один раз** - повторное использование ключа полностью разрушает секретность 3. **Ключ выбирается равномерно случайно** - если некоторые ключи более вероятны, противник может это использовать 4. **Ключ независим от сообщения** - выбор ключа не должен зависеть от содержания сообщения Эти условия не просто достаточны - они **необходимы**. Обойти их невозможно.

Результат Шеннона накладывает фундаментальное ограничение: **совершенная секретность требует ключ, равный по длине сообщению**. Это делает её непрактичной для большинства задач. Если вы хотите зашифровать гигабайт данных с совершенной секретностью, вам нужен гигабайтный ключ, который нужно как-то безопасно доставить получателю. Но если у вас есть безопасный канал для гигабайтного ключа, зачем вам шифрование - отправьте сообщение по этому каналу напрямую!

One-Time Pad (OTP)

One-Time Pad (одноразовый блокнот) - единственный известный шифр, обладающий **доказуемой совершенной секретностью**. Идея проста до гениальности: каждый бит сообщения XOR-ится с соответствующим битом **случайного** ключа той же длины. Шифр был запатентован Гилбертом Вернамом в 1917 году (Vernam cipher), а его совершенная секретность была доказана Шенноном в 1949. Принцип работы: C = M XOR K, расшифровка: M = C XOR K. Ключевое свойство XOR: он полностью маскирует исходный бит, если ключевой бит случаен.

Последняя строка кода выше демонстрирует суть совершенной секретности: для любого шифротекста и любого гипотетического сообщения **существует ключ**, который превращает шифротекст в это сообщение. Противник, перехватив шифротекст, не может узнать, было ли зашифровано "Attack at dawn" или "Nothing here!" - оба варианта одинаково вероятны. Это и есть P(M|C) = P(M) на практике.

**VENONA: катастрофа повторного использования ключа** Во время Второй мировой войны советская разведка использовала One-Time Pad для шифрования сообщений. Но из-за нехватки ключевого материала некоторые страницы блокнотов были **использованы повторно**. В 1943-1980 годах проект VENONA (АНБ/ЦРУ) взломал эти сообщения: Если K используется дважды: - C1 = M1 XOR K - C2 = M2 XOR K - C1 XOR C2 = M1 XOR M2 (ключ исчез!) M1 XOR M2 содержит структуру обоих сообщений. Используя частотный анализ и известные фрагменты (имена, даты, формулировки), криптоаналитики восстановили сотни сообщений. Были раскрыты шпионские сети, в том числе атомные шпионы.

**Почему OTP непрактичен для повседневного использования:** 1. **Длина ключа = длина сообщения.** Чтобы зашифровать 1 ГБ данных, нужен 1 ГБ случайного ключа 2. **Доставка ключа - та же проблема.** Если есть безопасный канал для 1 ГБ ключа, можно отправить по нему и само сообщение 3. **Истинная случайность дорога.** os.urandom() использует аппаратный генератор, но его пропускная способность ограничена 4. **Одноразовость.** Каждый бит ключа используется ровно один раз, потом уничтожается. Хранить огромные объёмы ключей - сложная задача 5. **Нет аутентификации.** Базовый OTP не защищает от модификации: противник может XOR-ить известные биты и менять сообщение

Несмотря на непрактичность, OTP использовался и используется в ситуациях, где стоимость не важна, а безопасность критична. "Красный телефон" (прямая линия Вашингтон--Москва) использовал OTP. Дипломатические каналы некоторых стран до сих пор используют OTP для сообщений максимальной секретности. Ключи доставляются дипкурьерами в физических контейнерах.

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

Мы выяснили, что OTP с его ключом равным по длине сообщению - единственный совершенно секретный шифр. Но реальные шифры используют короткие ключи (128-256 бит). Возникает вопрос: **сколько шифротекста нужно перехватить, чтобы теоретически определить единственный ключ?** Этот вопрос ведёт к понятию **расстояния единственности (unicity distance)** - минимальной длины шифротекста, при которой ключ определяется однозначно.

Шеннон вывел формулу: **U = H(K) / D**, где U - расстояние единственности, H(K) - энтропия ключа, а D - **избыточность** языка в битах на символ. Избыточность D = R - r, где R - максимальная энтропия (log2 от размера алфавита), а r - реальная энтропия языка. Для английского: R = log2(26) = 4.7 бит, r = 1.0-1.5 бит/символ, D = 3.2-3.7 бит/символ. Избыточность - это та структура в языке (частоты букв, правила грамматики, ограниченный словарь), которая позволяет отличить осмысленный текст от случайного.

Расстояние единственности - **теоретический** показатель. Оно говорит: "начиная с этой длины, ключ *в принципе* может быть определён однозначно". Но это не значит, что его *практически* можно найти. Для AES-128 расстояние единственности около 19 байт, но ни один известный метод не позволяет реально определить ключ AES даже при терабайтах перехваченного текста. Разница - между информационно-теоретической и вычислительной безопасностью.

**Практический смысл расстояния единственности:** - **U маленькое (< длины типичного сообщения):** большинство перехваченных сообщений достаточно длинны для теоретического определения ключа. Безопасность шифра полностью зависит от вычислительной сложности поиска - **U большое (> длины типичного сообщения):** даже теоретически ключ не определяется однозначно. Шифр имеет некоторый запас информационно-теоретической безопасности - **U = бесконечность (OTP):** ключ никогда не определяется. Совершенная секретность - **Чем больше избыточность языка (D), тем меньше U:** структурированные данные (текст, код) "выдают" ключ быстрее, чем сжатые данные. Поэтому сжатие перед шифрованием увеличивает U

Расстояние единственности объясняет, почему **сжатие данных перед шифрованием** увеличивает безопасность: сжатые данные имеют энтропию, близкую к максимальной (r близко к R), избыточность D стремится к нулю, и U стремится к бесконечности. Это также объясняет, почему классические шифры (Caesar, Vigenere, простая замена) так легко взламываются: их малое пространство ключей и высокая избыточность естественного языка дают крошечное U - 2-25 символов.

Ключевые идеи

• **Энтропия Шеннона H(X) = -sum(p(x) * log2(p(x)))** измеряет реальную неопределённость: честная монетка = 1 бит, кость = 2.58 бит, английский текст = 1.0-1.5 бит/символ. Для криптографии ключевой вывод: энтропия ключа определяет его реальную стойкость, а не длина в битах
• **Совершенная секретность P(M|C) = P(M)** означает, что шифротекст не содержит ни бита информации о сообщении. Теорема Шеннона: для этого ключ должен быть не короче сообщения, использоваться однократно и быть равномерно случайным
• **One-Time Pad** - единственный доказуемо невзламываемый шифр: C = M XOR K с равномерно случайным ключом длиной с сообщение. Но его непрактичность (проблема доставки ключа) привела к сознательному компромиссу в пользу вычислительной безопасности
• **Расстояние единственности U = H(K) / D** показывает, сколько шифротекста нужно для теоретического определения ключа. Для OTP оно бесконечно (совершенная секретность), для AES-128 - всего 19 байт, но вычислительная безопасность компенсирует это. Именно этот компромисс между идеальной безопасностью и практичностью, который доказал Шеннон, определяет архитектуру всей современной криптографии

Связанные темы

Теория информации Шеннона - фундамент, на котором стоит вся криптография: от генерации ключей до оценки стойкости шифров:

• Вероятность и случайность — Энтропия определяется через вероятности, а совершенная секретность требует истинной случайности ключей. Генераторы случайных чисел - практическая сторона теории Шеннона: их качество напрямую определяет энтропию ключей
• Введение в криптографию — Теория информации формализует то, что было интуитивным во введении: почему одни шифры стойкие, а другие нет, и что значит 'безопасный шифр' математически. Шеннон дал первое строгое определение криптографической безопасности
• Классический криптоанализ — Расстояние единственности объясняет, почему классические шифры (Caesar, Vigenere, простая замена) так легко взламываются: их малое пространство ключей и высокая избыточность языка дают крошечное U
• AES — AES - практический ответ на теорему Шеннона: раз совершенная секретность непрактична, AES обеспечивает вычислительную безопасность с коротким 128/256-битным ключом. Расстояние единственности AES мало, но вычислительная сложность компенсирует это

Вопросы для размышления

• Шеннон доказал, что совершенная секретность требует ключ не короче сообщения. Означает ли это, что все реальные шифры (AES, RSA) - лишь "временно безопасные", которые когда-нибудь будут взломаны? Или вычислительная безопасность может быть достаточной навсегда?
• Если сжать данные перед шифрованием до максимальной энтропии (устранив избыточность), расстояние единственности стремится к бесконечности. Почему тогда это не эквивалентно совершенной секретности?
• Проект VENONA показал, что даже совершенный шифр уязвим при нарушении условий использования. Какие ещё "человеческие факторы" могут разрушить теоретически безопасную систему?

Связанные уроки

• prob-25-info-theory