Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 5.1
| 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: жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|