| DSS, Digital Signatur Standard | |
|---|---|
| Skaber | National Institute of Standards and Technology |
| Oprettet | august 1991 |
| Nøglestørrelse | 512-1024 bit |
| Signaturstørrelse | to tal på 160 bit |
DSS ( Digital Signature Standard ) er en amerikansk standard , der beskriver Digital Signature Algorithm ( DSA ) , der kan bruges til at generere en digital signatur . Den digitale signatur bruges til at etablere dataændringer og til at autentificere underskriveren. Modtageren af de signerede data kan bruge den digitale signatur til at bevise over for en tredjepart, at signaturen faktisk er lavet af afsenderen.
Når en besked modtages, kan modtageren ønske at kontrollere, om beskeden er blevet ændret under forsendelsen. Modtageren vil muligvis også bekræfte underskriverens identitet. DSA gør det muligt at gøre dette.
DSA'en bruges af den ene side til at generere datasignaturen og den anden side til at autentificere abonnenten. Signaturen genereres ved hjælp af den private nøgle. Enhver part kan verificere ægtheden af en digital signatur ved hjælp af den offentlige nøgle. Den offentlige nøgle sendes sammen med de signerede data. De offentlige og private nøgler stemmer ikke overens.
Når der genereres en signatur, bruges en hash-funktion til at opnå en komprimeret version af dataene. De modtagne data behandles af DSA for at opnå en digital signatur. Den samme hash-funktion bruges til at bekræfte signaturen. Hash-funktionen er beskrevet i SHS (Secure Hash Standard).
| Brug af SHA med DSA |
|---|
DSA bruger følgende parametre:
1. p er et primtal p, hvor 2 L-1 < p < 2 L , 512 =< L =< 1024 og L er et multiplum af 64 2. q er en primtal divisor af p-1, hvor 2 159 < q < 2 160 3. g = h (p-1)/q mod p, hvor h er et hvilket som helst heltal 1 < h < p - 1, således at h (p-1)/q mod p > 1 4. x er et tilfældigt eller pseudo-tilfældigt heltal, hvor 0 < x < q 5. y = g x mod p 6. k er et tilfældigt eller pseudo-tilfældigt heltal, hvor 0 < k < q.Heltallene p, q og g kan være offentlige og kan deles af en gruppe mennesker. x og y er henholdsvis private og offentlige nøgler. x- og k-parametrene bruges kun til at generere signaturen og skal holdes hemmelige. Parameteren k er forskellig for hver signatur.
Signaturen for beskeden M er et par tal r og s, hvor
SHA(M) er en 160-bit binær streng.
Hvis r = 0 eller s = 0, skal en ny k genereres og en ny signatur beregnes. Hvis signaturen blev beregnet korrekt, er sandsynligheden for, at r = 0 eller s = 0 meget lille.
Signaturen sendes sammen med beskeden til modtageren.
Tallene p, q, g og den offentlige nøgle er i det offentlige domæne.
Lad M', r' og s' være de modtagne versioner af henholdsvis M, r og s, og lad y være den offentlige nøgle. Når du verificerer en signatur, skal du først se, om følgende uligheder holder:
0 < r' < q 0 < s' < q.Hvis mindst én ulighed ikke er opfyldt, skal underskriften afvises. Hvis ulighedsbetingelserne er opfyldt, foretages følgende beregninger:
Hvis v = r', bekræftes signaturens ægthed.
Hvis v ≠ r', kan meddelelsen være blevet ændret, meddelelsen kan være blevet underskrevet forkert, eller meddelelsen kan være blevet underskrevet af en svindler. I dette tilfælde skal de modtagne data betragtes som beskadigede.
Dette afsnit inkluderer algoritmer til generering af p- og q-primtal for DSA. Disse algoritmer bruger en tilfældig talgenerator.
For at generere primtal p og q, er en primalitetstest nødvendig. Der er flere hurtige sandsynlighedstest. I vores tilfælde vil en forenklet version af Miller-Rabin-testen blive brugt . Hvis testen gentages n gange, vil den frembringe et primtal med en fejlsandsynlighed på højst 1/4 n . For at kontrollere, om et heltal er primtal, skal du:
Trin 1. Indstil i = 1 og vælg n>=50. Trin 2. Sæt lighedstegn mellem w med det tal, der testes, og repræsentere det som w = 1 + 2 a m, hvor m er et ulige tal. Trin 3. Generer et tilfældigt tal b: 1 < b < w. Trin 4. Indstil j = 0 og z = b m mod w. Trin 5. Hvis j = 0 og z = 1, eller hvis z = w - 1, så gå til trin 9. Trin 6. Hvis j > 0 og z = 1, så gå til trin 8. Trin 7. j = j + 1. Hvis j < a, så indstil z = z 2 mod w og gå til trin 5. Trin 8. w er ikke simpelt. Hold op. Trin 9. Hvis i < n, så sæt i = i + 1 og gå til trin 3. Ellers er w måske et primtal.DSS kræver 2 primtal p og q, som skal opfylde følgende betingelser:
2 159 < q < 2 160 2 L-1 < p < 2 L , hvor L = 512 + 64j, og 0 <= j < = 8 p - 1 er deleligt med q.For at generere en simpel q: 2 159 < q < 2 160 , bruges SHA-1 og et SEED-frø. Derefter bruges SEED-nummeret til at skabe tallet X: 2 L-1 < X < 2 L . Et primtal p opnås ved at afrunde X, så det resulterende tal er 1 mod 2q.
Lad L - 1 = n*160 + b, hvor b og n er heltal og tager værdier fra 0 til 160.
Trin 1. Vi vælger en vilkårlig sekvens på mindst 160 bit og kalder det SEED. Lad g være længden af SEED i bits. Trin 2. Beregn U = SHA[SEED] XOR SHA[(SEED+1) mod 2 g ]. Trin 3. Opret q fra U ved at indstille LSB og MSB til 1: q = U OR 2 159 ELLER 1. Bemærk at 2 159 < q < 2 160 . Trin 4. Tjek q for enkelhed. Trin 5. Hvis q ikke er simpelt, skal du gå til trin 1. Trin 6. Lad tæller = 0 og offset = 2. Trin 7. For k = 0,...,n beregn Vk = SHA[(SEED + offset + k) mod 2 g ]. Trin 8 Beregn 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 . Bemærk at 0 <= W < 2 L-1 og 2 L-1 <= X < 2 L . Trin 9. Lad c = X mod 2q og p = X - (c - 1). Bemærk at p er lig med 1 mod 2q. Trin 10. Hvis p < 2 L-1 , så gå til trin 13. Trin 11. Tjek p for enkelhed. Trin 12. Hvis p bestod testen i trin 11, skal du gå til trin 15. Trin 13. tæller = tæller + 1 og offset = offset + n + 1. Trin 14. Hvis tæller >= 2 12 = 4096, gå til trin 1, ellers gå til trin 7. Trin 15 Gem SEED og tæller for at bekræfte, at p og q blev genereret korrekt.Enhver DSA-implementering kræver tilfældige eller pseudo-tilfældige heltal. Disse numre er valgt ved hjælp af metoderne beskrevet i dette afsnit eller andre FIPS -godkendte metoder.
Algoritmen i afsnit 7.1 kan bruges til at generere x. Algoritmen for k og r er beskrevet i afsnit 7.2. Algoritmerne bruger en envejsfunktion (en funktion hvis gensidige er meget svær at beregne) G(t, c) hvor t er 160 bit, c er b bit (160 < b < 512) og G(t, c) er 160 bit. G kan oprettes ved hjælp af Secure Hash Algorithm ( SHA-1 ) eller ved hjælp af Data Encryption Standard ( DES ), beskrevet i henholdsvis afsnit 7.3 og 7.4.
Lad x være underskriverens private nøgle. Følgende algoritme kan bruges til at generere m værdier af x:
Trin 1. Vælg en ny værdi for den originale nøgle, XKEY. Trin 2. I hexadecimalt talsystem t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. Dette er startværdien for H 0 ||H 1 ||H 2 ||H 3 ||H 4 i SHS. Trin 3. For j = 0..m - 1 en. XSEED j = valgfri værdi indtastet af brugeren. b. XVAL = (XKEY + XSEED j ) mod 2 b . c. xj = G(t, XVAL ) mod q. d. XKEY = (1 + XKEY + x j ) mod 2 b .Denne algoritme kan bruges til at forudberegne k, k −1 og r for m beskeder på samme tid. Algoritme:
Trin 1. Vælg et hemmeligt frø til KKEY. Trin 2. I hexadecimalt talsystem t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Dette er det indledende skift for H 0 ||H 1 ||H 2 ||H 3 ||H 4 i SHS. Trin 3. For j = 0..m - 1: en. k = G(t,KKEY) mod q. b. Beregn k j −1 = k −1 mod q. c. Beregn r j = (g k mod p) mod q. d. KKEY = (1 + KKEY + k) mod 2 b . Trin 4. Antag at M 0 , ... , M m-1 er de næste m meddelelser. For j = 0..m - 1: en. Lad h = SHA( Mj ). b. s j = (k j −1 (h + xr j )) mod q. c. r j ,s j ) - signatur for M j . Trin 5. t = h. Trin 6. Gå til trin 3.Trin 3 gør det muligt at beregne de nødvendige mængder for at underskrive de næste m beskeder. Trin 4 udføres umiddelbart efter, at disse m beskeder er modtaget.
G(t, c) kan opnås ved brug af SHA-1 , men før det skal {Hj } og M1 initialiseres som følger:
1. Initialiser {Hj} ved at dividere 160-bit værdien t i fem 32-bit segmenter: t = t 0 ||t 1 ||t 2 ||t 3 ||t 4 Så er Hj = t j for j = 0..4. 2. Meddelelsesblok M 1 er defineret som følger: M1 = c||0 512-b (De første b bits af meddelelsen M1 indeholder c, og de resterende (512-b) bits er sat til nul).Derefter udføres SHA-1 [1] , og vi får en 160-bit streng G(t, c), repræsenteret som:
Ho || H1 || H2 || H3 || H4 . _Lad a XOR b betegne bitvis XOR ( modulo 2 addition ). Lad a 1 , a 2 , b 1 , b 2 være 32 rækker. Lad b 1 ' være de mindst signifikante 24 bits af b 1 . Lad K = b 1 '||b 2 og A = a 1 ||a 2 . Betegn
DES b1,b2 (a 1 , a 2 ) = DES K (A)DES K (A) betegner normal DES-kryptering [2] af en 64-bit blok A med en 56-bit nøgle K. Antag, at t og c hver er 160 bit. For at beregne G(t, c):
Trin 1. Optagelse t = t 1 ||t 2 ||t 3 ||t 4 ||t 5 c = c 1 ||c 2 ||c 3 ||c 4 ||c 5 Hver t i og c i er 32 bit. Trin 2. For i = 1..5: x i = t i XOR c i Trin 3. For 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) Trin 4. For i = 1..5: z i = y i,1 XOR y ((i+1) mod 5)+1,2 XOR y ((i+2) mod 5)+1,1 Trin 5. G(t,c) = z 1 | |z 2 ||z 3 ||z 4 ||z 5Dette afsnit indeholder algoritmer til generering af g, k −1 og s −1 , der bruges i DSS. For at generere g:
Trin 1. Generering af p og q er beskrevet ovenfor. Trin 2. Lad e = (p - 1)/q. Trin 3. Sæt lighedstegn mellem h med et hvilket som helst heltal: 1 < h < p - 1. Trin 4. g = h e mod p. Trin 5. Hvis g = 1, gå til trin 3.For at beregne n −1 mod q, hvor 0 < n < q og 0 < n −1 < q:
Trin 1. i = q, h = n, v = 0 og d = 1. Trin 2. Lad t = i DIV h, hvor DIV er heltalsdivision. Trin 3. x = h. Trin 4. h = i - tx. Trin 5. i = x. Trin 6. x = d. Trin 7. d = v - tx. Trin 8. v = x. Trin 9. Hvis h > 0, gå til trin 2. Trin 10. Lad n −1 = v mod q.Bemærk, at ved trin 10 kan v være negativ.
Lad L = 512 (størrelse p). I dette eksempel vil alle værdier være i hexadecimal notation. P- og q-værdierne blev genereret som beskrevet ovenfor ved hjælp af følgende 160-bit SEED-værdi:
SEED = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3Med denne SEED blev algoritmen fundet p og q ved tidstælleren = 105. x blev genereret ved hjælp af algoritmen beskrevet i afsnit 7.1 ved brug af SHA-1 til at generere G (afsnit 7.3) 160-bit XKEY:
XKEY=bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6 t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 x = G(t,XKEY) mod qk blev genereret som beskrevet i afsnit 7.2 ved hjælp af SHA-1 til at generere G (afsnit 7.3) 160-bit KKEY:
KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584 t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 k = G(t,KKEY) mod qLangt om længe:
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 = ordet "abc" fra det engelske alfabet ( 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