DSA

DSA, Digital Signature Algorithm
Создатель:	NIST
Создан:	1991 год
Опубликован:	1994 год
Размер ключа:	закрытый: 160-256 бит, открытый: 1024-3072 бит
Размер подписи:	два числа по 160-256 бит

Эта статья включает описание термина «DSA»; о значении Dsa см. Классификация климатов Кёппена.

DSA (Digital Signature Algorithm) — алгоритм с использованием открытого ключа для создания электронной подписи, но не для шифрования (в отличие от RSA и схемы Эль-Гамаля). Подпись создается секретно, но может быть публично проверена. Это означает, что только один субъект может создать подпись сообщения, но любой может проверить её корректность. Алгоритм основан на вычислительной сложности взятия логарифмов в конечных полях.

Алгоритм был предложен Национальным институтом стандартов и технологий (США) в августе 1991 и является запатентованным U.S. Patent 5 231 668, но НИСТ сделал этот патент доступным для использования без лицензионных отчислений. Алгоритм вместе с криптографической хеш-функцией SHA-1 является частью DSS (Digital Signature Standard), впервые опубликованного в 1994 (документ FIPS-186 (Federal Information Processing Standards)[1]). Позднее были опубликованы 2 обновленные версии стандарта: FIPS 186-2[2] (27 января 2000 года) и FIPS 186-3[3] (июнь 2009).

Использование алгоритма

Для подписывания сообщений необходима пара ключей — открытый и закрытый. При этом закрытый ключ должен быть известен только тому, кто подписывает сообщения, а открытый — любому желающему проверить подлинность сообщения. Также общедоступными являются параметры самого алгоритма. Для обеспечения такого доступа достаточно авторитетная организация (или несколько организаций) поддерживает базу соответствия между реальными реквизитами автора (это может быть как частное лицо, так и организация) и открытыми ключами, а также всеми необходимыми параметрами схемы цифровой подписи (используемая хеш-функция). Эта организация также выдает цифровые сертификаты.

Параметры схемы цифровой подписи

Для построения системы цифровой подписи нужно выполнить следующие шаги:

1. Выбор криптографической хеш-функции H(x).
2. Выбор большого простого числа q, размерность которого N в битах совпадает с размерностью в битах значений хэш-функции H(x).
3. Выбор простого числа p, такого, что (p-1) делится на q. Битовая длина p обозначается L ($2^{L-1} < p < 2^{L}$).
4. Выбор числа g такого, что его мультипликативный порядок по модулю p равен q. Для его вычисления можно воспользоваться формулой $g = h^{(p-1)/q}\mod p$, где h — некоторое произвольное число, $h \in (1; p - 1)$ такое, что $g \neq 1$. В большинстве случаев значение h = 2 удовлетворяет этому требованию.

Как упомянуто выше, а также в DSS (Digital Signature Standard), первоочередным параметром схемы цифровой подписи является используемая криптографическая хеш-функция, необходимая для преобразования текста сообщения в число, которое собственно и будет подписано. Важной характеристикой этой функции является битовая длина выходной последовательности, обозначаемая далее N (160 для функции SHA-1). В первой версии стандарта DSS рекомендована функция SHA-1 и, соответственно, битовая длина подписываемого числа 160 бит. Сейчас SHA-1 уже не является достаточно безопасной. В стандарте указаны следующие возможные пары значений чисел L и N:

1. L = 1024, N = 160
2. L = 2048, N = 224
3. L = 2048, N = 256
4. L = 3072, N = 256

В соответствии с этим рекомендованы хеш-функции семейства SHA-2. Правительственные организации должны использовать один из этих вариантов, но все другие вольны выбирать. Проектирующий систему может выбрать любую хеш-функцию. Поэтому далее не будет заостряться внимание на использовании конкретной хеш-функции. Стойкость криптосистемы на основе DSA не превосходит стойкость используемой хеш-функции и стойкость пары (L,N), чья стойкость не больше стойкости каждого из чисел по отдельности. Ранее рекомендовалась длина p L = 1024 бита. В данный момент для систем, которые должны быть стойкими до 2010 (2030) года, рекомендуется длина в 2048 (3072) бита.

