rijndael (Курсовая - Построение и исследование криптосистемы на основе Rijndael), страница 3

В нашем случаепосле преобразования SR разница остается прежней ∆T = [02 00 00 00].И наконец, преобразование MC также не изменяет вероятность дифференциала, но производит следующие действия над нашей разницей ∆T . Аименно, пусть даны состояние S и разница ∆S до преобразования MC.S = [s0 s1 s2 s3 ] и ∆S = [∆s0 ∆s1 ∆s2 ∆s3 ]e после преТогда посмотрим чему будут равны состояние Se и разница ∆S,образования MC. (Заметим, что можно рассматривать первые два байта ипоследние два байта в состоянии S независимо, так как преобразование производится над каждым столбцом независимо.)se0 = 02 • s0 ⊕ 03 • s1se1 = 03 • s0 ⊕ 02 • s1se0 ⊕ ∆es0 = 02 • (s0 ⊕ ∆s0 ) ⊕ 03 • (s1 ⊕ ∆s1 ) = se0 ⊕ 02 • ∆s0 ⊕ 03 • ∆s1se1 ⊕ ∆es1 = 03 • (s0 ⊕ ∆s0 ) ⊕ 02 • (s1 ⊕ ∆s1 ) = se1 ⊕ 03 • ∆s0 ⊕ 02 • ∆s111Откуда разница ∆Se равна∆es0 ∆es1e∆S = ∆es2∆es302 • ∆s0 ⊕ 03 • ∆s1  03 • ∆s0 ⊕ 02 • ∆s1 =  02 • ∆s2 ⊕ 03 • ∆s3 03 • ∆s2 ⊕ 02 • ∆s3Можно также заметить, что преобразование MC обладает следующимсвойством (которое пригодиться нам при построении дифференциальной характеристики).

Если ∆s = ∆s0 = ∆s1 , то ∆es = ∆es0 = ∆es1 = ∆s.После преобразования MC (а следовательно, и после всего раунда) мыполучили дифференциал первого раунда (∆X, ∆Y1 ) с вероятностью 3/4, где∆Y1 = [04 06 00 00]. Откуда видно, что изменения затронули уже 2 полубайта.Повторив описанную процедуру еще на один раунд, мы получим интересующий нас дифференциал (∆X, ∆Y ), где ∆Y = ∆Y2 = [06 05 11 1E]. Ноего вероятность уже будет равнаp=93 3 1· · =≈ 0.141,4 8 264так как вероятности дифференциалов S-блока (04, 03) и (06, 0F) равны 3/8и 1/2, соответственно.В приведенной ниже таблице показаны последовательно все преобразования, каждая строка которой показывает разницу после текущего преобразования.

Третий столбец обозначает преобразование, а последний столбецпоказывает номер раунда.∆X∆Y1∆Y2[01 00 00 00][02 00 00 00][02 00 00 00][04 06 00 00][03 0F 00 00][03 00 00 0F][06 05 11 1E][0x 0x xx xx][0x xx xx 0x]0SBSRMCSBSRMCSBSR123Обозначения xx в последнем раунде нужны только для того, чтобы проследить в каких именно полубайтах происходят различия, вызванные разницей∆X. Именно в этих позициях и следует извлекать биты подключа последнегораунда.Итак, сделаем выводы из полученного результата. Мы получили дифференциал с довольно высокой вероятностью 9/64 ≫ 1/232 . Но из-за большогоколичества различий в конце характеристики, его применение на практикесомнительно (объяснение этого утверждения будет дано ниже).

Следовательно, нужно пытаться найти другую характеристику, которая будет обладатьвысокой вероятностью и малым числом различий.Такие характеристики были найдены. Ниже приводятся их конечные дифференциалы, вероятность которых одинакова и равнаp=729≈ 0.045.1638412(∆X (1) , ∆Y (1) ) = ([01 01 04 04], [02 02 00 00])(∆X (2) , ∆Y (2) ) = ([04 04 01 01], [00 00 02 02])(∆X (3) , ∆Y (3) ) = ([10 10 40 40], [20 20 00 00])(∆X (4) , ∆Y (4) ) = ([40 40 10 10], [00 00 20 20])Для примера, приведем таблицу преобразований для первого дифференциала (∆X (1) , ∆Y (1) ).∆X∆Y1∆Y2[01 01 04 04][02 02 03 03][02 03 02 03][01 00 00 01][02 00 00 02][02 02 00 00][02 02 00 00][0x 0x 00 00][0x 00 00 0x]0SBSRMCSBSRMCSBSR123Каждый из этих четырех дифференциалов позволяет извлечь 8 бит (из32 возможных) ключа последнего раунда, причем эти биты не пересекаются.А следовательно, приведенные четыре дифференциала позволяют определитьцелоком весь ключ последнего раунда, по которому сразу же определяетсяисходный ключ K.3.1.4 Извлечение бит подключа последнего раунда.В ходе процесса криптоанализа зашифровываются многие пары открытыхтекстов, для которых разница ∆X одинакова.

