线性密码分析-中国科学技术大学.ppt

1、网络信息安全,中国科学技术大学肖 明 军,2,第二章 信息加密技术（4）,本节学习目标：掌握常用密码分析相关知识对称密码分析：DES非对称密码分析：RSA,3,基本概念,Kerckhoff假设通常假定密码分析者或敌手知道所使用的密码系统攻击类型（攻击强度递增）唯密文攻击：密码分析者有一个或多个密文已知明文攻击：密码分析者有一些明文以及相应的密文选择明文攻击：密码分析者有机会使用密码机，因此可选择一些明文，并产生密文选择密文攻击：密码分析者有机会使用密码机，因此可选择一些密文，并产生明文,4,分组密码的分析方法,典型的攻击方法强力攻击方法差分密码分析线性密码分析差分-线性密码分析,5,强力攻击,

2、强力攻击可用于任何分组密码，攻击复杂度只依赖于分组长度和密码长度穷尽密钥搜索攻击：攻击者试用密钥空间中的所有密钥解密一个或多个密文，直至得到一个或多个有意义的明文。字典攻击：攻击者搜集明密文对，编排成字典，遇到密文时查找字典获得明文,6,强力攻击,查表攻击：采用选择明文攻击，对给定明文，用所有可能的密钥，计算密文，并建立密钥和密文的表，通过密文查表获得密钥时间-存储权衡攻击：是一种选择明文攻击，由穷尽密钥搜索攻击和查表攻击两种方法混合而成，在选择明文攻击中以时间换空间，比穷尽密钥搜索攻击时间复杂度小，比查表攻击空间复杂度小,7,差分密码分析,差分密码分析基本原理差分密码分析是已知的攻击跌代密码

3、（所谓跌代密码就是以跌代一个简单的轮函数为基础的密码，即通过选择某个较简单的密码变换，在密钥控制下以跌代方式多次利用它进行加密变换）最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特,8,差分密码分析,对分组长度为n的r轮跌代密码，设Y0和Y0*是明文对，Yi和Yi*(1ir)是第i轮的输出，第i+1轮的输入，第i轮的子密钥为Ki，轮函数为F，即Yi=F(Yi-1,Ki)定义1 差分：Yi=YiYi*-1，其中表示n比特串集上的一个特定群运算， Yi*-1表示Yi*在此群中的逆元研究结果表明，对于Yi=F(Yi-1,Ki)和Yi*=F(Yi-1*,Ki)

4、，若三元组(Yi-1, Yi, Yi*)的一个或多个值是已知的，则确定子密钥Ki是容易的。从而，若密文对已知，并且最后一轮的输入对的差分能够得到，则一般来说，确定最后一轮的子密钥或其一部分是可行的。在差分密码分析中，通过选择具有特定差分值a0的明文对(Y0, Y0*)，使得最后一轮的输入差分Yr-1以很高的概率取特定值ar-1来达到这一点,9,差分密码分析,定义2 r-轮特征是一个差分序列a0,a1,ar，其中ai是Yi和Yi*(0ir)的差分。 r-轮特征=a0,a1,ar的概率是指在明文Y0和子密钥K1,Kr独立、均匀随机时，明文对Y0和Y0*的差分为a0的条件下，Yi和Yi* *(0ir

5、)的差分为ai的概率定义3 如果 r-轮特征=a0,a1,ar满足条件： Y0和Y0*的差分为a0，第i轮输出Yi和Yi*的差分为ai(1ir)，则称明文对Y0和Y0*为特征的一个正确对，否则称为特征的错误对定义4 1=a0,a1,am和2=b0,b1,bl分别是m轮和l轮特征，如果am=b0，则1和2可以串联为一个m+l的轮特征3=a0,a1,am, b0,b1,bl。3称为1和2的串联,10,差分密码分析,定义5 在r-轮特征=a0,a1,ar中，定义pi=P(F(Y)=ai | Y=ai-1)，即pi表示在输入差分为ai-1的条件下，轮函数F的输出差分为ai的概率注意：由于轮函数F与子密

6、钥有关，所以pi是对所有可能的子密钥而言的。对某些密码体制，选取合适的群运算能保证对所有可能的子密钥值，此概率是常值。实际中，r-轮特征=a0,a1,ar的概率可用pi来近似替代，因此r-轮特征可以看作r个单轮特征的串联，它的概率是r个单轮特征概率的乘积。,11,差分密码分析,R轮迭代密码的差分攻击算法第1步：找出一个(r-1)轮特征=a0,a1,ar-1，使得它的概率达到最大或几乎最大第2步：均匀随机地选择明文Y0并计算Y0*，使得Y0和Y0*的差分为a0，找出Y0和Y0*在实际密钥加密下所得的密文Yr和Yr*。若最后一轮的子密钥Kr(或Kr的部分比特)有2m个可能值Krj(1j2m)，设置

7、相应的2m个计数器j(1j2m)；用每个Krj解密密文Yr和Yr*，得到Yr-1和Yr-1*，如果Yr-1和Yr-1*的差分是ar-1，则给相应的计数器j加1。第3步：重复第2步，直到一个或几个计数器的值明显高于其他计数器的值，输出它们所对应的子密钥（或部分比特）,12,DES的差分密码分析,差分密码分析最初是针对DES提出的一种攻击方法，它虽然未能破译16-轮的DES，但是破译轮数低的DES是很成功的（8轮的在个人计算机上只要几分钟）。属于选择明文攻击,13,DES的差分密码分析原理,由于DES中的初始置换IP及其逆置换IP-1是公开的，所以在密码分析时可以忽略。设n轮DES，L0R0为明文

8、，LnRn为密文，差分分析的基本观点是比较两个明文的异或与相应的两个密文的异或。定义6 设Sj是一个特定的S-盒(1j 8)，(Bj, Bj*)是一对长度为6比特的串。我们说Sj的输入异或是BjBj*， Sj的输出异或是Sj(Bj) Sj(Bj*)。对于任何BjZ26，记(Bj)=(Bj,Bj*)|BjBj*=Bj。易知，|(Bj)| =26 =64，且(Bj)=(Bj, BjBj)|BjZ26。对(Bj)中的每一对，我们能计算出Sj的一个输出异或，共可计算出64个输出异或，它们分布在24=16个可能的值上，将这些分布列成表。这些分布的不均匀性将是差分密码攻击的基础。,14,DES的差分密码分

9、析原理,例1 设第一个S盒S1的输入异或为110100，那么(110100)=(0000 00, 110100),(000001,110101),(111111,001011)。对集合(110100)中的每一个有序对，计算S1的输出异或，获得输出异或分布一般，如果我们固定一个S-盒Sj和一个输入异或Bj，那么平均来讲，所有可能的输出异或中实际上出现大约75%-80%。定义7 对于1j8，长度为6比特的串Bj和长度为4比特的串Cj，定义INj(Bj, Cj)=BjZ26|Sj(Bj)Sj(BjBj)=Cj，Nj(Bj,Cj)=|INj(Bj, Cj)|，表示对S盒Sj具有输入异或为Bj，输出异或

10、为Cj的对的数量。,15,DES的差分密码分析原理,对于8个S盒，每一个都有64个可能的输入异或，共需计算512个分布，可以通过计算机很容易地算出。如IN1(110100, C1)的分布为,16,DES的差分密码分析原理,在第i轮， S-盒的输入可写成B=EJ，其中E=E(Ri-1)是的Ri-1扩展，J=Ki由第i轮的密钥比特构成。此时，输入异或可通过下式来计算：BB*=(EJ)(E*J)=EE*即，输入异或不依赖于密钥比特J。(输出异或会依赖这些密钥比特)将B，B*，E，E*，J 和J*均写成长度为6比特的串的级联。如B=B1B2B3B4B5B6B7B8，E=E1E2E3E4E5E6E7E8

11、，假设对某一j，1j 8，我们知道Ej、Ej*的值和Sj的输出异或Sj(Bj) Sj(Bj*)=Cj，则必有EjJjINj(Ej, Cj)，其中Ej= EjEj*=BB*=Bj定义8 设Ej和Ej*是两个长度为6比特的串，Cj是一个长度为4比特的串，定义testj(Ej,Ej*,Cj)=BjEj|BjINj(Ej,Cj)，这里Ej=Ej Ej*。testj(Ej,Ej*,Cj)也就是Ej和集合INj(Ej,Cj)中的每一个元素取异或所得的异或值构成的集合,17,DES的差分密码分析原理,定理2 设Ej和Ej*是S盒Sj的两个输入，Sj的输出异或是Cj，记Ej=EjEj*，则密钥比特Jj出现在集

12、合testj(Ej,Ej*,Cj)中，即Jjtestj(Ej,Ej*,Cj)在集合testj(Ej,Ej*,Cj)中恰有Nj(Ej,Cj)个长度为6比特的串，Jj的正确值必定是这些可能值中之一例2 设E1=000001，E1*=110101，C1=1101。因为N1(110100,1101) =8，所以在集合test1(000001,110101,1101)中恰有8个比特串。查表知，IN1(110100,1101)= 000110,010000,010110, 011100,100010, 100100,101000,110010，因此，test1(000001, 110101,1101)=0

13、00 111,010001,010111,011101,100011,100101,101001,110011。如果有第二个这样的三重组E1,E1*,C1，那么我们能获得包含密钥比特J1的第二个集合test2，则J1必定是在这两个集合的交集之中。如果我们有一些这样的三重组，那么就能很快地确定J1中的密钥比特,18,3轮DES的差分密码分析,设L0R0和L0*R0*是两对明文，对应的密文分别为L3R3和L3*R3*。可将R3表示为R3=L2f(R2,K3)=R1f(R2,K3)=L0f(R0,K1)f(R2,K3)。同样地，R3*=L0*f(R0*,K1)f(R2*,K3)。因此，R3=R3R3

14、*=L0f(R0, K1)f(R0*,K1)f(R2,K3)f(R2*,K3)，其中L0=L0L0*。现在假定我们选择明文使得R0=R0*,即R0=R0R0*=000，则R3=L0f(R2,K3)f(R2*,K3)。因为L0,L0*,R3,R3*已知，所以R3和L0可计算出。这样f(R2,K3)f(R2*, K3)可由下式算出： f(R2,K3)f(R2*,K3)=R3L0。又f(R2,K3)=P(C)，f(R2*,K3)=P(C*),C,C*分别表示8个S盒的两个输出，所以P(C)P(C*)=R3L0。而P是固定的、公开的、线性的，故CC*=P-1(R3L0)，这正是3轮DES的8个盒的输出

15、异或,19,3轮DES的差分密码分析,由DES算法知，R2=L3和R2*=L3*，所以我们能使用公开知道的扩展函数E计算E=E(L3)和E*=E(L3*)对3轮DES的第3轮，我们已经知道了E,E*和C，现在的问题是构造testj，1j8，Jjtestj。算法如下：输入：L0R0，L0*R0*，L3R3和L3*R3*，其中R0=R0*计算C=P-1(R3L0);计算E=E(L3)和E*=E(L3*);对1j8，计算testj(Ej,Ej*,Cj)通过建立8个具有64个计数器的计数矩阵，最终只能确定K3中的68=48比特密钥，而其余的56-48=8比特可通过搜索28=256种可能的情况来确定,2

16、0,3轮DES的差分密码分析,例3 已知3对3轮DES的明文和密文，分析密钥,21,3轮DES的差分密码分析,从第1对计算第3轮S盒的输入，分别是E=E(L3)=000000000111111000001110100000000110100000001100E*=E(L3*)=101111110000001010101100000001010100000001010010S盒的输出异或是C=CC*=P-1(R3L0)=10010110010111010101101101100111从第2对计算第3轮S盒的输入，分别是E=1010000010111111111101000001010100000

17、01011110110E*=100010100110101001011110101111110010100010101010S盒的输出异或是C=10011100100111000001111101010110,22,3轮DES的差分密码分析,从第3对计算第3轮S盒的输入，分别是E=111011110001010100000110100011110110100101011111E*=000001011110100110100010101111110101011000000100S盒的输出异或是C=11010101011101011101101100101011现在建立8个具有64个计数器的计数矩

