基本信息
文件名称:轻量级分组密码S盒的优化设计案例1600字.docx
文件大小:76.64 KB
总页数:9 页
更新时间:2025-06-28
总字数:约3.89千字
文档摘要

轻量级分组密码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_