Алгоритм цифровой подписи DSA

Алгоритм цифровой подписи DSA (Digital Signature Algorithm) был предложен в 1991 году Национальным институтом стандартов и технологии США (National Institute of Standards and Technology - NIST) и стал стандартом США в 1993 году. Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К. Шнорра [10, 59]. Ниже приводятся процедуры генерации ключей, генерации подписи и проверки подписи в алгоритме DSA

Генерация ключей DSA

Отправитель и получатель электронного документа используют при вычислениях большие целые числа: g и р - простые числа, длиной L битов каждое (512 < L < 1024); q - простое число длиной 160 бит (делитель числа - 1). Числа g, р, q являются открытыми и могут быть общими для всех пользователей сети.

Отправитель выбирает случайное целое число х, 1 < х < q. Число х является секретным ключом отправителя для формирования электронной цифровой подписи.

Затем отправитель вычисляет значение

Число у является открытым ключом для проверки подписи отправителя. Число у передается всем получателям документов.

Генерация подписи DSA

Этот алгоритм предусматривает использование односторонней функции хэширования /?(•). В стандарте определен алгоритм безопасного хэширования SHA-1.

Для того чтобы подписать сообщение М, участник Л выполняет следующие шаги:

  • 1. Выбирает случайное целое к в интервале [1, q - 1 ].
  • 2. Вычисляет г = (g* mod р) mod q.
  • 3. Вычисляет k ' mod q.
  • 4. Вычисляет s = k '{h(M) + Л7'} mod q, где h есть алгоритм хэширования SHA-1.
  • 5. Если s = 0 тогда перейти к шагу 1. (Если s = 0, тогда s ' mod q не существует; s требуется на шаге 2 процедуры проверки подписи.)
  • 6. Подпись для сообщения М есть пара целых чисел (г, s).

Проверка подписи DSA

Для того чтобы проверить подпись (г, s) сообщения М от участника Л, участник В делает следующие шаги:

  • 1. Получает подлинную копию открытого ключа у участника Л.
  • 2. Вычисляет w =1 mod q и хэш-значение h(M).
  • 3. Вычисляет значения иЛ = h(M)w mod q и и2 = {т) mod q.
  • 4. Используя открытый ключ у, вычисляет значение

5. Признает подпись (г, л) под документом М подлинной, если v = г.

Поскольку г и х являются целыми числами, причем каждое меньше q, подписи DSA имеют длину 320 бит. Безопасность алгоритма цифровой подписи DSA базируется на трудностях задачи дискретного логарифмирования.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >