Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 39

2.11Лабораторна робота № 11. Розподіл ключів. Протокол Діффі-Хелмана.

Тема: Розподіл ключів. Протокол Діффі-Хелмана

Ціль роботи: Відпрацювати вміння використання протоколу розподілу ключів Діффі-Хелмана, на практиці здійснити формування загального ключа між двома користувачами. Усвідомити сильні і слабкі сторони в застосуванні даного протоколу.

Загальні відомості

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

У.Діффі і М.Хелман запропонували для створення криптографічних систем з відкритим ключем використовувати однобічну функцію дискретного зведення в ступінь.[19]

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

Необоротність перетворення в цьому випадку забезпечується тим, що досить легко обчислити показову функцію виду ax mod p, де х – велике просте число (наприклад, розміру 256 бітів), та знайти а з даного співвідношення, при коректному виборі р, практично неможливо.

Протокол Діффі-Хелмана здійснює так називаний експонентний ключовий обмін, з використанням функції f(x), при заздалегідь обраних несекретних параметрах а, р. Ці параметри залежні, у тому змісті, що а вибирається так, щоб послідовність ступенів а1 mod р, а2 mod р,...,ар-1 mod р, збігалася, з точністю до перестановки з послідовністю 1,2,...р-1. Число а називається примітивним елементом або первісним коренем. Примітивні елементи по модулю простого числа завжди існують.[19]

Протокол Діффі-Xелмана вирішує задачу безпечної побудови загального ключа виду k= аxy mod р, де х і у – випадкові відрахування по модулю р-1, обрані учасниками ключового обміну незалежно і зберігаються в секреті. При цьому, 2 х, у р-2. У ході протоколу учасники обмінюються значеннями ах(mod р) і ау(mod р). Оскільки одному з них відомий х, а іншому – у, то кожен учасник у стані обчислити значення k= аxy (mod р). При перехопленні, знання ах mod р не дозволяє знайти х (використовується одностороння функція), крім того, у даний час, для перебування аxy (mod р) по ах (mod р) і аy (mod р), підходів, не еквівалентних звертанню однобічної функції, не знайдено.[1]

Приклад організації системи експонентного ключового обміну.

Виберемо просте число: р = 13.

Виберемо первісний корінь:

а = 7, оскільки: {7',72,...,712} = {7,10,5,9,11,12,6,3,8,4,2,1}.

3.Опублікуємо а, р.

Приклад експонентного ключового обміну між абонентами А, В.

1. А генерує псевдовипадкове число, х і передає В значення

А0x(mod р).

2. В генерує псевдовипадкове число, у і передає А значення

Ар=ау(mod р).

А обчислює К0рхху(mod р) і посилає В .

В обчислює Кр= А0хху(mod р).

Псевдовипадкове число Кр= К0 можна використовувати як ключ для симетричної криптосистеми.

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

1.  Вивчити схему відкритого розподілу ключів Діффі-Хелмана.

2.  З додатку 1 взяти параметри системи відкритого розподілу ключів відповідно до номеру студента у журналі.

3.  Здійснити експоненціальний ключовий обмін між двома абонентами.

4.  Скласти звіт, у якому вказати вхідні дані, послідовність дій розподілу ключів і відповіді на контрольні запитання.

Контрольні питання.

1.  Чому при експонентному ключовому обміні необхідно уникати значень х, у рівних 0, 1, р-1?

2.  Чи розв'язне рівняння 2x=3(mod р), при р=13 і 1 з р-1?

3.  Чи розв'язне рівняння 5x=9(mod 13)?

4.  Який повинний бути розмір р (тобто size(р)), щоб можна було б при експонентному ключовому обміні формувати ключі для алгоритму DES ?

5.  Укажіть мінімальне значення size(р) для формування сеансових ключів для алгоритму ГОСТ 28147-89.

6.  З погляду загальної стійкості криптосистеми, відповісти, для якого алгоритму DES або ГОСТ експонентний ключовий обмін більш прийнятний?

7.  Наскільки, на Ваш погляд, складна програмна й апаратна реалізація вивченого протоколу ключового обміну?


2.12Лабораторна робота №12. Геш-функції та їхнє застосування.

Тема роботи: Геш-функції та їхнє застосування.

Ціль роботи: На практиці відпрацювати застосування геш-функцій для отримання дайджестів повідомлень. Запропонувати області застосування геш-функцій.

Загальні відомості

Під терміном геш-функція розуміється функція, що відображає електронні повідомлення довільної довжини (іноді довжина повідомлення обмежена, але досить великим числом), у значення фіксованої довжини. Останні часто називають геш-кодами [6].

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

Коли на вхід системи перевірки подається довільне повідомлення, воно не шифрується саме по собі, а на його основі обчислюється геш-код (причому довжина його фіксована і звичайно дорівнює 128 бітам). Якщо довжина коду n біт, то всього можливо 2n різних кодів. Тоді для 128 біт це 2128 » 3.4×1038 різних значень, тобто досить для того, щоб кожне повідомлення мало свій «оригінальний» геш-код довжиною усього в 128 біт [4].

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

Математично: у всякої геш-функции h існує велика кількість колізій, тобто пара значень х і у таких, що h(x) = h(y). Основна вимога до геш-функцій полягає у відсутності ефективних алгоритмів пошуку колізій (тобто щоб знайти пари різних документів з однаковим геш-кодом було важко). Геш-функція, що володіє такою властивістю, називається Геш-функцією, вільної від колізій. Крім того, геш-функція повинна бути однобічною, тобто функцією, за значенням якої обчислювально важко знайти її аргумент, у той же час, функцією, для аргументу якої обчислювально важко знайти інший аргумент, який давав би те ж саме значення функції [2].