Jednocestná funkce se zadními vrátky

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