6

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

我的问题是（在网上搜索后），如何将生成的整数反转回原始字符串。

谢谢。

4

7 回答 7

9

理论上你不能这样做，至少不能以一种有效的方式（阅读：“在合理的时间内”），即使哈希不是加密安全的。

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

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

于 2013-06-30T19:14:48.897 回答
7

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

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

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

  • 对于整数 n，哈希由hash(n) = n mod P给出，其中 P sys.hash_info.modulus= 2 61 - 1，一个大素数。

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

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

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

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

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

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

    (2 52 + m)/2 52 × 2 e-1023

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

    (2 52 + m) (2 e-1023-52 ) ≡ h mod P

    (2 52 + m) ≡ ((2 1023+52-e ) × h) mod P

    m ≡ (2 1023+52-e × h - 2 52 ) 模 P

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

所以这里是一个（Python 3）函数，它对于给定的h产生所有 int 和 float 值，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

等等

于 2019-05-22T01:39:25.770 回答
5

你不能，而且它不是独一无二的。这就是使它成为hash的原因。来自help(hash)：

返回对象的哈希值。具有相同值的两个对象具有相同的哈希值。反过来不一定正确，但很可能。

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

于 2013-06-30T19:13:03.153 回答
1

即使您可以反转它，逆散列函数（通常）也不会是唯一的。例如，有无限数量的字符串，从这些字符串中生成哈希键到一个有限的整数范围内，该范围受您机器上的字长限制。

于 2013-06-30T19:12:36.400 回答
0

人们遗漏的另一点不仅是很难找到与哈希匹配的字符串，而且那里没有足够的信息来确定字符串是什么。

散列（通常）是一种将给定输入转换为不可逆整数的加密方式。但是，哈希可能会发生冲突或碰撞，这在 MD5 中是可能的。因此，在这样的散列函数下，可以散列到相同数字的不同字符串的数量是无限的——所以即使可以反转（它不是），你仍然不会知道哪个字符串是原始的！

于 2013-07-01T06:35:55.543 回答
0

散列的计算成本很高，难以逆转。通常，“反转”它们的唯一方法是暴力破解用于生成输出的输入。

于 2013-06-30T20:20:29.263 回答
0

反函数为：

def inverse_hash(target):
    return target - 2*(target-hash(target))*(hash(target+1)-hash(target))

我认为使用( x_(n+1) = x_n - delta_x*(df/dx) )带有负平方的梯度下降算法method( minimize (target-f(x))^2 )。因为 inhash(x) x是整数，dx并且delta_x都等于 1。（注：df/dx = lim(dx->0, (f(x+dx)-f(x))/dx )）。

于 2021-11-14T12:20:56.110 回答