Информация

Передача сообщений

Если ифнормация, переданная в сообщении, известна заранне, или a priori, то количество ифнормации, переданной в сообщении, равно нулю. Потому что ничего нового из сообщения мы не узнали.

Но если ифнормация, которая подтверждается сообщением, еще не известна точно, но только с некоторой вероятностью $p$? Тогда сообщение, очевидно, содержит новую информацию.

Пример: вы капитан корабля и вы знаете, что половина всех кораблей в Карибском море - пиратские. Корабль, который вы видите, еще не поднял флага, и вы не знаете, что это за корабль.

Как только флаг поднят, вы получаете повую порцию информации - так как другой корабль передал вам сообщение, обозначил себя как пиратский или "мирный".

Хороший вопрос - как измерять количество переданной в сообщении информации?

Некоторое "наивное" представление говорит, что количество переданной в сообщении информации может быть сзязано с битами. Логично предположить, что флаг корабля можно представить как один бит информации:

$$\{0 - корабль\ обычный, 1 - корабль\ пирасткий\}$$

Подняли флаг - передали один бит. Но, вообще говоря, это верно не всегда, а только когда корабли рапределены поровну между пиратами и "не пиратами".

На самом деле немного сложнее

Более реалистичная ситуация - допустим, всего $\dfrac{1}{8}$ кораблей является пиратскими.

Итак, капитан корабля предполагает, что с вероятностью 1/8 другой корабль является пиратским. Равноценно ли "сообщение", которое передает флаг,

• Когда корабль пиратский?
• Когда корабль не пирасткий?

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

И сколько информации при этом будет передано?

Немного другой пример

Если товарищ подсказывает, какой из двух ответов на вопрос теста правильный, он передает вам 1 бит информации.

А если подсказать два ответа на два вопроса, с двумя вариантами ответов каждый?

По идее, должно быть два бита.

• Три вопроса? Четыре?
• Если дали подсказку, какой вариант из семи правильный? Из восьми?

Вывод формулы собственной информации

Если вероятность события $w_i$ равна 1 (всех пиратов поймали), то передача информации (подъем флага) не несет важной ифнормации; количество переданной информации должно быть равно $I(w_i) = 0$.

Если вероятность события $w_i$ меньше нуля, то количество информации $I(w_i) > 0$

Если два независимых события происходят "одновременно", то количество информации, переданное в сообщении о том, что случились эти два события, должна быть равна сумме ифнормации сообщений об отдельных событиях.

То есть, например,

• Если 1/8 кораблей - пиратские, и 1/8 капитанов - испанцы (предположим, нет никакой связи между национальностью капитана и "пиратскостью корабля"), то количество информации от одновременно ипиратского и испанского флагов равно сумме информации отдельно от пиратского и от испанского флагов

$I(Пиратский, Испанский) = I(Пиратский) + I(Испанский) $

Та же логика с подсказкой ответов на тесты:

$I(Ответ\ 1, Ответ\ 2) = I(Ответ\ 1) + I(Ответ\ 2) $

Важно! В случае, если один из правильных ответов вам известен (например, ответ на второй вопрос) - количество информации, переданной во втором сообщении будет равно нулю. Потому что это событие уже определено для вас, вероятность его равна $1$.

Так что тогда, фактически, вам передали $1$ бит новой информации.

Определим функцию, которая удовлетворяет критириям, перечисленным выше, и "превращает" вероятнсоть события в собственную информацию.

$$ \begin{align} I(w_1\cap w_2) &= I(w_1) + I(w_2) \notag \\ f(P(w_1\cap w_2)) &= f(P(w_1)) + f(P(w_2)) \notag \\ &= f(P(w_1)\cdot P(w_2)) \notag \\ \end{align} $$

Последнее равенство верно, потому что вероятность одновременного появления двух независимых событий равна произведению вероятнсотей этих событий.

Окей, что за функция $f(x\cdot y) = f(x) + f(y)$?

Логарифм! Точнее, здесь используется $K\log {x}$

Так как $0 \leq P(w_i) \leq 1$, их логарифм будет отрицательным. Отсюда вытекает значение константы $K < 0$. Для "бинарного" случая и двоичного логарифма используется $-1$.

В итоге,

$I(P(w_i)) = -\log_2 {P(w_i)} = \log_2 {\dfrac{1}{P(w_i)}} $

Как вариант, информацию иногда записывают через случайную переменную $X$ для состояния переменной $x$:

$I_X(x) = -\log_2 {p_X(x)} = \log_2 {\dfrac{1}{p_X(x)}} $

Для энтропии, определенной через двоичный логарифм, единица измерений - бит (что особенно хорошо совместимо с ситуацией, когда появления "значений" равновероятны и неопределны - 1 бит - 1 бит :) ).

Энтропия

Энтропия в теории информации - это математическое ожидание собственной ифнормации.

$$H(X) = E[I(X)] = E[-log {P(X)}]$$

Если предположить, что $X$ может принимать $n$ значений с вероятностями $\{P(x_1), P(x_2), ..., P(x_n)\}$ - как записать математическое ожидание?

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

$H(X) = - \sum\limits_{i=1}^{n}P(x_i) \cdot \log {P(x_i)}$

Шеннон основывал свои рассуждения на следующих свойствах энтропии:

• $I(p)$ монотонна
• $I(p) \geq 0$ - информация неотрицательна
• $I(1) = 0$ - гарантированно случающиеся события не создают (новой) информации
• $I(p_1, p_2) = I(p_1) + I(p_2)$ - информация независимых событий аддитивна

для который отлично подходит (если решить определенную систему дифференциальных уравнений) функция $I(x) = k \log{x}$.

За N сообщений конкретная реализация $w_i$ случится $NP(w_i) = n_i$ раз, тогда для всех событий будет

$$\sum\limits_{i}n_i I(w_i) = -\sum\limits_{i}NP(w_i)\log {P(w_i)}$$

поделим на $N$, получим среднее количество информации (мат. ожидание) на одно событие

$$ - \sum\limits_{i}P(w_i)\log {P(w_i)}$$$$ \sum\limits_{i}P(w_i) I(w_i)$$

Совместная энтропия (Joint entopy)

Совместная энтропия базируется на совместной вероятности (совместное распределение). Та же идея, что и для энтропии Шеннона, но уже для набора переменных.

Например, в нашем "пиратском" случае можно говорить о совместном распределении типа корабля и национальной принадлежности корабля. При этом "пиратскость" и национальность, скорее всего, не независимые переменные.

Для броска двух игральных костей также можно построить совместное распределение.

Совместная энтропия:

$$H(X_1, ..., X_n) = - \sum\limits_{x_1 \in X_1, ..., x_n \in X_n} p(x_1, ..., x_n) \log {p(x_1, ...,x_n)}$$

Условная энтропия

Условная энтропия - это энтропия события $Y$ при условии события $X$. Фактически, это матожидание количества информации, которое передается в $Y$, когда значение $X$ известно.

$$H(Y|X) = -\sum\limits_{x \in X, y \in Y} p(x,y) \log{\dfrac{p(x,y)}{p(x)}}$$

$0 \log {c/0}$ по соглашению равен $0$ (также это значение $\lim\limits_{x \to +0}x \log {c/x}$)

Здесь $p(x, y)$ - вероятность совместного появления $x$ и $y$.

Условная энтропия нужна, когда события $x,y$ зависимы. Например, пиратов может быть больше среди испанцев, тогда информация о том, что капитан - испанец, несколько "снижает" ценность последующей информации о том, что корабль - пиратский.

Окей. Допустим, в акватории есть только испанские и голландские корабли, голандских кораблей - $1/4$, распределение пиратских и торговых кораблей такое:

    P.  M.
D. 1/8 7/8
S. 1/4 3/4

Условная энтропия (conditional entropy)

Какова энтропия $H(Y|X) = \sum\limits_{x \in X}H(Y|X = x)$?

То есть сколько в среднем мы получим информации, зная, пиратский корабль, или нет?

$$ \begin{align} H(Y,X) &= - \bigg(\dfrac{p(D,P)log(D,P) + p(D,M)log(D,M)}{p(D)} + \dfrac{p(S,P)log(S,P) + p(S,M)log(S,M)}{p(S)}\bigg) \notag \\ &= - \bigg(\dfrac{1/8 \cdot log(1/8) + 7/8 \cdot log(7/8)}{1/4} + \dfrac{1/4 \cdot log(1/4) + 3/4 \cdot log(3/4)}{3/4} \bigg) \notag \\ &=3.256 \end{align} $$

Вопросы:

• Когда $H(Y|X) = 0$?

• Когда $H(Y|X) = H(Y)$?
  (опишите зависимость $X$ и $Y$)

• $H(Y|X) = 0$, когда $Y$ полностью определено $X$

• $H(Y|X) = H(Y)$, когда случайные переменные $X,Y$ независимы.

Chain rule

$H(Y|X) = H(X,Y) - H(X)$

$H(X_1, X_2, ..., X_n) = \sum\limits_{i=1}^{n}H(X_i|X_1, X_2, ...,X_{i-1})$

Формула, аналогичная chain rule для вероятности:

$\mathrm P(X_n \cap \ldots \cap X_1) = \prod_{i=1}^n \mathrm P\left(X_i \,\Bigg|\, \bigcap_{j=1}^{i-1} X_j\right)$

Вообще, формулы для вероятности, имеющие "осмысленные" аналоги для энтропии, получаются заменой деления/умножения вычитанием/сложением.

Применение к кодам Хаффмана

Старая, добрая $GATTACA$. Давайте оценим оптимальность кодировки.

$M = \{A, C, G, T\}$

$P(A) = 3/7, P(T) = 2/7, P(C) = P(G) = 1/7$

$$ \begin{align} &A \to 0 \notag \\ &T \to 10 \notag \\ &C \to 111 \notag \\ &G \to 110 \notag \\ \end{align} $$

Сколько бит информации в среднем требуется, чтобы передать один символ?

$\sum\limits_i p(M_i) \cdot (bits\ of\ M_i) = 2.1429$

А какой теоретический предел сжатия информации для данного набора символов и текста?

$H(M) = \sum\limits_i p(M_i) \log {p(M_i)} = 1.8424$

Избыточность информации

Уже более практическая вещь: она встретится в контексте кодировок, а так же связана с максимально возможным сжатием.

Определяется через "плотность информации" от случайного процесса (rate):

$$r = \lim\limits_{n \to \inf} \dfrac{1}{n}H(M_1, M_2, ...,M_n)$$

$M = \{M_1, M_2, ...,M_n\}$ - символы алфавита

$R = \log |M|$ - максимальное количество информации, которе может быть передано при помощи алфавита $M$, если кодировка не избыточна. "Идеальные улсовия" - если текущее состояние не зависит от предыдущих, появления символов равновероятны.

Абсолютная избыточность - $D = R - r$; Относителльная избыточность -

$$\dfrac{R-r}{R} = \dfrac{\log{|M|} - \lim\limits_{n \to \inf} \dfrac{1}{n}H(M_1, M_2, ...,M_n)}{\log {|M|}}$$

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

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

Строка 'ACACACAC...' - всегда только из 'AC'

$M = \{a, b\}$

$R = \log {2} = 1$

$r = 1/2$

$( R - r )/ R = 1/2$; строку можно сжать в два раза

TBD:

• добавлю расчет $r$ для этой строки
• добавлю пример с настоящим генетичеким кодом и триплетами

Совместная информация

Полезна как теоретический критерий для оценки качества шифра: должна быть равна $0$ в случае, когда шифр оптимален.

$I(X,Y) = H(X) - H(X|Y)$

Вопрос: вспоминая предыдущие определения - почему $I(X,Y)$ должна быть равна нулю?

</font>

Типы шифрования

Симметричное шифрование

• Для шифрования и расшифровки используется один и тот же ключ
• Базово, операции шифрования и расшифровки комбинируются из P-box'ов (перестановки) и S-box'ов (подстановки)
• Возникает проблема передачи ключа
• Примеры: DES, AES

Асимметричное шифрование

• Есть пара ключей - открытый и закрытый
• Открытый ключ используется для шифрования, а закрытый - для дешифрования сообщения
• Открытый ключ можно передавать по общедоступным каналам
• Часто алгоритмы асимметричного шифрования используются для того, чтобы перед передачей зашифровать ключ алгоритма симметричного шифрования (которые, как правило, быстрее)
• Примеры: RSA, Elgamal (Эль-Гамаль), Rabin
• Ключ больше, чем в симметричном шифровании
• Медленнее, сложнее вычислительно

</font>

Симметричное шифрование

Запутанность (конфузия) и диффузия

Запутанность

Количество бит ключа, от который зависит каждый бит зашифрованного сообщения. Запутанность делает зависимость входных данных и шифротекста нелинейной, реализуется, в основном, через S-блоки

Диффузия

"Рассредоточненность" части оригинального сообщения на зашиврованное, т.е. от одного бита сообщения должно зависеть состояние многих битов зашифрованной версии.

Диффузия "распределяет" избыточную информацию из исходного текста по всему шифротексту.

• Сложнее делать выводы о составе ключа по шифротексту
• Сложнее определить текст, зная часть ключа
• Работа основана на перестановках (P-боксы)

В идеале, изменение любого бита $i$ текста должно с вероятсностью $\dfrac{1}{2}$ менять состояние произвольного бита ключа $j$.

Лавинный эффект (avalanche effect)

Изменение малого количества битов в ключе или входных данных приводит к "лавине" изменений в шифротексте.

Нестрогий критерий

Изменение одного бита на входе функции $f: \{0, 1\}^n \to \{0, 1\}^n$ приводит к изменению примерно полвины битов на выходе для

Строгий лавинный критерий

Для булевой функции $f(x \in \{0,1\}^n)$ изменение одного входного бита меняет состояние с вероятностью ровно $1/2$.

Напишите функцию, удовлетворяющую строгому лавинному критерию для $\{0, 1\}^2$ (двухбитовых строк)

$$ \begin{align} &00 \to ? \notag \\ &01 \to ? \notag \\ &10 \to ? \notag \\ &11 \to ? \notag \\ \end{align} $$

$$ \begin{align} &f: 00 \to 0 \notag \\ &f: 01 \to 0 \notag \\ &f: 10 \to 1 \notag \\ &F: 11 \to 1 \notag \\ \end{align} $$

S-box

Подстановка одних значений на место других.

P-box

Перемешивание значений.

Основной вопрос - как включить в S- и P-боксы ключ, чтобы сделать процесс шифрования обратимым?

</font>

DES

В DES (Data Encryption Standart) P-box и S-box объединены в одну функцию для шифрования - функцию Фейстеля.

Применение F-функции для шифрования и расшифровки

Есть набор ключей: $K_0, K_1, ...,K_n$

Текст для шифрования разделяется на правую ($R$) и левую ($L$) части

Шифрование выполняется итеративным выполнением операций:

$L_{i+1} = R_i$
$R_{i+1} = L_i \oplus F(R_i, K_i)$

$(R_{n+1}, L_{n+1})$ представляет собой зашифрованный текст (обратите внимание не перестановку $R$ и $L$.

Для расшифровки ключи применяются в обратном порядке:

$R_i = L_{i+1}$
$L_i = R_{i+1} \oplus F(L_{i+1}, K_{i})$

$(L_0, R_0)$ - результат декодирования - расшифрованный текст, тождественный оригинальному

Корректность применения F-функции

Набор операций шифрования, фактически, делает следующее:

$(L, R) \to (L \oplus F(R, K), R)$

Свойство операции $XOR$?

$$X \oplus Y \oplus Y = X$$

Тогда

$(L \oplus F(R, K) \oplus F(R, K), R) = (L, R) $

- применение шага дешифровки!

• Мы можем соединить подряд столько операций, сколько нам нужно
• Функция $F$ не обязательно должна быть обратимо

Например, в AES для расшифровки должны использоваться обратные к S- и P-боксу функции.

Пример работы

Попробуем сделать 1 шаг схемы шифрования Фейстеля, а затем выполнить дешифровку.

Сообщение: $1110$
Ключ: $01$
$L = 11, R = 10$

Давайте еще определим $F$ как $F(x, k)$ = $P(S(x \oplus k))$,

$S$ как отображение $00 \to 10$
$01 \to 11$
$10 \to 00$
$11 \to 10$

и $P$ как перестановку

$$ P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$

Зашифровка

$$ \begin{align} (11 \oplus F(10, 01), 10) &= (11 \oplus P(S(11)), 10) \notag \\ &= (11 \oplus P(10), 10) \notag \\ &= (11 \oplus 01, 10) \notag \\ &= (10, 10) \notag \\ \end{align} $$

Расшифровка

$$ \begin{align} (10 \oplus F(10, 01), 10) &= (10 \oplus 01, 10) \notag \\ &= (11, 10) \notag \\ \end{align} $$

F-функция DES

На изображении - конкретная реализация f-функции, используемая в DES.

Есть несколько особенностей, связанных с практическими аспектами - скоростью работы и тем, что на практике часть информации теряется, и, например, часть битов используется как биты четности для проверки корректности.

• На входе и выходе DES добавлена перестановка. Перестановка на выходе является обратной к перестановке на входе
• Длина слова - 64 бита, делится на блоки по 32
• Размер ключа - 64 бита, но! 8 бит используются для проверки четности, а на каждом шаге ключа осуществляется сдвиг, а из ключа выбирается 48 бит для кодирования
• Перед подстановкой на блок из 32 двух бит применяется операция $E$ (Extension), переводящая блок в 48 бит
• Затем $E(L) \oplus K$ - XOR расширенной последовательности и ключа
• Операция подстановки $S$, S-box, отображает 6-битные блоки в 4-х битные, т.е. получается преобразование из 48-битной в 32-битную размерность
• Проводится перестановка по стандартной таблице, можно переходить к следующему шагу
• Всего 16 шагов

По ссылке таблицы для DES

Лавинный эффект в DES

В DES лавинный эффект - строгий, к 4-5 раунду при изменении одного входного бита или одного бита ключа проявляется лавинный эффект.

Здесь можно посмотреть на таблицы влияния изменений

</font>