Криптосистема ElGamal
Поряд з RSA, існують і інші криптосистеми з відкритим ключем. Багато з них засновані на різних версіях проблеми дискретного логарифму.
Криптосистема ElGamal, звана варіантом еліптичної кривої, також заснована на задачі дискретного логарифму. Вона отримує силу захисту з припущення, що дискретні логарифми не можуть бути знайдені в практичному часовому інтервалі для заданого числа, тоді як зворотна операція потужності може бути розрахована ефективно.
Наприклад, проста версія ElGamal, яка працює з числами modulo p. У разі варіантів еліптичної кривої метод заснований на абсолютно різних системах числення. Кожен користувач криптосистеми ElGamal генерує пару ключів наступним чином:
N | N 3 | 3 n mod 5 |
1 | 3 | 3 |
2 | 9 | 4 |
3 | 27 | 2 |
4 | 81 | 1 |
Вибір секретного ключа. Приватним ключем x є будь-яке число, більше 1 і менше, ніж (p-1). Обчислення частини відкритого ключа. Значення y обчислюється за параметрами p, g і закритого ключа x наступним чином:
y = gx mod p.
Отримання відкритого ключа. Відкритий ключ ElGamal складається з трьох параметрів (p, g, y).Припустимо, наприклад, що p = 17 і g = 6. Можна стверджувати, що 6 є генератором групи Z 17. Закритий ключ x може бути будь-яким числом більше 1 і менше 71, тому вибирають x = 5. Потім значення y обчислюється наступним чином:
y = 65 mod 17 = 7.
Таким чином, закритий ключ дорівнює 62, а відкритий ключ – (17, 6, 7).