Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Методичні вказівки до лабораторної роботи №1 з курсу "Проектування засобів захисту інформації в комп’ютерних мережах" для студентів напрямків 091501, 091501 "Комп’ютерні системи та мережі"

Скачати 88.79 Kb.

Методичні вказівки до лабораторної роботи №1 з курсу "Проектування засобів захисту інформації в комп’ютерних мережах" для студентів напрямків 091501, 091501 "Комп’ютерні системи та мережі"




Скачати 88.79 Kb.
Дата конвертації13.06.2017
Розмір88.79 Kb.
ТипМетодичні вказівки


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

Кафедра ЕОМ



Обчислення хеш-функції за алгоритмом MD5


Методичні вказівки
до лабораторної роботи № 1

з курсу “Проектування засобів захисту інформації в комп’ютерних мережах”


для студентів напрямків 7.091501, 8.

Геш-функція (Хеш-функція) - функція, що перетворює вхідні дані будь-якого (як правило великого) розміру в дані фіксованого розміру.

Студе́нт (лат. studens, родовий відмінок studentis - «ретельно працюючий», «такий, що займається») - учень вищого, у деяких країнах і середнього навчального закладу.

Зáхист інформáції (англ. Data protection) - сукупність методів і засобів, що забезпечують цілісність, конфіденційність і доступність інформації за умов впливу на неї загроз природного або штучного характеру, реалізація яких може призвести до завдання шкоди власникам і користувачам інформації.

091501 “Комп’ютерні системи та мережі”

8.091502 “Системне програмне забезпечення”

8.091503 “Спеціалізовані комп’ютерні системи”

Затверджено


на засіданні кафедри
Електронних Обчислювальних Машин
Протокол №  від 2006 року
Львів – 2006

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

Обчи́слення - є гілкою математики, зосередженою на функціях, похідних, інтегралах, і нескінченному ряду чисел. Цей предмет являє собою важливу частину сучасної математичної освіти. Воно складається з двох основних галузей - диференціального і інтегрального численнь, які пов'язують основні теореми обчислення.

Націоналі́зм (фр. nationalisme) - ідеологія і напрямок політики, базовим принципом яких є теза про цінність нації як найвищої форми суспільної єдності та її первинності в державотворчому процесі[джерело?].

Укладачі: В.М. Грига, асистент кафедри ЕОМ

В.М. Сокіл, асистент кафедри ЕОМ

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

Рецензенти: ВА. Голембо, к.т.н., доц. кафедри ЕОМ.

Ю.В. Морозов, к.т.н., доц. кафедри ЕОМ.



1 Мета роботи


Мета роботи: реалізувати демонстраційну програму обчислення значення сигнатури вхідного повідомлення за алгоритмом MD5.

2 Очікуваний результат роботи


В ході роботи необхідно засвоїти основні принципи побудови алгоритмів обчислення сигнатури повідомлень, розробити демонстраційну програму обчислення значення сигнатури вхідного повідомлення за алгоритмом MD5.

Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.


3 Теоретичні відомості

Алгоритм MD5 (Message Digest) – це алгоритм хешування, розроблений професором Рональдом Л.Рівестом з Массачусетського технологічного інституту (МТІ) в 1992 році.

В якості вхідних даних береться повідомлення (потік даних) довільної довжини, і обчислюється 128 – розрядний хеш-код (сигнатура, дайджест). Припускається, що не існує двох повідомлень, які мають однакові сигнатури, або не можливо створити повідомлення з наперед заданою сигнатурою. Цей алгоритм застосовується в криптографії при формуванні цифрових підписів та генерації ключів шифрування.

Массачусетс (Massachusetts) - штат у США на Атлантичному узбережжі (інші назви: штат біля Затоки, штат Старої Колонії). Площа 21,5 тис. км², населення 6 016 400 мешканців (1990); головні міста: Бостон (адміністративний центр, порт), Спрингфілд, Вустер, Нью-Бедфорд, Кембридж; низовинно-височинний, на заході Аппалачі;

Генерація - покоління, що представлене більш чи менш одноманітними особинами, які змінюються наступним поколінням, яке при диференціації життєвого циклу може істотно відрізнятися від попереднього. Наприклад: при чергуванні поколінь (гетерогонії, метагенезі) у тлі (Aphidoidea), галиць (Cecidomyiidae) та деяких інших комах.

