Reverse that Math function

Question

Hello,

I need to reverse a function with hard Math operations, I'm asking here to check if it's even possible, eventually for help.

    public static UInt32 Func_4(UInt32 P, UInt32 X, UInt32 G)
    {
        UInt64 result = 1;
        UInt64 mult = G;
        if (X == 0)
            return 1;
        while (X != 0)
        {
            if ((X & 1) != 0)
                result = (mult * result) % P;
            X = X >> 1;
            mult = (mult * mult) % P;
        }
        return (UInt32)result;
    }

By "Reversing" I mean this: I know G, I know P, I know the result. I need X.

I tried to translate it again this morning while my mind was clear, but I failed. Is it even possible?

Thank you in advance.

Answer 1

It looks like your Func_4() function calculates G^X mod P. What you're asking for is a solution to the discrete logarithm problem, but no efficient algorithm is known.

Answer 2

It looks like i = (g**x) mod p. That means there may be more than one x

Answer 3

well,

working through this by hand for:

P=5, X=0b0000 1110, G=7

P=5, X=0b0001 1110, G=7

P=5, X=0b0011 1110, G=7

P=5, X=0b0111 1110, G=7

etc, i think you see the pattern

all have the same return value for result (4)...

therefore any attempt to reverse this to get a value for X would have multiple possible values for X..

depending what you actually need out of this thing, this may not really matter...

whats the context of this thing?

Answer 4

Since the modulo operator is in play, you can tell immediately that the function is not bijective: for a fixed P and G, different x's may return the same result.

But the function is bijective for a limited domain of x. Just like atan, asin, sqrt, .... produce a whole set of values, when you limit the domain, you can pick the correct one.

At first sight, what the function does, for a very large P, is,

The product of G^(2i*x[i]), where x[i] is the i'th bit of x (starting with bit 0 as least significant).

This means that given a large P (larger than Prod(G²ⁱ), for x=0x1111...111), you can reverse the function. It also seems that the function was designed not to be reversible for smaller P's.

Answer 5

I seriously think you're abusing this algorithm. From your description, and from looking at the algorithm, it's pretty clear that this is designed to go forward only. Think of it as computing a checksum of X using keys P and G.

Answer 6

pseduo algorithm

R = pow(G,X) mod P

ie) there exists one Q which is R + P * Q = pow (G,X)

In reverse, Check Y for all Q from 0 to UINT32((MAXUINT32-R)/P),

Y = log ( R + P * Q ) / log (G)

and if the value Y does not have fractions, then they are the Set of multiple "X" answers to your problem.

Assume X1 is the first X value which does not have fractions and X2 is the second X Value which does not have fractions. Then Set of all X can be given in the equation X(S) = X1 + (X2-X1) * S where S=0 to UINT32( (MAXUINT32-X1) / (X2-X1) ).

That is due to if 1= Pow(G,T) mod P and then Pow(G,X+T) mod P = Pow(G,X) mod P * Pow(G,T) mod P which is also Pow(G,X) mod P. Hence X, X+T, X+2T, X+3T... all will have same values..