| DSS, standard de semnătură digitală | |
|---|---|
| Creator | Institutul Național de Standarde și Tehnologie |
| Creată | august 1991 |
| Dimensiunea cheii | 512-1024 biți |
| Dimensiunea semnăturii | două numere de 160 de biți |
DSS ( Digital Signature Standard ) este un standard american care descrie Digital Signature Algorithm ( DSA ) care poate fi folosit pentru a genera o semnătură digitală . Semnătura digitală este utilizată pentru a stabili modificările datelor și pentru a autentifica semnatarul. Destinatarul datelor semnate poate folosi semnătura digitală pentru a dovedi unui terț că semnătura a fost într-adevăr făcută de expeditor.
Când un mesaj este primit, destinatarul poate dori să verifice dacă mesajul a fost modificat în timpul tranzitului. Destinatarul poate dori, de asemenea, să verifice identitatea semnatarului. DSA face posibilă acest lucru.
DSA este folosit de o parte pentru a genera semnătura datelor și de cealaltă parte pentru a autentifica abonatul. Semnătura este generată folosind cheia privată. Orice parte poate verifica autenticitatea unei semnături digitale folosind cheia publică. Cheia publică este trimisă împreună cu datele semnate. Cheile publice și private nu se potrivesc.
Când se generează o semnătură, o funcție hash este utilizată pentru a obține o versiune comprimată a datelor. Datele primite sunt procesate de către DSA pentru a obține o semnătură digitală. Aceeași funcție hash este utilizată pentru a verifica semnătura. Funcția hash este descrisă în SHS (Secure Hash Standard).
| Folosind SHA cu DSA |
|---|
DSA utilizează următorii parametri:
1. p este un număr prim p, unde 2 L-1 < p < 2 L , 512 =< L =< 1024 și L este un multiplu de 64 2. q este un divizor prim al lui p-1, unde 2 159 < q < 2 160 3. g = h (p-1)/q mod p, unde h este orice număr întreg 1 < h < p - 1 astfel încât h ( p-1)/q mod p > 1 4. x este un întreg aleatoriu sau pseudo-aleatoriu, unde 0 < x < q 5. y = g x mod p 6. k este un întreg aleatoriu sau pseudoaleator, unde 0 < k < q.Numerele întregi p, q și g pot fi publice și pot fi partajate de un grup de oameni. x și y sunt chei private și, respectiv, publice. Parametrii x și k sunt utilizați doar pentru a genera semnătura și trebuie păstrați secreti. Parametrul k este diferit pentru fiecare semnătură.
Semnătura mesajului M este o pereche de numere r și s, unde
SHA(M) este un șir binar de 160 de biți.
Dacă r = 0 sau s = 0, trebuie generat un nou k și calculată o nouă semnătură. Dacă semnătura a fost calculată corect, probabilitatea ca r = 0 sau s = 0 este foarte mică.
Semnătura este trimisă împreună cu mesajul către destinatar.
Numerele p, q, g și cheia publică sunt în domeniul public.
Fie M’, r’ și s’ versiunile primite ale lui M, r și respectiv s și fie y cheia publică. Când verificați o semnătură, mai întâi trebuie să vedeți dacă sunt valabile următoarele inegalități:
0 < r' < q 0 < s' < q.Dacă cel puțin o inegalitate nu este satisfăcută, semnătura trebuie respinsă. Dacă sunt îndeplinite condițiile de inegalitate, se fac următoarele calcule:
Dacă v = r', atunci se confirmă autenticitatea semnăturii.
Dacă v ≠ r', atunci mesajul ar fi putut fi modificat, mesajul ar fi putut fi semnat incorect sau mesajul ar fi putut fi semnat de un fraudator. În acest caz, datele primite ar trebui considerate corupte.
Această secțiune include algoritmi pentru generarea primelor p și q pentru DSA. Acești algoritmi folosesc un generator de numere aleatorii.
Pentru a genera numere prime p și q, este necesar un test de primalitate. Există mai multe teste de probabilitate rapide. În cazul nostru, va fi utilizată o versiune simplificată a testului Miller-Rabin . Dacă testul este repetat de n ori, va produce un număr prim cu o probabilitate de eroare de cel mult 1/4 n . Pentru a verifica dacă un număr întreg este prim, trebuie să:
Pasul 1. Setați i = 1 și alegeți n>=50. Pasul 2. Echivalați w cu numărul testat și reprezentați-l ca w = 1 + 2 a m, unde m este un număr impar. Pasul 3. Generați un număr aleator b: 1 < b < w. Pasul 4. Setați j = 0 și z = b m mod w. Pasul 5. Dacă j = 0 și z = 1, sau dacă z = w - 1, atunci treceți la pasul 9. Pasul 6. Dacă j > 0 și z = 1, atunci treceți la pasul 8. Pasul 7. j = j + 1. Dacă j < a, atunci setați z = z 2 mod w și treceți la pasul 5. Pasul 8. w nu este simplu. Stop. Pasul 9. Dacă i < n, atunci setați i = i + 1 și treceți la pasul 3. În caz contrar, poate w este un număr prim.DSS necesită 2 numere prime p și q, care trebuie să îndeplinească următoarele condiții:
2 159 < q < 2 160 2 L-1 < p < 2 L , unde L = 512 + 64j și 0 <= j < = 8 p - 1 este divizibil cu q.Pentru a genera un q simplu: 2 159 < q < 2 160 , se folosesc SHA-1 și o sămânță SEED. După aceea, numărul SEED este folosit pentru a crea numărul X: 2 L-1 < X < 2 L . Un prim p se obține prin rotunjirea lui X astfel încât numărul rezultat să fie 1 mod 2q.
Fie L - 1 = n*160 + b, unde b și n sunt numere întregi și iau valori de la 0 la 160.
Pasul 1. Alegem o secvență arbitrară de cel puțin 160 de biți și o numim SEED. Fie g lungimea SEED în biți. Pasul 2. Calculați U = SHA[SEED] XOR SHA[(SEED+1) mod 2 g ]. Pasul 3. Creați q din U setând LSB și MSB la 1: q = U SAU 2 159 SAU 1. Rețineți că 2 159 < q < 2 160 . Pasul 4. Verificați q pentru simplitate. Pasul 5. Dacă q nu este simplu, treceți la pasul 1. Pasul 6. Fie counter = 0 și offset = 2. Pasul 7. Pentru k = 0,...,n se calculează Vk = SHA[(SEED + offset + k) mod 2 g ]. Pasul 8 Calculați 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 . Rețineți că 0 <= W < 2 L-1 și 2 L-1 <= X < 2 L . Pasul 9. Fie c = X mod 2q și p = X - (c - 1). Rețineți că p este egal cu 1 mod 2q. Pasul 10. Dacă p < 2 L-1, atunci treceți la pasul 13. Pasul 11. Verificați p pentru simplitate. Pasul 12. Dacă p a trecut testul la pasul 11, treceți la pasul 15. Pasul 13. contor = contor + 1 și offset = offset + n + 1. Pasul 14. Dacă contorul >= 2 12 = 4096, treceți la pasul 1, în caz contrar treceți la pasul 7. Pasul 15 Salvați SEED și contorul pentru a confirma că p și q au fost generate corect.Orice implementare DSA necesită numere întregi aleatoare sau pseudoaleatoare. Aceste numere sunt selectate folosind metodele descrise în această secțiune sau alte metode aprobate de FIPS .
Algoritmul din Secțiunea 7.1 poate fi folosit pentru a genera x. Algoritmul pentru k și r este descris în secțiunea 7.2. Algoritmii folosesc o funcție unidirecțională (o funcție a cărei reciprocă este foarte dificil de calculat) G(t, c) unde t este 160 biți, c este b biți (160 < b < 512) și G(t, c) este 160 de biți. G poate fi creat folosind algoritmul Secure Hash ( SHA-1 ) sau folosind Standardul de criptare a datelor ( DES ), descris în secțiunile 7.3 și, respectiv, 7.4.
Fie x cheia privată a semnatarului. Următorul algoritm poate fi utilizat pentru a genera m valori ale lui x:
Pasul 1. Alegeți o nouă valoare pentru cheia originală, XKEY. Pasul 2. În sistemul numeric hexazecimal t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. Aceasta este valoarea inițială pentru H 0 ||H 1 ||H 2 ||H 3 ||H 4 în SHS. Pasul 3. Pentru j = 0..m - 1 A. XSEED j = valoare opțională introdusă de utilizator. b. XVAL = (XKEY + XSEED j ) mod 2 b . c. xj = G(t, XVAL ) mod q. d. XKEY = (1 + XKEY + x j ) mod 2 b .Acest algoritm poate fi folosit pentru a precalcula k, k -1 și r pentru m mesaje în același timp. Algoritm:
Pasul 1. Selectați o sămânță secretă pentru KKEY. Pasul 2. În sistemul numeric hexazecimal t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Aceasta este deplasarea inițială pentru H 0 ||H 1 ||H 2 ||H 3 ||H 4 în SHS. Pasul 3. Pentru j = 0..m - 1: A. k = G(t,KKEY) mod q. b. Calculați k j −1 = k −1 mod q. c. Calculați r j = (g k mod p) mod q. d. KKEY = (1 + KKEY + k) mod 2 b . Pasul 4. Să presupunem că M 0 , ... , M m-1 sunt următoarele m mesaje. Pentru j = 0..m - 1: A. Fie h = SHA(M j ). b. s j = (k j −1 (h + xr j )) mod q. c. r j ,s j ) - semnătură pentru M j . Pasul 5. t = h. Pasul 6. Treceți la pasul 3.Pasul 3 face posibilă calcularea cantităților necesare semnării următoarelor m mesaje. Pasul 4 este executat imediat după primirea acestor m mesaje.
G(t, c) poate fi obținut folosind SHA-1 , dar înainte de aceasta {H j } și M 1 trebuie inițializate după cum urmează:
1. Inițializați {Hj} împărțind valoarea de 160 de biți t în cinci segmente de 32 de biți: t = t 0 ||t 1 ||t 2 ||t 3 ||t 4 Atunci Hj = t j pentru j = 0..4. 2. Blocul de mesaje M 1 este definit după cum urmează: M1 = c||0 512-b (Primii b biți ai mesajului M1 conțin c, iar restul (512-b) biți sunt setați la zero).După aceea, SHA-1 [1] este executat și obținem un șir de 160 de biți G(t, c), reprezentat ca:
H 0 ||H 1 ||H 2 ||H 3 ||H 4 .Fie un XOR b să desemneze XOR pe biți ( adunare modulo 2 ). Fie a 1 , a 2 , b 1 , b 2 cu 32 de rânduri. Fie b 1 ' cei 24 de biţi cei mai puţin semnificativi ai b 1 . Fie K = b 1 '||b 2 şi A = a 1 ||a 2 . Denota
DES b1,b2 (a 1 ,a 2 ) = DES K (A)DES K (A) denotă criptarea DES normală [2] a unui bloc A de 64 de biți cu o cheie K de 56 de biți. Să presupunem că t și c sunt fiecare de 160 de biți. Pentru a calcula G(t, c):
Pasul 1. Înregistrare t = t 1 ||t 2 ||t 3 ||t 4 ||t 5 c = c 1 ||c 2 ||c 3 ||c 4 ||c 5 Fiecare t i și c i este de 32 de biți . Pasul 2. Pentru i = 1..5: x i = t i XOR c i Pasul 3. Pentru 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 biți) Pasul 4. Pentru i = 1..5: z i = y i,1 XOR y ((i+1) mod 5)+1,2 XOR y ((i+2) mod 5)+1,1 Pasul 5. G(t,c) = z 1 | |z 2 ||z 3 ||z 4 ||z 5Această secțiune oferă algoritmi pentru generarea g, k -1 și s -1 care sunt utilizați în DSS. Pentru a genera g:
Pasul 1. Generarea lui p și q este descrisă mai sus. Pasul 2. Fie e = (p - 1)/q. Pasul 3. Echivalează h cu orice număr întreg: 1 < h < p - 1. Pasul 4. g = h e mod p. Pasul 5. Dacă g = 1, treceți la pasul 3.Pentru a calcula n -1 mod q, unde 0 < n < q și 0 < n -1 < q:
Pasul 1. i = q, h = n, v = 0 și d = 1. Pasul 2. Fie t = i DIV h, unde DIV este diviziune întreagă. Pasul 3. x = h. Pasul 4. h = i - tx. Pasul 5. i = x. Pasul 6. x = d. Pasul 7. d = v - tx. Pasul 8. v = x. Pasul 9. Dacă h > 0, treceți la pasul 2. Pasul 10. Fie n −1 = v mod q.Rețineți că la pasul 10, v poate fi negativ.
Fie L = 512 (dimensiunea p). În acest exemplu, toate valorile vor fi în notație hexazecimală. Valorile p și q au fost generate așa cum este descris mai sus folosind următoarea valoare SEED de 160 de biți:
SEED = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3Cu acest SEED, algoritmul a găsit p și q la contorul de timp = 105. x a fost generat folosind algoritmul descris în secțiunea 7.1 folosind SHA-1 pentru a genera G (secțiunea 7.3) XKEY pe 160 de biți:
XKEY=bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6 t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 x = G(t,XKEY) mod qk a fost generat așa cum este descris în secțiunea 7.2 folosind SHA-1 pentru a genera G (secțiunea 7.3) KKEY pe 160 de biți:
KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584 t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 k = G(t,KKEY) mod qIn cele din urma:
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 ae52f917M = cuvântul „abc” din alfabetul englez ( 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