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.
Достарыңызбен бөлісу: