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



Pdf көрінісі
бет185/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   181   182   183   184   185   186   187   188   ...   249
Криптография Катц

РИС. 6.9: Дифференциалы в нашем S-блоке.
Этот же процесс можно выполнить для всех 24 входных разностей ∆x , чтобы 
вычислить вероятность каждого дифференциала. А именно, для каждой пары 
(∆x, ∆y ) мы заносим в таблицу количество 4-битных входов x, для которых S(x) 

S(x ⊕ ∆x) = ∆y . Мы сделали это для S-блока нашего примера на рис. 6.9. (Для 
краткости мы представим (∆x, ∆y ), используя шестнадцатеричную запись). Та-
блицу нужно читать следующим образом: запись (i, j) подсчитывает, сколько 
входных данных с разностью i отображается в выходных данных с разностью 
j. Заметим, например, что имеется 8 входов с разностью 0xF = 1111, которая 
отображается на выходе 0xA = 1010, как мы показали выше. Это наиболее ве-
роятный дифференциал (за исключением тривиального дифференциала (0, 0)). 
Но существуют другие интересные дифференциалы: входная разность 0x4 = 
0100 отображается на выходной разности 0x6 = 0110 с вероятностью 6/16 = 3/8, 
и есть несколько дифференциалов с вероятностью 4/16 = 1/4.
РИС. 6.10: Дифференциалы трассировки через четыре раунда SPN, в которой 
используется S-блок и смешивающая перестановка, приведенная в тексте.


252
Теперь продолжим это, чтобы найти хороший дифференциал для первых 
трех раундов SPN. Рассмотрим оценку SPN на двух входах, которые имеют 
дифференциал 0000 1100 0000 0000, и проследим дифференциал между про-
межуточными значениями на каждом этапе этой оценки. (См. рис. 6.10, на кото-
ром показаны четыре полных раунда SPN плюс этап заключительного ключе-
вого смешивания. Для ясности, на рис. опущена смешивающая перестановка 
в 4-ом раунде; эта смешивающая перестановка влияет только на перетасовку 
битов дифференциала, и поэтому может быть легко учтена при атаке). Этап 
ключевого смешивания в первом раунде не влияет на дифференциал и поэтому 
входы для второго S-блока в первом раунде имеют дифференциал 1100. Из рис. 
6.9. видно, что разность 0xC = 1100 во входных данных для S-блока дает раз-
ность 0x8 = 1000 в выходных данных S-блока с вероятностью 1/4. Таким обра-
зом, с вероятностью 1/4 дифференциал в выходных данных 2-го S-блока после 
раунда 1 является одиночным битом, который при смешивающей перестановке 
перемещается с 5-ой позиции в 12-ю позицию. (Входные данные для других 
S-блоков равны, поэтому их выходные данные равны и дифференциалы на вы-
ходах равны 0000). Если предположить, что это так, то входная разность для 
третьего S-блока во втором раунде равна 0x1 = 0001 (опять же, этап ключевого 
смешивания во втором раунде не влияет на дифференциал); используя рис. 6.9, 
имеем, что с вероятностью 1/4 выходная разность от этого S-блока равна 0x4 = 
0100. Таким образом, опять же имеется только единственный выходной бит, 
который отличается, и он перемещается из 10-й позиции в первую позицию при 
смешивающей перестановке. И наконец, сверившись еще раз с рис. 6.9, видим, 
что входная разность 0x8 = 1000 для S-блока дает в результате выходную раз-
ность 0xF = 1111 с вероятностью 1/4. Биты в позициях 1, 2, 3 и 4 затем переме-
щаются при смешивающей перестановке в позиции 7, 2, 3 и 8.
В целом, мы далее видим, что входная разность ∆x = 0000 1100 0000 0000 дает 
выходную разность ∆y = 0110 0011 0000 0000 после трех раундов с вероятностью 
минимум 1/4•1/4 •1/4= 1/64•7 (Мы перемножаем вероятности, поскольку эври-
стически предполагаем независимость каждого раунда). Для случайной функци-
ивероятность того, что появляется любой данный дифференциал равна только 
2−16=1/65536. Таким образом, дифференциал, который мы нашли, появляется 
с вероятностью существенно выше, чем можно было бы ожидать для случайной 
функции. Заметим также, что мы нашли дифференциал с низким весом.
Мы можем использовать этот дифференциал, чтобы найти первые 8 битов 
итогового вспомогательного ключа k5. Как обсуждалось ранее, начнем, пред
___________________________________________________________
7 Это нижняя граница вероятности дифференциала, поскольку могут существовать другие 
разности в промежуточных значениях, которые приведут к той же разности в выходных данных.


253
ставляя, что {(xi , xi )}L является множеством L пар случайных входных данных с 
дифференицалом ∆x. Используя атаку подобранного открытого текста, мы затем по-
лучим значения yi = Fk (xi ) и yi = Fk (xi ) для всех i. Теперь, для всех возможных значе-
ний для начальных 8 битов k5 мы вычислим начальные 8 битов y˜i , y˜i промежуточ-
ные значения после этапа ключевого смешивания 4-го раунда. (Мы можем делать это 
потому, что нам нужно только инвертировать два крайних левых S-блока 4-го раунда, 
чтобы получить эти 8 битов). Если мы угадаем правильное значение для начальных 8 
битов k5, то мы можем ожидать, что 8-битный дифференциал 0110 0011 появляется с 
вероятностью минимум 1/64. Эвристически неправильный прогноз дает ожидаемый 
дифференциал только с вероятностью 2−8 = 1/256. При задании L достаточно боль-
шим, мы можем (с высокой вероятностью) определить правильное значение.


Достарыңызбен бөлісу:
1   ...   181   182   183   184   185   186   187   188   ...   249




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

    Басты бет