Home > Enterprise >  Function including random number that can be inverted without the random number
Function including random number that can be inverted without the random number

Time:07-30

Given a number x and a random number n, I am looking for two functions F and G so that:

  • y = F(x, n) where y is different for different values of n
  • x = G(y)

all numbers are (large, e.g. 256 bit) integers

For instance given a list of numbers k1, k2, k3, f4 generated by applying multiple times F, it is possible to calculate k3 from k4 but not k4 from k3 (the random number prevents the inversion).

The problem is obvious if we allow to use n (or derived) in G (it is basically an asymmetric encryption) but this is not the target.

Any idea?

Update

I found a function that works with infinite precision F = x * pow(coprime(x), n)

x = 29
p = 5
n = 20

def f(x,n):
    return x * pow(p,n) 

f(x,n) => 2765655517578125


and G becomes

def g(y):
    x = y
    while x % p == 0:
        x = x/p
    return x
g(y) = 29

Unfortunately this fails with overflow as soon as numbers become big (limited precision)

Many Thanks

CodePudding user response:

Based on your requirements, the following should work. If there is some other requirement that I did not understand from your question, please clarify, because this seems to suffice based on your definition. In that case, I will change or delete this answer.

f(x, n) = x | n;
g(y | n) = y;

where | means concatenation of bits. We can assign a fixed (maximum) number of bits for n and pad with zeros.

CodePudding user response:

there can be no solution for this problem because: for a constant x1 and variable r you would have an output set with all Integers in it. for a constant x2 and variable r again you would have an output set with all Integers in it. so at best you can have a function g which would take a number from the output set of function f and return all possible answers which are infinite. this is similar to writing a reverse hashing function; which defies logic.

  • Related