Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”

Кафедра ЕОМ
Обчислення хеш-функції за алгоритмом MD5
Методичні вказівкидо лабораторної роботи № 1
з курсу “Проектування засобів захисту інформації в комп’ютерних мережах” для студентів напрямків 7.091501, 8.091501 “Комп’ютерні системи та мережі”
8.091502 “Системне програмне забезпечення”
8.091503 “Спеціалізовані комп’ютерні системи”
Затвердженона засіданні кафедриЕлектронних Обчислювальних МашинПротокол №  від 2006 року
Львів – 2006
Алгоритм обчислення хеш-функції MD5: Методичні вказівки до лабораторної роботи з курсу „Проектування засобів захисту інформації” для студентів напрямків 7.091501, 8.091501 “Комп’ютерні системи та мережі”, 8.091502 “Системне програмне забезпечення”, 8.091503 “Спеціалізовані комп’ютерні системи” / Укладачі: В.М. Грига, В.М. Сокіл – Львів: Національний університет “Львівська політехніка”, 2006, 11 с.
Укладачі: В.М. Грига, асистент кафедри ЕОМ
В.М. Сокіл, асистент кафедри ЕОМ

Відповідальний за випуск: В.Т. Кремінь, к.т.н., доц. кафедри ЕОМ
Рецензенти: ВА. Голембо, к.т.н., доц. кафедри ЕОМ.
Ю.В. Морозов, к.т.н., доц. кафедри ЕОМ.

1 Мета роботи
Мета роботи: реалізувати демонстраційну програму обчислення значення сигнатури вхідного повідомлення за алгоритмом MD5.
2 Очікуваний результат роботи
В ході роботи необхідно засвоїти основні принципи побудови алгоритмів обчислення сигнатури повідомлень, розробити демонстраційну програму обчислення значення сигнатури вхідного повідомлення за алгоритмом MD5.
3 Теоретичні відомості
Алгоритм MD5 (Message Digest) – це алгоритм хешування, розроблений професором Рональдом Л.Рівестом з Массачусетського технологічного інституту (МТІ) в 1992 році.
В якості вхідних даних береться повідомлення (потік даних) довільної довжини, і обчислюється 128 – розрядний хеш-код (сигнатура, дайджест). Припускається, що не існує двох повідомлень, які мають однакові сигнатури, або не можливо створити повідомлення з наперед заданою сигнатурою. Цей алгоритм застосовується в криптографії при формуванні цифрових підписів та генерації ключів шифрування. По суті, алгоритм хешування MD5 – це спосіб перевірки цілісності даних, набагато надійніший ніж контрольна сума або інші методи.
Алгоритм під час розробки був оптимізований для 32 – розрядних систем і не потребує великих об’ємів пам’яті. MD5 є дещо повільніший, ніж MD4, але більш стійкий до криптографічних атак.
Опис алгоритму
Перед тим, як розглянути детально сам алгоритм, визначимо основні терміни та поняття, що ним використовуються. Під терміном “слово” будемо розуміти кількість інформації, яка представлена 32-ома розрядами (бітами), а під терміном “байт” – 8 розрядів (біт). Послідовність біт як послідовність байт, де кожна група із 8 – ми розрядів є окремим байтом, причому старший розряд байта іде першим. Аналогічно представляється послідовність байт, тільки молодший байт іде першим.
В якості вхідного потоку будемо мати потік даних розрядів. - невід’ємне ціле число (можливо 0), не обов’язково кратне 8.
На рис. 1 зображена схема логіки виконання MD5.

