Общие сведения о линейном криптоанализе

Линейный анализ базируется на знании криптоаналитиком открытого и зашифрованного текста при использовании блочных схем шифрования, таких как DES. Одним из первых, кто вплотную занялся данным видом криптоанализа, был М. Матсуи. В связи с тем, что алгоритм шифрования DES является открытым, то есть заранее известны все его таблицы перестановок и замен, то Матсуи и взял его для криптоанализа. Как видно из таблицы 5.1 линейный криптоанализ Матсуи алгоритма DES требует значительного числа открытых текстов.

Таблица 5.1

Линейный криптоанализ основывается на том, что существует возможность заменить нелинейную функцию ее линейным аналогом. Так как все зашифровываемые тексты представлены в двоичном виде, то будем рассматривать случайную величину S – {0,1}, для которой Р(S=1) = р, соответственно Р(S=0) = 1-р, а D( S) = |1-2р|.

Рассмотрим схему произвольного блочного шифра в i-м цикле:

Y(i) = Е(X(i),K(i)). (5.1)

Здесь Е – функция шифрования, Х(i) – блок открытого текста в i-м цикле, Y(i) – блок шифртекста, K(i) – подключ, используемый в i-м цикле. Y(i), X(i)ÎV_n, K(i)ÎV_m, где V – двоичный вектор, n – размер блока, m – размер подключа.

Обозначим через (Х,a) = Х₁a₁ Å…Å Х_na_n = Х_i1 Å…Å Х_ik = X[i₁,…,i_k] – скалярное произведение двух двоичных векторов Х и a, где (a_i1,…, a_ik) единичные координаты вектора a, а по сути дела сложение по модулю 2 битов вектора Х, соответствующих ненулевым битам вектора a.

Линейным статистическим аналогом нелинейной функции (5.1) называется случайная величина

S_(i) = (Y_(i), a_(i))Å(X_(i), b_(i))Å(K_(i), c_(i)), (5.2)

если вероятность P(S_(i) = 1) = р ¹ ½ для случайно выбранного открытого текста Х_(i).

Отклонение D(S_(i)) = |1-2р| определяет эффективность линейного статистического аналога (5.2).

Для применения линейного криптоанализа необходимо решить следующие задачи:

1. Нахождение эффективного статистического линейного аналога и вычисление его вероятности;

2. Определение ключа (или некоторых битов ключа) с использованием эффективного линейного статистического аналога.