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


Эксперимент по поиску коллизии Hash-collA,Π(n)



Pdf көрінісі
бет124/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   120   121   122   123   124   125   126   127   ...   249
Криптография Катц

Эксперимент по поиску коллизии 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. (Все доказательства в этой книге отвечают этому ус-
ловию.) В этом случае интерпретация доказательства защиты заключается в том, что, 
если противник может взломать схему на практике, он может быть использован и для 
того, чтобы найти коллизию на практике, а это, мы полагаем, не так просто сделать.


Достарыңызбен бөлісу:
1   ...   120   121   122   123   124   125   126   127   ...   249




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

    Басты бет