Коротко — что такое энтропия Шеннона:

Для дискретной случайной величины X с вероятностями p$x$ энтропия определяется как
H$X$ = −∑ p$x$ log2 p$x$.
Это среднее количество бит неопределённости $или«информации»$ о значении X; в теории источников — нижняя граница средней длины любых кодов для этого источника.

Примеры и вычисления

1) Строка "ABABABAB..." — два способа её рассматривать:
a) Если вы моделируете источник как независимые броски с p$A$=p$B$=1/2 $i.i.d.равновероятныесимволы$, то
H$X$ = −$1/2$ log2$1/2$ − $1/2$ log2$1/2$ = 1 бит на символ.
Интерпретация: если вы не учитываете зависимость между символами, то каждый символ в среднем даёт 1 бит неопределённости.
b) Если же строка действительно детерминирована как строго чередующиеся символы $период2$, то будущие символы полностью предсказуемы после того, как вы знаете фазу $какойсимволбылпервым$. В этом случае энтропия-скорость источника $entropyrate$ Hrate = lim{n→∞} H$X1,...,Xn$/n = 0 бит/символ,
потому что единственная неопределённость — это выбор начального символа $1бит$, а при больших n средняя неопределённость на символ стремится к 0. То есть такой источник с памятью имеет нулевую асимптотическую неопределённость.

Замечание: H$X1$ = 1 бит $еслипервыйсимволравновероятен$, H$X2|X1$ = 0 бит $следующийоднозначноопределён$, поэтому среднее по блоку быстро падает.

2) Строка с равновероятными символами $алфавитразмераk,каждыйсимволсp=1/k$:
H = −∑_{i=1..k} $1/k$ log2$1/k$ = log2 k бит на символ.
Примеры: для двоичного алфавита k=2 → H=1 бит/символ; для 26 букв H = log2 26 ≈ 4.7 бит/символ.

Связь между энтропией и сжатием

Закон Шеннона $теоремаокодированииисточника$ говорит: при кодировании длинных блоков средняя длина кода $вбитах/символ$ не может быть меньше энтропии источника; существуют коды, приближающиеся к H при большом блоке.Интерпретация:
Источник с низкой энтропией на символ $многоизбыточности,закономерностей$ хорошо сжимается — среднее количество бит на символ можно существенно снизить.Источник с высокой энтропией $близкойкlog2|alphabet|$ почти несжимаем — оптимальный код даёт мало выигрыша по сравнению с тупой фиксацией битов.Примеры:
Для детерминантной строки "ABAB..." энтропия-скорость 0 → в теории вы можете сжать её до O$logn$ бит (записать правило "повторять 'AB' n/2 раз") vs исходный n символов.Для i.i.d. равновероятных символов размером k оптимальное сжатие даёт ≈ n log2 k бит, то есть нет существенной экономии по сравнению с минимальным битовым представлением.

Конфликт между эффективным сжатием и криптографической стойкостью

Цель сжатия — удалить избыточность, сделать данные компактными. Цель шифрования — сделать данные непредсказуемыми/неотличимыми от случайной последовательности.Последствия:
1) После хорошего шифрования $идеальныйшифр$ ciphertext должен выглядеть как равномерно распределённая случайная строка — максимально высокая энтропия на символ, поэтому ciphertext не сжимается.
2) Поэтому сжатие обычно выполняют до шифрования $compress\to encrypt$. Сжатие уменьшает избыточность, что убирает возможные утечки через повторяющиеся паттерны.
3) Однако сжатие может привести к уязвимостям: если злоумышленник может наблюдать длину зашифрованного и/или сжатого сообщения и управлять частью вводимых данных, он может по изменениям длины вывести информацию о секретных частях $атакиCRIME,BREACH$. Причина — изменение совпадения между атакуемыми строками и секретом меняет степень сжатия, а это отражается в длине выходных данных.Практические рекомендации из этой двойственности:
Сжимайте перед шифрованием, если хотите убрать избыточность, но не давайте атакам возможность запрашивать/наблюдать сжатые результаты с изменяемым вводом, который зависит от секретов.Для сетевых протоколов часто отключают компрессию для секретных полей или применяют защиту $фиксированнаядлина,padding,независимыеблоки$, чтобы длина не была информативной.Современные криптографические принципы: шифрование должно давать индуцированное распределение, которое не даёт компрессионной выгоды и устойчиво к выбранным-plaintext атакам.

Короткое резюме

Энтропия Шеннона измеряет среднюю неопределённость $бит/символ$. Для равновероятного алфавита размером k H = log2 k. Для i.i.d. бинарного равновероятного источника H = 1 бит/символ.Но для источников с памятью (например строгое "ABAB...") энтропия-скорость может быть значительно ниже $внашемслучае0$, и такие источники легко сжимаются.Компрессия удаляет статистическую структуру; шифрование, напротив, стремится её замаскировать. Комбинация сжатия и шифрования должна быть построена аккуратно, потому что сжатие может стать каналом утечки $атак$ несмотря на то, что оно обычно полезно для предварительной обработки перед шифрованием.