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

но

X=TÅK

и тогда

DT=T'ÅT''=(X'ÅK)Å(X''ÅK)=X'ÅX''=DX

так как ключ K не меняется.

Следовательно, ключ не имеет никакого влияния на разницу входа и может игнорироваться. Другими словами, S-блок с учетом ключа имеет то же самое распределение, что и S-блок без учета ключа.

3.1.3 Построение дифференциальной характеристики.

Как только собралась информация о дифференциалах для S-блока, мы можем продолжить построение полезной дифференциальной характеристики полного шифра (за исключением последнего раунда). Это можно сделать, связывая соответствующие пары разниц S-блоков.

Например, рассмотрим подробно процесс построения дифференциальной характеристики (в дальнейшем этот процесс будет показан через таблицу). Из таблицы 1 видно, что дифференциал S-блока (01,02) имеет самую высокую вероятность 3/4. Поэтому логичнее всего взять значение для разницы входа равное DX=[01 00 00 00]. И проследим как отразится изменение всего лишь в одном полубайте на конце нашей характеристики.

Так как ключ не имеет никакого влияния на разницу входа и может игнорироваться, то мы не будем рассматривать преобразование AddRoundKey(), и каждый раунд будет состоять из 3 преобразований в следующем порядке: SubBytes(), ShiftRows() и MixColumns(). Соответственно введем для них краткие обозначения: SB, SR и MC.

Итак, в начале первого раунда DX=[01 00 00 00]. После преобразования SB промежуточная разница DT=[02 00 00 00], причем полученный дифференциал (DX,DT) имеет вероятность 3/4.

Далее идет преобразование SR, которое в разнице DT меняет местами 2 и 4 координаты

[aa bb cc dd]¾®[aa dd cc bb],

но не изменяет вероятность полученного дифференциала. В нашем случае после преобразования SR разница остается прежней DT=[02 00 00 00].

И наконец, преобразование MC также не изменяет вероятность дифференциала, но производит следующие действия над нашей разницей DT. А именно, пусть даны состояние S и разница DS до преобразования MC.

Тогда посмотрим чему будут равны состояние S и разница DS, после преобразования MC. (Заметим, что можно рассматривать первые два байта и последние два байта в состоянии S независимо, так как преобразование производится над каждым столбцом независимо.)

Откуда разница DS равна

Можно также заметить, что преобразование MC обладает следующим свойством (которое пригодиться нам при построении дифференциальной характеристики). Если , то .

После преобразования MC (а следовательно, и после всего раунда) мы получили дифференциал первого раунда с вероятностью 3/4, где . Откуда видно, что изменения затронули уже 2 полубайта.

Повторив описанную процедуру еще на один раунд, мы получим интересующий нас дифференциал (DX,DY), где . Но его вероятность уже будет равна

так как вероятности дифференциалов S-блока (04,03) и (06,0F) равны 3/8 и 1/2, соответственно.

В приведенной ниже таблице показаны последовательно все преобразования, каждая строка которой показывает разницу после текущего преобразования. Третий столбец обозначает преобразование, а последний столбец показывает номер раунда.

Обозначения xx в последнем раунде нужны только для того, чтобы проследить в каких именно полубайтах происходят различия, вызванные разницей DX. Именно в этих позициях и следует извлекать биты подключа последнего раунда.

Итак, сделаем выводы из полученного результата. Мы получили дифференциал с довольно высокой вероятностью . Но из-за большого количества различий в конце характеристики, его применение на практике сомнительно (объяснение этого утверждения будет дано ниже). Следовательно, нужно пытаться найти другую характеристику, которая будет обладать высокой вероятностью и малым числом различий.

Такие характеристики были найдены. Ниже приводятся их конечные дифференциалы, вероятность которых одинакова и равна

Для примера, приведем таблицу преобразований для первого дифференциала .

Каждый из этих четырех дифференциалов позволяет извлечь 8 бит (из 32 возможных) ключа последнего раунда, причем эти биты не пересекаются. А следовательно, приведенные четыре дифференциала позволяют определить целоком весь ключ последнего раунда, по которому сразу же определяется исходный ключ K.

3.1.4 Извлечение бит подключа последнего раунда.

В ходе процесса криптоанализа зашифровываются многие пары открытых текстов, для которых разница DX одинакова. Так же задана некая характеристика, и те пары, для которых она выполняется, называются правильными, в противном случае они носят название ошибочных.

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

Другими словами, весь ключ последнего раунда разбивается на две части. В первую часть — целевую — входят те биты, которые восстанавливают истинное значение ключа. Во вторую входят остальные биты ключа, которые не играют роли и могут принимать любые значения. Заметим, что это верно только для конкретной дифференциальной характеристики.

Для каждого возможного значения целевого частичного подключа строится ключ K', на котором выполняется частичное расшифрование такой пары шифртекстов, для которой разница DX соответствующих им пары открытых текстов одинакова.

Для каждого такого значения K' ведется счет, который увеличивается, когда разница DY=Y'ÅY'' перед последним раундом соответствует значению, ожидаемому из дифференциальной характеристики (DX,DY). Значение целевого частичного подключа, которое имеет самый большой счет, принимается за правильное.

Это верно, потому что считается, что при правильном значеним частичного подключа частота появления разницы DY (то есть, возникновение правильной пары) приближается к ожидаемой вероятности характеристики, так как характеристика имеет высокую вероятность появления. Неправильный подключ предполагает, что заданная характеристика будет ожидаться с очень низкой вероятностью.

Итак, возьмем первый дифференциал

Из приведенной выше таблицы преобразований видно, что в целевую часть подключа входят биты с 4 по 7 и с 28 по 31:

Соответственно, нам нужно перебрать все 256 возможных значения подключа . Для каждого значения подключа мы выберем случайных открытых текстов X, для которых построим столько же открытых текстов XÅDX. Далее для каждой такой пары получим шифртексты на неизвестном ключе K, и произведем их частичное расшифрование на текущем ключе-кандидате. Если пара является правильной, то увеличиваем счет ключа-кандидата. В конце подсчитываем вероятность p правильных пар для каждого значения подключа.

Ниже приведена часть результата нашей атаки.

Аналогочные атаки были проведены при помощи других трех дифференциалов

Соответственно им, ниже приведены части результатов атак на оставшиеся биты ключа .

Часть результата для второго дифференциала.

Часть результата для третьего дифференциала.

Часть результата для четвертого дифференциала.

Как видно из результатов, полученные вероятности очень близки к ожидаемым (0.045). В итоге мы получили весь ключ третьего раунда