171
ные шифры имеют фиксированную длину ключа) и, как правило, являются нелю-
чевыми, что означает, что хэш-функция - это всего лишь фиксиров анная функция
H : {0, 1}* → {0, 1}A. Это проблематично с теоретической точки зрения, так как
для любой такой функции всегда существует постоянный алгоритм , который вы-
водит коллизию H: алгоритм просто выводит сталкивающуюся пару (x, xr), жестко
закодированную в сам алгоритм. Использование ключевых хэш-функций решает
эту техническую проблему, так как невозможно жестко закодировать сталкиваю-
щуюся пару для каждого возможного ключа, используя оправданное количества
пространства (и в асимптотических условиях будет невозможно жестко закодиро-
вать сталкивающиюся пару для каждого значения параметра защиты).
Несмотря на вышесказанное, (бесключевые) криптографические хэш-функции, ис-
пользуемые на практике, являются устойчивыми к коллизиям для всех практических
целей, так как сталкивающиеся пары неизвестны (и их сложно найти вычислитель-
но), даже если они на самом деле имеют место. Доказательство защиты какой-либо
конструкции на основе стойкости к коллизиям хэш-функции имеет смысл, даже если
используется неключевая хэш-функция H, так как доказательство показывает, что
умелый злоумышленник, «ломающий» примитив, может быть использован для того,
чтобы легко найти коллизию в H. (Все доказательства в этой книге отвечают этому ус-
ловию.) В этом случае интерпретация доказательства защиты заключается в том, что,
если противник может взломать схему на практике, он может быть использован и для
того, чтобы
найти коллизию на практике, а это, мы полагаем, не так просто сделать.
Достарыңызбен бөлісу: