djb2的逆向算法

字数 382，阅读大约需 2 分钟

djb2算法介绍

DJB2 算法是一种常用的哈希函数算法，由 Dan Bernstein（德克斯特・科曾和道格拉斯・琼斯）在 20 世纪 90 年代初期开发。该算法以其简单高效、分布均匀的特点，在字符串哈希场景中得到广泛应用，常用于哈希表、数据校验和等领域。

核心思想

通过将字符串的每个字符与一个特定的基数（通常为 33）进行运算，并不断累加哈希值，最终生成一个哈希结果。这种设计使得字符的顺序和内容都能影响哈希值，从而减少哈希冲突的概率。

算法公式

对于字符串 s = s₀s₁s₂...sₙ₋₁，哈希值计算方式为：

hash = 5381
for 每个字符c in 字符串s:
    hash = ((hash << 5) + hash) + c  # 等价于 hash * 33 + c
return hash

逆向djb2算法的局限性

djb2是一种hash值算法，将算法反过来计算原字符串，会出现一个hash对应多个字符串的情况。

python代码

# 计算出的第一个满足hash值的字符串
defreverse_djb2_min_length(target_hash, min_len=0x1, max_len=20, charset="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"):
defhelper(current_hash, depth_left):
if depth_left == 0:
returnNone
for c in charset:
            val = current_hash - ord(c)
if val % 33 != 0:
continue
            prev_hash = val // 33
if prev_hash == 5381and depth_left == 1:
return c
            sub = helper(prev_hash, depth_left - 1)
if sub:
return sub + c
returnNone

for length inrange(min_len, max_len + 1):
        result = helper(target_hash, length)
if result:
return result
returnNone


# 结果：hello
reversed_string = reverse_djb2_min_length(0x310f923099)
print(len(reversed_string))