Изучение современных методов криптоанализа. Бабенко Л.К - 22 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

22
Определение 1. Линейным статистическим аналогом нелинейной
функции (1) будем называть случайную величину
Q(i) = (Y(i), α(i))⊕(X(i), β(i))⊕(K(i), χ(i)), (2)
если вероятность P(Q(i) = 1) = р ≠ ½ для случайно выбранного откры-
того текста Х(i).
Отклонение ∆(Q(i)) = |1-2р| определяет эффективность линейного ста-
тистического аналога (2).
Для применения линейного криптоанализа необходимо решить сле-
дующие задачи:
1) нахождение эффективного статистического линейного аналога и
вы-
числение его вероятности;
2) определение ключа (или некоторых бит ключа) с использованием
эффективного линейного статистического аналога.
3.2.1. Нахождение статистических аналогов для 1 цикла алгоритма
DES
Наиболее эффективным является рассмотрение блока F алгоритма DES,
а именно находящиеся в нем S-блоки, так как именно в этом случае можно
явно проследить зависимость выходных битов от входных в
их всевозмож-
ных комбинациях. Один цикл DES преобразования изображен на рис. 1.4.
Нелинейная функция, реализующая а-й S блок алгоритма DES, может
быть записана в виде:
Y = F
a
(X⊕K), a = 1,…,8, (3)
Y ∈ V
4
, X,K ∈ V
6
.
Линейным статистическим аналогом каждого из всевозможных урав-
нений (3) будет являться уравнение вида:
(Y,j) = (X’,i), (4)
где X’ = X⊕K;
1 ≤ i ≤ 63;
1 ≤ j ≤ 15.
Обозначим через Q
a
(i, j), a = 1,…,8; i = 1,…63; j = 1,…15; число ненуле-
вых X ∈ V
6
для а-го S блока DES таких, что для i и j выполняется равенство
(4). В этом случае значение Q
a
(i, j) будет определять количество совпадений
суммы по модулю 2 некоторых битов входных данных с суммой по модулю
2 некоторых битов выходных данных. Так как сумма по модулю 2 двух оди-
наковых бит (1 и 1 или 0 и 0) в результате дает 0, то Q
a
(i, j) и будет по сути
дела указывать, сколько раз из возможных 64 комбинаций выполняется
формула (2) с результатом 0. Так как всего 64 возможных комбинации, то
при Q
a
(i, j)=32 будем иметь Р = (Q = 0) = 32/64 = 1/2, а Р(Q = 1) = 1 – ½ = ½.
Поэтому когда Q
a
≠ 32, можно сказать, что есть статистическая связь между
входными и выходными битами а-го S блока. При этом чем больше будет

Страницы