Алгоритм DSA

Источники:
1. описание стандарта NIST FIPS PUB 186, "Digital Signature Standard", U.S. Department of Commerce, май 1994
2. Брюс Шнайер "Прикладная криптография", 2-е издание

DIGITAL SIGNATURE STANDARD (DSS) май 1994 г.
Стандарт цифровой подписи, в котором описан алгоритм DSA.

FIPS – Federal Information Processing Standard (Федеральный стандарт обработки информации)

Стандарт устанавливает алгоритм цифровой подписи (DSA) для приложений, требующих цифровой, а не рукописной подписи. Цифровая подпись DSA – это пара больших чисел, в компьютерном представлении – бинарные строки. Цифровая подпись вычисляется по определенному алгоритму (например, DSA) с определенными параметрами, такими, чтобы можно было бы проверить целостность данных и личность, подписавшего сообщение. DSA обеспечивает возможность создания и проверки подписей. Для создания цифровой подписи используется закрытый ключ, а для проверки подписи – открытый ключ, который соответствует (но не равен) закрытому ключу. Каждый пользователь обладает парой ключей – открытый и закрытый ключ. Открытые ключи считаются общедоступными. А закрытые ключи держатся в секрете. Любой может проверить подпись пользователя с использованием открытого ключа данного пользователя. Саму подпись может создать только обладатель закрытого ключа.

dsa00.jpg

Кстати, подписывается не все сообщение, а дайджест сообщения (сжатая версия подписываемых данных, хэш-значение). Дайджест сообщения является входным параметром алгоритма DSA. Цифровая подпись отправляется предназначенному верификатору вместе с подписанными данными (часто именуют сообщением). Верификатор проверяет подпись сообщения, используя открытый ключ отправителя. В процессе проверки должна использоваться та же хэш-функция, что и у отправителя. Хэш-функция задается в отдельном стандарте, Secure Hash Standard (SHS), FIPS 180 (стандарт описывает всем известный алгоритм SHA).

Параметры DSA.

Алгоритм DSA представляет собой вариант алгоритмов подписи Шнорра и Эль-Гамаля. В алгоритме используются следующие параметры:

p = простое число длиной L бит, где L принимает значения, кратное 64, в диапазоне от 512 до 1024. (В первоначальном стандарте размер p был фиксирован и равен 512 битам. Это ограничение вызвало множество критических замечаний, и NIST отменил его в FIPS PUB 186).
q – 160-битный простой множитель (p-1).

g = h(p-1)/q mod p, где h– любое число, меньшее (p-1), для которого h(p-1)/q mod p больше 1.

x – случайное или псевдослучайное число 0 < x < q.

y = gx mod p

В алгоритме также используется однонаправленная хэш-функция: H(m). Стандарт определяет использование алгоритма SHA. Первые три параметра: p,q,g открыты и могут быть общими для пользователей сети. Закрытым ключом является x, а открытым – y.

Создание и проверка подписи

Чтобы подписать сообщение m:

  1. Алиса генерирует случайное число 0 < k < q.
  2. Алиса генерирует:

      r = (gk mod p) mod q
      s = (k-1 * (H(m)+xr)) mod q
      k-1 – это обратное число k по модулю q, т.е. k-1 * k mod q = 1
      Как вариант, можно ввести дополнительную проверку на случай, если r = 0 или s = 0. Если r = 0 или s = 0, то надо создать новое значение k и подпись пересчитать (хотя такой случай, что r = 0 или s = 0, крайне маловероятен).

  1. Ее подписью служат параметры r и s, которые она посылает (вместе с сообщением) Бобу
  2. Боб проверяет подпись, вычисляя

      w = s-1 mod q
      u1 = (H(m) * w) mod q
      u2 = (rw) mod q
      Используя открытый ключ y, считаем параметр v:
      v = gu1 * yu2 mod p mod q
      Если v == r, то подпись правильная.

Открытый ключ:
p - простое число длиной от 512 до 1024 бита (может использоваться группой пользователей)
q - 160-битовый простой множитель (p-1) (может использоваться группой пользователей)
g (может использоваться группой пользователей)
y = gx mod p

Закрытый ключ:
x < q

Доказательство v == r

Лемма. Пусть p и q простые числа, такие, что q множитель (p-1), h положительное целое число, меньшее p, и g = h(p-1)/q mod p. Тогда gq mod p = 1, и если m mod q = n mod q, то gm mod p = gn mod p.