18、阵，将这3对中的每一对都进行计数。在第1对中，我们有E1=101111,C1=1001。IN1(101111,1001)=000000,000111,101000,101111。因为E1=000000，所以J1test1(000000,101111,1001)=000000,000111,101000,101111。因此，我们在J1的计数矩阵中的位置0，7，40和47处增加1(长度为6的比特串看作0到63之间的整数的二元表示),23,3轮DES的差分密码分析,24,3轮DES的差分密码分析,25,3轮DES的差分密码分析,26,3轮DES的差分密码分析,27,3轮DES的差分密码分析,在8个计

19、数矩阵的每一个中，都有唯一的一个计数器具有值3，这些计数器的位置确定J1,J2,J8中的密钥比特，这些位置分别是47,5,19,0,24, 7,7,49。将其转化为二进制，可获得J1,J2,J8： J1=101111,J2=000101,J3=010011,J4=000000,J5=011000,J6=000111,J7=000111,J8=110001。现在通过查找第3轮的密钥方案构造出密钥的48比特。密钥K具有如下形式：0001101 0110001 01?01?0 1?001000101001 0000?0 111?11? ?100011这里已略去了校验比特，“?”表示一个未知的密钥比特

20、。完全的密钥是1A624C89520DEC46,28,差分密码分析,差分密码分析可以分析多于3轮的DES，8轮DES需要214个选择明文，10轮、14轮和16轮分别需要224、231、239和247个选择明文才能破译差分密码分析的推广截断差分密码分析：对某些密码体制，寻找高概率的差分几乎是不可能的，但如果知道几比特差值的特性，就可以利用截断差分密码分析高阶差分密码分析：将差分密码分析推广到高阶,29,线性密码分析,本质上是一种已知明文攻击的方法可用221个已知明文破译8轮DES，可用247个已知明文破译16轮DES。基本思想：通过寻找一个给定密码算法的有效的线性近似表达式来破译系统,30,线性

21、密码分析,设明文分组长度和密文分组长度都为n比特，密钥分组长度为m比特。记随机给定的明文分组为P1,Pn，相应的密文分组为C1, Cn，密钥分组为K1,Km，定义Ai,j,k=AiAj Ak。线性密码分析的目标就是找出以下形式的有效线性方程：Pi1,i2,iaCj1,j2,jb=Kk1,k2,kc （*）其中1an， 1bn， 1cm。如果方程成立的概率p1/2，则称该方程是有效的线性逼近。如果|p-1/2|是最大的，则称该方程是最有效的线性逼近。,31,线性密码分析,如果我们获得一个有效的线性表达式，则可以通过下列的基于最大似然方法的算法推测出一个密钥比特 ：设N表示明文数，T是使方程左边为

22、0的明文数。如果TN/2，则令如果TN/2，则令从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于密钥的一组线性方程，从而确定出密钥比特。,32,线性密码分析,研究表明，当|p-1/2|充分小时，攻击成功的概率是这一概率只依赖于sqrt(N)|p-1/2|，并随着N或|p-1/2|的增加而增加公式（*）成立的概率可以用堆积引理来计算：设Xi(1in)是相互独立的随机变量，且P(Xi=0)=pi， P(Xi=1)=1-pi，则,33,RSA密码分析,RSA体制的安全性完全依赖于大整数分解问题只是一个推测，目前，还未能从数学上证明c和e计算出m一定需要分解n。但是，如果存

23、在新的方法能使密码分析者推算出d，它则成为大数分解的新方法通过猜测(n) =(p-1)(q-1)的值，可以攻击RSA体制，但这种方法并不比分解n容易分解n是最显而易见的攻击方法，目前，155位的整数已被分解密码分析者完全可能去尝试每一个可能的d，但这种强力攻击还不如分解n有效,34,RSA密码分析,n的选择要选择足够大的n，就要选择足够大的p和q。在选择p和q时，首先它们应该是随机素数并且不包含在素数表中。另外，两个素数不应该太接近，当p和q接近时n很容易就分解。因为n=pq=(p+q)2/4-(p-q)2/4，当(p-q)/2很小时，t=(p+q)/2只比根号n稍大一点，此时逐个检验大于根号

