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

Так как у нас всего две строки, то перваястрока остается на месте (сдвиг на 0 позиций), а вторая на 1 позицию.Преобразование MixColumns(). Каждый столбец нашей системы можнопредставить как полином 1 степени с коэффициентами над полем GF(28 ).Преобразование MixColumns() заменяет каждый столбец [s0 s1 ] на другой[s′0 s′1 ] по следующему правилу s′ (x) = a(x) ⊗ s(x), где a(x) = 03x + 02:¸·¸· ′ ¸ ·02 03s0s0=s′103 02s16Преобразование AddRoundKey(). Это преобразование остается без изменений.

Оно заключается в том, что каждый столбец [s0+2·c s1+2·c ] складывается с 16-битным словом расширенного ключа wround·N b+c2.4.2 Расшифрование.Полный алгоритм расшифрования описан следующим образом:state = inpAddRoundKey(state, w[Nr*Nb..Nr*Nb+1])for round = Nr-1 step -1 downto 1ShiftRows(state)InvSubBytes(state)AddRoundKey(state, w[round*Nb..round*Nb+1])MixColumns(state)end forShiftRows(state)InvSubBytes(state)AddRoundKey(state, w[0..1])out = stateАлгоритм расшифрования полностью повторяет алгоритм зашифрования вобратном порядке, за исключением одного преобразования InvSubBytes(),которое является обратным к SubBytes().

Остальные преобразования попостроению оказались совпали со своими обратными.Преобразование InvSubBytes(). Данное преобразование по построениюэквивалентно своему обратному, разница в том, что вместо подстановки S16−1используется обратная к ней подстановка S16.0 1 2 3 4 5 6 7 8↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓F A E B 7 C 6 D 29 A B C D E F↓ ↓ ↓ ↓ ↓ ↓ ↓0 4 1 5 8 3 92.4.3 Процедура развертывания ключа.В нашей системе ключ имеет длину 32 бита.

Так как на каждом раунде применяется свой раундовый ключ, то расширенный ключ строится с помощьюпроцедуры развертывания ключа KeyExpansion() из исходного ключа K.Алгоритм этой процедуры следующий:word tempi = 0while (i < Nk)w[i] = word(key[2*i], key[2*i+1])i = i+1end while7i = Nkwhile (i < Nb * (Nr+1))temp = w[i-1]if (i mod Nk = 0)temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]end ifw[i] = w[i-Nk] xor tempi = i + 1end whileИз этого алгоритма следует, что раундовый ключ строится только поключу предыдущего раунда, т.е. это рекуррентная процедура.Преобразование RotWord(). Это преобразование меняет местами координаты столбца [w0 w1 ] на столбец [w1 w0 ]. Данное преобразование эквивалентно умножению на x:w′ (x) = w(x) ⊗ xПреобразование SubWord().

Это преобразование повторяет преобразование SubBytes(), только в данном случае оно действует на столбец расширенного ключа.Раундовая константа Rcon[i].[xi−1 00].2.5Для раунда i данная константа равняетсяПрограммная реализация.Исходный код на языке C++ нашей криптосистемы приведен в Приложении 1.3 Методы криптоанализа.Наши методы криптоанализа проводятся при выбираемых открытых текстовX и соответствующих им шифртекстов Y = f (X, K).

Их целью являетсявосстановление неизвестного ключа K.Зададим значение ключа равное K = [2B 7E 15 16], одинаковое для двухметодов криптоанализа. Это значение и требуется определить в ходе атаки,используя разные методы.Прежде чем перейти непосредственно к конкретным типам криптоанализа, оценим верхнюю границу их эффективности.Длина ключа нашей системы составляет 32 бита.

Соответственно методом полного перебора всего ключевого пространства мы обязательно найдемнеизвестный ключ K ′ = K. Для этого нам потребуется максимально 232шифрований вида Y = f (X, K ′ ).Следовательно, целью криптоанализа является не только восстановлениенеизвестного ключа K, но и чтобы это восстановление с вычислительнойстороны было эффективнее метода полного перебора. Иначе считается, чтокриптосистема стойка к данным методам криптоанализа.83.1Дифференциальный криптоанализ.3.1.1 Описание криптоанализа.Дифференциальный криптоанализ использует высокую вероятность возникновения определенных различий открытого текста и различий шифртекста впоследний раунде.

Например, рассмотрим систему со входомX = [X1 X2 . . . Xn ]и выходомY = [Y1 Y2 . . . Yn ].Возьмем два входа X и X c соответствующими выходами Y ′ и Y ′′ , соответственно. Разность этих двух входов задается как ∆X = X ′ ⊕ X ′′ , где ⊕представляет двоичную операцию Исключающие-ИЛИ n-битных векторов и,следовательно,∆X = [∆X1 ∆X2 . . . ∆Xn ]′′′где ∆Xi = Xi′ ⊕ Xi′′ . Подобным образом определяется разность двух выходов∆Y .В идеальном рандомизированном шифре, вероятность, что определеннаяразница ∆Y происходит при определенной разности ∆X, равняется 1/2n ,где n — число бит в X. Дифференциальный криптоанализ стремится найти такую ситуацию, в которой определенная разность ∆Y происходит приопределенной разности ∆X с очень высокой вероятностью (то есть, намногобольшей чем 1/2n ).

Пара (∆X, ∆Y ) называется дифференциалом.Дифференциальный криптоанализ — это атака с выбираемым открытомтекстом. Это означает, что нападающий может выбирать входы и исследоватьвыходы в попытке получить ключ. Для дифференциального криптоанализа,нападающий выберает пары входов X ′ и X ′′ , удовлетворяющих определеннойразности ∆X, зная что для этого значения ∆X определенное значение ∆Yпроисходит с высокой вероятностью.В этом разделе мы исследуем построение дифференциала (∆X, ∆Y ), состоящего из открытого текста X и входа последнего раунда системы Y .

Мыбудем делать это, исследуя высоковероятные дифференциальные характеристики, где дифференциальная характеристика — это последовательностьразностей входа и выходов для каждого раунда такая, что разность выходаодного раунда соответствует разности входа для следующего раунда. Использование высоковероятной дифференциальной характеристики дает намвозможность использовать информацию для получения битов ключа последнего раунда.Чтобы построить высоковероятные дифференциальные характеристики,мы исследуем свойства отдельных S-блоков и используем эти свойства, чтобы определить полную дифференциальную характеристику.

Более точно, мыпросматриваем все возможные комбинации разниц входа и выхода S-блока,чтобы найти его высоковероятный дифференциал. Объединеним найденныедифференциалы S-блока от раунда к раунду так, чтобы отличная от нуляразница выхода от одного раунда соответствовала отличной от нуля разницевхода следующего раунда. Это позволит нам найти высоковероятный дифференциал, состоящий из открытого текста и входа последнего раунда системы.93.1.2 Дифференциальный анализ S-блока.Исследуем теперь пары разниц входа ∆X и выхода ∆Y S-блока. Рассмотрим его строение. S-блок имеет вход X = [X1 X2 X3 X4 ] и выход Y =[Y1 Y2 Y3 Y4 ]. Все пары разниц S-блока (∆X, ∆Y ) могут быть исследованы,и вероятность каждой может быть получена, рассматривая пары входа X ′ иX ′′ , такие что X ′ ⊕ X ′′ = ∆X.

Для этого нам надо всего лишь просмотретьвсе 16 различных значений для входа X ′ , и затем, перебирая все возможные∆X, получить значение X ′′ . Это возможно, так как значение X ′′ однозначноопределяется значениями X ′ и ∆X, а именно X ′′ = X ′ ⊕ ∆X.Таким образом мы можем получить значения ∆Y для каждой пары входа(X ′ ⊕ X ′′ = ∆X). Если бы S-блок был “идеальным”, то число возникновенийкаждого дифференциала равнялось бы 1, что дает вероятность 1/16 возникновения определенной разницы ∆Y при заданом значении ∆X. (Доказано,что такого “идеального” S-блока не существует.)Мы можем занести все полученные результаты для S-блока в таблицу распределения дифференциалов, в которой номер строки представляет значение∆X (в шестнадцатиричном виде), а номер столбца представляет значение∆Y .

В таблице 1 приводится распределение дифференциалов для S-блоканашей криптосистемы.0123456789ABCDEF0160000000000000001 20 00 122 00 00 06 00 40 00 00 02 04 00 02 00 00 030002600000422000400000044800000005002402000020060060400000408000000700422000000260008 90 00 02 00 04 02 00 00 00 20 26 00 00 02 00 20 10A B0 00 00 02 02 04 00 00 00 20 20 06 02 00 00 100 2C0060020000204200D0000000822000022E0006200000022400F0000008022000022Таблица 1. Распределение дифференциалов для S-блока.Прежде чем перейти к построению дифференциальной характеристики,обсудим влияние ключа на дифференциал S-блока.

Мы изучили S-блок, навход которого поступает некая последовательность. В нашей схеме на вход Sблока попадает последовательность, равная сложению по модулю 2 состоянияT с ключом K на предыдущем раунде.∆T = T ′ ⊕ T ′′ноX =T ⊕K10и тогда∆T = T ′ ⊕ T ′′ = (X ′ ⊕ K) ⊕ (X ′′ ⊕ K) = X ′ ⊕ X ′′ = ∆Xтак как ключ K не меняется.Следовательно, ключ не имеет никакого влияния на разницу входа иможет игнорироваться. Другими словами, S-блок с учетом ключа имеет тоже самое распределение, что и S-блок без учета ключа.3.1.3 Построение дифференциальной характеристики.Как только собралась информация о дифференциалах для S-блока, мы можемпродолжить построение полезной дифференциальной характеристики полного шифра (за исключением последнего раунда). Это можно сделать, связываясоответствующие пары разниц S-блоков.Например, рассмотрим подробно процесс построения дифференциальнойхарактеристики (в дальнейшем этот процесс будет показан через таблицу).Из таблицы 1 видно, что дифференциал S-блока (01, 02) имеет самую высокую вероятность 3/4.

Поэтому логичнее всего взять значение для разницывхода равное ∆X = [01 00 00 00]. И проследим как отразится изменениевсего лишь в одном полубайте на конце нашей характеристики.Так как ключ не имеет никакого влияния на разницу входа и может игнорироваться, то мы не будем рассматривать преобразование AddRoundKey(),и каждый раунд будет состоять из 3 преобразований в следующем порядке:SubBytes(), ShiftRows() и MixColumns(). Соответственно введем дляних краткие обозначения: SB, SR и MC.Итак, в начале первого раунда ∆X = [01 00 00 00]. После преобразования SB промежуточная разница ∆T = [02 00 00 00], причем полученныйдифференциал (∆X, ∆T ) имеет вероятность 3/4.Далее идет преобразование SR, которое в разнице ∆T меняет местами2 и 4 координаты[aa bb cc dd] −→ [aa dd cc bb],но не изменяет вероятность полученного дифференциала.