╚ßst 32 - CW 43/97

Algoritmy na bßzi problΘmu digitßlnφho logaritmu

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 = g^x mod p snadno spoΦitatelnß, kde₧to hodnota x je z inverznφho vztahu x = log_g 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 = g^x 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 = g^k mod p

b = M (+) y^k

a tuto dvojici hodnot poÜle p°φjemci. P°φjemce zφskß zprßvu M v otev°enΘm tvaru ze vztahu

M = a^x 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 = g^k mod p

b se vypoΦte tak, aby platil vztah M = (x.a + k.b) mod p.

Verifikace probφhß podle vztahu y^aa^b mod p = g^M 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 = g^x 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 = (g^k 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 = ((g^u1 . y^u2) 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 = g^x mod p = 2⁸ 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:
3⁶ 6³ mod 11 = 2⁵ 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 = 3⁷⁸ mod 7879 = 170
Tajn² klφΦ: x = 75
Ve°ejn² klφΦ: y = 170⁷⁵ mod 7879 = 4567
Podpis: k = 50 k^-1 mod 101 = 99 H(M) = 1234
r = 170⁵⁰ 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 = ((170⁴⁵ . 4567²⁷) mod 7879) mod 101 = 94
Proto₧e v = r, podpis je platn².

P°φklad 2: Digitßlnφ podpis zprßvy -- algoritmus DSA