Wednesday, March 30, 2016

elementary number theory - 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.


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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...