轻量级分组密码S盒的优化设计案例
目录
轻量级分组密码S盒的优化设计案例 1
1.1异或门数优化 1
1.2启发式算法介绍 2
1.3LED算法S盒优化过程及原理 3
1.4S盒实现及优化结果 4
1.1异或门数优化
线性函数电路的门优化已经得到了广泛的研究。结果表明，线性电路优化问题是NP难问题。因此，我们在本研究中的利用了改进已知的启发式方法。最成功的启发式方法是由于Paar[11]引起的贪婪算法的变化，而我们使用的启发式算法与前者相比也有显著的改进。
域F上的线性直线程序是直线程序上的一种特殊形式，它不允许变量作乘法。也就是说，程序的每一行都是u=λv+uw的形式，其中、u在域F
中取值，1和W是变量。为给定的函数f构造一个线性)路等价于在
GF(2上构造一个计算f的线性直)程序(注意，在GF(2上，λ和μ总是1,因此)不显示地写入)。
如果GF(2上的线性直线程序，对于程序u=v+w的每一行，W的表达式中没有2的变量，乙的表达式中没有W的变量，即计算中没有抵消变量，那么线性直线程序被认为是无取消的)
以前关于S盒电路最小化的工作。只考虑在GF(2)上生成一组线性形式的无取消直线程)。一些研究者似乎提出了错误的假设，即总是存在GF(2)上无取消的最优线性程序。一个小小的反例，证实并不是最优：
x?十x?;x?+x?+x?;x?+x?+x?+x4;x?+x?+x?
不难发现，反例中最优无取消直线程序的长度为5。而还存在长度为4的解决
2
方案：
V?=x?+x?
;V?=v?+x?;
V?=V?+x?;v?=v?+x?
在之后的优化工作我们也将利用引入中间变量的方式，力求降低异或门数，以求获得异或门数上的优化，而启发式算法是我们找到最小化异或门数的一个很重要的工具。
1.2启发式算法介绍
定义M为二元域上m×n的常数矩阵，定义x为二元域上n个变量的常数向量。SLP的问题是找到行数最少的方式来计算Mx。在这里，程序的每一行都格式固定。即，计算一组线性方程所需的最小线性运算量。
在二元域中解决上述SLP等效于找到最短电路以仅使用XOR门来计算函数。因此，优化S盒的线性部分的操作可以等同于上述SLP问题。因此，优化S盒的线性部分的操作可能等效于解决二元域上的SLP问题。
启发式算法可以解决如下问题：
设M是一个基本向量集，就是变量X?,X2…,Xm的集合。距离向量D「是中的每一行到的最小汉明距离，即D[i]=δ(S,f:l,其中f.是的第行乘以输入向量x。初始的D[il等于第行的汉明权重减1。然后，我们执行以下循环：
1.通过两个现有基础元素组合出新的基础元素，并将其添加到S中；
2.根据新的S更新D[;
3.重复过程1、2,直到所有的D[i]=0为止。
这个启发式方法中的距离向量是通过穷举搜索来计算的。因此它适用于中等大小的矩阵，距离只能减小，并且实际上只能减少1。因此，当考虑一个新基本元素时，如果距离为d,则仅需考虑d-1个旧基础元素和新基础元素的组合。
选择新基础元素的标准是选择一个使新距离之和最小的元素。如果两对基本向量之间存在距离相同的情况，则选择使新向量的欧几里得范数最大化的那对。
此启发式方法的距离向量是通过穷举来实现的。因此，它适用于中型大小的矩阵。
3
之后，我们将以LED算法4×4S盒的优化为例，叙述启发式算法的优化过程及其原理。
1.3LED算法S盒优化过程及原理
1.将算法S盒优化问题转化成SLP问题实例。将SAT求解器求出的.solution文件里面涉及到的x的异或转换成一个矩阵M,s代表X?,X2,X2,X△的集合。Ms则代表整个涉及x的solution算式。初始距离向量
[1,1,2,1,0,1,2,3,1,1,21(异或门数量),基本向量为xn,x?,X?,xal,分别对应[1,0,0,0][0,1,0,0][0,0,1,0][0,0,0,1]。如图1.3.1,即为算法更改结果示例：
q_0=1+x_1+x_2
q_1=1+x_