![]() Specializovaný týdeník o výpočetní technice |
|
![]() |
Seriál o bezpečnosti a informačním soukromí |
Část 27 - CW 37/97
Modulární aritmetika a šifrováníJan Paseka
Máme-li zašifrovat nebo pouze zakódovat nějakou zprávu, je tato zpráva většinou v nějakém přirozeném jazyku (angličtina, čeština, němčina atd.). Pro jednoduchost uvažujme dále zprávu psanou v angličtině, takže máme k dispozici právě 26 písmen (nerozlišujeme velká či malá písmena, resp. interpunkci). Zakódování zprávy lze pak přirozeným způsobem provést následovně: A B C D E F...V W X Y Z 00 01 02 03 04 05...21 22 23 24 25. V čem se pak zakódovaný text 19042319 liší od zdrojového textu TEXT? Jednoduše v tom, že na celých číslech 0, 1, -1, 2, -2 atd. lze násobit a sčítat (odčítat) a tyto matematické operace lze přirozeným způsobem přenést na množinu {0, ..., 25}. Přitom "součet", resp. "součin" dvou čísel z této množiny musí být opět číslo z této množiny, tj. to jediné možné číslo, které se od obvyklého součtu, resp. součinu celých čísel liší o nějaký celočíselný násobek počtu prvků této množiny, tj. o číslo 26. Říkáme pak, že sčítáme, resp. násobíme modulo m, kde m = 26. Přitom číslo přirozené m nazýváme modulem. Pro počítání s celými čísly máme celou řadu výpočetně rychlých algoritmů (např. Euklidův algoritmus pro výpočet největšího společného dělitele, resp. jeho binární verzi, ve které se nepoužívá dlouhé dělení, ale jen odčítání a dělení dvěma, tj. realizované posunem). Zásadním pojmem z elementární teorie čísel je pojem kongruence -- říkáme, že dvě celá čísla x a y jsou kongruentní modulo m (píšeme x=y mod m), pokud se x a y liší o nějaký celočíselný násobek modulu m. Označme f(m) počet přirozených čísel nesoudělných s m, tj. je-li například m prvočíslo, přirozená čísla nesoudělná s m jsou po řadě 1, 2, 3,..., m-1, pak f(m) = m-1. Funkce f(m) se nazývá Eulerova funkce. Pierre de Fermat (1601-1695) dokázal, že pro prvočíslo p a přirozené číslo a nesoudělné s p platí následující: ap-1=1 mod p tj. (p-1)-ní mocnina čísla a je tvaru 1+kp pro vhodné celé číslo k. Toto tvrzení zobecnil Leonard Euler (1707--1783) tak, že pro přirozené číslo m a přirozené číslo a nesoudělné s m platí následující: af(x)=1 mod m. Přitom prvočísla můžeme charakterizovat pomocí Wilsonovy věty jakožto přirozená čísla m větší než 1 taková, že (m-1)! je kongruentní s (m-1) modulo m. Pokud navíc číslo a z Eulerovy věty splňuje podmínku, že ax není kongruentní s jedničkou modulo m pro přirozená čísla x=1,2,...,f(m)-1, nazveme a primitivním kořenem modulo m. Můžeme pak definovat diskrétní logaritmus. Uvažme tedy to přirozené číslo m, které má primitivní kořen a. Pro všechna x=1,2,...,f(m)-1 tak, že máme y=ax mod m, nazveme x diskrétním logaritmem z čísla y při základu a modulo m. Píšeme pak x=logay mod m. Předpoklad toho, že a je primitivní kořen, je nutný a zajistí nám, že pro každé takové y existuje právě jedno x, x=1,2,...,f(m)-1 a tedy je diskrétní logaritmus dobře definován. Přitom se dá ověřit, že exponenciální funkce ax modulo m se snadno spočítá, ale obrácený postup -- diskrétní logaritmování je obtížný a srovnatelný s faktorizací přirozeného čísla, tj. rozkladem na součin prvočísel. Takové funkce se nazývají jednosměrné a s úspěchem se využívají v kryptografii. Přistupme nyní k rozkladu přirozeného čísla na prvočinitele. Jedná se v podstatě o tři úkoly: -- Je-li dáno přirozené číslo n, máme rychle rozhodnout, zda n splňuje nějakou podmínku, která je splněna každým prvočíslem a tedy rozhodnout, zda je to určitě číslo složené, nebo zda je to asi prvočíslo (tzv. test na složenost); -- Víme-li, že n je asi prvočíslo, musíme dokázat, že n je skutečně prvočíslem, nebo to vyvrátit (tzv. test na prvočíselnost); -- Víme-li, že n je složené, je třeba nalézt netriviálního dělitele d čísla n. Uvedené kroky můžeme opakovat pro čísla n a n/d. Popišme nyní některé základní metody nalezení rozkladu. Nejznámější je tzv. Eratosthenovo síto (přibližně 200 let př. n. l.), kde zkoušíme dělit n postupně všemi prvočísly 2, 3, 5... až do jisté hranice -- pokud je touto hranicí druhá odmocnina z n, provedeme všechny tři úkoly současně. V případě, že n je příliš velké, bývá výhodné dělit prvočísly až do vhodné hranice, abychom se zbavili malých faktorů. Věnujme se nyní testům na složenost. Zdánlivě dobrou podmínkou se zdá být Wilsonova věta, ale problém je, jak spočítat pro velká n dostatečně rychle číslo (n-1)! mod n. Výhodnější je proto použít Fermatovu větu, protože umocňování lze provádět modulo n opravdu rychle. Máme tedy zjistit, zda je n číslo složené. Pokud nalezneme přirozené číslo a, a<n, pro které není an-1 kongruentní s 1 modulo n, víme okamžitě, že n je číslo složené. Číslo a se pak nazývá svědek složenosti čísla n. Pokud je však an-1 kongruentní s 1, nemůžeme z toho usoudit nic a musíme zkoušet dále. Po jistém počtu pokusů, kdy nenajdeme svědka složenosti, pak postup ukončíme a s jistou pravděpodobností usoudíme, že n je prvočíslo. Složená čísla, pro která platí, že an-1 je kongruentní s 1, se nazývají Carmichaelova čísla (je jich nekonečně mnoho) a nelze je výše uvedeným postupem odhalit. Proto se používají jistá zesílení Fermatovy věty (např. tzv. Miller-Rabinův test, který má kubickou časovou náročnost na výpočet a pravděpodobnost, že nám objeví každé složené číslo, je vysoká). Věnujme se nyní testům na prvočíselnost. Vstupem je číslo n, o kterém s velkou pravděpodobností platí, že je to prvočíslo. To je však třeba dokázat. Lze to provést např. n-1 testem Poclingtona a Lehmera, testem Goldwassera a Kiliana pomocí eliptických křivek, Atkinovou metodou, resp. metodou Jacobiho sum, přičemž výpočetní složitost posledně jmenované metody se blíží složitosti polynomiální. Hledání netriviálního dělitele lze provést samozřejmě metodou pokusného dělení. Z metod používaných v praxi jmenujme Lehmannovu metodu, Pollardovu rho-metodu, Pollardovu (p-1) metodu, Lenstrovu metodu eliptických křivek, metodu kvadratického síta a metodu síta v číselném tělese. Metoda síta v číselném tělese je potenciálně nejrychlejší známá metoda rozkládání velkých přirozených čísel. Bohužel, výpočty při použití této metody jsou opravdu velmi komplikované (je zde potřeba zkonstruovat a popsat nejmenší těleso algebraických čísel obsahující jisté předem zvolené algebraické číslo a pak provést jisté prosívání možných výsledků). Tedy tato výhodnost se začne projevovat až pro dosti velká čísla (o alespoň 130 dekadických cifrách). Ale pro čísla ve speciálním tvaru (Mersenneova, Fermatova čísla) může být náročnost metody zjednodušena a stává se použitelnou i pro 120ciferná čísla. Poprvé byla tato metoda s úspěchem použita v roce 1990 při rozkladu devátého Fermatova čísla n=2512+1, které má 155 cifer, na prvočinitele. Za pomoci mnoha dobrovolníků prostřednictvím elektronické pošty byl vynaložen ekvivalent několika let procesorového času na jednom počítači. Získaná data pak byla zpracována Gaussovou eliminací řídké matice nad dvojprvkovým tělesem. Hledáme totiž lineární závislosti mezi řádky velmi velké matice, která má však v každém řádku jen několik jedniček a zbytek řádku tvoří nuly. Z této matice sestavíme mnohem menší matici, v níž se provede Gaussova eliminace obvyklým způsobem. Tvůrci algoritmu RSA, spočívajícího na předpokladu, že je výpočetně prakticky nezvládnutelné faktorizovat dostatečně velké přirozené číslo, vsadili 100 dolarů na to, že nikdo nerozluští jejich anglický text zašifrovaný pomocí RSA s veřejným exponentem e =9007 a modulem o 129 cifrách. V dubnu 1994 pak bylo oznámeno, že se podařilo metodou kvadratického síta roznásobit 129ciferné číslo RSA-129, a tak odhalit výše uvedený text, přičemž tato činnost měla podle odhadu profesora Rivesta trvat více než 40 000 000 000 000 000 let. O dva roky později, v dubnu 1996 byl proveden rozklad 130ciferného čísla RSA-130 metodou síta v číselném tělese. Zbývá tak opravdu jen relativně velmi málo, aby byl proveden úspěšný útok na standardní modul RSA o 512 bitech. Vidíme, že na první pohled triviální problém rozkladu využívá netriviálních výsledků teorie čísel a je pro velká přirozená n stále velmi náročný. Je tedy vhodný (při vhodné volbě čísla n) pro použití při šifrování (algoritmus RSA s větším modulem, například 1 024 nebo 2 048 bitů apod.).
Seriál je rovněž dostupný na www.idg.cz/computerworld/bvsk/
| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage | |