Цифровая подпись Эль-Гамаля. Схема RSA

Пусть – простое число, – примитивный элемент поля .

Выберем случайное число в интервале и вычислим

значение .

Число является секретным ключом,

набор – открытым ключом.

Подпись для сообщения М вычисляется по алгоритму:

1. Выбрать случайное целое число , .

2. Вычислить .

3. Для вычислить .

4. Подписью для сообщения М положить пару .