3

我制作了一个使用 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 位数字的哈希值本身有大约千万分之一的机会。这真的只发生在第五次迭代中，还是我的设置有问题？更重要的是，是否还有其他类似的错误会对我的哈希产生严重影响？

谢谢。

4

2 回答 2

8

代码的“随机”部分弊大于利。

首先，代码将几个不相关的数字相加：

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！

于 2012-11-06T03:19:58.537 回答
0

在进行 md.update 调用之前，该算法肯定会经历所有步骤。

请注意，您不是在选择随机数。实际上，您正在测试您的算法是否在重复应用下找到了一个固定点，该固定点是您的输入值的吸引子，仅在几次迭代中就达到了。

在测试了几个一位数字字符串后，我发现了另一个定点吸引子：

hash("3") = "3147559"
hash("3147559") = "1874964"
hash("1874964") = "1874964"

我建议进行更多测试，使用您打算使用它的输入类型，并且不将结果反馈给算法。运行几百万个具有适当特征的随机字符串，看看某些值是否比其他值显示得更多。

于 2012-11-06T03:24:08.437 回答