《第四章-分组密码-4.3--穷举攻击-密码学课件.ppt》由会员分享，可在线阅读，更多相关《第四章-分组密码-4.3--穷举攻击-密码学课件.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、密码学第四章 分组密码4.3 穷举攻击 穷举攻击穷举攻击是攻击者依次试用密钥空间中的是攻击者依次试用密钥空间中的密钥逐个对截获的密文进行脱密测试，从而找密钥逐个对截获的密文进行脱密测试，从而找出正确密钥的一种攻击方法。出正确密钥的一种攻击方法。穷举攻击是最基本的密码分析方法，它是穷举攻击是最基本的密码分析方法，它是其它攻击方法的基础，其它的密码分析方法都其它攻击方法的基础，其它的密码分析方法都是穷举攻击的变形、推广和简化。是穷举攻击的变形、推广和简化。一、穷举攻击基本思想一、穷举攻击基本思想穷举攻击的基本思想：穷举攻击的基本思想：分析者利用假设的密钥分析者利用假设的密钥 k 对密文进行脱密：对
2、密文进行脱密：k 为正确密钥为正确密钥D(c,k)=mk 为错误密钥为错误密钥D(c,k)=m 以很小的概率成立以很小的概率成立判决方法：判决方法：D(c,k)mk 一定不是正确密钥一定不是正确密钥D(c,k)=mk 可能是正确密钥可能是正确密钥一、穷举攻击基本思想一、穷举攻击基本思想穷举攻击的基本思想：穷举攻击的基本思想：分析者利用假设的密钥分析者利用假设的密钥 k 对明文进行加密：对明文进行加密：k 为正确密钥为正确密钥E(k,m)=ck 为错误密钥为错误密钥E(k,m)=c 以概率以概率p成立成立判决方法：判决方法：E(k,m)ck 一定不是正确密钥一定不是正确密钥E(k,m)=ck 可
3、能是正确密钥可能是正确密钥一、穷举攻击基本思想一、穷举攻击基本思想加密算法加密算法E，明文，明文 m 及其对应的密文及其对应的密文c，并已知其，并已知其它检验条件。它检验条件。二、穷举攻击的基本方案二、穷举攻击的基本方案已知条件：已知条件：Step2 Step2：利用其它条件对利用其它条件对 k 作进一步检验，作进一步检验，检验通过时输出检验通过时输出k，算法终止。否则返回，算法终止。否则返回 Step1Step1试试验下一个可能密钥。验下一个可能密钥。注：注：注：注：该算法是找到一个候选密钥就进行检验，只该算法是找到一个候选密钥就进行检验，只要检验通过算法就中止。因此算法一定输出一个要检验通
4、过算法就中止。因此算法一定输出一个正确密钥，但未必将密钥空间穷举。正确密钥，但未必将密钥空间穷举。算法算法 1：二、穷举攻击的基本方案二、穷举攻击的基本方案 评评价价一一个个攻攻击击算算法法的的优优劣劣主主要要有有四个密不可分的指标四个密不可分的指标:算法的成功率算法的成功率 算法的存储复杂性算法的存储复杂性 算法的数据复杂性算法的数据复杂性 算法的计算复杂性算法的计算复杂性二、穷举攻击的基本方案二、穷举攻击的基本方案存储复杂性存储复杂性数据复杂性数据复杂性 算法算法1只需存储一个明文和一个密文，因而只需存储一个明文和一个密文，因而存储复杂性可以忽略不计。存储复杂性可以忽略不计。算法算法1只需
5、一个明文和一个密文，因而数据只需一个明文和一个密文，因而数据复杂性为一对已知明密文。复杂性为一对已知明密文。二、穷举攻击的基本方案二、穷举攻击的基本方案 平均计算复杂性：平均计算复杂性：设需依次穷举的密钥为设需依次穷举的密钥为并假设正确密钥并假设正确密钥 的出现是随机的，即的出现是随机的，即二、穷举攻击的基本方案二、穷举攻击的基本方案三、不带校验的穷举攻击三、不带校验的穷举攻击加密算法加密算法E，明文，明文 m 及其对应的密文及其对应的密文c，并已知其，并已知其它检验条件。它检验条件。已知条件：已知条件：Step2Step2：返回返回Step1Step1检验下个可能密钥。当所检验下个可能密钥。
6、当所有可能密钥都检验完毕时，算法终止。有可能密钥都检验完毕时，算法终止。注：注：该算法穷举了密钥空间中所有元素，找到一该算法穷举了密钥空间中所有元素，找到一个候选密钥存储一个，算法最后输出的是一个候个候选密钥存储一个，算法最后输出的是一个候选密钥集，且正确密钥必在其中。选密钥集，且正确密钥必在其中。算法算法2：三、不带校验的穷举攻击三、不带校验的穷举攻击算法算法2的分析：的分析：成功率成功率 由于上述攻击方案对所有可能的密钥都进行了由于上述攻击方案对所有可能的密钥都进行了测试，且不会漏掉正确密钥，因而成功率为测试，且不会漏掉正确密钥，因而成功率为1 1。计算复杂性计算复杂性 由于攻击方案对所有
7、由于攻击方案对所有2K个可能的密钥都进行测个可能的密钥都进行测试试,因而计算复杂性为因而计算复杂性为2K。三、不带校验的穷举攻击三、不带校验的穷举攻击存储复杂性存储复杂性存储复杂性是候选密钥的数量。存储复杂性是候选密钥的数量。候选密钥的个数候选密钥的个数 设密钥的规模为设密钥的规模为K比特，明文分组规模为比特，明文分组规模为N比特，且比特，且 。三、不带校验的穷举攻击三、不带校验的穷举攻击 正确密钥一定是候选密钥，错误密正确密钥一定是候选密钥，错误密钥通过检验的概率为钥通过检验的概率为 .由于共有由于共有 个个错误密钥错误密钥,因而通过检验的错误密钥的期因而通过检验的错误密钥的期望个数为望个数
8、为 .这说明通过检验的这说明通过检验的候选密钥的个数近似为候选密钥的个数近似为 三、不带校验的穷举攻击三、不带校验的穷举攻击候选密钥的个数候选密钥的个数三、不带校验的穷举攻击三、不带校验的穷举攻击算法算法 3：Step1:Step1:对每个可能的密钥对每个可能的密钥 k，攻击者计算，攻击者计算 ，并判断，并判断 是否成立。不成立时，是否成立。不成立时，返回返回Step1试验下一个可能密钥，否则将试验下一个可能密钥，否则将k 作为候选作为候选密钥密钥 ，算法终止。，算法终止。注：注：该算法只要有一个密钥通过检验，就输出该该算法只要有一个密钥通过检验，就输出该密钥并中止算法。密钥并中止算法。三、不
9、带校验的穷举攻击三、不带校验的穷举攻击成功率成功率：算法算法3输出的候选密钥必然属于算法输出的候选密钥必然属于算法2输出的候选密钥集合，因此，算法输出的候选密钥集合，因此，算法3的成功率就的成功率就是输出的候选密钥恰是正确密钥的概率。是输出的候选密钥恰是正确密钥的概率。算法算法3的分析：的分析：设密钥的规模为设密钥的规模为K比特，明文分组规模为比特，明文分组规模为N比特。比特。成功率为：成功率为：成功率为：成功率为：三、不带校验的穷举攻击三、不带校验的穷举攻击计算复杂性计算复杂性算法在检测完第算法在检测完第 i 个试验密钥终止等价于个试验密钥终止等价于 且且 ，都有，都有 有有 ，因而此时上述
10、事件发生因而此时上述事件发生的概率为的概率为 ，其期望为，其期望为 。平均计算复杂性为平均计算复杂性为 。算法算法3的平均计算复杂性就近似为算法的平均计算复杂性就近似为算法1的平均计算复杂性的平均计算复杂性 。三、不带校验的穷举攻击三、不带校验的穷举攻击利用算法利用算法1进行穷举攻击进行穷举攻击 Step1 Step1：对每个可能的密钥对每个可能的密钥 ，攻击者计算攻击者计算 ，并判断，并判断 是否成立。是否成立。当它不成立时，返回试验下一个可能密钥；当它当它不成立时，返回试验下一个可能密钥；当它成立时，将成立时，将 k 作为候选密钥，并执行作为候选密钥，并执行Step2Step2 ；Step
11、2 Step2：利用其余的明密文对利用其余的明密文对 k 作译报测试，作译报测试，测试通过时输出测试通过时输出k ，算法终止。否则返回，算法终止。否则返回Step1Step1试试验下一个可能密钥。验下一个可能密钥。四、穷举攻击实例四、穷举攻击实例指标分析指标分析：成功率成功率 错误密钥通过的概率错误密钥通过的概率 ，因此通过检验的一定是正确密钥因此通过检验的一定是正确密钥 。算法算法的成功率为的成功率为1。四、穷举攻击实例四、穷举攻击实例利用算法利用算法2进行穷举攻击进行穷举攻击 Step1 Step1：对每个可能的密钥对每个可能的密钥 ，攻击者计算攻击者计算 判断下列等式是否全成立判断下列等
12、式是否全成立 当有不成立时，返回试验下一个可能密钥；当全成当有不成立时，返回试验下一个可能密钥；当全成立时，将立时，将 k 作为候选密钥；作为候选密钥；Step2 Step2：试验下一个可能密钥试验下一个可能密钥,当所有可能密钥当所有可能密钥都检验完毕时，算法终止。都检验完毕时，算法终止。四、穷举攻击实例四、穷举攻击实例指标分析：指标分析：候选密钥的个数候选密钥的个数 当利用当利用200个已知的明文分组进行穷举攻个已知的明文分组进行穷举攻击时，由于密文比特数为击时，由于密文比特数为25600比特，候选密比特，候选密钥的数量近似为钥的数量近似为 。计算复杂性计算复杂性计算复杂性为计算复杂性为2256四、穷举攻击实例四、穷举攻击实例利用算法利用算法3进行穷举攻击进行穷举攻击成功率成功率计算复杂性计算复杂性平均计算复杂性为平均计算复杂性为2255 Step1 Step1：对每个可能的密钥对每个可能的密钥 ，攻击者计算攻击者计算 判断下列等式是否全成立判断下列等式是否全成立 当有不成立时，返回试验下一个可能密钥；当全成当有不成立时，返回试验下一个可能密钥；当全成立时，将立时，将 k 作为候选密钥，算法终止。作为候选密钥，算法终止。四、穷举攻击实例四、穷举攻击实例