2. Алгоритм Діфі-Хелмана

Алгоритм відкритого розподілу ключів Діфі-Хелмана був запропонований у 1976 році. Цей алгоритм був першим алгоритмом з відкритим ключем [9,10,11]. Його безпека обумовлена труднощами обчислення дискретних логарифмів у скінченному полі, на відміну від легкості дискретного зведення в степінь у тому ж скінченному полі.

Припустимо, що два користувачі А і В хочуть організувати захищений комунікаційний канал. Обидві сторони заздалегідь вибирають велике просте число N і число g (1 ≤ g ≤ N-1), яке є первісним коренем по модулю N, тобто його степені

g¹, g², g³,…,g^N-1

є різними по модулю N. Наприклад. Нехай N=7. Тоді g=3 є первісним коренем по модулю 7, тому що

3¹=3≡3 (mod 7),

3²=9≡2 (mod 7),

3³=27≡6 (mod 7),

3⁴=81≡4 (mod 7),

3⁵=243≡5 (mod 7),

3⁶=729≡1 (mod 7).

Ці два цілих числа N і g є спільними для всіх користувачів комп'ютерної системи і їх не треба зберігати в секреті. Алгоритм складається з наступних кроків.

1.	Спочатку користувачі А і В незалежно один від одного вибирають власні секретні ключі KCA і KCB (KCA і KCB – випадкові великі цілі числа, що зберігаються користувачами А і В у секреті).
2.	Далі користувач А обчислює відкритий ключ КОA=gKCA (mod N), а користувач В – відкритий ключ КОB=gKCB (mod N).
3.	Потім користувачі А і В обмінюються відкритими ключами КОA і КОB по незахищеному каналу.
4.	Нарешті користувачі А і В обчислюють спільний секретний ключ. Користувач А обчислює К= (КОB)КCA = (gKCB) КCA(mod N), а користувач В: К' = (КОA)КCB = (gKCA) КCB(mod N). При цьому К = К', тому що (gKCB) КCA = (gKCA) КCB(mod N).

Ключ К може використовуватися в якості спільного секретного ключа симетричної криптосистеми.

Зловмисник, перехопивши значення N, g, КО_A і КО_B, теж хотів би знайти ключ К. Очевидний шлях для вирішення цієї задачі складається в обчисленні такого значення КС_A по N, g, КО_A, що

g^KС_A mod N = КО_A .

Оскільки в цьому випадку, обчисливши КС_A можна знайти

К= (КО_B)^КС_A (mod N).

Однак знаходження КС_А по N, g і КО_A – задача дискретного логарифмування в скінченному полі, яка вважається практично нерозв'язною [9,11].

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

Для розподілу секретних ключів між користувачами розподіленої інформаційної системи можна використовувати і алгоритм RSA. Перевага методу Діфі-Хелмана в порівнянні з методом RSA полягає в тім, що формування загального секретного ключа відбувається в сотні разів швидше. У системі RSA генерація нових секретних і відкритих ключів заснована на генерації нових простих чисел, що займає багато часу [9,11].

Приклад. Виберемо модуль N = 19, а первісним коренем по модулю N = 19 число g = 2. Припустимо, що користувачі А і В вибрали своїми секретними ключами КC_А =3 і КC_B =6. Щоб мати спільний секретний ключ К, вони обчислюють спочатку значення своїх відкритих ключів:

КО_A=g^KC_A (mod N)=2³=8=8 (mod 19),

КО_B=g^KC_B (mod N)=2⁵=32=13 (mod 19).

Після того, як користувачі А і В обміняються значеннями КО_A=8 і КО_B=13, вони обчислюють спільний секретний ключ

К= (КО_B)^КCA (mod N)=13³=2197=12 (mod 19),

К' = (КО_A)^КCB (mod N)=8⁵=32768 =12 (mod 19).

Отже, спільний секретний ключ К=12.