我一直在尝试反转一个看起来非常简单的函数。 该函数以汇编形式表示: (参数被加载到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 是什么)。 对于某些值来说,可能有多个答案,因此缩小范围是我的目标。
谢谢, 或者。
最佳答案
这是一个 hash function.
您无法反转哈希函数,因为它的全部意义在于它是一个单向函数。
乘法显然是可逆的,异或则不然。通过组合乘法的低位和高位部分,你会丢失信息。
正如您在图中看到的那样,有一些空格,因为该图中有 2^16 个空格,这意味着还有不同的输入值哈希为相同的值。
这在哈希函数中很常见。
“反转”它的唯一方法是构建一个查找表,将输出值转换为可能的输入值。然而,您会发现每个输出值都是 1 个或多个输入值。
偶数 x 偶数始终是 4 的倍数。
因此低 2 位始终为 0,因此结果的低 2 位是乘法的第 16+17 位。
位 2..15 是位 2..15 异或位 18..31 的混合。
快速模拟显示 24350 个唯一输出,因此每个输入值平均 1.34 0.34 个重复项,不错。
最大碰撞次数为 6,但大多数数字不会发生碰撞。
对于所有不冲突的数字,您可以在查找表中唯一地查找您的输入值(所有这些显然都忽略奇数输入值)。
关于function - 反转功能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37161326/