4

個人の個人情報、特に名前、生年月日、性別、人種を比較しています。この情報をすべて含む文字列をハッシュし、ハッシュ オブジェクトの 16 進ダイジェストを比較しています。これにより、データベースの主キーとして使用している 32 桁の 16 進数が生成されます。たとえば、識別文字列を使用すると、次のようになります。

>> import hashlib
>> id_string = "BrianPeterson08041993MW"
>> byte_string = id_string.encode('utf-8')
>> hash_id = hashlib.md5(bytesring).hexdigest()
>> print(hash_id)
'3b807ad8a8b3a3569f098a575091bc79'

この時点で、衝突の危険性を確認しようとしています。私の理解では、少なくとも比較的小さい文字列 (長さは約 20 ～ 40 文字) については、MD5 には重大な衝突のリスクはありません。ただし、128 ビットのダイジェスト オブジェクトではなく、32 桁の 16 進数のダイジェストを使用しています。

さて、16 進ダイジェストはダイジェストを圧縮したもの (つまり、より少ない文字数で格納されている) だと思います。それとも私は基地外ですか？

4

2 に答える 2

5

さて、16 進ダイジェストはダイジェストを圧縮したもの (つまり、より少ない文字数で格納されている) だと思います。それとも私は基地外ですか？

[...]

私の質問は次のとおりだと思います:表現を行うために使用する情報の単位数と、元のメッセージがエンコードするのに必要な情報の単位数に基づいて、表現が異なると、一意ではない可能性が異なるのではないでしょうか? もしそうなら、使用するのに最適な表現は何ですか? ええと、あなたの次の答えを前置きさせてください: 私が 10 歳のように私に話してください

古い質問ですが、はい、いわばベースから少し外れていました。

重要なのは、プレゼンテーションの長さではなく、ランダム ビットの数です。

ダイジェストは単なる数字、整数であり、異なる数の異なる数字を使用して文字列に変換できます。たとえば、いくつかの異なる基数で示される 128 ビットの数値:

"340106575100070649932820283680426757569" (base 10)
"ffde24cb47ecbff8d6e461a67c930dc1" (base 16, hexadecimal)
"7vroicmhvcnvsddp31kpu963e1" (base 32)

短いほど (認証トークンなどで) 便利で便利ですが、各表現にはまったく同じ情報と衝突の可能性があります。同じものをエンコードしながら、「55」が「110111」よりも短いのと同じ理由で、より短い表現はより短くなります。

この回答は、次のようなコードをいじるだけでなく、物事を明確にすることもできます。

new BigInteger("340106575100070649932820283680426757569").toString(2)

...または他の言語 (上記の Java/Scala) で同等のもの。

より実用的なレベルでは、

[...] データベースの主キーとして使用しています

通常の自動インクリメントされた id 列 ( MySQL、PostgreSQL)を使用して衝突の可能性を排除しない理由がわかりません。BIGINT AUTO_INCREMENTBIGSERIAL

于 2015-12-20T02:55:02.210 に答える
2

短縮された 32 ビットの 16 進ダイジェスト (16 進数の 8 文字) では、衝突のないユーザー データベースを効果的に保証するのに十分な長さではありません。

誕生日の衝突確率の式は次のとおりです。

2^32 セットの文字列を渡した場合、md5 衝突の確率はどのくらいですか?

32 ビット キーを使用すると、約 10,000 ユーザーでソフトウェアが壊れ始めることになります。 衝突確率は約 1% です。 その後、非常に急速に悪化します。100,000 ユーザーでは、衝突確率は 69% です。

64 ビット キーと 100 億人のユーザーは、約 2.7% の衝突率の別の限界点です。

1,000 億人のユーザー (予見可能な将来の地球人口の寛大な上限) にとって、96 ビット キーは少し危険だと思います。衝突の可能性は約 1 億分の 1 です。実際には、約 1X10^-17 の衝突率 を与える 128 ビットのキーが必要です。

128 ビット キーの長さは 128/4 = 32 の 16 進文字です。審美的な目的で短いキーを使用する場合は、128 ビットを超える 23 文字の英数字を使用する必要があります。または、印刷可能な文字 (ASCII 32-126) を使用する場合は、20 文字で済む可能性があります。

したがって、ユーザーについて話している場合、衝突のないランダム キー、または 20 ～ 32 文字の長さの文字列、または 128/8 = 16 バイトのバイナリ表現には、少なくとも 128 ビットが必要です。

于 2015-07-02T02:36:48.063 に答える