Модуль 2. Математичні основи криптографії 1

Лекция 3 Хэш-функции и аутентификация сообщений. Часть 1 1. Хэш-функции. Общие понятия. 2. Хэш-функции основных алгоритмов. MD5 2

1. Хэш-функции. Общие понятия. Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных. Хэш-код создается функцией Н: h = H (M) М - сообщение произвольной длины h - хэш-код фиксированной длины. 3

4 Требования к Хєш-функциям 1.Хэш-функция Н должна применяться к блоку данных любой длины. 2.Хэш-функция Н создает выход фиксированной длины. 3.Н (М) легко вычисляется для любого значения М. 4.Для любого значения хэш-кода h невозможно найти M такое, что Н (M) = h. 5.Для любого х невозможно найти y x, что H (y) = H(x). 6.Невозможно найти произвольную пару (х, y) такую, что H (y) = H (x). 1. Хэш-функции. Общие понятия.

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если для функции выполняется и шестое свойство, то такая функция называется сильной хэш-функцией Хэш-функции. Общие понятия.

6 Простые хэш-функции Алгоритм построения Входное значение (сообщение, файл и т.п.) рассматривается как последовательность n-битных блоков. Входное значение обрабатывается последовательно блок за блоком, и создается m-битное значение хэш-кода. 1. Хэш-функции. Общие понятия.

7 простейший пример - продольный избыточный контроль С i = b i1 b i2... b ik где С i - i-ый бит хэш-кода, 1 i n. k - число n-битных блоков входа. b ij - i-ый бит в j-ом блоке. - операция XOR. 1. Хэш-функции. Общие понятия. продольный избыточный контроль

8 1. Хэш-функции. Общие понятия. Дополнение - продольного избыточного контроля – ротационный XOR (RXOR) Установить n-битный хэш-код в ноль. Для каждого n-битного блока данных выполнить следующие операции: сдвинуть циклически текущий хэш-код влево на один бит; выполнить операцию XOR для очередного блока и хэш-кода.

9 Алгоритм получает на входе сообщение произвольной длины и создает в качестве выхода дайджест сообщения длиной 128 бит. 2. Хэш-функции основных алгоритмов. MD5

Шаг 1: добавление недостающих битов Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512. Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное Хэш-функции основных алгоритмов. MD5

Шаг 2: добавление длины 64-битное представление длины исходного сообщения в битах присоединяется к результату первого шага. Если первоначальная длина больше, чем 2 64, то используются только последние 64 бита Хэш-функции основных алгоритмов. MD5

Шаг 3: инициализация MD-буфера Буфер может быть представлен как четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются шестнадцатеричными числами: А = В = 89ABCDEF C = FEDCBA98 D = Хэш-функции основных алгоритмов. MD5

13 Шаг 4: обработка последовательности 512- битных (16-словных) блоков Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как HMD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую f F, f G, f H и f I соответственно 2. Хэш-функции основных алгоритмов. MD5

14 2. Хэш-функции основных алгоритмов. MD5

15 Шаг 5: выход После обработки всех L 512-битных блоков выходом L-ой стадии является 128- битный дайджест сообщения. 2. Хэш-функции основных алгоритмов. MD5

16 Логика цикла обработки 512-битного блока 2. Хэш-функции основных алгоритмов. MD5

17 B + CLS s (A + f (B, C, D) + X [k] + T [i]) Где A, B, C, D - четыре слова буфера; после выполнения шага - циклический сдвиг влево на одно слово. f - одна из элементарных функций f F, f G, f H, f I. CLS s - циклический сдвиг влево на s битов 32-битного аргумента. X [k] - M [q * 16 + k] - k-ое 32-битное слово в q-ом 512 блоке сообщения. T [i] - i-ое 32-битное слово в матрице Т. + - сложение по модулю Хэш-функции основных алгоритмов. MD5

18 Элементарные функции: f F = (B & C) (not B & D) f G = (B & D) V (C & not D) f H = B C D f I = C (B & not D) 2. Хэш-функции основных алгоритмов. MD5

19 2. Хэш-функции основных алгоритмов. MD5 Итог алгоритма MD5 MD 0 = IV MD q+1 = MD q + f I [Y q, f H [Y q, f G [Y q, f F [Y q, MD q ]]]] MD = MD L-1 Где IV - начальное значение буфера ABCD Y q - q-ый 512-битный блок сообщения L - число блоков в сообщении MD - окончательное значение дайджеста сообщения