24、n的整数x，直到找到一个，使得x2-n是一个平方数，记为y2，则p=x+y，q=x-y。例如，若n=311313，则根号n=311.998，而3122-n=1，因此直接得到p=313，q=311,35,RSA密码分析,p和q的选择也必须考虑到可能的基于重复加密的攻击。这个方法是从密文c开始反复计算它的e次幂，可得一旦出现 ，就有 ，即在出现c之前的计算结果就是明文m。当t不是很大的时候，这种攻击是可行的。 就是 。若m模n的阶为k，则 。t可取的最小值就是e模k的阶，必须使这个阶尽可能大。e模k的阶是(k)的因子，所以最好(k)中有大的素因子。又由于k是m模n的阶，因而k是(n) =(p-1)

25、(q-1)的因子，所以，最好选择p和q使得p-1和q-1分别有大素因子p和q并且p-1和q-1也有大素因子,36,RSA密码分析,对RSA体制的选择密文攻击方法1E窃听A的通讯过程，并设法收集到一个用她公钥加密的密文c，为了恢复c的明文m，E首先选取一个小于n的随机数r并用A的公钥加密计算得如果 ，则 。然后E让A用它的密钥对y签名。A将 发送给E。现在E计算于是E就获得了m,37,RSA密码分析,方法2E想让A对m3签名，她产生两份电文m1、m2，使得m3=m1m2(mod n)如果E能让A对m1、m2签名，则能计算m3的签名m3d(mod n)=(m1dmod n)(m2dmod n)因此

26、：绝对不要对一个陌生人提交给你的随机文件签名，而应该总是首先使用一个单向Hash函数,38,RSA密码分析,RSA的共模攻击若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互素(一般情况下都成立)，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则： C1 = Pe1 mod n C2 = Pe2 mod n 密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，故用Euclidean算法能找到r和s，满足： r * e1 + s * e2 = 1 假设r为负

27、数，需再用Euclidean算法计算C1-1，则 ( C1-1) -r * C2s = P mod n,39,RSA密码分析,RSA的低指数攻击如果公钥e取较低的值，会使RSA体制的加密及签名验证加快，但也会导致不安全。Hastad给出了对小加密密钥的RSA体制的成功攻击方法，证明了如果用具有相同一个值e的不同的公钥来加密多于e(e+1)/2个线性相关的消息(消息具有形式aim+bi，其中ai和bi已知)，将使窃密者能够恢复出消息对具有小解密指数d的RSA攻击，由Wiener给出。但如果e和d是随机选取的，则使Wiener攻击成功的情况很少发生；如果e的值很小时，这种情况则不可能发生为了防止低

28、指数攻击，首先在加密明文之前，用随机值做填充，并保证使明文长度大约与n的长度相同，同时要选择大的d值,40,MD5密码分析,已知一杂凑函数H有n个可能的输出，H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为1-1-1/nk1-1-k/n=k/n。所以当概率为0.5时，k=n/2。如果H的输出为m比特长，即可能的输出个输n=2m，则k=2m-1,41,MD5密码分析,生日悖论生日悖论是考虑这样一个问题：在k个人中至少有两个人的生日相同的概率大于0.5时，k至少多大

29、？事实上，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相（大多数人会认为，23人中有2人生日相同的概率应该远远小于50%）抵触的意义上，它才称得上是一个悖论。计算与此相关的概率被称为生日问题， 在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。N个数中，随机选择k个，有两个相同的概率为P(n,k)=1-n!/(n-k)!nk)，令P(n,k)0.

30、5，可得k=1.18sqrt(n) sqrt(n) ，当n=365，则k=1.18sqrt(365) 22.54。,42,MD5密码分析,生日攻击设用户A用自己的密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发送给接受者敌手对A发送的消息M产生出2m/2个变形的消息，每个消息的消息本质上的涵义与原消息相同，同时敌手还准备一个假冒的消息M，并对假冒消息产生2m/2个变形的消息敌手在产生的两个消息集合中，找出杂凑值相同的一对消息M1，M2，由上述讨论可知敌手成功的概率大于0.5。如果不成功，则重新产生一个假冒消息，并产生变形消息，直到找到杂凑值相同的一对消息为止敌手将M1提交给A请求签字，由于M1和M2的杂凑值相同，所以可将A对M1的签字当作对M2的签字，将此签字连同M2一起发给意欲的接受者。,43,作业,请写出3轮DES加密以及差分分析步骤请写出RSA密钥生成及加解密步骤,