Lecture_11_1
.pdfВыбирается простое число , которое обычно равно по длине 1024 битам
Выбирается другое простое число , которое имеет тот же самый размер, что и дайджест (например, 160 битов),такое , что
− 1 = 0
Выбирается 1, такое, что 1 = 1 путем вычисления 1 =0 −1/ , где 0 первообразный корень
Выбирается целое < и вычисляется 2 = 1
Объявляется открытый ключ (1, 2, , ) Назначается закрытый ключ
Выбирается случайное число , 1 << ( заново выбирается для каждого нового сообщения)
Вычисляется первая часть подписи
1 = 1 )
Вычисляется вторая часть подписи
2 = + × 1 |
|
Вычисляется
= 1 2 × 2−1 )
Если ≡ 1 , то подпись действительна
Все атаки на схему Эль-Гамаля могут быть применены к схеме Шнорра
Однако схема Шнорра находится в лучшем положении,
потому что 1 = 1 ) т.е. хэш-функция применяется к комбинации сообщение и 1 , в которой является секретным.
Стандарт цифровой подписи (DSS) принятый NIST в 1994 г.
В процессе подписания две функции 1 и 2создают две части подписи. В процессе проверки выход функции 3 сравнивается с первой частью подписи. Это подобно схеме Шнорра
Эта схема использует дайджест сообщения (не само сообщение), как часть входов к функциям 1 и 3
Схема применяет два общедоступных модуля: p и q. Функции 1 и 3 используют оба модуля p и q, функция 2 - только q
Выбирается простое число , длиной между 512 и 1024 битами. Число битов в p должно быть кратно 64
Выбирается другое простое число , которое имеет тот же самый размер дайджеста 160 битов, такое , что
− 1 = 0
Выбирается 1, такое, что 1 = 1 путем вычисления 1 =0 −1/ , где 0 первообразный корень (теорема Ферма)
Выбирается целое < и вычисляется 2 = 1
Объявляется открытый ключ (1, 2, , ) Назначается закрытый ключ
Выбирается случайное число , 1 << ( заново выбирается для каждого нового сообщения)
Вычисляется первая часть подписи
1 = (1 )
Вычисляется дайджест ( ) Вычисляется вторая часть подписи
|
= ( ) + × |
× −1 |
2 |
1 |
|
Проверяем :
0 < 2 <
0 < 1 <
Вычисляем
|
|
|
|
1 |
|
|
= |
|
2 |
× 2 |
|
|
|
|
1 |
|
2 |
|
|
|
Если V ≡ 1 подпись действительна
Вычисление DSA подписи быстрее, чем вычисление подписей RSА, при использовании того же самого p
DSA подпись короче, чем подписи в схеме Эль-Гамаля и Шнорра, потому что q меньше, чем p
Одним из главных аргументов против DSA является то, что, в отличие от общей задачи вычисления дискретного логарифма, ее частный случай, использованный в данной схеме, мало изучен и, возможно, имеет существенно меньшую сложность вскрытия