DSA

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. září 2016; kontroly vyžadují 76 úprav .

DSA, Algoritmus digitálního podpisu
Tvůrce	NIST
Vytvořeno	1991
zveřejněno	1998
Velikost klíče	zavřeno: 160-256 bitů, otevřeno: 1024-3072 bitů
Velikost podpisu	dvě čísla 160-256 bitů

DSA ( Digital Signature Algorithm - digitální podpisový algoritmus ) - kryptografický algoritmus využívající soukromý klíč ( z páru klíčů: <public; private>) k vytvoření elektronického podpisu , nikoli však k šifrování (na rozdíl od RSA a schématu ElGamal ). Podpis je vytvořen tajně (soukromý klíč), ale může být veřejně ověřen (veřejný klíč). To znamená, že pouze jeden subjekt může vytvořit podpis zprávy, ale kdokoli může ověřit, že je správný. Algoritmus je založen na výpočetní složitosti logaritmů v konečných polích .

Algoritmus byl navržen National Institute of Standards and Technology ( USA ) v srpnu 1991 a je patentován [1] (autor patentu - David W. Kravitz), NIST tento patent zpřístupnil pro použití bez licenčních poplatků . DSA je součástí DSS ( Digital Signature Standard), poprvé zveřejněného 15. prosince 1998 (dokument FIPS-186 [2] ( Federal Information Processing Standards ) . Standard byl několikrát aktualizován [3] [4] , nejnovější verze je FIPS-186-4 [5] . (Červenec 2013).

Popis algoritmu

DSA obsahuje dva algoritmy (S, V): pro vytvoření podpisu zprávy (S) a pro jeho ověření (V).

Oba algoritmy nejprve vypočítají hash zprávy pomocí kryptografické hashovací funkce . Algoritmus S používá k vytvoření podpisu hash a tajný klíč, algoritmus V používá k ověření podpisu hash zprávy, podpis a veřejný klíč.

Je třeba zdůraznit, že ve skutečnosti není podepsána zpráva (libovolně dlouhé), ale její hash (160 - 256 bitů), kolize jsou proto nevyhnutelné a jeden podpis obecně platí pro několik zpráv se stejným hashem. . Proto je výběr dostatečně „dobré“ hashovací funkce velmi důležitý pro celý systém jako celek. První verze standardu používala hashovací funkci SHA-1 [6] [2] ( Secure Hash Algorithm - secure hash algorithm) , v nejnovější verzi můžete použít i libovolný algoritmus rodiny SHA-2 [6] [5 ] . V srpnu 2015 byl publikován FIPS-202 [7] popisující novou hashovací funkci SHA-3 . Dnes ale není součástí standardu DSS [5] .

Systém vyžaduje korespondenci mezi skutečnými údaji o autorovi (může to být jednotlivec nebo organizace) a veřejnými klíči a také všechny potřebné parametry schématu digitálního podpisu (hashovací funkce, prvočísla ). Jako takový základ může sloužit například certifikační autorita .

Možnosti schématu digitálního podpisu

Chcete-li vytvořit systém digitálního podpisu, musíte provést následující kroky:

Volba kryptografické hašovací funkce H(x).
Výběr prvočísla q , jehož rozměr N v bitech je stejný jako rozměr v bitech hash hodnot H(x).
Volba prvočísla p takové, že (p-1) je dělitelné q . Bitová délka p je označena L .
Volba čísla g ( ) takové, že jeho multiplikativní řád modulo p se rovná q . K jeho výpočtu můžete použít vzorec , kde h je nějaké libovolné číslo takové, že . Ve většině případů hodnota h = 2 tento požadavek splňuje. [5] $g\neq 1$ $g=h^{{(p-1)/q}}\mod p$ $h\in(1;p-1)$ $g\neq 1$

Jak bylo zmíněno výše, primárním parametrem schématu digitálního podpisu je kryptografická hašovací funkce používaná k převodu textu zprávy na číslo , pro které je podpis vypočítán. Důležitou charakteristikou této funkce je bitová délka výstupní sekvence, níže označená N . V první verzi standardu DSS je doporučena funkce SHA-1 [2] a podle toho je bitová délka podepsaného čísla 160 bitů. Nyní SHA-1 již není dostatečně bezpečný [8] [9] . Norma specifikuje následující možné dvojice hodnot pro čísla L a N :

L=1024, N=160
L=2048, N=224
L=2048, N=256
L=3072, N=256

Podle tohoto standardu jsou doporučeny hašovací funkce rodiny SHA-2 . Vládní organizace USA musí použít jednu z prvních tří možností, CA musí použít pár, který je stejný nebo větší než pár používaný předplatiteli [5] . Návrhář systému si může vybrat jakoukoli platnou hashovací funkci. Další pozornost proto nebude zaměřena na použití konkrétní hashovací funkce.

Síla kryptosystému na bázi DSA nepřesahuje sílu použité hašovací funkce a sílu páru (L,N), jehož síla není větší než síla každého z čísel samostatně. Je také důležité zvážit, jak dlouho musí systém zůstat bezpečný. V současné době se pro systémy, které musí být perzistentní do roku 2010 ( 2030 ), doporučuje délka 2048 (3072) bitů. [5] [10]

Veřejné a soukromé klíče

Tajný klíč je číslo $x\in(0,q)$
Veřejný klíč se vypočítá pomocí vzorce $y=g^{x}\mod p$

Veřejnými parametry jsou čísla (p, q, g, y) . Existuje pouze jeden soukromý parametr – číslo x . V tomto případě mohou být čísla (p, q, g) společná pro skupinu uživatelů a čísla x a y jsou soukromé a veřejné klíče konkrétního uživatele. Při podepisování zprávy se používají tajná čísla x a k a číslo k musí být zvoleno náhodně (v praxi pseudonáhodně) při výpočtu podpisu každé další zprávy.

Protože (p, q, g) může být použito pro více uživatelů, v praxi jsou uživatelé často rozděleni podle určitých kritérií do skupin se stejným (p, q, g) . Proto se tyto parametry nazývají parametry domény. [5]

Podpis zprávy

Podpis zprávy se provádí podle následujícího algoritmu [5] :

Výběr náhodného čísla $k\in(0,q)$
výpočet $r=(g^{k}\mod p)\mod q$
Volba jiného k if $r=0$
výpočet $s=k^{{-1}}(H(m)+x\cdot r)\mod q$
Volba jiného k if $s=0$
Podpis je pár celkové délky $(r,s)$ $2N$

Výpočetně složité operace jsou umocňování modulo (výpočet ), pro které existují rychlé algoritmy , výpočet hash , kde složitost závisí na zvoleném hashovacím algoritmu a velikosti vstupní zprávy a nalezení inverzního prvku pomocí např. rozšířeného euklidovského algoritmus nebo Fermatův malý teorém ve formě . $g^{k}{\bmod {p))$ $H(x)$ $k^{-1}{\bmod {q))$ $k^{-1}{\bmod {q}}=k^{q-2}{\bmod {q}}$

Ověření podpisu

Ověření podpisu se provádí podle algoritmu [5] :

1 Výpočet 2 Výpočet 3 Výpočet 4 Výpočet 5 Podpis je správný, pokud

w=s^{{-1}}\mod q

u_{1}=H(m)\cdot w\mod q

u_{2}=r\cdot w\mod q

v=(g^{{u_{1}}}\cdot y^{{u_{2}}}\mod p)\mod q

v=r

Při zaškrtnutí jsou výpočetně složité operace dvě umocnění , výpočet hash a nalezení inverzního prvku . $g^{u_{1}}y^{u_{2}}$ $H(x)$ $s^{-1}{\bmod {q))$

Správnost schématu

Toto schéma digitálního podpisu je správné do té míry, že osoba, která si přeje ověřit pravost podpisu, vždy obdrží kladný výsledek v případě pravosti. Pojďme si to ukázat:

Nejprve, jestliže , pak z Fermatovy Malé věty vyplývá, že . Protože g >1 a q je prvočíslo, pak g musí mít multiplikativní řád q modulo p . $g=h^{{(p-1)/q}}\mod p$ $g^{q}=h^{{p-1}}=1\mod p$

Chcete-li podepsat zprávu, vypočítává

s=k^{{-1}}(H(m)+x\cdot r)\mod {q}.

Proto

k=H(m)\cdot s^{{-1}}+x\cdot r\cdot s^{{-1}}=H(m)\cdot w+x\cdot r\cdot w\mod { q}.

Protože g je řádu q , dostaneme

g^{k}=g^{{H(m)\cdot w\mod q}}g^{{x\cdot r\cdot w\mod q}}=g^{{H(m)\cdot w \mod q}}y^{{r\cdot w\mod q}}=g^{{u1}}y^{{u2}}\mod {p}.

Nakonec z toho vyplývá správnost schématu DSA

r=(g^{k}\mod p)\mod q=(g^{{u1}}y^{{u2}}\mod p)\mod q=v.

[5]

Příklad práce

Uveďme příklad, jak funguje algoritmus pro malá čísla. Nechte hash hodnotu naší zprávy . $H=9$

Generování parametrů

$H=9_{10}=1001_{2}$
hash length , takže si můžete vybrat $čtyři$ $q=11_{10}=1011_{2}$
vybrat , protože $p=23$ $23-1=22=2*q$
Vybrat $g=2^{2}=4$

Vytváření klíčů

vyberte jako tajný klíč $x=7$
pak veřejný klíč $y=g^{x}{\bmod {p}}=4^{7}{\bmod {2}}3=16384{\bmod {2}}3=(712\cdot 23+8) {\bmod {2}}3=8$

Podpis zprávy

Vybrat $k = 3$
pak $r=(g^{k}{\bmod {p))){\bmod {q}}=(4^{3}{\bmod {2}}3){\bmod {1}}1 =7$
$r\neq 0$ , jdi dál
$s=k^{-1}(H(m)+x\cdot r){\bmod {q}}=4(9+7\cdot 7){\bmod {1}}1=1$ , kde se počítá s tím $3^{-1}{\bmod {1}}1=4$
$s\neq 0$ , jdi dál
podpis je dvojice čísel $(r,s)=(7,1)$

Ověření podpisu

$w=s^{-1}{\bmod {q}}=1^{-1}{\bmod {1}}1=1$
$u_{1}=H(m)\cdot w{\bmod {q}}=9\cdot 1{\bmod {1}}1=9$
$u_{2}=r\cdot w{\bmod {q}}=7\cdot 1{\bmod {1}}1=7$
$v=(g^{u_{1}}\cdot y^{u_{2}}{\bmod {p}}){\bmod {q}}=(4^{9}\cdot 8^ {7}{\bmod {2}}3){\bmod {1}}1=7$
přijato, což znamená, že podpis je správný. $v = r$

Analogy

Algoritmus DSA je založen na obtížnosti výpočtu diskrétních logaritmů a je modifikací klasického schématu ElGamal [11] , kde je přidán hash zprávy a všechny logaritmy jsou počítány pomocí , což umožňuje, aby byl podpis kratší než u analogů. [12] . Na základě schématu ElGamal byly postaveny i další algoritmy, například ruský GOST 34.10-94 , který je nyní považován za zastaralý. Byla nahrazena normou GOST R 34.10-2012 [13] , která používá skupinu bodů eliptické křivky . $mod~q$

Taková úprava, tzn. přechod od multiplikativní skupiny modulo prvočíslo ke skupině bodů eliptické křivky existuje také pro DSA - ECDSA [14] ( Eliptic Curve Digital Signature Algorithm - algoritmus digitálního podpisu na eliptických křivkách) . Používá se například v kryptoměně bitcoin k potvrzování transakcí. Tento překlad umožňuje zmenšit velikost klíčů bez obětování bezpečnosti – v bitcoinovém systému je velikost soukromého klíče 256 bitů a odpovídajícího veřejného klíče 512 bitů.

Další běžný algoritmus veřejného klíče (používaný pro šifrování i digitální podpis), RSA (pojmenovaný podle autorů: Rivest , Shamir , Adleman ), je založen na obtížnosti faktorizace velkých čísel.

Kryptografická síla

Jakýkoli útok na algoritmus lze popsat následovně: útočník obdrží všechny parametry veřejného podpisu a určitou sadu párů (zpráva, podpis) a pokusí se pomocí této sady vytvořit platný podpis pro novou zprávu, která není v sadě zastoupena. .

Tyto útoky lze podmíněně rozdělit do dvou skupin – za prvé se útočník může pokusit získat tajný klíč a poté okamžitě získá příležitost podepsat libovolnou zprávu a za druhé se může pokusit vytvořit platný podpis pro novou zprávu bez přímo obnovit tajný klíč. $X$

Předvídatelnost náhodného parametru

Rovnoměrné rozložení náhodného parametru je velmi důležité pro bezpečnost systému. Pokud je známo několik po sobě jdoucích parametrových bitů pro sérii podpisů, pak může být tajný klíč s vysokou pravděpodobností obnoven. [patnáct] $k$ $k$

Opakování parametru pro dvě zprávy vede k jednoduchému hacknutí systému. To se může stát při použití špatného generátoru pseudonáhodných čísel . Tato chyba zabezpečení v systému PlayStation 3 umožňovala podepisování jakýchkoli programů jménem společnosti Sony . V některých implementacích bitcoinového systému pro Android by útočník mohl získat přístup k peněžence. [16] [17] Oba příklady využívaly systém ECDSA [14] .

Pokud byl stejný parametr použit pro dvě zprávy , jejich podpisy budou mít stejné , ale odlišné , říkejme jim . $m_{1}, m_{2}$ $k$ $(r,s)$ $r$ $s$ ${\displaystyle s_{1},s_{2))$

Z výrazu pro můžeme vyjádřit celkem : $s$ $k$

$k=(H(m)+xr)s^{-1}\mod q$ .

A srovnejte společné pro různé zprávy: $k$

$(H(m_{1})+xr)s_{1}^{-1}\mod q=(H(m_{2})+xr)s_{2}^{-1}\mod q$

Odtud je snadné vyjádřit tajný klíč : $X$

$x={\frac {H(m_{1})s_{1}^{-1}-H(m_{2})s_{2}^{-1}}{r(s_{2} ^{-1}-s_{1}^{-1})}}$

Existenciální padělek

Některé algoritmy digitálního podpisu mohou být napadeny existujícím padělkem (Existenční padělek) . Spočívá v tom, že pro podpis (ať už vůbec náhodný nebo vytvořený podle nějakého pravidla) je možné vytvořit korektní zprávu (která však většinou nedává smysl) pouze pomocí veřejných parametrů.

U schématu DSA je podpis v každém případě platný pro zprávu s hashem . $r=g^{e}y\mod p\mod q$ $s=r$ $E$ $H(m)=es$

To je jeden z důvodů hashování vstupní zprávy. Pokud je hašovací funkce zvolena správně, je algoritmus DSA před tímto útokem chráněn, protože inverze kryptografické hašovací funkce (tj. pro daný nález takový, že ) je výpočetně náročná. [osmnáct] $k$ $m$ $H(m)=k$

Obnova klíče

podmínku správnosti podpisu lze přepsat do jiné podoby:

$g^{ks}\mod p\mod q=g^{H(m)+xr}\mod p\mod q$

tato rovnice je ekvivalentní (protože multiplikativní řád g modulo p se rovná q)

$H(m)\mod q=ks-xr\mod q$

takže můžeme předpokládat, že pro obnovení klíče útočník potřebuje vyřešit systém rovnic formuláře

$H(m_{i})\mod q=k_{i}s_{i}-xr_{i}\mod q$

ale v tomto systému je neznámá a to je vše , což znamená, že počet neznámých je o jednu větší než rovnic a pro všechny existují ty , které systém splňují. Protože q je velké prvočíslo, bude pro obnovu vyžadován exponenciální počet párů (zpráva, podpis). [jeden] $X$ $k_i$ $X$ $k_i$ $x\mod q$

Padělek podpisu

Můžete se pokusit zfalšovat podpis bez znalosti tajného klíče, to znamená pokusit se vyřešit rovnici

$r^{s}\mod p\mod q=g^{H(m)}y^{r}\mod p\mod q$

s ohledem na a . Pro každý pevný je rovnice ekvivalentní výpočtu diskrétního logaritmu. [jeden] $r$ $s$ $r$

Systém ověřování implementace algoritmu

Licenční podmínky vám umožňují implementovat algoritmus v softwaru a hardwaru. NIST vytvořil DSAVS [19] ( Eng. The Digital Signature Algorithm Validation System - systém pro kontrolu algoritmu digitálního podpisu ). DSAVS se skládá z několika modulů pro testování shody, které testují každou komponentu systému nezávisle na ostatních. Testované implementační komponenty:

Generování parametrů domény
Kontrola nastavení domény
Generování páru veřejného a soukromého klíče
Vytvořte podpis
Ověření podpisu

Pro otestování implementace musí vývojář odeslat žádost o testování její implementace do laboratoře CMT ( Cryptographic Module Testing Laboratory ) . [5]

Generování prvočísel

Algoritmus DSA vyžaduje dvě prvočísla ( a ), takže je potřeba generátor prvočísel nebo pseudo -prvočísel . $p$ $q$

Ke generování prvočísel se používá Shaw-Taylorův algoritmus [20] .

Pseudoprimy se generují pomocí hashovací funkce a k testování primality se používá Miller-Rabinův pravděpodobnostní test . Lze k ní přidat jediný test Lukeovy primality . [5]

Požadovaný počet iterací závisí na délce použitých čísel a na ověřovacím algoritmu [5] :

možnosti	pouze M-R test	M-R test + Luke test
p: 1024 bitů q: 160 bitů pravděpodobnost chyby $2^{-80}$	40	p: 3 q:19
p: 2048 bitů q: 224 bitů pravděpodobnost chyby $2^{-112}$	56	p: 3 q:24
p: 2048 bitů q: 256 bitů pravděpodobnost chyby $2^{-112}$	56	p: 3 q:27
p: 3072 bitů q: 256 bitů pravděpodobnost chyby $2^{-128}$	64	p: 2 q:27

Generování náhodných čísel

Algoritmus také vyžaduje generátor náhodných nebo pseudonáhodných čísel. Tento generátor je potřebný ke generování soukromého uživatelského klíče x a také ke generování tajného náhodného parametru . $k$

Norma nabízí různé způsoby generování pseudonáhodných čísel pomocí blokových šifer nebo hashovacích funkcí. [5] [21]

Poznámky

↑ 123 Patent US 5231668 A .
↑ 123 FIPS 186-1 . _
↑ FIPS 186-2 .
↑ FIPS 186-3 .
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 FIPS 186-4 .
↑ 12 FIPS 180-4 .
↑ FIPS 202 .
↑ Hledání kolizí v plném SHA-1 .
↑ Kolize volného startu pro plné SHA-1 .
↑ Zvláštní publikace NIST 800-57 .
↑ Elgamal, 1985 .
↑ C. P. Schnorr. Efektivní identifikace a podpisy pro čipové karty // Pokroky v kryptologii - CRYPTO' 89 Sborník / Gilles Brassard. — New York, NY: Springer, 1990. — S. 239–252 . - ISBN 978-0-387-34805-6 . - doi : 10.1007/0-387-34805-0_22 . Archivováno z originálu 12. dubna 2022.
↑ GOST R 34.11-2012
↑ 1 2 Algoritmus digitálního podpisu eliptické křivky (ECDSA) .
↑ Nebezpečnost algoritmu digitálního podpisu s částečně známými nonces .
↑ ECDSA – selhání aplikace a implementace .
↑ Kryptografie eliptické křivky v praxi .
↑ Bezpečnostní argumenty pro digitální podpisy a slepé podpisy .
↑ Systém ověřování digitálního podpisu .
↑ Generování silných prvočísel .
↑ Generování náhodných čísel .

Literatura

Normy a patenty

FIPS. PUB 186-1 .
FIPS. PUB 186-2 .
FIPS. PUB 186-3 .
FIPS. PUB 186-4 .
FIPS. PUB 180-4 . Archivováno z originálu 26. listopadu 2016.
FIPS. PUB 202 (anglicky) .
FIPS. PUB 202 (anglicky) .
David W. Kravitz. Algoritmus digitálního podpisu 5231668 A (anglicky) .
Speciální publikace NIST 800-57 Část 1 Revize 4. Doporučení pro správu klíčů .
GOST R 34.10-2012. Informační technologie. Kryptografická ochrana informací. Procesy tvorby a ověřování elektronického digitálního podpisu . (Ruština)
Systém ověřování algoritmu digitálního podpisu .

Články

Marc Stevens, Pierre Karpman, Thomas Peyrin. Kolize volného startu pro plné SHA- 1 .
Speciální publikace NIST 800-90A Doporučení pro generování náhodných čísel pomocí deterministických generátorů náhodných bitů .
J. Shawe-Taylor. Generování silných prvočísel .
Xiaoyun Wang, Yiqun Lisa, Hongbo Yu. Hledání kolizí v plné SHA-1 .
Phong Q. Nguyen, Igor E. Shparlinski. Nebezpečnost algoritmu digitálního podpisu s částečně známými nonces .
David Pointcheval, Jacques Stern. Bezpečnostní argumenty pro digitální podpisy a slepé podpisy .
Markus Schmid. ECDSA – Chyby aplikace a implementace .
Don Johnson, Alfred Menezes, Scott Vanstone. Algoritmus digitálního podpisu eliptické křivky (ECDSA ) .
Elgamal T. Kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech, kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1985. - Sv. 31, Iss. 4. - S. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Joppe W. Bos, J. Alex Halderman, Nadia Heninger, Jonathan Moore, Michael Naehrig, Eric Wustrow. Kryptografie eliptické křivky v praxi .

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta