- Trapdoor functions are very similiar to one-way functions in that their inverse is computationally infeasible.
- However they have an additional property such that they contain a trapdoor.
- A trapdoor is an extra piece of information which makes it easy to invert the function.
- A common one-way function is semi-prime factorization:
- X is a set of prime numbers
- Y is a set of integers
- f is a function that maps X2 to Y:
- Given x1 and x2 it is easy to find y (you can just multiply them together).
- However given only y, it becomes computationally infeasible to find x1 and x2, especially if they are very large.
- The trapdoor in this function is when you know one of the values of X. For example: if you know that x1 is always equal to 23:
def f(_x1, _x2): return _x1 * _x2 def g(_y, _x1): return _x1, _y // x1 x1, x2 = 7, 13 y = f(x1, x2) print("The image of " + str((x1, x2)) + " is " + str(y)) # prints: The image of (7, 13) is 91 x1 = 7 y = 91 x1, x2 = g(y, x1) print("The preimage of " + str(y) + " is " + str((x1, x2))) # prints: The preimage of 91 is (7, 13)