![]() Specializovaný týdeník o výpočetní technice |
|
![]() |
Seriál o bezpečnosti a informačním soukromí |
Část 32 - CW 43/97
Algoritmy na bázi problému digitálního logaritmuJaroslav Dočkal
V našem seriálu jsme se setkali již se dvěma typy jednocestných funkcí -- s faktorizací přirozeného čísla (rozkladem čísla na součin prvočísel, viz algoritmus RSA) a s aritmetickými operacemi nad eliptickými křivkami. Třetí významná skupina algoritmů tohoto typu je založena na obtížnosti řešení problému diskrétního algoritmu. Obecně je problém diskrétního logaritmu objasněn ve 27. dílu seriálu. Stručně zopakováno: Jsou-li dány dva parametry -- prvočíslo p a přirozené číslo g nesoudělné s p, pak hodnota y je ze vztahu y = gx mod p snadno spočitatelná, kdežto hodnota x je z inverzního vztahu x = logg y spočitatelná velmi obtížně. Diskrétní logaritmus je tedy tou těžko řešitelnou stranou jednocestné funkce. S výhodou se této vlastnosti využívá u algoritmů s veřejným klíčem, z nichž nejznámější je ElGamalův algoritmus.
ElGamalův algoritmus Jedna verze algoritmu slouží pro potřeby šifrování, druhá pro tvorbu digitálního podpisu. Šifrování probíhá tak, že si předpokládaný příjemce zprávy zvolí privátní (tajný) klíč x a vygeneruje pomocí vztahu y = gx mod p veřejný klíč y, který pošle předpokládanému odesilateli zprávy. Ten si zvolí náhodné číslo k < p a s využitím zprávy M vypočte dvojici hodnot (a,b): a = gk mod p
b = M (+) yk
M = ax mod p (+) b Předání veřejného klíče odesilateli zprávy proběhne u digitálního podepisování naprosto stejně jako u šifrování. Pak jsou dvě složky podpisu vypočteny následujícím způsobem: a = gk mod p b se vypočte tak, aby platil vztah M = (x.a + k.b) mod p. Verifikace probíhá podle vztahu yaab mod p = gM mod p. Použití algoritmu demonstruje příklad 1.
Další algoritmy Na bázi problému diskrétního algoritmu již byla navržena celá řada algoritmů. Zvláště podnětný algoritmus navrhl Schnorr, který přišel s nápadem předzpracovat si některé výpočty a tak zkrátit proces podepisování. Další výhodou jeho algoritmu byl kratší podpis -- a to jak vůči schématu ElGamala, tak vůči RSA. To byl důvod, proč spolu s algoritmem ElGamala byl Schnorrův algoritmus použit jako zdroj pro návrh amerického standardu DSA (Digital Signature Algorithm).
Algoritmus DSA Postup při podepisování pomocí DSA je následující: Je zvoleno 160bitové prvočíslo q a vypočteno prvočíslo p o 512, resp. 1 024 bitech tak, aby platilo p = i . q + 1, kde i je přirozené číslo. Zvolí se hodnota h a vypočte hodnota g ze vztahu g = h(p-1)/q mod p. Tajný klíč musí být podobně jako q 160bitový, ale přitom menší než q. Výpočet veřejného klíče příjemce probíhá opět podle vzorce y = gx mod p. Podpis je opět dvousložkový, zde (r,s), a pracuje se zase s náhodným číslem k < q. Složky podpisu se počítají podle vzorců r = (gk mod p) mod q s = (k-1(H(M) + x . r)) mod q H(M) zde označuje zhašovanou (zkomprimovanou) zprávu, neboli zásadně se nepodepisuje samotná zpráva; podepisování se tím značně urychlí. Verifikace probíhá složitějším způsobem. Příjemce zprávy počítá
w = s-1mod q Pokud platí v = r, pak je podpis verifikovaný. Použití algoritmu demonstruje příklad 2 (oba příklady jsou převzaty z knihy Schneier D. R.: Applied Cryptography. John Wiley & Sons, 1993 a 1995, označované za bibli kryptografů). DSA byl předložen americkým NIST (National Institute of Standards and Technology), ale jak se později ukázalo, jeho vytvoření bylo plně v rukou vládní agentury NSA (National Security Agency). Tuto agenturu založil v roce 1952 Harry Truman a upřímně řečeno, tato její role je zdrojem různých pochybovačných názorů. Obchodní kruhy tuto instituci označují za pozůstatek studené války a vyčítají jí přílišné omezování exportu kryptografických zařízení. Odborná kryptografická veřejnost ji zase podezírá, že umisťuje do svých produktů "zadní vrátka". Možná jsou to jenom paranoidní představy, kdo ví. V každém případě byl algoritmus DSA navržen pouze pro podepisování. Smysl zavádět nový standard má tehdy, je-li v něčem lepší. Podepisování je u DSA ve srovnání s RSA velice rychlé, navíc tuto rychlost lze zvýšit některými opatřeními během předzpracování (lze si například všimnout, že hodnota r není závislá na zprávě a proto je možno vytvořit sadu náhodných hodnot k a předvypočítat si k-1 a r). Naopak verifikace je ve srovnání s RSA pomalejší (10--40krát). A která úspora je významnější, je předmětem sporů dodnes. V souvislosti s DSA se také často uvádějí výhrady etické povahy. Je zde snaha o standardizaci algoritmu, který čerpá z jiných algoritmů, z nichž jeden je dokonce patentován až do roku 2008 (Schnorr). A zase jsme u etických problémů, tak často diskutovaných v tomto seriálu.
Parametry protokolu: Příklad 2: Digitální podpis zprávy -- algoritmus DSA Seriál je rovněž dostupný na www.idg.cz/computerworld/bvsk/
| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage | |