crypto

Cracking A Nearly One-Way Function

For our standard maths, we have a function f(x), and then are able to reverse it to find f^{-1}(x). This could be:

and where the reverse is the square of the result:

But, is it possible to have a one-way function, and where we cannot reverse it? Well, it is thought that there might be irreversible one-way functions, but it has not been found yet. There are, though, a number of candidate one-way functions that, at the present time, where they are easy to compute, but extremely difficult to reverse. These can be defined as one-way permutations and are:

• Exponentiation modulo p. This is where we have f(x)=g^x (mod p) and where p is a prime number, and where it is extremely difficult to determine x, even though we know f(x), g and p.
• RSA function. This is where we cannot determine x for f(x)=x^e (mod n). With this n=pq, and where p and q are large prime numbers, and where e is selected to not share a factor with (p-1)(q-1).
• Rabin function. With this, we have n=pq, and where p and q are primes which equal 3 (mod 4). We then have f(x)=x² (mod n), and which results in a pseudo-random sequence where it is not possible to know x.

But, let’s crack the Rabin function with a backdoor function of: