Введение в современную криптографию
Расширение области: Преобразование Меркле-Дамгорда
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- КОНСТРУКЦИЯ 5.3
| 5.2 Расширение области: Преобразование Меркле-Дамгорда
Конструирование хэш-функций зачастую начинается с разработки стой- кой к коллизиям функции сжатия, которая обрабатывает входные данные фиксированной длины, затем используется расширение области, чтобы обработать входные данные произвольной длины. В данном разделе мы покажем одно из решений проблемы расширения области. Мы вернемся к вопросу разработки стойкой к коллизиям функции сжатия в Разделе 6.3. Преобразование Меркле-Дамгорда является стандартным подходом для расширения функции сжатия до полноценной хэш-функции, которая при этом сохранила свойство стойкости к коллизиям. Он широко используется на практике для хэш-функций, включая семейства MD5 и SHA (см. Раздел 6.3). Существование этого преобразования означает, что при разработке стойких к коллизиям хэш-функций мы можем меньше уделять внимание дынным фиксированной длины. В свою очередь, это делает процесс разра- ботки стойких к коллизиям хэш-функции намного более простым. Преоб- разование Меркле-Дамгорда также представляет интерес с теоретической точки зрения, так как он подразумевает, что сжатие на один бит настолько же просто (или сложно), как и сжатие на произвольное количество. Для конкретности, предположим, что функция сжатия (Gen, h) сжима- ет входные данные в полтора раза; скажем, длина входных данных n , а длина выходных данных n. (Конструкция работает независимо от длины входных/выходных данных до тех пор, пока h сжимает.) Мы построили стойкую к коллизиям хэш-функцию (Gen, H), которая преобразовывает входные данные произвольной длины в выходные данные длиной n. (Gen остается неизменным.) Преобразование Меркле-Дамгорда определено в Конструкции 5.3 и изображено на Рисунке 5.1. Значение z0 , используемое в шаге 2 конструкции под названием вектор инициализации или IV явля- ется произвольным и может быть заменено любой константой. 173 КОНСТРУКЦИЯ 5.3 Пусть (Gen, h) будет хэш-функцией фиксированной длины для входных дан- ных длиной 2n и ывыходных данных длиной n. Постройте хэш-функцию (Gen, H) следующим образом: • Gen: остается неизменным. • H: при вводе ключа s и строки x ∈{0, 1}* длиной L < 2n, сделайте слудующее: 1. Установите B := [L/n] , (то есть количество блоков в x). Заполните x ну- лями, чтобы ее длина стала кратной n. Разберите дополненный результат как последовательность n-битных блоков x1, . . . , xB . Установите xB+1 := L, где L зашифрована как n-битная строка. 2. Установите z0 := 0n. (Это также называется IV.) 3. Для i = 1, . . . , B + 1 вычислите zi:= hs(zi−1||xi). 4. Выведите zB+1. Преобразование Меркле-Дамгорда. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|