Šifrování RSA: krok 3

Před 2000 lety Eukleides dokázal, že každé číslo má jedinečný prvočíselný rozklad, který si můžeme představit jako tajný klíč. Ukazuje se, že prvočíselný rozklad je složitý problém. Vyjasníme si, co myslíme pojmy "snadný" a "složitý" pomocí tzv. časové složitosti algoritmu. Všichni umíme násobit čísla a každý z nás pro urychlení používá svůj vlastní postup. Pokud naprogramujeme počítač, aby násobil čísla, tak to může provádět mnohem rychleji než člověk. Zde je graf, který ukazuje kolik času potřebuje počítač, aby vypočetl násobek dvou čísel. Potřebný čas pro získání výsledku se zvyšuje s rostoucími čísly. Všimněte si, že čas pro výpočet se drží pod 1s i s poměrně vysokými čísly. Proto je snadné provádět násobení. Teď to porovnejte s prvočíselným rozkladem. Pokud by vám někdo řekl, abyste našli prvočíselný rozklad čísla 589, tak si hned všimnete, že se příklad zdá být těžší. Bez ohledu na vaši strategii to bude vyžadovat použití metody pokus-omyl, dokud nenajdete číslo, kterým lze 589 dělit. Až s tím dozápasíte, tak zjistíte, že prvočíselný rozklad je (19 krát 31). Pokud byste měli najít prvočíselný rozklad čísla 437231, tak byste to pravděpodobně vzdali a vzali si na pomoc počítač. Tohle funguje dobře pro malá čísla, ale pokud zkusíme rozkládat větší čísla, tak výsledek nebude spočítán "v rozumném čase". Čas potřebný k výpočtu rapidně roste s přírůstkem potřebných kroků. A jak čísla rostou, tak počítač potřebuje minuty a pak i hodiny. Nakonec bude potřebovat stovky nebo tisíce let pro prvočíselný rozklad obrovských čísel. Proto říkáme, že je to těžký problém. Kvůli nárůstu času potřebného k řešení. Takže prvočíselný rozklad je to, co Cocks použil pro vytvoření řešení se zadními vrátky. Krok 1: Alice náhodně vygeneruje prvočíslo přes 150 číslic dlouhé. Nazveme ho P1. Potom vygeneruje druhé náhodné prvočíslo o zhruba stejné velikosti. Říkejme mu P2. Pak vynásobí tyto dvě prvočísla, aby dostala složené číslo N, které má více než 300 číslic. Tento krok s násobením zabere méně než sekundu. Zvládli byste to provést dokonce i ve svém webovém prohlížeči. Potom vezme prvočíselný rozklad N, (P1 krát P2), a schová ho. I kdyby se teď N dostalo ke komukoliv jinému, tak by mu trvalo roky, než by na počítači nalezl prvočíslený rozklad N. Krok 2: Cocks potřeboval nalézt funkci, která závisí na znalosti prvočíselného rozkladu N. Kvůli tomu se podíval do práce z roku 1760, jejímž autorem byl švýcarský matematik Leonhard Euler.