╚ßst 30 - CW 41/97

Diffie-Hellmanova funkce a Üifrovacφ algoritmus RSA

Z p°edchozφ Φßsti serißlu (viz CW 36/97) u₧ Φtenß° vφ, ₧e na poΦßtku 70. let (Diffie a Hellman, Merkle) vznikly Üifrovacφ systΘmy s ve°ejn²m klφΦem, tj. systΘmy, v nich₧ otev°en² text m∙₧e b²t zaÜifrovßn ka₧dou osobou, kterß mß p°φstup k ve°ejnΘmu klφΦi, deÜifrovat jej pak m∙₧e pouze oprßvn∞n² p°φjemce (skupina p°φjemc∙), kter² vlastnφ tajn² klφΦ. ProΦ vÜak na tuto jednoduchou myÜlenku nep°iÜli kryptologovΘ dßvno p°edtφm? Odpov∞∩ na tuto otßzku je prostß -- to, ₧e Üifrovacφ systΘm s ve°ejn²m klφΦem je bezpeΦn², vypl²vß z teorie slo₧itosti, kterß, jako modernφ disciplφna zab²vajφcφ se tφm, jak dlouho budou trvat r∙znΘ v²poΦty, je relativn∞ mladß.

Formßln∞ si m∙₧eme Üifrovacφ systΘm s ve°ejn²m klφΦem popsat nßsledovn∞: vÜichni u₧ivatelΘ, kte°φ si p°ejφ spolu navzßjem komunikovat, majφ t²₧ Üifrovacφ algoritmus E a deÜifrovacφ algoritmus D. Ka₧d² u₧ivatel U_i mß dvojici klφΦ∙ (K_i,L_i) tak, ₧e pro vÜechny mo₧nΘ zprßvy M platφ identita D(E(M,K_i),L_i) = M, p°iΦem₧ klφΦ K_i je zve°ejn∞n a ulo₧en v tzv. ve°ejnΘm souboru, klφΦ L_i je utajen a naz²vßme jej tajn² klφΦ, klφΦ K_i naz²vßme ve°ejn² klφΦ. P°eje-li si u₧ivatel U_j poslat u₧ivateli U_i zprßvu M, postupuje nßsledovn∞:

-- zjistφ si ve°ejn² klφΦ K_i u₧ivatele U_i ve ve°ejnΘm souboru,

-- poÜle u₧ivateli U_i zaÜifrovan² text C = E(M,K_i).

BezpeΦnost systΘmu pak zßvisφ na funkcφch E a D, kterΘ by m∞ly mφt nßsledujφcφ vlastnosti:

-- v²poΦet zaÜifrovanΘho textu by m∞l b²t snadn²,

-- je-li zachycen pouze zaÜifrovan² text, m∞lo by b²t v reßlnΘm Φase v²poΦetn∞ neproveditelnΘ nalezenφ p∙vodnφho otev°enΘho textu, tj. nem∞l by neexistovat deÜifrovacφ algoritmus pracujφcφ v polynomißlnφm Φase,

-- je-li znßm zaÜifrovan² text a tajn² klφΦ, m∞lo by b²t v²poΦetn∞ snadnΘ urΦenφ p∙vodnφho otev°enΘho textu.

èifrovacφm funkcφm, kterΘ majφ prvnφ dv∞ vlastnosti, se °φkß jednosm∞rnΘ funkce, je-li navφc spln∞na t°etφ podmφnka, mluvφme o funkci s vlastnostφ zadnφch vrßtek. Aby byl takov² systΘm praktick², budeme po₧adovat i snadnΘ vygenerovßnφ "nßhodnΘ" dvojice ve°ejn²ch a tajn²ch klφΦ∙. V podstat∞ se jednß o po₧adavek mφt k dispozici dostateΦn∞ mnoho takov²chto dvojic, aby systΘm nebyl napadnuteln² tφm, ₧e si nep°φtel vygeneruje vÜechny takovΘ dvojice a postupn∞ je prochßzφ.

Poznamenejme, ₧e tradiΦnφ teorie slo₧itosti nenφ zrovna ideßlnφ z hlediska kryptografie -- zab²vß se toti₧ tφm nejhorÜφm mo₧n²m p°φpadem. Kryptografa zajφmß spφÜe pr∙m∞rnß slo₧itost zkoumanΘho problΘmu. Z hlediska teorie slo₧itosti jsou dobr²mi kandidßty jednosm∞rnΘ funkce, vedoucφ k NP-·pln²m problΘm∙m.

