Jednosměrná funkce s padacími dvířky

Jednosměrná funkce s padacími dvířky je funkce, kterou je snadné spočítat a všeobecně se věří, že je jí těžké invertovat, nemaje informaci navíc (tj. mají ony padací dvířka, jimiž nejde projít v opačném směru). 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 mají zadní vrátka. Tyto funkce se na stavbu kryptosystémů rovněž používají (ElGamal, DSA).

Parametry funkcí jsou často čísla, která jsou autoritou vydána a u nichž nelze zkontrolovat, zda tím funkce neobsahují zadní vrátka. Jednou z možností zvýšit důvěru ve funkci je použít takzvaná "nothing-up-my-sleeve" čísla jako je například Ludolfovo číslo.

Odkazy

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