💻 computer science

Evolutionary Approach to S-box Generation: Optimizing Nonlinear Substitutions in Symmetric Ciphers

该研究提出了一种结合遗传算法与沃尔什 - 哈达玛谱成本函数的新方法，成功生成了非线性度达到 104 的 8x8 S 盒，在保持 100% 成功率的同时将迭代次数大幅降低至与现有最佳方法相当的水平，显著提升了遗传算法在对称密码 S 盒生成中的效率与实用性。

原作者： Oleksandr Kuznetsov, Nikolay Poluyanenko, Emanuele Frontoni, Marco Arnesano, Oleksii Smirnov

发布于 2026-04-13

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Oleksandr Kuznetsov, Nikolay Poluyanenko, Emanuele Frontoni, Marco Arnesano, Oleksii Smirnov

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于如何制造“超级密码锁”的故事。为了让你轻松理解，我们可以把现代网络世界想象成一个巨大的、充满宝藏的城堡，而对称加密算法（Symmetric Ciphers）就是保护这些宝藏的防盗门。

在这扇防盗门上，有一个最关键的小零件，叫做S-box（替换盒）。

1. 什么是 S-box？（城堡里的“变形金刚”）

想象一下，你输入一串数字密码（比如 1011），S-box 就像一个魔法变形金刚，它能把这串数字瞬间变成另一串完全看不懂的乱码（比如 0110）。

它的作用：让黑客无法通过简单的数学规律猜出你的密码。如果 S-box 太“老实”（线性），黑客就能轻易破解；如果 S-box 足够“狡猾”（非线性），黑客就会晕头转向。
目标：研究人员想要制造出最狡猾、最难以预测的 S-box。对于 8x8 的 S-box（就像是一个有 256 个格子的转盘），有一个衡量它“狡猾程度”的指标叫非线性度（Nonlinearity）。目前的“黄金标准”是达到 104 分。

2. 以前的难题：大海捞针

制造这种完美的 S-box 非常难。

想象一下：你要在一个由 256 个不同颜色的珠子组成的巨大项链中，找到一种排列方式，能让项链在旋转时呈现出最完美的光影效果。
问题：可能的排列方式有 $256!$ （256 的阶乘）种，这是一个比宇宙中所有原子还要多的天文数字。用传统的“穷举法”（一个个试）去试，就算把全人类都算上，等到宇宙毁灭也试不完。

3. 以前的方法：靠“运气”和“经验”

为了解决这个问题，科学家们以前用过两种主要方法：

数学公式法：像造房子一样，用严格的数学公式直接“算”出一个 S-box。但这就像用预制板盖房子，虽然快，但结构太固定，容易被懂行的人（黑客）找到弱点。
随机搜索法：像模拟退火（模仿金属冷却）或爬山（一步步往上走）。这些方法有点像在迷宫里乱撞，虽然能找到出口，但往往需要撞几百万次甚至几千万次，效率很低。

4. 这篇论文的新方法：进化论 + 智能筛选

这篇论文的作者（来自意大利和乌克兰的科学家）提出了一种新玩法：用“进化论”来设计密码锁。

他们使用了一种叫**遗传算法（Genetic Algorithm）**的技术，这就像是在培养一群“密码特工”：

初始种群：先随机生成一群（比如 1 个或几个）S-box，就像一群刚出生的小猴子。
自然选择：给每个小猴子打分（看它的“非线性度”够不够高）。分数低的直接淘汰，分数高的留下来。
变异（Mutation）：这是最有趣的部分。作者发现，与其让一群猴子互相交配（传统的遗传算法），不如只留一只最聪明的猴子，然后让它不断地**“自我微调”**。
- 比喻：想象你在玩一个拼图游戏。你手里有一块拼图，你每次随机交换两个小块的位置，看看拼图是不是变得更完美了。如果是，就保留；如果不是，就换回来。
- 作者发现，这种**“单兵作战 + 疯狂微调”**的策略，比“大部队作战”效率高得多！
裁判（WHS 成本函数）：他们请了一位非常严格的裁判（基于 Walsh-Hadamard 谱的算法），专门负责给 S-box 打分，确保它足够“狡猾”。

5. 惊人的结果：快、准、狠

经过大量的实验（他们跑了 12,100 次模拟），他们发现：

速度极快：以前用遗传算法可能需要跑几百万次才能找到一个完美的 S-box。而他们的“单兵微调”策略，平均只需要跑 49,399 次 就能成功！
成功率 100%：只要给足时间，他们的方法每次都能造出完美的 S-box（非线性度达到 104）。
打破纪录：这个成绩和目前世界上最好的“爬山法”（Hill Climbing）几乎一样快，但用的是完全不同的思路。

6. 这意味着什么？（给普通人的启示）

工具箱更丰富了：以前密码学家手里只有一把“锤子”（爬山法），现在他们多了一把“瑞士军刀”（优化的遗传算法）。如果锤子不好用，他们可以用军刀，而且效果一样好。
更安全：这种随机生成的 S-box 没有固定的数学结构，黑客更难找到规律去破解。
更灵活：这种方法很容易在电脑集群上并行运行（就像让 8 个人同时干活），未来可以生成更多样化、更安全的密码系统。

总结

这篇论文就像是在说：“我们不用那种笨重的、需要几百万次尝试的旧方法了。我们发明了一种聪明的‘单兵进化’策略，就像让一个特工不断微调自己的动作，结果发现他能在极短的时间内，完美地制造出世界上最难破解的密码锁。”

这不仅让密码学更有趣，也让我们的数字世界更安全。

以下是基于论文《Evolutionary Approach to S-box Generation: Optimizing Nonlinear Substitutions in Symmetric Ciphers》（S 盒生成的进化方法：对称密码中非线性替换的优化）的详细技术总结：

1. 研究背景与问题 (Problem)

核心挑战：在对称密钥密码学中，S 盒（Substitution boxes）是提供非线性特性的关键组件，直接决定了算法抵抗线性密码分析和差分密码分析的能力。对于现代密码（如 AES），8x8 S 盒的非线性度（Nonlinearity, NL）达到 104 是一个重要的基准。
现有局限：
- 代数构造的弱点：基于有限域逆运算等代数构造的 S 盒（如 AES 使用的）虽然效率高，但具有固有的代数结构，容易受到代数攻击（Algebraic Attacks）。
- 搜索空间巨大：8x8 S 盒的搜索空间约为 $8!^{256}$ （约 $10^{506}$ ），穷举搜索不可行。
- 启发式方法的效率：虽然模拟退火、爬山算法和遗传算法（GA）已被用于生成 S 盒，但早期的遗传算法实现通常需要数百万次迭代才能达到目标非线性度，计算成本高昂且效率不如某些特定的爬山算法。
研究目标：探索遗传算法在生成高非线性 S 盒方面的潜力，特别是结合 Walsh-Hadamard 谱（WHS）代价函数，旨在以与现有最佳方法相当甚至更优的效率生成非线性度为 104 的 8x8 S 盒。

2. 方法论 (Methodology)

作者提出了一种改进的遗传算法，其核心设计如下：

