Digital Signature Standard

DSS, Digital Signature Standard
DSS, Digital Signature Standard
Создатель	Национальный институт стандартов и технологий
Создан	август 1991
Размер ключа	512—1024 бит
Размер подписи	два числа по 160 бит

DSS (Digital Signature Standard) — американский стандарт, описывающий Digital Signature Algorithm (DSA), который может быть использован для генерации цифровой подписи. Цифровая подпись служит для установления изменений данных и для установления подлинности подписавшейся стороны. Получатель подписанных данных может использовать цифровую подпись для доказательства третьей стороне факта, что подпись действительно сделана отправляющей стороной.

Введение[править | править код]

Когда получено сообщение, получатель может пожелать проверить, не изменили ли это сообщение при его передаче. Получатель также может захотеть проверить подлинность подписавшейся стороны. DSA дает возможность сделать это.

Использование DSA[править | править код]

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

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

Использование SHA вместе с DSA

Параметры DSA[править | править код]

DSA использует следующие параметры:

1. p – простое число p, где 2^L-1 < p < 2^L, 512 =< L =< 1024 и L кратно 64
2. q – простой делитель p-1, причем 2¹⁵⁹ < q < 2¹⁶⁰
3. g = h^(p-1)/q mod p, где h любое целое число 1 < h < p - 1 такое, что h^(p-1)/q mod p > 1
4. x – случайное или псевдослучайное целое число, где 0 < x < q
5. y = g^x mod p
6. k – случайное или псевдослучайное целое число, где 0 < k < q.

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

Генерация подписи[править | править код]

Подписью сообщения M является пара чисел r и s, где

r = (g^k mod p) mod q 
s = (k⁻¹(SHA(M) + xr)) mod q.

SHA(M) — 160-битная бинарная строка.

Если r = 0 или s = 0, должно быть сгенерировано новое k и вычислена новая подпись. Если подпись вычислялась правильно, вероятность того, что r = 0 или s = 0 очень мала.

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

Проверка подписи[править | править код]

Числа p, q, g и открытый ключ находятся в открытом доступе.

Пусть M', r' и s' — полученные версии M, r и s соответственно, и пусть y — открытый ключ. При проверке подписи сначала нужно посмотреть, выполняются ли следующие неравенства:

0 < r' < q 
0 < s' < q.

Если хотя бы одно неравенство не выполнено, подпись должна быть отвергнута. Если условия неравенств выполнены, производятся следующие вычисления:

w = (s')⁻¹ mod q 
u1 = ((SHA(M')w) mod q 
u2 = ((r')w) mod q 
v = (((g)^ul (y)^u2) mod p) mod q.

Если v = r', то подлинность подписи подтверждена.

Если v ≠ r', то сообщение могло быть изменено, сообщение могло быть неправильно подписано или сообщение могло быть подписано мошенником. В этом случае полученные данные следует рассматривать как поврежденные.

Генерация простых чисел для DSA[править | править код]

Этот раздел включает алгоритмы для генерации простых чисел p и q для DSA. В этих алгоритмах используется генератор случайных чисел.

Вероятностный тест на простоту[править | править код]

Для генерации простых p и q необходим тест на простоту. Есть несколько быстрых вероятностных тестов. В нашем случае будет использоваться упрощенная версия теста Миллера-Рабина. Если повторить тест n раз, он выдаст простое число с вероятностью ошибки не больше 1/4ⁿ. Для проверки целого числа на простоту нужно:

Шаг 1. Устанавливаем i = 1 и выбираем n>=50.
Шаг 2. Приравниваем w тестируемому числу и представляем его в виде w = 1 + 2^am, где m – нечетное число.
Шаг 3. Генерируем случайное число b: 1 < b < w. 
Шаг 4. Устанавливаем j = 0 и z = b^m mod w.
Шаг 5. Если j = 0 и z = 1, или если z = w - 1, то переходим на шаг 9. 
Шаг 6. Если j > 0 и z = 1, то переходим на шаг 8.
Шаг 7. j = j + 1. Если j < a, то устанавливаем z = z² mod w и переходим на шаг 5.
Шаг 8. w не простое. Стоп.
Шаг 9. Если i < n, то устанавливаем i = i + 1 и переходим на шаг 3. Иначе, возможно w – простое число.

Генерация простых чисел[править | править код]

Для DSS нужны 2 простых числа p и q, которые должны удовлетворять следующим условиям:

2¹⁵⁹ < q < 2¹⁶⁰ 
2^L-1 < p < 2^L, где L = 512 + 64j, причем 0 <= j < = 8 
p - 1 делится на q.

Для генерации простого q: 2¹⁵⁹ < q < 2¹⁶⁰ используется SHA-1 и начальное число SEED. После этого число SEED используется для создания числа X: 2^L-1 < X < 2^L. Простое p получается округлением X таким образом, чтобы полученное число было равно 1 mod 2q.

Пусть L — 1 = n*160 + b, где b и n целые и принимают значения от 0 до 160.

Шаг 1. Выбираем произвольную последовательность из как минимум 160 бит и называем её SEED. Пусть g – длина SEED в битах.
Шаг 2. Вычисляем U = SHA[SEED] XOR SHA[(SEED+1) mod 2^g ].
Шаг 3. Создаем q из U устанавливая младший и старший бит равным 1:
       q = U OR 2¹⁵⁹ OR 1.
       Заметим, что 2¹⁵⁹ < q < 2¹⁶⁰. 
Шаг 4. Проверяем q на простоту. 
Шаг 5. Если q непростое, переходим на шаг 1. 
Шаг 6. Пусть counter = 0 и offset = 2. 
Шаг 7. Для k = 0,...,n вычисляем Vk = SHA[(SEED + offset + k) mod 2^g].
Шаг 8. Вычисляем W = V₀ + V₁*2¹⁶⁰ + ... + V_n-1*2^(n-1)*160 + (V_n mod 2^b) * 2^n*160 
       X = W + 2^L-1. 
       Заметим, что 0 < = W < 2^L-1  и 2^L-1 < = X < 2^L. 
Шаг 9. Пусть c = X mod 2q и p = X - (c - 1). Заметим, что p равно 1 mod 2q. 
Шаг 10. Если p < 2^L-1, тогда переходим на шаг 13. 
Шаг 11. Проверяем p на простоту. 
Шаг 12. Если p прошло тест на 11 шаге, переходим на 15 шаг. 
Шаг 13. counter = counter + 1 и offset = offset + n + 1. 
Шаг 14. Если counter >= 2¹² = 4096 переходим на шаг 1, иначе переходим на шаг 7. 
Шаг 15. Сохраняем SEED и counter для  того, чтобы подтвердить правильную генерацию p и q.

Генерация случайных чисел для DSA[править | править код]

Для любой реализации DSA требуются случайные или псевдослучайные целые числа. Эти числа выбираются при помощи методов описанных в этом разделе или при помощи других одобреных FIPS методов.

Алгоритм в разделе 7.1 может быть использован для генерации x. Алгоритм для k и r описан в разделе 7.2. Алгоритмы используют одностороннюю функцию (функцию, обратное значение которой очень трудно вычислить) G(t, c), где t имеет размер 160 бит, c имеет размер b бит (160 < b < 512) и G(t, c) — 160 бит. G может быть создана с помощью Secure Hash Algorithm (SHA-1) или с помощью Data Encryption Standard (DES), описанные в разделах 7.3 и 7.4 соответственно.

Алгоритм для вычисления m значений числа x[править | править код]

Пусть x — секретный ключ подписывающей стороны. Следующий алгоритм можно использовать для генерации m значений числа x:

Шаг 1. Выбираем новое значение для исходного ключа, XKEY.
Шаг 2. В шестнадцатеричной системе счисления
t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0.
Это начальное значение для H₀||H₁||H₂||H₃||H₄ в SHS.
Шаг 3. Для j = 0..m - 1
       a. XSEED_j = опциональное значение, введенное пользователем.
       b. XVAL = (XKEY + XSEED_j) mod 2^b.
       c. x_j = G(t,XVAL) mod q.
       d. XKEY = (1 + XKEY + x_j) mod 2^b.

Алгоритм для предварительного вычисления k и r[править | править код]

Этот алгоритм может быть использован для предварительного вычисления k, k⁻¹ и r для m сообщений одновременно. Алгоритм:

Шаг 1. Выбирается секретное начальное значение для KKEY.
Шаг 2. В шестнадцатеричной системе счисления
t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301.
Это начальный сдвиг для H₀||H₁||H₂||H₃||H₄ в SHS.
Шаг 3. Для j = 0..m - 1:
       a. k = G(t,KKEY) mod q.
       b. Вычисляем k_j⁻¹ = k⁻¹ mod q.
       c. Вычисляем r_j = (g^k mod p) mod q.
       d. KKEY = (1 + KKEY + k) mod 2^b. 
Шаг 4. Предположим M₀, ... , M_m-1 - следующие m сообщений. Для j = 0..m - 1:
       a. Пусть h = SHA(M_j).
       b. s_j = (k_j⁻¹(h + xr_j)) mod q.
       c. r_j,s_j) - подпись для M_j. 
Шаг 5. t = h.
Шаг 6. Переходим на шаг 3.

Шаг 3 дает возможность вычислить величины, необходимые для подписи следующих m сообщений. Шаг 4 выполняться сразу после того, когда получены эти m сообщений.

Создание функции G при помощи SHA[править | править код]

G(t, c) может быть получена при помощи SHA-1, но перед этим {H_j} и M₁ должны быть инициализированы следующим образом:

1. Инициализируем {Hj} деление 160-битного значения t на пять 32-битных сегмента:
   t = t₀||t₁||t₂||t₃||t₄
   Тогда Hj = t_j для j = 0..4. 
2. Блок сообщения M₁ определяется следующим образом:
   M₁ = c||0^512-b
   (Первые b бит сообщения M₁ содержат c, а оставшиеся (512-b) бит устанавливаются нулями).

После этого выполняется SHA-1^[1] и получаем 160-битную строку G(t, c), представленную в виде:

H₀||H₁||H₂||H₃||H₄.

Создание функции G при помощи DES[править | править код]

Пусть a XOR b обозначает побитовое исключающее «ИЛИ» (сложение по модулю 2). Пусть a₁, a₂, b₁, b₂ — 32-строки. Пусть b₁' — 24 младших бита числа b₁. Пусть K = b₁'||b₂ и A = a₁||a₂. Обозначим

DES_b1,b2(a₁,a₂) = DES_K(A)

DES_K(A) обозначает обычное DES-шифрование^[2] 64-битного блока A при помощи 56-битного ключа K. Предположим, что t и c имеют размер 160 бит каждое. Для вычисления G(t, c):

Шаг 1. Записываем
       t = t₁||t₂||t₃||t₄||t₅
       c = c₁||c₂||c₃||c₄||c₅
       Каждое t_i и c_i имеет размер 32 бита. 
Шаг 2. Для i = 1..5:
       x_i = t_i XOR c_i 
Шаг 3. Для i = 1..5:
       b₁ = c_{((i+3) mod 5) + 1}
       b₂ = c_{((i+2) mod 5) + 1}
       a₁ = x_i
       a₂ = x_{(i mod 5) + 1} XOR x_{((i+3) mod 5) + 1}
       y_i,1||y_i,2 = DES_b1,b2(a₁,a₂) (y_i,1, y_i,2 = 32 бита)
Шаг 4. Для i = 1..5:
       z_i = y_i,1 XOR y_{((i+1) mod 5)+1,2} XOR y_{((i+2) mod 5)+1,1} 
Шаг 5. G(t,c) = z₁||z₂||z₃||z₄||z₅

Генерация других параметров[править | править код]

В этом разделе приведены алгоритмы для генерации g, k⁻¹ и s⁻¹, которые используются в DSS. Для генерации g:

Шаг 1. Генерация p и q описана выше.
Шаг 2. Пусть e = (p - 1)/q.
Шаг 3. Приравниваем h любому целому числу: 1 < h < p - 1.
Шаг 4. g = h^e mod p.
Шаг 5. Если g = 1, переходим на шаг 3.

Для вычисления n⁻¹ mod q, где 0 < n < q и 0 < n⁻¹ < q:

Шаг 1. i = q, h = n, v = 0 и d = 1.
Шаг 2. Пусть t = i DIV h, где DIV - целочисленное деление.
Шаг 3. x = h.
Шаг 4. h = i - tx.
Шаг 5. i = x.
Шаг 6. x = d.
Шаг 7. d = v - tx.
Шаг 8. v = x.
Шаг 9. Если h > 0, переходим на шаг 2.
Шаг 10. Пусть n⁻¹ = v mod q.

Заметим, что на шаге 10, v может быть отрицательным.

Пример DSA[править | править код]

Пусть L = 512 (размер p). В этом примере все величины будут в шестнадцатеричном представлении. Величины p и q были сгенерированы, как описано выше, используя следующее 160-битное значение SEED:

SEED = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3

С этим SEED, алгоритм нашел p и q в момент, когда counter = 105. x было сгенерировано при помощи алгоритма, описанного в разделе 7.1, с использованием SHA-1 для генерации G (раздел 7.3) 160-битный XKEY:

XKEY = bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6

t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0

x = G(t,XKEY) mod q

k было сгенерировано как описано в разделе 7.2 с использованием SHA-1 для генерации G (раздел 7.3) 160-битный KKEY:

KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584

t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301

k = G(t,KKEY) mod q

Окончательно:

h = 2

p = 8df2a494 492276aa 3d25759b b06869cb eac0d83a fb8d0cf7 cbb8324f 0d7882e5 
    d0762fc5 b7210eaf c2e9adac 32ab7aac 49693dfb f83724c2 ec0736ee 31c80291

q = c773218c 737ec8ee 993b4f2d ed30f48e dace915f

g = 626d0278 39ea0a13 413163a5 5b4cb500 299d5522 956cefcb 3bff10f3 99ce2c2e 
    71cb9de5 fa24babf 58e5b795 21925c9c c42e9f6f 464b088c c572af53 e6d78802

x = 2070b322 3dba372f de1c0ffc 7b2e3b49 8b260614

k = 358dad57 1462710f 50e254cf 1a376b2b deaadfbf

k⁻¹ = 0d516729 8202e49b 4116ac10 4fc3f415 ae52f917

M = слово «abc» из английского алфавита(ASCII)

(SHA-1)(M) = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

y = 19131871 d75b1612 a819f29d 78d1b0d7 346f7aa7 7bb62a85 9bfd6c56 75da9d21 
    2d3a36ef 1672ef66 0b8c7c25 5cc0ec74 858fba33 f44c0669 9630a76b 030ee333

r = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0

s = 41e2345f 1f56df24 58f426d1 55b4ba2d b6dcd8c8

w = 9df4ece5 826be95f ed406d41 b43edc0b 1c18841b

u₁ = bf655bd0 46f0b35e c791b004 804afcbb 8ef7d69d

u₂ = 821a9263 12e97ade abcc8d08 2b527897 8a2df4b0

g^u1 mod p = 51b1bf86 7888e5f3 af6fb476 9dd016bc fe667a65 aafc2753 9063bd3d 2b138b4c 
            e02cc0c0 2ec62bb6 7306c63e 4db95bbf 6f96662a 1987a21b e4ec1071 010b6069

y^u2 mod p = 8b510071 2957e950 50d6b8fd 376a668e 4b0d633c 1e46e665 5c611a72 e2b28483 
            be52c74d 4b30de61 a668966e dc307a67 c19441f4 22bf3c34 08aeba1f 0a4dbec7

v = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0

Примечания[править | править код]

↑ FIPS PUB 180-1 (англ.). — описание стандарта SHS. Архивировано из оригинала 7 апреля 2012 года.
↑ FIPS PUB 46-3 (англ.). — описание стандарта DES. Архивировано из оригинала 7 апреля 2012 года.

Ссылки[править | править код]

Зарубежные[править | править код]

FIPS-186 (англ.). — the first version of the official DSA specification. Архивировано из оригинала 7 апреля 2012 года.
FIPS-186, change notice No.1 (англ.). — the first change notice to the first version of the specification. Архивировано из оригинала 7 апреля 2012 года.
FIPS-186-1 (англ.). — the first revision to the official DSA specification. Архивировано из оригинала 7 апреля 2012 года.
FIPS-186-3 (англ.). — the third revision to the official DSA specification. Архивировано из оригинала 7 апреля 2012 года.
FIPS-186-4 (англ.). — the fourth and current revision to the official DSA specification. Архивировано 27 декабря 2016 года.

FIPS-186-3 Approval (англ.). — approval announcement of the third revision to the official DSA specification. Архивировано из оригинала 7 апреля 2012 года.
Recommendation for Key Management -- Part 1: general (англ.). — NIST Special Publication 800-57, p. 62–63. Архивировано 21 августа 2005 года.

Русские[править | править код]

Алгоритм DSA (рус.). — краткое описание алгоритма DSA. Архивировано из оригинала 6 января 2013 года.

Реализация[править | править код]

DSA-методы (рус.). — описание методов DSA-класса из библиотеки классов платформы .NET Framework. Архивировано из оригинала 7 апреля 2012 года.

[1] FIPS PUB 180-1 (англ.). — описание стандарта SHS. Архивировано из оригинала 7 апреля 2012 года.

[2] FIPS PUB 46-3 (англ.). — описание стандарта DES. Архивировано из оригинала 7 апреля 2012 года.

[1]

[2]

Digital Signature Standard

Содержание

Введение[править | править код]

Использование DSA[править | править код]

Параметры DSA[править | править код]

Генерация подписи[править | править код]

Проверка подписи[править | править код]

Генерация простых чисел для DSA[править | править код]

Вероятностный тест на простоту[править | править код]

Генерация простых чисел[править | править код]

Генерация случайных чисел для DSA[править | править код]

Алгоритм для вычисления m значений числа x[править | править код]

Алгоритм для предварительного вычисления k и r[править | править код]

Создание функции G при помощи SHA[править | править код]

Создание функции G при помощи DES[править | править код]

Генерация других параметров[править | править код]

Пример DSA[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Зарубежные[править | править код]

Русские[править | править код]

Реализация[править | править код]

Навигация

Digital Signature Standard

Введение[править | править код]

Использование DSA[править | править код]

Параметры DSA[править | править код]

Генерация подписи[править | править код]

Проверка подписи[править | править код]

Генерация простых чисел для DSA[править | править код]

Вероятностный тест на простоту[править | править код]

Генерация простых чисел[править | править код]

Генерация случайных чисел для DSA[править | править код]

Алгоритм для вычисления m значений числа x[править | править код]

Алгоритм для предварительного вычисления k и r[править | править код]

Создание функции G при помощи SHA[править | править код]

Создание функции G при помощи DES[править | править код]

Генерация других параметров[править | править код]

Пример DSA[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Зарубежные[править | править код]

Русские[править | править код]

Реализация[править | править код]

Навигация

Поиск