Interesting Byte Mix Equation and it's inverse

Question

I recently came across this interesting equation (from the spectre code) that Mixes the value of a byte:

MixedByte = ((ByteToMix * 167) + 13) & 0xFF

or

MixedByte = BITAND((ByteToMix * 167) + 13, 255)

Which returns for each value 0-255 a mixed value 0-255 without duplicates or missing values. Ie. Reorders the values.

Since my maths is not that great I played around with the equation trying to figure out the inverse function.

Through trail and error I eventually stumbled across the solution:

OriginalByte = (MixedByte  * 23 + 213) & 0xFF

or

OriginalByte = BITAND(MixedByte  * 23 + 213, 255)

Can anyone explain how I could have determined the correct inverse function without using trail and error?

Answer 1

This isn't really bit manipulation. It's modular arithmetic.

"And"ing with 255 is the same as mod 256.

Every integer mod 256 has a multiplicative inverse. It can be computed with a modified version of Euclid's algorithm. But that's been done for you.

Check the modular inverse of 167 here. You'll find it's 23. The definition of a multiplicative inverse of x is a number that, when multiplied with x produces 1. You can verify that (167 * 23) mod 256 is 1. So you're in business.

Then a little simple algebra... Solve this equation for b...

a = 167 * b + 13 (mod 256)

like so...

a - 13 = 167 * b               (mod 256)
23 * (a - 13) = (23 * 167) * b (mod 256)
23 * a - 23 * 13 = 1 * b       (mod 256)
b = 23 * a + 213               (mod 256)

This is exactly your inverse expression. The last step requires -23*13 = 213 (mod 256), another identity of modular arithmetic. This is verified by -23*13 + 2*256 = 213.

Everyone who programs ought to learn a bit of number theory at this level.