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



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

Двукратное шифрование
Пусть F будет блочным шифром с ключом длиной n- битов и длиной блока A-битов.
Тогда новый блочный шифр F r с ключом длиной 2n может быть определен согласно
где k1 and k2 – это независимые ключи. Для случая, когда F – это DES, мы полу-
чим шифр F r , называемый 2DES, для которого требуется 112-битный ключ, если 
полный поиск ключа был бы наилучшей доступной атакой, то ключ длиной 112 
битов был бы достаточным, поскольку атака, требующая времени 2112 совер-
шенно невозможна. К сожалению, мы сейчас выявим атаку на F r , которая прохо-
дит в течение приблизительно 2n, что существенно меньше времени 22n , которое, 
как можно было бы надеяться, необходимо для полного поиска для 2n-битного 
ключа. Это означает, что новый блочный шифр, по существу, не лучше старого, 
даже несмотря на то, что у него есть ключ, который в два раза длиннее.6
Эта атака называется «атакой встречи посередине» по причинам, которые 
скоро станут понятны. Скажем, оппонент получает отдельную входную/вы-
ходную пару (x, y), где y = F r* * (x) = Fk* (Fk* (x)) для неизвестного k* , k*.
Оппонент может сузить множество возможных ключей следующим образом:
1. Для каждого k1 ∈ {0, 1}n, вычисляем z := Fk (x) и сохраняем (z, k1) в списке L.
2. Для каждого k2 ∈ {0, 1}n, вычисляем z := F −1(y) и сохраняем (z, k2) в списке Lr.
______________________________________________________
6Это не совсем верно, поскольку атака простым последовательным перебором на F мо-
жет быть осуществлена за время 2n и с постоянным объемом памяти, тогда как атака на 
F r , которую мы показываем, требует 2n времени и 2n памяти. Тем не менее, эта атака 
показывает, что F r не достигает желаемого уровня безопасности.


243
3. Записи (z1, k1) ∈ L и (z2, k2) ∈ Lr совпадают, если z1 = z2. Для каждого 
такого совпадения добавьте (k1, k2) в множество S. (Совпадения можно легко 
обнаружить после сортировки L и Lr по их первым компонентам).
Графическое описание атаки см. на рис. 6.7.
Эта атака занимает времени O(n • 2n) и требует объема памяти O((n + A) • 2n). 
Вывод множества S по этому алгоритму содержит в точности те же значения 
(k1, k2), для которых
или, что то же самое, для которых y = F r (x). В частности, (k* , k*) ∈ S. С 
другой стороны, ожидается (эвристически), что пара (k1, k2) ƒ= (k* , k*) будет 
удовлетворять Выражение (6.4) с вероятностью 2−A , если рассматривать Fk (x) 
и F −1(y) как равномерные
РИС. 6.7: Атака встречи на середине.
Строки A-битов и, таким образом, ожидаемый размер S составляет 22n 
• 2−A = 22n−A . Используя несколько других входных/выходных пар и вы-
полнив пересечение множеств, которые получены, правильное (k* , k*) можно 
идентифицировать с очень высокой вероятностью.


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




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

    Басты бет