COMPUTERWORLD
Specializovaný týdeník o výpočetní technice

Seriál
o bezpečnosti
a informačním soukromí

Část 30 - CW 41/97

Diffie-Hellmanova funkce a šifrovací algoritmus RSA

Jan Paseka

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 Ui má dvojici klíčů (Ki,Li) tak, že pro všechny možné zprávy M platí identita D(E(M,Ki),Li) = M, přičemž klíč Ki je zveřejněn a uložen v tzv. veřejném souboru, klíč Li je utajen a nazýváme jej tajný klíč, klíč Ki nazýváme veřejný klíč. Přeje-li si uživatel Uj poslat uživateli Ui zprávu M, postupuje následovně:

-- zjistí si veřejný klíč Ki uživatele Ui ve veřejném souboru,

-- pošle uživateli Ui zašifrovaný text C = E(M,Ki).

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 10i-1< n < 10i. 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 = Me mod n. Dešifrujeme pak M° = Cd 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 ar 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)2/4 - n = (p - q)2/4. Chceme-li pak faktorizovat n, testujeme taková čísla x, která převyšují druhou odmocninu z n až do doby, než bude x2 - n = y2 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 Ui 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 Ui 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 Ui přidělí číslo x = id mod n. Uživatel pak podepíše zprávu, resp. svůj veřejný klíč w jakožto dvojici čísel (s, t), kde platí se = itg(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 Ui snadno vygenerovat pomocí náhodného výběru čísla r a položením t = re mod n, s = xrg(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 Ui 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.


Seriál je rovněž dostupný na www.idg.cz/computerworld/bvsk/


| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage |