algorithm - 找到从特定输入计算特定输出的算法

Question

这个问题更多是在数学方面。我已经给出了一个 4 字节的十六进制 UID 列表和一个相应的 2 字节代码列表——我们称它们为散列。

看起来像这样:

7D04E214 --> 4A49
7D048DC3 --> A0E7
7D04DB2E --> 4191
...

我有大约 50 个这样的元组，所以我想如果我找到一种算法可以为所有 UID 计算正确的哈希值，我可以非常确定它是正确的。

这是我的问题:我真的不知道如何开始。我不是数学家，对这类问题没有经验。我怀疑某种按位算法。看起来它可能是 CRC16，但我已经伪造了它。我不认为这是任何流行的算法。我也认为(或者说希望)算法不会太复杂。

我知道找到从特定输入计算特定输出的函数的一般问题是不可判定的。但是假设算法是一个简单的算法，我有什么可能性？有什么可用的工具可以帮助我吗？对于编写我自己的工具，您有什么建议可以阅读吗？我正在考虑某种蛮力，但我如何以系统的方式做到这一点？

提前致谢!

更新:因为我的问题有些不清楚:我真的需要首先找到一种用于从 UID 创建哈希的算法 - 或者至少是一种表现良好的算法所有可能的 UID(即 4 字节数字)都采用相同的方式。由于有人指出可能的函数有无限多，我想我必须找到最简单的函数并针对更多 UID 值测试它们。正如我所说，我实际上假设该算法很简单并且没有充满晦涩的 key 。如果我错了，正如你所说，我注定要失败。但如果没有，也许我有机会试错。

Answer 1

正如其他人评论/回答的那样，您遇到了一个不适定的问题以及关于未知函数的鲜为人知的信息(好吧，毕竟它是未知的:)。虽然您可以尝试通过遗传编程来猜测一个函数，但您不能指望它实际上代表未知函数有任何信心 -- 而不是只有 50 个输入 -> 输出。

但是，作为一个虚拟实验，我玩弄了遗传编程，它为您给出的 3 个示例找到了以下程序:

def guess(a, key=0xbeef): # The parameter 'a' is an input value.
    temp = (a % (-14)) << 3
    if temp == 0:
        temp = -4
    temp = ((a ^ (-2 * key)) - temp) >> 2
    res = (temp + a + (a % (-15))) % key
    return res

结果如下:

Input      Output (guess)   Actual output    Diff
0x7d04e214 0x4a49           0x4a49           0
0x7d048dc3 0xa0e7           0xa0e7           0
0x7d04db2e 0x4191           0x4191           0

所以生成的程序对于这些输入的总误差为 0 个单位，因此函数对于给定的示例是正确的，但这没有任何意义。运行了几次，几千代，等等，生成一个没有给出示例错误的程序。现在，这里要注意的直接问题是我假设未知函数将 key 参数与输入一起使用——情况可能是这样，也可能不是。此外，我只是猜测 key 可能是 0xbeef，主要是因为它是一个很好的十六进制值。这些决定的结果是程序将尝试生成一个程序来适应这些选择，这可能与未知函数的作用完全不正确。这意味着您需要以某种方式让这个未知函数比现在更广为人知，以便期待任何相关结果。