分組密碼 43窮舉攻擊

1、密碼學(xué)第四章 分組密碼4.3 窮舉攻擊 窮舉攻擊窮舉攻擊是攻擊者依次試用密鑰空間中的是攻擊者依次試用密鑰空間中的密鑰逐個(gè)對截獲的密文進(jìn)行脫密測試，從而找密鑰逐個(gè)對截獲的密文進(jìn)行脫密測試，從而找出正確密鑰的一種攻擊方法。出正確密鑰的一種攻擊方法。 窮舉攻擊是最基本的密碼分析方法，它是窮舉攻擊是最基本的密碼分析方法，它是其它攻擊方法的基礎(chǔ)，其它的密碼分析方法其它攻擊方法的基礎(chǔ)，其它的密碼分析方法都是窮舉攻擊的變形、推廣和簡化。都是窮舉攻擊的變形、推廣和簡化。 一、窮舉攻擊基本思想一、窮舉攻擊基本思想 密碼分析者的已知條件密碼分析者的已知條件（1）所需密文所需密文（2）明文統(tǒng)計(jì)特性明文統(tǒng)計(jì)特性（3）

2、密碼算法密碼算法（4）密鑰空間及其統(tǒng)計(jì)特性密鑰空間及其統(tǒng)計(jì)特性對密碼分析者來說，只有密鑰是保密的。對密碼分析者來說，只有密鑰是保密的。一、窮舉攻擊基本思想一、窮舉攻擊基本思想分析者利用假設(shè)的密鑰分析者利用假設(shè)的密鑰 k 對密文進(jìn)行脫密：對密文進(jìn)行脫密：k 為正確密鑰為正確密鑰D(c, k) = mk 為錯(cuò)誤密鑰為錯(cuò)誤密鑰D(c, k) = m 以很小的概率成立以很小的概率成立判決方法：判決方法：D(c, k) mk 一定不是正確密鑰一定不是正確密鑰D(c, k) = mk 可能是正確密鑰可能是正確密鑰一、窮舉攻擊基本思想一、窮舉攻擊基本思想分析者利用假設(shè)的密鑰分析者利用假設(shè)的密鑰 k 對明文進(jìn)

3、行加密：對明文進(jìn)行加密：k 為正確密鑰為正確密鑰E(k, m) = ck 為錯(cuò)誤密鑰為錯(cuò)誤密鑰E(k, m) = c 以概率以概率p成立成立判決方法：判決方法：E(k, m) ck 一定不是正確密鑰一定不是正確密鑰E(k, m) = ck 可能是正確密鑰可能是正確密鑰一、窮舉攻擊基本思想一、窮舉攻擊基本思想加密算法加密算法E，明文，明文 m 及其對應(yīng)的密文及其對應(yīng)的密文c，并已知，并已知其它檢驗(yàn)條件。其它檢驗(yàn)條件。二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案已知條件：已知條件：對每個(gè)可能的密鑰對每個(gè)可能的密鑰 k，攻擊者計(jì)算，攻擊者計(jì)算 并判斷并判斷 是否成立。當(dāng)它不成是否成立。當(dāng)它不成立時(shí)，

4、返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)它成立時(shí)，立時(shí)，返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)它成立時(shí)，將將 k 作為候選密鑰，并執(zhí)行作為候選密鑰，并執(zhí)行 cmkE),(cc 算法算法 1：二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案利用其它條件對利用其它條件對 k 作進(jìn)一步檢驗(yàn)，作進(jìn)一步檢驗(yàn)，檢驗(yàn)通過時(shí)輸出檢驗(yàn)通過時(shí)輸出k，算法終止。否則返回，算法終止。否則返回 試驗(yàn)下一個(gè)可能密鑰。試驗(yàn)下一個(gè)可能密鑰。該算法是找到一個(gè)候選密鑰就進(jìn)行檢驗(yàn)，只該算法是找到一個(gè)候選密鑰就進(jìn)行檢驗(yàn)，只要檢驗(yàn)通過算法就中止。因此算法一定輸出一個(gè)要檢驗(yàn)通過算法就中止。因此算法一定輸出一個(gè)正確密鑰，但未必將密鑰空間窮舉。正確密鑰，但未必將密鑰空間

5、窮舉。 算法算法 1：二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案 評價(jià)一個(gè)攻擊算法的優(yōu)劣主要有評價(jià)一個(gè)攻擊算法的優(yōu)劣主要有四個(gè)密不可分的指標(biāo)四個(gè)密不可分的指標(biāo): : 算法的成功率算法的成功率 算法的存儲(chǔ)復(fù)雜性算法的存儲(chǔ)復(fù)雜性 算法的數(shù)據(jù)復(fù)雜性算法的數(shù)據(jù)復(fù)雜性 算法的計(jì)算復(fù)雜性算法的計(jì)算復(fù)雜性二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案算法算法1的分析：的分析： 由于算法由于算法1一定能找到正確密鑰，一定能找到正確密鑰，故其成功率為故其成功率為1 1。二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案 算法算法1只需存儲(chǔ)一個(gè)明文和一個(gè)密文，因而只需存儲(chǔ)一個(gè)明文和一個(gè)密文，因而存儲(chǔ)復(fù)雜性可以忽略不計(jì)。

6、存儲(chǔ)復(fù)雜性可以忽略不計(jì)。 算法算法1只需一個(gè)明文和一個(gè)密文，因而數(shù)據(jù)只需一個(gè)明文和一個(gè)密文，因而數(shù)據(jù)復(fù)雜性為一對已知明密文。復(fù)雜性為一對已知明密文。二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案以所需要檢驗(yàn)的密鑰個(gè)數(shù)來衡量計(jì)算復(fù)雜性。以所需要檢驗(yàn)的密鑰個(gè)數(shù)來衡量計(jì)算復(fù)雜性。設(shè)密鑰的規(guī)模為設(shè)密鑰的規(guī)模為K 比特，明文分組規(guī)模為比特，明文分組規(guī)模為N比特。比特。 最小計(jì)算復(fù)雜性為最小計(jì)算復(fù)雜性為 1 1 最大計(jì)算復(fù)雜性為最大計(jì)算復(fù)雜性為K2二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案 平均計(jì)算復(fù)雜性：平均計(jì)算復(fù)雜性： ( )E21()KiipiKiKi212112212KK設(shè)需依次窮舉的密鑰為設(shè)需依

7、次窮舉的密鑰為并假設(shè)正確密鑰并假設(shè)正確密鑰 的出現(xiàn)是隨機(jī)的，即的出現(xiàn)是隨機(jī)的，即122,Kkkkk1()2Kpi二、窮舉攻擊的基本方案二、窮舉攻擊的基本方案三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊加密算法加密算法E，明文，明文 m 及其對應(yīng)的密文及其對應(yīng)的密文c，并已知，并已知其它檢驗(yàn)條件。其它檢驗(yàn)條件。已知條件：已知條件：對每個(gè)可能的密鑰對每個(gè)可能的密鑰k ，攻擊者計(jì)算，攻擊者計(jì)算并判斷并判斷 是否成立。當(dāng)它不成是否成立。當(dāng)它不成立時(shí)，返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)它成立時(shí)，立時(shí)，返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)它成立時(shí)，將將 k 作為候選密鑰。作為候選密鑰。cmkE),(cc 算法算法2：三、不

8、帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊返回返回檢驗(yàn)下個(gè)可能密鑰。當(dāng)所檢驗(yàn)下個(gè)可能密鑰。當(dāng)所有可能密鑰都檢驗(yàn)完畢時(shí)，算法終止。有可能密鑰都檢驗(yàn)完畢時(shí)，算法終止。注：注：該算法窮舉了密鑰空間中所有元素，找到一該算法窮舉了密鑰空間中所有元素，找到一個(gè)候選密鑰存儲(chǔ)一個(gè)，算法最后輸出的是一個(gè)候個(gè)候選密鑰存儲(chǔ)一個(gè)，算法最后輸出的是一個(gè)候選密鑰集，且正確密鑰必在其中。選密鑰集，且正確密鑰必在其中。 算法算法2：三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊算法算法2的分析：的分析：成功率成功率由于上述攻擊方案對所有可能的密鑰都進(jìn)行由于上述攻擊方案對所有可能的密鑰都進(jìn)行了測試，且不會(huì)漏掉正確密鑰，因而成功率為了

9、測試，且不會(huì)漏掉正確密鑰，因而成功率為1 1。計(jì)算復(fù)雜性計(jì)算復(fù)雜性 由于攻擊方案對所有由于攻擊方案對所有2K個(gè)可能的密鑰都進(jìn)行測個(gè)可能的密鑰都進(jìn)行測試試, ,因而計(jì)算復(fù)雜性為因而計(jì)算復(fù)雜性為2K。 三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊存儲(chǔ)復(fù)雜性存儲(chǔ)復(fù)雜性存儲(chǔ)復(fù)雜性是候選密鑰的數(shù)量。存儲(chǔ)復(fù)雜性是候選密鑰的數(shù)量。 候選密鑰的個(gè)數(shù)候選密鑰的個(gè)數(shù) 設(shè)密鑰的規(guī)模為設(shè)密鑰的規(guī)模為K比特，明文分組規(guī)模為比特，明文分組規(guī)模為N比特，且比特，且 。 ( ,)2Np E k mc三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊 正確密鑰一定是候選密鑰，錯(cuò)誤密正確密鑰一定是候選密鑰，錯(cuò)誤密鑰通過檢驗(yàn)的概率為鑰通

10、過檢驗(yàn)的概率為 . .由于共有由于共有 個(gè)個(gè)錯(cuò)誤密鑰錯(cuò)誤密鑰, ,因而通過檢驗(yàn)的錯(cuò)誤密鑰的期因而通過檢驗(yàn)的錯(cuò)誤密鑰的期望個(gè)數(shù)為望個(gè)數(shù)為 . .這說明通過檢驗(yàn)的這說明通過檢驗(yàn)的候選密鑰的個(gè)數(shù)近似為候選密鑰的個(gè)數(shù)近似為 2N21K(21)2KN1 (21) 212KNKN 三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊(1)KN121KN(2)KN121KN三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊 當(dāng)利用當(dāng)利用1個(gè)已知的明文分組進(jìn)行窮舉攻擊個(gè)已知的明文分組進(jìn)行窮舉攻擊時(shí)，由于密文比特?cái)?shù)為時(shí)，由于密文比特?cái)?shù)為128比特，候選密鑰的比特，候選密鑰的數(shù)量近似為數(shù)量近似為 。256 128128212

