python – 如何计算我需要多少哈希才能找到碰撞？
|
我正在开发一个程序,使用十六进制字符将图像URL散列为10个字符的字符串,例如64fd54ad29.
它是用Python编写的,哈希的计算如下： def hash_short(self,url):
return hashlib.sha1(url).hexdigest()[:10]
我担心与这么短的哈希冲突.我预计在大约一百万次哈希之后会发生碰撞,但是当我遇到蛮力时我需要一千万次哈希. 计算 十六进制数字有16个可能的值,或2 ^ 4.有十个字符,我有2 ^ 40种可能性,或40位熵. 为了得到1的概率,我们需要查看2 ^ 40 1个URL(通过鸽子原理),但我们会更快地发现碰撞. n位散列的生日攻击(即暴力)将在2 ^(n / 2)次尝试后发现冲突.因此,我们会看到大约2 ^ 20个URL后的冲突,即1,048,576. 蛮力 我写了一个简单的Python脚本,迭代了很长的URL列表,并将每个哈希值与我之前看到的哈希值进行了比较.我花了10,800,000个网址才找到我的第一次碰撞：“http://c69025.r25.cf3.rackcdn.com/_image1/_Model/34897.jpg”和“http://media.editd.com/assets/matrix/ full / 72f9a997b67c65c66f4adc769ee0a127d1db25eb.jpg“都哈希到”ba2be44bd1“. import hashlib
import json
def calculate_short_hash(url):
return hashlib.sha1(url).hexdigest()[:10]
def url_from_json(json_string):
return json.loads(json_string)['image_url']
if __name__ == '__main__':
short_hashes = set()
for i,line in enumerate(open('urls.all')):
short_hash = calculate_short_hash(url_from_json(line))
if short_hash in short_hashes:
print "Already seen: %s" % short_hash
break
else:
short_hashes.add(short_hash)
if i % 100000 == 0:
print "Processed %d lines" % (i,)
摘要 要么我的数学不正确,要么我非常不走运.这是什么？我多么不走运？ 解决方法
我认为您的碰撞检测代码是错误的：
import hashlib
import random
import string
def hash_short(url):
return hashlib.sha1(url).hexdigest()[:10]
hashes = dict()
while True:
if len(hashes) % 10000 == 0:
print len(hashes)
newurl = ''.join(random.choice(string.lowercase) for _ in xrange(30))
newhash = hash_short(newurl)
if newhash in hashes and newurl != hashes[newhash]:
print 'found a collision!'
print newhash
print newurl
print hashes[newhash]
print len(hashes)
break
hashes[newhash] = newurl
输出(运行一次)： ... 770000 780000 found a collision! 216be03ec7 txnbkwrfkpkmiexloxrifdsnjumkex xlnmlhobtsswjvmqnjupaybkspptpo 780758 显然我的所谓的url不是,但是这应该与一个好的哈希函数没有区别(并且SHA1有利于此目的).如果你发现一个数据集在SHA1的前5个字节上确实具有异常低的冲突率,那么做得好！用最后5个字节再试一次:-) 你有点不走运？当你有1000万个哈希时,你的2 ** 40空间已经满了大约100k的一个部分.所以没有碰撞的概率大致是(手指在空中),(99999.0 / 100000)** 1000万,即3.7e-44.因此,如果我的数学是正确的[编辑：它不是,请参阅评论]你是天文数字,被定罪 – 超出合理怀疑不幸. 作为偶然发生碰撞概率的保守上限,在已经有100万个哈希值发挥作用后,你做了900万次试验.没有碰撞的概率严格小于(999999.0 / 1000000)** 9000000,仅为0.0001.你可以通过进一步分割它来产生更小的界限：你进行了100万次试验,占用了900万个哈希值.或者你可以准确地计算概率(CodesInChaos做了：1e-20) 所以,贝叶斯统计数据就是这样,我估计你的代码中的错误概率高于所有这些数字,甚至是真正大的保守界限:-) （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |