Digital Signature Standard

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
DSS, Digital Signature Standard
Создатель:

Национальный институт стандартов и технологий

Создан:

август 1991

Опубликован:

19 мая 1994

Размер ключа:

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, где 2L-1 < p < 2L, 512 =< L =< 1024 и L кратно 64
2. q – простой делитель p-1, причем 2159 < q < 2160
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 = gx mod p
6. k – случайное или псевдослучайное целое число, где 0 < k < q.

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

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

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

r = (gk mod p) mod q 
s = (k−1(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')−1 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/4n. Для проверки целого числа на простоту нужно:

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

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

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

2159 < q < 2160 
2L-1 < p < 2L, где L = 512 + 64j, причем 0 <= j < = 8 
p - 1 делится на q.

Для генерации простого q: 2159 < q < 2160 используется SHA-1 и начальное число SEED. После этого число SEED используется для создания числа X: 2L-1 < X < 2L. Простое 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 2g ].
Шаг 3. Создаем q из U устанавливая младший и старший бит равным 1:
       q = U OR 2159 OR 1.
       Заметим, что 2159 < q < 2160. 
Шаг 4. Проверяем q на простоту. 
Шаг 5. Если q непростое, переходим на шаг 1. 
Шаг 6. Пусть counter = 0 и offset = 2. 
Шаг 7. Для k = 0,...,n вычисляем Vk = SHA[(SEED + offset + k) mod 2g].
Шаг 8. Вычисляем W = V0 + V1*2160 + ... + Vn-1*2(n-1)*160 + (Vn mod 2b) * 2n*160 
       X = W + 2L-1. 
       Заметим, что 0 < = W < 2L-1  и 2L-1 < = X < 2L. 
Шаг 9. Пусть c = X mod 2q и p = X - (c - 1). Заметим, что p равно 1 mod 2q. 
Шаг 10. Если p < 2L-1, тогда переходим на шаг 13. 
Шаг 11. Проверяем p на простоту. 
Шаг 12. Если p прошло тест на 11 шаге, переходим на 15 шаг. 
Шаг 13. counter = counter + 1 и offset = offset + n + 1. 
Шаг 14. Если counter >= 212 = 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.
Это начальное значение для H0||H1||H2||H3||H4 в SHS.
Шаг 3. Для j = 0..m - 1
       a. XSEEDj = опциональное значение, введенное пользователем.
       b. XVAL = (XKEY + XSEEDj) mod 2b.
       c. xj = G(t,XVAL) mod q.
       d. XKEY = (1 + XKEY + xj) mod 2b.

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

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

Шаг 1. Выбирается секретное начальное значение для KKEY.
Шаг 2. В шестнадцатеричной системе счисления
t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301.
Это начальный сдвиг для H0||H1||H2||H3||H4 в SHS.
Шаг 3. Для j = 0..m - 1:
       a. k = G(t,KKEY) mod q.
       b. Вычисляем kj−1 = k−1 mod q.
       c. Вычисляем rj = (gk mod p) mod q.
       d. KKEY = (1 + KKEY + k) mod 2b. 
Шаг 4. Предположим M0, ... , Mm-1 - следующие m сообщений. Для j = 0..m - 1:
       a. Пусть h = SHA(Mj).
       b. sj = (kj−1(h + xrj)) mod q.
       c. rj,sj) - подпись для Mj. 
Шаг 5. t = h.
Шаг 6. Переходим на шаг 3.

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

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

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

1. Инициализируем {Hj} деление 160-битного значения t на пять 32-битных сегмента:
   t = t0||t1||t2||t3||t4
   Тогда Hj = tj для j = 0..4. 
2. Блок сообщения M1 определяется следующим образом:
   M1 = c||0512-b
   (Первые b бит сообщения M1 содержат c, а оставшиеся (512-b) бит устанавливаются нулями). 

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

H0||H1||H2||H3||H4.

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

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

DESb1,b2(a1,a2) = DESK(A)

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

Шаг 1. Записываем
       t = t1||t2||t3||t4||t5
       c = c1||c2||c3||c4||c5
       Каждое ti и ci имеет размер 32 бита. 
Шаг 2. Для i = 1..5:
       xi = ti XOR ci 
Шаг 3. Для i = 1..5:
       b1 = c((i+3) mod 5) + 1
       b2 = c((i+2) mod 5) + 1
       a1 = xi
       a2 = x(i mod 5) + 1 XOR x((i+3) mod 5) + 1
       yi,1||yi,2 = DESb1,b2(a1,a2) (yi,1, yi,2 = 32 бита)
Шаг 4. Для i = 1..5:
       zi = yi,1 XOR y((i+1) mod 5)+1,2 XOR y((i+2) mod 5)+1,1 
Шаг 5. G(t,c) = z1||z2||z3||z4||z5

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

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

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

Для вычисления n−1 mod q, где 0 < n < q и 0 < n−1 < 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−1 = 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−1 = 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

u1 = bf655bd0 46f0b35e c791b004 804afcbb 8ef7d69d

u2 = 821a9263 12e97ade abcc8d08 2b527897 8a2df4b0

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

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

v = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0

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

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

Ссылки[править | править вики-текст]

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

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

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