Jednφm z takov²ch problΘm∙ je problΘm ruksaku (knapsack problem). Bohu₧el, Shamir v roce 1982 ukßzal, ₧e tΘm∞° pro vÜechny mo₧nΘ p°φpady je tento problΘm °eÜiteln² v polynomißlnφm Φase a podobn∞ o rok pozd∞ji Adleman totΘ₧ ov∞°il pro iterovanou verzi tohoto systΘmu.

V roce 1977 pßnovΘ Rivest, Shamir a Adleman oznßmili objev prvnφho konkrΘtnφho Üifrovacφho systΘmu s ve°ejn²m klφΦem, kter² se nynφ naz²vß RSA. Tento systΘm je zalo₧en na p°ekvapiv∞ jednoduchΘ Φφseln∞-teoretickΘ ·vaze -- aΦkoliv je snadnΘ vynßsobit dv∞ velkß prvoΦφsla (°ßdov∞ 100mφstnß), je bez jejich znalosti opravdu extrΘmn∞ obtφ₧nΘ zp∞tn∞ provΘst rozklad tohoto souΦinu na prvoΦφsla. Blφ₧e o rozkladu p°irozen²ch Φφsel na prvoΦφsla pojednßval Φlßnek Modulßrnφ aritmetika a Üifrovßnφ (viz CW 37/97). Jejich souΦin m∙₧eme tedy publikovat a pou₧φt jako ve°ejn² klφΦ pro zaÜifrovßnφ zprßvy. P°itom tato dv∞ prvoΦφsla jsou pot°ebnß pro jejφ deÜifrovßnφ.

Zßrove≥ je t°eba zd∙raznit, ₧e aΦkoliv doposud nebyl podßn d∙kaz (matematick²) toho, ₧e faktorizace je opravdu neproveditelnß ("pouze" za obdobφ vφce ne₧ dvou tisφc let, b∞hem nich₧ je tato problematika zkoumßna, nebyla nalezena vhodnß metoda -- pokud existuje) a ₧e je opravdu schopnost faktorizovat skuteΦn∞ pot°ebnß pro ·sp∞ÜnΘ napadnutφ RSA systΘmu, platnosti v²Üe uvedenΘho nasv∞dΦuje mnoho empirick²ch poznatk∙.

RSA pod lupou

PopiÜme nynφ blφ₧e systΘm RSA. Nech¥ p a q jsou dv∞ velkß nßhodnß prvoΦφsla. OznaΦme n = pq, f(n) = (p - 1)(q - 1), p°itom f(n) je Eulerova funkce urΦujφcφ poΦet p°irozen²ch Φφsel nesoud∞ln²ch s n. Vyberme dßle nßhodn∞ velkΘ p°irozenΘ Φφslo d > 1 tak, ₧e Φφsla d a f(n) jsou nesoud∞lnß, tj. dle Bezoutovy v∞ty existuje jednoznaΦn∞ urΦenΘ Φφslo e, 1 < d < f(n) tak, ₧e souΦin ed je kongruentnφ s 1 modulo f(n). P°itom Φφslo n naz²vßme modul, Φφslo e Üifrovacφm exponentem a Φφslo d deÜifrovacφm exponentem. Ve°ejn² klφΦ zde tvo°φ Φφsla e, n, zadnφmi vrßtky je Φtve°ice Φφsel p, q, d, f(n). P°itom znalost jednoho z Φφsel p, q, f(n) vede k bezprost°ednφmu nalezenφ zb²vajφcφch t°φ a znalost Φφsla d nßm dßvß pravd∞podobnostnφ polynomißlnφ algoritmus pro faktorizaci Φφsla n.

Specißln∞ tedy budeme p°edpoklßdat, ₧e otev°en² text je zak≤dovßn jako n∞jakΘ p°irozenΘ Φφslo, kterΘ je rozd∞leno do blok∙ vhodnΘ velikosti. Ka₧d² blok se pak Üifruje zvlßÜ¥. Vhodnß velikost bloku je Φφslo i, kterΘ spl≥uje nerovnosti 10^i-1< n < 10ⁱ. Je-li d∙le₧itß jednoznaΦnost deÜifrovßnφ, bere se n∞kdy za velikost bloku Φφslo i-1. Je-li tedy M blok otev°enΘho textu a C odpovφdajφcφ blok ÜifrovΘho textu, platφ C = M^e mod n. DeÜifrujeme pak M░ = C^d mod n. To, ₧e bude M░ = M mod n, plyne z bezprost°ednφ aplikace Eulerovy v∞ty rozliÜenφm mo₧nostφ zda p, resp. q d∞lφ M. D∙le₧itß v²hoda RSA je v tom, ₧e operace zaÜifrovßnφ i deÜifrovßnφ jsou stejnΘho typu -- mluvφme o umocn∞nφ modulo n, tj. o v²poΦtu, kdy poΦφtßme zbytek Φφsla a^r modulo n. Tuto operaci m∙₧eme provΘst mnohem rychleji, ne₧ jen opakovßnφm nßsobenφ Φφslem a za sebou. Pou₧ijeme p°itom metodu umoc≥ovßnφ Φtverc∙.

