对称加密算法的混淆层(S盒)密码学指标详细介绍

对称加密算法的混淆层(S盒)密码学指标详细介绍

对称加密算法包括分组加密算法，序列密码算法，密码杂凑算法，认证加密算法和消息鉴别算法，通常其算法结构由混淆层(S盒)和扩散层(P盒)构成。我们可以这样理解：对称加密算法是一种伪随机置换，把明文通过密钥和加密算法变换成近似随机的无意义数据，在不知道密钥的情况下，敌方就算得到密文，也无法通过密文获得明文的任何信息。

密码学之父香农曾提出，安全的加密算法需要两大操作：混淆和扩散。其中S盒就是实现混淆的核心利器：混淆性是指明文密钥和密文之间的依赖关系应该尽可能复杂，以至于攻击者无法利用这种关系。nXm规模的S盒是指：该S盒的输入为n比特，输出为m比特。例如DES算法使用的是6X4规模S盒，AES算法使用的是8X8规模S盒，SHA3算法使用的是5X5规模S盒，SM4算法使用的是8X8规模S盒，PRESENT算法使用的是4X4规模S盒等。更多S盒详见对称加密算法中的混淆层(S盒)大盘点。

下面我将列举S盒的常用密码学指标，以供大家参考。

（1）平衡性

简单来说，一个平衡的S盒，其输出值在统计上必须是均匀分布的。 这意味着，对于n×m的S盒，当所有可能的输入值以相同概率出现时，每一个可能的输出值也恰好出现相同的次数（即2^(n-m)次，对于n×n的S盒来说就是1次）。

S盒的平衡性是其发挥混淆作用的基石，如果不平衡，会直接引发严重的安全漏洞。

1.保证算法可逆（解密）：这是最根本的要求。对于AES这类分组密码，解密过程需要逆S盒。只有当S盒是双射（即输入与输出一一对应）时，它才是可逆的。而双射是平衡性在n×n S盒上的最强体现。一个不平衡的S盒无法构造唯一的逆，加密将无法解密。

2.抵抗统计分析攻击：一个平衡的S盒不会泄露输入数据的统计模式。如果S盒不平衡，某些输出值出现频率更高，攻击者就可能利用这种偏差来破解密钥，这与古典密码学中利用字母频率分析破解的原理类似。

双射函数在输入值遍历的时候，输出值也遍历，故双射函数是平衡的。因此我们通常通过构造双射变换来作为S盒使用，因其天然具有平衡性。

总而言之，平衡性是S盒的安身立命之本。一个优秀的S盒，必须在满足平衡性的基础上，再去追求高非线性度、低差分均匀度等其他指标，以达到安全与性能的最佳平衡。

（2）正交性

“S盒的正交性”在密码学中通常与平衡性紧密关联，有时甚至被视为其等价或更严格的概念。简单来说，正交性是平衡性在考虑所有输入分量（比特）时的全面推广。一个S盒可以看作由多个布尔函数（对应每个输出比特）组成。之前提到的平衡性，要求的是S盒的每一个输出比特本身是均衡的（即输出0和1的次数相等）。而正交性，则对S盒提出了更高的要求：它要求S盒任意多个输出比特的线性组合也必须是平衡的。

正交性是一个比平衡性更强的“优良”性质，它确保S盒在更广泛的线性组合下都不会引入统计偏差，从而能更好地抵抗线性密码分析等攻击。有资料直接指出“S盒的正交性（平衡性）”，表明在许多研究和实践中，这两个概念是紧密联系甚至等同看待的。一个满足正交性的S盒，其安全性被认为更高。

总的来说，正交性可以看作是S盒平衡性的一个更严格、更全面的版本。它要求S盒所有的非零输出比特组合都具备平衡性，是衡量S盒抵抗线性分析能力的一个重要指标。

（3）不动点

简单来说，对于一个S盒，如果存在某个输入值x，经过S盒替换后，输出值恰好等于它自身，即满足 S(x) = x，那么这个输入值x就被称为该S盒的一个不动点 (Fixed Point)。与之相关的另一个概念是反向不动点 (Reverse Fixed Point)，它指存在某个输入x，使得 S(x) = ¬x（即输出是输入按位取反的结果）。

不动点之所以被视为一个可被利用的安全弱点，主要因为以下几点：

引入可预测的线性关系：S盒的核心作用是提供非线性以达到“混淆”的目的。而不动点S(x) = x在这一点上建立了一个线性关系，削弱了S盒的非线性。这为攻击者提供了可乘之机，可能被用于线性密码分析等攻击。

导致“无效替换”：S盒的本质是一个替换表，当遇到不动点时，它实际上没有对输入做任何改变。这相当于在加密过程中出现了一个“漏洞”，使得该字节的混淆效果为零，从而可能被攻击者利用。

总而言之，不动点是S盒中一个应该被避免的、可能削弱其非线性强度和混淆效果的安全弱点，因此在设计“强”S盒时，消除不动点是一个重要的目标。

（4）周期性

“S盒的周期性”是衡量其迭代行为的重要指标，尤其对于双射S盒（输入输出一一对应）而言。它关注的是，当我们把S盒的输出再次作为输入，不断迭代应用这个S盒时，其状态变化会呈现出怎样的循环模式。

对于一个双射S盒，可以将其看作一个置换（Permutation）。当我们从任意一个输入值开始，不断应用S盒（即计算 S(x), S(S(x)), S(S(S(x))), ...），由于输入空间有限，最终必然会回到某个已出现过的状态，形成一个循环或周期（Cycle/Orbit）。

1.周期（Period）：指在迭代过程中，一个状态序列重新回到起始状态所需的步数。

2.循环结构（Cycle Structure）：指一个S盒所有可能输入值，在迭代下形成的所有循环的集合。这描述了S盒迭代行为的整体图景。

评估一个S盒的周期性，主要有两个关键点：

最大周期（Maximal Periodicity）：指从任何一个输入值开始迭代，其循环长度都能覆盖所有可能的状态。例如，对于一个8×8的S盒，最大周期为256，意味着从任意输入开始，迭代S盒256次，会遍历0到255的所有值，然后回到起点。这是设计者追求的理想状态。

短周期（Short Cycle）：这是需要避免的弱点。指某些输入值经过少数几次迭代后就快速回到自身，形成一个很小的循环。

S盒的周期性，特别是其循环结构，是衡量其迭代行为随机性和复杂度的关键因素。短周期（如AES S盒中存在的）被视为弱点，而设计具有最大周期的S盒是提升其安全性的重要目标之一。

（5）差分均匀度

差分均匀度衡量的是，对于给定的输入差分（两个不同输入之间的差异），其对应的输出差分（两个输出之间的差异）在统计上分布得有多均匀。

其定义如下：

对于S盒所有可能的输入对 (x, y)，计算其输入差分 Δx = x ⊕ y 和输出差分 Δy = S(x) ⊕ S(y)。统计对于每一个非零的输入差分 Δx，所有可能的输出差分 Δy 的出现次数。差分均匀度就是所有这些出现次数中的最大值。

这个最大值越小，说明输入和输出差分之间的对应关系越不规律，攻击者就越难通过分析差分传播来破解密码。

1.理想值：差分均匀度的理想值是2。达到此值的函数被称为几乎完美非线性（APN，Almost Perfect Nonlinear）函数。