找到算法来计算特定输入的具体输出

这个问题更多的是数学方面。我给出了一个4字节的UID列表和一个相应的2字节代码列表 - 让我们称它们为散列。找到算法来计算特定输入的具体输出

它看起来像这样：

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

我有一些像这样的元组50，所以我想，如果我发现计算正确的哈希所有的UID的算法，我可以很肯定是正确的。

这是我的问题：我真的不知道如何开始。我不是数学家，对这类问题没有经验。我怀疑某种按位算法。它看起来可能是CRC16，但我已经证明了这一点。我不认为这是任何流行的算法。我也认为（或者更希望）算法不是太复杂。

我知道寻找计算某个输入的函数的一般问题是不可判定的。但假设算法很简单，我有什么可能？有没有可以帮助我的工具？是否有任何你可以建议写入我自己的工具的读取？我正在考虑某种暴力行为，但我怎样以系统的方式来做到这一点？

在此先感谢！

更新：由于没有关于我的问题有些不清晰：我真的需要找到的是使用了第一个地方创建的UID的哈希值的一种算法 - 即表现为以同样的方式或至少一个所有可能的UID（即4字节数字）。既然有人指出可能存在无数的函数，那么我想我必须找到最简单的函数，并根据更多的UID值进行测试。正如我所说的，我实际上假设该算法很简单并且没有充满模糊的密钥。如果我错了，我注定你注意到的。但如果没有，也许我有机会尝试错误。

来源

2013-02-10 j0ker

可能属于[之一]（http://cs.stackexchange.com/）[the]（http://programmers.stackexchange.com/）[other]（http://cstheory.stackexchange.com /）[网站]（http://math.stackexchange.com/）。 – Dukeling 2013-02-10 22:36:51

给定50个元组，找到一个成功预测kew密钥映射的算法：没有机会。给定50个元组，找到一个成功映射所有密钥的算法：简单。给定50个元组，找到一个成功映射所有密钥而不实际存储映射的算法：非平凡自动执行。另外，并不常用。 – 2013-02-10 22:38:04

@ JanDvorak答案的一个稍微更加明确的版本：假设它只有50对，并且你没有被赋予哈希算法，那么最简单的解决方案就是创建一个映射（例如Java的'HashMap'或Python的'dict'），其中键是原始字符串，并且值（从输入密钥获得）是所需的散列。 50对于计算机来说是一个小数目，因此尝试对哈希算法进行逆向工程是不值得花时间的（根据所使用的哈希算法，这是一个很难实际上不可能完成的任务）。 – acattle 2013-02-10 22:43:07

正如其他人已经评论/回答，你有一个不健康的问题，以及很少知道未知函数的信息（当然，它是未知的:)。虽然您可以尝试通过遗传编程来猜测函数，但您不能期望它确信它实际上代表了未知函数 - 而不是仅具有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个单位的误差，因此该函数对于给定的例子是正确的，但这意味着什么都没有。它花了几次运行，几千代等，生成一个程序，没有错误的例子。现在，需要注意的问题是，我认为未知函数将参数与输入结合在一起 - 可能或不是这样。此外，我只是猜测关键可能是0xbeef主要是因为它是一个很好的十六进制值。这些决定的结果是，程序将尝试产生一个程序来适应这些选择，这与未知函数的作用可能完全不正确。这意味着你需要以某种方式使这个未知函数比现在更为人所知，以期望得到任何相关的结果。

来源

2013-02-11 03:22:35 mmgp

我发现这个结果真的令人印象深刻，即使它不能像其他UID一样工作，正如您所期望的那样。你能详细说明你是如何做遗传编程的？我是这个领域的总新手，所以一些帮助会很棒。如果我能为所有价值找到一个函数，那么向我的上司表明这个问题不可解决就是一个令人印象深刻的结果。 – j0ker 2013-02-11 09:24:30

它通过生成被限制使用一些基本函数的'n'随机程序开始：常数，参数访问，加法，减法，乘法，模数，异或（如果其他），以及其他大多数快捷方式（如细节左移/右移）。然后根据已知输入' - >'输出评估这些程序中的每一个。 'k'最好的程序（产生更接近已知结果的那些程序）被保留，剩下的程序要么完全变异，要么在两个程序之间应用交叉运算符。这是重复的代数'g'。 – mmgp 2013-02-11 12:53:54

这将有所帮助。谢谢！ – j0ker 2013-02-11 13:42:48

你应该尝试澄清你特别想要达到的目标。

如果您只想将50 FIXED输入值映射到某些其他50 FIXED输出值，那么已经建议创建某种映射表，从输入到输出值就足够了。

如果另一方面给出了大约50个输入值及其对应的50个输出值，并且希望能够正确地预测任何其他输入值的相应输出值，至少从数学的角度来看，您的问题是无法解决的，因为给定ANY固定数量的输入到输出值映射仍然存在于无限数量的函数中，该函数将到目前为止所看到的所有输入值映射到迄今为止看到的完全相同的输出值，并仍然计算迄今为止未见的任何值的另一结果。

来源

2013-02-10 22:53:24 mikyra

感谢您的建议。我相应地更新了我的问题。 – j0ker 2013-02-10 23:05:48

这是一个不可能的任务，除非你能找到更多的信息或组装一个所有可能的输入和他们的输出的映射，所以你可以试验彻底。

来源

2013-02-10 23:12:56 EJP

找到算法来计算特定输入的具体输出

回答

相关问题