Jednosměrná funkce se zadními vrátky

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Jednosměrná funkce se zadními vrátky je funkce, kterou je snadné spočítat a všeobecně se věří, že je jí těžké invertovat, nemaje informaci navíc (ony zadní vrátka). Tyto funkce se široce uplatňují v kryptografii.

Příkladem může být násobení velkých prvočísel. Existují efektivní algoritmy na nalezení a verifikaci velkých prvočísel, rovněž je jednoduché je vynásobit. Rozložit výsledek opět na součin prvočísel už tak snadné není. Pravděpodobnostní test prvočíselnosti nemusí systematicky odhalit pseudoprvočísla (například Carmichaelovo číslo), která jsou vygenerovaná někým jiným.

Pionýry kryptografie s veřejným klíčem, která uvedla tyto funkce do širšího povědomí byli v polovině sedmdesátých let Diffie, Hellman a Merkle. Posléze se ukázalo, že najít vhodné kandidáty je poměrně složité. Těmi nejnadějnějšími jsou RSA a Rabinovy soubory funkcí. Oba jsou založeny na počítání mocnin modulo složené číslo a souvisí s jeho faktorizací.

O funkcích založených na předpokladu nemožnosti efektivní inverze diskrétního logaritmu (modulo prvočíslo, nebo v grupě definované nad eliptickou křivkou) není dosud známo, zdali jsou zadní vrátka. Tyto funkce se na stavbu kryptosystémů rovněž používají (ElGamalova šifra, DSA).

Odkazy[editovat | editovat zdroj]

  • W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), pp644–654 (1976). PDF version of the paper