Lecture_11_1
.pdfВпроцессе подписания две функции 1 и 2 создают две части подписи
Впроцессе подтверждения выходы двух функций 1 и 3 сравниваются между собой
Сообщение присутствует на входе 2 , при подписании, а также часть входа к функции 1 при подтверждении
Вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 - по модулю
p - 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 - первообразный корень, то можно доказать, что полученное сравнение справедливо тогда и только тогда, когда
M ≡ |
1 + 2 |
− 1 , поэтому |
|
≡ |
− × |
× −1 ( − 1) |
|
2 |
|
1 |
|
Получен тот же результат, с которого начато подписание
Подписи, созданные с использованием алгоритма Elgamal называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи ( 1, 2), поскольку каждый раз будет использоваться новое значение
Экзистенциальная подделка. Перехвачена цифровая подпись 1 и 2
и подбирается ′, , удовлетворяющие сравнению
′ ≡ а × 1 + × 2 − 1
Селективная подделка. Имеется заданное сообщение М и требуется
подобрать две части подписи 1 и 2 . Выбираем 1 и пытаемся |
||||||||
вычислить |
|
× |
2 |
≡ |
|
. Это вычислительно |
||
из 1 |
|
|
||||||
|
|
2 |
2 |
1 |
|
1 |
|
|
трудная задача дискретного логарифмирования |
||||||||
|
≡ |
|
− 1 × |
|
|
|
||
2 |
1 |
2 |
1 |
|
|
|
|
|
Claus-Peter Schnorr
Шнорр предложил новую схему, основанную на схеме Эль-Гамаля , но с уменьшенным размером подписи
В процессе подписания две функции создают две части подписи. В процессе проверки выход одной функции сравнивается с первой частью подписи
Схема использует два модуля: p и q. Функции 1 и 3 используют p, а функция 2 использует q