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:

With this, we can create a pseudo-random sequence. For example, we can have p=23 and q=7, which are both equal to 3 (mod 4). We then get the Blum integer of n=161. If we use a seed value of x=59, we get the sequence of:

P=23
Q=7
N=161, phi=132
Seed=59
1 Current=100  \\ 59^2 mod (161)
2 Current=18   \\ 100^2 mod (161)
3 Current=2    \\ 18^2 mod (161)
4 Current=4 
5 Current=16 
6 Current=95 
7 Current=9 

Thus, the random sequence would be 100, 18, 2, 4, and so on. It should not be possible to determine the previous value of x as it is a one-way permutation (obviously, we are using small prime numbers if it would be possible), and we can only go forward and not in reserve. But, with some magic — the knowledge of the original prime numbers — we can reverse with the function of:

So here is the Python code to try this out [here]:

import random
import sympy
import sys

def next_usable_prime(x):
 p = sympy.nextprime(x)
 while (p % 4 != 3):
  p = sympy.nextprime(p)
 return p

bits=8

if (len(sys.argv)>1):
    bits=int(sys.argv[1])

p = next_usable_prime(random.randint(1,2**bits))
q = next_usable_prime(random.randint(1,2**bits))

N=p*q


print(f"P={p}")
print(f"Q={q}")
phi=(p-1)*(q-1)


print(f"N={N}, phi={phi}")

x=random.randint(1,N)
print(f"Seed={x}")

for i in range(1,21):
 x=pow(x,2,N)
 x_inv=pow(x,((p-1)*(q-1)+4)//8,N)
 print(f"{i} Current={x} Previous={x_inv}")

A sample run for 8 bit prime numbers gives [ ]:

P=239
Q=103
N=24617, phi=24276
Seed=10648
1 Current=18619 Previous=12321
2 Current=10567 Previous=18619
3 Current=23394 Previous=10567
4 Current=18709 Previous=23394
5 Current=22175 Previous=18709
6 Current=6050 Previous=22175
7 Current=21638 Previous=6050
8 Current=12321 Previous=21638
9 Current=18619 Previous=12321
10 Current=10567 Previous=18619
11 Current=23394 Previous=10567
12 Current=18709 Previous=23394
13 Current=22175 Previous=18709
14 Current=6050 Previous=22175
15 Current=21638 Previous=6050
16 Current=12321 Previous=21638
17 Current=18619 Previous=12321
18 Current=10567 Previous=18619
19 Current=23394 Previous=10567
20 Current=18709 Previous=23394

In this case, p is 239, q is 103 and n=24517.

We can see that, apart from the first value, the formula was able to take the current value and then work out the previous value of x. This is a back-door function, and it should not be possible to perform the reversing without knowing p and q in a reasonable amount of time. You can try the code here:

Cracking a pseudo random sequence