algorithm - 有趣的字节混合方程及其逆

Question

我最近遇到了这个有趣的等式(来自幽灵代码)，它混合了一个字节的值:

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

或

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

它为每个值 0-255 返回一个混合值 0-255，没有重复值或缺失值。 IE。重新排序值。

由于我的数学不是很好，所以我玩弄方程式试图找出反函数。

通过反复试验，我最终偶然发现了解决方案:

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

或

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

谁能解释我如何在不使用跟踪和错误的情况下确定正确的反函数？

Answer 1

这不是真正的位操作。这是模运算。

“与”255 与 mod 256 相同。

每个整数 mod 256 都有一个 multiplicative inverse .它可以用 modified version of Euclid's algorithm 来计算.但那已经为你完成了。

检查 167 的模逆 here .你会发现它是 23。x 的乘法逆的定义是一个数字，当它与 x 相乘时产生 1。你可以验证 (167 * 23) mod 256 是 1。所以你在做生意。

然后是一些简单的代数......求解这个方程式......

a = 167 * b + 13 (mod 256)

像这样...

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)

这正是您的反表达式。最后一步需要 -23*13 = 213 (mod 256)，这是模运算的另一个恒等式。这由 -23*13 + 2*256 = 213 验证。

每个编程人员都应该在这个级别学习一些数论。