Рис. 1. Логіка виконання MD5.
Для обчислення MD5 хеш - функції необхідно виконати наступні 5 кроків:
Крок 1: Вирівнювання потоку
Повідомлення доповнюється таким чином, щоб його довжина була рівною 448 по модулю 512 (довжина = 448 mod 512). Це означає, що довжина доданого повідомлення на 64 розряди меньша ніж число кратне 512. Додавання розрядів проводиться завжди, навіть тоді, коли повідомлення має потрібну довжину. Наприклад, якщо довжина повідомлення 448 розрядів, то воно доповнюється 512 розрядами до 960 розрядів. Отже число доданих розрядів знаходиться в межах від 1 до 512. Вирівнювання відбувається наступним чином: потік доповнюється одним бітом ‘1’, а за ним біти ‘0’ до тих пір, поки довжина потоку не буде рівною 448 по модулю 512.
Крок 2: Додавання довжини
64 – розрядне представлення довжини вихідного (до добавлення) повідомлення в бітах приєднується до результату першого кроку. Якщо початкова довжина більша ніж , то використовуються молодші 64 розряди. Іншими словами поле містить довжину вихідного повідомлення по модулю .
В результаті перших двох кроків утворюється повідомлення, довжина якого кратна 512 розрядам. Це розширене повідомлення представляється, як послідовність 512 – бітних блоків , при цьому загальна довжина розширеного повідомлення рівна розрядам. Таким чином довжина отриманого розширеного повідомлення кратна шістнадцяти 32 – бітним словам.

Рис. 2. Структура розширеного повідомлення.
Крок 3: Ініціалізація MD-буфера
Для збереження проміжних і кінцевих результатів хеш-функції використовується 128-розрядний буфер. Він представляється, як чотири 32 – розрядні регістри (). В якості ініціалізуючих значень використовуються наступні шістнадцяткові числа:

Крок 4: Обробка послідовності 512 – розрядних (по 16 слів) блоків
Основою алгоритму є блок, який складається із чотирьох циклів. Він позначається як
. Чотири цикли мають подібну структуру, але для кожного циклу застосовується
своя елементарна логічна функція і відповідно.

Рис. 3. Обробка чергового 512-розрядного блоку.
Кожний цикл отримує в якості вхідних даних поточний 512 – розрядний блок та 128 – розрядне значення буфера , що є проміжним значенням хеш-функції, та змінює вмістиме цього буфера. Кожний цикл використовує четверту частину 64 – елементної таблиці , побудованої на основі функції , , де - ціла частина.
Наприклад: ,
- ий елемент , який позначається , приймає значення рівне цілій частині від , число задається в радіанах. Оскільки функція приймає значення, які знаходяться в проміжку від 0 до 1, то кожний елемент є цілим, яке можна представити 32 розрядами. Для отримання вихід чотирьох циклів додається по модулю з . Додавання виконується незалежно для кожного з чотирьох слів в буфері.
Крок 5: Вихід
Після обробки всіх , 512 - розрядних блоків виходом -ої стадії є 128 – розрядний дайджест повідомлення.
Розглянемо детальніше логіку кожного із чотирьох циклів обробки одного 512 – розрядного блоку. Цикл обробки складається із 16 кроків, які оперують з буфером .
Кожний крок можна подати у вигляді:

Рис. 4. Логіка виконання окремого кроку.
,
де
- чотири слова буфера; після виконання кожного окремого кроку відбувається циклічний зсув вліво на одне слово.

- одна з елементарних функцій .

- циклічний зсув вліво на розрядів 32-розрядного аргументу.

- -те 32-розрядне слово в - му 512-розрядному блоці повідомлення.

- -те 32-розрядне слово в матриці .

- операція додавання по модулю .


В кожному з чотирьох циклів алгоритму застосовується одна з чотирьох елементарних логічних функцій. Кожна елементарна функція отримує три 32-розрядних слова на вході і на виході формує одне 32-розрядне слово. Елементарні функції мають наступний вигляд:

В цих формулах застосовуються такі логічні операції: логічне множення (&, порозрядне І), логічне додавання (, порозрядне АБО), додавання по модулю 2 (, порозрядне виключне АБО) та інверсія (, побітове заперечення ).
Масив з 32-ох розрядних слів приймає значення поточного 512 – розрядного блоку Кожний цикл виконується 16 раз. Оскільки кожен блок вхідного повідомлення обробляється в чотирьох циклах, то кожний блок вхідного повідомлення обробляється по схемі, яка зображена на рис.4, 64 рази.
Якщо подати вхідний 512 – розрядний блок у вигляді шістнадцяти 32-розрядних слів, то кожне вхідне 32-розрядне слово використовується чотири рази, по одному разу