Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Digital Signature Standard



План:


Введення

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



1. Введення

Коли повідомлення отримано, одержувач може побажати перевірити не змінили чи повідомлення під час передачі. Одержувач також може захотіти перевірити справжність підписаного сторонами. DSA дає можливість зробити це.

2. Використання DSA

DSA використовується однією стороною для генерації підпису даних, а інший для перевірки автентичності передплатника. Підпис генерується за допомогою закритого ключа. Будь-яка сторона може перевірити справжність цифрового підпису за допомогою відкритого ключа. Відкритий ключ посилається разом з підписаними даними. Відкритий і закритий ключі не співпадають.

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

Використання SHA разом з DSA
Генерація цифрового підпису Перевірка цифрового підпису

3. Параметри DSA

DSA використовує наступні параметри:

 1. p - просте число p, де 2 L-1 

L, 512 = 2159 <2160 3. g = h (p-1) / q mod p, де h будь-яке ціле число 1 (p-1) / q mod p> 1 4. x - випадкове або псевдовипадкове ціле число, де 0 x mod p 6. k - випадкове або псевдовипадкове ціле число, де 0

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


4. Генерація підпису

Підписом повідомлення M є пара чисел r і s, де

 r = (g k mod p) mod qs = (k -1 (SHA (M) + xr)) mod q. 

SHA (M) - 160-бітна бінарна рядок.

Якщо r = 0 або s = 0, має бути згенеровано нове k і обчислена нова підпис. Якщо підпис обчислювалася правильно, ймовірність того, що r = 0 або s = 0 дуже мала.

Підпис разом з повідомленням пересилається одержувачу.

5. Перевірка підпису

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

Нехай M ', r' і s 'отримані версії M, r і s, відповідно, і нехай y - відкритий ключ. При перевірці підпису спочатку потрібно подивитися, чи виконуються наступні нерівності:

 0 

Якщо хоча б одне нерівність не виконано, підпис повинна бути відкинута. Якщо умови нерівностей виконані, виробляються наступні обчислення:

 w = (s ') -1 mod q u1 = ((SHA (M') w) mod q u2 = ((r ') w) mod qv = (((g) ul (y) u2) mod p) mod q. 

Якщо v = r ', то справжність підпису підтверджена.

Якщо v ≠ r ', то повідомлення могло бути змінено, повідомлення могло бути неправильно підписано або повідомлення могло бути підписана шахраєм. У цьому випадку отримані дані слід розглядати як пошкоджені.


6. Генерація простих чисел для DSA

Цей розділ включає алгоритми для генерації простих чисел p і q для DSA. У цих алгоритмах використовується генератор випадкових чисел.

6.1. Імовірнісний тест на простоту

Для генерації простих p і q необхідний тест на простоту. Є кілька швидких імовірнісних тестів. У нашому випадку буде використовуватися спрощена версія тесту Міллера-Рабіна. Якщо повторити тест n раз, він видасть просте число з імовірністю помилки не більше 1/4 n. Для перевірки цілого числа на простоту потрібно:

 Крок 1. Встановлюємо i = 1 і вибираємо n> = 50. Крок 2. Прирівнюємо w тестируемому числу і представляємо його у вигляді w = 1 + 2 a m, де m - непарне число. Крок 3. Генеруємо випадкове число b: 1 m mod w. Крок 5. Якщо j = 0 і z = 1, або якщо z = w - 1, то переходимо на крок 9. Крок 6. Якщо j> 0 і z = 1, то переходимо на крок 8. Крок 7. j = j + 1. Якщо j 2 mod w і переходимо на крок 5. Крок 8. w не просте. Стоп. Крок 9. Якщо i 

6.2. Генерація простих чисел

Для DSS потрібні 2 простих числа p і q, які повинні задовольняти наступним умовам:

 2159 160 2 L-1 

L, де L = 512 + 64j, причому 0 <= j <= 8 p - 1 ділиться на q.

Для генерації простого q: 2159 <2160 використовується SHA та початкове число SEED. Після цього число SEED використовується для створення числа X: 2 L-1 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 2159 OR 1. Зауважимо, що 2159 <2160. Крок 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 0 + V 1 * 2160 + ... + 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 12 = 4096 переходимо на крок 1, інакше переходимо на крок 7. Крок 15. Зберігаємо SEED і counter для того, щоб підтвердити правильну генерацію p і q. 

7. Генерація випадкових чисел для DSA

Для будь реалізації DSA потрібні випадкові або псевдовипадкові цілі числа. Ці числа вибираються за допомогою методів описаних в цьому розділі або за допомогою інших схвалених FIPS методів.

Алгоритм у розділі 7.1 може бути використаний для генерації x. Алгоритм для k і r описаний в розділі 7.2. Алгоритми ізпользуют односторонню функцію (функцію, зворотне значення якої дуже важко обчислити) G (t, c), де t має розмір 160 біт, c має розмір b біт (160 SHA) або за допомогою Data Encryption Standard ( DES), описані в розділах 7.3 і 7.4 відповідно.


7.1. Алгоритм для обчислення m значень числа x

Нехай x - секретний ключ підписує боку. Наступний алгоритм можна використовувати для генерації m значень числа x:

 Крок 1. Вибираємо нове значення для вихідного ключа, XKEY. Крок 2. У шістнадцятковій системі числення t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. Це початкове значення для H 0 | | H 1 | | H 2 | | H 3 | | H 4 в SHS. Крок 3. Для j = 0 .. m - 1 a. XSEED j = опціональне значення, введене користувачем. b. XVAL = (XKEY + XSEED j) mod 2 b. c. x j = G (t, XVAL) mod qd XKEY = (1 + XKEY + x j) mod 2 b. 

7.2. Алгоритм для попереднього обчислення k і r

Цей алгоритм може бути використаний для попереднього обчислення k, k -1 і r для m повідомлень одночасно. Алгоритм:

 Крок 1. Вибирається секретне початкове значення для KKEY. Крок 2. У шістнадцятковій системі числення t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Це початковий зрушення для H 0 | | H 1 | | H 2 | | H 3 | | H 4 в SHS. Крок 3. Для j = 0 .. m - 1: a. k = G (t, KKEY) mod qb Обчислюємо k j -1 = k -1 mod qc Обчислюємо r j = (g k mod p) mod qd KKEY = (1 + KKEY + k) mod 2 b. Крок 4. Припустимо M 0,... , M m-1 - наступні m повідомлень. Для j = 0 .. m - 1: a. Нехай h = SHA (M j). b. s j = (k j -1 (h + xr j)) mod qc r j, s j) - підпис для M j. Крок 5. t = h. Крок 6. Переходимо на крок 3. 

Крок 3 дає можливість обчислити величини, необхідні для підпису наступних m повідомлень. Крок 4 виконуватися відразу після того, коли отримані ці m повідомлень.


7.3. Створення функції G за допомогою SHA

G (t, c) може бути отримана за допомогою SHA, але перед цим {H j} і M 1 повинні бути ініціалізований наступним чином:

 1. Ініціалізували {Hj} поділ 160-бітного значення t на п'ять 32-бітових сегмента: t = t 0 | | t 1 | | t 2 | | t 3 | | t 4 Тоді Hj = t j для j = 0 .. 4. 2. Блок повідомлення M 1 визначається наступним чином: M 1 = c | | 0512-b (Перші b біт повідомлення M 1 містять c, а що залишилися (512-b) біт встановлюються нулями). 

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

 H 0 | | H 1 | | H 2 | | H 3 | | H 4. 

7.4. Створення функції G за допомогою DES

Нехай a XOR b позначає побітове виключає "АБО" ( складання по модулю 2). Нехай a 1, a 2, b 1, b 2 - 32-рядка. Нехай b 1 '- 24 молодших біта числа b 1. Нехай K = b 1 '| | b 2 і A = a 1 | | a 2. Позначимо

 DES b1, b2 (a 1, a 2) = DES K (A) 

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

 Крок 1. Записуємо t = t 1 | | t 2 | | t 3 | | t 4 | | t 5 c = c 1 | | c 2 | | c 3 | | c 4 | | c 5 Кожна t i і c i має розмір 32 біта. Крок 2. Для i = 1 .. 5: x i = t i XOR c i Крок 3. Для i = 1 .. 5: b 1 = c ((i +3) mod 5) + 1 b 2 = c ((i +2) mod 5) + 1 a 1 = x i a 2 = x (i mod 5) + 1 XOR x ((i +3) mod 5) + 1 y i, 1 | | y i, 2 = DES b1, b2 (a 1, a 2) (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 1 | | z 2 | | z 3 | | z 4 | | z 5 

8. Генерація інших параметрів

У цьому розділі наведені алгоритми для генерації g, k -1 і s -1, які використовуються в DSS. Для генерації g:

 Крок 1. Генерація p і q описана вище. Крок 2. Нехай e = (p - 1) / q. Крок 3. Прирівнюємо h будь цілої: 1 e mod p. Крок 5. Якщо g = 1, переходимо на крок 3. 

Для обчислення n -1 mod q, де 0 -1

 Крок 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 може бути негативним.


9. Приклад 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 u 1 = bf655bd0 46f0b35e c791b004 804afcbb 8ef7d69d u 2 = 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 

Примітки

  1. FIPS PUB 180-1 - www.itl.nist.gov/fipspubs/fip180-1.htm (Англ.) . - Опис стандарту SHS. Читальний - www.webcitation.org/66kq6hVtl з першоджерела 8 квітня 2012.
  2. FIPS PUB 46-3 - csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf (Англ.) . - Опис стандарту DES. Читальний - www.webcitation.org/66kuhPhSB з першоджерела 8 квітня 2012.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Standard & Poor's
Dolby Digital
BR Standard Class 9F
Standard Oil
Advanced Encryption Standard
Linux Standard Base
Digital Visual Interface
Digital Millennium Copyright Act
3DNews Daily Digital Digest
© Усі права захищені
написати до нас
Рейтинг@Mail.ru