如何找到玩具哈希函数的冲突？
如何找到玩具哈希函数的冲突？
提问于 2016-04-12 11:00:02
我想为下面的一个简单哈希函数(Python)找到一个冲突：
def hash_function(s=''): # 'Hello World!' -> 7b2ea1ba
a, b, c, d = 0xa0, 0xb1, 0x11, 0x4d
result_hash = ''
for byte in bytes(s, 'ascii'):
a ^= byte
b = b ^ a ^ 0x55
c = b ^ 0x94
d = c ^ byte ^ 0x74
for i in [d, c, a, b]:
tmp = str(hex(i))[2:]
result_hash += tmp if len(tmp) is 2 else '0' + tmp
return result_hash这里还有一个js实现在jsbin
我已经找到了关于这样的问题，但我并不完全理解那里的答案。
函数输出的长度总是等于8。a、b、c和d变量是整数，在结束时转换为十六进制值，以形成结果散列，即123 -> 7b、46 -> 2e、13 -> 0d等。
所以，你能帮我找出那个函数的碰撞吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-04-12 12:07:13
查找具有相同散列的字符串对的一个简单方法是生成随机字符串，散列并将结果存储在dict中，使用哈希作为键，字符串作为值。如果您得到一个已经在dict中的散列，请打印它。
我稍微优化了您的hash_function，并使代码Python2/3兼容。
from __future__ import print_function
from random import choice, randrange, seed
def hash_function(s=''): # 'Hello World!' -> 7b2ea1ba
a, b, c, d = 0xa0, 0xb1, 0x11, 0x4d
for byte in bytearray(s):
a ^= byte
b = b ^ a ^ 0x55
c = b ^ 0x94
d = c ^ byte ^ 0x74
return format(d<<24 | c<<16 | a<<8 | b, '08x')
s = b'Hello World!'
print(s, hash_function(s))
#ASCII chars that print nicely
ascii = b''.join([chr(i) for i in range(33, 127)])
seed(37)
found = {}
for j in range(5000):
#Build a random 4 byte random string
s = b''.join([choice(ascii) for _ in range(4)])
h = hash_function(s)
if h in found:
v = found[h]
if v == s:
#Same hash, but from the same source string
continue
print(h, found[h], s)
found[h] = s输出
Hello World! 7b2ea1ba
0944dbd0 TXN9 YXC9
105a9dce wA5> rA0>
7a29e4bd %+m' -+e'
7776b2e2 u&4u n&/u
7c3ea3aa D-\6 z-b6
6d46d1d2 `<r_ "<0_
6a26e0b2 ;;x8 ";a8
1033eda7 ,AwW =AfW
627395e7 #3@e ;3Xe
7d6ee7fa D,Hg `,lg
3c2bb2bf NmRc Cm_c
1e31b9a5 nOc[ oOb[
1a49f7dd MKv' ]Kf'
161beb8f )G\y IG<y
0247bbd3 !SX1 VS/1页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36571298
复制相关文章
相似问题
腾讯云开发者
