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


Расширение области: Преобразование Меркле-Дамгорда



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

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.
Преобразование Меркле-Дамгорда. 


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




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

    Басты бет