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



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

5.1.1 Стойкость к коллизиям 
Проще говоря, функция H является стойкой к коллизиям, если она недости-
жима для любого вероятностного полиномиально-временного алгоритма поис-
ка коллизий в H. Нас будут интересовать только те хэш-функции, чья область 
больше, чем их диапазон. В таком случае коллизии должны иметь место, но 
такие коллизии должно быть тяжело найти.
Проще говоря, мы рассмотрим ключевые хэш-функции. То есть H является функ-
цией с двумя входными параметрами, принимающая в качестве параметра ключ s и 
строкук x, и выводящая строку Hs(x) H(s, x). Требование состоит в том, что кол-
лизию в Hs должно быть тяжело найти из-за ключа s, сгенерированного случайным 
образом. Существуют по крайней мере два отличия между ключами в этом контексте 
и ключами, которые мы использовали до этого. Отличие первое в том, что не обяза-
тельно все строки соответствуют верным ключам (то есть Hs может не быть опреде-
лен для определенного s), и, таким образом, ключ s будет скорее всего сгенерирован 
алгоритмом Gen, чем будет подобран единообразно. Отличие второе, и, возможно, 
более важное, в том, что этот ключ s (как правило) не держится в секрете, и стойкость 
к коллизиям необходима даже если злоумышленник овладел s. Чтобы подчеркнуть 
это, мы будем использовать верхний индекс для ключа и писать Hs, а не Hs.
ОПРЕДЕЛЕНИЕ 5.1  Хэш-функция (с выходной длиной A) - это пара ве-
роятностных полиномиально-временных алгоритмов (Gen, H) , удовлетворяю-
щих следующие условия:
• Gen - это вероятностный алгоритм, который принимает в качестве вход-
ных данных параметр защиты 1n и выводит ключ s. Мы допускаем, что 1n 
подразумевается в s.
• H принимает в качестве входных данных ключ s и строку x  {0, 1}* и вы-


170
водит строку Hs(x)  {0, 1}A(n) (, где n - это значение параметра защиты, 
подразумеваемого в s).
Если Hs определяется только для входных данных x  {0, 1}A (n) и Ar(n) > A(n), 
тогда мы скажем, что (Gen, H) = это хэш-функция фиксированной длины для 
входных данных длиной Ar. В этом случае мы также назовем H функцией сжатия. 
В случае с фиксированной длиной нам необходимо, чтобы Ar была больше, чем 
A. Это будет означать, что функция сжала свои входные данные. В общем случае 
функция принимает в качестве входных данных строки произвольной длины. Та-
ким образом, она также осуществляет сжатия (хотья толкьо строк большей длины, 
чем A(n)). Обратите внимание, что без сжатия стойкость к коллизиям является три-
виальной (так как можно просто взять тождественную функцию Hs(x) = x). Теперь 
мы перейдем к определению защиты. Как правило, сначала мы определим экспе-
римент для хэш-функции Π = (Gen, H), злоумышленника A и параметра защиты n:


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




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

    Басты бет