在python中反转hash()函数

Question

不确定这是否可行,但在python中有一个hash()函数,它接受一个字符串或一个整数,并生成该输入的[EDIT not-unique]整数表示.

我的问题是(在线搜索后),如何将生成的整数反转回原始字符串.

谢谢.

Answer 1

理论上你不能这样做,至少不是以有效的方式(读取:"在合理的时间内"),即使散列不是加密安全的.

现在,如果您的搜索空间足够小(例如,如果唯一可能的输入是1000个单词的列表),您可以预先计算所有可能哈希值(作为键)的排序表及其相应的输入并执行一O(log(n))上查找.

这当然会为您提供可能结果的列表,因为哈希不是唯一的.现在,再次,如果您的搜索空间足够小,您可能只对每个输入都有唯一的结果.但除非我们对您的数据来源有更多了解,否则我们无法确定它.

Answer 2

Python 中的内置函数hash主要用于散列集合中的键，例如dict和set。的唯一必需的属性，或多或少是，它比较了相等的对象必须有相同的散列值。

在 Python 的默认 CPython 实现中，对于str, bytesor类型的对象datetime，使用了一个难以反转的哈希函数（SipHash），而且自 Python 3.3 起使用哈希随机化来防止哈希泛滥攻击。这意味着哈希值会随着 Python 的调用而变化。因此，如果您尝试反转hash()以恢复具有该散列的字符串，请忘记它。

但是对于数值（包括int, float, Decimal, Fraction），自2010 年以来使用了一个简单而优雅的散列函数，该函数具有以下特性：对于相等的数值，即使它们属于不同类型（如and和and and ），它们的散列也是相等的。使用的函数如下（暂时忽略负数）：4242.0Decimal('42')Fraction(42, 1)complex(42, 0)

• 对于整数 n，散列简单地由hash(n) = n mod P 给出，其中 P 是sys.hash_info.modulus= 2 ⁶¹ - 1，一个大素数。

• 这被推广到所有有限有理数如下：对于有理数 n = p/q，散列是hash(p/q) = (p/q) mod P，除法被解释为模 P。换句话说，如果 p/q 是最低形式（或者至少，去除了 P 的公因数），那么 hash(p/q) 是通过计算 q mod P 的倒数，乘以 p，然后取模 P 得到的.

• 对于负数，hash(-n) = -hash(n)。

（有一些关于特殊值的更多细节：如果 n 是浮点无穷大，或者如果 q 没有逆，即是 P 的倍数，则sys.hash_info.inf使用，如果 n 是NaN，则sys.hash_info.nan使用。还有散列值永远不会是 -1。）

这使得反转这个hash函数成为一个很好的练习。对于给定的非负值 h，其中 0 ？h < P,

• 整数 n 具有 hash(n) = h 当且仅当 n mod P 是 h，即如果 n 对于某个整数 k 具有 (h + kP) 的形式。

• 具有 52 个尾数位 m 和 11 个指数位 e的（IEEE 754 双精度）浮点数表示有理数

  (2 ⁵² + m)/2 ⁵² × 2 ^e-1023

  所以如果它的哈希是 h，那么我们有同余条件：

  (2 ⁵² + 米) (2 ^e-1023-52 ) ? 高模P

  (2 ⁵² + 米) ? ((2 ^1023+52-e ) × h) 模 P

  米？(2 ^1023+52-e × h - 2 ⁵² ) 模 P

  对 m 的唯一约束是 0 ？米 < 2 ⁵²。因此，对于e的 2 ¹¹ = 2048 个可能值中的每一个，我们可以计算相应的 m 并验证它是否导致有效的浮点数。

因此，这里是一个（Python 3中）函数，对于给定h的产率都int和浮点值n，使得hash(n)是h。

import sys

def invert(h):
    if h == -1: return []  # -1 gets coerced to -2 so no value has hash -1
    if h < 0:
        sign = -1
        h = -h
    else:
        sign = 1
    M = sys.float_info.mant_dig - 1  # = 52 = Bits available for mantissa
    E = (sys.float_info.max_exp - sys.float_info.min_exp + 1)  # = 1023 = bias
    B = sys.float_info.radix  # = 2, base of the floating point values
    P = sys.hash_info.modulus  # = 2^61 - 1 = the prime used as hash modulus
    if not (0 <= h == int(h) < P):
        return []
    for e in range((E + 1) * 2):
        # Want m such that (B^M + m) * B^(e-M-E) = h mod P
        m = (h * B**(M+E-e) - B**M) % P
        if m >= B**M: continue  # Happens with probability (1-B**M/P)
        f = (B**M + m) * B**(e-M-E)
        if f == int(f): continue  # We'll see this later as an integer
        assert hash(f) == h
        yield sign * f
    # Special values if any
    if h == sys.hash_info.inf:
        yield sign * float('inf')
    if h == sys.hash_info.nan:
        yield float('nan')
    # Now the integers
    k = 0
    while True:
        yield sign * (h + k * P)
        k += 1

用法示例：

num = 0
for n in invert(314159265):
    print(hash(n), n)
    num += 1
    if num > 25: break

输出：

314159265 2.1332628416727795e-304
314159265 4.918969210286518e-286
314159265 1.1342370766076572e-267
314159265 2.6153726338867434e-249
314159265 6.030638704336553e-231
314159265 1.390570609748797e-212
314159265 3.2064375193072873e-194
314159265 7.393541538375207e-176
314159265 1.7048346069593532e-157
314159265 3.9310809603228e-139
314159265 9.064455551013383e-121
314159265 2.0901211464632472e-102
314159265 4.81949123398199e-84
314159265 1.111299016984405e-65
314159265 2.5624810694595406e-47
314159265 5.908679060255712e-29
314159265 1.3624486304777972e-10
314159265 314159265
314159265 2305843009527853216
314159265 4611686018741547167
314159265 6917529027955241118
314159265 9223372037168935069
314159265 11529215046382629020
314159265 13835058055596322971
314159265 16140901064810016922
314159265 18446744074023710873

等等。

Answer 3

你可以\xe2\x80\x99t，并且它\xe2\x80\x99s不是唯一的。这\xe2\x80\x99s使它成为一个散列。从help(hash)：

\n\n

\n

返回对象的哈希值。具有相同值的两个对象具有相同的哈希值。相反的情况不一定成立，但有可能成立。

\n

\n\n

所以这一般来说是不可能的。您可以检查某个列表是否有匹配的哈希值，但您永远无法确定它是原始列表，除非您知道原始列表位于某个集合中并且\xe2\x80\x99t 与该集合中的另一个项目没有冲突。

\n

Answer 4

即使你可以反转它，逆哈希函数（通常）也不会是唯一的。例如，有无限数量的字符串，从中生成哈希键到有限的整数范围，该范围受计算机上的字大小限制。