Техноло́гія (від грец. τεχνολογια, що походить від грец. τεχνολογος; грец. τεχνη - майстерність, техніка; грец. λογος - (тут) передавати) - наука («корпус знань») про способи (набір і послідовність операцій, їх режими) забезпечення потреб людства за допомогою (шляхом застосування) технічних засобів (знарядь праці).

Криптогра́фія (від грецького kryptós - прихований і gráphein - писати) - наука про математичні методи забезпечення конфіденційності, цілісності і автентичності інформації. Розвинулась з практичної потреби передавати важливі відомості найнадійнішим чином.

Шифрува́ння - оборотне перетворення даних, з метою приховання інформації. Шифрування з'явилось близько 4 тис. років назад. Першим відомим зразком шифру вважається єгипетський текст, створений приблизно в 1900 р.

Профе́сор (лат. professor - викладач, учитель) - учене звання і посада викладача вищого навчального закладу або наукового співробітника науково-дослідної установи. Офіційний статус із XVI століття (вперше в Оксфордському університеті).

Електро́нний цифрови́й пі́дпис (ЕЦП) (англ. digital signature) - вид електронного підпису, отриманого за результатом криптографічного перетворення набору електронних даних, який додається до цього набору або логічно з ним поєднується і дає змогу підтвердити його цілісність та ідентифікувати підписувача.

По суті, алгоритм хешування MD5 – це спосіб перевірки цілісності даних, набагато надійніший ніж контрольна сума або інші методи.

Контро́льна су́ма - деяке значення, розраховане на основі набору даних з використанням певного алгоритму, що використовується для перевірки цілісності даних при їх передачі або збереженні. Також контрольні суми можуть використовуватись для швидкого порівняння двох наборів даних на нееквівалентність: з великою вірогідністю різні набори даних матимуть відмінні контрольні суми.

Алгоритм під час розробки був оптимізований для 32 – розрядних систем і не потребує великих об’ємів пам’яті. MD5 є дещо повільніший, ніж MD4, але більш стійкий до криптографічних атак.


Опис алгоритму

Перед тим, як розглянути детально сам алгоритм, визначимо основні терміни та поняття, що ним використовуються. Під терміном “слово” будемо розуміти кількість інформації, яка представлена 32-ома розрядами (бітами), а під терміном “байт” – 8 розрядів (біт). Послідовність біт як послідовність байт, де кожна група із 8 – ми розрядів є окремим байтом, причому старший розряд байта іде першим. Аналогічно представляється послідовність байт, тільки молодший байт іде першим.

В якості вхідного потоку будемо мати потік даних розрядів.

Послідо́вність - функція визначена на множині натуральних чисел яка набуває значення на об'єктах довільної природи. f : N → X \,\rightarrow \,\!X} .

Анало́гія - (грец. αναλογια - «відповідність») - подібність, схожість у цілому відмінних предметів, явищ за певними властивостями, ознаками або відношеннями.

В теорії інформації вла́сна інформ́ація (англ. self-information), або несподі́ваність (англ. surprisal), - це міра кількості інформації, пов'язаної з подією в імовірнісному просторі, або зі значенням дискретної випадкової величини.

Поті́к да́них (англ. data stream) в телекомунікаціях і програмуванні - це послідовність кодованих когерентних сигналів (пакетів даних) в цифровій формі, яка використовується, щоб передавати або отримати інформацію це знаходиться в передачі.

