2015-06-05
400
Одним из ключевых моментов остается нахождение дифференциала (r-1) цикла, то есть в нашем случае это будет дифференциал третьего цикла. Когда речь идет об одном цикле, то не возникает никаких проблем. Мы легко можем найти оптимальную пару значений (DX1, DY1), показывающую нам зависимость выхода DY1 f-блока, от выхода DX1 в этот блок. Пары значений (DX1, DY1) для алгоритма S-DES приведены в таблице 4.8.
Таблица 4.8
|
|
|
Таким образом, можно сказать, что в алгоритме S-DES для одного цикла шифрования можно выделить четыре оптимальные пары, а именно: (0010, 0011), (0010,0111), (1011,1000), (1100,1001). Согласно вышеизложенному алгоритму, нам необходимо найти дифференциал третьего цикла. Для этого воспользуемся одной из приведенных выше оптимальных пар, например (0010, 0011). Мы знаем, что в случае, если последние 4 бита входного D = 0010, то на выходе f-блока первого цикла с вероятностью р1=3/8 будет получено D = 0011. Также известно, что если входное D = 0000, то с вероятностью р2=1 на выходе f-блока будет получено D = 0000. Поэтому, для того чтобы на вход f-блока второго цикла шифрования поступило D = 0000, необходимо чтобы первые 4 бита входного D были равны 0011, то есть, наиболее вероятному выходу f-блока первого цикла. В этом случае, входная D третьего цикла шифрования будет как и для первого цикла равна 0010 и с вероятностью р3=р1=3/8 даст на выходе D =
 |
0011.
|
|
|
Так как во всех трех циклах используются оптимальные пары, то
Рис. 4.4
можно сказать, что оптимальным дифференциалом третьего цикла будет являться пара (00110010, 00100011) с вероятностью р=р1*р2*р3=(3/8)*1*(3/8)=9/64 (см рис. 4.4).
Теперь, зная оптимальный дифференциал третьего цикла, можно перейти непосредственно к самому дифференциальному криптоанализу алгоритма S-DES, используя описанный выше алгоритм. Из всех известных пар открытых текстов выбираем те, D которых равна 00110010. Так как мы знаем соответствующие этим парам текстов закрытые тексты, а также знаем, что DY(3) = 00100011, то из уже выбранных пар оставляем те, у которых DY = 0011хххх.
Прежде, чем перейти к дальнейшему анализу, приведем таблицы 2.6 и 2.7 к несколько иной табличной форме, показанной в таблице 4.9.
Таблица 4.9
| Вход в S блок | Выход S0 блока | Выход S1 блока |
После этого начинаем работать с каждой парой текстов в отдельности до тех пор, пока один из подключей не будет встречаться чаще других. Первая пара открытых текстов: Х1 = 01111000, Х2 = 01001010 и соответствующая им пара закрытых текстов Y1=01000011, Y2 = 01110111. В этом случае DY = 00110100. Мы знаем, что D левой части промежуточного шифруемого значения, поступающая на вход четвертого цикла, равна 0010. D = 0010 может быть получено 16 разными способами:
1. 0000 Å 0010;
2. 0001 Å 0011;
3. 0010 Å 0000;
4. 0011 Å 0001;
5. 0100 Å 0110;
6. 0101 Å 0111;
7. 0110 Å 0100;
8. 0111 Å 0101;
9. 1000 Å 1010;
10. 1001 Å 1011;
11. 1010 Å 1000;
12. 1011 Å 1001;
13. 1100 Å 1110;
14. 1101 Å 1111;
15. 1110 Å 1100;
16. 1111 Å 1101.
Поэтому, для каждого из значений Y1 и Y2 будем рассматривать 16 возможных вариантов:
1) в случае, когда D = 0010 получено сложением по модулю 2 чисел 0000 Å 0010, имеем:
для Y1 на вход f-блока четвертого цикла поступает значение 0100, а так как DYп = 0011, то можно предположить, что на выходе f-блока будет получено значение 0011 (см рис. 4.5). Так как вход f-блока проходит перестановку с расширением, то входное значение 0100 будет преобразовано в 00101000. Выходное значение f-блока также претерпевает перестановку, однако, зная алгоритм перестановки можно определить значение, которое было до нее, то есть выходные значения S-блоков. В нашем случае это значение будет равно 1010 и с помощью таблицы перестановки преобразуется к значению 0011 на выходе f-блока. Итак, на вход первого блока замены поступает значение 0010, сложенное по модулю 2 с подключом данного цикла, и в результате замены на выходе получается значение 10. Исходя из этого, а также воспользовавшись таблицей 4.9, получаем: 0010 Å К1 = 10, где К1 представляет собой первые 4 бита подключа. Значение 10 на выходе первого блока замены может быть получено в том случае, когда на вход этого блока подано одно из следующих значений: 0011, 0110 и 1010. Исходя из этого, К1 может принимать одно из следующих значений: 0001, 0100, 1000. На вход второго блока замены поступает значение 1000, сложенное по модулю 2 с подключом данного цикла, и в результате замены на выходе получается значение 10. Исходя из этого, а также воспользовавшись таблицей 4.9, получаем: 1000 Å К2 = 10, где К2 представляет собой последние 4 бита подключа. Значение 10 на выходе второго блока замены может быть получено в том случае, когда на вход этого блока подано одно из следующих значений: 0001, 0100 и 1001. Исходя из этого, К2 может принимать одно из следующих значений: 1001, 1100,
 |
