Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 1
Lekce 4: Moderní kryptografieŠifrování RSA: krok 3
Třetí krok v šifrování pomocí RSA algoritmu. Jak dlouho trvá násobení a prvočíselný rozklad opravdu velkých čísel? Tvůrce: Brit Cruise.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.
Transkript
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.