哈希算法中真的很奇怪的碰撞:巧合还是错误？

Question

我做了一个哈希算法,它使用MD5进行一些低安全性密钥生成.基本上,它采用字符串的字符并对其索引产品求和,然后在MD5之前采用随机数的模数.在Java中:

BigInteger bi = BigInteger.ZERO;
char[] array = input.toCharArray();
for (int i = 0; i < array.length; i++) {
    bi = bi.add(BigInteger.valueOf(i + 1).multiply(
            BigInteger.valueOf(array[i])));
}
final int moduloOperator = 52665; // random constant
final byte[] moduloResult = bi.remainder(
        BigInteger.valueOf(moduloOperator)).toByteArray();
MessageDigest md;
try {
    md = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException nsae) {
    nsae.printStackTrace();
    return null;
}
md.update(moduloResult);
return new BigInteger(1, md.digest()).toString().substring(0, 7);

我最后有子串,因为它需要易于阅读.

乍一看,它按预期工作:不同的输入提供不同的输出,但结果在运行中是一致的.

但是,在玩一下时,我注意到以下几点:

hash("")        = "1963546"
hash("1963546") = "1322048"
hash("1322048") = "2101764"
hash("2101764") = "3234562"

到目前为止看起来很好 适当随机.但是之后:

hash("3234562") = "3234562"
hash("3234562") = "3234562" [etc.]

这让我目瞪口呆.我猜想7位数的散列本身就有大概有千分之一的机会.这真的只发生在第五次迭代,或者我的设置有问题吗？更重要的是,是否还有其他类似的错误会对我的哈希产生严重影响？

谢谢.

Answer 1

代码中的"随机"部分弊大于利.

首先,代码将几个不相关的数字加在一起:

for (int i = 0; i < array.length; i++) {
bi = bi.add(BigInteger.valueOf(i + 1).multiply(
        BigInteger.valueOf(array[i])));
}

让我们看看"2101764"和"3234562"的结果.我将使用Python简洁.

In [0]: sum((i+1)*int(digit) for (i, digit) in enumerate("3234562"))
Out[0]: 107

In [1]: sum((i+1)*int(digit) for (i, digit) in enumerate("2101764"))
Out[1]: 107

好吧,这是你的问题.

还记得中心极限定理吗？随机数的总和比单个数字本身更容易预测.信封背面,对于7位数输入,总和的分布方差为13.16,平均值为115.5.可以安全地推断,至少所有60%的金额都在50个数字范围内,95%的金额在100个数字范围内,所有金额都在189个数字范围内 - 如果有的话,我认为这是慷慨的关于总和的熵.

在通过添加破坏信息之后,算法采用模求和52665.只有52665个可能的数字模52665,所以这个代码在最好的情况下只能产生52665个哈希值.

并且......没有理由做任何这个! 随机代码不会产生随机数.制作好的哈希函数很难.你不会通过破解一些代码来切片和切块来改进散列.相反,你可能会破坏随机性的来源.如果您想要随机哈希,请使用其他人编写的哈希值.

比方说,MD5!