| DSS, standard digitálního podpisu | |
|---|---|
| Tvůrce | Národní institut pro standardy a technologie |
| Vytvořeno | srpna 1991 |
| Velikost klíče | 512-1024 bitů |
| Velikost podpisu | dvě čísla po 160 bitech |
DSS ( Digital Signature Standard ) je americký standard , který popisuje algoritmus digitálního podpisu ( DSA ) , který lze použít ke generování digitálního podpisu . Digitální podpis se používá k provedení změn dat a k ověření podepsané osoby. Příjemce podepsaných dat může použít digitální podpis k prokázání třetí straně, že podpis skutečně provedl odesílatel.
Když je zpráva přijata, příjemce si může přát zkontrolovat, zda byla zpráva při přenosu pozměněna. Příjemce může také chtít ověřit identitu podepisujícího. DSA to umožňuje.
DSA používá jedna strana ke generování datového podpisu a druhá strana k autentizaci předplatitele. Podpis je generován pomocí soukromého klíče. Kterákoli strana může ověřit pravost digitálního podpisu pomocí veřejného klíče. Veřejný klíč je odeslán spolu s podepsanými daty. Veřejný a soukromý klíč se neshodují.
Při generování podpisu se k získání komprimované verze dat používá hašovací funkce. Přijatá data zpracovává DSA za účelem získání digitálního podpisu. Stejná hashovací funkce se používá k ověření podpisu. Hašovací funkce je popsána v SHS (Secure Hash Standard).
| Použití SHA s DSA |
|---|
DSA používá následující parametry:
1. p je prvočíslo p, kde 2 L-1 < p < 2 L , 512 =< L =< 1024 a L je násobek 64 2. q je prvočíselný dělitel p-1, kde 2 159 < q < 2 160 3. g = h (p-1)/q mod p, kde h je libovolné celé číslo 1 < h < p - 1 takové, že h (p-1)/q mod p > 1 4. x je náhodné nebo pseudonáhodné celé číslo, kde 0 < x < q 5. y = g x mod p 6. k je náhodné nebo pseudonáhodné celé číslo, kde 0 < k < q.Celá čísla p, q a g mohou být veřejná a mohou být sdílena skupinou lidí. x a y jsou soukromé a veřejné klíče. Parametry x a k se používají pouze ke generování podpisu a musí být uchovávány v tajnosti. Parametr k je pro každý podpis jiný.
Signaturou zprávy M je dvojice čísel r a s, kde
SHA(M) je 160bitový binární řetězec.
Pokud r = 0 nebo s = 0, musí se vygenerovat nové k a vypočítat nový podpis. Pokud byl podpis vypočten správně, pravděpodobnost, že r = 0 nebo s = 0 je velmi malá.
Podpis je odeslán spolu se zprávou příjemci.
Čísla p, q, g a veřejný klíč jsou ve veřejné doméně.
Nechť M', r', a s' jsou přijaté verze M, r a s, a nechť y je veřejný klíč. Při ověřování podpisu musíte nejprve zjistit, zda platí následující nerovnosti:
0 < r' < q 0 < s' < q.Pokud není splněna alespoň jedna nerovnost, musí být podpis odmítnut. Pokud jsou splněny podmínky nerovnosti, provedou se následující výpočty:
Je-li v = r', pak je pravost podpisu potvrzena.
Pokud je v ≠ r', pak mohla být zpráva pozměněna, zpráva mohla být nesprávně podepsána nebo mohla být podepsána podvodníkem. V tomto případě by měla být přijatá data považována za poškozená.
Tato část obsahuje algoritmy pro generování prvočísel p a q pro DSA. Tyto algoritmy používají generátor náhodných čísel.
Pro generování prvočísel p a q je zapotřebí test prvočíselnosti. Existuje několik rychlých testů pravděpodobnosti. V našem případě bude použita zjednodušená verze Miller-Rabinova testu . Pokud se test opakuje nkrát, vytvoří prvočíslo s pravděpodobností chyby nejvýše 1/4 n . Chcete-li zkontrolovat, zda je celé číslo prvočíslo, musíte:
Krok 1. Nastavte i = 1 a zvolte n>=50. Krok 2. Přirovnejte w k testovanému číslu a reprezentujte jej jako w = 1 + 2 a m, kde m je liché číslo. Krok 3. Vygenerujte náhodné číslo b: 1 < b < w. Krok 4. Nastavte j = 0 az = b m mod w. Krok 5. Pokud j = 0 az = 1, nebo pokud z = w - 1, přejděte ke kroku 9. Krok 6. Pokud j > 0 az = 1, přejděte ke kroku 8. Krok 7. j = j + 1. Pokud j < a, pak nastavte z = z 2 mod w a přejděte ke kroku 5. Krok 8. w není jednoduchý. Stop. Krok 9. Pokud i < n, nastavte i = i + 1 a přejděte ke kroku 3. V opačném případě je w možná prvočíslo.DSS vyžaduje 2 prvočísla p a q, která musí splňovat následující podmínky:
2 159 < q < 2 160 2 L-1 < p < 2 L , kde L = 512 + 64j a 0 <= j < = 8 p - 1 je dělitelné q.Ke generování jednoduchého q: 2 159 < q < 2 160 se používá SHA-1 a seed SEED. Poté se číslo SEED použije k vytvoření čísla X: 2 L-1 < X < 2 L . Prvočíslo p získáme zaokrouhlením X tak, aby výsledné číslo bylo 1 mod 2q.
Nechť L - 1 = n*160 + b, kde b a n jsou celá čísla a nabývají hodnot od 0 do 160.
Krok 1. Zvolíme libovolnou sekvenci alespoň 160 bitů a nazveme ji SEED. Nechť g je délka SEED v bitech. Krok 2. Vypočítejte U = SHA[SEED] XOR SHA[(SEED+1) mod 2 g ]. Krok 3. Vytvořte q z U nastavením LSB a MSB na 1: q = U NEBO 2 159 NEBO 1. Všimněte si, že 2 159 < q < 2 160 . Krok 4. Zkontrolujte q pro jednoduchost. Krok 5. Pokud q není jednoduché, přejděte ke kroku 1. Krok 6. Nechte čítač = 0 a offset = 2. Krok 7. Pro k = 0,...,n vypočítejte Vk = SHA[(SEED + offset + k) mod 2 g ]. Krok 8 Vypočítejte W = V 0 + V 1 *2 160 + ... + V n-1 *2 (n-1)*160 + (V n mod 2 b ) * 2 n*160 X = W + 2 L -1 . Všimněte si, že 0 <= W < 2 L-1 a 2 L-1 <= X < 2 L. Krok 9. Nechť c = X mod 2q a p = X - (c - 1). Všimněte si, že p se rovná 1 mod 2q. Krok 10. Pokud p < 2 L-1 , přejděte ke kroku 13. Krok 11. Zkontrolujte jednoduchost p. Krok 12. Pokud p prošel testem v kroku 11, přejděte ke kroku 15. Krok 13. čítač = čítač + 1 a offset = offset + n + 1. Krok 14. Pokud čítač >= 2 12 = 4096, přejděte ke kroku 1, jinak přejděte ke kroku 7. Krok 15 Uložte SEED a počítadlo, abyste potvrdili, že p a q byly vygenerovány správně.Jakákoli implementace DSA vyžaduje náhodná nebo pseudonáhodná celá čísla. Tato čísla se vybírají pomocí metod popsaných v této části nebo jiných metod schválených FIPS .
Algoritmus v části 7.1 lze použít ke generování x. Algoritmus pro k a r je popsán v části 7.2. Algoritmy používají jednosměrnou funkci (funkci, jejíž reciprokou hodnotu je velmi obtížné vypočítat) G(t, c) kde t je 160 bitů, c je b bitů (160 < b < 512) a G(t, c) je 160 bitů. G lze vytvořit pomocí algoritmu Secure Hash Algorithm ( SHA-1 ) nebo pomocí standardu Data Encryption Standard ( DES ), popsaného v částech 7.3 a 7.4.
Nechť x je soukromý klíč podepisujícího. Pro generování m hodnot x lze použít následující algoritmus:
Krok 1. Vyberte novou hodnotu pro původní klíč, XKEY. Krok 2. V hexadecimální číselné soustavě t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. Toto je počáteční hodnota pro H 0 ||H 1 ||H 2 ||H 3 ||H 4 v SHS. Krok 3. Pro j = 0..m - 1 A. XSEED j = volitelná hodnota zadaná uživatelem. b. XVAL = (XKEY + XSEED j ) mod 2 b . C. xj = G(t, XVAL ) mod q. d. XKEY = (1 + XKEY + x j ) mod 2 b .Tento algoritmus lze použít k předběžnému výpočtu k, k −1 a r pro m zpráv současně. Algoritmus:
Krok 1. Vyberte tajný zdroj pro KKEY. Krok 2. V hexadecimální číselné soustavě t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Toto je počáteční posun pro H 0 ||H 1 ||H 2 ||H 3 ||H 4 v SHS. Krok 3. Pro j = 0..m - 1: A. k = G(t,KKEY) mod q. b. Vypočítejte k j −1 = k −1 mod q. C. Vypočítejte r j = (g k mod p) mod q. d. KKEY = (1 + KKEY + k) mod 2 b . Krok 4. Předpokládejme, že M 0 , ... , M m-1 je dalších m zpráv. Pro j = 0..m - 1: A. Nechť h = SHA(M j ). b. s j = (k j −1 (h + xr j )) mod q. C. r j ,s j ) - podpis pro M j . Krok 5. t = h. Krok 6. Přejděte na krok 3.Krok 3 umožňuje vypočítat množství potřebná k podepsání dalších m zpráv. Krok 4 se provede okamžitě po přijetí těchto m zpráv.
G(t, c) lze získat pomocí SHA-1 , ale předtím musí být {Hj } a M1 inicializovány následovně:
1. Inicializujte {Hj} rozdělením 160bitové hodnoty t do pěti 32bitových segmentů: t = t 0 ||t 1 ||t 2 ||t 3 ||t 4 Potom Hj = t j pro j = 0..4. 2. Blok zpráv M 1 je definován takto: M1 = c||0 512-b (Prvních b bitů zprávy Mi obsahuje c a zbývající (512-b) bity jsou nastaveny na nulu) .Poté se provede SHA-1 [1] a dostaneme 160bitový řetězec G(t, c), reprezentovaný jako:
H 0 ||H 1 ||H 2 ||H 3 ||H 4 .Nechť a XOR b označuje bitové XOR ( modulo 2 sčítání ). Nechť a 1 , a 2 , b 1 , b 2 je 32 řádků. Nechť b 1 ' je nejméně významných 24 bitů b 1 . Nechť K = b 1 '||b 2 a A = a 1 ||a 2 . Označit
DES b1,b2 (a 1 ,a 2 ) = DES K (A)DES K (A) označuje normální DES šifrování [2] 64bitového bloku A s 56bitovým klíčem K. Předpokládejme, že t a c jsou každé 160 bitů. Pro výpočet G(t, c):
Krok 1. Nahrávání t = t 1 ||t 2 ||t 3 ||t 4 ||t 5 c = c 1 ||c 2 ||c 3 ||c 4 ||c 5 Každé ti a c i je 32 bitů. Krok 2. Pro i = 1,.5: x i = t i XOR c i Krok 3. Pro 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 bitů) Krok 4. Pro i = 1,.5: z i = y i,1 XOR y ((i+1) mod 5)+1,2 XOR y ((i+2) mod 5)+1,1 Krok 5. G(t,c) = z 1 | |z 2 ||z 3 ||z 4 ||z 5Tato část poskytuje algoritmy pro generování g, k −1 a s −1 , které se používají v DSS. Chcete-li vygenerovat g:
Krok 1. Generování p a q je popsáno výše. Krok 2. Nechť e = (p - 1)/q. Krok 3. Přirovnejte h k libovolnému celému číslu: 1 < h < p - 1. Krok 4. g = h e mod p. Krok 5. Pokud g = 1, přejděte ke kroku 3.Chcete-li vypočítat n −1 mod q, kde 0 < n < q a 0 < n −1 < q:
Krok 1. i = q, h = n, v = 0 a d = 1. Krok 2. Nechť t = i DIV h, kde DIV je celočíselné dělení. Krok 3. x = h. Krok 4. h = i - tx. Krok 5. i = x. Krok 6. x = d. Krok 7. d = v - tx. Krok 8. v = x. Krok 9. Pokud h > 0, přejděte ke kroku 2. Krok 10. Nechť n −1 = v mod q.Všimněte si, že v kroku 10 může být v záporné.
Nechť L = 512 (velikost p). V tomto příkladu budou všechny hodnoty v hexadecimálním zápisu. Hodnoty p a q byly vygenerovány výše popsaným způsobem s použitím následující 160bitové hodnoty SEED:
SEED = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3S tímto SEED algoritmus našel p a q na časovém čítači = 105. x bylo vygenerováno pomocí algoritmu popsaného v části 7.1 pomocí SHA-1 pro generování G (část 7.3) 160bitového XKEY:
XKEY=bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6 t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 x = G(t,XKEY) mod qk bylo vygenerováno podle popisu v části 7.2 pomocí SHA-1 ke generování G (část 7.3) 160bitového KKEY:
KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584 t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 k = G(t,KKEY) mod qKonečně:
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 deadfbf k −1 = 0d516729 8202e49b 4116ac10 4fc3f415 ae52f917M = slovo „abc“ z anglické abecedy ( 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