资源描述：
《5.7线性密码分析原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章第五章分组密码与数据加密标准分组密码与数据加密标准第七节线性密码分析原理1第五章第五章分组密码与数据加密标准分组密码与数据加密标准线性密码分析的方法是寻找一个给定密码算法的具有下列形式的“有效的”线性表达式P[i1,i2,…,ia]⊕C[j1,j2,…,jb]=K[k1,k2,…,kc](4.11)这里i1,i2,…,ia；j1,j2,…,jb和k1,k2,…,kc,表示固定的比特位置。对随机给定的明文P和相应的密文C上面的等式成立的概率p≠1/2.2第五章第五章分组密码与数据加密标准分组密码与数据加密标准需
2、要解决的问题需要解决的问题1.是否存在线性优势？2.如何求单轮变换的线性优势？3.如何求多轮变换的线性优势？3第五章第五章分组密码与数据加密标准分组密码与数据加密标准我们需要的是等式成立的概率具有非均匀的分布，所以用⏐p−1/2⏐来刻画等式的有效性(定义εi=pi−1/2为偏差).4第五章第五章分组密码与数据加密标准分组密码与数据加密标准我们把最有效的线性表达式（也就是⏐p−1/2⏐是最大的）称作最佳线性逼近式,相应的概率p称作最佳概率.为了计算等式(4.11)成立和有效的概率,我们先给出一些理论上要用到的结果.5
3、第五章第五章分组密码与数据加密标准分组密码与数据加密标准堆积引理设X1,X2,…,Xk是取值于集合{0,1}的独立随机变量.设p1,p2,….都是实数,且对所有的i,i=1,2,…,k有0≤pi≤1,再设Pr[Xi=0]=pi,则Pr[Xi=1]=1−pi.对取值于{0,1}的随机变量,用分布偏差来表示它的概率分布.随机变量Xi的偏差定义为1ε=p−ii26第五章第五章分组密码与数据加密标准分组密码与数据加密标准引理（堆积引理.Piling-uplemma）设X,......,Xii1k是独立的随机变量,εii12
4、......ik表示随机变量Xi1⊕Xi2-⊕…⊕Xi的偏差,则kkk−1εii12......ikj=2∏εij=1证明：用数学归纳法。首先k=2时……7第五章第五章分组密码与数据加密标准分组密码与数据加密标准推论设X,......,X是独立的随机变量,ii1kεii12......ik表示随机变量Xi1⊕Xi2⊕…⊕Xik的偏差,若对某个j有ε=0,则ε=0.ijii12......ik注：引理4.1只在相关随机变量是统计独立的情况下才成立.8第五章第五章分组密码与数据加密标准分组密码与数据加密标准利用堆积引理
5、,我们可以将每轮变换中偏差最大的线性逼近式进行组合,组合后的所有轮变换的线性逼近式,也将拥有最佳的偏差,即寻找分组密码的最佳线性逼近式.9第五章第五章分组密码与数据加密标准分组密码与数据加密标准S-盒的线性逼近由上述分析我们知道,分组密码的最佳线性逼近式的寻找,归结为每轮线性逼近式的寻找,而每轮的变换中,除了非线性变换(即S-盒)部分,线性部分是自然的线性关系,也就是说,每轮线性逼近式的寻找,只需寻求S-盒部分的最佳线性逼近式.10第五章第五章分组密码与数据加密标准分组密码与数据加密标准mn考虑如下一个S-盒π:{
6、0,1}→{0,1}(我们并未假s定π是一个置换,甚至也未假定m=n).m重输入smX=(x1,x2,…,xm)均匀随机地从集合{0,1}中选取,这就是说,每一个坐标xi定义了一个随机变量Xi,Xi取值于{0,1},并且其偏差ε=0即ipX(0==)(1pX==)1/2.ii11第五章第五章分组密码与数据加密标准分组密码与数据加密标准进一步,假设这m个随机变量相互独立,n重输出Y=(y1,y2,…,yn)中每一个坐标yi定义了一个随机变量Y,Y取值于{0,1}.这n个随机变量一般来说不ii是相互独立的,与Xi也不相
7、互独立.12第五章第五章分组密码与数据加密标准分组密码与数据加密标准现在考虑计算如下形式的随机变量的偏差值：mm()⊕⊕aX()⊕bYiijjii==11其中a=(a1,…,am)和b=(b1,…,bn)分别为m和n维随机向量,ai和bj为0或1.13第五章第五章分组密码与数据加密标准分组密码与数据加密标准设NL(a,b)表示满足如下条件的二元m+n组(x1,x2,…,xm,y1,…,yn)的个数:(y1,…,yn)=πs(x1,x2,…,xm)（记为条件B）且mn()aX⊕=()bY0（记为条件A）⊕⊕iijji
8、j==11则m+nmm+nP(A/B)=P(A,B)/P(B)=(NL(a,b)/2)/(2/2)m=NL(a,b)/2,14第五章第五章分组密码与数据加密标准分组密码与数据加密标准对于一个具有输入a与输出b的随机变量mm()⊕⊕aX()⊕bYiijjii==11的偏差计算公式为:mε（a,b）=NL(a,b)/2−1/2正是由于S-盒的ε（a,b）的不同,
