基于rijnel算法的s盒构造

基于rijnel算法的s盒构造

1s盒分组密码设计的一般原则s框是大多数分组密码算法中唯一的非线性组件。因此，其密码强度决定了整个分组密码算法的安全强度。S盒主要提供了分组密码算法所必须的混淆作用,但如何全面准确地度量S盒的密码强度,如何设计安全有效的S盒是分组密码设计和分析中的研究难题。纵观近几年的研究成果,S盒主要有以下一些设计准则:非线性度(Ns)、差分均匀度(δ)、代数次数及项数分布、相关免疫性等。基于以上设计准则,人们提出了许多构造方法,如随机选取并测试、使用数学函数等方法。随机选取方法要求设计者有足够的时间和计算能力;使用数学函数可以构造一些好的S盒。目前常用的此类S盒有:指数函数和对数函数、有限域GF(2n)上的逆映射以及有限域上的幂函数。高级加密标准Rijndael算法中的S盒是通过GF(28)上的乘法逆与一个可逆仿射变换合成的,它满足若干密码学性质,能够抵抗现有的各种攻击。2抗癫痫药物的结构和性能分析2.1计算：x8+1AESS盒的构造可用矩阵的形式表示如下:式(1)中的向量Y表示S盒输入向量X的乘法逆元,若将与Y相乘的矩阵设为U,则可将矩阵U简写成如下形式:其中,每个Ui都是一个含有八个元素的列向量。式(1)是将S盒的一个输入字节分两步进行变换:首先取其在GF(28)上的乘法逆,然后将其逆元通过一个仿射变换得到了S盒的一个输出字节。而仿射变换又可以写成如下的多项式形式:其中,m(x)=x8+1。从式(1)可以很容易看出v(x)=(x6+x5+x+1),下面就对u(x)进行求解:为了对式(3)所求出的u(x)进行正确性检验,下面将通过求出的u(x)来分别计算U1～U7:可见式(2)中的u(x)=x4+x3+x2+x+1是正确的。同时,经过实验验证,将式(2)与有限域上的求逆运算结合起来可以生成AESS盒中的256个元素。定理1当m(x)=xn+1时,由多项式u(x)转换成的矩阵U有以下形式:其中,U7=(U6<<1),U6=(U5<<1),…,U1=(U0<<1)。证明:Ui的多项式表示为u(x)×xi;Ui-1的多项式表示为u(x)×xi-1,由于u(x)×xi=(x·(u(x)×xi-1))mod(xn+1),所以(1)当Ui-1的最高位为0时,Ui=(Ui-1shl1)⇔Ui-1<<1;(2)当Ui-1的最高位为1时,Ui=(Ui-1shl1)♁(100…01)⇔Ui-1<<1。根据定理1可将矩阵U和向量U×Y表示成如下形式:从式(4)右端的矩阵可以看出:×Y=u0×Y♁u1×(Y<<1)♁u2×(Y<<2)♁u3×(Y<<3)♁…(u7×(Y<<7),ui=0或1。矩阵的这一特点使得构造S盒的程序运行起来速度很快,因为只要将乘法逆元集中的每个元素进行循环移位和异或运算即可。2.2aess盒的密码学性能经测试表明,AESS盒具有如下密码学性能:(1)满足整数平衡性;(2)非线性度Ns=112;(3)差分均匀度δs=2-2;(4)没有不动点和反不动点;(5)严格雪崩性,虽然S盒的每个输出比特的布尔函数均不满足SAC,但由表1可知S盒的输出比特的雪崩概率都很接近1/2。对于n×n的S盒,它们的非线性度Ns与差分均匀度δs的最优值是与n有关的。根据文献可知,当n=8时,S盒的非线性度Ns的上界(即最优值)是120,差分均匀度δs的下界是2/256。可见,AESS盒具有较好的密码学性能。本文通过将逆变换与仿射变换进行合成构造了一批密码性能良好的S盒,由定理1可知,这种构造方法最大的优点就在于它实现起来比较简单。这些4×4和6×6的S盒为进一步构造大规模的S盒提供了基础,从而为设计分组密码算法提供了丰富的非线性资源。344.s盒的结构和分析3.1x+x+1,x+1,x+1伽罗瓦域GF(24)上的既约多项式共有三个,分别是:x4+x+1,x4+x3+1和x4+x3+x2+x+1。这三个既约多项式对应的乘法逆元分别是:(0191413117615212510438)仿射变换条件(0112861541431311102975);(0115108659473141312112)在选择仿射变换时,m(x)可以是任意最高次数为4的多项式,而u(x)必须与m(x)互素,v(x)的选择只要满足:令S盒没有不动点和反不动点。假设选取的乘法逆元集是第二组,以下列出的若干对{m(x),u(x),v(x)}可以生成若干个密码性能良好的S盒(实际上远不止这些)。3.2加正形变换的44和44和44和44和44和5-5-5和5-5-5和5-2-2,5.以下是测试得到的这类4×4的S盒的密码学性能:(1)满足整数平衡性;(2)非线性度Ns=4;(3)差分均匀度δs=2-2;(4)没有不动点和反不动点。对于4×4的S盒,非线性度的上界是6,差分均匀度的下界是2-2。文献通过构造正交拉丁方表来构造基于正形变换的所有4×4的S盒,这些S盒的非线性度Ns≤4,差分均匀度δs≥2-2,然后通过软件测试的办法构造出了一大批达到这两个界并满足其他若干密码学性质的4×4的S盒。本文采用构造AESS盒的方法来构造4×4的S盒,它们的非线性度和差分均匀度都达到了文献中的两个界,但构造方法要简洁、快速得多。3.3s盒的16个可检测可适应性雪崩概率是度量分组密码抗各种攻击能力的定性指标,也是分组密码两个安全性原则(扩散原则和混乱原则)的间接体现。S盒的雪崩概率是指改变输入的1bit,输出比特改变的概率。当概率为0.5时是最理想的。用这种方法构造的没有不动点和反不动点的4×4的S盒有700多个,通过对这些S盒进行测试,发现它们的雪崩概率有如下特点:(1)绝大多数S盒的雪崩概率只包括0.25,0.5,0.75这三个值,显然,在一个S盒的16个雪崩概率值中0.5的个数越多,则S盒就越安全。(2)存在少部分S盒的雪崩概率包含0值,这种S盒的安全性比较差。生成这类S盒的{m(x),u(x),v(x)}组合满足以下条件:u(x)是一个三次既约多项式,而m(x)包含u(x)这个因子。可见,雪崩概率与v(x)和计算乘法逆元的既约多项式无关。(3)若选择既约多项式x4+x+1来生成有限域上的乘法逆元,则生成的S盒安全性最好的情况是雪崩概率的方差为0.008,这种{m(x),u(x)}组合的个数是2;最差的雪崩概率方差为0.039,{m(x),u(x)}组合的个数是8。(4)若选择的既约多项式是x4+x3+1,则安全性最好的S盒的雪崩概率的方差为0.008,{m(x),u(x)}组合的个数是3;最差的雪崩概率方差是0.039,{m(x),u(x)}组合的个数是6。(5)若选择的既约多项式是x4+x3+x2+x+1,则安全性最好的S盒的雪崩概率方差为0,这是最理想的,即S盒的16个雪崩概率值都是0.5,这种{m(x),u(x)}组合的个数是4;最差的雪崩概率方差是0.043,{m(x),u(x)}组合的个数是3。466.s盒的结构和分析4.1s盒结构4.1.1既约多项式的构造求伽罗瓦域GF(26)上的乘法逆元,首先要找到该域上的一个既约多项式。通过计算求得九个六次既约多项式,选择不同的既约多项式可以构造出多个密码学性能相似的不同的S盒。本文构造的6×6的S盒选用的既约多项式是x6+x3+1。然后利用扩展的Euclid算法求出了域上64个元素的逆元,如表2所示。4.1.2选择范围的确定首先,令m(x)=x6+1,然后是u(x)的选取,必须保证与m(x)的互素原则。这里m(x)=x6+1=(x+1)2(x2+x+1)2,从而得出u(x)的选择范围:不含(x+1)和(x2+x+1)两个因子。现列出部分满足条件的且非不可约的多项式u(x):下面以u(x)=x5+x4+x3+x+1,v(x)=x2+x为例,根据定理1,可将生成S盒的仿射变换描述成以下的矩阵形式:S盒的表格描述如表3所示。4.2差分均匀度s用此类方法构造的6×6的S盒的密码学性质如下:①S盒满足整数平衡性;②非线性度NS′=24;③差分均匀度δS′=2-2;④没有不动点;⑤S盒的雪崩概率(表4)。对于6×6的S盒,S盒的非线性度Ns的上界(即最优值)是28,差分均匀度δs的下界是2-2。可见,用这种方法构造出来的6×6的S盒的密码学性能也相当接近理想值。4.3构造s盒雪施工质量的绝对根据AESS盒的设计思想,构造了一批密码性能良好的6×6的S盒,用这种方法所构造出来的S盒之间除了雪崩概率有所改变外,其他密码学性能都一样。下面从方差的角度去分析这类S盒的雪崩概率。根据方差的定义,计算结果如下:所构造的S盒的雪崩概率的方差绝对值为0.00347。可见,构造出来的S盒的雪崩概率集中在0.5附近的程度较高,安全性也较好。六次既约多项式一共有九个,通过对它们进行穷举测试,发现S盒的雪崩概率不受v(x)的影响。以下的结论是针对m(x)=x6+1而言的:(1)由既约多项式x6+x+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有三种:0.00477,0.00586和0.00510,对应的u(x)分别有:(2)由既约多项式x6+x5+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有两种:0.00651和0.00380,对应的u(x)分别有:(3)由既约多项式x6+x3+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有两种:0.00553和0.00347,对应的u(x)分别有:(4)由既约多项式x6+x5+x3+x2+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有两种:0.00369和0.00412,对应的u(x)分别有:(5)由既约多项式x6+x5+x2+x+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有三种:0.00434,0.00347和0.00781,对应的u(x)分别有:(6)由既约多项式x6+x5+x4+x2+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有两种:0.00543和0.00347,对应的u(x)分别有:(7)由既约多项式x6+x5+x4+x+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有两种:0.00423和0.00380,对应的u(x)分别有:(8)由既约多项式x6+x4+x3+x+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有三种:0.00358,0.00467和0.00716,对应的u(x)分别有:(9)由既约多项式x6+x4+x2+x+1生成乘法逆元,构造出来的S盒雪崩概率方差的绝对值一共有三种:0.00358,0.00467和0.00716,对应的u(x)分别有:5逆元和可逆仿射变换相结合的s盒本文对Rijndael算法中S盒的构造