Python 中的 Murmur Hash 3

Question

我正在尝试在 python 中实现 murmur hash 3 。我对这个功能感到困惑

mmh3.hash_bytes(key)

。

这是我尝试过的代码：

a = bitarray()
print(mmh3.hash('A')) # output is 1423767502 a hash value 

接下来，我又尝试了一项功能

print(mmh3.hash_bytes('A')) 
# output is b'z\xb1)\x9a\xb7\xc2_\x037\x99\xddF\x9c\xf2}8'

mmh3.hash_bytes('A') 的输出让我感到困惑。两个函数不应该具有相同的值吗？因为两者的哈希值都是'A'。如果我错了请纠正我。

Answer 1

来自在线文档：

mmh3.hash("foo") # returns a 32-bit signed int

[...]

mmh3.hash_bytes("foo") # 128 bit value as bytes

维基百科也说了同样的话：

当前版本是 MurmurHash3，它产生 32 位或 128 位哈希值。

这在 C++ 实现的 头文件中也有明确说明 :

void MurmurHash3_x86_32  ( const void * key, Py_ssize_t len, uint32_t seed, void * out );

void MurmurHash3_x86_128 ( const void * key, Py_ssize_t len, uint32_t seed, void * out );

验证不同的测试也是如此（1，2）：

assert mmh3.hash("foo") == -156908512

[...]

assert mmh3.hash_bytes("foo") == b"aE\xf5\x01W\x86q\xe2\x87}\xba+\xe4\x87\xaf~"

所以我承认，同一个哈希函数返回两个不同的结果可能会令人惊讶，但实际上它并不是完全相同的哈希函数。

Answer 2

它们不同的原因在现代密码学中很简单；域分离，以便对 MurmurHash 的不同大小的调用（SHA2 有它，SHA3 派生也有它）将输出不同的值。这可能会防止加密情况下的某些攻击（MurmurHash 不是加密哈希）或有助于在某些攻击中分散表...

从散列到椭圆曲线的一个很好的定义

经常分析使用随机预言的加密协议
假设随机预言机只回答查询
由该协议生成。实际上，这个假设并不成立
如果两个协议查询同一个随机预言机，则成立。具体来说，
考虑查询随机预言机 R 的协议 P1 和 P2：如果 P1 和 P2 都在相同的值x上查询R，一或
的安全分析 两种协议都可能失效。

解决此问题的常用方法称为域
分离，允许单个随机预言机模拟多个， 独立的预言机。这是通过确保每个
模拟预言机看到的查询与
看到的查询不同 所有其他模拟预言机。例如，模拟两个oracle R1 R2 给定一个预言机 R，可以定义

R1(x) := R("R1" || x) R2(x) := R("R2" || x)

在本例中，“R1”和“R2”称为域分隔标签；
它们确保对 R1 和 R2 的查询不会产生相同的结果
查询 R。因此，将 R1 和 R2 视为独立是安全的
神谕。

如果我们查看 Wikipedia 中的代码示例，我们将看到这一行；

hash ← hash XOR len

即将所需长度 (

len

) 合并到 MurmurHash 中，以便值会发生变化，而不是简单地截断 128 位输出。

Answer 3

我认为您遇到的困惑是由于 mmh3 库中

mmh3.hash()

和

mmh3.hash_bytes()

函数的输出差异造成的。

mmh3.hash()

函数返回 32 位有符号整数哈希值，而

mmh3.hash_bytes()

函数以字节字符串形式返回哈希值。 在您的示例中，

mmh3.hash('A')

返回哈希值 1423767502，它是一个 32 位有符号整数。 另一方面，

mmh3.hash_bytes('A')

返回字节字符串 b'z\xb1)\x9a\xb7\xc2_\x037\x99\xddF\x9c\xf2}8'。该字节字符串表示相同的哈希值，但格式不同。 要比较两个输出，您可以使用

int.from_bytes()

将字节字符串转换为整数

import mmh3
hash_value = mmh3.hash('A')
print(hash_value)  # Output: 1423767502

byte_string = mmh3.hash_bytes('A')
hash_value_from_bytes = int.from_bytes(byte_string, byteorder='big', signed=False)
print(hash_value_from_bytes)  # Output: 1423767502