Открытый и секретный ключи

1. Секретный ключ представляет собой число $x \in (0, q)$
2. Открытый ключ вычисляется по формуле $y=g^x \mod p$

Открытыми параметрами являются числа (p, q, g, y). Закрытый параметр только один — число x. При этом числа (p, q, g) могут быть общими для группы пользователей, а числа x и y являются соответственно закрытым и открытым ключами конкретного пользователя. При подписании сообщения используются секретные числа x и k, причем число k должно выбираться случайным образом (на практике псевдослучайным) при подписывании каждого следующего сообщения.

Поскольку (p, q, g) могут быть использованы для нескольких пользователей, на практике часто делят пользователей по некоторым критериям на группы с одинаковыми (p, q, g). Поэтому эти параметры называют доменными параметрами (Domain Parameters).

Подпись сообщения

Подпись сообщения выполняется по следующему алгоритму:

1 Выбор случайного числа $k \in (0,q)$
2 Вычисление $r=(g^k \mod p)\mod q$
3 Вычисление $s=k^{-1}(H(m)+x\cdot r)\mod q$
4 Выбор другого k, если оказалось, что r=0 или s=0

Подписью является пара чисел (r, s), общая длина подписи 2*N.

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

Проверка подписи выполняется по алгоритму:

1 Вычисление $w=s^{-1} \mod q$
2 Вычисление $u_1 = H(m)\cdot w \mod q$
3 Вычисление $u_2 = r\cdot w \mod q$
4 Вычисление $v = (g^{u_1}\cdot y^{u_2} \mod p) \mod q$

Подпись верна, если v = r

Корректность схемы

Данная схема цифровой подписи корректна в той степени, что желающий проверить подлинность подписи всегда получит положительный результат в случае подлинности. Покажем это:

Во-первых, если $g=h^{(p-1)/q} \mod p$, то из этого по Малой теореме Ферма следует $g^q=h^{p-1}=1 \mod p$. Поскольку g>1 и q простое число, то g должно иметь мультипликативный порядок q по модулю p.

Для подписи сообщения вычисляется

$s=k^{-1}(H(m)+x \cdot r) \mod{q}.$

Из этого следует

$k=H(m) \cdot s^{-1}+x \cdot r \cdot s^{-1}=H(m) \cdot w + x \cdot r \cdot w \mod{q}.$

Так как g имеет порядок q, получим

$g^k=g^{H(m) \cdot w \mod q}g^{x \cdot r \cdot w \mod q}=g^{H(m) \cdot w \mod q}y^{r \cdot w \mod q}=g^{u1}y^{u2} \mod{p}.$

Наконец, корректность схемы DSA следует из

$r=(g^k \mod p) \mod q=(g^{u1}y^{u2} \mod p) \mod q=v.$

Поскольку фактически подписывается не само сообщение, а его хеш, то очевидно, что несколько различных сообщений могут иметь одинаковую подпись. Это связано с наличием у хеш-функций коллизий (существуют множества сообщений такие, что внутри каждого такого множества хеш-значения элементов совпадают).

Реализация алгоритма

Поскольку НИСТ сделал алгоритм свободным к использованию, то алгоритм можно свободно реализовывать программным, аппаратным или любым другим образом. НИСТ разработал программу проверки соответствия реализации алгоритма стандарту. Информация об этой системе доступна в документе [4]. Примеры работы алгоритма имеются в этом документе[5]. Реализации систем цифровой подписи должны использовать криптографические алгоритмы, алгоритмы генерации криптографических ключей и способы распределения ключей, безопасность которых так или иначе подтверждена. К таким алгоритмам и методам относятся алгоритмы и методы:

1. описанные в документах FIPS (Federal Information Processing Standard)
2. принятые в рекомендациях FIPS или NIST
3. указанные в списке функций с подтвержденной безопасностью в документе FIPS 140-2.

Система проверки реализации алгоритма