0001.
Рис. 4.5
для Y2 на вход f-блока четвертого цикла поступает значение 0111, а так как DYп = 0111, то можно предположить, что на выходе f-блока будет получено значение 0101 (см рис. 4.5). Так как вход f-блока проходит перестановку с расширением, то входное значение 0111 будет преобразовано в 10111110. Выходное значение f-блока также претерпевает перестановку, однако, зная алгоритм перестановки можно определить значение, которое было до нее, то есть выходные значения S-блоков. В нашем случае это значение будет равно 1001 и с помощью таблицы перестановки преобразуется к значению 0101 на выходе f-блока. Итак, на вход первого блока замены поступает значение 1011, сложенное по модулю 2 с подключом данного цикла, и в результате замены на выходе получается значение 10. Исходя из этого, а также воспользовавшись таблицей 4.9, получаем: 1011 Å К1 = 10, где К1 представляет собой первые 4 бита подключа. Значение 10 на выходе первого блока замены может быть получено в том случае, когда на вход этого блока подано одно из следующих значений: 0011, 0110 и 1010. Исходя из этого, К1 может принимать одно из следующих значений: 1000, 1101, 0001. На вход второго блока замены поступает значение 1110, сложенное по модулю 2 с подключом данного цикла, и в результате замены на выходе получается значение 01. Исходя из этого, а также воспользовавшись таблицей 4.9, получаем: 1110 Å К2 = 01, где К2 представляет собой последние 4 бита подключа. Значение 01 на выходе второго блока замены может быть получено в том случае, когда на вход этого блока подано одно из следующих значений: 0000, 0010, 0101, 1011 и 1100. Исходя из этого, К2 может принимать одно из следующих значений: 1110, 1100, 1011, 0101 и 0010.
|
|
|
Для 2)-го и последующих пятнадцати пунктов проводим аналогичный анализ, учитывая соответствующие значения, которыми может быть получено требуемое D = 0010. Для удобства дальнейшей работы объединим результаты анализа в таблицу 4.10.
Таблица 4.10
| Y1 | Y2 | |||
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
Аналогичным образом проведем анализ еще нескольких пар текстов и сведем результаты анализа в такие же таблицы.
|
|
|
Для X1 = 10011001, Y1=00001100; Х2=10101011, Y2 = 00110011 результаты анализа приведены в таблице 4.11
Таблица 4.11
| Y1 | Y2 | |||
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
Для Х1 = 11001011, Y1=01011011; Х2=11111001 Y2 = 01100011 результаты анализа сведены в таблицу 4.12.
Таблица 4.12
| Y1 | Y2 | |||
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
Для х1 = 11111001, y1=01100011; Х2=11001011, y2 = 01011011 результаты анализа сведены в таблицу 4.13.
Таблица 4.13
| Y1 | Y2 | |||
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
| K1 | K2 | K1 | K2 | |
Дальнейшая обработка результатов будет заключаться в сопоставлении полученных вариантов подключей. Для удобства работы составим таблицу 4.14, столбцы которой будут представлять собой первые четыре бита искомого подключа, а строки – последние четыре бита. Например, для первой строки таблицы 4.10 первые четыре бита подключа, то есть К1, 0001 и 1000 одинаковы для Y1 и Y2, последние четыре бита подключа, то есть К2, одинаковые для Y1 и Y2, равны 1100. Поэтому в новой таблице на пересечении 0001 и 1100 мы ставим 1, равно как и на пересечении 1000 и 1100. Таким образом, проанализировав наши таблицы, мы получим статистику частоты появления того или иного подключа.
Таблица 4.14
| К2 | ||||||||||||||||
| К1 | ||||||||||||||||
Из таблицы 4.14 видно, что четыре подключа встречаются чаще других, а именно: 00011010, 00011100, 10001010, 10001100. Дальнейший анализ других пар текстов поможет выяснить, какой же из этих подключей истинный. Таким образои будут найдены 8 бит ключа из 10. Остальные два бита можно найти методом грубого перебора.
