求S盒布尔函数表达式的一种新算法

《求S盒布尔函数表达式的一种新算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求S盒布尔函数表达式的一种新算法韦宝典刘景伟王新梅西安电子科技大学综合业务网国家重点实验室西安710071摘要:本文提出一种求S盒布尔函数表达式的新递归算法，具有简洁、易于编程实现、准确而快速的特点.算法中只进行异或和内积运算，运算次数少，应用于DES获得与公开文献相符的结果，应用于AES首次求出其S盒的布尔函数表达式关键词:S盒布尔函数递归DESAES1引言S盒11,3.4.51是大多数分组密码中至关重要的非线性部分，高代数次数S盒是安全密码的一个必要条件。一般的密码算法都给出S盒的构造方法，或者给出S盒真值表，很少直接给出每一输出比特与所

2、有输人比特之间的关系一一名盒布尔函数表达式。如何求解这一表征S盒非线性性程度的表达式对算法安全性分析具有重要意义。当前，对已知构造方法的S盒，如AES算法Rijndae1121，可根据其构造方法进行逆推，但这会涉及高阶非线性矩阵运算，不但计算量大、容易出错，而且也不易于计算机编程实现;对已知真值表的S盒，用化简小项表达式的方法同样具有如上的缺点;而逐一猜测表达式通式中所有系数的办法无异于用穷举法搜索长为2”比特的密钥，这更是不可能实现。虽然S盒的输人通常只有几个比特，但由于高度的非线性性，其布尔函数表达式的项数长达数十位，甚至上百位，仅此就使

3、手工运算望而却步。本文设计了一种新的易于计算机编程实现的简便算法，用于求解布尔函数表达式，复杂度小，运行快速准确。本文第2节给出的六个定理及其证明是算法设计的思路和理论基础;第3节完整地描述了新算法，对算法的复杂度进行了分析.给出算法在典型分组密码DES和AES中的应用结果;最后结论在第4节给出。2算法思路和原理输人为二=艺xi2'=(Xn-1,Xn-_，.IX1"X0)2的nxnS盒布尔函数的通式为f(x卜叉C1x}-ixn-2...X.X;'xo"，系数。、。(0,1)=艺i,2‘二(1n-1,1=--，二，11+10)2·基金项目:国家

4、973项目(G1999035803):863重大项目(2002AA143021):“十五”国家密码发展基金.902.这里，输人变量x、下标从。开始，并且从右到左依次增大，这样主要是为了算法描述和n-12"-1实现的一致性·通项记为P,(x)二n对=x-ix-_二右x;'堵，则f(x)=乏c,P,(x)·对具体输1州牙司人x=k=艺k:2'，P,.(x),=k二(x1x-2二x'2xixo),=k}=iV0-i...k;'ko0，其中若。=0，即x,项不存在于P(x)中，则将k;'项约化为1。例如，P65(x)=P,o10(I1o1),(x)_

5、x,'xex5x4x3x,对41=x7xsxzxo召.(x)x=se=0。定理1Pi(x)-=1证明:P,(x)二‘=(x润x}'"=:x;xo)s-'=翻i'....i;.i'}对i,=0,x*项已约化为1;对i,=I，绘=I,故有,W-n-l艺在随后的定理中，我们令k=倒k;2'=(kn-1,kn2，-,k,k,)2一n=-o11，2’=(1卜】，1卜2...，i11'0)2，则P(x),zk=记NZ(k)={jIkim0,js(0,1,2,.--,n一1))入2(1)=(jIiix0,je(0,1,2,...,n一1)}，则k=艺2j,

6、i艺2'。声NZ(k,i.NZ(i)定理2若i>k，则蔽五5r)NZ(i)x4).其中NZ(k)=(0,1,2,...,n一1)一NZ(k)。证明(反证法):若NZ(k)nNZ(i)=，则NZ(i)二NZ(k)，进而i=乏2'、艺2)=k这与i>k矛盾，故NZ(k)nNZ(i)x。定理3对。Sk

7、这说明，计算x=k时多项式!(x)的值只需考虑前k个项。定理4对。<_s<_k<2'，若NZ(s)!=-NZ(k)则几(x)-k=1;否则几(x)s_,=0。证明:(I)对jENZ(s)二NZ(k)，s%=1，k%=1，因而P(x)rk=nk})=1·声NZ(,)(2)若NZ(s)dNZ(k)，则3mENZ(s)n反或k)，类似定理3的证明，凡(x)，二*=0定理5若!NZ(k)1=m，则f(x)二‘=(艺c,P(x))二*中有2”项且2"<_k+1·证明:由定理4知f(x)_。中的有效项为满足NZ(s)c_NZ(k)的项CrP(x)r,:·

8、而NZ(k)子集个数为21NZ(O=2m，每个子集对应一个:。又由m_Dlog2(k+1)J有2'<_k+1根据定理3，我们可以求出这2'个:值:对应NZ(k)，构