- невід’ємне ціле число (можливо 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-розрядний буфер.

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

Він представляється, як чотири 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-розрядне слово використовується чотири рази, по одному разу в кожному циклі, і кожний елемент таблиці , який складається з 64-ьох 32-розрядних слів використовується тільки один раз. Після кожного кроку циклу відбувається циклічний зсув вліво чотирьох слів і . На кожному кроці змінюється тільки одне з чотирьох слів буфера . Відповідно кожне слово буфера змінюється 16 раз, 17-ий раз в кінці для отримання остаточного виходу поточного блоку. Результат обчислення (хеш) представлений за допомогою чотирьох 32-розрядних слів - (молодші записуються в , старші в ).
Приклад псевдокоду алгоритму обчислення MD5 хеш функції наведено нижче.

Псевдокод - це неформальний запис алгоритму, який використовує структуру поширених мов програмування, але нехтує деталями коду, неістотними для розуміння алгоритму (опис типів, виклик підпрограм тощо).


// обробка вхідного потоку даних блоками по 16 слів

for i = 0 to N/16 - 1 do


{
    // копіювання i-го блоку в X
    for j = 0 to 15 do
        X[j] = M[i * 16 j]

    // Збереження значень A, B, C, D


    AA = A
    BB = B
    CC = C
    DD = D

    // цикл 1


    // нехай [abcd k s i] означають операцію
    //     a = b ((a  F(b, c, d) X[k] T[i]) <<< s)
    // виконати 16 наступних операцій
    [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
    [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
    [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
    [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]
    // цикл 2
    // нехай [abcd k s i] означають операцію
    //     a = b ((a  G(b, c, d) X[k] T[i]) <<< s)
    // виконати 16 наступних операцій
    [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
    [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
    [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
    [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]
    // цикл 3
    // нехай [abcd k s i] означають операцію
    //     a = b ((a  H(b, c, d) X[k] T[i]) <<< s)
    // виконати 16 наступних операцій
    [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
    [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
    [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
    [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]
    // цикл 4
    // нехай [abcd k s i] означають операцію
    //     a = b ((a  I(b, c, d) X[k] T[i]) <<< s)
    // виконати 16 наступних операцій
    [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
    [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
    [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
    [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]

    A = AA


    B = BB
    C  = CC
    D = DD
}

4 Література

1. В. Стоуллингс “Криптография и защита сетей – Принципы и практика”, Киев 2003


2. Menezes A., van Oorshot P., Vanstone S. Handbook of applied cryptography. CRC Press, 1997


  1. Соколов А. В., Шаньгин В. Ф. “Защита информации в распределенных корпоративных системах”, Москва 2002




  1. RFC 1321 The MD5 Message-Digest Algorithm. B. Kaliski. April 1992.


Зміст

1 Мета роботи..........................................................................................................................……3

2 Очікуваний результат роботи................................................................................................. …3

3 Теоретичні відомості……………………………… …….…………………………………......

Тео́рія (від грец. θεωρία - розгляд, дослідження) - сукупність висновків, що відображає відносини і зв'язки між явищами реальності у вигляді інформаційноі моделі. Теорією стає гіпотеза, що має відтворюване підтвердження явищ та механізмів і дозволяє спостерігачу прогнозувати наслідки дій чи зміни стану об'єкта спостережень.

3

4 Література…………………………………………………...……………………...…..……. ....9

Навчальне видання


Методичні вказівки

до лабораторної роботи

“ Обчислення хеш-функції за алгоритмом MD5
з дисципліни

" Проектування засобів захисту інформації "
для студентів напрямків 7.091501, 8.091501 “Комп’ютерні системи та мережі”

8.091502 “Системне програмне забезпечення”

8.091503 “Спеціалізовані комп’ютерні системи”

Укладачі Грига Володимир Михайлович

Сокіл Володимир Михайлович

Редактор
Комп’ютерне складання

Підписано до друку 200 р.

Полігра́фія (від полі - багато; графо - пишу) - галузь техніки, сукупність технічних засобів для множинного репродукування текстового матеріалу й графічних зображень.

Формат 70 х 100 1/16. Папір офсетний.

Друк на різографі.

Різо́граф (від назви фірми-виробника - Riso Kagaku Corporation) - друкарська машина, цифрова система друку, копір, робота якої базується на використанні методу трафаретного друку фарбою. Менш вживаними є назви: «дуплікатор» - від назви іншої фірми-виробника друкарських машин даного типу DUPLO; «пріпорт» - так називає свої друкарські машини виробник RICOH.

Умовн. друк. арк. ...... Обл.-вид. арк. ......

Наклад ..... прим. Зам. 780.
Поліграфічний центр

Видавництва Національного університету “Львівська політехніка”



вул. Колесси, 2, 79000, Львів




Скачати 88.79 Kb.

  • 1 Мета роботи
  • 3 Теоретичні відомості
  • 4 Література
  • Навчальне видання