┌tok a obrana RSA

V∞nujme se nynφ krßtce ·toku a obran∞ v rßmci RSA systΘmu. P°i v²b∞ru prvoΦφsel p a q je dob°e znßmo, ₧e ob∞ prvoΦφsla by m∞la b²t volena dßle od sebe, tj. ₧e bitovΘ reprezentace by se m∞ly o n∞kolik bit∙ liÜit ve svΘ dΘlce, jinak by se ·toΦnφkovi ulehΦilo napadßnφ systΘmu -- platφ toti₧ evidentnφ rovnost (p + q)²/4 - n = (p - q)²/4. Chceme-li pak faktorizovat n, testujeme takovß Φφsla x, kterß p°evyÜujφ druhou odmocninu z n a₧ do doby, ne₧ bude x² - n = y² pro vhodnΘ Φφslo y. Pak nutn∞ p = x + y, q = x - y. Co vφme o funkci f(n)? Proto₧e jak (p - 1), (q - 1) jsou Φφsla sudß, je f(n) Φφslo d∞litelnΘ Φty°mi. Je-li navφc jejich nejv∞tÜφ spoleΦn² d∞litel co nejv∞tÜφ, je nutn∞ jejich nejmenÜφ nßsobek u co nejmenÜφ ve srovnßnφ s hodnotou funkce f(n). Mßme pak, ₧e ed = 1 mod u a je tedy v²hodn∞jÜφ najφt deÜifrovacφ exponent testovßnφm mo₧nostφ. Jsou znßmy jeÜt∞ dalÜφ mo₧nosti, kterΘ podstatn∞ usnad≥ujφ faktorizaci, resp. vlastnφ deÜifrovßnφ. Ty je pak nutno brßt p°i nßvrhu konkrΘtnφho Üifrovacφho systΘmu v ·vahu.

PodpisovΘ schΘma

Na zßv∞r krßtce popiÜme podpisovΘ schΘma, zalo₧enΘ na identifikaci u₧ivatele U_i ve ve°ejn∞ p°φstupnΘ sφti. Identifikace u₧ivatele m∙₧e b²t urΦena bu∩ jeho jmΘnem, nebo jeho e-mailovou adresou. Tento ·daj m∙₧eme reprezentovat pomocφ Φφsla i. Budeme dßle p°edpoklßdat, ₧e pro tento ·Φel existuje specißlnφ d∙v∞ryhodnß instituce, kterß ka₧dΘmu u₧ivateli U_i p°i°adφ tajnΘ Φφslo x, kterΘ bude funkcφ Φφsla i. P°esn∞ji, nech¥ jsou znßma Φφsla n, e ze systΘmu RSA a jednosm∞rnß funkce g dvou prom∞nn²ch. P°itom Φφslo d a faktorizace n je znßmo pouze tΘto instituci. Ta pak u₧ivateli U_i p°id∞lφ Φφslo x = i^d mod n. U₧ivatel pak podepφÜe zprßvu, resp. sv∙j ve°ejn² klφΦ w jako₧to dvojici Φφsel (s, t), kde platφ s^e = it^g(t,w) mod n, co₧ mohou ostatnφ u₧ivatelΘ snadno ov∞°it, proto₧e i, n, e a g jsou ve°ejn∞ znßmΘ. ╚φsla s a t si m∙₧e u₧ivatel U_i snadno vygenerovat pomocφ nßhodnΘho v²b∞ru Φφsla r a polo₧enφm t = r^e mod n, s = xr^g(t,w) mod n, p°iΦem₧ funkce g provede kryptografickΘ haÜovßnφ (zkrßcenφ) Φφsel t a w. To, ₧e pouze u₧ivatel U_i je schopen vytvo°it trojici (w,s,t), plyne z toho, ₧e pouze on a d∙v∞ryhodnß instituce znajφ Φφslo x, pomocφ kterΘho je urΦeno Φφslo s.

Celkov∞ lze o RSA °φci, ₧e se stal nejpou₧φvan∞jÜφm Üifrovacφm algoritmem s ve°ejn²m klφΦem a de facto sv∞tov²m pr∙myslov²m standardem. P°i zv∞tÜenφ poΦtu bit∙ ve°ejnΘho modulu na 1 024 bit∙ (a tφm i poΦetnφ nßroΦnosti) m∙₧eme s jistotou (pokud to v∙bec jde) tvrdit, ₧e jeÜt∞ n∞jakou dobu tφmto standardem z∙stane.