分组密码 43穷举攻击

1、密码学第四章 分组密码4.3 穷举攻击 穷举攻击穷举攻击是攻击者依次试用密钥空间中的是攻击者依次试用密钥空间中的密钥逐个对截获的密文进行脱密测试，从而找密钥逐个对截获的密文进行脱密测试，从而找出正确密钥的一种攻击方法。出正确密钥的一种攻击方法。 穷举攻击是最基本的密码分析方法，它是穷举攻击是最基本的密码分析方法，它是其它攻击方法的基础，其它的密码分析方法其它攻击方法的基础，其它的密码分析方法都是穷举攻击的变形、推广和简化。都是穷举攻击的变形、推广和简化。 一、穷举攻击基本思想一、穷举攻击基本思想 密码分析者的已知条件密码分析者的已知条件（1）所需密文所需密文（2）明文统计特性明文统计特性（3）

2、密码算法密码算法（4）密钥空间及其统计特性密钥空间及其统计特性对密码分析者来说，只有密钥是保密的。对密码分析者来说，只有密钥是保密的。一、穷举攻击基本思想一、穷举攻击基本思想分析者利用假设的密钥分析者利用假设的密钥 k 对密文进行脱密：对密文进行脱密：k 为正确密钥为正确密钥D(c, k) = mk 为错误密钥为错误密钥D(c, k) = m 以很小的概率成立以很小的概率成立判决方法：判决方法：D(c, k) mk 一定不是正确密钥一定不是正确密钥D(c, k) = mk 可能是正确密钥可能是正确密钥一、穷举攻击基本思想一、穷举攻击基本思想分析者利用假设的密钥分析者利用假设的密钥 k 对明文进

3、行加密：对明文进行加密：k 为正确密钥为正确密钥E(k, m) = ck 为错误密钥为错误密钥E(k, m) = c 以概率以概率p成立成立判决方法：判决方法：E(k, m) ck 一定不是正确密钥一定不是正确密钥E(k, m) = ck 可能是正确密钥可能是正确密钥一、穷举攻击基本思想一、穷举攻击基本思想加密算法加密算法E，明文，明文 m 及其对应的密文及其对应的密文c，并已知，并已知其它检验条件。其它检验条件。二、穷举攻击的基本方案二、穷举攻击的基本方案已知条件：已知条件：对每个可能的密钥对每个可能的密钥 k，攻击者计算，攻击者计算 并判断并判断 是否成立。当它不成是否成立。当它不成立时，

