轻量级分组密码S盒的优化设计案例
目录
轻量级分组密码S盒的优化设计案例1
i.i异或门数优化1
1.2启发式算法介绍2
1.3LED算法S盒优化过程原理3
1.4S盒实现优化结果4
1.1异或门数优化
线性函数电路的门优化已经得到了广泛的研究。结果表明，线性电路优化问
题是NP难问题。因此，我们在本研究中的利用了改进已知的启发式方法。最成功
的启发式方法是由于Paar［ll］引起的贪婪算法的变化，而我们使用的启发式算法与
前者相比也有显著的改进。
域F上的线性直线程序是直线程序上的一种特殊形式，它不允许变量作乘法。
也就是说，程序的每一行都是u=/tv+uu的形式，其中入〃在域F
中取值，［和协是变量。为给定的函数f构造一个线性）路等价于在
GF⑵上构造一个计算f的线性直）程序（注意，在GF（2、上，制“总
是1,因此）不显示地写入）。
如果GF（2、上的线性直线程序，对于程序u=v+w的每一行，M
的表达式中没有「的变量，r的表达式中没有队的变量，即计算中没有
抵消变量，那么线性直线程序被认为是无取消的）
以前关于S盒电路最小化的工作。只考虑在GF12上生成一组线性形式的
无取消直线程）。一些研究者似乎提出了错误的假设，即总是存在GF（2上无
取消的最优线性程序。一个小小的反例，证实并不是最优：
X1+X,:%1+%2+七；%1+%2+^3+刀4；+%3+%4
不难发现，反例中最优无取消直线程序的长度为5。而还存在长度为4的解决
方案:
Vi=X1+Xj:V2=vt+;
%=#2+V4=V3+%!
在之后的优化工作我们也将利用引入中间变量的方式，力求降低异或门数，
以求获得异或门数上的优化，而启发式算法是我们找到最小化异或门数的一个很
重要的工具。
1.2启发式算法介绍
定义M为二元域上mXn的常数矩阵，定义x为二元域上ri个变
量的常数向量。SLP的问题是找到行数最少的方式来计算Mxo在这里，程序
的每一行都格式固定。即，计算一组线性方程所需的最小线性运算量。
在二元域中解决上述SLP等效于找到最短电路以仅使用XOR门来计算函数。
因此，优化S盒的线性部分的操作可以等同于上述SLP问题。因此，优化S盒的
线性部分的操作可能等效于解决二元域上的SLP问题。
启发式算法可以解决如下问题：
设m是一个基本向量集，就是变量的集合。距离向量dn
是出中的每一行到5的最小汉明距离，即DR]=6（Srn,其中f
是也的第i行乘以输入向量“初始的D们等于第行的汉明权
重减1。然后，我们执行以下循环：
1.通过两个现有基础元素组合出新的基础元素，并将其添加到5中；
2.根据新的5更新DF1；
3.重复过程1、2,直到所有i的DR1=0为止。
这个启发式方法中的距离向量是通过穷举搜索来计算的。因此它适用于中等
大小的矩阵，距离只能减小，并且实际上只能减少1。因此，当考虑一个新基本元
素时，如果距离为d,则仅需考虑d-1个旧基础元素和新基础元素的组合。
选择新基础元素的标）隹是选择一个使新距离之和最小的元素。如果两对基本
向量之间存在距离相同的情况，则选择使新向量的欧几里得范数最大化的那对。
此启发式方法的距离向量是通过穷举来实现的。因此，它适用于中型大小的
矩阵。