自动化搜索ARX分组密码：不可能差分与零相关线性闭包算法

"该文提出了一种自动化搜索ARX分组密码不可能差分与零相关线性闭包的算法，通过构建差分特征和线性掩码的传播方程，结合SAT求解器进行有效搜索，对TEA、XTEA和SIMON等密码进行了分析，找到了它们的最优不可能差分和零相关线性闭包。" 在密码学领域，差分分析和线性分析是两种重要的密码攻击方法，用于评估加密算法的安全性。不可能差分是一种特殊的差分，它描述了输入数据微小变化如何在加密过程中几乎不影响输出，这在理论上提供了攻击密码的可能路径。零相关线性则关注加密过程中的线性关系，即使在大量随机输入下，这些关系依然保持为零，揭示了加密算法可能的弱点。 ARX结构是一种基于加法、旋转和扩展操作的分组密码设计方法，因其简单和高效而被广泛应用。然而，这种结构的密码也面临着被差分和线性分析攻击的风险。本文提出的自动化搜索算法针对ARX结构，首先建立差分特征和线性掩码的传播方程，这是分析加密算法内在特性的关键步骤，因为这些方程可以反映操作如何影响输入和输出之间的差异或线性关系。 接下来，利用SAT（Boolean satisfiability problem）求解器解决这些传播方程。SAT求解器是一种强大的计算工具，能够确定是否存在一组输入使得布尔公式为真，这里则用于判断传播系统是否有效，即是否存在不可能差分或零相关线性。通过遍历所有可能的差分特征和线性掩码组合，算法能够自动化地寻找最优的不可能差分和零相关线性闭包，这是评估密码安全性的重要指标。 实验部分，作者运用该算法对TEA（Tiny Encryption Algorithm）、XTEA（Extended Tiny Encryption Algorithm）和SIMON家族的分组密码进行了分析。TEA和XTEA是著名的轻量级密码，SIMON系列则是一组由美国国家安全局设计的低功耗加密算法。通过算法的搜索，他们得到了这些密码的最佳不可能差分和零相关线性闭包，这些结果对于进一步理解这些算法的安全性，以及潜在的改进方案具有重要意义。 此外，该算法还表明，除了ARX结构的密码，它也可以有效地应用于基于S盒（Substitution Box）的分组密码的不可能差分和零相关线性闭包搜索。S盒是许多传统密码算法的核心组件，负责非线性转换，提高密码的混淆度。 总结起来，这篇研究提供了一种自动化工具，能够深入探究ARX结构以及其他类型分组密码的不可能差分和零相关线性特性，有助于密码学家评估和增强现有密码系统的安全性。这种方法的效率和通用性对于密码学研究和实践都具有重要价值。