摘要
由于分组密码具有安全强度高、运行速度快、便于实现的特点，因此它获得了广泛的应用，尤其是在各类资源有限的嵌入式设备中。本文主要围绕分组密码算法中S盒的紧凑实现展开了工作:基于有限域上乘法运算和逆运算的代数性质，调研了一种称为塔域结构分解的技术，系统扩展了影响该技术的一个因素，将其运用于AES、Camellia和SM4上并获得了比之前的实现方案效果更好的电路;针对更一般的布尔函数，提出了一种新的搜索算法，该算法能与具体工艺库结合，给出在当前库下的大部分3比特和4比特S盒的最小电路。 具体的研究工作和创新点如下: 1.传统分组密码算法中8比特S盒的紧凑实现。部分密码算法的S盒可以看作是F28上的逆运算与仿射变换结合后的产物。我们使用塔域结构分解技术来实现逆运算。在实现时我们找到了影响实现结果的三个因素，分别是中间域、不可约多项式和基底。在固定了中间域和基底后，我们穷搜了所有的不可约多项式组合，发现对于所有同构的F28，不可约多项式的组合均为720种，且多项式中的系数可以用统一的表达式来表示。根据有限域上乘法运算和逆运算的表达式，我们将720种组合分为18个实现上的等价类，之前文献中的方案均集中在其中的两个等价类中，我们对其余的等价类进行了细致的探讨，发现使用其中一个等价类能获得更好的实现结果。仿真实验显示，对于AES，我们的电路打破了之前最小电路的记录，面积降低了2.7％～4.8％;对于Camellia和SM4，我们的电路能有显著的改进，面积至少降低了37％。 2.轻量级分组密码算法中3比特和4比特S盒的极小化实现。我们把3比特和4比特的S盒看作向量布尔函数，将搜索函数电路的问题转换为有向图中寻找到达特殊结点的最小路径的问题，并进一步将有向图分解为树状图，解决了结点的生成和扩展问题。我们提出了一种本质上为广度优先搜索的算法，从理论上证明了该算法返回的结果一定是最小路径，即对应了面积最小的电路。但该算法的时间复杂度和空间复杂度都较高，为了能在现实环境下执行，我们在算法中增加了一些约束条件，修改为两个变种，这两个变种会过滤一些结点和路径，极大地降低了运行需要的时间和计算机内存，并且仍然能保证部分结果是最佳的。此外，通过加入延迟信息和延迟约束，我们的算法还可以在优化面积的同时尽量降低延迟，或者是在规定的延迟内找到面积最小的实现。实验结果表明我们的算法能求解出大多数轻量级密码的最小电路，与以前的算法相比，我们的算法将面积降低了1.6％～50％。
NETL