27

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

Кафедра ЕОМ

Методичні вказівки до циклу лабораторних робіт

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

для студентів напрямків 7.091501, 8.091501 “Комп’ютерні системи та мережі”

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

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

Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол №  1 від 28 серпня 2012 року

Львів – 2012

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

Укладачі: В.М. Сокіл, к.т.н., доц. кафедри ЕОМ

О.М. Колодчак, асистент кафедри ЕОМ

А.А. Андрух, ст. викл. кафедри ЕОМ

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

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

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

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

1 Мета роботи

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

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

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

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

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

Логіка виконання SHA-1

Алгоритм отримує на вході повідомлення максимальної довжини 2 ⁶⁴ біт і створює в якості виходу дайджест повідомлення довжиною 160 біт.

Алгоритм складається з наступних кроків:

512 біт 512 біт

160 біт 160біт 160біт

Рис. 1. Логіка виконання SHA-1

Крок 1: додавання бракуючих бітів

Повідомлення додається таким чином, щоб його довжина була кратна 448 по модулю 512 (довжина 448 mod 512). Додавання здійснюється завжди, навіть якщо повідомлення вже має потрібну довжину. Таким чином, число додаваних бітів знаходиться в діапазоні від 1 до 512. Додавання складається з одиниці, за якою слід необхідну кількість нулів.

Крок 2: додавання довжини

До повідомлення додається блок з 64 бітів. Цей блок трактується як беззнаковое 64-бітне ціле і містить довжину вихідного повідомлення до додавання.

Результатом перших двох кроків є повідомлення, довжина якого кратна 512 бітам. Розширене повідомлення може бути представлене як послідовність 512-бітних блоків Y₀, Y₁,. . . , Y_L-1, так що загальна довжина розширеного повідомлення є L * 512 біт. Таким чином, результат кратний шістнадцяти 32-бітними словам.

Крок 3: ініціалізація SHA-1 буфера

Використовується 160-бітний буфер для зберігання проміжних та остаточних результатів хеш-функції. Буфер може бути представлений як п'ять 32-бітних регістрів A, B, C, D і E. Ці регістри ініціалізується наступними шістнадцятковому числами:

A = 67452301

B = EFCDAB89

C = 98BADCFE

D = 10325476

E = C3D2E1F0

Крок 4: обробка повідомлення в 512-бітних блоках

Основою алгоритму є модуль, що складається з 80 циклічних обробок, позначений як H_SHA. Всі 80 циклічних обробок мають однакову структуру.

SHA_q(160біт)

Y_q(512біт)

A B C D E

………………………………………………….

SHA_q+1(160біт)

Рис. 2. Обробка чергового 512-бітного блоку

Кожен цикл отримує на вході поточний 512-бітний обробляємий блок Yq і 160-bit значення буфера ABCDE, і змінює вміст цього буфера.

У кожному циклі використовується додаткова константа Кt, яка приймає тільки чотири різних значення:

0 ≤ t ≤ 19 Kt = 5A827999 (ціла частина числа [2³⁰ × 2^1/2])

20 ≤ t ≤ 39 K t = 6ED9EBA1 (ціла частина числа [2³⁰ × 3^1/2])

40 ≤ t ≤ 59 K t = 8F1BBCDC (ціла частина числа [2³⁰ × 5^1/2])

60 ≤ t ≤ 79 K t = CA62C1D6 (ціла частина числа [2³⁰ × 10^1/2])

Для отримання SHA q +1 вихід 80-го циклу складається зі значенням SHAq. Додавання за модулем 2³² виконується незалежно для кожного з п'яти слів в буфері з кожним з відповідних слів у SHAq.

Крок 5: вихід

Після обробки всіх 512-бітних блоків виходом L-ої стадії є 160-бітний дайджест повідомлення.

Розглянемо більш детально логіку в кожному з 80 циклів обробки одного 512-бітного блоку. Кожен цикл можна представити у вигляді:

A, B, C, D, E (CLS₅ (A) + f t (B, C, D) + E + W t + K t), A, CLS₃₀ (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.

Рис. 3. Логіка виконання окремого циклу

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

Номер циклу	ft (B,C,D)
(0≤ t ≤19)	(B ˄ C) ˅ (¬ B ˄ D)
(20≤ t ≤39)	B + C + D
(40≤ t ≤59)	(B ˄ C) ˅ (B ˄ D) ˅ (C ˄ D)
(60≤ t ≤79)	B + C + D

Насправді використовуються тільки три різні функції. Для 0 ≤ t ≤ 19 функція є умовною: if B then C else D. Для 20 ≤ t ≤ 39 і 60 ≤ t ≤ 79 функція створює біт парності.

Для 40 ≤ t ≤ 59 функція є істинною, якщо два або три аргументу правдиві.

32-бітні слова Wt виходять з чергового 512-бітного блоку повідомлення наступним чином.

Рис. 4. Отримання вхідних значень кожного циклу з чергового блоку

Перші 16 значень Wt беруться безпосередньо з 16 слів поточного блоку. Решта значення визначаються наступним чином:

W_t = W_t-16+W_t-14+W_t-8+W_t-3, де

+ - додавання за модулем 2.

У перших 16 циклах вхід складається з 32-бітного слова даного блоку. Для решти 64 циклів вхід складається з XOR декількох слів з блоку повідомлення.

Алгоритм SHA-1 можна підсумувати наступним чином:

SHA ₀ = IV

SHA _{q +1} = Σ₃₂ (SHA_q, ABCDE_q)

SHA = SHA _L-1

де

IV - початкове значення буфера ABCDE.

ABCDE q - результат обробки q-того блоку повідомлення.

L - число блоків у повідомленні, включаючи поля додавання і довжини.

Σ32 - сума за модулем 2 ³², здійснюється окремо для кожного слова буфера.

SHA - значення дайджеста повідомлення.

Завдання для виконання роботи:

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

Порядок виконання роботи:

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

2. Реалізувати підсистеми обчислення хеш-функції засобами MS Visual Studio 2005.

3. Побудувати графічний інтерфейс програми обчислення значення сигнатури вхідного повідомлення .

4. Підготувати та захистити звіт.

Література

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

2. FIPS PUB 180-1 Secure hash standard