Введение в современную криптографию
Эксперимент по поиску коллизии Hash-collA,Π(n)
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 5.2
| Эксперимент по поиску коллизии Hash-collA,Π(n):
1. Ключ s генерируется действующим Gen(1n). 2. Злоумышленник A получил s и выводит x, xr . (If Π - это хэш- функция фиксированной длины для входных данных длиной Ar(n), затем на потребуется x, xr ∈ {0, 1}A (n).) 3. Вывод эксперимента определенно 1 , если и только если x ƒ= xr и Hs(x) = Hs(xr). В таком случае мы скажем, что A нашел коллизию. Определение стойкости к коллизиям подразумевает, что ни один умелый зло- умышленник не сможет найти коллизию в вышеописанном эксперименте, раз- ве что с пренебрежимо мало вероятностью. ОПРЕДЕЛЕНИЕ 5.2 Хэш-функция Π = (Gen, H) является стойкой к колли- зиям, если для вероятностных полиномиально-временных противников A суще- ствует пренебрежимо малая функция negl, такая, что Pr [Hash-collA,Π(n) = 1] ≤ negl(n). Для упрощения, мы иногда называем H или Hs как «стойкая к коллизиям хэш- функция», пусть технически мы должны говорить только, что и (Gen, H) тоже. Это не должно воодить в заблуждение. Криптографические хэш-функции разработаны с одной ясной целью - быть стойкими к коллизиям (помимо прочего). Мы обсудим некоторые реальные хэш-функции в Главе 6. В Разделе 8.4.2 мы увидим, насколько это возможно сконструировать хэш-функции с подтвержденными коллизиями на основании на предположении о сложности определенных теоретико-числовых проблем. Бесключевые хэш-функции. Криптографические хэш-функции, используемые на практике, в общем, имеют фиксированные выходные данные (также как и блоч- 171 ные шифры имеют фиксированную длину ключа) и, как правило, являются нелю- чевыми, что означает, что хэш-функция - это всего лишь фиксиров анная функция H : {0, 1}* → {0, 1}A. Это проблематично с теоретической точки зрения, так как для любой такой функции всегда существует постоянный алгоритм , который вы- водит коллизию H: алгоритм просто выводит сталкивающуюся пару (x, xr), жестко закодированную в сам алгоритм. Использование ключевых хэш-функций решает эту техническую проблему, так как невозможно жестко закодировать сталкиваю- щуюся пару для каждого возможного ключа, используя оправданное количества пространства (и в асимптотических условиях будет невозможно жестко закодиро- вать сталкивающиюся пару для каждого значения параметра защиты). Несмотря на вышесказанное, (бесключевые) криптографические хэш-функции, ис- пользуемые на практике, являются устойчивыми к коллизиям для всех практических целей, так как сталкивающиеся пары неизвестны (и их сложно найти вычислитель- но), даже если они на самом деле имеют место. Доказательство защиты какой-либо конструкции на основе стойкости к коллизиям хэш-функции имеет смысл, даже если используется неключевая хэш-функция H, так как доказательство показывает, что умелый злоумышленник, «ломающий» примитив, может быть использован для того, чтобы легко найти коллизию в H. (Все доказательства в этой книге отвечают этому ус- ловию.) В этом случае интерпретация доказательства защиты заключается в том, что, если противник может взломать схему на практике, он может быть использован и для того, чтобы найти коллизию на практике, а это, мы полагаем, не так просто сделать. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|