使用不同的密钥解密相同的密文（AES）

Question

假设我有一个密钥k和明文P。然后我使用密钥k使用AES加密P：

C = AES_k(P)

现在假设我有另一个我选择的纯文本 - P*。这个纯文本与P无关，我选择它是任意的。

是否可能找到一个密钥k*，使得当我使用k*解密C时，我会得到P*？

即： D_k*( AES_k(P) ) = P*

- qowpr

---

你实际上是在问是否有可能找到这个键，还是更简单地说，这样的键是否存在？ - Oliver Charlesworth

我对这个键是否存在感兴趣，如果存在的话，是否有任何有效的方法来生成它（因为尝试查找所有可能选项并不可行）。 - qowpr

Answer 1

我认为密钥不一定存在。密钥定义了一个块的所有可能值的排列。对于128位块大小，有(2^128)!种可能的排列。对于256位密钥，有2^256种可能的密钥。这远小于排列数，因此并非每个排列都可以被指定。我认为 - 尽管我无法证明或争论 - 这意味着可能不存在可指定的置换将您选择的第二个明文映射到密文。

如果这样的置换存在，我认为它将非常难以找到。如果很容易找到，密码的已知明文攻击将是微不足道的。

- Tom Anderson

---

我同意密钥不一定存在，但我认为对于AES-128来说，它很可能存在；对于AES-192来说，可能有2^64个这样的密钥；对于AES-256来说，可能有2^128个这样的密钥。他只限制了结果排列中的一个条目。 - President James K. Polk

@Nick Johnson：我一开始也以为它是一个单一的块，就像这个答案一样。一个随机密钥映射P*到C的概率大约是2^(-128)，其余的就可以推导出来了。 - President James K. Polk

@Nick Johnson：我猜你是指排列数量，而不是块数。但是@GregS是正确的，因为我们只关心排列中的一个点，它存在的概率比我提出来的要高得多。然而，你仍然无法找到它的密钥！ - Tom Anderson

@Harlan：我想不是这样的。一个N位块有2^N个不同的值。一组M个不同的值有M!种排列方式。因此，对于一个N位块的值，有(2^N)!种排列方式。 - Tom Anderson

@Harlan：因为这是加密128位块的可能方式数量。密码是将N位输入映射到N位输出的函数；它必须将每个输入映射到唯一的输出，以便它是可逆的。这相当于一个置换-如果您运行从0到2^N-1的N位块的2^N个可能值，对每个进行加密，并将结果写入列表中，则您有2^N个不同的值，因此您拥有您开始的值的置换。因此，有(2^N)!种可能的不同密码。 - Tom Anderson

Answer 2

我假设你的明文和密文P、P*和C都是128位块。

如果你的密钥k和k*长度为128位（即你正在使用AES-128），那么有大约36.8％的概率没有解决方案：更准确地说，如果你考虑所有可能的C和P*值集合（2²⁵⁶个组合），则对于其中约e^-1个组合，不存在k*会使AES_k*(P*) = C成立。

这源于这样一个思想：对于给定的P*值，将k*转换成AES_k*(P*)的函数应该表现得像一个随机函数，而从大小为N的集合到相同大小的目标集合的随机函数具有平均覆盖率 1-e^-1。这里，对于给定的P*值，有大约63.2％的128位字可以作为使用128位密钥加密P*时的AES加密输出。

另一方面，如果允许k*更宽（AES还接受192位和256位密钥），则应该有很多解k*可以满足你的方程。

无论如何，实际上找到k*（甚至192位或256位的k*）应该是不可行的，其工作量接近于2¹²⁸个操作。能够以比这更小的工作量找到k*可能被视为AES中的结构缺陷。对P和k的了解在任何方面都没有帮助：对于给定的128位密文C，很容易找到匹配的配对（P，k）。

注意：如果你使用AES并交换明文和密钥的角色，则可以获得有限输入和128位输出的原始哈希函数的粗略仿真。你所要求的是对该哈希函数的预像攻击的可行性。

- Thomas Pornin

---

你能提供一下如何计算随机函数的1-e^-1平均覆盖率的提示吗？ - Mehran Torki

Answer 3

可以通过使用另一种类型的密码（例如维纳姆密码）对C进行解密，从而获得k*并解密C以获取明文P*。

您可以获得k*，使得D_k*( AES_k(P) )生成您的P*。

只需执行以下操作：P* ^ C即可获得您的k*，然后如果您解密：k* ^ C，您将获得P*（假设C和P*的大小相等）。

但是，如果您的P*的大小小于C，则会产生重复的P*。

^：按位异或

我不确定这是否是您想要的，因为您没有提到您也想使用AES进行解密。

- user668726

Answer 4

对于您选择的任何明文，这都不应该是可能的。能够将密文解密为任意明文将意味着某种被称为完美安全（或完美保密）的东西。

例如，如果我有密码ADGWTX，并且我知道它是使用简单的异或和6个字母的密钥加密的，我仍然不能在没有更多关于密钥的信息的情况下破解它。因为一个密钥会给我ESCAPE，而另一个密钥会给我ATTACK。

完美安全是“一次性密码本”（http://en.wikipedia.org/wiki/One-time_pad）的特征，但不是AES的特征。

- irritate