Šifra veřejného klíče

Šifrování s pomocí veřejného klíče je tzv. asymetrická kryptografie, která pro šifrování a dešifrování používá dva odlišné klíče. Odesilatel zprávy použije k zašifrování veřejný klíč. Tuto zprávu je ale schopen rozluštit pouze příjemce - majitel soukromého (tajného) klíče. Takže ani odesilatel není schopen zprávu rozluštit. Výhoda tohoto postupu spočívá v tom, že odesilatel a příjemce zprávy mezi sebou nemusí sdílet jeden tajný klíč, což je slabinou symetrické šifry, která používá jeden klíč k šifrování i dešifrování.

První aplikací šifrování veřejného klíče je algoritmus RSA (což jsou iniciály jeho autorů: Rivest, Shamir a Adleman), na který se podíváme podrobněji. Princip RSA spočívá v tom, že je velmi jednoduché provést vynásobení dvou čísel, ale je nesmírně obtížné provést faktorizaci - neboli rozklad součinu na jeho činitele.

Postup RSA šifrování

Alice si vybere dvě opravdu veliká náhodně zvolená prvočísla p a q. Tato čísla mezi sebou vynásobí, čímž získá číslo N. Následně vybere číslo e, které je menší než (p-1)·(q-1) a s tímto součinem je nesoudělné. N a e dohromady tvoří veřejný klíč. Ten Alice zveřejní, aby mohl každý tímto klíčem zašifrovat zprávu a poslat ji Alici.

Pro zašifrování je nutné převést zprávu na číslo (M). Toho lze docílit například kódováním ASCII, jehož rozšířená osmibitová verze obsahuje 256 znaků. Číslo M se poté zašifruje tak, že vytvoří šifrované číslo C podle vzorce: C = M^e (mod N).

Bob pošle Alici zašifrovanou zprávu C. Alice nyní potřebuje svůj tajný soukromý klíč, kterým by zprávu dešifrovala. Alice je jediná, která zná čísla p a q. S pomocí nich vytvoří souktomý klíč d, pro který platí:
d · e 1 (mod (p-1)·(q-1)). Hodnotu d zjistí použitím rozšířeného Euklidova algoritmu (EEA).
K dešifrování zprávy použije Alice následující vzorec: M = C^d (mod N). Celý postup si ukážeme na příkladu.

Jednoduchý příklad použití RSA

1) p = 5, q = 11
2) N = p · q = 5 · 11 = 55
3) e = 7
4) M = 33 (v kódu ASCII se jedná o znak pro vykřičník)
5) C = M^e (mod N) = 33⁷ (mod 55) = [33⁴ (mod 55) · 33² (mod 55) · 33 (mod 55)] (mod 55)
     C = (11 · 44 · 33) (mod 55) = 15 972 (mod 55) = 22
6) d · e 1 (mod (p-1)·(q-1))
     d · 7 1 (mod 4x10) => 7 · d 1 (mod 40)
     pomocí EEA zjistíme, že d = 23
7) M = C^d (mod N) = 22²³ (mod 55) = [(22⁴ (mod 55))⁵ · 22² (mod 55) · 22 (mod 55)] (mod 55)
     M = 11⁵ · 44 · 22 (mod 55) = 155 897 368 (mod 55) = 33

Bob pomocí veřejného klíče (N = 55, e = 7) zašifroval a poslal Alici zprávu C = 22. Alice svým soukromým klíčem (d = 23) zprávu rozšifruje a zjistí, že jí Bob poslal vykřičník (M = 33).

Sami si můžete vyzkoušet šifrování metodou RSA v jednoduché aplikaci v sekci kalkulačky.

Komentáře k článku