0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there a trick for even numbers too, or no? $\endgroup$ – Bart Pelle Jul 29 '15 at 12:17
  • $\begingroup$ 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$) $\endgroup$ – gammatester Jul 29 '15 at 13:27
  • $\begingroup$ So one can very much verify a pair by checking if the gcd of the two components is equal to 1? $\endgroup$ – Bart Pelle Jul 29 '15 at 14:08
  • $\begingroup$ 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}$ $\endgroup$ – gammatester Jul 29 '15 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.