If you're seeing this message, it means we're having trouble loading external resources on our website.

Pokud používáš webový filtr, ujisti se, že domény: *.kastatic.org and *.kasandbox.org jsou vyloučeny z filtrování.

Hlavní obsah

Šifrování RSA: krok 2

Vytvoření jednosměrné funkce Tvůrce: Brit Cruise.

Chceš se zapojit do diskuze?

Zatím žádné příspěvky.
Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.

Transkript

Řešení nalezl jiný britský matematik a odborník na šifrování Clifford Cocks. Cocks musel vytvořit zvláštní druh jednosměrné funkce známé jako jednosměrná funkce s tzv. zadními vrátky. Je to funkce, kterou je snadné spočítat v jednom směru, ale přitom těžké spočítat v opačném směru, pokud nemáte speciální informaci, které se říká "zadní vrátka". K tomu využil umocňování v modulární aritmetice, kterou jsme si ukázali jako hodinovou aritmetiku v Diffie-Hellmanově protokolu takto: Vezměte číslo a umocněte ho nějakým exponentem, vydělte modulem a výsledkem je zbytek po dělení. A takto to může být použito pro zašifrování zprávy: Představte si, že Bob má zprávu, kterou převedl na číslo 'm'. Pak vynásobí své číslo tím samým číslem 'e' krát, kde 'e' je veřejný exponent. Poté vydělí výsledek náhodným číslem 'N' a výstupem je zbytek po dělení. Tedy nějaké číslo 'c'. Tento výpočet je snadné provést. Ale pokud máme pouze 'c', 'e' a 'N', tak je mnohem obtížnější určit, které 'm' bylo použito. Protože se musíme uchýlit k nějaké formě pokus/omyl. Toto je tedy jednosměrná funkce, kterou můžeme aplikovat na 'm'. Je snadné to provést, ale obtížné vypočítat zpětně. To je náš matematický zámek. A teď: Jak je to s klíčem? Klíč jsou "zadní vrátka". Kousek informace díky kterému je snadné zprávu dešifrovat. Potřebujeme umocnit 'c' nějakým dalším exponentem 'd' a tím vrátit zpět původní operaci, která byla provedena na 'm' a výstupem bude původní zpráva 'm'. Takže obě operace společně jsou totéž, co 'm' na 'e' to celé na 'd', což je to samé co 'm' na ('e' krát 'd'). 'e' je zašifrování a 'd' je dešifrování. Proto potřebujeme způsob, jak může Alice vytvořit 'e' a 'd' tak, že bude pro ostatní obtížné nalézt 'd'. A to vyžaduje druhou jednosměrnou funkci, která se používá pro vytvoření 'd' a kvůli tomu se Clifford Cocks podíval zpět k Eukleidovi.