2015-06-05
408
Для того, чтобы наглядно убедиться в том, как работает данный метод, рассмотрим схему шифрования, описанную в главе Линейный криптоанализ. Для удобства работы с данными создадим Таблицу 4.2, отражающую зависимость выходов блоков замены от входных данных.
Таблица 4.2
| Вход в блок перестановки | Выход Блока 1 | Выход Блока 2 | Выход Блока 3 |
После того, как подготовительная работа проведена можно приступить к анализу блоков замены и построению таблиц зависимостей DА от DС.
Строятся данные таблицы следующим образом. Так как на вход каждого блока замены подается по четыре бита, то и их размерность их суммы по модулю 2 не будет превышать четырех бит. Таким образом, диапазон изменения DА лежит в пределах 0000 – 1111. Но, так как пара анализируемых текстов должна различаться хотя бы одним битом, то мы не можем использовать DА=0000. Поэтому диапазон изменения DА составляет 15 значений от 0001 до 1111. Каждое из значений DА может быть получено шестнадцатью возможными комбинациями входных данных блоков замены. Так, например, DА=0001 может быть получено следующими возможными комбинациями:
1. 0000Å0001;
2. 0001Å0000;
3. 0010Å0011;
4. 0011Å0010;
5. 0100Å0101;
6. 0101Å0100;
7. 0110Å0111;
8. 0111Å0110;
9. 1000Å1001;
10. 1001Å1000;
11. 1010Å1011;
12. 1011Å1010;
13. 1100Å1101;
14. 1101Å1100;
15. 1110Å1111;
16. 1111Å1110;
При этом, сумма выходов по модулю 2, полученных после прохождения любой пары данных входов через конкретный блок замены, не всегда совпадет с суммой выходов того же блока замены по модулю 2 другой пары. Поясним сказанное на примере. Рассмотрим пару входов 0011Å0010. 0011 при прохождении через Блок 1 даст нам 011, а 0010 – 001. Сумма этих выходов по модулю 2 будет равна DС = 011Å001 = 010.
А теперь рассмотрим другую пару входов 0110Å0111. При прохождении через Блок 1 0110 даст нам 010, а 0111 – 101. Таким образом, DС = 010Å101 =111.
Из данного примера наглядно видно, что одному и тому же значению DА могут соответствовать различные DС. Анализ блоков замены приведен в таблицах 4.3, 4.4 и 4.5 соответственно. Как видно из таблицы 4.3, в случае, когда DА = 0001, 8 раз появляется DС = 010, 2 раза DС = 101 и DС = 110 и 4 раза DС = 111.
Таблица 4.3
Зависимость DС от DА в Блоке 1
| DС | ||||||||
| DА | ||||||||
Таблица 4.4
Зависимость DС от DА в Блоке 2
| DС | ||||||||
| DА | ||||||||
Таблица 4.5
Зависимость DС от DА в Блоке 3
| DС | ||||
| DА | ||||
После того, как проведен анализ и построены таблицы, можно приступить к выявлению наилучшего DА и соответствующего ему DС, то есть пары (DА, DС). Из таблиц 4.4 и 4.5 сразу видно, что для Блока 2 оптимальна пара (1111,111), а для Блока 3 – (1111,01). Таким образом, сразу можно сказать, что однозначно определены последние 8 бит DА (того DА, которое получается суммированием по модулю 2 Е(Х) и Е(Х1)), то есть DА = хххх11111111, а значит однозначно определены последние 5 бит соответствующего DС (DС = ххх11101). Немного иначе обстоит дело с таблицей 4.3. В ней можно выделить несколько равновероятных пар (DА, DС). Вот они: (0001,010), (1010,100), (1110,111), (1111,101). А соответственно возникает 4 варианта 12-битного DА. Однако, следует учитывать еще один немаловажный факт: DА равно сумме по модулю 2 переставленных и расширенных входных битов. Поэтому, согласно таблице перестановки с расширением, используемой в данном алгоритме шифрования, в DА соответственно должны быть равны следующие пары бит: 3 и 9, 8 и 10, 2 и 11, 4 и 12. Этому условию удовлетворяет единственное значение DА = 111111111111, которому соответствует DС = 10111101. Именно с ним и будет вестись дальнейшая работа. Сведения по определению наилучшего 12-битного DА приведены в таблице 4.6.
Таблица 4.6
Выбор наилучшего 12-битного DА
| DА | DХ | DС |
| -------- | ||
| -------- | ||
| -------- | ||
| хххххххх11111111 |
Теперь, зная наилучшее DА, можно приступить к нахождению ключа. Для этого нам понадобятся несколько пар открытых текстов (Х, Х1), таких, что DА = Е(Х)ÅЕ(Х1) = 111111111111, а DС = S(Е(Х))ÅS(Е(Х1)) = 10111101. Для того, чтобы из зашифрованного сообщения Х выделить S(Е(Х)) необходимо к последним восьми битам шифрованного сообщения добавить первые восемь бит открытого текста, а затем учесть последнюю перестановку. Для удобства работы данные тексты и относящиеся к ним данные занесены в таблицу 4.7.
Таблица 4.7
Пары открытых текстов (Х,Х1), соответствующие наилучшим (DА, DС)
| № | Х | Е(Х) | S(Е(Х)) | Y | Х1 | Е(Х1) | S(Е(Х1)) | Y1 |
Рассмотрим приведенные пары открытых текстов. Необходимо так же учитывать, что результат f-блока складывается по модулю 2 с левой частью исходного сообщения. Но в связи с тем, что в нашем случае левые восемь бит исходных сообщений равны нулю, то можно сделать вывод, что левые восемь бит шифрованного сообщения и есть выход f-блока. Так как на вход блоков замены поступают значения Е(Х), то для всех Х и Х1 имеем следующую картину:
Для Блока 1:
1. Пара (0000000000000001, 0000000011111110):
Так как на вход блока поступает значение Е(Х) Å Кi, то имеем следующую картину:
0000ÅК1 даст на выходе 010;
1111ÅК1 даст на выходе 111;
Из таблицы 4.2 определяем, что на выходе Блока 1 значение 010 получается в том случае, когда на его вход подается одно из значений 0110 или 1010, а значение 111 – при входных 1001 или 0101. Исходя из этого имеем следующие возможные варианты:
0000ÅК1 = 0110; К1 = 0110;
0000ÅК1 = 1010; К1 = 1010;
1111ÅК1 = 1001; К1 = 0110;
1111ÅК1 = 0101; К1 = 1010;
2. Пара (0000000000000010, 0000000011111101):
Для Блока 1 данную пару рассматривать нет необходимости, так как первые четыре бита Е(Х) и Е(Х1) будут аналогичны тем же битам предыдущей пары, а следовательно дадут такой же результат.
3. Пара (0000000000011010,0000000011100101):
Аналогично пункту 1 определяем:
0100ÅК1 даст на выходе 011;
1011ÅК1 даст на выходе 110;
Из таблицы 4.2 определяем, что на выходе Блока 1 значение 011 получается в том случае, когда на его вход подается одно из значений 0011 или 1110, а значение 110 – при входных 0001 или 1100. Исходя из этого имеем следующие возможные варианты:
0100ÅК1 = 0011; К1 = 0111;
0100ÅК1 = 1110; К1 = 1010;
1011ÅК1 = 0001; К1 = 1010;
1011ÅК1 = 1100; К1 = 0111;
Вывод: даже проанализировав две пары открытых текстов, мы видим, что один из подключей, а именно К1 = 1010, встречается чаще остальных. Таким образом, можно предположить, что это и есть первый подключ.
Для Блока 2:
1. Пара (0000000000000001, 0000000011111110):
Так как на вход блока поступает значение Е(Х) Å Кi, то имеем следующую картину:
0100ÅК2 даст на выходе 010;
1011ÅК2 даст на выходе 101;
Из таблицы 4.2 определяем, что на выходе Блока 2 значение 010 получается в том случае, когда на его вход подается одно из значений 1110 или 0011, а значение 101 – при входных 0001 или 1100. Исходя из этого имеем следующие возможные варианты:
0100ÅК2 = 1110; К2 = 1010;
0100ÅК2 = 0011; К2 = 0111;
1011ÅК2 = 0001; К2 = 1010;
1011ÅК2 = 1100; К2 = 0111;
2. Пара (0000000000000010, 0000000011111101):
0001ÅК2 даст на выходе 011;
1110ÅК2 даст на выходе 100;
Из таблицы 4.2 определяем, что на выходе Блока 2 значение 011 получается в том случае, когда на его вход подается одно из значений 0000 или 1011, а значение 100 – при входных 0100 или 1000. Исходя из этого имеем следующие возможные варианты:
0001ÅК2 = 0000; К2 = 0001;
0001ÅК2 = 1011; К2 = 1010;
1110ÅК2 = 0100; К2 = 1010;
1110ÅК2 = 1000; К2 = 0110;
3.Пара (0000000000011010, 0000000011100101):
Аналогично пункту 1 определяем:
0011ÅК2 даст на выходе 110;
1100ÅК2 даст на выходе 001;
Из таблицы 4.2 определяем, что на выходе Блока 2 значение 110 получается в том случае, когда на его вход подается одно из значений 0101 или 1001, а значение 001 – при входных 0110 или 1010. Исходя из этого имеем следующие возможные варианты:
0011ÅК2 = 0101; К2 = 0110;
0011ÅК2 = 1001; К2 = 1010;
1100ÅК2 = 0110; К2 = 1010;
1100ÅК2 = 1010; К2 = 0110;
Вывод: проанализировав три пары открытых текстов, мы видим, что один из подключей, а именно К2 = 1010, встречается чаще остальных. Таким образом, можно предположить, что это и есть второй подключ.
Для Блока 3:
1. Пара (0000000000000001, 0000000011111110):
Так как на вход блока поступает значение Е(Х) Å Кi, то имеем следующую картину:
0100ÅК3 даст на выходе 11;
1011ÅК3 даст на выходе 10;
Из таблицы 4.2 определяем, что на выходе Блока 3 значение 11 получается в том случае, когда на его вход подается одно из 5 значений: 0010 или 0101 или 1000 или 1011 или 1110, а значение 10 – при входных 0000 или 0011 или 0110 или 1001 или 1100. Исходя из этого имеем следующие возможные варианты:
0100ÅК3 = 0010; К3 = 0110;
0100ÅК3 = 0101; К3 = 0001;
0100ÅК3 = 1000; К3 = 1100;
0100ÅК3 = 1011; К3 = 1111;
0100ÅК3 = 1110; К3 = 1010;
1011ÅК3 = 0000; К3 = 1010;
1011ÅК3 = 0011; К3 = 1111;
1011ÅК3 = 0110; К3 = 1100;
1011ÅК3 = 1001; К3 = 0001;
1011ÅК3 = 1100; К3 = 0110;
2. Пара (0000000000000010, 0000000011111101):
0000ÅК3 даст на выходе 10;
1111ÅК3 даст на выходе 11;
Из таблицы 4.2 определяем, что на выходе Блока 3 значение 10 получается в том случае, когда на его вход подается одно из 5 значений: 0001 или 0100 или 0111 или 1010 или 1101, а значение 11 – при входных 0010 или 0101 или 1000 или 1011 или 1110. Исходя из этого имеем следующие возможные варианты:
0000ÅК3 = 0001; К3 = 0001;
0000ÅК3 = 0100; К3 = 0100;
0000ÅК3 = 0111; К3 = 0111;
0000ÅК3 = 1010; К3 = 1010;
0000ÅК3 = 1101; К3 = 1101;
1111ÅК3 = 0010; К3 = 1101;
1111ÅК3 = 0101; К3 = 1010;
1111ÅК3 = 1000; К3 = 0111;
1111ÅК3 = 1011; К3 = 0100;
1111ÅК3 = 1110; К3 = 0001;
3.Пара (0000000000011010, 00000000011100101):
0001ÅК3 даст на выходе 11;
1110ÅК3 даст на выходе 10;
Из таблицы 4.2 определяем, что на выходе Блока 3 значение 11 получается в том случае, когда на его вход подается одно из 5 значений: 0010 или 0101 или 1000 или 1011 или 1110, а значение 10 – при входных 0001 или 0100 или 0111 или 1010 или 1101. Исходя из этого имеем следующие возможные варианты:
0001ÅК3 = 0010; К3 = 0011;
0001ÅК3 = 0101; К3 = 0100;
0001ÅК3 = 1000; К3 = 1001;
0001ÅК3 = 1011; К3 = 1010;
0001ÅК3 = 1110; К3 = 1111;
1110ÅК3 = 0001; К3 = 1111;
1110ÅК3 = 0100; К3 = 1010;
1110ÅК3 = 0111; К3 = 1001;
1110ÅК3 = 1010; К3 = 0100;
1110ÅК3 = 1101; К3 = 0011;
Вывод: проанализировав три пары открытых текстов, мы видим, что один из подключей, а именно К3 = 1010, встречается чаще остальных. Таким образом, можно предположить, что это и есть третий подключ.
Объединив результаты анализа, получим искомый ключ К = 101010101010. Экспериментальным путем можно убедиться, что при зашифровании данных пар открытых текстов применялся именно этот ключ.
