# Modular Multiplicative Inverse / Euclidean Algorithm

There's a method of obfuscating programs which is around that turns code like:

my_int32 = my_value


into

my_int32 = my_value * 1448272385


and

return my_int32


into

return my_int32 * -1322181119


Now, after I have looked around a bit I think that this is related to the Modular multiplicative inverse and the Extended euclidean algorithm is used to find the pairing integer of an existing value.

Now, what I don't understand is that in some way, multiplying an integer value which overflows twice results in the original integer. E.g. 1234 * 1448272385 * -1322181119 results in 1234. What is the logic behind this? What properties of those numbers are the cause of this? I'm really terrible at maths, so my apologies if this is either obvious or my question is illogical.

The numbers are inverse $\pmod {2^{32}}.$ A further obfuscation is the usage of signed integers. Here you have $$1448272385\times(2^{32}-1322181119) \equiv 1\pmod {2^{32}}$$ But note that this trick only works for odd numbers not for even because even numbers have no inverse $\pmod {2^{32}}.$
The reason why you see no explicit $\pmod {2^{32}}$ is, that this is the way many programming languages work with 32-bit integers.
• No, there is no such multiplication trick for even numbers because they have no inverse (the GCD of even numbers and $2^{32}$ is not $1$, but a multiple of $2$) – gammatester Jul 29 '15 at 13:27
• No the crucial property is that the product must be $\equiv 1 \pmod {2^{32}}$. Each number must have $\mathrm{gcd}=1$ with $2^{32}$ – gammatester Jul 29 '15 at 14:24