| DSS, digitális aláírás szabvány | |
|---|---|
| Teremtő | Nemzeti Szabványügyi és Technológiai Intézet |
| Létrehozva | 1991. augusztus |
| Kulcsméret | 512-1024 bit |
| Aláírás mérete | két 160 bites szám |
A DSS ( Digital Signature Standard ) egy amerikai szabvány, amely leírja a digitális aláírás generálására használható Digital Signature Algorithm ( DSA ) algoritmust . A digitális aláírás az adatváltozás megállapítására és az aláíró hitelesítésére szolgál. Az aláírt adat címzettje a digitális aláírással harmadik fél felé bizonyíthatja, hogy az aláírást valóban a feladó írta.
Amikor üzenet érkezik, a címzett ellenőrizheti, hogy az üzenet nem módosult-e az átvitel során. Előfordulhat, hogy a címzett ellenőrizni szeretné az aláíró személyazonosságát. A DSA ezt lehetővé teszi.
A DSA-t az egyik oldal az adataláírás generálására, a másik oldal pedig az előfizető hitelesítésére használja. Az aláírás a privát kulcs segítségével jön létre. Bármely fél ellenőrizheti a digitális aláírás hitelességét a nyilvános kulcs segítségével. A nyilvános kulcsot az aláírt adatokkal együtt elküldjük. A nyilvános és a privát kulcs nem egyezik.
Aláírás generálásakor egy hash függvényt használunk az adatok tömörített verziójának beszerzésére. A kapott adatokat a DSA feldolgozza digitális aláírás beszerzése céljából. Ugyanezt a hash függvényt használják az aláírás ellenőrzésére. A hash funkciót az SHS (Secure Hash Standard) írja le.
| SHA használata DSA-val |
|---|
A DSA a következő paramétereket használja:
1. p egy p prímszám, ahol 2 L-1 < p < 2 L , 512 =< L =< 1024 és L 64 többszöröse 2. q a p-1 prímosztója, ahol 2 159 < q < 2 160 3. g = h (p-1)/q mod p, ahol h bármely 1 < h < p - 1 egész szám, amelyre h (p-1)/q mod p > 1 4. x egy véletlenszerű vagy pszeudovéletlen egész szám, ahol 0 < x < q 5. y = g x mod p 6. k egy véletlenszerű vagy pszeudovéletlen egész szám, ahol 0 < k < q.A p, q és g egész számok nyilvánosak lehetnek, és egy csoport megoszthatja őket. x és y privát, illetve nyilvános kulcsok. Az x és k paraméterek csak az aláírás generálására szolgálnak, és ezeket titokban kell tartani. A k paraméter minden aláírásnál más.
Az M üzenet aláírása egy r és s számpár, ahol
Az SHA(M) egy 160 bites bináris karakterlánc.
Ha r = 0 vagy s = 0, új k-t kell generálni, és új aláírást kell kiszámítani. Ha az aláírást helyesen számítottuk ki, nagyon kicsi annak a valószínűsége, hogy r = 0 vagy s = 0.
Az aláírást az üzenettel együtt elküldik a címzettnek.
A p, q, g számok és a nyilvános kulcs nyilvánosak.
Legyen M', r' és s' az M, r és s kapott változata, y pedig a nyilvános kulcs. Az aláírás ellenőrzésekor először meg kell vizsgálnia, hogy a következő egyenlőtlenségek fennállnak-e:
0 < r' < q 0 < s' < q.Ha legalább egy egyenlőtlenség nem teljesül, az aláírást el kell utasítani. Ha az egyenlőtlenségi feltételek teljesülnek, a következő számításokat kell elvégezni:
Ha v = r', akkor az aláírás hitelessége megerősítést nyer.
Ha v ≠ r', akkor előfordulhat, hogy az üzenetet megváltoztatták, az üzenetet helytelenül írták alá, vagy az üzenetet csaló írta alá. Ebben az esetben a kapott adatokat sérültnek kell tekinteni.
Ez a szakasz a DSA számára p és q prímek generálására szolgáló algoritmusokat tartalmaz. Ezek az algoritmusok véletlenszám-generátort használnak.
A p és q prímek generálásához primalitásteszt szükséges. Számos gyors valószínűségi teszt létezik. Esetünkben a Miller-Rabin teszt egyszerűsített változatát használjuk . Ha a tesztet n-szer megismételjük, akkor legfeljebb 1/4 n hibavalószínűségű prímszámot ad . Annak ellenőrzéséhez, hogy egy egész szám prímszám-e, a következőket kell tennie:
1. lépés Állítsa be az i = 1 értéket, és válassza az n>=50 értéket. 2. lépés: Egyenlítse w-t a tesztelt számmal, és ábrázolja w = 1 + 2 a m-ként, ahol m egy páratlan szám. 3. lépés: Generáljon egy véletlenszámot b: 1 < b < w. 4. lépés Állítsa be j = 0 és z = b m mod w. 5. lépés: Ha j = 0 és z = 1, vagy ha z = w - 1, akkor folytassa a 9. lépéssel. 6. lépés Ha j > 0 és z = 1, akkor folytassa a 8. lépéssel. 7. lépés j = j + 1. Ha j < a, akkor állítsa be a z = z 2 mod w értéket, és folytassa az 5. lépéssel. 8. lépés w nem egyszerű. Állj meg. 9. lépés Ha i < n, akkor állítsa be az i = i + 1 értéket, és folytassa a 3. lépéssel. Ellenkező esetben w egy prímszám.A DSS-hez 2 p és q prím szükséges, amelyeknek meg kell felelniük a következő feltételeknek:
2 159 < q < 2 160 2 L-1 < p < 2 L , ahol L = 512 + 64j, és 0 <= j < = 8 p - 1 osztható q-val.Egy egyszerű q generálásához: 2 159 < q < 2 160 , SHA-1 és egy SEED magot használunk. Ezt követően a SEED számot használjuk az X szám létrehozásához: 2 L-1 < X < 2 L . Egy p prímértéket úgy kapunk, hogy X-et úgy kerekítünk, hogy a kapott szám 1 mod 2q legyen.
Legyen L - 1 = n*160 + b, ahol b és n egész számok, és 0 és 160 közötti értékeket vesznek fel.
1. lépés: Válasszunk ki egy tetszőleges, legalább 160 bites sorozatot, és SEED-nek nevezzük. Legyen g a SEED hossza bitekben. 2. lépés: Számítsa ki az U = SHA[MAGVET] XOR SHA[(SEED+1) mod 2 g ]. 3. lépés: Hozzon létre q-t U-ból az LSB és az MSB 1-re állításával: q = U VAGY 2 159 VAGY 1. Vegye figyelembe, hogy 2 159 < q < 2 160 . 4. lépés. Ellenőrizze a q-t az egyszerűség kedvéért. 5. lépés Ha q nem egyszerű, folytassa az 1. lépéssel. 6. lépés. Legyen a számláló = 0 és az eltolás = 2. 7. lépés. Ha k = 0,...,n számítja ki Vk = SHA[(SEED + offset + k) mod 2 g ]. 8. lépés Számítsa ki 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 . Vegye figyelembe, hogy 0 <= W < 2 L-1 és 2 L-1 <= X < 2 L . 9. lépés. Legyen c = X mod 2q és p = X - (c - 1). Vegye figyelembe, hogy p egyenlő 1 mod 2q-val. 10. lépés Ha p < 2 L-1 , akkor folytassa a 13. lépéssel. 11. lépés. Az egyszerűség kedvéért ellenőrizze a p-t. 12. lépés Ha p sikeresen teljesítette a 11. lépésben szereplő tesztet, folytassa a 15. lépéssel. 13. lépés számláló = számláló + 1 és eltolás = eltolás + n + 1. 14. lépés: Ha a számláló >= 2 12 = 4096, folytassa az 1. lépéssel, ellenkező esetben folytassa a 7. lépéssel. 15. lépés Mentse el a SEED-et és a számlálót, hogy megbizonyosodjon arról, hogy p és q megfelelően lett generálva.Bármely DSA-megvalósítás véletlenszerű vagy pszeudo-véletlen egész számokat igényel. Ezeket a számokat az ebben a részben leírt módszerekkel vagy más FIPS által jóváhagyott módszerekkel választja ki.
A 7.1. szakaszban található algoritmus használható x generálására. A k és r algoritmusát a 7.2. Az algoritmusok egy egyirányú függvényt (egy olyan függvényt használnak, amelynek reciprokát nagyon nehéz kiszámítani) G(t, c), ahol t 160 bit, c b bit (160 < b < 512) és G(t, c) 160 bit. A G a Secure Hash Algorithm ( SHA-1 ) vagy az Adattitkosítási Szabvány ( DES ) használatával hozható létre , amelyeket a 7.3, illetve a 7.4 szakaszban ismertetünk.
Legyen x az aláíró privát kulcsa. A következő algoritmus használható x m értékének generálására:
1. lépés: Válasszon új értéket az eredeti kulcshoz, XKEY. 2. lépés Hexadecimális számrendszerben t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0.Ez a H 0 ||H 1 ||H 2 ||H 3 ||H 4 kezdeti értéke az SHS-ben. 3. lépés: j = 0..m - 1 esetén a. XSEED j = a felhasználó által megadott opcionális érték. b. XVAL = (XKEY + XSEED j ) mod 2 b . c. xj = G(t, XVAL ) mod q. d. XKEY = (1 + XKEY + x j ) mod 2 b .Ezzel az algoritmussal k, k −1 és r előre számítható m üzenetre egyidejűleg. Algoritmus:
1. lépés: Válasszon ki egy titkos magot a KKEY számára. 2. lépés Hexadecimális számrendszerben t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Ez a H 0 ||H 1 ||H 2 ||H 3 ||H 4 kezdeti eltolódása az SHS-ben. 3. lépés: j = 0..m - 1 esetén: a. k = G(t,KKEY) mod q. b. Számítsuk ki k j −1 = k −1 mod q. c. Számítsuk ki r j = (g k mod p) mod q-t. d. KKEY = (1 + KKEY + k) mod 2 b . 4. lépés. Tegyük fel, hogy M 0 , ... , M m-1 a következő m üzenet. j = 0..m - 1 esetén: a. Legyen h = SHA(M j ). b. s j = (k j −1 (h + xr j )) mod q. c. r j ,s j ) - M j aláírása . 5. lépés t = h. 6. lépés Folytassák a 3. lépéssel.A 3. lépés lehetővé teszi a következő m üzenet aláírásához szükséges mennyiségek kiszámítását. A 4. lépés azonnal végrehajtódik, miután ezek az m üzenetek megérkeztek.
G(t, c) megkapható az SHA-1 segítségével , de előtte {H j } és M 1 inicializálni kell az alábbiak szerint:
1. Inicializálja a {Hj}-t, ossza fel a t 160 bites értéket öt 32 bites szegmensre: t = t 0 ||t 1 ||t 2 ||t 3 ||t 4 Ekkor Hj = t j , ha j = 0..4.2. Az M1 üzenetblokk meghatározása a következő: M 1 = c||0 512-b (Az M 1 üzenet első b bitje c-t tartalmaz, a fennmaradó (512-b) bit pedig nullára van állítva).Ezután az SHA-1 [1] végrehajtásra kerül , és egy 160 bites G(t, c) karakterláncot kapunk, amelyet a következőképpen ábrázolunk:
H 0 ||H 1 ||H 2 ||H 3 ||H 4 .Jelölje a XOR b bitenkénti XOR-t ( modulo 2 összeadás ). Legyen a 1 , a 2 , b 1 , b 2 32 soros. Legyen b 1 ' b 1 legkisebb jelentőségű 24 bitje . Legyen K = b 1 '||b 2 és A = a 1 ||a 2 . Jelöli
DES b1,b2 (a 1 ,a 2 ) = DES K (A)A DES K (A) egy 64 bites A blokk normál DES titkosítását [2] jelöli 56 bites K kulccsal. Tegyük fel, hogy t és c egyaránt 160 bites. G(t, c) kiszámításához:
1. lépés Felvétel t = t 1 ||t 2 ||t 3 ||t 4 ||t 5 c = c 1 ||c 2 ||c 3 ||c 4 ||c 5 Mindegyik t i és c i 32 bites. 2. lépés: i = 1...5 esetén: x i = t i XOR c i 3. lépés: i = 1...5 esetén: 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) 4. lépés: i = 1...5 esetén: z i = y i,1 XOR y ((i+1) mod 5)+1,2 XOR y ((i+2) mod 5)+1,1 5. lépés. G(t,c) = z 1 | |z 2 ||z 3 ||z 4 ||z 5Ez a szakasz a DSS-ben használt algoritmusokat tartalmazza g, k −1 és s −1 generálására. A g generálásához:
1. lépés: p és q generálását fentebb leírtuk. 2. lépés Legyen e = (p - 1)/q. 3. lépés. Adja meg h tetszőleges egész számnak: 1 < h < p - 1. 4. lépés g = h e mod p. 5. lépés Ha g = 1, folytassa a 3. lépéssel.Az n −1 mod q kiszámításához , ahol 0 < n < q és 0 < n −1 < q:
1. lépés: i = q, h = n, v = 0 és d = 1. 2. lépés. Legyen t = i DIV h, ahol DIV egész osztás. 3. lépés x = h. 4. lépés h = i - tx. 5. lépés i = x. 6. lépés x = d. 7. lépés d = v - tx. 8. lépés v = x. 9. lépés Ha h > 0, folytassa a 2. lépéssel. 10. lépés. Legyen n −1 = v mod q.Vegye figyelembe, hogy a 10. lépésben v lehet negatív.
Legyen L = 512 (p méret). Ebben a példában minden érték hexadecimális jelöléssel lesz megadva. A p és q értékeket a fent leírtak szerint generáltuk a következő 160 bites SEED értékkel:
SEED = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3Ezzel a SEED-del az algoritmus p és q értéket talált az időszámlálónál = 105. Az x-et a 7.1. szakaszban leírt algoritmussal generáltuk az SHA-1 használatával a G (7.3. szakasz) 160 bites XKEY létrehozásához:
XKEY=bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6 t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 x = G(t,XKEY) mod qA k-t a 7.2 szakaszban leírtak szerint generáltuk az SHA-1 használatával a G (7.3 szakasz) 160 bites KKEY generálásához:
KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584 t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 k = G(t,KKEY) mod qVégül:
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 = az "abc" szó az angol ábécéből ( 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