加密算法有多少抗碰撞能力？

Question

给定一个由对称或非对称加密算法生成的密文，它工作在一个明文/密钥对上，找到另一个明文/密钥对以产生相同的密文有多难？

同时，找到两个明文/密钥对以产生相同的密文有多难？

引发这个问题的原因是另一个问题，可能与上述问题无关：

如果你有一个密文和一个密钥，并想使用某些解密例程进行解密，该例程通常会告诉你密钥是否正确。但它是如何知道的呢？它是否寻找一些模式，表明解密成功？是否存在另一个密钥导致某个不同的明文，其中包含该模式，并且也被该例程报告为“有效”？

跟进问题启发了答案和评论：

如果允许的明文/密钥对在以下一种或两种方式中受到限制：

1）明文以密钥的KCV（密钥检查值）开头。

2）明文以某些明文/密钥组合的哈希值开头。

这是否会使得碰撞查找变得不可行？是否清楚存在这样的明文/密钥？

- Johannes Gerer

---

这里有一些很棒的人回答你的问题，但是我通常会在涉及这类问题时押注于crypto。 - Maarten Bodewes

谢谢，我不知道那个网站！ - Johannes Gerer

不要使用KCV或明文/密钥组合的哈希值。这类方案的漏洞有大量的研究。应使用加密后身份认证方案，例如首先使用AES-CBC，然后使用HMAC-SHA256。 - Henrick Hellström

Answer 1

你的问题的答案如你所说，是没有任何碰撞防止措施。

对称情况下，假设您有一个明文PT，其长度是底层块密码的倍数。您生成一个随机IV，并使用密钥K、CBC模式和无填充加密明文。生成产生相同密文CT的明文PT'和密钥K'很容易。只需随机选择K'，使用密钥K'和IV解密CT，即可得到碰撞的PT'。

如果还使用填充，则会变得有些复杂，但仍然可能。如果使用PKCS#5/7填充，只需不断生成密钥，直到找到一个使得解密后的文本PT'的最后一个八位字节为0x01的密钥。这需要平均尝试128次。

为了使此类碰撞查找变得不可行，必须使用消息认证码（MAC）。

非对称情况下，RSA公钥加密也类似。如果您不使用填充（显然不推荐，可能甚至不受大多数加密库的支持），并使用公钥（N，E）将PT加密为CT，则只需生成第二个密钥对（N'，E'，D'），其中N'> N，那么PT'= CT^D'（mod N）将在（N'，E'）下加密为CT。

如果您正在为RSA加密使用PKCS#1 V1.5填充，则RSA私钥操作后最重要的八位字节必须为0x02，其概率约为256中的一次。此外，第一个值为0x00的八位字节不得早于索引9，这将以很高的概率发生（约为0,97）。因此，平均而言，您将需要生成大约264个相同位大小的随机RSA密钥对，然后才能找到其中一个可以为某些明文生成相同的密文。

如果您使用RSA-OAEP填充，则保证私钥解密会失败，除非密文是使用相应的公钥生成的。

- Henrick Hellström

---

升级了，现在考虑不对称的部分？ - Maarten Bodewes

@HenrickHellström：为什么是N'>N？ - Ashwin

@Ashwin：数学要求是N'>CT，但在这种情况下，预期的碰撞率会略微偏斜。我提到的条件只是为了举例说明。 - Henrick Hellström

Answer 2

如果您加密了一些明文（长度小于n），则有2^ n个唯一的输入字符串，每个字符串都必须产生一个唯一的密文（否则它将无法恢复）。因此，长度为n的所有可能字符串都是有效的密文。但这对于所有密钥都是正确的。因此，对于任何给定的密文，有2 ^ k种获得它的方法，每种方法具有不同的k长度密钥。

因此，回答您第一个问题：非常容易！只需选择任意密钥并“解密”密文。您将获得与密钥匹配的明文。

我不确定您所说的“例行程序通常会告诉您密钥是否正确”的含义。

- Oliver Charlesworth

---

你不可能比一个大小为n的密钥更好。 - UmNyobe

嗨Oli，我刚投了这个答案的赞，但别忘了Johannes是在问“给定（对称或非对称）加密算法”，这会使得答案变得有些复杂。填充也可能是一个问题。 - Maarten Bodewes

“例程通常会告诉您密钥是否正确”是指最终用户加密软件通常会告知用户提供的密钥是否正确。 - Johannes Gerer

Answer 3

检查密钥有效性的一种简单方法是在加密之前向明文添加已知部分。如果解密无法还原该部分，则不是正确的密钥。

已知部分不应该是常量，因为那将是一个即时 破译。但它可以是明文的哈希值；如果对解密后的文本进行哈希运算得到相同的哈希值，则该密钥可能是正确的（除了 哈希冲突 的情况）。

- Roland Smith

---

从您提供的维基百科页面中可以看出：“像高级加密标准这样的现代密码算法目前不容易受到已知明文攻击。”实际上，一种广为人知的生成密钥ID的方法是加密一个全零块，并可能从中删除一些信息，这被称为KCV（密钥校验值）。您描述哈希函数的使用方式以及哈希冲突问题的方式还有待改进。 - Maarten Bodewes

然而，添加哈希或校验和的方法是被使用的。例如，在 scrypt 实用程序中；http://www.tarsnap.com/scrypt.html - Roland Smith

scrypt使用哈希函数来派生密钥，这与对明文进行哈希然后加密不同。后者相当无用，因为它仍会产生静态值 - 你可以将所有零加密。 - Maarten Bodewes

它使用SHA256向头部添加签名以验证密码。请参阅lib/scryptenc/scryptenc.c中的scryptenc_setup。 - Roland Smith

为什么对明文进行哈希处理会产生静态值？如果“现代密码算法如高级加密标准目前不容易受到已知明文攻击。”，为什么这会成为问题？KCV有什么用途？ @owlstead - Johannes Gerer