Overview#
Trapdoor Function is a
function that is easy to compute in one direction, yet
difficult to compute in the opposite direction (finding its inverse) without special information, called the "
trapdoor". Trapdoor Function are widely used in
cryptography.
RSA Assumption#
In this
example, having the inverse of e modulo φ(n), the Euler's totient function of n, is the trapdoor:
f(x)=xe mod (n)
If the factorization is known,
- φ(n) can be computed,
- so then the inverse d of e can be computed d = e−1 mod φ(n),
- and then given y = f(x) we can find x = yd mod n = xed mod n = x mod n.
Its hardness follows from RSA assumption.!! More Information
There might be more information for this subject on one of the following: