Algoritmus digitálneho podpisu

Algoritmus digitálneho podpisu (DSA) je kryptosystém s verejným kľúčom a federálny štandard spracovania informácií pre digitálne podpisy, založený na matematickom koncepte modulárnej exponencie a probléme diskrétneho logaritmu. DSA je variantom podpisových schém Schnorr a ElGamal.
Národný inštitút pre štandardy a technológie (NIST) navrhol DSA na použitie vo svojom Štandarde Digitálneho Podpisu (DSS) v roku 1991 a v roku 1994 ho prijal ako FIPS 186. Boli vydané štyri revízie pôvodnej špecifikácie. Najnovšia špecifikácia je: FIPS 186-4 z júla 2013. DSA je patentovaný, ale NIST tento patent sprístupnil celosvetovo bez licenčných poplatkov. V návrhu verzie špecifikácie FIPS 186-5 sa uvádza, že DSA už nebude schválená na generovanie digitálnych podpisov, ale môže sa používať na overovanie podpisov vytvorených pred dátumom implementácie tejto normy.
Prehľad.
DSA funguje v rámci kryptosystémov s verejným kľúčom a je založený na algebraických vlastnostiach modulárnej exponencie spolu s problémom diskrétneho logaritmu, ktorý sa považuje za výpočtovo ťažko riešiteľný. Algoritmus používa kľúčový pár pozostávajúci z verejného a súkromného kľúča. Súkromný kľúč sa používa na generovanie digitálneho podpisu správy a takýto podpis sa dá overiť pomocou príslušného verejného kľúča podpisovateľa. Digitálny podpis zabezpečuje autentifikáciu správy (príjemca môže overiť pôvod správy), integritu (príjemca môže overiť, že správa nebola od jej podpísania zmenená) a nepopierateľnosť (odosielateľ nemôže nepravdivo tvrdiť, že správu nepodpísal).
História.
V roku 1982 vláda USA požiadala o predloženie návrhov na štandard podpisu verejným kľúčom. V auguste 1991 Národný inštitút pre štandardy a technológie (NIST) navrhol DSA na použitie vo svojom štandarde digitálneho podpisu (DSS). Spočiatku sa stretol so značnou kritikou, najmä zo strany softvérových spoločností, ktoré už investovali úsilie do vývoja softvéru na digitálny podpis založeného na kryptosystéme RSA. Napriek tomu NIST v roku 1994 prijal DSA ako federálny štandard (FIPS 186). Boli vydané štyri revízie pôvodnej špecifikácie: FIPS 186-1 v roku 1998, FIPS 186-2 v roku 2000,FIPS 186-3 v roku 2009 a FIPS 186-4 v roku 2013. Návrh verzie normy FIPS 186-5 zakazuje podpisovanie pomocou DSA, pričom umožňuje overovanie podpisov vytvorených pred dátumom implementácie normy. Má byť nahradená novšími podpisovými schémami, ako je EdDSA.
Na DSA sa vzťahuje na U.S. Patent 5 231 668, ktorý bol podaný 26. júla 1991 a ktorého platnosť už vypršala a ktorý sa pripisuje Davidovi W. Kravitzovi, bývalému zamestnancovi NSA. Tento patent bol udelený "Spojeným štátom americkým zastúpeným Ministerstvom obchodu, Washington, D.C." a NIST tento patent sprístupnil celosvetovo bez licenčných poplatkov. Claus P. Schnorr tvrdí, že jeho U.S. Patent 4 995 082 (tiež už neplatný) pokrýva DSA; toto tvrdenie je sporné.
Operácia.
Algoritmus DSA zahŕňa štyri operácie: generovanie kľúča (čím sa vytvorí kľúčový pár), distribúciu kľúča, podpisovanie a overenie podpisu.
1. Generovanie kľúčov.
Generovanie kľúčov má dve fázy. V prvej fáze sa vyberajú parametre algoritmu, ktoré môžu byť spoločné pre rôznych používateľov systému, zatiaľ čo v druhej fáze sa vypočíta jeden pár kľúčov pre jedného používateľa.
Generovanie parametrov.
Parametre algoritmu sú formula_26. Tieto môžu byť zdieľané medzi rôznymi používateľmi systému.
Kľúče pre jednotlivých používateľov.
Pri danom súbore parametrov sa v druhej fáze vypočíta dvojica kľúčov pre jedného používateľa:
formula_27 je súkromný kľúč a formula_31 je verejný kľúč.
2. Distribúcia kľúčov.
Podpisovateľ by mal zverejniť verejný kľúč formula_31. To znamená, že by mal poslať kľúč príjemcovi prostredníctvom spoľahlivého, ale nie nevyhnutne tajného mechanizmu. Podpisovateľ by mal udržať súkromný kľúč formula_27 v tajnosti.
3. Podpisovanie.
Správa formula_34 je podpísaná takto:
Podpis je formula_43
Výpočet formula_35 a formula_45 sa rovná vytvoreniu nového kľúča na správu. Modulárna exponenciácia pri výpočte formula_45 je výpočtovo najnáročnejšia časť operácie podpisovania, ale môže sa vypočítať skôr, ako je známa správa. Výpočet modulárnej inverzie formula_47 je druhou najzložitejšou časťou a tiež sa môže vypočítať skôr, ako je známa správa. Môže sa vypočítať pomocou rozšíreného Euklidovho algoritmu alebo pomocou Fermatovej malej vety ako formula_48.
4. Overovanie podpisov.
Možno overiť, že podpis "(r,s)" je platný podpis pre správu "m" takto:
Správnosť algoritmu.
Podpisová schéma je správna v tom zmysle, že overovateľ vždy akceptuje pravé podpisy. To sa dá dokázať takto:
Po prvé, keďže formula_55, vyplýva, že formula_56 podľa Fermatovej malej vety. Keďže formula_57 a formula_15 je prvočíslo, formula_59 musí byť rádu formula_15 .
Podpisovateľ vypočíta
formula_61
Preto
formula_62
Keďže formula_59 je rádu formula_15 my máme
formula_65
Nakoniec, správnosť DSA vyplýva z
formula_66
Citlivosť.
Pri DSA sú rozhodujúce entropia, utajenie a jedinečnosť náhodnej hodnoty podpisu "k". Je taká kritická, že porušenie ktorejkoľvek z týchto troch požiadaviek môže útočníkovi odhaliť celý súkromný kľúč. Použitie tej istej hodnoty dvakrát (aj pri zachovaní tajnosti "k"), použitie predvídateľnej hodnoty alebo únik aj niekoľkých bitov "k" v každom z niekoľkých podpisov stačí na odhalenie súkromného kľúča "x".
Tento problém sa týka algoritmu DSA aj algoritmu ECDSA (Elliptic Curve Digital Signature Algorithm) - v decembri 2010 skupina, ktorá si hovorí fail0verflow, oznámila obnovenie súkromného kľúča ECDSA, ktorý používala spoločnosť Sony na podpisovanie softvéru pre hernú konzolu PlayStation 3. Útok bol možný, pretože spoločnosť Sony nedokázala pre každý podpis vygenerovať nový náhodný "k".
Tomuto problému sa dá predísť deterministickým odvodením "k" zo súkromného kľúča a hashu správy, ako to opisuje RFC 6979. Tým sa zabezpečí, že "k" je pre každý "H(m)" iný a nepredvídateľný pre útočníkov, ktorí nepoznajú súkromný kľúč "x".
Okrem toho je možné vytvoriť škodlivé implementácie DSA a ECDSA, v ktorých je zvolený "k" s cieľom podprahového úniku informácií prostredníctvom podpisov. Napríklad offline súkromný kľúč by mohol uniknúť z dokonalého offline zariadenia, ktoré by vydalo len nevinne vyzerajúce podpisy.
Implementácie.
Nižšie je uvedený zoznam kryptografických knižníc, ktoré poskytujú podporu pre DSA: