Jednosměrná funkce

Jednosměrná funkce, někdy též jednocestná funkce, je taková funkce, kterou lze snadno vyčíslit, ale je velmi obtížné z výsledku funkce odvodit její vstup. Ze zadaného x tedy lze snadno získat f(x), avšak výpočet inverzní funkce, získání x při znalosti f(x), je sice teoreticky možné, ale prakticky velmi obtížné. Důvodem je existence velmi vysokého počtu možných řešení, přičemž je nutné všechny ověřit, aby skutečné řešení bylo nalezeno a toto ověření by trvalo neúměrně dlouho (v praxi se požadují tisíce, miliardy i více let).

Na existenci jednosměrných funkcí spoléhá velká část asymetrické kryptografie.

V současné době není matematicky dokázáno, zda jednosměrné funkce vůbec existují. Důkaz existence by také znamenal, že P≠NP (naopak ani z důkazu nerovnosti těchto tříd složitosti existence jednosměrných funkcí nutně nevyplývá).

Možné jednosměrné funkce

Mezi funkce, které jsou v současné době používány jako jednosměrné funkce, patří například následující: * Násobení: Součin dvou (i velmi velkých) čísel lze spočítat snadno; nejrychlejší známý algoritmus pro rozklad velkých čísel na prvočinitele (faktorizace) vyžaduje čas 2^{O\left(\sqrt{\log P \log \log P}\right)}, kde P je druhý největší prvočinitel faktorizovaného čísla. * Rabinova funkce: Lze dokázat, že zjišťování druhé odmocniny modulo N je výpočetně ekvivalentní faktorizaci čísla N. +more Druhá mocnina na konečném tělese je tedy kandidátem na jednosměrnou funkci. (Viz též kvadratické reziduum. ) * Umocňování nad konečným tělesem: Výpočet diskrétního logaritmu se obecně pokládá za náročnou úlohu. * Za další kandidáty se považují některé NP-úplné problémy jako např. problém batohu či subset sum.

Související články

Hašovací funkce * Jednosměrná funkce se zadními vrátky

Externí odkazy

[url=https://web. archive. +moreorg/web/20050826172740/http://www. fi. muni. cz/~xkumpost/bakalarka. pdf]Marek Kumpošt: Hašovací funkce[/url] (bakalářská práce, Fakulta informatiky Masarykovy university, 2002).

Kategorie:Kryptografická primitiva