算法架构：
- 采用**精英选择（Elite Selection）**机制，每一代仅保留表现最好的 S 盒。
- 结合了**随机爬山（Stochastic Hill Climbing）**的思想。实验发现，当种群大小（ $K_{pop}$ ）设为 1 时，算法表现最佳，实际上退化为一种高效的随机爬山策略，但保留了遗传算法的框架。
变异算子（Mutation Operator）：
- 为了保持 S 盒的双射性（Bijectivity），变异操作定义为随机交换 S 盒中两个不同位置的元素（Swap）。
- 每个 S 盒在每一代中应用多次变异（ $K_{mut}$ 次）。
目标函数（Objective Function）：
- 采用 Clark 等人提出的 Walsh-Hadamard Spectrum (WHS) 代价函数。
- 该函数通过计算 S 盒分量函数及其线性组合的 Walsh-Hadamard 变换系数来评估非线性度。
- 参数设定： $R=12, X=0$ ，经实验证明这对生成高非线性双射 S 盒效果最佳。
实验设置：
- 语言与环境：C++ 实现，利用 8 线程并行计算以加速。
- 参数扫描：对种群大小（ $K_{pop}$ : 1-21）和变异次数（ $K_{mut}$ : 1-31）进行了广泛的参数扫描。
- 评估指标：主要指标是生成并评估的 S 盒数量（ $K_{Sbox}$ ），即找到非线性度 $\ge 104$ 的 S 盒所需的平均迭代次数。
- 终止条件：找到 NL $\ge 104$ 的 S 盒或达到最大迭代限制（150,000）。

3. 关键贡献 (Key Contributions)

性能突破：证明了遗传算法（在特定配置下）可以达到与当前最佳方法（如改进的爬山算法）相当的性能。
效率提升：相比于早期的遗传算法实现（通常需要数百万次迭代），该方法将所需的平均迭代次数降低了几个数量级。
发现最优配置：实验揭示了一个反直觉但关键的发现——种群大小为 1（ $K_{pop}=1$ ） 的配置表现最好。这表明在该问题的搜索景观中，激进的局部搜索（类似爬山）比维持大种群的多样性更有效。
100% 成功率：在最佳配置下，算法生成非线性度为 104 的 S 盒的成功率达到 100%。

4. 实验结果 (Results)

最佳配置：种群大小 $K_{pop} = 1$ ，变异次数 $K_{mut} = 7$ 。
性能数据：
- 平均迭代次数（ $K_{Sbox}$ ）：49,277（论文摘要和结论中取整为 49,399）。
- 成功率：100%。
- 非线性度（NL）：104。
对比分析（见表 2）：
- 与 Hill Climbing (HC) 方法（如 [5, 24]）相比：性能几乎持平（HC 约需 50,000 次，GA 需 49,399 次）。
- 与早期遗传算法（如 [10, 31]）相比：迭代次数从数百万次（如 3,849,881）减少到约 5 万次，效率提升巨大。
- 与其他启发式方法（如模拟退火 SA）相比：在达到 100% 成功率方面表现更优，且迭代次数更低。
参数敏感性：随着种群大小（ $K_{pop}$ ）的增加，所需的迭代次数显著增加，表明大种群在此特定问题上增加了计算开销而未带来收敛速度的提升。

5. 意义与影响 (Significance)

扩展工具箱：该研究为密码学家提供了一个新的、高效的 S 盒生成工具。虽然性能未超越现有的最佳爬山算法，但它证明了遗传算法同样具备解决此类高难度优化问题的潜力，增加了方法的多样性。
抗攻击性增强：生成的 S 盒缺乏固有的代数结构，具有更高的代数免疫性（Algebraic Immunity），能有效抵抗代数攻击和针对特定代数结构的攻击。
灵活性与可扩展性：遗传算法框架天然适合并行化，且易于调整以适应多目标优化（如同时优化差分均匀性、代数免疫性等）。
理论启示：研究结果表明，在某些复杂的组合优化问题中，简单的“单点”进化策略（退化为随机爬山）可能比复杂的种群进化策略更高效，这对启发式算法的设计提供了新的视角。

总结：
这篇论文通过引入改进的遗传算法策略（特别是小种群/单点策略结合 WHS 代价函数），成功解决了 8x8 S 盒生成中的效率瓶颈问题。它以极低的计算成本（约 5 万次迭代）和 100% 的成功率，生成了满足高非线性度（104）要求的 S 盒，其性能与领域内最顶尖的爬山算法相当，为对称密码系统的组件设计提供了高效且可靠的解决方案。