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