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.
Answer
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 comments:
Post a Comment