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



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

Двухраундовый DES. В двухраундовом DES, выходной элемент y равен (L2, 
R2), где
L1 = R0
R1 = L0 ⊕ f1(R0)
L2 = R1 = L0 ⊕ f1(R0)
R2 = L1 ⊕ f2(R1).
L0, R0, L2 и R2 известны из полученной входной/выходной пары (x, y), и, таким 
образом, мы также знаем L1 = R0 и R1 = L2. Это означает, что мы знаем вхоной/
выходной элементы и f1, и f2, и поэтому тот же самый метод , который был ис-
пользован для атаки на однораундовый DES, может быть использован здесь для 
определения как k1, так и k2 за время приблизительно 2 • 216. Данная атака рабо-
тает, даже если k1 и k2 являются полностью независимыми ключами, хотя, фак-
тически, расписание смены ключей DES подтверждает, что многие из битов k1 и 
k2 равны (что можно использовать для ускорения атаки в дальнейшем).


238
Трехраундовый DES. Согласно Рисуноку 6.5, выходное значение y теперь 
равняется (L3, R3). Поскольку L1 = R0 и R2 = L3, есдинственными неизвестны-
ми значениями на рисунке остаются R1 и L2 (которые равны).
Теперь у нас уже больше нет входной/выходной пары для любой раундовой 
функции fi. Например, выходное значение f2 равняется L1 ⊕ R2, где оба этих 
значения равны. Однако, мы не знаем значения R1, которое является входным 
элементом f2. Аналогично, мы можем определить входные элементы f1 и f3 , 
но не выходные элементы этих функций. Таким образом, атака, которую мы ис-
пользовали, чтобы взломать однораундовый DES, здесь не сработает.
Вместо того, чтобы надеяться на знания о входных и выходных элементах одной из 
раундовых функций, мы используем знания об определенном отношении между вход-
ными и выходными данными f1 и f3. Обратите внимание, что выходной элемент f1
равен L0 ⊕R1 = L0 ⊕ L2, а выходной элемент f3 равен L2 ⊕ R3. Следовательно, f1(R0) 

f3(R2) = (L0 ⊕L2) ⊕ (L2 ⊕ R3) = L0 ⊕ R3, где известны и L0, и R3. То есть XOR вы-
ходных данных f1 и f3 известен. Более того, входной элемент в f1 - это R0 , а входной 
элемент в f3 - это L3, оба они известны. Подытоживая, можно сказать, что мы можем 
определить входные данные в f1 и f3, а также XOR их выходных данных. Сейчас мы 
опишем атаку, которая находит секретный ключ на основе данной информации.
Вспомним, что расписание смены ключей DES имеет такое свойство, что 
мастер-ключ делится на «левую половину», которую мы обозначили как kL, 
и «правую половину» kR, каждая из которых содержит 28 бит. Более того, 24 
самых левых бита подключа, используемых в каждом раунде берутся только 
из kL, а 24 самых правых бита каждого подключа берутся из kR. Это означает, 
что kL влияет толко на входные данные в первые четыре S-блока в раунде, в то 
время как kR влияет только на входные данные в последние четыре S-блока. 
Поскольку смешивающая перестановка известна, мы также знаем, какие биты 
выходного элемента каждой раундовой функции выходят из каждого S-блока.
Идея, что кроется в атаке, - это по-отдельности пересечь пространство ключей 
за каждой половиной мастер-ключа, осуществляя атаку со сложностью прибли-
зительно 2 • 228 , а не 256. Такая атака будет возможна, если мы сможем про-
верить догадку о половине мастер-ключа, и мы сейчас покажем, как это можно 
сделать. Скажем, мы угадали какое-то значение для kL, левую половину мастер-
ключа. Мы знаем входной элемент R0 функции f1, и поэтому используя угады-
вание kL , мы можем вычислить входной элемент в первые четыре S-блока. Это 
означает, что мы можем вычислить половину выходных битов f1 (смешивающая 
перестановка распространяет биты, которые мы знаем, но поскольку смешиваю-
щая перестановка известна, мы знаем точно, какие это биты). Аналогичным об-
разом мы можем вычислить одинаковые расположения в выходном элементу f3 
, используя известный входной элемент L3 в f3 , а также ту же догадку для kL. 


239
Наконец, мы можем вычислить XOR этих выходных значений и проверить, со-
впадают ли соответствующие биты, в известном значении XOR выходных дан-
ных f1 и f3. Если они не равны, тогда наша догадка для kL является некорректной 
. Корректная догадка для kL будет всегда проходит этот тест, и поэтому не будет 
исключена, но некорректная догадка ожидаемо пройдет этот тест только с вероят-
ностью приблизительно 2−16 (поскольку мы проверяем равенство 16 бит в двух 
вычисленных значениях). Существует 228 возможных значений для kL, поэтому 
если каждое некорректное значение остается жизнеспособным возможным зна-
чением с вероятностью2−16 , тогда мы ожидаемо отанемся с только лишь 228 • 
2−16 = 212 вариантов для kL после вышеописанного.
Выполняя вышеописанное для каждой половины мастер-ключа, мы получим за 
время 2 • 228 приблизительно 212 возможных значений для левой половины и 212 
возможных значений для правой половины. Поскольку каждая комбинация левой и 
правой половин возможна, у нас есть 224 возможных ключей, и мы можем запустить 
перебор с использованием «грубой силы» по этому множеству, используя дополни-
тельную входную/выходную пару (xr , yr). (Альтернативный подход, который более 
эффективный, - это просто повторить предыдущую атаку, используя 212 оставшихся 
возможных значений для каждой половины ключа.) Временная сложность атаки со-
ставляет приблизительно 2 • 228 + 224 < 230, что намного меньше, чем 256.


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




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

    Басты бет