SP-сети и линейный криптоанализ по лекциям Токаревой

Так, для применения леммы 1 при получении вероятности линейного приближения в методе «от простого — к сложному» требуется.Предположение 1. Считаем, что случайные величины X i, определяющие соотношения X i = 0 из схемы раундовых приближений, независимы. Заметим, что на практике это предположение выполняется очень редко. Тем не менее, лемму 1 почти всегда применяют, поскольку в реальных шифрах влияние зависимости случайных величин оказывается очень малым. Предположение 2. Пусть найдено линейное соотношение L вида (Р,а) 0 {С, в) = (K , y ), выполняющееся с вероятностью 1/2 + е, достаточно сильно отличающейся от 1/2 при случайном равновероятном выборе открытого текста Р и ключа K . Тогда предполагаем, что для практически всех ключей K вероятность выполнения L также достаточно сильно отличается от 1 /2 при случайном равновероятном выборе открытого текста Р.Пусть при фиксированном ключе K вероятность выполнения линейного соотношения L равна 1/2 + . Тогда, предположение 2 означает, что если величина достаточно большая, то для практически всех ключей K величина также большая. Заметим, что если линейное приближение L было получено методом «от простого — к сложному», то предположение 2 всегда выполняется, так как при любом ключе K справедливо = . Следующее предположение необходимо для работы алгоритма 2 определения нескольких битов ключа.1.4 Линейный криптоанализ DES.Линейный криптоанализ шифра DES. предложенный МицуруМацуи в 1994 году, проводится по второму алгоритму и основан на следующем. Строится линейное приближение L для 14 раундов шифра DES (без первого и последнего раундов). Определяются 12 активных битов ключа, знания которых достаточно для того, чтобы по известной паре открытого и шифрованного текстов вычислить левую часть соотношения L. Далее линейный криптоанализ запускается параллельно 212 раз и по алгоритму 2 определяется правильное значение группы активных битов ключа. Кроме того, из самого линейного соотношения определяется еще один, 13-й, бит ключа. Затем процедура повторяется с аналогичным линейным соотношением, полученным из первого перестановкой местами открытого и шифрованного текстов. Так восстанавливаются еще 13 битов ключа. Оставшиеся 30 битов ключа находятся перебором.Линейное приближение для DES. Для нахождения линейного приближения по методу «от простого — к сложному» используются следующие линейные приближения S-блоков:S -блоксоотношениевероятность:=42/64:=34/64:=52/64Сначала по методу «от простого — к сложному» каждое соотношение используется для построения приближений раундовой функции DES. С помощью этих соотношений выстраиваем специальную схему приближений для четырнадцати раундов шифра DES (без первого и последнего раундов, как требуется во втором алгоритме линейного криптоанализа), см. таблицу. После сложения всех линейных соотношений из таблицы получаем линейное приближение для раундов со второго по пятнадцатый включительно:Это соотношение согласно piling-up лемме выполняется с вероятно+**********=+0.50000057Напомним, что если на вход алгоритма DES подать шифртекст C, а раундовые ключи использовать в обратном порядке (т. е. сначала K 16, затем K 15 и т. д.), то на выходе алгоритма получим открытый текст P. Благодаря этому свойству шифра DES по (8.1) устанавливаем еще одно линейное соотношение также выполняющееся с вероятностью 1/2 + . Оба эти соотношения будем использовать для анализа.В среднем для нахождения ключа DES с помощью данного метода потребуется приблизительно пар открытого и шифрованного текстов. При этом успех ожидается в 85% случаев, т.е. найденный с помощью метода ключ будет правильным вероятностью 0,85. Отметим, что вследствие большого объема статистики этот метод криптоанализаDES не относится к числу практичных.Замечания. Линейный криптоанализ шрифта DES оказался возможным в связи со слабыми свойствами его S-блока. Для того, чтобы шифр имел стойкость к линейному крипроанализу, его S-блоки должны быть построены с использованием нелинейных булевых функций, таких как максимально нелинейные функции и их обобщения.СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫТокарева Н. Н. Симметричная криптография. Краткий курс: учебное пособие / Новосиб. гос. ун-т. Новосибирск, 2012. 234 с.Видео Лекция 3. Линейный и дифференциальный криптоанализ. https://www.youtube.com/watch?v=nEHVfeaPjNw&t=4778s. (дата обращения 12.11.2022).Токарева Н. Н. Об истории криптографии в России. https://cyberleninka.ru/article/n/ob-istorii-kriptografii-v-rossii. (дата обращения 12.11.2022).Токарева Н. Н. Квадратичные аппроксимации специального вида для четырехразрядных подстановок в S-блоках.https://cyberleninka.ru/article/n/kvadratichnye-approksimatsii-spetsialnogo-vida-dlya-chetyrehrazryadnyh-podstanovok-v-s-blokah. (дата обращения 12.11.2022).Городилова А. А., Токарева Н. Н., Шушуев Г. И. Криптография и криптоанализ : сборник задач : учебное пособие / А. А. Городилова, Н. Н. Токарева, Г. И. Шушуев; М-во образования и науки РФ, Новосибирский гос. ун-т, Мех.-мат. фак., Каф. теоретической кибернетики. - Новосибирск : НГУ, 2014. - 325 с.