4、返回试验下一个可能密钥；当它成立时，立时，返回试验下一个可能密钥；当它成立时，将将 k 作为候选密钥，并执行作为候选密钥，并执行 cmkE),(cc 算法算法 1：二、穷举攻击的基本方案二、穷举攻击的基本方案利用其它条件对利用其它条件对 k 作进一步检验，作进一步检验，检验通过时输出检验通过时输出k，算法终止。否则返回，算法终止。否则返回 试验下一个可能密钥。试验下一个可能密钥。该算法是找到一个候选密钥就进行检验，只该算法是找到一个候选密钥就进行检验，只要检验通过算法就中止。因此算法一定输出一个要检验通过算法就中止。因此算法一定输出一个正确密钥，但未必将密钥空间穷举。正确密钥，但未必将密钥空间

5、穷举。 算法算法 1：二、穷举攻击的基本方案二、穷举攻击的基本方案 评价一个攻击算法的优劣主要有评价一个攻击算法的优劣主要有四个密不可分的指标四个密不可分的指标: : 算法的成功率算法的成功率 算法的存储复杂性算法的存储复杂性 算法的数据复杂性算法的数据复杂性 算法的计算复杂性算法的计算复杂性二、穷举攻击的基本方案二、穷举攻击的基本方案算法算法1的分析：的分析： 由于算法由于算法1一定能找到正确密钥，一定能找到正确密钥，故其成功率为故其成功率为1 1。二、穷举攻击的基本方案二、穷举攻击的基本方案 算法算法1只需存储一个明文和一个密文，因而只需存储一个明文和一个密文，因而存储复杂性可以忽略不计。

6、存储复杂性可以忽略不计。 算法算法1只需一个明文和一个密文，因而数据只需一个明文和一个密文，因而数据复杂性为一对已知明密文。复杂性为一对已知明密文。二、穷举攻击的基本方案二、穷举攻击的基本方案以所需要检验的密钥个数来衡量计算复杂性。以所需要检验的密钥个数来衡量计算复杂性。设密钥的规模为设密钥的规模为K 比特，明文分组规模为比特，明文分组规模为N比特。比特。 最小计算复杂性为最小计算复杂性为 1 1 最大计算复杂性为最大计算复杂性为K2二、穷举攻击的基本方案二、穷举攻击的基本方案 平均计算复杂性：平均计算复杂性： ( )E21()KiipiKiKi212112212KK设需依次穷举的密钥为设需依

7、次穷举的密钥为并假设正确密钥并假设正确密钥 的出现是随机的，即的出现是随机的，即122,Kkkkk1()2Kpi二、穷举攻击的基本方案二、穷举攻击的基本方案三、不带校验的穷举攻击三、不带校验的穷举攻击加密算法加密算法E，明文，明文 m 及其对应的密文及其对应的密文c，并已知，并已知其它检验条件。其它检验条件。已知条件：已知条件：对每个可能的密钥对每个可能的密钥k ，攻击者计算，攻击者计算并判断并判断 是否成立。当它不成是否成立。当它不成立时，返回试验下一个可能密钥；当它成立时，立时，返回试验下一个可能密钥；当它成立时，将将 k 作为候选密钥。作为候选密钥。cmkE),(cc 算法算法2：三、不

8、带校验的穷举攻击三、不带校验的穷举攻击返回返回检验下个可能密钥。当所检验下个可能密钥。当所有可能密钥都检验完毕时，算法终止。有可能密钥都检验完毕时，算法终止。注：注：该算法穷举了密钥空间中所有元素，找到一该算法穷举了密钥空间中所有元素，找到一个候选密钥存储一个，算法最后输出的是一个候个候选密钥存储一个，算法最后输出的是一个候选密钥集，且正确密钥必在其中。选密钥集，且正确密钥必在其中。 算法算法2：三、不带校验的穷举攻击三、不带校验的穷举攻击算法算法2的分析：的分析：成功率成功率由于上述攻击方案对所有可能的密钥都进行由于上述攻击方案对所有可能的密钥都进行了测试，且不会漏掉正确密钥，因而成功率为了

9、测试，且不会漏掉正确密钥，因而成功率为1 1。计算复杂性计算复杂性 由于攻击方案对所有由于攻击方案对所有2K个可能的密钥都进行测个可能的密钥都进行测试试, ,因而计算复杂性为因而计算复杂性为2K。 三、不带校验的穷举攻击三、不带校验的穷举攻击存储复杂性存储复杂性存储复杂性是候选密钥的数量。存储复杂性是候选密钥的数量。 候选密钥的个数候选密钥的个数 设密钥的规模为设密钥的规模为K比特，明文分组规模为比特，明文分组规模为N比特，且比特，且 。 ( ,)2Np E k mc三、不带校验的穷举攻击三、不带校验的穷举攻击 正确密钥一定是候选密钥，错误密正确密钥一定是候选密钥，错误密钥通过检验的概率为钥通

10、过检验的概率为 . .由于共有由于共有 个个错误密钥错误密钥, ,因而通过检验的错误密钥的期因而通过检验的错误密钥的期望个数为望个数为 . .这说明通过检验的这说明通过检验的候选密钥的个数近似为候选密钥的个数近似为 2N21K(21)2KN1 (21) 212KNKN 三、不带校验的穷举攻击三、不带校验的穷举攻击(1)KN121KN(2)KN121KN三、不带校验的穷举攻击三、不带校验的穷举攻击 当利用当利用1个已知的明文分组进行穷举攻击个已知的明文分组进行穷举攻击时，由于密文比特数为时，由于密文比特数为128比特，候选密钥的比特，候选密钥的数量近似为数量近似为 。256 128128212

11、当利用当利用2个已知的明文分组进行穷举攻击个已知的明文分组进行穷举攻击时，由于密文比特数为时，由于密文比特数为256比特，候选密钥的比特，候选密钥的数量近似为数量近似为 。256 256212 当利用当利用3个已知的明文分组进行穷举攻击个已知的明文分组进行穷举攻击时，由于密文比特数为时，由于密文比特数为384比特，候选密钥的比特，候选密钥的数量近似为数量近似为 。256 38412821211 例如，对具有例如，对具有256比特密钥，比特密钥，128比特明文比特明文分组的分组的AES算法。算法。三、不带校验的穷举攻击三、不带校验的穷举攻击算法算法 3：对每个可能的密钥对每个可能的密钥 k ，攻

12、击者计算，攻击者计算 ，并判断，并判断 是否成立。不成立时，是否成立。不成立时，返回返回Step1试验下一个可能密钥，否则将试验下一个可能密钥，否则将k 作为候选作为候选密钥密钥 ，算法终止。，算法终止。cmkE),(cc 注：注：该算法只要有一个密钥通过检验，就输出该该算法只要有一个密钥通过检验，就输出该密钥并中止算法。密钥并中止算法。三、不带校验的穷举攻击三、不带校验的穷举攻击成功率成功率：算法算法3输出的候选密钥必然属于算法输出的候选密钥必然属于算法2输出的候选密钥集合，因此，算法输出的候选密钥集合，因此，算法3的成功率就的成功率就是输出的候选密钥恰是正确密钥的概率。是输出的候选密钥恰是

13、正确密钥的概率。算法算法3的分析：的分析： 设密钥的规模为设密钥的规模为K比特，明文分组规模为比特，明文分组规模为N比特。比特。(1)KN121KN成功率为：成功率为：(2)KN1121KN成功率为：成功率为：三、不带校验的穷举攻击三、不带校验的穷举攻击计算复杂性计算复杂性算法在检测完第算法在检测完第 i 个试验密钥终止等价于个试验密钥终止等价于 且且 ，都有，都有( ,)iE k mcti ( ,)tE k mc2N(1)KN 有有 ， 因而此时上述事件因而此时上述事件发生的概率为发生的概率为 ，其期望值为，其期望值为 。 平均计算复杂性为平均计算复杂性为 。( ,):( ,)2Np k m

14、E k mc1()2(1 2)NNipi2N(2)KN 算法算法3的平均计算复杂性就近似为算法的平均计算复杂性就近似为算法1的平均计算复杂性的平均计算复杂性 。12K三、不带校验的穷举攻击三、不带校验的穷举攻击 以密钥规模为以密钥规模为256比特比特, ,分组规模为分组规模为128比特比特的的AES算法为例，介绍穷举攻击的实现方案。算法为例，介绍穷举攻击的实现方案。 条件：条件：已知已知200200个明文分组个明文分组及对应的密文分组及对应的密文分组 。12200,c cc12200,m mm目的目的: :求解加密密钥求解加密密钥 。Tk四、穷举攻击实例四、穷举攻击实例利用算法利用算法1进行穷

15、举攻击进行穷举攻击对每个可能的密钥对每个可能的密钥 ，攻击者计算攻击者计算 ，并判断，并判断 是否成立。是否成立。当它不成立时，返回试验下一个可能密钥；当它当它不成立时，返回试验下一个可能密钥；当它成立时，将成立时，将 k 作为候选密钥，并执行作为候选密钥，并执行256(0,1,21)k k 11( ,)E k mc11cc 利用其余的明密文对利用其余的明密文对 k 作译报测试，作译报测试，测试通过时输出测试通过时输出k ，算法终止。否则返回，算法终止。否则返回试试验下一个可能密钥。验下一个可能密钥。四、穷举攻击实例四、穷举攻击实例 成功率成功率 错误密钥通过的概率错误密钥通过的概率 ，因此通

16、过检验的一定是正确密钥因此通过检验的一定是正确密钥 。 算法算法的成功率为的成功率为1。2001281()02四、穷举攻击实例四、穷举攻击实例计算复杂性计算复杂性计算复杂性平均为计算复杂性平均为 2552存储复杂性存储复杂性存储复杂性为存储复杂性为200个明密对。个明密对。最小计算复杂性为最小计算复杂性为1最大计算复杂性为最大计算复杂性为2562四、穷举攻击实例四、穷举攻击实例利用算法利用算法2进行穷举攻击进行穷举攻击对每个可能的密钥对每个可能的密钥 ，攻击者计算攻击者计算 判断下列等式是否全成立判断下列等式是否全成立 当有不成立时，返回试验下一个可能密钥；当全成当有不成立时，返回试验下一个可

17、能密钥；当全成立时，将立时，将 k 作为候选密钥；作为候选密钥；试验下一个可能密钥试验下一个可能密钥, ,当所有可能密当所有可能密钥都检验完毕时，算法终止。钥都检验完毕时，算法终止。256(0,1,21)k k 11( ,),E k mc11,cc 22( ,),E k mc200200,( ,)E k mc22,cc 200200,cc四、穷举攻击实例四、穷举攻击实例 候选密钥的个数候选密钥的个数 当利用当利用200个已知的明文分组进行穷举攻个已知的明文分组进行穷举攻击时，由于密文比特数为击时，由于密文比特数为25600比特，候选密比特，候选密钥的数量近似为钥的数量近似为 。256 25600211 计算复杂性计算复杂性计算复杂性为计算复杂性为2256四、穷举攻击实例四、穷举攻击实例利用算法利用算法3进行穷举攻击进行穷举攻击成功率