Нахождение статистических аналогов для 1 цикла алгоритма DES

Наиболее эффективным является рассмотрение блока F алгоритма DES, а именно находящиеся в нем S-блоки, так как именно в этом случае можно явно проследить зависимость выходных битов от входных в их всевозможных комбинациях. Один цикл DES преобразования изображен на рис. 1.4.

Нелинейная функция, реализующая а -й S блок алгоритма DES, может быть записана в виде:

Y = F_a(XÅK), a = 1,…,8, (3)

Y Î V₄, X,K Î V₆.

Линейным статистическим аналогом каждого из всевозможных уравнений (3) будет являться уравнение вида:

(Y,j) = (X’,i), (4)

где X’ = XÅK;

1 £ i £ 63;

1 £ j £ 15.

Обозначим через S_a(i, j), a = 1,…,8; i = 1,…63; j = 1,…15; число ненулевых X Î V₆ для а -го S блока DES таких, что для i и j выполняется равенство (4). В этом случае значение S_a(i, j) будет определять количество совпадений суммы по модулю 2 некоторых битов входных данных с суммой по модулю 2 некоторых битов выходных данных. Так как сумма по модулю 2 двух одинаковых бит (1 и 1 или 0 и 0) в результате дает 0, то S_a(i, j) и будет по сути дела указывать, сколько раз из возможных 64 комбинаций выполняется формула (2) с результатом 0. Так как всего 64 возможных комбинации, то при S_a(i, j)=32 будем иметь Р = (S = 0) = 32/64 = 1/2, а Р(S = 1) = 1 – ½ = ½. Поэтому, когда S_a ¹ 32 можно сказать, что есть статистическая связь между входными и выходными битами а -го S блока. При этом чем больше будет отклонение значения вероятности для каждой пары (i, j), тем более эффективным будет линейный аналог.

Пусть S^*_a(i*, j*): | S^*_a(i*, j*) – 32| = max| S_a(i, j) – 32| (5)

1 £ i £ 63;

1 £ j £ 15.

Тогда уравнение

(X,i*) Å (Y,j*) = (К, i*) (6)

является эффективным линейным статистическим аналогом для а -го S блока в классе всех линейных статистических аналогов вида (4) с вероятностью:

Р_а = S^*_a(i*, j*)/64, а = 1,…,8.

Анализ всех восьми Sблоков показал, что наибольшее отклонение от ½ находится в S₅блоке. Чтобы все вышесказанное стало более понятным, проанализируем S₅блок алгоритма DES.

Шестибитовым входам в S₅блок однозначно соответствуют четырехбитовые выходы. Их значения можно определить с помощью известной таблицы замены, которая представляет собой таблицу из четырех строк и шестнадцати столбцов. По шести входным битам S блока определяется, под каким номером столбцов и строк следует искать выходное значение (см. таблицу 1.10).

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

В ходе анализа идет получение статистики совпадения суммы по модулю 2 некоторых входных бит и суммы по модулю 2 некоторых входных бит. При чем учитываются всевозможные комбинации. Результат анализа приведен в Приложении в таблице 2. В этой таблице значение S₅(i,j), имеющее наибольшее отклонение от ½, помечено *. Следовательно, S*₅(I*,j*) = 12, где i = (1,1,1,1), а j = (0,1,0,0,0,0). Это говорит о том, что из всех возможных входных значений (от 0 до 63) и соответствующих им выходных значений, 12 раз встречается совпадение второго входного бита и суммы по модулю 2 всех четырех выходных битов. Из таблицы 1, приведенной в приложении, следует, что данными 12 парами являются следующие:

1. 000010 – 1100 (0 = 1 Å 1 Å 0 Å 0);

2. 000111 – 1100 (0 = 1 Å 1 Å 0 Å 0);

3. 001010 – 1010 (0 = 1 Å 0 Å 1 Å 0);

4. 001110 – 0110 (0 = 0 Å 1 Å 1 Å 0);

