指数域上的aes算法

指数域上的aes算法

1指数域和线性世界空间下的密码分析自提出标准dea的文件以来，研究dea的方法一直在进行。例如，文件攻击减少了轮数的aes，文件跟踪了aes加密过程中比特模型的发展，文件试图将aes的安全性等于任何时代的计算难度，并在文献中讨论了所谓的xss攻击。尽管评估专家的结果表明，dea的分析并没有结束。因为密钥学的一项重要任务是持续分析每个实际密码，并探索潜在的薄弱环节。直到密码退役。在密码学实践中,专家的论证是建立在某些前提假定之下的,比如仅考虑已知的攻击,所以真正的安全性信心是由时间累积而成的.而时间的含义则是不断出现的新的分析角度.人们已知AES对差分攻击或者线性攻击是安全的,但是从未有人断言它对任何攻击都具有免疫力.因此,将密码置于新的框架下考察是有益的,它可以提示新的角度.密码分析的第2项任务是发现密码设计者未公布的考虑.比如设计者宣称AES的仿射子层是为了消除逆元子层的不动点,但是我们在指数域上发现其作用更强.不动点在256数中仅占两数,但是仿射子层搅乱的比特数远大于此.本文通过对数映射,将明文、密文及中间结果表示在指数域上,以考察AES加密过程在指数域上的表现.自然的结果是AES原先的非线性层(即乘法逆元运算)在指数域上变成线性运算,而原先的线性层则可能成为非线性层.我们观察到指数域上的重要的非线性运算是log(exp(x)+1).这个运算的非线性复杂度是比较弱的.虽然这并不必然意味着AES的安全性的减弱,但是,这确实提供了一个新的观察角度.本文对该运算做了较系统的考察,发现了它的一些规律.本文假定读者熟悉AES算法.否则可从文献阅读AES的完整表述.为方便计,本文仅考虑128bit明文和128bit密钥.2数学基础本节为AES的数学基础,可参照文献.为读者方便计,简述如下:2.1z988.x[x]的模mx剩余域记Z为整数集,Z2?为模2剩余域,Z2?[x]为Z2?上多项式环.令m(x)=x8+x4+x3+x+1∈Z2?[x],则可以定义Z2?[x]的模m(x)剩余域如下:又记Z8228[x]为Z2?上所有次数小于8的多项式全体之集,即那么作为集合,Z8228[x]与Z2?[x]modm(x)有相同的元素.将Z8228[x]与Z2?[x]modm(x)视为等同,或者等价地说,用Z2?[x]modm(x)的加法和乘法在Z8228[x]上定义加法和乘法,则Z8228[x]构成有限域.2.2阶段a—字节整数域BYTE记BYTE∶={a∈Z|0≤a<256},则BYTE中的元素称为字节整数.这个名称来源于这样的事实:BYTE中的元素恰好可以被计算机用一个字节存储.对BYTE中的任意元素a,存在惟一的二进制分解:由此分解式可以建立BYTE到Z8228[x]的一一对应p:于是,原Z2?[x]modm(x)的加法和乘法诱导了BYTE上的加法和乘法,即对任意a,b∈BYTE,由此BYTE构成有限域.2.3型的ayte指数域型记BYTE*∶={a≠0|a∈BYTE},人们已经证明它对式(6)定义的乘法形成循环群,特别是3∈BYTE是循环群的生成元.对BYTE的任意元素a和任意自然数i,我们定义指数运算如下:其中,乘法由式(6)定义.则BYTE*={3i|0≤i<255}.这自然诱导了整数环Z255?与BYTE*之间的一一对应:将此对应扩充成Z255?∪{-∞}与BYTE之间的一一对应,为此只须定义exp(-∞)=0.将集合Z255?∪{-∞}称为BYTE的指数域,并记为AYTE.为了方便,将-∞记为十六进制的FF(即十进制255).这样,AYTE的元素在形式上就与BYTE相同了.但是,AYTE的元素与BYTE的元素服从不同的运算,特别是FF∈AYTE实际上代表-∞.在AYTE中,如果a,b≠FF,则其加法和乘法是整数环Z255?上的模255整数运算,当涉及FF时,有既然exp是AYTE到BYTE的一一对应,自然可以定义其逆运算:当然,log(0)=FF.于是,BYTE上的乘法诱导AYTE上的模255加法,BYTE上的加法诱导AYTE上的新运算,定义如下:对任意a,b∈AYTE,3aes算法的构成对于128bit的明文和密钥,AES将其分别写成4×4阵列,也就是BYTE上的4×4矩阵,分别记为E=(Eij),K=(Kij),其中,Eij,Kij∈BYTE,i,j∈Z4?={0,1,2,3},即整数的模4剩余环.下标i,j在后面有参与运算,其加法和乘法也是Z4?上模4剩余加法和乘法.对于128bit的明文和密钥,AES有10轮,每轮分AddRoundKey,ByteSub,ShiftRow,MixColumn四步,最后一轮缺MixColumn.每一步在AES提案中称为层(layer),其中ByteSub又可分为两个子层,用矩阵分量Eij表示如下:逆元子层:仿射子层:其余各层的矩阵分量表示为其中,下标i,j的运算是Z4?上模4剩余加法,矩阵L和向量b见文献,为节约篇幅不予赘述.在式(12)～(16)中,等号左边为本步操作完成后Eij的值,等号右边为本步操作前Eij的值.由上述各层构成AES算法如下:算法AES;AddRoundKey(E,RK);{加初始密钥}fori=1to9{前9轮:}ByteSub(E);ShiftRow(E);MixColumn(E);AddRoundKey(E,RK);end{for}{第10轮:}ByteSub(E);ShiftRow(E);AddRoundKey(E,RK);END{算法AES}其中,RK是轮密钥,由KeySchedule从K=(Kij)计算而得.令:则算法AES各步在BYTE上的状态被映射成AYTE上4×4矩阵,其中log函数由式(10)定义.AES在F∶=(Fij)上构成并行的状态轨迹.AES在F上的状态与E上的状态一一对应,所以安全性相同,但是它们的运算性质却不同.对式(12)～(16)取log,得到各层在指数域AYTE上的表达式:AddRoundKey层:ShiftRow层:MixColumn层:ByteSub逆元子层:其中,式(22)中的减法实际是模255剩余加法.ByteSub的仿射子层比较复杂,原线性变换式(13)即Eij∶=LEij+b也可以表示成:其中,函数LS(x)是BYTE上的循环左移,LSk(Eij)∶=LS(LSk-1(Eij)).如果把BYTE视为Z2?上的8维矢量空间,则LS(x)当然是矢量空间上的线性变换,但是从有限域角度讲,LS(x)却不是线性的,它定义为这里+和×是BYTE域上的加法和乘法.于是在AYTE上自然地表示为其中,L是LS在AYTE上的诱导运算.容易验证,所以,仿射子层基本上也可以(但是不能完全)归结为AYTE上的加法运算和∨运算.注记:式(24)～(26)中的若干数据来源如下:在AES的提案说明中,仿射子层被淡化为辅助层,仅仅起掩盖逆元子层不动点的作用.但是,如果将仿射子层修改成Eij∶=Eij+99或者Eij∶=13Eij+99,同样可以掩盖逆元子层的不动点,只不过在AYTE域上的非线性强度会削弱.这说明密码的设计者是有所考虑的.这也是密码分析者的任务,密码设计者未必会公布所有设计原理,以保持其领先的设计地位.尽管算法是公开的,但是,当其他设计者在仿效现有算法以研制新的算法时,掌握较少设计原理的设计者将可能提供强度较低的密码.比如在仿效DES的密码中,一些仿制的S盒就不如DES原有的S盒安全.因此,密码分析的第2项任务不是证明现有密码不安全,而是发掘现有密码的设计中未公布的想法.4为非线性运算.本节考察BYTE域上的线性运算+在AYTE域上诱导的非线性运算∨.其中,第4.1节将运算∨归结为更本质的非线性运算:星对偶运算.第4.2节讨论运算∨的一般性质以及与log运算、仿射子层的循环左移的关系.4.1星对偶运算third定义1.对任意i∈AYTE,记称为i的星对偶.引理1.i*=j当且仅当i∨j=0.下面的定理揭示了运算∨由星对偶运算与线性运算混合而成;定理1.对任意i,j∈AYTE,其中+、-为AYTE上的模255加减法.证明.对3i+3j=3i(1+3j-i)两边取log运算即得.证毕.关于星对偶运算的具体值,限于篇幅,在此不予赘述.我们提供简短的C语言片段如下,由读者自行生成数据:unsignedchare={1},ie={255};unsignedcharx,y;unsignedinti;for(i=1;i<255;i++){x=e[i-1];y=x∧(x<<1);if(x>>7)y∧=27;e[i]=y;ie[y]=i;}for(i=0;i<256;i++){if(i%8==0)printf(“

”);printf(“%3d*=%3d”,i,ie[e[i]∧1]);}注意运算∨是双目运算,运算结果的枚举是256×256的数据表,而星对偶运算是单目运算,运算结果的枚举仅需256个数据.这表明运算∨的非线性本质被包含在256个数据内.这实际上是非线性强度的一种度量,用于刻画非线性的数据越少,非线性强度就越弱.下面的2个定理表明,用来刻画运算∨的非线性的数据个数实际比256更少.定理2.星对偶运算满足如下性质:①对偶律:如果i*=j,则j*=i;②二倍律:如果i*=j,则(2i)*=2j;③负斜线性律:如果i*=j,则(-i)*=j-i,(-j)*=i-j.证明.注意在BYTE域上的加法实为按位异或运算,因而有a+a=0,对任意a∈BYTE.于是:①i*=j?⇔3i+1=3j⇔3i=3j+1⇔j*=i;②3i+1=3j⇔32j=(3i+1)2=32i+3i+3i+1=32i+1⇔(2i)*=2j;③3i+1=3j⇔1+3-i=3j-i⇔(-i)*=j-i.另一式类似.证毕.推论.对任意i∈AYTE,i*-(-i)*=i.证明.这是负斜线性律的等价表述.证毕.注记1.在AYTE上的二倍律有一个直观的解释:对任意a∈AYTE,2a实际上是a的循环左移.换言之,若a的二进制是(a7a6a5a4a3a2a1a0),则2a的二进制是(a6a5a4a3a2a1a0a7).所以二倍律的含义就是循环左移保持星对偶关系.此外,二倍律可以自然地推广为:如果i*=j,则(2ki)*=2kj,0≤k≤7.当k=8时,2k=256=1(mod255),重复k=0的情形.注记2.对偶律和二倍律都是线性律,这表明星对偶运算仍然包含相当多的线性成份.注意线性运算的一个重要特点是整个映射由基的像确定.星对偶运算有类似的性质.定理3.如果有AYTE上的映射p(i)适合定理2的三律,即①p(p(i))=i;②p(2i)=2p(i);③p(i)-p(-i)=i,且指定p在AYTE上9个元素的值:p(1)=25,p(5)=138,p(15)=33,p(45)=31,p(27)=104,p(49)=197,p(17)=68,p(85)=170,p(0)=FF,则p就是星对偶运算,即p(i)=i*.证明.由对偶律,p(85)=170和p(0)=FF确定了p(170)=85和p(FF)=0,从而获得4个数的值;类似地,根据定理2的三律,由p(17)=68可以推算出12个数的值;由p(15)=33和p(45)=31可以各自推算出24个数的值(共48个数的值);由p(1)=25,p(5)=138,p(27)=104和p(49)=197各自可以推算出48个数的值(共192个数的值).所以总共获得4+12+48+192=256个数的值.一方面用三律从9个元素的值计算出所有这些值,另一方面用我们前面提供的C代码求出星对偶运算的所有值,两相对照,二者完全一致,所以命题成立.证毕.我们在构造密码学意义上的非线性映射时,其实还包括“随机性”的含义.这个“随机性”很难定义,因为按照传统的理解,映射本身是确定性的.但是有一个著名的定义认为,如果在描述一个映射的各种方式中,枚举式描述所需要的字符个数最少,那么这个映射就是“随机”的.定理2,3给出了类似的刻画.如果一个映射可以从一个子集上通过若干定律推广到整个集合上,那么子集的大小和定律的繁简程度给出了“随机性”的直观度量.星对偶运算的枚举式描述是定义在256个数上的,而定理3指出,这个运算可以从9个数通过定理2的三律拓展到256个数上.而定理2的三律相当接近线性律,因此,星对偶运算的“随机性”是较弱的.同样,运算∨的“随机性”也是较弱的.4.2准ayteayte的假设根据运算∨的定义,对任意i,j,k∈AYTE,等式k=i∨j等价于BYTE上的等式3k=3i+3j.由此容易验证,运算∨满足交换律、结合律,此不赘述.众所周知,一般情况下,有限域上的指数运算有多项式时间的算法,但是离散对数运算则没有.本节对离散对数建立基于运算∨和星对偶运算的多项式时间算法,并讨论了仿射子层用运算∨表示的问题.对BYTE中的任意元素a,其二进制分解是由此获得log(a)的表达式.定理4.其中,ifak=0thenc(ak)=FF,证明.注意log(a+b)=log(a)∨log(b),log(2)=25,log(ak2k)=log(ak)+25k,以及log(1)=0,log(0)=FF,0+25k=25k,FF+25k=FF,故命题成立.证毕.注记:对运算∨来说,FF可以读做无(NULL),因为对任意i∈AYTE,i∨FF=i.在表达式中可以略去.比如,log(9)=log(8)∨log(1)=(25×3)∨0