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

     После этого восьмибитовое сообщение претерпевает перестановку согласно таблице 2.4.5 и на выходе получается готовый шифр - текст.

Таблица 2.4.1 – Промежуточные вычисления.

Таблица 2.4.2 Таблица 2.4.1 – Промежуточные  вычисления. 
 

Таблица 2.4.3 Таблица 2.4.1 – Промежуточные вычисления.

Таблица 2.4.4 Таблица 2.4.1 – Промежуточные вычисления.

Таблица 2.4.5 Таблица 2.4.1 – Промежуточные вычисления. 

     Как и в случае с алгоритмом шифрования DES, криптоанализ данного алгоритма начнется с анализа блоков замены и нахождения наиболее эффективного линейного уравнения. Результаты анализа блока 1, 6лока2 и блока 3 приведены соответственно в таблицах (2.4.6), (2.4.7), (2.4.8).

Таблица 2.4.6 – Анализ блока 1.

Таблица 2.4.7 – Анализ блока 2.

Таблица 2.4.8 – Анализ блока 3.

     Итак, согласно таблице 2.4.6 мы можем составить первые три наиболее эффективных линейных уравнения. Сразу следует отметить, что одно из уравнений будет более эффективным, однако его не достаточно для нахождения битов ключа, поэтому мы берем еще уравнение, наиболее приближенное по своей эффективности к первому. В табл. 3.11 определены три пары (i,j) - (12,5), (14,1) и (15,2). Так как в блок 1. согласно таблице перестановки с расширением входят биты ХЗ, Х4. XI, Х2, а выходные биты после перестановки оказываются на местах Y7, Y4, Y3, то. учитывая, что мы работаем с правой 8-битовой частью исходного 16-битового сообщения, а также сложение по модулю два левой части исходного сообщения с результатом функции f. получаем следующие уравнения:

Х11 ⊕ Х12 ⊕ Y7 ⊕ Y3 ⊕ Х7 ⊕ Х3 = К1 ⊕ К2,                (2.4.1)

которое  выполняется  с  вероятностью р = 1/16, а соответственно  ∆  = |1 –2р| =7/8.

Х11 ⊕ Х12 ⊕ Х9 ⊕ Y3 ⊕ Х3 = К1 ⊕ К2 ⊕ К3,            (2.4.2)

которое выполняется с вероятностью р = 13/16, а соответственно ∆  = |1 –2р| =5/8.

Х11 ⊕ Х12 ⊕ Х9 ⊕ Х10 ⊕ Y4 ⊕ Х4 = К1 ⊕ К2 ⊕ K3 ⊕ К4,      (2.4.3)

которое выполняется  с  вероятностью р = 3/16, а соответственно ∆  = |1 –2р| =5/8.

Аналогичным образом составляем уравнения для  двух остальных блоков. Результаты анализа сведены в табл. 3.14.

Таблица 2.4.9 – Уравнения для S-блоков DES.

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

     Используя уравнения, полученные из блока 1, находим . что из N=30 открытых текстов число открытых текстов, для которых левая часть уравнения (1) равна 0, Т=22. Так как в этом случае вероятность р = 1/16, то по вышеописанному алгоритму находим, что: К1⊕К2 = 1.

     Для уравнения (2) T = 23, а р= 13/16, тогда К1⊕К2⊕КЗ = 0. (2.4.4)

     Для уравнения (3) T = 12, а р=3/16, тогда К1⊕К2⊕К3⊕К4 = 0. (2.4.5)

     Зная  это, из уравнений (16) и (17), находим, что К4 = 0. Из уравнений

(16) и (15) находим, что КЗ = 1. Так как К1⊕К2 = 1, то возможны два варианта: либо Kl=0 и К2 = 1, либо Kl=1 и К2 = 0.

     Аналогичным образом находим биты ключа для  второго блока.

     Для уравнения (4) T = 4, а р=1/8, тогда К5⊕К6⊕К7 = 0.                (2.4.6)

     Для уравнения (5) T = 25, а р=3/16, тогда К7 = I                          (2.4.7)

     Для уравнения (6) T = 25. а р=3/16, тогда К5⊕К6⊕К8 = I.            (2.4.8)

     Для уравнения (7) T = 6, а р= 13/196. тогда К5⊕К6 =1.             (2.4.9)

     Для уравнения (8) T = 6. а р=1/8, тогда К5⊕К6⊕К7⊕К8 = 0.    (2.4.10)

     Из  уравнений (20) и (21) находим К8 = 0. Так как К5⊕К6 = 1, то возможны два варианта: либо К5=0 и Кб = I: либо К5=1 и К6 = 0.

     Итак, после анализа двух таблиц имеем четыре возможных вариантов первых восьми бит ключа:

Kl= 01100110xxxx:

К2 = 1010011хххх

КЗ = 01101010хххх

К4 = 10101010хххх.

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

ЗАКЛЮЧЕНИЕ 
 

      С развитием современной криптографии, от разрабатываемых методов шифрования требуется все больше  доказательств устойчивости их алгоритмов против различных атак и методов криптоанализа. Одним из таких методов криптоанализа является линейный. Появившийся не так давно, он показал уязвимость многих методов шифрования, яркими примерами этого является уже ставший классическим шифр DES, RC5 (в случае использования слабых ключей), и так далее. В настоящее время от разрабатываемых новых методов шифрования требуется доказательство стойкости против линейного криптоанализа.

     Линейный  метод криптоанализа продолжает совершенствоваться, границы его  применимости уже распространились на потоковые шифры. 
 
 
 
 
 
 
 
 

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТРАТУРЫ 

1. Бабенко Л.К., Ищукова Е.А. - Современные алгоритмы блочного шифрования и методы их анализа.

2.  Бабенко  Л.К. Мишустина Е.А. – Изучение  современных методов криптоанализа  (методическое пособие).

3. Материалы сайта www.intuit.ru. 
 
 
 
 
 
 
 
 
 
 
 
 
 

ПРИЛОЖЕНИЯ

Таблица 1 – Соответствие входов и выходов  алгоритма шифрования DES.

Таблица 2 – Анализ блока S5 алгоритма шифрования DES для применения метода линейного криптоанализа.

Таблица 3 – 30 пар открытый-закрытый текст , зашифрованных с помощью учебного алгоритма на ключе К=101010101010