Забезпечення цілісності інформації. Алгоритми хешування. Стандарт MD5.

Цілісність інформації - це здатність засобів обчислювальної техніки або автоматизованої системи забезпечувати незмінність інформації в умовах випадкового і (або) навмисного викривлення (руйнування). Існують різні методи забезпечення цілісності інформації, такі як механізм електронного цифрового підпису, метод контрольних сум, метод "циклічного контрольного коду", односпрямовані функції "хешування".

Алгоритм хешування - це алгоритм,який використовується для генерації хеш-кодів цифрових об'єктів, таких як повідомлення або ключі сеансів. Надійний алгоритм хешування володіє якістю, що зміна вхідних даних призведе до зміни всіх бітів в результуючому хеш-коді; хеш-коди корисні в сеансах для визначення факту модифікації великого цифрового об'єкта, такого як повідомлення. Прикладами алгоритмів хешування є MD2, MD4, MD5 і SHA-1.

MD5 — 128-бітний алгоритм хешування. Призначений для створення «відбитків» або «дайджестів» повідомлень довільної довжини. MD5 дозволяє отримувати відносно надійний ідентифікатор для блоку даних. Така властивість алгоритму широко застосовується в різних областях. Воно дозволяє шукати дублюючі файли на комп'ютері, порівнюючи MD5 файлів, а не їх вміст. MD5 також використовується для хешування паролів.

Логика MD5

Алгоритм берет в качестве входных данных сообщение произвольной длины и выдает на выходе 128-битовое значение профиля сообщения. Вводимые данные обрабатываются последовательно 512-битовыми блоками.

Шаг 1. Добавление битов заполнителя. Сообщение дополняется так, чтобы его общая длина в битах была сравнима со значением 448 по модулю 512 (т.е. длина = 448 512). Длина дополненного сообщения в битах долж­на быть на 64 меньше, чем ближайшее кратное целого числа 512. Операция дополнения выполняется всегда, даже если сообщение уже оказывает­ся требуемой длины. Структура битов заполнителя следующая: первый бит равен 1, а все ос­тальные равны 0.

Шаг 2. Добавление значения длины. К результату выполнения шага 1 до­бавляется 64-битовое значение длины в битах исходного сообщения (т.е сообщения, каким оно было перед добавлением заполнителя), причем наи­менее значимый байт записывается первым. Если длина исходного сооб­щения превосходит 2⁶⁴, то используются только младшие 64 бита значения длины. Таким образом, соответствующее поле будет содержать длину исходного сообщения по модулю 2⁶⁴.

В результате выполнения первых двух этапов получается сообщение, длина которого кратна 512 битам. Дополненное сообщение представлено как последовательность 512-битовых блоков так что в итоге длина сообщения оказывается равной 512 битов. Это значит также, что длина дополненного сообщения кратна длине блока из 16-ти 32-битовых слов. Пусть означает слова дополненного сооб­щения, тогда будет кратно числу 16. Таким образом, N.

Шаг 3. Инициализация буфера MD. Для того чтобы хранить промежуточ­ные и конечные результаты функции хэширования, используется 128-битовый буфер. Буфер можно представить в виде четырех 32-битовых ре­гистров (А, В, С, D). Эти регистры инициализируются следующими 32-битовыми целыми значениями (в шестнадцатеричном представлении).

А = 67452301,В = EFCDAB89,С = 98BADCFE,D = 10325476.

Эти значения сохраняются в формате прямого порядка записи байтов, ко­гда наименее значимый байт слова находится в позиции с младшим адре­сом. Как 32-битовые строки, значения инициализации (в шестнадцатеричной записи) будут иметь вид слово А: 01 23 45 67, слово В: 89 АВ CD EF, слово С: FE DC ВА 98, слово D: 76 54 32 10.

Шаг 4. Обработка сообщения 512-битовыми блоками (блоками по 16 слов). Сердцем алгоритма является функция сжатия, состоящая из четырех "раундов" обработки. Все четыре раунда имеют подобную структуру, но в каждом из них используется своя примитивная логическая функция (на рисунке соответствующие функции обозначены F, G, Н и I).

