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 桁の数字のハッシュ自体が 1,000 万分の 1 の確率であると推測できます。これは本当に 5 回目の反復で発生したのでしょうか、それとも私の設定に何か問題があるのでしょうか? さらに重要なことに、ハッシュに重大な影響を与える可能性のある他の同様のエラーがある可能性はありますか?

ありがとう。

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 の範囲内にあると推測することは安全です。和のエントロピーについて。

加算によって情報が破棄された後、アルゴリズムは和 modulo を取ります52665。52665 を法とする可能な数は 52665 しかないため、このコードは最高の状況で 52665 ハッシュしか生成できません。

そして...これを行う理由はありません! ランダム コードは乱数を作成しません。良いハッシュ関数を作るのは難しいです。いくつかのコードをハッキングして物事を切り刻むことによって、ハッシュを改善するつもりはありません。それどころか、ランダム性のソースを破壊する可能性があります。ランダムなハッシュが必要な場合は、他の誰かが書いたものを使用してください。

たとえば、MD5 と言います。

于 2012-11-06T03:19:58.537 に答える
0

md.update 呼び出しを実行する前に、アルゴリズムは間違いなくすべてのステップを通過しています。

乱数を選択していないことに注意してください。事実上、アルゴリズムを繰り返し適用して、わずか数回の反復で到達した入力値のアトラクタである固定点を見つけるかどうかをテストしています。

いくつかの 1 桁の文字列をテストした後、別の固定小数点アトラクタを見つけました。

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

使用する予定の入力の種類を使用して、結果をアルゴリズムにフィードバックせずに、さらにテストを行うことをお勧めします。適切な特性を持つ数百万のランダムな文字列を実行し、いくつかの値が他の値よりも多く表示されるかどうかを確認します。

于 2012-11-06T03:24:08.437 に答える