11、當(dāng)利用當(dāng)利用2個(gè)已知的明文分組進(jìn)行窮舉攻擊個(gè)已知的明文分組進(jìn)行窮舉攻擊時(shí)，由于密文比特?cái)?shù)為時(shí)，由于密文比特?cái)?shù)為256比特，候選密鑰的比特，候選密鑰的數(shù)量近似為數(shù)量近似為 。256 256212 當(dāng)利用當(dāng)利用3個(gè)已知的明文分組進(jìn)行窮舉攻擊個(gè)已知的明文分組進(jìn)行窮舉攻擊時(shí)，由于密文比特?cái)?shù)為時(shí)，由于密文比特?cái)?shù)為384比特，候選密鑰的比特，候選密鑰的數(shù)量近似為數(shù)量近似為 。256 38412821211 例如，對具有例如，對具有256比特密鑰，比特密鑰，128比特明文比特明文分組的分組的AES算法。算法。三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊算法算法 3：對每個(gè)可能的密鑰對每個(gè)可能的密鑰 k ，攻

12、擊者計(jì)算，攻擊者計(jì)算 ，并判斷，并判斷 是否成立。不成立時(shí)，是否成立。不成立時(shí)，返回返回Step1試驗(yàn)下一個(gè)可能密鑰，否則將試驗(yàn)下一個(gè)可能密鑰，否則將k 作為候選作為候選密鑰密鑰 ，算法終止。，算法終止。cmkE),(cc 注：注：該算法只要有一個(gè)密鑰通過檢驗(yàn)，就輸出該該算法只要有一個(gè)密鑰通過檢驗(yàn)，就輸出該密鑰并中止算法。密鑰并中止算法。三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊成功率成功率：算法算法3輸出的候選密鑰必然屬于算法輸出的候選密鑰必然屬于算法2輸出的候選密鑰集合，因此，算法輸出的候選密鑰集合，因此，算法3的成功率就的成功率就是輸出的候選密鑰恰是正確密鑰的概率。是輸出的候選密鑰恰是

13、正確密鑰的概率。算法算法3的分析：的分析： 設(shè)密鑰的規(guī)模為設(shè)密鑰的規(guī)模為K比特，明文分組規(guī)模為比特，明文分組規(guī)模為N比特。比特。(1)KN121KN成功率為：成功率為：(2)KN1121KN成功率為：成功率為：三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊計(jì)算復(fù)雜性計(jì)算復(fù)雜性算法在檢測完第算法在檢測完第 i 個(gè)試驗(yàn)密鑰終止等價(jià)于個(gè)試驗(yàn)密鑰終止等價(jià)于 且且 ，都有，都有( ,)iE k mcti ( ,)tE k mc2N(1)KN 有有 ， 因而此時(shí)上述事件因而此時(shí)上述事件發(fā)生的概率為發(fā)生的概率為 ，其期望值為，其期望值為 。 平均計(jì)算復(fù)雜性為平均計(jì)算復(fù)雜性為 。( ,):( ,)2Np k m

14、E k mc1()2(1 2)NNipi2N(2)KN 算法算法3的平均計(jì)算復(fù)雜性就近似為算法的平均計(jì)算復(fù)雜性就近似為算法1的平均計(jì)算復(fù)雜性的平均計(jì)算復(fù)雜性 。12K三、不帶校驗(yàn)的窮舉攻擊三、不帶校驗(yàn)的窮舉攻擊 以密鑰規(guī)模為以密鑰規(guī)模為256比特比特, ,分組規(guī)模為分組規(guī)模為128比特比特的的AES算法為例，介紹窮舉攻擊的實(shí)現(xiàn)方案。算法為例，介紹窮舉攻擊的實(shí)現(xiàn)方案。 條件：條件：已知已知200200個(gè)明文分組個(gè)明文分組及對應(yīng)的密文分組及對應(yīng)的密文分組 。12200,c cc12200,m mm目的目的: :求解加密密鑰求解加密密鑰 。Tk四、窮舉攻擊實(shí)例四、窮舉攻擊實(shí)例利用算法利用算法1進(jìn)行窮

15、舉攻擊進(jìn)行窮舉攻擊對每個(gè)可能的密鑰對每個(gè)可能的密鑰 ，攻擊者計(jì)算攻擊者計(jì)算 ，并判斷，并判斷 是否成立。是否成立。當(dāng)它不成立時(shí)，返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)它當(dāng)它不成立時(shí)，返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)它成立時(shí)，將成立時(shí)，將 k 作為候選密鑰，并執(zhí)行作為候選密鑰，并執(zhí)行256(0,1,21)k k 11( ,)E k mc11cc 利用其余的明密文對利用其余的明密文對 k 作譯報(bào)測試，作譯報(bào)測試，測試通過時(shí)輸出測試通過時(shí)輸出k ，算法終止。否則返回，算法終止。否則返回試試驗(yàn)下一個(gè)可能密鑰。驗(yàn)下一個(gè)可能密鑰。四、窮舉攻擊實(shí)例四、窮舉攻擊實(shí)例 成功率成功率 錯(cuò)誤密鑰通過的概率錯(cuò)誤密鑰通過的概率 ，因此通

