function - 反转功能

Question

我一直在尝试反转一个看起来非常简单的函数。该函数以汇编形式表示:(参数被加载到AX中)

AND AX, 0xFFFE (round down to even number)
MUL AX (Multiply AX by AX ; the result is represented as DX:AX)
XOR AX,DX

该函数可以描述为:H(X) = F(X & 0xFFFE); F(X) = ((X * X) mod 2^16) xor ((X * X) div 2^16)

计算了从 1 到 2^16 的所有值并在 matlab 上绘制，以便“看到”某个函数。

谁能帮我找到这个问题的答案吗？ (当给定 y 时，参数 x 是什么)。对于某些值来说，可能有多个答案，因此缩小范围是我的目标。

谢谢，或者。

Answer 1

这是一个 hash function.
您无法反转哈希函数，因为它的全部意义在于它是一个单向函数。
乘法显然是可逆的，异或则不然。通过组合乘法的低位和高位部分，你会丢失信息。

正如您在图中看到的那样，有一些空格，因为该图中有 2^16 个空格，这意味着还有不同的输入值哈希为相同的值。
这在哈希函数中很常见。

“反转”它的唯一方法是构建一个查找表，将输出值转换为可能的输入值。然而，您会发现每个输出值都是 1 个或多个输入值。

偶数 x 偶数始终是 4 的倍数。
因此低 2 位始终为 0，因此结果的低 2 位是乘法的第 16+17 位。
位 2..15 是位 2..15 异或位 18..31 的混合。
快速模拟显示 24350 个唯一输出，因此每个输入值平均 1.34 0.34 个重复项，不错。
最大碰撞次数为 6，但大多数数字不会发生碰撞。

对于所有不冲突的数字，您可以在查找表中唯一地查找您的输入值(所有这些显然都忽略奇数输入值)。