如果是，我如何（有效地）找到这样的一对？
#1 楼
简短版本：很可能大部分键都有固定点，但我对如何找到它们不了解。长版：随机参数
有$ 2 ^ 128位块的{128}！$置换，其中$！2 ^ {128} $（这是子因子）是无固定点的。众所周知，
$ \ lim_ {N \ to \ infty} \ frac {！N} {N！} = \ frac 1e \约0.3679 $（并且很快达到了此限制），即比所有排列的三分之一都是无固定点的。
AES-128从这些$ 2 ^ {128}！$排列中选择$ 2 ^ {128} $。假设此选择的行为就像一个随机的选择，则大约63％的密钥具有至少一个固定点。
（此参数对具有足够大块的任何块密码有效，此处没有AES特定的内容。）
但是...
当然，AES（以及实践中可用的任何分组密码）不是随机选择的排列-例如，AES选择的所有排列都是偶数（AES由一些操作组成，每个操作都会位不变，这些是偶数，偶数排列的组成是偶数），因此可用空间减半。使每个密钥（或没有密钥）具有固定点（无固定点排列和无固定点排列的数目都比可用AES密钥的数目大得多）。我在这里一无所知（而且正如Thomas所指出的，了解更多可能表明AES的弱点）。 >
评论
$ \ begingroup $
但是AES并不是128位$ 2 ^ {128}！$排列的随机子集；例如，它仅生成偶数排列。我们怎么知道它不只是从排列中选择？
$ \ endgroup $
–固定
2011-10-15 2:16
$ \ begingroup $
好点。我在这里不知道答案（而且不确定是否有答案）。实际上，如果将AES的固定点设置为比预期的少，或者根本没有，则我不会感到惊讶。
$ \ endgroup $
–PaŭloEbermann
2011-10-15 2:23
$ \ begingroup $
如何在不引入某些可利用结构的情况下“使固定点比预期的少”？你有个主意吗
$ \ endgroup $
– ByteCoin
2011-10-15 2:27
$ \ begingroup $
伯纳德·哈里斯（Bernard Harris）自1960年以来与随机映射有关的概率分布可能有用。
$ \ endgroup $
– ByteCoin
2011-10-15 2:32
$ \ begingroup $
@ByteCoin：不，我不知道。仅无定点排列的空间足够大，我们仅可以从那些中选择，而不会因此而引入一些缺点。希望我们从对AES有更多了解的人那里得到一些答案（进行了一些密码分析或阅读了相应的论文）。我在这里的论点是一个通用的论点，它对于该块和密钥大小的任何块密码均有效（或无效），与AES无关。 （我睡一会儿后再编辑答案。）
$ \ endgroup $
–PaŭloEbermann
2011-10-15 2:37
#2 楼
据我所知，尚无这样的固定点，但将其视为高度不可能（如@Pa（lo所指出的那样）。我们可以说缺少固定点将被认为是一个弱点：AES应该“看起来像”随机排列。另一方面，即使能够证明（ （非建设性地）固定点的存在将被视为可疑的：这样的证明不能存在于真正随机的排列上，因此证明本身必须利用AES的内部结构。因此，我们目前无法证明不动点的存在。
没有已知的有效算法可以找到不动点。目前最好的算法是尝试随机密钥和消息，直到达到固定点为止，平均AES计算费用为$ 2 ^ {128} $美元。
评论
$ \ begingroup $
您是否认为所有AES排列甚至都是“可疑的”证据？
$ \ endgroup $
–固定
2011年10月15日16:55
$ \ begingroup $
@Fixee：是的。但是，Feistel方案中也存在该属性，该方案自1970年代开始部署，并不意味着任何实际的攻击，因此我学会了使用它。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011-10-15 19:38
$ \ begingroup $
顺便说一句，在AES-128中找到一个定点就等于倒转了一轮基于AES的Davies-Meyer。展示如何有效地做到这一点将是一个令人震惊的结果。
$ \ endgroup $
–固定
2011-10-17 4:27
$ \ begingroup $
@Fixee：只有在已知$ 2 ^ {128} -2 $（resp。$ 2 ^ {64} -2 $）纯文本/密文对之后，AES（res DES）才是偶数排列这一事实才有意义；这就解释了为什么在实践中将其视为非问题。
$ \ endgroup $
–fgrieu♦
2012年4月30日在21:53
评论
只需注意一下，有目的地避免不动点可能是导致谜题机器被破解的主要原因。避免定点是密码的一大弱点。