Šifrování RSA: krok 4

Nyní máme zadní dvířka pro řešení Fí. Pokud známe rozklad pro 'N', pak najít Fí(N) je snadné. Například, rozklad prvočísla 77 je (7 krát 11). Takže Fí(77) je (6 krát 10). ... 60. Krok 3: Jak spojit funkci Fí s modulárním umocňováním? Odpovědí je Eulerova věta, což je vztah mezi funkcí Fí a modulárním umocňováním: 'm' umocněné na Fí(n) je kongruentní s (1 mod n). To znamená, že můžeme vybrat jakékoliv dvě čísla, která nemají společného dělitele. Budeme je nazývat 'm' a 'n'. Řekněme, že 'm' je rovno 5 a 'n' je rovno 8. Když umocníme 'm' na Fí(n) (což jsou 4), a vydělíme 'n', tak vždy vyjde 1. Musíme pouze změnit tuto rovnici použitím dvou jednoduchých pravidel. 1. Pokud umocníš číslo 1 jakýmkoliv exponentem 'k', tak vždy dostaneš 1. Stejně tak můžeme vynásobit exponent Fí(N) jakýmkoliv číslem 'k' a řešení je stále 1. 2. Pokud vynásobíš 1 jakýmkoliv číslem, řekněme 'm', tak se to vždy rovná 'm'. Stejně tak můžeme vynásobit levou stranu 'm', abychom dostali 'm' na pravé straně, a toto může být zjednodušeno jako 'm' umocněné na (k krát Fí(n) plus 1). Toto je průlomové. Nyní máme rovnici pro nalezení (e krát d), které závisí na Fí(n). Proto je jednoduché vypočítat 'd' pouze, pokud je známý rozklad 'n'. Což znamená, že 'd' by měl být soukromý klíč Alice. Jsou to zadní dvířka, která jí umožní zrušit vliv 'e'. Pojďme si ukázat jednoduchý příklad toho všeho v akci. Řekněme, že Bob má zprávu, kterou přeměnil na číslo 'm'. Poté Alice vygeneruje její veřejný a soukromý klíč následovně: Za prvé vygeneruje dvě náhodné prvočísla podobné velikosti a vynásobí je, a dostane 'n', 3127. Pak Fí(n) vypočítá jednoduše, jelikož zná rozklad 'n', což je 3016. Pak vybere nějaký malý veřejný exponent 'e', pod podmínkou, že musí být liché číslo, které nemá společného dělitele s Fí(n). V tomto případě vybere 'e' rovno 3. Nakonec najde hodnotu jejího soukromého exponentu 'd', což je v tomto případě (2 krát Fí(n) plus 1) děleno 3, nebo 2011. Vše schová, kromě hodnot 'n' a 'e', protože 'n' a 'e' tvoří její veřejný klíč. Je to jako otevřený zámek. Pošle to Bobovi, aby si tím zamkl jeho zprávu. Bob si zamkne jeho zprávu tím, že vypočítá m na (e mod n), nazvěme to 'c', jeho šifrovaná zpráva, kterou pošle zpět Alici. Nakonec Alice dešifruje jeho zprávu použitím svého soukromého klíče 'd' přes svoje zadní dvířka, c na (d mod n) je rovno Bobově originální zprávě 'm'. Všimni si, že Eve nebo kdokoliv jiný s 'c', 'n' a 'e' může zjistit pouze exponent 'd', pouze pokud mohou vypočítat Fí(n), což vyžaduje, aby znali prvočíselný rozklad 'n'. Pokud bude 'n' dostatečně velké, tak si Alice může být jistá, že by trvalo stovky let i s tou nejsilnější sítí počítačů. Tento trik byl okamžitě utajen po jeho zveřejnění. Bylo to však znovu objeveno v roce 1977 Ronem Rivestem, Adi Shamirem a Leonardem Adlemanem. To je důvod, proč je to nyní známo jako RSA šifrování. RSA je nejrozšířenější algoritmus na světě využívající veřejný klíč. A nejčastěji kopírovaný software v historii. Každý uživatel internetu na Zemi používá RSA nebo jeho variantu, ať si to uvědomují či nikoliv. Jeho síla stojí na obtížnosti prvočíselného rozkladu, která souvisí s otázkou o rozložení prvočísel. Otázkou, která zůstala nevyřešena po tísíce let.