Для определения соответствия реализации стандарту создана система для проверки реализации алгоритма (The Digital Signature Algorithm Validation System (DSAVS)). Система включает 5 отдельных тестов для проверки каждой из частей системы подписи, так что каждая компонента системы может быть протестирована на соответствие стандарту независимо от другой. Тестируемые компоненты реализации:

1. Генерация доменных параметров
2. Проверка доменных параметров
3. Генерация пары открытый-закрытый ключ
4. Создание подписи
5. Проверка подписи

Для проведения проверки реализации, разработчик должен подать соответствующую заявку на тестирование его реализации в авторизованную лабораторию тестирования криптографических модулей (Cryptographic Module Testing Laboratory (CMT laboratory)). Реализация, на проверку которой подана заявка, называется тестируемой реализацией (Implementation Under Test (IUT)). Запрос на тестирование реализации наряду со специфической информацией, необходимой для проведения тестов, содержит общую информацию о разработчике и тестируемой реализации. А именно, следующую информацию:

1. Товарный знак разработчика
2. Название продукта, содержащего реализацию
3. Версия этого продукта
4. Способ реализации (программно, аппаратно, программно-аппаратно)
5. Поддерживаемая конфигурация оборудования и операционная система (в случае программной или программно-аппаратной реализации)
6. Краткое описание тестируемой реализации или продукта (семейства продуктов), в котором производитель реализовал тестируюмую систему (2-3 предложения)
7. Поддерживаемые размеры числа p
8. поддерживаемые значения доменных параметров, если реализация работает только с конкретными значениями доменных параметров

Генерация псевдопростых чисел для использования в алгоритме

При работе алгоритма DSA требуется два простых числа (p и q), следовательно необходим генератор псевдослучайных псевдопростых чисел. В соответствии с DSS псевдопростые числа должны генерироваться с помощью методов, безопасность которых подтверждена в документах FIPS. Один из таких методов описан в дополнении к документу FIPS 186. При этом для проверки на простоту рекомендовано использовать вероятностный тест Миллера — Рабина (в соответствии с FIPS 186 рекомендовано число итераций 50).

Простые числа должны удовлетворять условиям:

1. $2^{N - 1} < q < 2^{N}$
2. $2^{L-1} < p < 2^{L}$
3. $(p-1)$ делится на $q$

Для генерации обоих чисел используется начальное число (SEED), которое может определяться уникальными данными домена, для которого планируется генерация доменных параметров, или быть случайным.

Рекомендованный алгоритм генерации

Пусть L представлена в виде $L - 1 = n*N + b$, где n и b — целые числа, причем b лежит в диапазоне от 0 включая до N. Генерация псевдопростых чисел p и q выполняется следующим образом:

1. Выбор битовой последовательности длиной от N, далее обозначаемой SEED. Обозначим длину этой последовательности в битах seedlen.
2. Вычисляем $U=H(SEED) \oplus H(SEED+1 \mod 2^{seedlen})$
3. Формирование числа q из числа U путем выставления младшего и старшего значащих бит в 1. Что значит побитовое булево сложение с числами 1 и $2^{N-1}$. Заметим, что при этом $2^{N-1} < q < 2^{N}$. 
4. Проверка, является ли полученное q простым.
5. Если окажется, что q составное, то переход на шаг 1
6. Введем переменные counter = 0 и offset = 2. 
7. Для всех k = 0,...,n вычислим $V_k = H(SEED + offset + k \mod 2^{seedlen})$.
8. Введем целое число $W = V_0 + V_1*2^{N} + ... + V_{n-1}*2^{(n-1)*N} + (V_n \mod 2b) * 2^{n*N}$ и число $X = W + 2^{L-1}$. Отметим, что $0 <= W < 2^{L-1}$, следовательно $2^{L-1} <= X < 2L$. 
9. Пусть $c = X \mod 2q$ и $p = X - (c - 1)$. При этом $p=1 \mod 2q$. 
10. Если $p < 2^{L-1}$, то переходим на шаг 13. 
11. Проверка p на простоту. 
12. Если p проходит тест на простоту, то переходим на шаг 15.
13. Выполнение операций counter = counter + 1 и offset = offset + n + 1. 
14. Если $counter >= 2^{12} = 4096$, то переходим на шаг 1, иначе переход на шаг 7. 
15. Запоминаем значения SEED и counter для последующего использования (чтобы удостовериться в правильной генерации p и q).

Генерация псевдослучайных чисел для использования в алгоритме

Для работы алгоритма требуется также генератор случайных или псевдослучайных чисел. Этот генератор нужен для создания частного пользовательского ключа (x), а также для создания секретного случайного числа k, которое вырабатывается заново для подписи каждого документа. Как и простые числа p и q, эти случайные или псевдослучайные числа должны быть получены с помощью алгоритмов, безопасность которых подтверждена FIPS. Один из таких методов описан в дополнении C к стандарту ANSI X9.17 (Financial Institution Key Management (Wholesale)). Далее описываются методы, приведенные в дополнении к стандарту DSS (документ FIPS 186[6]).
Эти алгоритмы используют одностороннюю функцию G(t, c), где t — это N-битное число, c — b-битное, а результат функции G(t, c) — N-битное. Один из способов построения такой функции — использование хеш-функции. Другой метод — использовать алгоритм симметричного шифрования. Эти методы для случая использования SHA-1 (N = 160) описаны в документе FIPS-186.

Способ получения $m$ значений секретного ключа

1. Выбор секретного значения XKEY 
2. Число t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 (в шестнадцатеричной записи)
3. Цикл по j с 0 до m - 1
 
   $XSEED_j =$<необязательное значение, может быть получено путем ввода пользователем>; 
   $XVAL = XKEY + XSEED_j \mod 2^b$; 
   $x_j = G(t,XVAL) \mod q$;
   $XKEY = 1 + XKEY + x_j \mod 2^b$;
 

Способ предварительного вычисления нескольких секретных значений k и r

1. Выбор секретного случайного значения KKEY. 
2. Число t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 (в шестнадцатеричной записи)
3. Цикл по j с 0 до m - 1
 
   $k = G(t,KKEY) \mod q$;
   $k_j^{-1} = k^{-1} \mod q$;
   $r_j = g^k \mod p \mod q$;
   $KKEY = 1 + KKEY + k \mod 2b$;
 
4. Обозначим следующие m сообщений как $M_0, ..., M_{m-1}$. Цикл по j от 0 до m - 1
 
   h = SHA(Mj);
   $s_j = k_j^{-1}(h + x \cdot r_j) \mod q$
   Цифровая подпись для $M_j$ - $(r_j,s_j)$;
 
5. t = h;
6. Переход к шагу 3;

Шаг 3 позволяет предварительно вычислить величины, необходимые для подписания следующих m сообщений. К шагу 4 можно переходить в любой момент, когда первое из этих m сообщений имеется в наличии. Когда следующее сообщение еще не доступно, исполнение шага 4 может быть приостановлено. Как только этапы 4 и 5 завершились, можно перейти к исполнению этапа 3 для работы со следующей группой из m сообщений. Кроме памяти для KKEY, необходимо выделить память для хранения двух массивов длины m (один массив для значений $r_0, ..., r_{m-1}^{}$ и второй для чисел $k_0^{-1}, ...,k_{m-1}^{-1}$), полученных на этапе 3. Память для чисел $s_0, ..., s_{m-1}^{}$ надо выделять только если необходим сохранять подписи для группы сообщений, иначе же $s_j$ на этапе 4 могут быть заменены на одну переменную s.

См. также

• Электронная цифровая подпись
• Схема Эль-Гамаля
• RSA
• ECDSA
• ГОСТ Р 34.10-2001
• Случайное простое число

Ссылки

• FACT SHEET ON DIGITAL SIGNATURE STANDARD

Ссылки на стандарты (англоязычные)

• Announcing the Standard for Digital Signature Standard (FIPS PUB 186)
• FIPS PUB 186-2
• FIPS PUB 186-3
• Digital Signature Algorithm Validation System
• FIPS PUB 140-2 (Security Requirements for Cryptographic Modules)
• FIPS PUB 180-3 (Secure Hash Standard)