Введение в современную криптографию


Атаки на DES с уменьшиным числом раундов



Pdf көрінісі
бет175/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   171   172   173   174   175   176   177   178   ...   249
Криптография Катц

Атаки на DES с уменьшиным числом раундов
Полезным упражнением для более углубленного понимания конструкции 
DES и ее безопасности будет наблюдение за поведением DES с всего несколь-
кими раундами. Мы покажем атаки на одно-, двух-, и трехраундовые варианты 
DES (напоминаем, что настоящий DES имеет 16 раундов). DES с тремя раунда-
ми или менее не может быть псевдослучайной функцией, потому что три раун-
да не достаточно для того, чтобы произошел лавинный эффект. Таким образом, 
мы заинтересованы в демонстрации более трудных (и вредящих) атак с вос-
становлением ключа, которые высчитывают ключ k, используя относительно 
маленькое количество входных/выходных пар, высчитаных с использованием 
ключа. Некоторые из атак похожи на те, что мы наблюдали в контексте подста-
новочных-перестановочных сетей; здесь, однако, мы увидим, как они применя-
ются к конкретному блочному шифру, а не к какой-то абстрактной конструкции.
Атаки ниже, будут атаками на основе открытого текста, в которых злоумыш-
ленник знает какие-то пары открытого текста/шифротекста {(xi, yi)} при yi = 
DESk (xi) для какого-то секретного ключа k. При описании атак мы будем ак-
центировать внимание на определенной входной/выходной паре (x, y) и предо-
ставим информацию о ключе, который злоумышленник может извлечь из этой 
пары. Продолжая использовать обозначения, разработанные ранее, мы обозна-
чим левую и правую половины входного элемента x как L0 и R0, соответсвенно, 


237
и пусть Li, Ri обозначают левую и правую половины после раунда i. Вспомним, 
что E обозначает функцию расширения DES, ki обозначает подключ, использу-
емый в раунде i, и fi(R) = fˆ(ki, R) обозначает собственно функцию, применяе-
мую в сети Фейстеля в раунде i.
Однораундовый DES. Скажем, у нас имеется входная/выходная пара (x, y). В 
однораундовом DES y = (L1, R1), где L1 = R0 и R1 = L0 ⊕ f1(R0). Мы, таким об-
разом, знаем входную/выходную пару для f1; в частности, мы знаем, что f1(R0) = 
R1 ⊕ L0. Путем применения обращения смешивающей перестановки к выходно-
му элементу R1 ⊕ L0 мы получим промежуточное значение, состоящее из выход-
ных данных со всех S-блоков, где первые 4 бита - это выходной элемент из перво-
го S-блока, следующие 4 бита - выходной элемент из второго S-блока и так далее.
Рассмотрим (известный) 4-битный выходной элемент из первого S-блока. По-
скольку каждый S-блок является функцией 4-к-1, это означает, что существуют 
ровно четыре возможных входных элемента в этот S-блок, которые превратятся 
в имеющийся выходной элемент, то же самое и с другими S-блоками; каждый 
такой входной элемент длиной 6 бит. Входной элемент в S-блоки - это просто 
XOR E(R0) с подключом k1. Поскольку R0 и, следовательно, E(R0) нам изве-
стен, мы можем вычислить набор из четырех воможных значений для каждой 
6-битной части k1. Это значит, что мы уменьшили число возможных ключей 
k1 с 248 до 448/6 = 48 = 216 (поскольку существуют 4 варианта для каждой из 
восьми 6-битных частей k1). Это уже небольшое число, и поэтому мы можем 
просто попробовать все варианты на другой входной/выходной паре (xr , yr) 
найти правильный ключ. Таким образом, мы получим ключ, используя только 
два известных открытых текста за время приблизительно 216.


Достарыңызбен бөлісу:
1   ...   171   172   173   174   175   176   177   178   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет