COMPUTERWORLD
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 logaritmu

Jaroslav 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

a tuto dvojici hodnot pošle příjemci. Příjemce získá zprávu M v otevřeném tvaru ze vztahu

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
u1 = (H(M) . w) mod q
u2 = (r . w) mod q
v = ((gu1 . yu2) mod p) mod 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 = 11
g = 2
Tajný klíč:
x = 8 (<11)
Veřejný klíč:
y = gx mod p = 28 mod 11 = 3
Podpis:
M = 5, k = 9, NSD(k,p-1) = (9,10) = 1
M = x . a + k . b (mod p-1)
5 = 8 . 6 + 9 . b (mod 10)
Z Euklidova algoritmu plyne, že b = 3
Podpisem je tedy pár (6,3)
Verifikace:
36 63 mod 11 = 25 mod 11

Příklad 1: Digitální podpis zprávy - algoritmus ElGamal




Parametry protokolu:
q = 101
p = 78q + 1 = 7879
h zvolíme rovno 3
g = 378 mod 7879 = 170
Tajný klíč: x = 75
Veřejný klíč: y = 17075 mod 7879 = 4567
Podpis: k = 50 k-1 mod 101 = 99 H(M) = 1234
r = 17050 mod 7879 ) mod 101) = 94
s = (99(1234 + 75 . 94) mod 101 = 97
Podpisem je tedy pár (94,97)

Verifikace zprávy:
w = 97-1 mod 101
u1 = (1234 . 25) mod 101 = 45
u2 = (94 . 25) mod 101 = 27
v = ((17045 . 456727) mod 7879) mod 101 = 94
Protože v = r, podpis je platný.

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 |