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

Использование ключей с длиной, сопоставимой с размером текста, имеет смысл только в очень редких случаях, когда есть возможность предварительно обменяться ключевой информацией, объём которой много больше планируемого объёма передаваемой информации. Но в большинстве случаев использование абсолютно надёжных систем оказывается неэффективным как с экономической, так и с практической точек зрения. Если двум сторонам нужно постоянно обмениваться большим объёмом информации, и они смогли найти надёжный канал для передачи ключа, то ничто не мешает воспользоваться этим же каналом для передачи самой информации сопоставимого объёма.

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

Если длина ключа может быть много меньше длины открытого текста, то это означает, что энтропия ключа может быть много меньше энтропии открытого текста: $H(K) \ll H(M)$. Для таких ситуаций важным понятием является расстояние единственности, впервые предложенном в работах Клода Шеннона [24, 91].

definition Расстоянием единственности называется количество символов шифртекста, которое необходимо для однозначного восстановления открытого текста.

Пусть зашифрованное сообщение (шифртекст) $C$ состоит из $N$ символов $L$-буквенного алфавита:

$$C = (C_1, C_2, \dots, C_N).$$

Определим функцию $h(n)$ как условную энтропию ключа при перехвате криптоаналитиком $n$ символов шифртекста:

$$ \begin{array}{l} h ( 0 ) = H(K), \\ h ( 1 ) = H(K | C_1), \\ h ( 2 ) = H(K | C_1 C_2), \\ \dots \\ h ( n ) = H(K | C_1 C_2 \dots C_n), \\ \dots \end{array} $$

Функция $h(n)$ называется функцией неопределённости ключа. Она является невозрастающей функцией числа перехваченных символов $n$. Если для некоторого значения $n_u$ окажется, что $h ( n_u ) = 0$, то это будет означать, что ключ $K$ является детерминированной функцией первых $n_u$ символов шифртекста $C_1, C_2, \dots, C_{n_u}$, и при неограниченных вычислительных возможностях используемый ключ $K$ может быть определён. Число $n_u$ и будет являться расстоянием единственности. Полученное $n_u$ соответствует определению [definition:unicity_distance], так как для корректной криптосистемы определение ключа единственным образом также означает и возможность получить открытый текст только одним способом.

Найдём типичное поведение функции $h(n)$ и значение расстояния единственности $n_u$. Используем следующие предположения.

Криптограф всегда стремится спроектировать систему таким образом, чтобы символы шифрованного текста имели равномерное распределение, и следовательно энтропия шифртекста имела максимальное значение:
$$ H(C_1 C_2 \dots C_n) \approx n \log_2 L, ~ n = 1, 2, \dots, N. $$
Имеет место соотношение:
$$ H(C | K) = H(C_1 C_2 \dots C_N | K) = H(M), $$
которое следует из цепочки равенств:
$$ H(MCK) = H(M) + H(K | M) + H(C | MK) = H(M) + H(K), $$
так как
$$ H(K | M) = H(K), ~~ H(C | MK) = 0, $$

$$H(MCK) = H(K) + H(C | K) + H(M | CK) = H(K) + H(C | K), $$
поскольку
$$ H(M | CK) = 0. $$
Предполагается, что для любого $n \leq N$ приближённо выполняются соотношения:
$$ H(C_n | K) \approx \frac{1}{N} H(M), $$

$$ H(C_1 C_2\dots C_n | K) \approx \frac{n}{N} H(M). $$

Вычислим энтропию $H(C_1 C_2 \dots C_n ; K)$ двумя способами:

$$ H( C_1 C_2 \dots C_n ; K ) = H(C_1 C_2 \dots C_n) + H(K | C_1 C_2 \dots C_n) \approx $$

$$ \approx n \log_2 L + h(n), $$

$$ H( C_1 C_2 \dots C_n ; K ) = H(K) + H(C_1 C_2 \dots C_n | K) \approx $$

$$ \approx H(K) + \frac{n}{N} H(M). $$

Отсюда следует, что

