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