Линейный криптоанализ основывается на том, что существует возможность заменить нелинейную функцию ее линейным аналогом. Так как все зашифровываемые тексты представлены в двоичном виде, то будем рассматривать случайную величину S – {0,1}, для которой Р(S=1) = р, соответственно Р(S=0) = 1-р, а D(S) = |1-2р|.
Рассмотрим схему произвольного блочного шифра в i-м цикле:
Здесь Е – функция шифрования, Х(i) – блок открытого текста в i-м цикле, Y(i) – блок шифртекста, K(i) – подключ, используемый в в i-м цикле. Y(i), X(i)ÎVn, K(i)ÎVm, где n – размер блока, m – размер подключа.
Y(i) = Е(X(i),K(i)). (1)
Обозначим через (Х,a) = Х1a1 Å…Å Хnan = Хi1 Å…Å Хik = X[i1,…,ik] – скалярное произведение двух двоичных векторов Х и a, где (ai1,…, aik) единичные координаты вектора a, а по сути дела сложение по модулю 2 битов вектора Х, соответствующих ненулевым битам вектора а.
Определение 1. Линейным статистическим аналогом нелинейной функции (1) будем называть случайную величину
S(i) = (Y(i), a(i))Å(X(i), b(i))Å(K(i), c(i)), (2)
если вероятность P(S(i) = 1) = р ¹ ½ для случайно выбранного открытого текста Х(i).
|
|
Отклонение D(S(i)) = |1-2р| определяет эффективность линейного статистического аналога (2).
Для применения линейного криптоанализа необходимо решить следующие задачи:
1. Нахождение эффективного статистического линейного аналога и вычисление его вероятности;
2. Определение ключа (или некоторых бит ключа) с использованием эффективного линейного статистического аналога.