Доказательство:
Используя малую теорему Ферма, мы получим
gq mod p = (h(p- 1)*q/q mod p) mod p = h(p-1) mod p = 1
Пусть теперь m mod q = n mod q, т.е. m = n + kq для некоторого целого k. Тогда
gm mod p = g(n+kq) mod p = (gn * gkq) mod p = ((gn mod p) * (gq mod p)k) mod p = ((gn mod p) * 1k) mod p = gn mod p.
Теперь мы готовы доказать основную теорему.

Теорема. Пусть у нас есть сообщение отправителя M и его подпись r и s. Доказать, что v = r.

Доказательство: Мы вычисляем
w = s-1 mod q
u1 = ((SHA(M))*w) mod q
u2 = (r*w) mod q
Теперь y = gx mod p, так что по лемме,
v = ((gu1 * yu2) mod p) mod q
= ((gSHA(M)w * yrw) mod p) mod q
= ((gSHA(M)w * gxrw) mod p) mod q
= (g(SHA(M)+xr)w mod p) mod q
Т.к. s = (k-1*(SHA(M) + xr)) mod q
Следовательно, w = s-1 mod q = (k * (SHA(M) + xr)-1) mod q
k mod q = (SHA(M) + xr) * w mod q
Таким образом, по лемме
v = (g(SHA(M)+xr)w mod p) mod q = (gk mod p) mod q = r

Атаки на DSA

Атаки, направленные на k [1]

Для каждой подписи нужно новое значение k, которое должно выбираться случайным образом. Если Ева узнает значение k, которое Алиса использовала для подписи сообщения, быть может, воспользовавшись некоторыми свойствами генератора случайных чисел, выдающего k, она сможет взломать закрытый ключ Алисы х. Если Ева добудет два сообщения, подписанные с помощью одного и того же k, то, даже не зная значение k, она сможет раскрыть х. А спомощью х Ева сможет тайно подделывать подпись Алисы. В любой реализации DSA для безопасности системы очень важен хороший генератор случайных чисел.

Опасности общих модулей

Хотя DSS не определяет применение пользователями общего модуля, различные реализации могут воспользоваться такой возможностью. Например, Налоговое управление рассматривает возможность применения DSS для электронного подтверждения налоговых деклараций. Что, если организация потребует, чтобы все налогоплательщики страны использовали общие p и q? Общий модуль слишком легко становится мишенью для криптоанализа. Пока слишком рано обсуждать различные реализации DSS, но причины для беспокойства есть.

Скрытый канал в DSA

Густавус Симмонс (Gustavus Simmons) обнаружил в DSA скрытый канал [2]. Этот скрытый канал позволяет встраивать в подпись тайное сообщение, которое может быть прочитано только тем, у кого есть ключ. Согласно Симмонсу, это «знаковое совпадение», что «все очевидные недостатки скрытых каналов, использующих схему Эль-Гамаля, могут быть устранены» в DSS, и что DSS «на сегодня обеспечивает наиболее подходящую среду для скрытых коммуникаций». Организации NIST и АНБ не комментировали этот скрытый канал, никто даже не знает, догадывались ли они о такой возможности. Т.к. этот скрытый канал позволяет при недобросовестной реализации DSS передавать с каждой подписью часть закрытого ключа, никогда не пользуйтесь реализацией DSS, если вы не доверяете разработчику реализации.

Уязвимая хэш-функция

По стандарту используемая хэш-функция должна быть – SHA. Но в некоторых реализациях DSA разработчики могут заменить SHA на другой алгоритм хэширования или, что еще хуже, на нечто самопальное. Тогда возникает возможность получить коллизию хэш-значения для сообщения, а значит, подделать подпись. Такой пример рассматривается в crackme MR.HAANDI – WeakDSA

Библиография
1. Vaudenay, Serge: The Security of DSA and ECDSA. In Desmedt, Yvo (editor): Public Key Cryptography, volume 2567 of Lecture Notes in Computer Science, pp 309–323.
2. G.J.Simmons, “Subliminal Communication is Easy Using the DSA”, Advances in Cryptology – EUROCRYPT ’93 Proceedings, Springer-Verlag, 1994, pp 218-232
Криптографические примитивы
Алгоритмы с открытым ключом RSA DSA
Поточные шифры RC4
Хэш-функции RIPEMD-160 SHA-1/2
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License