Теоремы Шеннона
Прямая и обратная теоремы Шеннона для источника общего вида — о связи энтропии источника и средней длины сообщений.
Прямая и обратная теоремы Шеннона для источника без памяти — о связи энтропии источника и достижимой степени сжатия с помощью кодирования с потерями и последующего неоднозначного декодирования.
Прямая и обратная теоремы Шеннона для канала с шумами — о связи пропускной способности канала и существования кода, который возможно использовать для передачи с ошибкой, стремящейся к нулю (при увеличении длины блока).
В теории информации, по традиции, утверждения типа «для любого кода имеет место некоторое свойство» называются обратными теоремами, а утверждения типа «Существует код с заданным свойством» — прямыми теоремами.
Теорема Найквиста — Шеннона (в русскоязычной литературе — теорема Котельникова) — об однозначном восстановлении сигнала по его дискретным отсчётам.
Теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Теорема Шеннона — Хартли
Шифр Вернама
Криптосистема была предложена для шифрования телеграфных сообщений, которые представляли собой бинарные тексты, в которых открытый текст представляется в коде Бодо (в виде пятизначных «импульсных комбинаций»). В этом коде, например, буква «А» имела вид (1 1 0 0 0). На бумажной ленте цифре «1» соответствовало отверстие, а цифре «0» — его отсутствие.
Для произведения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с ключом (называемым одноразовым блокнотом или шифроблокнотом). При этом ключ должен обладать тремя критически важными свойствами:
Иметь случайное равномерно распределение: , где k — ключ, а N — количество бинарных символов в ключе;
Совпадать по размеру с заданным открытым текстом;
Применяться только один раз.
Возможно объединять не только биты сообщения с битами ключа, но и, например, буквы. Идею Вернама можно проиллюстрировать с привлечением шифра Виженера. Ключ для этого шифра, по мысли Вернама, должен был представлять собой случайную последовательность букв.
Ключ |
EVTIQWXQVVOPMCXREPYZ |
Открытый текст |
ALLSWELLTHATENDSWELL |
Шифротекст |
EGEAMAIBOCOIQPAJATJK |
Шифрограмма |
EGEAM AIBOC OIQPA JATJK |
Без знания ключа такое сообщение не поддается анализу. Даже если бы можно было перепробовать все ключи, в качестве результата мы получили бы все возможные сообщения данной длины плюс колоссальное количество бессмысленных дешифровок, выглядящих как беспорядочное нагромождение букв. Но и среди осмысленных дешифровок не было бы никакой возможности выбрать искомую. Когда случайная последовательность (ключ) сочетается с неслучайной (открытым текстом), результат этого (шифротекст) оказывается совершенно случайным и, следовательно, лишённым тех статистических особенностей, которые могли бы быть использованы для анализа шифра.