Asymetrická šifra s veřejným klíčem

O veřejné distribuci klíčů jsem již dříve psal. Pojďme se však podívat nejen na samotnou distribuci, ale i na myšlenku asymetrického šifrování. Prvně je však třeba vysvětlit několik důležitých věcí. Začněme tím, co vlastně znamená asymetrická šifra. Před myšlenkou asymetrického šifrování, jejíž autorem je Whitfield Diffie, se používalo výhradně šifrování symetrické, což znamená, že proces dešifrování zakódované zprávy je přesně opačný k procesu šifrování. Asymetrické šifrování však zavádí myšlenku použití jiného klíče na šifrování a jiného na dešifrování.

Jak to vyřešit? Jak je možné použít jiný klíč na šifrování a jiný na dešifrování? Již existoval koncept, který umožňoval výměnu klíčů veřejně (a bezpečně). Stále byl však na principu synchronní komunikace odesílatele a příjemce, což nebylo optimální řešení a proto byl vymyšlen způsob jak tento problém obejít. Myšlenka byla jednoduchá. Příjemce musí vytvořit veřejný klíč, který následně zveřejní tak, aby byl veřejný opravdu pro všechny. V tomto případě je jasné, že by to nemělo smysl, pokud by se nepoužívala jednosměrná funkce šifrování, což je další pravidlo. A zároveň opět onen příjemce musí mít svůj tajný klíč, který dokáže informaci zašifrovanou veřejným klíčem dešifrovat. Z toho je patrná ta asymetričnost šifry. Nepoužívám stejný klíč na zašifrování a dešifrování jako u jiných šifer.

Tomuto systému se říká RSA (Ronald Riverst, Adi Shamir, Leonard Adleman). Pojďme se na něj teď podívat matematicky, protože teorie je moc obecná (a matematika zase složitá). Odesílatel zprávy si musí zvolit dvě velmi velká prvočísla (A, B). Tyto prvočísla mezi sebou vynásobí a dostane další ještě větší číslo (AB). Násobení je zcela triviální jednosměrná operace a systém RSA si zakládá na tom, že faktorizovat velké číslo je v reálním čase prakticky nemožné. Dále si odesílatel zvolí číslo C a to uveřejní společně s číslem AB. Toto jsou informace, které má každý k dispozici. Pro šifrování je nutné zprávu převést na číslo M (například binárně). Toto číslo se poté dosadí podle vzorce „šifra“= M^C (mod AB). Zpětně se pak informace dá velmi snadno dostat obráceným postupem se znalostí onoho součinu prvočísel zvolených na začátku. Bez znalosti těchto prvočísel je dešifrování téměř nemožné, což však také není úplně pravda viz poslední odstavec.

Je zřejmé, že úspěch šifry spočívá ve zvolení dostatečně velkých prvočísel a mocnitele C, který by vzhledem k prvočíslům neměl mít žádného společného dělitele. Resp. přesněji čísla C a (A-1) * (B-1). Při představení RSA byl pro jeho reprezentaci uveřejněn zašifrovaný text s veřejným klíčem. Soutěžním úkolem bylo faktorizovat veřejný klíč na dvě složky a poté zprávu dešifrovat. Faktorizace trvala ve výsledku celkem 17 let, kdy tým 600 dobrovolníků oznámil 26. dubna 1994 činitele veřejného klíče. A jaký že byl ten klíč?

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541

Dílčí prvočísla si nechám jako tajemství? (-:

  • V komentářích jsou povolené HTML tagy <a href=""> <blockquote> <code> <em> <strong>
  • Kódy programů zapisujte takto pomocí <pre><code>alert('XSS');</code></pre>