Jednocestná funkce se zadními vrátky
Z Wikipedie, otevřené encyklopedie
Trapdoor jednosměrná funkce je funkce, kterou je snadné spočítat a všeobecně se věří, že je jí těžké invertovat, nemaje informaci navíc (trapdoor). 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í.
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 and 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, zda-li jsou trapdoor. Tyto funkce se na stavbu kryptosystémů rovněž používají (ElGamalova šifra, DSA).
[editovat] Odkazy
- W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), pp644–654 (1976). PDF version of the paper