5. 010000 – 1000 (1 = 1 Å 0 Å 0 Å 0);

6. 011000 – 1101 (1 = 1 Å 1 Å 0 Å 1);

7. 011100 – 1110 (1 = 1 Å 1 Å 1 Å 0);

8. 011101 – 1000 (1 = 1 Å 0 Å 0 Å 0);

9. 100101 – 1100 (0 = 1 Å 1 Å 0 Å 0);

10. 101000 – 1010 (0 = 1 Å 0 Å 1 Å 0);

11. 111011 – 0100 (1 = 0 Å 1 Å 0 Å 0);

12. 111110 – 1110 (1 = 1 Å 1 Å 1 Å 0).

Отсюда эффективным линейным статистическим аналогом S₅ блока является уравнение:

X₂ Å Y₁ Å Y₂Å Y₃ Å Y₄ = K_2,(7)

и это уравнение выполняется с вероятностью р = 3/16.

Уравнения для эффективных линейных статистических аналогов всех S блоков приведены в таблице 3.2. Здесь X = (x₁, …, x₆), Y = (y₁, …, y₄), K = (k₁, …, k₆) – входные, выходные и ключевые вектора соответственно.

Таблица 3.2

№ S блока	Эффективное линейное уравнение	Р	D = \|1 – 2р\|
	X₂ Å Y₁ Å Y₂ Å Y₃ Å Y₄ = K₂	7/32	9/16
	X₁ Å X₅Å Y₁Å Y₃ Å Y₄ = K₁ Å K₅	1/4	½
	X₁ Å X₅ Å Y₁Å Y₂ Å Y₃ Å Y₄ = K₁ Å K₅	1/4	½
	X₁ Å X₅ Å Y₁ Å Y₂ Å Y₃ Å Y₄ = K₁ Å K₅ X₁ Å X₃ Å Y₁ Å Y₂ Å Y₃ Å Y₄ = K₁ Å K₃ X₁Å X₃ Å X₅ Å X₆ Å Y₂ Å Y₃= K₁ Å K₃ Å K₅Å K₆ X₁ Å X₃ Å X₅ Å X₆ Å Y₁ Å Y₄ = K₁ Å K₃ Å K₅ Å K₆	1/4 1/4 1/4 1/4	½ ½ ½ ½
	X₂ Å Y₁ Å Y₂Å Y₃ Å Y₄ = K₂	3/16	5/8
	X₂ Å Y₂ Å Y₃ Å Y₄ = K₂ X₁ Å X₅ Å Y₁ Å Y₃ Å Y₄ = K₁ Å K₅	9/32	7/16
	X₁ Å X₂ Å X₃Å X₅ Å X₆ Å Y₂ = K₁ Å K₂ Å K₃ Å K₅ Å K₆	7/32	9/16
	X₂ Å Y₁ Å Y₂ Å Y₃ Å Y₄ = K₂ X₁ Å X₅ Å Y₁ Å Y₂ Å Y₃ = K₁ Å K₅	1/4	½

Так как в рассматриваемом нами S₅ блоке в уравнении участвует второй бит, то легко можно посчитать, что этот бит на самом деле будет 26 битом всего входного сообщения Х. Однако, зная, что при входе в F блок, входной вектор претерпевает изменения с помощью перестановки с расширением, то, воспользовавшись приведенной ниже таблицей, легко можно определить, что на 26 позиции будет находиться на самом деле 17 входной бит (см. таблицу 3.3).

Таблица 3.3

DES – перестановка с расширением.

Точно так же выходной вектор, прежде чем выйти из F блока претерпевает перестановку с помощью Р-блока. Поэтому выходящие из S₅ блока 17, 18, 19 и 20 биты соответственно окажутся на 2, 8, 24 и 14 позиции выходного вектора (таблица 3.4).

Таблица 3.4

DES – перестановка с помощью Р-блока.