4.3. Криптосистема Вернама

Приведём пример системы с совершенной криптостойкостью.

Пусть сообщение представлено двоичной последовательностью длины $N$:

$$ m = (m_1, m_2, \dots, m_N). $$

Распределение вероятностей сообщений $P_m(m)$ может быть любым. Ключ также представлен двоичной последовательностью $ k = (k_1, k_2, \dots, k_N)$ той же длины, но с равномерным распределением:

$$ P_k(k) = \frac{1}{2^N} $$

для всех ключей.

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

$$ C = M \oplus K = (m_1 \oplus k_1, ~ m_2 \oplus k_2, \dots, m_N \oplus k_N). $$

Легальный пользователь знает ключ и осуществляет расшифрование:

$$ M =C \oplus K = (c_1 \oplus k_1, ~ c_2 \oplus k_2, \dots, c_N \oplus k_N). $$

Найдём вероятностное распределение $N$-блоков шифртекстов, используя формулу:

$$\begin{eqnarray} P(c = a) = P(m \oplus k = a) = \sum_{m} P(m) P(m \oplus k = a | m) = \\ = \sum_{m} P(m) P(k \oplus m) = \sum_{m} P(m) \frac{1}{2^N} = \frac{1}{2^N}. \end{eqnarray}$$

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

Запишем совместное распределение открытых текстов и шифртекстов:

$$ P(m = a, c = b) ~=~ P(m = a) ~ P(c = b | m = a). $$

Найдём условное распределение:

$$\begin{eqnarray} P(c = b | m = a) = P(m \oplus k = b | m = a) = \\ = P(k = b \oplus a | m = a) = P(k = b \oplus a) = \frac{1}{2^N}, \end{eqnarray}$$

так как ключ и открытый текст являются независимыми случайными величинами. Итого:

$$ P(c=b | m=a) = \frac{1}{2^N}. $$

Подстановка правой части этой формулы в формулу для совместного распределения даёт

$$ P(m=a,c=b)=P(m=a)\frac{1}{2^N}, $$

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