Algoritmus RSA
Jak bylo již řečeno v minulých částech, RSA je kryptosystém založený na principech veřejných klíčů. Pojmenován byl podle počátečních písmen svých tvůrců: Rivesta, Shamira a Adlemana. Dnes si nejprve teoreticky a poté i na příkladu ukážeme, jak algoritmus RSA funguje.
Nejprve se vytvoří modul n jako součin dvou velkých prvočísel p a q (n = p*q). Vybere se číslo e tak, aby bylo menší než n a jako relativní prvočíslo k*(p-1)*(q-1) , což znamená, že e a (p-1)*(q-1) nemají společného součinitele kromě jedničky. Poté se najde další číslo d takové, že (e*d-1) je dělitelné (p-1)*(q-1) . Hodnoty e a d se nazývají veřejné a privátní exponenty. Veřejný klíč je tvořen dvojicí (n,e). Privátní klíč pak tvoří dvojice (n,d). Činitelé p a q se mohou uchovávat u privátního klíče, nebo se mohou zničit.
Bezpečnost algoritmu RSA je založena na předpokladu, že je (velmi) obtížné získat z veřejného klíče (n,e) privátní klíč d. Pokud by se mohlo n rozložit na součinitele p a q , mohli bychom získat privátní klíč d. Ochrana před dešifrováním zpráv spočívá v dostatečné délce klíče (používá se např. 128, 512 nebo nejčastěji 1024bitů), hardwarových metodách výpočtu a hlavně v bezpečném softwaru a prostředí pro uložení privátního klíče.
Komu by předchozí výklad zdál příliš složitý, věřte, že na následujícím příkladu princip šifrování algoritmem RSA, snadno pochopíte. Mějme prvočísla p a q a k nim čísla i a j taková, aby platilo, že i*j - 1 je beze zbytku dělitelné (p - 1)*(q - 1). Na tomto místě je nutné ještě poznamenat, že ne pro každou dvojici p, q lze najít i, j taková, aby byla uvedená podmínka splněna. Šifrovací funkce pak bude mít tvar y = E(x) = x^i mod (p*q) a dešifrovací funkce tvar x = D(y) = y^j mod (p*q), kde x je znak zdrojových dat, y znak šifrovaných dat, znak ^ zastupuje mocninu a mod je zbytek po celočíselném dělení. Algoritmus RSA bezpečně funguje pro všechny znaky v rozmezí 0 až p*q - 1. Se zvětšujícími se hodnotami p, q a v závislosti na nich i hodnotami i, j se zvyšuje odolnost tohoto kryptosystému vůči napadení.
Předpokládejme, že odesilatel chce poslat zprávu m příjemci. Odesilatel vytvoří zašifrovaný tect c jako exponenciální funkci: c=me mod n, kde e a n tvoří příjemcův veřejný klíč. Odesilatel pošle poté zprávu c příjemci. Příjemce zprávu dešifruje jako exponenciální funkci m=cd mod n. Matematický vztah mezi e a d zaručuje, že příjemce správně přečte zprávu m. Vzhledem k tomu, že pouze příjemce zná d, může zprávu přečíst jen on.
Ověření RSA: Předpokládejme, že odesilatel chce zaslat příjemci zprávu m tak, aby si byl příjemce jist, že jde o původní zprávu a že je výhradně od odesilatele. Odesilatel vytvoří digitální podpis s jako exponenciální funkci s=md mod n, kde d a n tvoří jeho privátní klíč. Odešle příjemci m a s. K ověření podpisu příjemce vytvoří exponenciální funkci a ověří, že získal zprávu m: m=se mod n, kde e a n tvoří veřejný klíč odesilatele.
Je patrné, že zašifrování a ověření se provádějí bez sdílení privátních klíčů: každý používá veřejné klíče jiné osoby a svůj vlastní privátní klíč. Kdokoli může odeslat zašifrovanou zprávu nebo ověřit podepsanou zprávu použitím pouze veřejných klíčů, ale jen vlastník správného privátního klíče může dešifrovat nebo podepsat zprávu.
Doufám, že se vám z toho všeho šifrování nezatočila hlava, a že v příštím díle, který bude o vydávání a správě klíčů a navíc ještě o certifikačních autoritách, opět setkáme. Přejeme vám hezký den.
