Введение в современную криптографию
Глава 5 Хэш-функции и их применения
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 5.1 Определения
| Глава 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 сталкиваются. (Когда случается коллизия, два элемента оказываются храни- мыми в одной и той же ячейке, квеличивая тем самым время поиска.) Стойкие к коллизиям хэш-функции по сути идентичные. И снова же, их цель - пре- дотвратить коллизии. Однако, существуют фундаментальные различия. В первую очередь, желание минимизировать коллизии в условиях структур данных становится требованием предотвратить коллизий в условиях криптосистемы. Более того, в кон- тексте структур данных мы можем предположить, что набор элементов данных под- бирается независимо от хэш-функции и без какого-либо намерения вызвать коллизии. В контексте криптосистемы наоборот, мы сталкиваемся со злоумышленником, кото- рый может выбирать элементы с явной целью вызвать коллизии. Это означает, что стойкие к коллизиям хэш-функции разработать намного сложнее. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|