Так же задана некая характеристика, и те пары, для которых она выполняется, называются правильными,в противном случае они носят название ошибочных.Если обнаружена дифференциальная характеристика R-1 раундов с достаточно большой вероятностью для шифра с числом раундов R, то можно напасть на шифр, извлекая биты подключа последнего раунда. В нашемслучае, возможно извлечь биты из подключа K3 последнего раунда. Этотпроцесс основывается на частичном расшифровании последнего раунда двухшифртекстов, для которых известна разница ∆X, и исследовании разницы∆Y перед последним раундом с целью определения правильной пары.

Те позиции подключа, для которых разница после последнего раунда ненулевая,называются целевым частичным подключем.Другими словами, весь ключ последнего раунда разбивается на две части.В первую часть — целевую — входят те биты, которые восстанавливаютистинное значение ключа. Во вторую входят остальные биты ключа, которыене играют роли и могут принимать любые значения. Заметим, что это вернотолько для конкретной дифференциальной характеристики.Для каждого возможного значения целевого частичного подключа строится ключ K ′ , на котором выполняется частичное расшифрование F −1 такойпары шифртекстов, для которой разница ∆X соответствующих им пары открытых текстов одинакова. ′−1′ Y = FK′ (f (X , K))−1′′Y = FK ′ (f (X ′′ , K))∆X = X ′ ⊕ X ′′13Для каждого такого значения K ′ ведется счет, который увеличивается,когда разница ∆Y = Y ′ ⊕ Y ′′ перед последним раундом соответствует значению, ожидаемому из дифференциальной характеристики (∆X, ∆Y ).

Значение целевого частичного подключа, которое имеет самый большой счет,принимается за правильное.Это верно, потому что считается, что при правильном значеним частичного подключа частота появления разницы ∆Y (то есть, возникновение правильной пары) приближается к ожидаемой вероятности характеристики, таккак характеристика имеет высокую вероятность появления. Неправильныйподключ предполагает, что заданная характеристика будет ожидаться с оченьнизкой вероятностью.Итак, возьмем первый дифференциал(∆X, ∆Y ) = (∆X (1) , ∆Y (1) ) = ([01 01 04 04], [02 02 00 00]).Из приведенной выше таблицы преобразований видно, что в целевую частьподключа K3 входят биты с 4 по 7 и с 28 по 31:K3 = [0000 xxxx 0000 0000 0000 0000 0000 xxxx].Соответственно, нам нужно перебрать все 256 возможных значения подключа [K3,4 .

. . K3,8 , K3,28 . . . K3,31 ]. Для каждого значения подключа мы выберем214 случайных открытых текстов X, для которых построим столько же открытых текстов X ⊕∆X. Далее для каждой такой пары получим шифртекстына неизвестном ключе K, и произведем их частичное расшифрование на текущем ключе-кандидате.

