是否有一个哈希值等于其自身的字符串？

hash(x) = x

#1 楼

我将散列函数$ H $限制为具有固定大小$ n \ ge1 $位的输出，接受一些字符串作为输入，包括所有$ n $位字符串； MD5（分别为SHA-1，SHA-256）是$ n = 128 $（分别为$ n = 160 $，$ n = 256 $）这种功能的示例。
是否存在解决方案$ H（x）= x $取决于特定的哈希函数。如果$ H $是随机函数（如MD5，SHA-1和SHA-256的目标），则答案为是，对于$ n $的实际值，赔率在$ 63.2 \％$旁边。
更多恰好：仅当$ x $具有确切的$ n $位时，$ H（x）= x $才​​能成立。 $ x $的$ 2 ^ n $个值可以满足后面的条件，而将$ H $限制为这样的$ x $，则有$（2 ^ n）^ {（2 ^ n）} $个不同的$ H $函数，其中$（2 ^ n-1）^ {（2 ^ n）} $使得$ H（x）= x $没有解。因此，如果我们均匀地随机选择一个$ H $，则赔率恰好是$ 1-{（2 ^ n-1）^ {（2 ^ n）} \ over（2 ^ n）^ {（2 ^ n）}} =我们选择$ H $的1-（1-2 ^ {-n}）^ {（2 ^ n）} $使得$ H（x）= x $具有解。随着$ n $的增加，其收敛速度非常快，达到$ 1-1 / e \ approx0.632 $（其中$ e \ approx2.718 $是自然对数的底）。
这不能告诉MD5是否具有存在$ \ operatorname {MD5}（x）= x $（这将是一个128位位串$ x $）的解决方案的属性。我们能说的最好的是，它可能成立，赔率大约为63％，但确定断言是对还是错超出了我们当前的计算能力（我们拥有的最佳方法是穷举搜索，如果答案是否定的，则为无穷大）。将需要$ 2 ^ {128} $的哈希值；否则，仍可能需要超过$ 2 ^ {126} $的哈希值，这是无法实现的。）
PHP特有的：如果md5($string) === $string有某种解决方案，那将是32 -十六进制小写字符的字符串；我们没有像上面那样散列相同的$ 2 ^ {128} $个候选对象，因此问题并不相同，但是推理可以改编，同样，我们可以说的最好的是，很可能有一个解决方案，几率约为63％ 。
此外，原始问题询问是否存在诸如md5($string) == $string这样的字符串。为了回答这个问题，我们必须考虑到==运算符由于杂耍而在PHP中的工作方式（它拥有"0042" == "42"和"20e2" == " +002000"）。极有可能有一个解决方案（只需考虑在$ 200的{2 ^ {200} $字符串中包含200个空格或制表符以及一个额外的最终0，我们期望对$ "00000000000000000000000000000000"之一进行散列$ 31 \ cdot2 ^ {72} $哈希，"000000000000000000000000000000e0" .. "0e000000000000000000000000000000"）;但是我们不能展示一个。

定义散列函数$ H $很容易，使得$ H（x）= x $没有解决方案：例如，定义
$ $ H（x）= \ begin {cases} x \ oplus1＆\ text {if} \ operatorname {MD5}（x）= x \\\ operatorname {MD5}（x）＆\ text {otherwise} \ end {cases} $$

定义哈希函数$ H $也很容易，这样$ H（x）= x $至少具有一个解决方案：例如，选择一些任意的128位常量，例如$ k = \ text {af5d2bc6c9181f76f3161f43f41f6aeb} $，并定义
$$ H（x）= \ begin {cases} k＆\ text {if} x = k \\\ operatorname {MD5}（x）＆\ text {否则} \ end {cases} $$

不能有$ x $使得所有可能的散列函数$ H $，$ H（x）= x $。
证明矛盾：假设有这样的$ x $，函数$ H $具有$ x $具有该属性，并考虑由$ \ tilde H（x）= H（x）\ oplus1 $定义的函数$ \ tilde H $。

#2 楼

是的，您可以创建许多这样的功能。
例如，让我们基于SHA512构建这样的功能。生成一些随机值$ m_0 $并生成一个哈希值。这很重要，因为不能保证每个512位数字都有一个前映像。因此，让$ h_0 = \ operatorname {SHA512}（m_0）$。生成哈希后，将$ m_0 $丢掉。从技术上讲，您可以按照以下步骤进行操作。创建一个生成$ m_0 $作为流的程序。它应该生成一个64字节的随机值块，进行哈希处理，用一个新块覆盖这64字节，进行哈希处理等。因此，该程序在任何时候都不会具有$ m_0 $的完整值。 br />现在计算其哈希值：$ h_1 = \ operatorname {SHA512}（h_0）$。 $ h_1 $非常有可能与$ h_0 $不同。
现在定义新的哈希函数，如下所示：
\ begin {align} \ operatorname {hash}（x）＆=（\ operatorname { SHA512}（x）+ h_0-h_1 + 2 ^ {512}）\ bmod 2 ^ {512} \ end {align}
为$ h_0 $计算此哈希函数：
\ begin {align} \ operatorname {hash}（h_0）＆=（\ operatorname {SHA512}（h_0）+ h_0-h_1 + 2 ^ {512}）\ bmod 2 ^ {512} \\＆=（h_1 + h_0-h_1 + 2 ^ {512}）\ bmod 2 ^ {512} \\＆=（h_0 + 2 ^ {512}）\ bmod 2 ^ {512} \\＆= h_0 \ end {align}
因此\ begin {align } \ operatorname {hash}（h_0）= h_0 \ end {align}
我们的变换实际上是旋转一个512位数字。此操作不会更改密码属性。这意味着我们的哈希函数的加密属性与SHA512相同：


图像前电阻：除了单个值$ h_0 $是其自身的图像前，对于任何其他值，找到原始图像的难度与对SHA512一样困难

第二个原始图像电阻：对于任何输入和哈希，寻找给出相同哈希的另一输入的复杂性适用于SHA512。这也适用于$ h_0 $，因为我们不知道什么是$ m_0 $。

防冲突性：对于其他任何哈希，查找冲突的复杂性与SHA512的复杂性相同。 $ h_0 $也是如此，因为我们不知道什么是$ m_0 $。

这样，您可以创建具有其他固定点的其他哈希函数。

#3 楼

这是不可能的，因为MD5算法使位旋转了$ s $个位，其中每个操作的$ s $有所不同。因此，字符串的MD5永远不能是同一字符串。

请参阅Wikipedia的MD5文章的“算法”部分。

每种哈希算法都以分组密码为基础，并且字节移位是核心部分。因此，纯文本$ m $不可能等于密文$ c $。

#4 楼

根据您的要求使用任何哈希函数：

不。

如果您编写一个哈希函数，它以某种方式计算哈希值，然后在结果中附加一个t（因为您喜欢字母），那么无论您输入的字符串是什么，

对于特定的哈希函数：

当然可以；尤其是对于像“字符串的前三个字母”这样的“坏”哈希函数。


由于澄清（请参见注释）指出，该问题仅针对成熟的哈希函数，请有关MD5的详细信息，请参阅user2351586的答案。