16、過檢驗(yàn)的一定是正確密鑰因此通過檢驗(yàn)的一定是正確密鑰 。 算法算法的成功率為的成功率為1。2001281()02四、窮舉攻擊實(shí)例四、窮舉攻擊實(shí)例計(jì)算復(fù)雜性計(jì)算復(fù)雜性計(jì)算復(fù)雜性平均為計(jì)算復(fù)雜性平均為 2552存儲(chǔ)復(fù)雜性存儲(chǔ)復(fù)雜性存儲(chǔ)復(fù)雜性為存儲(chǔ)復(fù)雜性為200個(gè)明密對。個(gè)明密對。最小計(jì)算復(fù)雜性為最小計(jì)算復(fù)雜性為1最大計(jì)算復(fù)雜性為最大計(jì)算復(fù)雜性為2562四、窮舉攻擊實(shí)例四、窮舉攻擊實(shí)例利用算法利用算法2進(jìn)行窮舉攻擊進(jìn)行窮舉攻擊對每個(gè)可能的密鑰對每個(gè)可能的密鑰 ，攻擊者計(jì)算攻擊者計(jì)算 判斷下列等式是否全成立判斷下列等式是否全成立 當(dāng)有不成立時(shí)，返回試驗(yàn)下一個(gè)可能密鑰；當(dāng)全成當(dāng)有不成立時(shí)，返回試驗(yàn)下一個(gè)可

17、能密鑰；當(dāng)全成立時(shí)，將立時(shí)，將 k 作為候選密鑰；作為候選密鑰；試驗(yàn)下一個(gè)可能密鑰試驗(yàn)下一個(gè)可能密鑰, ,當(dāng)所有可能密當(dāng)所有可能密鑰都檢驗(yàn)完畢時(shí)，算法終止。鑰都檢驗(yàn)完畢時(shí)，算法終止。256(0,1,21)k k 11( ,),E k mc11,cc 22( ,),E k mc200200,( ,)E k mc22,cc 200200,cc四、窮舉攻擊實(shí)例四、窮舉攻擊實(shí)例 候選密鑰的個(gè)數(shù)候選密鑰的個(gè)數(shù) 當(dāng)利用當(dāng)利用200個(gè)已知的明文分組進(jìn)行窮舉攻個(gè)已知的明文分組進(jìn)行窮舉攻擊時(shí)，由于密文比特?cái)?shù)為擊時(shí)，由于密文比特?cái)?shù)為25600比特，候選密比特，候選密鑰的數(shù)量近似為鑰的數(shù)量近似為 。256 25600211 計(jì)算復(fù)雜性計(jì)算復(fù)雜性計(jì)算復(fù)雜性為計(jì)算復(fù)雜性為2256四、窮舉攻擊實(shí)例四、窮舉攻擊實(shí)例利用算法利用算法3進(jìn)行窮舉攻擊進(jìn)行窮舉攻擊成功率