Перший алгоритм DH
У початковій версії алгоритм працював за наступною схемою. Вибираються велике число a з безлічі простих і примітивний елемент b, породжує Z*a. Обидва числа a і b являють собою відкритий ключ, вони відомих усьому, в тому числі і зловмисникам. Як же тоді приховати повідомлення?
Саме на цьому кроці Діффі і Хеллман придумали дуже дотепний хід. Нехай у нас є дві людини, що між собою: А і Б. Спочатку А вибирає випадкове число x з Z*a , що є еквівалентом вибору числа з {1, …, a-1}. Потім він обчислює значення за формулою (bx mod a) і відправляє його Б. В свою чергу Б вибирає деяке число y з того ж безлічі, обчислює значення (mod by a) і відправляє результат назад А.
Таким хитрим способом виходить, що секретний ключ виглядає bxy . Завдяки властивості ступенів, яке свідчить gxy = (gy)x, співрозмовник А може обчислити потрібне значення і розшифрувати пересланную йому інформацію. І точно так само це значення обчислює співрозмовник Б. Таким чином, обидва мають однаковий секретний ключ.
Які проблеми відчуває зловмисник при такому обміні інформацією? Він може перехопити числа gx і gy. І навіть при знанні відкритих ключів задача обчислення gxy не є тривіальною, оскільки поки що не існує ефективного алгоритму пошуку потрібного значення в розподілі ключів Діффі-Хеллмана. Ця задача відома під назвою “проблема обчислення дискретного логарифма”.
