encryption - 加密算法的抗冲突性如何？

Question

对于由在明文/ key 对上工作的给定(对称或非对称)加密算法生成的给定密文，找到产生相同密文的不同明文/ key 对有多难？

找到两个明文/ key 对导致相同的密文有多难？

导致这个问题的原因是另一个可能与上述问题无关的问题:

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

后续问题灵感来自答案和评论:

如果允许的明文/ key 对在以下(或两种)方式中受到限制:

1)明文以 key 的KCV(Key check value)开头。

2)明文以一些明文/键组合的哈希值开始

这会使碰撞发现不可行吗？是否清楚，这样的明文/ key 存在=

Answer 1

你的问题的答案是你的措辞，是没有碰撞阻力。

对称案例
假设您有一个纯文本 PT，其长度是底层分组密码的块长度的倍数。您生成一个随机 IV 并使用 key K、CBC 模式和无填充加密纯文本。

生成生成相同密文 CT 的纯文本 PT' 和 key K' 很容易。只需随机选择 K'，使用 key K' 和 IV 解密 CT，即可得到碰撞的 PT'。

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

要使这种冲突发现不可行，您必须使用消息身份验证代码 (MAC)。

不对称表 shell
类似的东西适用于 RSA 公钥加密。如果您不使用填充(这显然是不推荐的，甚至可能不被大多数加密库支持)，并使用公钥 (N,E) 将 PT 加密为 CT，只需生成第二个 key 对 (N',E) ',D') 使得 N' > N，那么 PT' = CT^D' (mod N) 将在 (N',E') 下加密成 CT。

如果您使用 PKCS#1 v1.5 填充进行 RSA 加密，则 RSA 私钥操作后最重要的八位字节必须是 0x02，它的概率约为 256 分之一。此外，第一个 0x00 值的八位字节必须不早于索引 9 发生，这将以很高的概率(大约 0.97)发生。因此，平均而言，您必须平均生成大约 264 个相同位大小的随机 RSA key 对，然后才能找到一个对于某些纯文本可能产生相同密文的 key 对。

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