Надійність простих чисел
В алгоритмі DH використовується велике і надійне число з безлічі простих. Як саме його вибрати? Розберемо по кроках.
Отриманий таким чином набір (a, k, b) може вважатися достатнім для використання в алгоритмі обміну ключами Діффі-Хеллмана. Відповідно, одержувачу повідомлення також потрібно перевірити значення, яке має бути ступенем b, і переконатися (наприклад, функцією символу Лежандра), що вона потрапляє в безліч, породжене числом b.
Використання підгруп
Головним мінусом вищеописаного алгоритму є недостатня ефективність. Припустимо, що довжина простого числа a дорівнює n біт, значить, k – n-1 біт. Виходить, всі ступені будуть мати довжину n-1. Тоді операція зведення в ступінь в середньому буде складатися з 3n/2 множень на a mod. Це досить великий процес.
Для того щоб впоратися з цією проблемою, було вирішено застосовувати підгрупи меншого розміру. Який виграш в продуктивності в такому випадку? Якщо число a складається з 2000 біт, тоді для обчислення bx потрібно 3000 операцій множення. Завдяки використанню підгруп, це число може бути скорочено до ~400. Це суттєве збільшення ефективності алгоритму робить можливим його всебічне застосування. Наприклад, алгоритм Діффі-Хеллмана з трьома і більше учасниками.
