密码学,第四章 分组密码,4.3,穷举攻击,穷举攻击,是攻击者依次试用密钥空间中的密钥逐个对截获的密文进行脱密测试，从而找出正确密钥的一种攻击方法。,穷举攻击是最基本的密码分析方法，它是其它攻击方法的基础，其它的密码分析方法都是穷举攻击的变形、推广和简化。,一、穷举攻击基本思想,穷举攻击的基本思想：,分析者利用假设的密钥,k,对密文进行脱密：,k,为正确密钥,D,(,c,k,),=m,k,为错误密钥,D,(,c,k,),=m,以很小的概率成立,判决方法：,D,(,c,k,),m,k,一定不是正确密钥,D,(,c,k,),=m,k,可能是正确密钥,一、穷举攻击基本思想,穷举攻击的基本思想：,分析者利用假设的密钥,k,对明文进行加密：,k,为正确密钥,E,(,k,m,),=c,k,为错误密钥,E,(,k,m,),=c,以概率,p,成立,判决方法：,E,(,k,m,),c,k,一定不是正确密钥,E,(,k,m,),=c,k,可能是正确密钥,一、穷举攻击基本思想,加密算法,E,，明文,m,及其对应的密文,c,，并已知其它检验条件。,二、穷举攻击的基本方案,已知条件：,Step2,：,利用其它条件对,k,作进一步检验，检验通过时输出,k,，算法终止。否则返回,Step1,试验下一个可能密钥。,注：,该算法是找到一个候选密钥就进行检验，只要检验通过算法就中止。因此算法一定输出一个正确密钥，但未必将密钥空间穷举。,算法,1,：,二、穷举攻击的基本方案,评价一个攻击算法的优劣主要有四个密不可分的指标:,算法的成功率,算法的存储复杂性,算法的数据复杂性,算法的计算复杂性,二、穷举攻击的基本方案,存储复杂性,数据复杂性,算法,1,只需存储一个明文和一个密文，因而存储复杂性可以忽略不计。,算法,1,只需一个明文和一个密文，因而数据复杂性为一对已知明密文。,二、穷举攻击的基本方案,平均计算复杂性：,设需依次穷举的密钥为,并假设正确密钥 的出现是随机的，即,二、穷举攻击的基本方案,三、不带校验的穷举攻击,加密算法,E,，明文,m,及其对应的密文,c,，并已知其它检验条件。,已知条件：,Step2：,返回,Step1,检验下个可能密钥。当所有可能密钥都检验完毕时，算法终止。,注：,该算法穷举了密钥空间中所有元素，找到一个候选密钥存储一个，算法最后输出的是一个候选密钥集，且正确密钥必在其中。,算法,2,：,三、不带校验的穷举攻击,算法,2,的分析：,成功率,由于上述攻击方案对所有可能的密钥都进行了测试，且不会漏掉正确密钥，因而成功率为1。,计算复杂性,由于攻击方案对所有,2,K,个可能的密钥都进行测试,因而计算复杂性为,2,K,。,三、不带校验的穷举攻击,存储复杂性,存储复杂性是候选密钥的数量。,候选密钥的个数,设密钥的规模为,K,比特，明文分组规模为,N,比特，且 。,三、不带校验的穷举攻击,正确密钥一定是候选密钥，错误密钥通过检验的概率为 .由于共有 个错误密钥,因而通过检验的错误密钥的期望个数为 .这说明通过检验的候选密钥的个数近似为,三、不带校验的穷举攻击,候选密钥的个数,三、不带校验的穷举攻击,算法,3,：,Step1:,对每个可能的密钥,k,，攻击者计算,，并判断 是否成立。不成立时，返回,Step1,试验下一个可能密钥，否则将,k,作为候选密钥，算法终止。,注：,该算法只要有一个密钥通过检验，就输出该密钥并中止算法。,三、不带校验的穷举攻击,成功率,：,算法3输出的候选密钥必然属于算法2输出的候选密钥集合，因此，算法3的成功率就是输出的候选密钥恰是正确密钥的概率。,算法,3,的分析：,设密钥的规模为,K,比特，明文分组规模为,N,比特。,成功率为：,成功率为：,三、不带校验的穷举攻击,计算复杂性,算法在检测完第,i,个试验密钥终止等价于,且 ，都有,有 ，因而此时上述事件发生的概率为 ，其期望为 。,平均计算复杂性为,。,算法3的平均计算复杂性就近似为算法1的平均计算复杂性 。,三、不带校验的穷举攻击,利用算法,1,进行穷举攻击,Step1,：,对每个可能的密钥 ，攻击者计算 ，并判断 是否成立。当它不成立时，返回试验下一个可能密钥；当它成立时，将,k,作为候选密钥，并执行,Step2,；,Step2,：,利用其余的明密文对,k,作译报测试，测试通过时输出,k,，算法终止。否则返回,Step1,试验下一个可能密钥。,四、穷举攻击实例,指标分析,：,成功率,错误密钥通过的概率 ，因此通过检验的一定是正确密钥。算法的成功率为,1,。,四、穷举攻击实例,利用算法,2,进行穷举攻击,Step1,：,对每个可能的密钥 ，攻击者计算,判断下列等式是否全成立,当有不成立时，返回试验下一个可能密钥；当全成立时，将,k,作为候选密钥；,Step2：,试验下一个可能密钥,当所有可能密钥都检验完毕时，算法终止。,四、穷举攻击实例,指标分析：,候选密钥的个数,当利用,200,个已知的明文分组进行穷举攻击时，由于密文比特数为,25600,比特，候选密钥的数量近似为,。,计算复杂性,计算复杂性为,2,256,四、穷举攻击实例,利用算法,3,进行穷举攻击,成功率,计算复杂性,平均计算复杂性为,2,255,Step1,：,对每个可能的密钥 ，攻击者计算,判断下列等式是否全成立,当有不成立时，返回试验下一个可能密钥；当全成立时，将,k,作为候选密钥，算法终止。,四、穷举攻击实例,Thank You!,