29.10.2025 18:25
Morgana0_0 0 278 Источник

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}, где каждый ключ k отвечает какому-либо обратимому преобразованию T_k. Важно, чтобы DES не был замкнутой криптосистемой. Напомню, что криптосистема называется замкнутой, если для любых трёх ключей i, j, k существуют ключи r, s, такие что T_iT_j(x) = T_r(x), T_iT_j^{-1}T_k(x) = T_s(x)для любого сообщения 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} и ищется пара ключей, такая, что T_k = T_aT_b. Если C замкнута, то такая пара с высокой вероятностью будет найдена, в противном случае её найти практически невозможно.

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

begin

  1. Выбираем k \in \mathcal{K} и p_1, ... ,p_l \xleftarrow{\text{R}} \mathcal{M}. Для i = \overline{1, l} вычисляем c_i = T_k(p_i). Пусть p = p_1 и c = c_1.

  2. Для i = \overline{1, r} выбираем a_i, b_i \in \mathcal{K} и вычисляем x_i = T_{a_i}(p) и y_i = T^{-1}_{b_i}(c).

  3. Сортируем по первой компоненте тройки (x_i, a_i, "A") и (y_i, b_i, "B") для i = \overline{1, r}.

  4. Для каждого "совпадения" x_i = y_jс 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}.

  5. return("Совпадений не найдено").

end

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

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

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

Пусть X = {x_1, ... , x_r}, Y = {y_1, ... , y_r}, 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( p )= 2ln((k - r)!) - ln(k!) - ln((k - 2r)!)

Помним, что 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 == 2(k-r)ln(k-r) - kln(k) - (k -2r)ln(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}|}}. Теорема доказана.

Литература

  1. https://csrc.nist.gov/files/pubs/fips/46-3/final/docs/fips46-3.pdf

  2. https://link.springer.com/article/10.1007/BF00206323

  3. https://www.jstor.org/stable/27956609

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