How to write a decryption function for this algorithm?

Question

C++ / C#

There is such a function for encrypting every two bytes in C:

// state = два байта из файла
for (r = 0; r < 34567890; r = r + 1) {
            state = state ^ 27569;
            state = state * -1635 - 16196;
            state = state * 31663;
            state = state + 14122;
            state = state * 25561;
            state = state ^ 17548;
            state = state * 18199 - 11258;
            state = state * 21727;
        } // (для удобства разбил действия на строки)

You need to write a decryption function.
I tried many different ways - replace multiplication with division, minus with plus and turn upside down - it doesn’t work ...
UPD: the algorithm most likely has an overflow

Answer 1

You need to reverse all operations and do them backwards.
Encryption does 34567890 iterations, you need to do the same. Internally, the order of operations must be reversed so that the undoes are performed in reverse order. If there are 2 operations in the line, for example, multiplication and subtraction, then first you need to perform the inverse of the subtraction and only then the inverse of the multiplication.
The inverses of subtraction and addition are addition and subtraction, respectively. If encryption adds 12345, then you need to subtract 12345 in the decryptor. Bitwise exclusive OR back to itself, because if you apply it 2 times, you get the original number.
With multiplication, everything is much more complicated. I'm assuming the type of state is unsigned int. If it's signed, then overflow multiplication is undefined behavior at all. In unsigned integers, multiplication with overflow is simply multiplication and modulo 2^32. That is, you need to find the operation inverse to multiplication modulo 2 ^ 32.
This will be multiplication by the inverse modulo .
To find it, you will need to use the extended Euclidean algorithm (it is described in the article at the link above). It can either be implemented separately to find the inverses of 31663 (and other factors). Or you can drive it away with your hands on a piece of paper.
Separately, you need to deal with a negative multiplier. You need to find a positive multiplier that will give exactly the same encryption result.Hint .
Edit, just noticed in the question that state is two bytes. So everything happens modulo 2^16.

Answer 2

And it’s not a fact that this is generally reversible, since when multiplied by 31663, a 16-bit integer is guaranteed to overflow, and the high bits will be lost.
You can try this, of course: create an array of all possible 16-bit numbers: 0, 1, 2, ..., 65535.
Then encrypt each element of this array with this algorithm.
If some elements are repeated in the resulting array, then it is impossible to completely reverse the operation - only partially, only for unique elements in the array.
If all elements of the array are unique, then you can reverse the operation by simply determining the index of the input pair of bytes in this array. This index will be the original value. There is already room for optimization.