Если пара является правильной, то увеличиваемсчет ключа-кандидата. В конце подсчитываем вероятность p правильных пардля каждого значения подключа.Ниже приведена часть результата нашей атаки.[K3,4 . . . K3,8 , K3,28 . . . K3,31 ]E BE CE DE EE FF 0F 1F 2F 3F 4F 5F 6F 7F 8F 9F AF Bp0.000610.000000.002010.000000.001590.000000.023010.005680.045110.022710.000000.029540.000000.011410.000000.011840.00507Аналогочные атаки были проведены при помощи других трех дифферен-14циалов(∆X (2) , ∆Y (2) ) = ([04 04 01 01], [00 00 02 02])(∆X (3) , ∆Y (3) ) = ([10 10 40 40], [20 20 00 00])(∆X (4) , ∆Y (4) ) = ([40 40 10 10], [00 00 20 20])Соответственно им, ниже приведены части результатов атак на оставшиесябиты ключа K3 .Часть результата для второго дифференциала.[K3,12 . .

. K3,15 , K3,20 . . . K3,23 ]9 E9 FA 0A 1A 2A 3A 4A 5A 6p0.000000.000000.023190.000000.042240.005000.000000.023740.00000Часть результата для третьего дифференциала.[K3,0 . . . K3,3 , K3,24 . . . K3,27 ]B 7B 8B 9B AB BB CB DB EB Fp0.016420.000000.023440.005130.044620.023010.000000.027950.00000Часть результата для четвертого дифференциала.[K3,8 . . . K3,11 , K3,16 . .

. K3,19 ]7 97 A7 B7 C7 D7 E7 F8 08 1p0.000000.021480.000000.005190.043880.000000.022520.000000.00000Как видно из результатов, полученные вероятности очень близки к ожидаемым (0.045). В итоге мы получили весь ключ третьего раунда K3K3 = [BF 7A D2 B3].153.1.5 Восстановление исходного ключа.Для восстановления исходного ключа K = [k0 k1 k2 k3 ] распишем подробноработу функции KeyExpansion().k4 = k0 ⊕ S(k3 ) ⊕ 01k5 = k1 ⊕ S(k2 )k6 = k2 ⊕ k4k7 = k3 ⊕ k5k8 = k4 ⊕ S(k7 ) ⊕ 02k9 = k5 ⊕ S(k6 )k10 = k6 ⊕ k8k11 = k7 ⊕ k9k12 = k8 ⊕ S(k11 ) ⊕ 04k13 = k9 ⊕ S(k10 )k14 = k10 ⊕ k12k15 = k11 ⊕ k13Так как мы знаем весь ключ K3 = [k12 k13 k14 k15 ], то можем получитьсначала подключи k10 и k11 , а затем k8 и k9 , то есть весь ключ K2 .k10 = k12 ⊕ k14 = BF ⊕ D2 = 6Dk11 = k13 ⊕ k15 = 7A ⊕ B3 = C9k8 = S(k11 ) ⊕ k12 ⊕ 04 = S(C9) ⊕ BF ⊕ 04 = 5F ⊕ BF ⊕ 04 = E4k9 = S(k10 ) ⊕ k13 = S(6D) ⊕ 7A = 67 ⊕ 7A = 1DПодобным образом мы находим ключ K1 и собственно исходный ключ K.K = [2B 7E 15 16]3.1.6 Эффективность криптоанализа.Всего было использовано 4 дифференциала.

Для каждого дифференциалачисло вариантов подключей равнялось 256. Для каждого подключа было проанализировано 214 пар открытых текстов. То есть всего было произведенно225 зашифрований.Откуда следует, что дифференциальный криптоанализ оказался на 7 порядков эффективнее, чем метод полного перебора, и наша криптосистемаоказалась нестойкой к данному методу криптоанализа.3.1.7 Программная реализация.Исходный код на языке C++ для дифференциального криптоанализа приведен в Приложении 2.3.2Линейный криптоанализ.3.2.1 Описание криптоанализа.Линейный криптоанализ пытается воспользоваться преимуществом возникновений с высокой вероятностью линейных выражений, включающих в себя16биты открытого текста, шифртекста и ключа.

В отличии от дифференциального, линейный криптоанализ — это атака с известным открытом текстом,то есть предполагается, что нападающий имеет информацию о наборах открытых текстов и соответствующим им шифртекстов.Основная идея состоит в том, чтобы найти линейное приближение длядействия части шифра.Xi1 ⊕ Xi2 ⊕ . .

. ⊕ Xiu ⊕ Yj1 ⊕ Yj2 ⊕ . . . ⊕ Yjv = 0(1)где Xi представляет i-ый бит входа X = [X1 X2 . . .] и Yj представляет j-ыйбит выхода Y = [Y1 Y2 . . .].Подход в линейному криптоанализу состоит в том, чтобы определить подобные линейные приближения, выполнение которых имеет высокую илинизкую вероятность. Если шифр проявляет тенденцию к таким приближениям, то это свидетельствует о его “неслучайности”. Для “случайного” шифраполагаем, что если мы случайно выбираем значения для u+v бит и подставляем их в уравнение выше, то вероятность, что выражение будет выполняться,была бы точно 1/2.Если все таки удается найти такое приближение, и оно выполяется свероятность pL 6= 1/2, то мы можем использовать его для линейного криптоанализа.

Величина ε = pL − 1/2 называется отклонением. Чем выше величина |ε| (или эффектвностью соотношения), тем лучше применимость линейного криптоанализа с меньшим количеством известных открытых текстов,требуемых в нападении.Есть несколько способов атаки при помощи линейного криптоанализа. Вэтой работе мы рассмотрим тот, который Матсуи называет Алгоритм 2. Оннесколько легче в применении на практике, чем основной метод, которыйописан в большинстве литературы.