Úvod do kryptografie

Algoritmus šifrování RSA

Algoritmus RSA leží v základech asymetrické kryptografie. RSA – je kryptografický systém otevřeného klíče zabezpečující takové mechanizmy ochrany, jako šifrování a digitální podpis (autenticita – ověření původnosti). Kryptosystém RSA byl vytvořen v roce 1977 a byl pojmenován na počest vývojářů Ronalda Rivesta, Adi Shamira a Leonarda Adlemana.
První etapou libovolného asymetrického algoritmu je vytvoření dvojice klíčů: otevřeného a zavřeného a rozšíření otevřeného klíče "na celém světě“. Druhou etapou je vlastně sam proces šifrování.

Etapa generování klíče
Pro algoritmus RSA se etapa vytvoření klíčů sestává z následujících operací:

1)	Berou se dvě prostá čísla (!)čísla p a q, náhodně a nezávislá na každém jiný. (ve skutečnosti čísla p a q jsou velmi velké. Požadovaná délka bitů je 1024)
2)	Vypočítává se jejich násobek *n (=pq)**
3)	Vypočítává se *(p-1)(q-1)**
4)	Vybírá se libovolné prosté číslo d (d<n), takové, že *NSD (d,(p-1)(q-1))=1, tj. d musí být vzájemně prostým s číslem (p-1)(q-1).*
5)	Určíme takové číslo e, pro které platí následující vztah: *(ed)mod((p-1)(q-1))=1* To se řeší Euklidovou metodou.
6)	Dvojice e a n tvoří otevřený klíč (veřejný).

Etapa šifrování

Čistý text (pouze malá písmena bez diakritiky)	Cifra	Odesílatel rozbíjí svou zprávu na bloky, přičemž každý může být představen ve tvaru čísla M(i)=0,1,2…, n-1 (tj. jen do n-1). Přídělíme pismenám svoje číslo od 0 do n-1 a dostaneme: A B C D E F G H I J K L M N O P … 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 … Pro každé takové číslo M(i) se vypočítává výraz C(i) = (M(i)^e) mod n Bloky C(i) jsou zašifrované zprávy. Je možné je klidně předávat otevřeným kanálem, protože operace umocnění podle modulu prostého čísla je nevratná matematická úloha. Její zpětná úloha se nazývá "logaritmování v konečném poli" a je to o několik řádů složitější úloha. Což znamená, jestliže útočník zná čísla e a n, tak podle C(i) nijak nepřečte původní zprávu M(i) kromě než úplným přebráním M(i).



Proces dešifrování
Cifra	Čistý text	Dešifrování provedeme pomoci zavřeného klíče a je nutno provést následující vypočítání: M(i) = (C(i)^d) mod n Ve skutečnosti jsou operace umocnění velkých čísel dostatečně obtížné pro moderní procesory i v případě, že jsou uskutečňovány podle časově optimalizovaných algoritmů. Proto se obvykle celý text zprávy kóduje obyčejnou blokovou šifrou (mnohem rychlejší), ale s použitím klíče průběhu a sám klíč průběhu se šifruje jako asymetrický algoritmus s pomocí otevřeného klíče příjemce a umisťuje se na začátek fajlu.

Rychlost práce algoritmu RSA.
Rychlost činnosti realizace RSA je přibližně 1000 krát nižší než rychlost činnosti přístrojové realizace DES. Rychlost činnosti VLSI (Very Large Scale Integration) - realizace RSA s 512-bitovým modulem – 64 Kb/s. Programová realizace DES je asi 100 krát rychlejší než programová realizace RSA. Tato hodnocení se mohou nepatrně měnit v závislosti na použité technologii, ale RSA nikdy nedosáhne produktivity symetrických algoritmů.

Krypto odolnost RSA
RSA mnohá léta odolává intenzivní kryptoanalýze. Kryptoodolnost RSA je založena na obtížnosti rozložení na násobky (faktorizaci) velkých čísel. Otevřený a tajný klíč jsou funkcemi dvou velkých (100 – 200 dvojkových výbojů nebo i více) prostých čísel. Předpokládá se, že úloha obnovení otevřeného textu z šifrovaného textu a otevřenému klíči je ekvivalentní úloha faktorizace. Avšak, nikdy nebylo matematicky dokázáno, že je nutné rozložit n na násobky, aby se obnovilo m podle ? a ?. Není vyloučeno, že může být odhalen úplně nový způsob kryptoanalýzy RSA. Přičemž, jestliže nový způsob umožní kryptoanalytikovi získat d, tak může být použit pro rozložení na násobky velkých čísel. Také je možné zaútočit na RSA, odhadnuv hodnotu (p-1)(q-1). Avšak tato metoda není jednodušší než rozložení na násobky. Otevření dokonce několika bitů informací z šifrovaného textu není lehčí než dešifrování celé zprávy. Nejzřejmějším útokem na RSA se jeví rozložení na násobky. Libovolný protivník může získat otevřený klíč e a modul n. Aby mohl najít dešifrovací klíč d, musí protivník rozložit n na násobky. Kryptoanalytik může probírat všechny možné d, dokud nevybere správnou hodnotu. Ale podobný silový útok je mnohem méně účinný než pokus rozložení n na násobky.
Podotýkáme, že je nedostatečné použít kryptoodolný algoritmus; bezpečným musí být celý kryptosystém zahrnujíc i kryptografický protokol. Slabé místo kteréhokoliv z těchto tří komponentů udělá systém nebezpečným.