Введение в современную криптографию
Атаки на DES с уменьшиным числом раундов
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Однораундовый DES.
| Атаки на 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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|