Klíčová slova

RSA

Roku 1977 přišli Ron Rivest obr. 1, Adi Shamir obr. 2 a Joe Adleman obr. 3 s implementací D-H protokolu pro svůj algoritmus. Asymetrická šifra RSA byla první tohoto typu. Zkratka RSA je tvořena počátečními písmeny příjmení autorů. Celý systém je založen na jednoduché myšlence.

Obr. 1 Ron Rivest

Obr. 2  Adi Shamir

Obr. 3  Leonard Adleman

Je snadné vynásobit dvě dlouhá prvočísla, ale bez jejich znalosti je prakticky nemožné zpětně provést rozklad výsledku na původní prvočísla.

Princip

Pro pochopení algoritmu slouží schéma, představující obecný algoritmus       obr. 4. Schéma ukazuje jak šifrování, tak dešifrování.

Obr. 4 Obecné schéma algoritmu RSA

Princip

Pro pochopení algoritmu slouží schéma, představující obecný algoritmus. Schéma ukazuje jak šifrování, tak dešifrování.Princip:

• Zvolíme dvě různá velká náhodná prvočísla p a q (my volíme prvočísla, která umíme relativně rychle spočítat a jsou v řádu desítek či stovek, v praxi se používají 100 i více ciferná čísla).
• spočítáme jejich součin m = p × q (dokážete si představit dvě 100ciferná čísla, která máte spolu vynásobit?).
• najdeme dvě čísla i a j tak, aby platilo (i × j) mod [(p − 1) × (q − 1)] = 1.

Pro šifrování čísla x potom volíme veřejný klíč složený z (m;i), který použijeme ve vzorečku y = xⁱ mod m. Pro dešifrování čísla y volíme soukromý klíč složený z (m;j), který použijeme ve vzorečku x = y^j mod m.

Příklad: Šifrujte pomocí algoritmu RSA zprávu. Zadané máme x = 3. Na obrázku 5 vidíme opět šifrování i dešifrování. (Pro šifrování známe tedy x = 3, pro dešifrování musíte znát y = 12)

Kryptoanalýza

Fakt, že není znám algoritmus, jenž dokáže vytvořit k veřejnému klíči klíč soukromý, tvoří základ každého asymetrického kryptosystému. Není ani dokázáno, že je nutné prolomit šifru pomocí modulární matematiky - čili hledáním prvočísel. Je možné, že existuje algoritmus, který rozluští zašifrovaný text jinak, než pomocí znalosti čísel. Dostupnými prostředky ale zatím není možné RSA prolomit. Teoreticky, pokud by se někomu podařilo najít čísla p a q, poté je na základě matematických znalostí možné, že přijde i na čísla i a j, která představují exponenty, a dopočítá se správného výsledku - klíče.Dnešní dostupná počítačová technika umožňuje rozložit číslo, které bude mít kolem 100 cifer. Poslední informace pocházející z RSA Challenge z roku 2003 říká, že nejmenší číslo vložené do algoritmu mělo 174 cifer.[1] Sami si můžete vyzkoušet dvě cvičení. V prvním jsou prvočísla malá a dopočítáte se velmi rychle, u druhého jsou volena čísla větší. A představte si, jak by vypadalo počítání s řádově 100- cifernými čísly. V praxi se totiž nepoužívají čísla jako 3, 7, 87, 141, ale několikaset násobná. Proto je i pro výpočetní techniku složité rozložit tolika místné číslo. Na obrázku můžete vidět rozklad 174- místného čísla, které bylo v již zmiňované soutěži RSA Challenge obr. 6.

Obr. 6  RSA-Challenge 2003

Použití

Systém RSA je hojně využíván při digitálním podpisu. Představte si, že chcete podepsat svá data a vyslat je do světa tak, aby každý věděl, že autorem jste vy.Napadlo by vás, jak toto realizovat?

• použijeme digitální podpis

RSA je také užíváno jako součást PGP. Nyní jsou připravena cvičení sloužící k upevnění jednotlivých funkcí, které algoritmus RSA používá.

Shrnutí

Představili jsme si jednoho z dalších představitelů asymetrického šifrování, kterým je algoritmus RSA. Používali jsme prvočísla, která by v praxi ani omylem neuspěla, ovšem pro vysvětlení principu šifrování a dešifrování, jsou dostačující.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.