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

3.1.5 Восстановление исходного ключа.

Для восстановления исходного ключа распишем подробно работу функции KeyExpansion().

Так как мы знаем весь ключ , то можем получить сначала подключи и , а затем и , то есть весь ключ .

Подобным образом мы находим ключ и собственно исходный ключ K.

K=[2B 7E 15 16]

3.1.6 Эффективность криптоанализа.

Всего было использовано 4 дифференциала. Для каждого дифференциала число вариантов подключей равнялось 256. Для каждого подключа было проанализировано пар открытых текстов. То есть всего было произведенно зашифрований.

Откуда следует, что дифференциальный криптоанализ оказался на 7 порядков эффективнее, чем метод полного перебора, и наша криптосистема оказалась нестойкой к данному методу криптоанализа.

3.1.7 Программная реализация.

Исходный код на языке C++ для дифференциального криптоанализа приведен в Приложении 2.

3.2 Линейный криптоанализ.

3.2.1 Описание криптоанализа.

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

Основная идея состоит в том, чтобы найти линейное приближение для действия части шифра.

(1)

где представляет i-ый бит входа и представляет j-ый бит выхода .

Подход в линейному криптоанализу состоит в том, чтобы определить подобные линейные приближения, выполнение которых имеет высокую или низкую вероятность. Если шифр проявляет тенденцию к таким приближениям, то это свидетельствует о его “неслучайности”. Для “случайного” шифра полагаем, что если мы случайно выбираем значения для u+v бит и подставляем их в уравнение выше, то вероятность, что выражение будет выполняться, была бы точно 1/2.

Если все таки удается найти такое приближение, и оно выполяется с вероятность , то мы можем использовать его для линейного криптоанализа. Величина называется отклонением. Чем выше величина |e| (или эффектвностью соотношения), тем лучше применимость линейного криптоанализа с меньшим количеством известных открытых текстов, требуемых в нападении.

Есть несколько способов атаки при помощи линейного криптоанализа. В этой работе мы рассмотрим тот, который Матсуи называет Алгоритм 2. Он несколько легче в применении на практике, чем основной метод, который описан в большинстве литературы. Мы рассмотрим построение линейного приближения, содержащего биты открытого текста X и биты входа последнему раунда Y. (То есть мы рассматриваем те же объекты, что и в дифференциальном криптоанализе.)

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

Обратим внимание, если , то это подразумевает, что шифр имеет катастрофическую слабость. Если , то это также признак катастрофической слабости.

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

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

3.2.2 Линейный анализ S-блока.

Перед рассмотрением атаки на полный шифр, сначала получим знания об линейной уязвимости S-блока. Рассмотрим S-блок со входом и соответствующим выходом . Все линейные приближения могут быть исследованы, чтобы определить их пригодность для линейного анализа, вычисляя для каждого отклонение. Следовательно, мы просмотрим все выражения вида (1), где X и Y — вход и выход S-блока, соответственно.

Рассмотрим общий вид линейного выражения для S-блока

где . Наборы коэффициентов и называются “суммой входа” и “суммой выхода”, соответственно. Они показывают какие биты входа и выхода присутствуют в конкретном линейном выражении. Их также удобно записывать в шестнадцатиричном виде. Например, если сумма входа и сумма выхода равны 6 и B, то линейное выражение имеет следующий вид

Полное перечисление всех линейных приближений S-блока в нашем криптоалгоритме приведено в таблице 2. Каждый элемент в таблице представляет число выполнения линейного выражения заданного суммой входа (строка таблицы) и суммой выхода (столбец таблицы) минус 8. Следовательно, поделив это число на 16, результат даст нам значение отклонения данного линейного выражения.

Table 2: Линейные приближения для S-блока.