Lecture_11_1

Генерируется случайное простое число p

Выбирается целое число 1 такое, что 1< 1< p, и 1- первообразный корень p

Выбирается случайное целое число d такое, что 1 < d < p

Вычисляется 2 = 1

Открытым ключом объявляется тройка ( 1, 2, p) Закрытым ключом назначается число d

Выбирается секретное случайное число r

Вычисляется первая часть подписи

1 = 1

Вычисляется вторая часть подписи

2 = ( − × 1) × −1( − 1),

где −1 - мультипликативная инверсия по модулю ( − 1)

Проверяем :

0 < 2 <

0 < 1 < − 1

Вычисляем

1 = 1

Вычисляем

2 = 2 1 × 1 2

Если 1 ≡ 2 подпись действительна

Ранее принято:

2 = 1 , 1 = 1 , 1 = 1 , 2 = 2 1 × 1 2

Заменим критерий 1 ≡ 2 на эквивалентный (подстановками)

1 ≡ 2 1 × 1 2 ≡ (1 ) 1 × (1 ) 2 ≡ 1 1+ 2

Поскольку 1 - первообразный корень, то можно доказать, что полученное сравнение справедливо тогда и только тогда, когда

Получен тот же результат, с которого начато подписание

Подписи, созданные с использованием алгоритма Elgamal называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи ( 1, 2), поскольку каждый раз будет использоваться новое значение

Экзистенциальная подделка. Перехвачена цифровая подпись 1 и 2

и подбирается ′, , удовлетворяющие сравнению

′ ≡ а × 1 + × 2 − 1

Селективная подделка. Имеется заданное сообщение М и требуется

Claus-Peter Schnorr

Шнорр предложил новую схему, основанную на схеме Эль-Гамаля , но с уменьшенным размером подписи

В процессе подписания две функции создают две части подписи. В процессе проверки выход одной функции сравнивается с первой частью подписи

Схема использует два модуля: p и q. Функции 1 и 3 используют p, а функция 2 использует q