Take the 2-minute tour ×

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.

share|improve this question
What are your expected inputs to the inverse? Which of P, X, and G are you looking to get back? –  Ben Alpert Apr 24 '09 at 4:34
It would help if you show the algorithm you hope to do. Also, if you know the result and don't know X, then why pass in X? Pass in the result as a parameter. –  James Black Apr 24 '09 at 4:38
James: I think he has r = f(p, x, g) and wants a function x = h(p, r, g). –  Ben Alpert Apr 24 '09 at 4:40
@Ben,I need X. @James,X by default is random everytime you use the whole algoritm.I need to get that random number always.I know the other two,they are static.I also know the result.I have to reverse that function and then put the result and the other two parameters I know to get X. –  Ivan Prodanov Apr 24 '09 at 4:41
What does the function compute? Let's start there. :) –  JP Alioto Apr 24 '09 at 4:45

6 Answers 6

up vote 20 down vote accepted

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

share|improve this answer
However, if the poster does solve this problem, I've got this RSA system I'm trying to break... –  Stefan Kendall Apr 24 '09 at 5:05
the "mod" is the problem. You won't break this ever. 5 mod 2 has the same result as 7 mod 2 and 9 mod 4 and so on. You can't determine the input based on the output. There is an infinity of input combinations that result in the desired output. Go to sleep. –  Andrei Rînea Apr 24 '09 at 21:09
Exactly. You're not supposed to get X. You're supposed to check whether the client knew the correct x by sending it different G and P, and check if their results agree with yours. But at no point is x supposed to be transmitted. –  Tim Lin Apr 29 '09 at 15:20


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?

share|improve this answer

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(G2i), 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.

share|improve this answer

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

share|improve this answer
Yeah,X = X << 1 ,everytime you step the loop. Does that mean its impossible? –  Ivan Prodanov Apr 24 '09 at 4:45
Not impossible, just that there are multiple answers (and not due to the << but due to the %). Is this fast enough for you?... x=0; do { if (Func_4(P,x,G)==I) then return x; x++; } while (x!=0); –  Doug Currie Apr 24 '09 at 14:54

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..

share|improve this answer

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.

share|improve this answer

Your Answer


