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

Лекция 4 Хэш-функции и аутентификация сообщений. Часть 2 1. Хэш-функции основных алгоритмов. SHA1 2. Коды аутентификации сообщений - МАС 2

1. Хэш-функции основных алгоритмов. SHA1 Безопасный хэш-алгоритм (Secure Hash Algorithm) был разработан национальным институтом стандартов и технологии (NIST) и опубликован в качестве феде- рального информационного стандарта (FIPS PUB 180) в 1993 году. SHA-1, как и MD5, основан на алгоритме MD4. 3

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

1. Хэш-функции основных алгоритмов. SHA1 Логика выполнения SHA-1 Шаг 1: добавление недостающих битов Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512. Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. (число добавляемых битов находится в диапазоне от 1 до 512). Добавление состоит из единицы, за которой следует необходимое количество нулей. 5

1. Хэш-функции основных алгоритмов. SHA1 Логика выполнения SHA-1 Шаг 2: добавление длины К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления. Результатом первых двух шагов является сообщение, длина которого кратна 512 битам. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y 0, Y 1,..., Y L-1, так что общая длина расширенного сообщения есть L * 512 бит. 6

1. Хэш-функции основных алгоритмов. SHA1 Логика выполнения SHA-1 Шаг 3: инициализация SHA-1 буфера Используется 160-битный буфер для хранения промежуточных и окончательных результатов хэш- функции. Буфер может быть представлен как пять 32- битных регистров A, B, C, D и E. Эти регистры инициализируются следующими шестнадцатеричными числами: A = B = EFCDAB89 C = 98BADCFE D = E = C3D2E1F0 7

1. Хэш-функции основных алгоритмов. SHA1 Логика выполнения SHA-1 Шаг 4: обработка сообщения в 512-битных (16- словных) блоках Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как H SHA. Все 80 циклических обработок имеют одинаковую структуру. 8

9

1. Хэш-функции основных алгоритмов. SHA1 10 t t t t Логика выполнения SHA-1 Каждый цикл получает на входе текущий 512-битный обрабатываемый блок Y q и 160-битное значение буфера ABCDE, и изменяет содержимое этого буфера. В каждом цикле используется дополнительная константа К t, которая принимает только четыре различных значения: 0 t 19 K t = 5A t 39 K t = 6ED9EBA1 40t 59 K t = 8F1BBCDC 60 t 79 K t = CA62C1D6 (целая часть числа [2 30 × 10 1/2 ])

1. Хэш-функции основных алгоритмов. SHA1 11 t t t t Логика выполнения SHA-1 Для получения SHA q+1 выход 80-го цикла складывается со значением SHA q. Сложение по модулю 2 32 выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHA q

1. Хэш-функции основных алгоритмов. SHA1 12 t t t t Логика выполнения SHA-1 Шаг 5: выход После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.

1. Хэш-функции основных алгоритмов. SHA1 13 t t t t Логика выполнения SHA-1 Каждый цикл можно представить в виде: A, B, C, D, E (CLS 5 (A) + f t (B, C, D) + E + W t + K t ), A, CLS 30 (B), C, D Где A, B, C, D, E - пять слов из буфера. t - номер цикла, 0 t 79. f t - элементарная логическая функция. CLS s - циклический левый сдвиг 32-битного аргумента на s битов. W t - 32-битное слово, полученное из текущего входного 512-битного блока. K t - дополнительная константа. + - сложение по модулю 2 32.

1. Хэш-функции основных алгоритмов. SHA1 14 t t t t Логика выполнения отдельного цикла

1. Хэш-функции основных алгоритмов. SHA1 15 t t t t Получение входных значений каждого цикла из очередного блока

1. Хэш-функции основных алгоритмов. SHA1 16 t t t t различия между алгоритмами MD5SHA1 Длина дайджеста128 бит160 бит Размер блока обработки 512 бит Число итераций64 (4 цикла по 16 итераций в каждом) 80 Число элементарных логических функций 43 Число дополнительных констант 644

1. Хэш-функции основных алгоритмов. SHA1 17 t t t t различия между алгоритмами Безопасность: дайджест SHA-1 на 32 бита длиннее, чем дайджест MD5. SHA-1 является более стойким алгоритмом. Скорость: SHA-1 выполняется приблизительно на 25% медленнее, чем MD5 на той же аппаратуре. Простота и компактность: оба алгоритма просты и в описании, и в реализации, не требуют больших программ или подстановочных таблиц.

2. Коды аутентификации сообщений - МАС 18 t t t t Под МАС (Message Authentication Code) понимается некоторый аутентификатор, являющийся определенным способом вычисленным блоком данных, с помощью которого можно проверить целостность сообщения.

2. Коды аутентификации сообщений - МАС 19 t t t t Функция вычисления МАС должна обладать следующими свойствами: MAC = C K (M) Должно быть вычислительно трудно, зная М и С K (M), найти сообщение М, такое, что С K (M) = С K (M). Значения С K (M) должны быть равномерно распределенными в том смысле, что для любых сообщений М и M вероятность того, что С K (M) = С K (M), должна быть равна 2 -n, где n - длина значения МАС.

2. Коды аутентификации сообщений - МАС 20 t t t t Функция вычисления МАС должна обладать следующими свойствами: MAC = C K (M) Должно быть вычислительно трудно, зная М и С K (M), найти сообщение М, такое, что С K (M) = С K (M). Значения С K (M) должны быть равномерно распределенными в том смысле, что для любых сообщений М и M вероятность того, что С K (M) = С K (M), должна быть равна 2 -n, где n - длина значения МАС.