Завдання №4. Функція хешування.

Функцією хешування (хеш-функцією) називається перетворення даних, що переводить рядок бітів M довільної довжини в рядок бітів h(M) деякої фіксованої довжини (декілька десятків або сотень біт).

Хеш-функція h(M) повинна задовольняти наступним умовам:

1. хеш-кодування-функція h(M) повинна бути чутлива до будь-яких змін вхідній послідовності M;

2. для даного значення h(M) повинно бути неможливо знайти значення M;

3. для даного значення h(M) повинно бути неможливо знайти значення M’  M таке, що h(M‘)= h(M).

Ситуація, при якої для різних вхідних послідовностей M, M‘ співпадають значення їх хеш-образів: h(M)= h(M‘), називається колізією.

При побудові хеш-образу вхідна послідовність M розбивається на блоки M_i фіксованої довжини і оброблюється поблочно по формулі H_i = f(H_i-1, M_i).

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

Як приклад розглянемо спрощений варіант хеш-функції з рекомендацій МККТТ Х.509:

H_i = (H_i-1 + M_i )² mod n,

де n = pq, p і q – великі прості числа, H₀ - довільне початкове заповнення, M_i - i-тий блок повідомлення M = M₁ M₂ . M_k .

Знайти хеш–образ свого Прізвища, використовуючи хеш–функцію , де n = pq; (p, q узяти із Завдання №3).

Хешоване повідомлення «КОЗИНА». Візьмемо двоє простих числа p=13, q=19 (див. Д5). Визначимо n=pq=13*19=247. Вектор ініціалізації виберемо рівним 8 (вибираємо випадковим чином). Слово «КОЗИНА» можна представити послідовністю чисел (12, 16, 9, 10, 15, 1) по номерах букв в абетці. Таким чином

n=247, H0=8, M1=12, M2=16, M3=9, M4=10, M5=15, M6=1.

Використовуючи формулу

,

отримаємо хеш-образ повідомлення «КОЗИНА»:

H1=(H0+M1)² mod n = ( 8 + 12)² mod 247 = 400 mod 247=153

H2=(H1+M2)² mod n = (153 + 16)² mod 247 = 28561 mod 247= 156

H3=(H2+M3)² mod n = (156 + 9)² mod 247 = 27225 mod 247= 55

H4=(H3+M4)² mod n = ( 55 + 10)² mod 247 = 4225 mod 247= 26

H5=(H4+M5)² mod n = ( 26 + 15)² mod 247 = 1681 mod 247= 199

H6=(H5+M6)² mod n = (199 + 1)² mod 247 = 40000 mod 247= 233

У результаті отримуємо хеш-образ повідомлення «КОЗИНА», рівне 233.

Завдання №5. Електронний цифровий підпис.

Класична схема створення цифрового підпису

При створенні цифрового підпису по класичній схемі відправник:

1. Застосовує до початкового повідомлення хеш-функцію;

2. Обчислює цифровий підпис по хеш-образу повідомлення з використанням секретного ключа створення підпису;

3. Формує нове повідомлення, що складається з початкового повідомлення і доданого до нього цифрового підпису.

Одержувач, отримавши підписане повідомлення :

1. Відокремлює цифровий підпис від основного повідомлення;

2. Застосовує до основного повідомлення хеш- функцію;

3. З використанням відкритого ключа перевірки підпису витягує хеш-образ повідомлення з цифрового підпису;

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

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

Для створення підпису повідомлення M відправник :

1. Обчислює хеш-образ r = h(M) повідомлення M за допомогою деякої хеш-функції;

2. Зашифровує отриманий хеш-образ r на своєму секретному ключі (d,n), тобто обчислює значення s = r^d mod n, яке і є підписом.

Для перевірки підпису одержувач :

1. Розшифровує підпис s на відкритому ключі (e,n) відправника, тобто обчислює

r’ = s^e mod n і таким чином відновлює передбачуваний хеш-образ r’ повідомлення M;

2. Обчислює хеш-образ h(M)= r повідомлення M за допомогою тієї ж самої хеш-функції, яку використовував відправник;

3. Порівнює набутих значень r і r’ . Якщо вони співпадають, то підпис правильний, відправник дійсно є тим, за кого себе видає, і повідомлення не було змінене при передаванні.

Використовуючи хеш-образ свого Прізвища, обчислите електронний цифровий підпис по схемі RSA.

Хай хеш-образ Прізвища дорівнює 233, а закритий ключ алгоритму RSA рівний (25, 247). Тоді електронний цифровий підпис повідомлення, що складається з Прізвища, обчислюється за правилом (див. Додаток Д7):

s = 233 ²⁵ mod 247 = 168.

Для перевірки ЕЦП, використовуючи відкритий ключ (121, 247), знайдемо

H = 168 ¹²¹ mod 247 = 233.

Оскільки хеш-кодування-образ повідомлення співпадає із знайденим значенням H, то підпис визнається справжнім.