Введение
23 ноября 1976 года DES или Data Encryption Standart был утверждён правительством США как официальный стандарт шифрования и оставался им до 1980 года. DES является алгоритмом симметричного шифрования, в основе которого лежит сеть Фейстеля. Останавливаться на подробном описании работы DES мы не будем, так как она нас не особо интересует в рамках данной статьи, но почитать подробнее можно, например, тут [1].
Любая криптосистема C характеризуется пятью параметрами: 
— множество ключей, 
— множество открытых текстов, 
— множество шифртекстов, E — преобразование зашифрования, D — преобразование расшифрования. Пространством сообщений в данном случае является 
, а множеством ключей 
, где каждый ключ 
отвечает какому-либо обратимому преобразованию 
. Важно, чтобы DES не был замкнутой криптосистемой. Напомню, что криптосистема называется замкнутой, если для любых трёх ключей 
существуют ключи 
, такие что 
, 
для любого сообщения 
. Замкнутость в свою очередь влечёт за собой групповую структуру, в этом случае нет смысла проводить операцию зашифрования больше одного раза, так как это будет эквивалентно какому-то единичному зашифрованию. Такая особенность значительно понижает криптостойкость системы. Также, такая она влечёт уязвимость к атаке с известным открытым текстом, которая в среднем будет требовать 
шагов.
Является ли DES группой?
В статье [2] было показано, что DES не является группой. Остановимся более подробно на вероятностном тесте MCT(meet-in-the-middle closure test), предложенном в [2] и основанном на атаке meet in the middle, и вычислим вероятность нахождения совпадения.
Теорема: если криптосистема C замкнута, то MCT найдёт совпадения с вероятностью не меньше 
, где 2r — количество ключей, выбранных для проведения теста. Если же C произвольная криптосистема, то вероятность совпадения не более 
.
В чём же суть MCT?
Тест работает следующим образом. На вход поступает эндоморфная (
) криптосистема C, выбирается случайным образом ключ 
и ищется пара ключей, такая, что 
. Если C замкнута, то такая пара с высокой вероятностью будет найдена, в противном случае её найти практически невозможно.
input:
; l, r — параметры контроля.
begin
Выбираем
и 
. Для 
вычисляем 
. Пусть 
= 
и 
.Для
выбираем 
и вычисляем 
и 
.Сортируем по первой компоненте тройки (
, 
, «A») и (
, 
, «B») для .Для каждого «совпадения»
с 
, если 
, то return(«Совпадение найдено»). Для проверки, что достаточно проверить, что 
для всех 
.return(«Совпадений не найдено»).
и 
. Для 
вычисляем 
. Пусть 
= 
и 
.
выбираем 
и вычисляем 
и 
.
, 
, «A») и (
, 
, «B») для 
.
с 
, если 
, то return(«Совпадение найдено»). Для проверки, что 
достаточно проверить, что 
для всех 
.end
Доказательство теоремы
Гораздо проще сначала доказать вторую часть утверждения. Предположим, что C замкнута, тогда для любого преобразования 
существует единственное преобразование 
, такое, что 
. Тогда всего возможных пар такого вида не более чем 
, и каждая пара даёт преобразование совпадающее с 
с вероятностью 
. Значит осталось посчитать вероятность наступления хотя бы одного из событий 
Все события независимы, значит вероятность успеха — их сумма их вероятностей. Т.е. 
.
Перейдём к групповому шифру. Для подсчёта соответствующей вероятности будем пользоваться идеей парадокса дня рождений [3]. P(«найти совпадения») это тоже самое, что 1 — P(«не найти совпадений»), а вероятность не найти совпадений посчитать гораздо проще.
Пусть X = {
}, Y = {
}, 
. Тогда
Попробуем вычислить эту вероятность приближённо.
Помним, что 
Используем разложение в ряд Тейлора:
Тогда
Т.е. 
.
К сожалению, ещё не всё.
P(«не найти совпадений») = 
P(«X без повторов») 
P(«Y без повторов»).
P(«X без повторов») = P(«Y без повторов») 
— вот опять пригодился парадокс дней рождений.
Отсюда P(«не найти совпадений») 
.
Тогда вероятность, что MCU найдёт совпадения
. Теорема доказана.
Литература
https://csrc.nist.gov/files/pubs/fips/46-3/final/docs/fips46-3.pdf
https://link.springer.com/article/10.1007/BF00206323
https://www.jstor.org/stable/27956609
Источник: habr.com