В каждом раунде на вход подается текущий 512-битовый блок () и 128-битовое значение буфера ABCD и, кроме того, обновляется содержимое буфера. В каждом раунде используется также четвертая часть 64-элементной таблицы , составленной из значений функции синуса.

Раунд	Примитивная функция g	g(b, c, d)
	F(b,с,d)	(b c) ( d)
	G(b,с,d)	(b d (с )
	H(b,с,d)	b с d
	I(b,с,d)	с (b )

Выходное значение четвертого раунда добавляется к входному значению первого раунда (), в результате чего получается . Сложение вы­полняется по модулю 2³² независимо для каждого из четырех слов буфера с соответствующими словами .

Шаг 5. Вывод. После обработки всех L 512-битовых блоков на выходе L -й стадии обработки получается 128-битовый профиль сообщения.

26. Забезпечення цілісності інформації. Алгоритми хешування. Стандарт SHA-1.
Цілісність інформації - це здатність засобів обчислювальної техніки або автоматизованої системи забезпечувати незмінність інформації в умовах випадкового і (або) навмисного викривлення (руйнування).

Існують різні методи забезпечення цілісності інформації, такі як механізм електронного цифрового підпису, метод контрольних сум, метод "циклічного контрольного коду", односпрямовані функції "хешування".

Алгоритм хешування - це алгоритм,який використовується для генерації хеш-кодів цифрових об'єктів, таких як повідомлення або ключі сеансів. Надійний алгоритм хешування володіє якістю, що зміна вхідних даних призведе до зміни всіх бітів в результуючому хеш-коді; хеш-коди корисні в сеансах для визначення факту модифікації великого цифрового об'єкта, такого як повідомлення. Більш того, якісний алгоритм хешування не дозволяє створити два незалежних набора вхідних даних, що мають однакові хеш-коди. Прикладами алгоритмів хешування є MD2, MD4, MD5 і SHA-1.

Secure Hash Algorithm 1 - алгоритм криптографічного хешування.

Для вхідного повідомлення довільної довжини алгоритм генерує 160-бітове хеш-значення, зване також дайджестом повідомлення. Використовується у багатьох криптографічних додатках і протоколах.

SHA-1 реалізує хеш-функцію, побудовану на ідеї функції стиснення. Входами функції стиснення є блок повідомлення довжиною 512 біт і вихід попереднього блоку повідомлення. Вихід є значення всіх хеш-блоків до цього моменту.

Ініціалізація
Вихідне повідомлення розбивається на блоки по 512 біт у кожному. Останній блок доповнюється до довжини, кратної 512 біт. Спочатку додається 1, а потім нулі, щоб довжина блоку стала рівною (512 - 64 = 448) біт. В останні 64 біта записується довжина вихідного повідомлення в бітах. Якщо останній блок має довжину більше 448, але менше 512 біт, доповнення виконується таким чином: спочатку додається 1, потім нулі аж до кінця 512-бітного блоку; після цього створюється ще один 512-бітний блок, який заповнюється аж до 448 біт нулями, після чого в решту 64 біта записується довжина вихідного повідомлення в бітах. Доповнення останнього блоку здійснюється завжди, навіть якщо повідомлення вже має потрібну довжину.

Головний цикл

Головний цикл обробляє кожен 512-бітний блок. Ітерація складається з чотирьох етапів по двадцять операцій в кожному. Блок повідомлення перетвориться з 16 32-бітових слів Mi у 80 32-бітових слів Wj за наступним правилом:

W_t = M_t при 0≤t≤15
W_t = (W_{t -3} W_{t -8} W_{t -14} W_{t -16}) << 1 при 16≤t≤79<< - це циклічний зсув вліво

для t от 0 до 79
temp = (a<<5) + F_t (b,c,d) + e + W_t + K_t e = d d = c c = b<<30 b = a a = temp

Після цього a, b, c, d, e додаються до A, B, C, D, E відповідно. Починається наступна ітерація.
Підсумковим значенням буде об'єднання п'яти 32-бітових слів в одне 160-бітове хеш-значення.

Хеш-функції використовуються в системах контролю версій, системах електронного підпису, а також для побудови кодів аутентифікації. SHA-1 є найбільш поширеним з усього сімейства SHA і застосовується в різних широко поширених криптографічні додатках і алгоритмах.