Основные идеи линейного криптоанализа

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

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

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

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

Обозначим через (Х,a) = Х₁a₁ Å…Å Х_na_n = Х_i1 Å…Å Х_ik = X[i₁,…,i_k] – скалярное произведение двух двоичных векторов Х и a, где (a_i1,…, a_ik) единичные координаты вектора 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. Определение ключа (или некоторых бит ключа) с использованием эффективного линейного статистического аналога.