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


Глава 5 Хэш-функции и их применения



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

Глава 5
Хэш-функции и их применения 
В этой главе мы представим криптографические хэш-функции и изучим некоторые 
их применения. На более базовом уровне хэш-функция обеспечивает способ преоб-
разования длинной входной строки в более короткую выходную строку, иногда име-
нуемую дайджест. Первоначальным требованием является предотвращение колли-
зий или двух входных данных, преобразующихся в один и тот же дайджест. Стойкая 
к коллизиям хэш-функция обладает множеством применений. Одним из примеров, 
который мы увидим здесь, будет другой подход, стандартизированный как HMAC, 
для достижения расширения области для кодов аутентификации сообщений. 
Помимо этого, хэш-функции стали повсеместно использоваться в криптографии, 
особенно в случаях, когда требуются свойства, намного более сильные, чем стой-
кость к коллизиям. Стало довольно обыденным явлением моделировать крипто-
графические хэш-функции как «абсолютно непредсказуемые» (другими словами 
случайные оракулы), и мы обсудим данную концепцию, а также противоречия, ко-
торые ее окружают, более подробно далее в этой главе. Мы здесь затронем только 
некоторые из применений модели со случайными оракулами, но столкнемся с нею 
вновь, когда мы перейдем к условиям криптосистемы с открытым ключом.
Хэш-функции интересны тем, что их можно рассматривать как будто они находят-
ся между средами криптосистем с закрытым и открытым ключом. С одной сторо-
ны, как мы видим в Главе 6, они (на практике) построены с использованием методов 
симметричного ключа, и много канонических применений хэш-функций находятся в 
условиях симметричных ключей. С теоретической точки зрения, однако, существова-
ние стойких к коллизиям хэш-функций оказывается представляет качественно более 
сильное условие, чем существование шифрования с открытым ключом).
5.1 Определения 
Хэш-функции являются простыми функциями, которые принимают входные 
данные определенной длины и сжимают их в короткие выходные данные фикси-
рованной длины. Классическое использование хэш-функций лежит в структурах 
данных, где они могут быть использованы для построения ханш-таблиц, обеспе-
чивающих время поиска O(1) при хранении набора элементов. В частности, если 
диапазон хэш-функции H имеет размер N , тогда элемент x хранится в строке H(x) 
таблицы размером N . Чтобы извлечь x, ей достаточно вычислить H(x) и перебрать-
по той строке таблицы, где хранятся элементы. «Хорошая» хэш-функция для этих 


169
целей такая, которая дает несколько коллизий, где коллизия - это пара отличающих-
ся элементов x и xr , для которых H(x) = H(xr); в этом случае мы также говорим, что 
x и xr сталкиваются. (Когда случается коллизия, два элемента оказываются храни-
мыми в одной и той же ячейке, квеличивая тем самым время поиска.)
Стойкие к коллизиям хэш-функции по сути идентичные. И снова же, их цель - пре-
дотвратить коллизии. Однако, существуют фундаментальные различия. В первую 
очередь, желание минимизировать коллизии в условиях структур данных становится 
требованием предотвратить коллизий в условиях криптосистемы. Более того, в кон-
тексте структур данных мы можем предположить, что набор элементов данных под-
бирается независимо от хэш-функции и без какого-либо намерения вызвать коллизии. 
В контексте криптосистемы наоборот, мы сталкиваемся со злоумышленником, кото-
рый может выбирать элементы с явной целью вызвать коллизии. Это означает, что 
стойкие к коллизиям хэш-функции разработать намного сложнее.


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




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

    Басты бет