c++ - 我如何找到简单哈希算法的冲突

Question

我有以下哈希算法:

    unsigned long specialNum=0x4E67C6A7;
    unsigned int ch;
    char inputVal[]="                        AAPB2GXG";


    for(int i=0;i<strlen(inputVal);i++)
    {
        ch=inputVal[i];

        ch=ch+(specialNum*32);
        ch=ch+(specialNum/4);

        specialNum=bitXor(specialNum,ch);
    }

    unsigned int outputVal=specialNum;

bitXor 只是做异或运算:

int bitXor(int a,int b)
{
    return (a & ~b) | (~a & b);
}

现在我想找到一种算法，可以在给定 outputVal 时生成“inputVal”。(生成的 inputVal 不一定与原始 inputVal 相同。这就是我想要的原因发现碰撞)。这意味着我需要找到一个算法来生成一个解决方案，当将其输入上述算法时，结果与指定的“outputVal”相同。要生成的解的长度应小于或等于32。

Answer 1

方法一:暴力破解。没什么大不了的，因为你的“specialNum”总是在一个 int 的范围内，所以在平均尝试了几十亿个输入值之后，你找到了正确的。应该在几秒钟内完成。

方法 2:蛮力，但很聪明。

考虑处理最后一个 ch 之前的 specialNum 值。您首先计算 (specialNum * 32) + (specialNum/4) + ch。由于 -128 <= ch < 128 或 0 <= ch < 256 取决于 char 的符号，您知道结果的最高 23 位，与 ch 无关。在将 ch 与 specialNum 进行异或后，您还知道最高 23 位(如果 ch 是有符号的，则最高 23 位有两个可能的值)。您检查这 23 位是否与所需的输出匹配，如果不匹配，您就一次性排除了 ch 的所有 256 个值。所以暴力法平均会在1600万步后结束。

现在考虑处理最后两个 ch 之前的 specialNum 值。同样，您可以在根本不检查最后两个字符的情况下确定结果的最高 14 位(如果 ch 有四种选择)。如果最高 14 位不匹配，您就完成了。

方法 3:这就是您的做法。依次考虑所有长度为 0、1、2 等的字符串 s(但是，您的算法很可能会更快地找到解决方案)。处理字符串 s 后计算 specialNum。按照您的算法，并允许对 char 进行签名，找到 specialNum 的最高 14 位在处理另外两个字符后可能具有的最多 4 个不同值。如果其中任何一个与所需的输出匹配，则在处理下一个字符的 256 个可能值中的每一个后检查 specialNum 的值，并在检查另一个字符后找出 specialNum 的最高 23 位可能具有的最多 2 个不同值。如果其中一个匹配所需输出的最高 23 位，则在处理完接下来的 256 个可能字符中的每一个字符后检查 specialNum 是什么，并寻找匹配项。

这应该在一毫秒内起作用。如果 char 是无符号的，则速度更快。