$$ h(n) \approx H(K) + n \left( \frac{H(M)}{N} - \log_2 L \right) $$

$$ n_u = \frac{H(K)}{ \left( 1 - \frac{H(M)}{N \log_2 L} \right) \log_2 L} = \frac{H(K)}{\rho \log_2 L}. $$

Здесь

$$ \rho = 1 - \frac{H(M)}{N \log_2 L} $$

означает избыточность источника открытых текстов.

Если избыточность источника измеряется в битах на символ, а ключ шифрования выбирается случайным образом из всего множества ключей $\{0, 1\}^{l_K}$, где $l_K$ – длина ключа в битах, то расстояние единственности $n$ также выражается в битах, и формула значительно упрощается:

equation n_u l_K.

Взяв нижнюю границу $H(M)$ энтропии одного символа английского текста как $1{,}3$ бит/символ [98, 135], получим:

$$ \rho _{en} \approx 1 - \frac{ 1{,}3 }{ \log _2 {26} } \approx 0{,}72.$$

Для русского текста с энтропией $H(M)$, примерно равной $3{,}01$ бит/символ [128]

Следует отметить, что для английского текста значение энтропии, равное $1{,}3$ бит/символ, представляет собой суммарную оценку для всего текста, в то время как оценка $3{,}01$ бит/символ энтропии для русского текста получена Лебедевым и Гармашем из анализа частот трёхбуквенных сочетаний в отрывке текста Л. Н. Толстого «Война и мир» длиной в 30 тыс. символов. Соответствующая оценка для английского текста, также приведённая в работе Шеннона, примерно равна $3{,}0$ бит/символ.

, получаем:

$$ \rho _{ru} \approx 1 - \frac{ 3{,}0 }{ \log _2 {32} } \approx 0{,}40.$$

Однако если предположить, что текст передаётся в формате простого текстового файла (англ. plain text) в стандартной кодировке UTF-8 (один байт на английский символ и два байта на символ кириллицы), то значения избыточности становятся равными приблизительно $0{,}83$ для английского и $0{,}81$ для русского языков:

gather* _en, UTF-8 1 - 1,3 _2 2^8 0,83, _ru, UTF-8 1 - 3,0 _2 2^16 0,81.

Подставим полученные значения в выражение [eq:unicity_distance_simple_frac] для шифров DES и AES. Запишем результаты в таблицу [table:unicity_distances].

Блочный шифр	Английский текст	Русский текст
Шифр DES,	$\approx~67$ бит;	$\approx~69$ бит;
ключ 56 бит	2 блока данных	2 блока данных
Шифр AES,	$\approx~153$ бит;	$\approx~158$ бит;
ключ 128 бит	3 блока данных	3 блока данных

Таблица 4.1 — Расстояния единственности для шифров DES и AES для английского и русского текстов в формате простого текстового файла и кодировке UTF-8

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

Улучшить ситуацию для легального пользователя помогает предварительное сжатие открытого текста с помощью алгоритмов архивации, что уменьшает его избыточность (а также уменьшает размер и ускоряет процесс шифрования в целом). Однако расстояние единственности не становится бесконечным, так как в результате работы алгоритмов архивации присутствуют различные константные сигнатуры, а для многих текстов можно заранее предсказать примерные словари сжатия, которые будут записаны как часть открытого текста. Более того, используемые на практике программы безопасной передачи данных вынуждены встраивать механизмы хотя бы частичной быстрой проверки правильности ключа расшифрования (например, добавлением известной сигнатуры в начало открытого текста). Делается это для того, чтобы сообщить легальному получателю об ошибке ввода ключа, если такая ошибка случится.

Соображения выше показывают, что для одного ключа расшифрования процедура проверки его корректности является быстрой. Чтобы значительно усложнить работу криптоаналитику, множество ключей, которые требуется перебрать, должно быть большой величиной (например, от $2^{80}$). Этого можно достичь, во-первых, увеличением битовой длины ключа, во-вторых, аккуратной разработкой алгоритма шифрования, чтобы криптоаналитик не смог «отбросить» часть ключей без их полной проверки.

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