Digital signaturstandard

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 april 2015; kontroller kräver 18 redigeringar .
DSS, digital signaturstandard
Skapare National Institute of Standards and Technology
Skapad augusti 1991
Nyckelstorlek 512-1024 bitar
Signaturstorlek två nummer på 160 bitar

DSS ( Digital Signature Standard ) är en amerikansk standard som beskriver Digital Signature Algorithm ( DSA ) som kan användas för att generera en digital signatur . Den digitala signaturen används för att upprätta dataändringar och för att autentisera undertecknaren. Mottagaren av de signerade uppgifterna kan använda den digitala signaturen för att bevisa för en tredje part att signaturen verkligen gjordes av avsändaren.

Introduktion

När ett meddelande tas emot kan mottagaren vilja kontrollera om meddelandet har ändrats under överföringen. Mottagaren kan också vilja verifiera undertecknarens identitet. DSA gör det möjligt att göra detta.

Använda DSA

DSA används av ena sidan för att generera datasignaturen och den andra sidan för att autentisera abonnenten. Signaturen genereras med den privata nyckeln. Vilken part som helst kan verifiera äktheten av en digital signatur med hjälp av den publika nyckeln. Den publika nyckeln skickas tillsammans med den signerade datan. De offentliga och privata nycklarna stämmer inte överens.

Vid generering av en signatur används en hashfunktion för att erhålla en komprimerad version av datan. Den mottagna datan behandlas av DSA för att erhålla en digital signatur. Samma hashfunktion används för att verifiera signaturen. Hashfunktionen beskrivs i SHS (Secure Hash Standard).

Använder SHA med DSA

DSA-parametrar

DSA använder följande parametrar:

1. p är ett primtal p, där 2 L-1 < p < 2 L , 512 =< L =< 1024 och L är en multipel av 64 2. q är en primtalsdelare av p-1, där 2 159 < q < 2 160 3. g = h (p-1)/q mod p, där h är vilket heltal som helst 1 < h < p - 1 så att h ( p-1)/q mod p > 1 4. x är ett slumpmässigt eller pseudoslumpmässigt heltal, där 0 < x < q 5. y = g x mod p 6. k är ett slumpmässigt eller pseudoslumpmässigt heltal, där 0 < k < q.

Heltalen p, q och g kan vara offentliga och kan delas av en grupp människor. x och y är privata respektive publika nycklar. Parametrarna x och k används endast för att generera signaturen och måste hållas hemliga. Parametern k är olika för varje signatur.

Signaturgenerering

Signaturen för meddelandet M är ett par siffror r och s, där

r = (g k mod p) mod q s = (k −1 (SHA(M) + xr)) mod q.

SHA(M) är en 160-bitars binär sträng.

Om r = 0 eller s = 0, måste ett nytt k genereras och en ny signatur beräknas. Om signaturen beräknades korrekt är sannolikheten att r = 0 eller s = 0 mycket liten.

Signaturen skickas tillsammans med meddelandet till mottagaren.

Signaturverifiering

Siffrorna p, q, g och den publika nyckeln är offentliga.

Låt M', r' och s' vara de mottagna versionerna av M, r och s, och låt y vara den publika nyckeln. När du verifierar en signatur måste du först se om följande ojämlikheter håller:

0 < r' < q 0 < s' < q.

Om minst en ojämlikhet inte är uppfylld ska signaturen avvisas. Om ojämlikhetsvillkoren är uppfyllda görs följande beräkningar:

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.

Om v = r', så bekräftas signaturens äkthet.

Om v ≠ r', kan meddelandet ha ändrats, meddelandet kan ha blivit felaktigt signerat eller meddelandet kan ha undertecknats av en bedragare. I det här fallet ska mottagna data anses vara korrupta.

Generering av primtal för DSA

Det här avsnittet innehåller algoritmer för att generera p- och q-primtal för DSA. Dessa algoritmer använder en slumptalsgenerator.

Probabilistiskt primalitetstest

För att generera primtal p och q behövs ett primalitetstest. Det finns flera snabba sannolikhetstester. I vårt fall kommer en förenklad version av Miller-Rabin-testet att användas . Om testet upprepas n gånger kommer det att producera ett primtal med en felsannolikhet på högst 1/4 n . För att kontrollera om ett heltal är primtal måste du:

Steg 1. Sätt i = 1 och välj n>=50. Steg 2. Jämställ w med talet som testas och representera det som w = 1 + 2 a m, där m är ett udda tal. Steg 3. Generera ett slumptal b: 1 < b < w. Steg 4. Ställ in j = 0 och z = b m mod w. Steg 5. Om j = 0 och z = 1, eller om z = w - 1, gå sedan till steg 9. Steg 6. Om j > 0 och z = 1, gå sedan till steg 8. Steg 7. j = j + 1. Om j < a, ställ in z = z 2 mod w och gå till steg 5. Steg 8. w är inte enkelt. Sluta. Steg 9. Om i < n, ställ in i = i + 1 och gå till steg 3. Annars kanske w är ett primtal.

Generering av primtal

DSS kräver två primtal p och q, som måste uppfylla följande villkor:

2 159 < q < 2 160 2 L-1 < p < 2 L , där L = 512 + 64j, och 0 <= j < = 8 p - 1 är delbart med q.

För att generera ett enkelt q: 2 159 < q < 2 160 , SHA-1 och ett SEED-frö används. Därefter används SEED-numret för att skapa talet X: 2 L-1 < X < 2 L . Ett primtal p erhålls genom att avrunda X så att det resulterande talet är 1 mod 2q.

Låt L - 1 = n*160 + b, där b och n är heltal och tar värden från 0 till 160.

Steg 1. Vi väljer en godtycklig sekvens på minst 160 bitar och kallar det SEED. Låt g vara längden på SEED i bitar. Steg 2. Beräkna U = SHA[SEED] XOR SHA[(SEED+1) mod 2 g ]. Steg 3. Skapa q från U genom att ställa in LSB och MSB till 1: q = U ELLER 2 159 ELLER 1. Observera att 2 159 < q < 2 160 . Steg 4. Kontrollera q för enkelhetens skull. Steg 5. Om q inte är enkelt, gå till steg 1. Steg 6. Låt räknaren = 0 och offset = 2. Steg 7. För k = 0,...,n beräkna Vk = SHA[(SEED + offset + k) mod 2 g ]. Steg 8 Beräkna 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 . Observera att 0 <= W < 2 L-1 och 2 L-1 <= X < 2 L . Steg 9. Låt c = X mod 2q och p = X - (c - 1). Observera att p är lika med 1 mod 2q. Steg 10. Om p < 2 L-1, gå till steg 13. Steg 11. Kontrollera p för enkelhetens skull. Steg 12. Om p klarade testet i steg 11, gå till steg 15. Steg 13. räknare = räknare + 1 och offset = offset + n + 1. Steg 14. Om räknare >= 2 12 = 4096 gå till steg 1, annars gå till steg 7. Steg 15 Spara SEED och räknare för att bekräfta att p och q genererades korrekt.

Generering av slumptal för DSA

Varje DSA-implementering kräver slumpmässiga eller pseudo-slumpmässiga heltal. Dessa nummer väljs med metoderna som beskrivs i detta avsnitt eller andra FIPS -godkända metoder.

Algoritmen i avsnitt 7.1 kan användas för att generera x. Algoritmen för k och r beskrivs i avsnitt 7.2. Algoritmerna använder en envägsfunktion (en funktion vars reciproka är mycket svår att beräkna) G(t, c) där t är 160 bitar, c är b bitar (160 < b < 512) och G(t, c) är 160 bitar. G kan skapas med hjälp av Secure Hash Algorithm ( SHA-1 ) eller med hjälp av Data Encryption Standard ( DES ), som beskrivs i avsnitt 7.3 respektive 7.4.

Algoritm för att beräkna m värden för ett tal x

Låt x vara undertecknarens privata nyckel. Följande algoritm kan användas för att generera m värden på x:

Steg 1. Välj ett nytt värde för den ursprungliga nyckeln, XKEY. Steg 2. I hexadecimalt talsystem t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. Detta är initialvärdet för H 0 ||H 1 ||H 2 ||H 3 ||H 4 i SHS. Steg 3. För j = 0..m - 1 a. XSEED j = valfritt värde angett av användaren. b. XVAL = (XKEY + XSEED j ) mod 2 b . c. xj = G(t, XVAL ) mod q. d. XKEY = (1 + XKEY + x j ) mod 2 b .

Algoritm för förberäkning av k och r

Denna algoritm kan användas för att förberäkna k, k −1 och r för m meddelanden samtidigt. Algoritm:

Steg 1. Välj ett hemligt frö för KKEY. Steg 2. I hexadecimalt talsystem t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Detta är det initiala skiftet för H 0 ||H 1 ||H 2 ||H 3 ||H 4 i SHS. Steg 3. För j = 0..m - 1: a. k = G(t,KKEY) mod q. b. Beräkna k j −1 = k −1 mod q. c. Beräkna r j = (g k mod p) mod q. d. KKEY = (1 + KKEY + k) mod 2 b . Steg 4. Antag att M 0 , ... , M m-1 är nästa m meddelanden. För j = 0..m - 1: a. Låt h = SHA(M j ). b. s j = (k j −1 (h + xr j )) mod q. c. r j ,s j ) - signatur för M j . Steg 5. t = h. Steg 6. Gå till steg 3.

Steg 3 gör det möjligt att beräkna de kvantiteter som behövs för att signera nästa m meddelanden. Steg 4 utförs omedelbart efter att dessa m meddelanden har tagits emot.

Skapa en G-funktion med SHA

G(t, c) kan erhållas med SHA-1 , men innan dess måste {H j } och M 1 initieras enligt följande:

1. Initiera {Hj} och dela 160-bitarsvärdet t i fem 32-bitars segment: t = t 0 ||t 1 ||t 2 ||t 3 ||t 4 Då Hj = t j ​​​​för j = 0..4. 2. Meddelandeblock M 1 definieras enligt följande: Mi = c||0 512-b (De första b-bitarna i meddelande Mi innehåller c, och de återstående (512-b) bitarna sätts till noll).

Efter det exekveras SHA-1 [1] och vi får en 160-bitars sträng G(t, c), representerad som:

Ho || Hi || H2 || H3 || H4 . _

Skapa en G-funktion med DES

Låt a XOR b beteckna bitvis XOR ( modulo 2 addition ). Låt a 1 , a 2 , b 1 , b 2  vara 32-rader. Låt b 1 ' vara de minst signifikanta 24 bitarna av b 1 . Låt K = b 1 '||b 2 och A = a 1 ||a 2 . Beteckna

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

DES K (A) betecknar normal DES-kryptering [2] av ett 64-bitars block A med en 56-bitars nyckel K. Antag att t och c vardera är 160 bitar. För att beräkna G(t, c):

Steg 1. Inspelning t = t 1 ||t 2 ||t 3 ||t 4 ||t 5 c = c 1 ||c 2 ||c 3 ||c 4 ||c 5 Varje t i och c i är 32 bitar. Steg 2. För i = 1..5: x i = t i XOR c i Steg 3. För 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 bitar) Steg 4. För i = 1..5: z i = y i,1 XOR y ((i+1) mod 5)+1,2 XOR y ((i+2) mod 5)+1,1 Steg 5. G(t,c) = z 1 | |z 2 ||z 3 ||z 4 ||z 5

Generering av andra parametrar

Det här avsnittet tillhandahåller algoritmer för att generera g, k −1 och s −1 som används i DSS. För att generera g:

Steg 1. Generering av p och q beskrivs ovan. Steg 2. Låt e = (p - 1)/q. Steg 3. Jämställ h med valfritt heltal: 1 < h < p - 1. Steg 4. g = h e mod sid. Steg 5. Om g = 1, gå till steg 3.

För att beräkna n −1 mod q, där 0 < n < q och 0 < n −1 < q:

Steg 1. i = q, h = n, v = 0 och d = 1. Steg 2. Låt t = i DIV h, där DIV är heltalsdivision. Steg 3. x = h. Steg 4. h = i - tx. Steg 5. i = x. Steg 6. x = d. Steg 7. d = v - tx. Steg 8. v = x. Steg 9. Om h > 0, gå till steg 2. Steg 10. Låt n −1 = v mod q.

Observera att vid steg 10 kan v vara negativ.

DSA-exempel

Låt L = 512 (storlek p). I det här exemplet kommer alla värden att vara i hexadecimal notation. P- och q-värdena genererades enligt beskrivningen ovan med följande 160-bitars SEED-värde:

SEED = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3

Med denna SEED, algoritmen hittade p och q vid tidräknaren = 105. x genererades med hjälp av algoritmen som beskrivs i avsnitt 7.1 med hjälp av SHA-1 för att generera G (avsnitt 7.3) 160-bitars XKEY:

XKEY=bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6 t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 x = G(t,XKEY) mod q

k genererades enligt beskrivningen i avsnitt 7.2 med SHA-1 för att generera G (avsnitt 7.3) 160-bitars KKEY:

KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584 t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 k = G(t,KKEY) mod q

Till sist:

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 = ordet "abc" från det engelska alfabetet ( 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

Anteckningar

  1. ↑ FIPS PUB 180-1  (engelska)  (länk ej tillgänglig) . — Beskrivning av SHS-standarden. Arkiverad från originalet den 7 april 2012.
  2. ↑ FIPS PUB 46-3  (eng.)  (inte tillgänglig länk) . — Beskrivning av DES-standarden. Arkiverad från originalet den 7 april 2012.

Länkar

Utländsk

Ryssar

Implementering

 Public key kryptosystem
Algoritmer
Faktorisering av heltal
Diskret logaritm
Kryptografi på galler
Övrig
Teori
Standarder
Ämnen