Как протестировать криптосистему на замкнутость? / forpes.ru

Главная
Как протестировать криптосистему на замкнутость?

Как протестировать криптосистему на замкнутость? +5

30.10.2025 07:23

Morgana0_0 2 266 Источник

Введение

23 ноября 1976 года DES или Data Encryption Standart был утверждён правительством США как официальный стандарт шифрования и оставался им до 1980 года. DES является алгоритмом симметричного шифрования, в основе которого лежит сеть Фейстеля. Останавливаться на подробном описании работы DES мы не будем, так как она нас не особо интересует в рамках данной статьи, но почитать подробнее можно, например, тут [1].

Любая криптосистема C характеризуется пятью параметрами: $\mathcal{K}$ - множество ключей, $\mathcal{X}$ - множество открытых текстов, $\mathcal{Y}$ - множество шифртекстов, E - преобразование зашифрования, D - преобразование расшифрования. Пространством сообщений в данном случае является $\mathcal{M} = \{0, 1\}^{64}$ , а множеством ключей $\mathcal{K} = \{0, 1\}^{56}$ , где каждый ключ отвечает какому-либо обратимому преобразованию . Важно, чтобы DES не был замкнутой криптосистемой. Напомню, что криптосистема называется замкнутой, если для любых трёх ключей существуют ключи , такие что , $T_iT_j^{-1}T_k(x) = T_s(x)$ для любого сообщения . Замкнутость в свою очередь влечёт за собой групповую структуру, в этом случае нет смысла проводить операцию зашифрования больше одного раза, так как это будет эквивалентно какому-то единичному зашифрованию. Такая особенность значительно понижает криптостойкость системы. Также, такая она влечёт уязвимость к атаке с известным открытым текстом, которая в среднем будет требовать $2^{28}$ шагов.

Является ли DES группой?

В статье [2] было показано, что DES не является группой. Остановимся более подробно на вероятностном тесте MCT(meet-in-the-middle closure test), предложенном в [2] и основанном на атаке meet in the middle, и вычислим вероятность нахождения совпадения.

Теорема: если криптосистема C замкнута, то MCT найдёт совпадения с вероятностью не меньше $1 - e^{\frac{-3r^2}{|\mathcal{K}|}}$ , где 2r - количество ключей, выбранных для проведения теста. Если же C произвольная криптосистема, то вероятность совпадения не более $\frac{|\mathcal{K}|^2}{|\mathcal{M}|!}$ .

В чём же суть MCT?

Тест работает следующим образом. На вход поступает эндоморфная ( $\mathcal{X} = \mathcal{Y}$ ) криптосистема C, выбирается случайным образом ключ $k \in \mathcal{K}$ и ищется пара ключей, такая, что . Если C замкнута, то такая пара с высокой вероятностью будет найдена, в противном случае её найти практически невозможно.

input:

$C<\mathcal{K}, \mathcal{M}, \mathcal{M}, T>$ ; l, r - параметры контроля.

begin

Выбираем $k \in \mathcal{K}$ и $p_1, ... ,p_l \xleftarrow{\text{R}} \mathcal{M}$ . Для $i = \overline{1, l}$ вычисляем . Пусть = и .
Для $i = \overline{1, r}$ выбираем $a_i, b_i \in \mathcal{K}$ и вычисляем $x_i = T_{a_i}(p)$ и $y_i = T^{-1}_{b_i}(c)$ .
Сортируем по первой компоненте тройки (, , "A") и (, , "B") для $i = \overline{1, r}$ .
Для каждого "совпадения" с $1 \leq i, j \leq r$ , если $T_k = T_{b_j}T_{a_i}$ , то return("Совпадение найдено"). Для проверки, что $T_k = T_{b_j}T_{a_i}$ достаточно проверить, что $c_h = T_{b_j}T_{a_i}(p_h)$ для всех $h = \overline{1, l}$ .
return("Совпадений не найдено").

end

Доказательство теоремы

Гораздо проще сначала доказать вторую часть утверждения. Предположим, что C замкнута, тогда для любого преобразования существует единственное преобразование , такое, что . Тогда всего возможных пар такого вида не более чем $|\mathcal{K}|^2$ , и каждая пара даёт преобразование совпадающее с с вероятностью $\frac{1}{|\mathcal{M}|!}$ . Значит осталось посчитать вероятность наступления хотя бы одного из событий Все события независимы, значит вероятность успеха - их сумма их вероятностей. Т.е. $\frac{|\mathcal{K}|^2}{|\mathcal{M}|!}$ .

Перейдём к групповому шифру. Для подсчёта соответствующей вероятности будем пользоваться идеей парадокса дня рождений [3]. P("найти совпадения") это тоже самое, что 1 - P("не найти совпадений"), а вероятность не найти совпадений посчитать гораздо проще.

Пусть X = {}, Y = {}, $k = |\mathcal{K}|$ . Тогда

$P((X \cap Y) = \varnothing) = (1 - \frac{r}{k})(1 - \frac{r}{k-1})...(1 - \frac{r}{k-r+1})=$ $= \frac{(k-r)(k-r-1)...(k-2r+1)}{\frac{k!}{(k-r)! }} = \frac{(k-r)!^2}{k!(k-2r)!} = p$

Попробуем вычислить эту вероятность приближённо.

Помним, что $ln(n!) \geq nln(n) - n$

$ln(p) \geq 2(k-r)ln(k-r) - 2(k-r) - kln(k) + k - (k-2r)ln(k-2r) + k - 2r =$

Используем разложение в ряд Тейлора:

$ln(k - r) \geq ln(k) - \frac{r}{k}$

$ln(k - 2r) \geq ln(k) - \frac{2r}{k}$

Тогда

$ln(p) \geq 2(k-r)(ln(k) - \frac{r}{k}) - kln(k) - (k - 2r)(lnk - \frac{2r}{k}) = \frac{-2r^2}{k}$

Т.е. $P((X \cap Y) = \varnothing) \geq e^{\frac{-2r^2}{k}}$ .

К сожалению, ещё не всё.

P("не найти совпадений") = $P((X \cap Y) = \varnothing)$ $\cdot$ P("X без повторов") $\cdot$ P("Y без повторов").

P("X без повторов") = P("Y без повторов") $\geq$ $e^{\frac{-r^2}{2k}}$ - вот опять пригодился парадокс дней рождений.

Отсюда P("не найти совпадений") $\geq$ $e^{\frac{-3r^2}{|\mathcal{K}|}}$ .

Тогда вероятность, что MCU найдёт совпадения $\geq 1 - e^{\frac{-3r^2}{|\mathcal{K}|}}$ . Теорема доказана.

Литература

Комментарии (2)

Number571
30.10.2025 09:11
#29038614
Важно, чтобы DES не был замкнутой криптосистемой. Напомню, что криптосистема называется замкнутой, если для любых трёх ключей существуют ключи , такие что , $T_iT_j^{-1}T_k(x) = T_s(x)$ для любого сообщения .

Что даёт условие $T_iT_j^{-1}T_k(x) = T_s(x)$ ? Кажется, что достаточным будет только условие .
1. Morgana0_0 Автор
  30.10.2025 09:11
  #29038820
  Да, тут не совсем точно. Для замкнутых достаточно первого. Второе условие нужно для неэндоморфных криптосистем, чтобы как бы обобщить для них понятие замкнутости. У Шеннона в https://pages.cs.wisc.edu/~rist/642-spring-2014/shannon-secrecy.pdf они называются "pure".