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í.

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