Šifrování RSA je základem bezpečné komunikace na internetu. Jedná se o typ kryptografie s veřejným klíčem, který chrání e-maily, digitální transakce a citlivá data odesílaná přes sítě. Algoritmus je pojmenován po svých tvůrcích: Ronald L. Rivest, Adi Shamir a Leonard Adleman. Vyvinuli tento systém, když pracovali jako fakulta na Massachusetts Institute of Technology.
Zabezpečení RSA spoléhá na jednoduchou matematickou překážku, kterou lze snadno vytvořit, ale je téměř nemožné ji zvrátit. Uživatel začne výběrem dvou velkých prvočísel, p a q. Tato čísla jsou tak velká, že jejich vynásobení, abychom dostali n, je triviální, ale faktorizace n zpět na p a q je výpočetně nemožná.
Představte si to takto: vynásobení dvou obrovských čísel trvá zlomek sekundy. Snažíte se zjistit, která dvě čísla byla vynásobena, abyste získali tento výsledek? S moderní technologií to může trvat miliardy let.
Od roku 2015 americké vládní bezpečnostní standardy vyžadují, aby n bylo alespoň 2048 bitů. V desítkovém tvaru to znamená, že p a q mají každé asi 308 číslic, což vytváří 617místné číslo pro n. Největší čísla, která jsme úspěšně zohlednili, jsou pouze poloviční. Složitost faktorizace se zhruba zdvojnásobuje s každým dalším třetím číslem modulu. Toto exponenciální zvýšení složitosti zajišťuje, že klíče o 617 znacích zůstanou chráněny před útoky hrubou silou po celá desetiletí.
Mechanika generování klíčů
Po výběru p a q systém vygeneruje veřejné a soukromé klíče. Uživatel vybere celé číslo e menší než n. Toto číslo musí být coprime se součinem (p – 1) a (q – 1). Jednoduše řečeno, e nemá s tímto produktem žádné společné faktory kromě 1.
Tato konkrétní volba zaručuje existenci dalšího čísla d. Když vynásobíte e d a vydělíte nejmenším společným násobkem (p – 1) a (q – 1), zbytek je 1.
Nalezení d je snadné, pokud znáte p a q. Euklidovský algoritmus to počítá v okamžicích. Ale pokud neznáte p a q, najít d z e je stejně obtížné jako faktorizovat n. Tato komplexnost je úplným základem kryptografického zabezpečení RSA.
Zabezpečení RSA není kouzlo; tohle je matematika. Zejména je to asymetrie mezi snadným násobením a nemožným faktorizací.
Veřejné klíče vs. soukromé klíče
Popisky d a e popisují spíše funkce než striktní role. Klíče jsou zaměnitelné. Tato flexibilita umožňuje RSA provádět dva různé úkoly: soukromí a ověřování.
Chcete-li vytvořit soukromý kanál, uživatel A publikuje e a n ve veřejném adresáři. Uživatel A udržuje d v tajnosti. Když chce někdo poslat soukromou zprávu A, převede zprávu na čísla menší než n a zašifruje ji pomocí e a n. Pouze A může dešifrovat, protože pouze A vlastní d. Předpokladem – a silným důkazem – je, že nikdo jiný nemůže zprávu dešifrovat bez faktoru n.
Autentizace funguje jinak. Uživatel A publikuje d a n a udržuje e v tajnosti. Uživatel B se chce ujistit, že komunikuje s A. B odešle ověřovací zprávu A. Pokud A vrátí zašifrovanou verzi pomocí e, B ji může dešifrovat pomocí prostého textu d. Pokud se dešifrovaná zpráva shoduje s testovací zprávou, B ví, že odesílatel vlastní e. Protože pouze A má e, identita je potvrzena.
Digitální podpisy a hašování
Digitální podpis přidává vrstvu složitosti. Vyžaduje kryptograficky silnou hashovací funkci. Toto je veřejná funkce, která komprimuje jakoukoli zprávu do menšího kontrolního součtu (digest). Každý kousek výtahu závisí na každém bitu původní zprávy. Změňte jeden bit v původní zprávě a přibližně polovina bitů ve výtahu se změní.
Kryptograficky silný hash znemožňuje výpočetně najít zprávu, která poskytuje konkrétní předem přiřazený kontrolní součet. Také je obtížné najít další zprávu se stejným kontrolním součtem, jako má známá.
Pro podepsání zprávy A zašifruje výtah svým tajným e a připojí ho ke zprávě. Samotná zpráva nemusí být tajná. Kdokoli může použít veřejný klíč d A k dešifrování podpisu a obnovení výtahu. Poté nezávisle vypočítají výtah přijaté zprávy. Pokud se dva výtahy shodují, podpis je platný. Pouze A mohl zašifrovat výtah, protože pouze A zná e.
Hybridní realita
Tato bezpečnost má svou cenu. Asymetrické šifrování vyžaduje podstatně více výpočtů než symetrické (jednoklíčové) šifrování. Tato vysoká spotřeba CPU dramaticky snižuje propustnost. Po dobu asi 20 let dosahovaly algoritmy s jedním klíčem 1 000 až 10 000krát vyšší propustnost než algoritmy se dvěma klíči se srovnatelnou úrovní zabezpečení.
Protože je RSA pomalé, zřídka se používá k přímému šifrování velkého množství dat. Místo toho pohání hybridní systémy. RSA zajišťuje většinu práce s ověřováním a digitálním podpisem. Také si bezpečně vyměňuje náhodně vygenerovaný klíč relace. Jakmile je tento klíč přenesen, systém se přepne na jednoklíčový algoritmus pro vysokorychlostní přenos skutečných dat. Po ukončení relace je klíč zahozen.
Tato kombinace nám dává to nejlepší z obou světů. Získáváme bezpečnou výměnu klíčů pomocí kryptografie veřejného klíče a rychlosti symetrického šifrování pro většinu našich dat.
Matematika se drží. Klíče zůstávají v bezpečí. Ale jak se zvyšuje výpočetní výkon, mění se definice „velkého“ čísla. Co je dnes nemožné hacknout, se zítra může ukázat jako řešitelný problém. Pokračujeme ve vytváření větších prvočísel. Nadále doufáme, že propast mezi snadným násobením a složitou faktorizací zůstane dostatečně široká, aby ochránila naše digitální životy.
