Reversing a function involving a modulus arithmetics

Question

I'm trying to reverse-engineer a function to get the input. Suppose we know the output (x). Is it possible to get the input (z)? The code for the function is as follows

uint myfunc (uint z){
    var uint_1 = 1372797859u;
    var uint_2 = 1114478491u;
    ulong a = (ulong)z;
    uint x  = 1u;
    for (int i = 0; i < 32; i += 1)
    {
        if ((uint_2 & 1u) != 0u)
        {
            x  = (uint)((ulong)x  * a % (ulong)uint_1);
        }
        a = a * a % (ulong)uint_1;
        uint_2 >>= 1;
    }
    return x ;
}

Suppose we know the value of the output (x) this function throws at us, say 35500.

Considering x = (uint)((ulong)x * a % (ulong)uint_1); It is obvious that x on left hand side is greater than the one on the right hand side as we start with uint x = 1u; If we had something like x = a % (ulong)uint_1;, we could just check the value of a by brute force (starting a with 1 and incrementing it with 1). The code is complex and I don't know if it is even possible to reverse-engineer this function.

Answer 1

Not only is it possible to get the input z, you can use your function myfunc with one little change to get it: simply change

var uint_2 = 1114478491u;

to

var uint_2 = 42451u;

To elaborate:

The function myfunc is performing modular exponentiation with a fixed exponent. Specifically, it is computing z^1114478491 mod 1372797859.

Also, 1372797859 = 25057 * 54787, both factors are primes. This may be recognized as an instance of the RSA cryptosystem with toy-sized parameters. We may regard myfunc as performing an RSA encryption^* and therefore 1114478491 as the encrypt exponent. Therefore, using the procedure outlined in the Wikipedia page we can compute the decrypt exponent which turns out to be 42451. Since myfunc is just a modular exponentiation function, merely by changing 1114478491u to 42451u we have the decrypt function which is the inverse.

^{*In RSA an encrypt and decrypt exponent exist, but which role is assigned to which exponent is arbitrary. However, in actual implementations the encrypt exponent is usually small, almost always 65537 in fact, and such a small exponent can only play the role of the encrypt exponent or the system is easily broken.}