DES算法的安全性分析課件

1DES演算法的安全性分析

2窮舉攻擊分析窮舉攻擊就是對所有可能的密鑰逐個進行脫密測試,直到找到正確密鑰為止的一種攻擊方法.

窮舉攻擊判斷正確密鑰的方法：將利用試驗密鑰脫密得到的可能明文與已掌握的明文的資訊相比較，並將最吻合的那個試驗密鑰作為演算法輸出的正確密鑰。

窮舉攻擊又稱為窮盡攻擊、強力攻擊、蠻幹攻擊等。只要明文不是隨機的，就可實施窮舉攻擊。3窮舉攻擊的演算法

已知條件：已知密文c及對應(yīng)的明文m.

Step1

對每個可能密鑰k,計算c’=D(k,m),並判斷c’=c是否成立.不成立時返回Step1檢驗下一個可能密鑰,成立時將k作為候選密鑰,並執(zhí)行Step2.

Step2

利用其他條件對作k進一步確認.確認通過時輸出,演算法終止.否則返回Step1檢驗下一個可能密鑰.4窮舉攻擊演算法的計算複雜性定理設(shè)密鑰在密鑰空間K中服從均勻分佈，且沒有等效密鑰,則窮舉攻擊平均需要檢驗完個密鑰後才找到正確密鑰。結(jié)論:

對DES演算法的窮舉攻擊平均計算複雜性為255.5一、

Feistel模型分析Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f

1.設(shè)計容易:f函數(shù)不要求可逆,加、脫密脫演算法結(jié)構(gòu)相同；2.強度高：如果f

函數(shù)是隨機的,則連續(xù)若干圈複合形成的函數(shù)與隨機置換是無法區(qū)分的.優(yōu)點:6Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f每圈加密時輸入有一半沒有改變;左右塊的加密處理不能並行實施缺點:7Feistel模型實現(xiàn)完全性的性能分析

定義2

如果對每個密鑰k,迭代次數(shù)為m的加密變換Ek(x)的每個輸入比特的變化都可能會影響到每個輸出比特的變化,則稱Ek(x)是完全的.

意義:

實現(xiàn)了Shannon提出的擴散性原則.

擴散原則(Diffusion)

讓明文中的每一位影響密文中的盡可能多的位，或者說讓密文中的每一位都受到明文中的盡可能多位的影響。

因為在檢驗完全性時,無法對所有的密鑰都來檢驗影響的必然性,只好退而求其次,來分析這種可能性.

8結(jié)論:

(1)Feistel模型至少需要3圈才可實現(xiàn)完全性.(2)如果Feistel模型的

f函數(shù)需要T圈迭代才能實現(xiàn)完全性,則Feistel模型經(jīng)T+2圈迭代可實現(xiàn)完全性.

(3)

DES演算法需且只需5圈即可實現(xiàn)完全性!9結(jié)論:

(1)Feistel模型至少需要3圈才可實現(xiàn)完全性,且當其f函數(shù)具有完全性時,只需3圈即可實現(xiàn)完全性.證明:

設(shè)(x,y)是Feistel模型的輸入,則其第1圈至第3圈的輸出依次為如果函數(shù)f是完全的,當不考慮變換結(jié)果的抵消時,則無論改變x或y的一個比特,第3圈的輸出的左半和右半的每個比特都可能改變,這說明此時3圈能夠?qū)崿F(xiàn)完全性.10二、DES的S盒的設(shè)計標準

DES演算法的設(shè)計者迫於公眾壓力公佈的S盒的設(shè)計標準為

1.S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。

3.當固定S盒的1位輸入時，S盒的每一位輸出中0和1的個數(shù)盡可能平衡。

2.S盒的輸入發(fā)生1比特變化，輸出至少有2比特發(fā)生變化。11

1.S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。仿射函數(shù)的定義

設(shè)f是n元布爾函數(shù),如果則稱f

是仿射函數(shù);又若仿射函數(shù)滿足f(0)=0,則f為線性函數(shù).等價定義:

設(shè)f是n元布爾函數(shù),則f是仿射函數(shù)等價於存在常數(shù)c1,c2,…,cn和a使對所有x,都有此時,如果a=0,則f為線性函數(shù).

仿射函數(shù)的缺點:

(1)

輸入與輸出之間的代數(shù)關(guān)係太簡單;

(2)

輸入的變化與輸出的變化之間的代數(shù)關(guān)係太簡單.仿射函數(shù)的優(yōu)點:實現(xiàn)簡單12線性性質(zhì)是密碼設(shè)計的大敵!13S盒是DES演算法中唯一的非線性變換，是在DES演算法起核心作用的密碼變換!S盒的設(shè)計標準對於實現(xiàn)DES演算法的完全性，對於實現(xiàn)混亂和擴散原則，對於確保DES演算法的密碼強度，具有十分重要的作用。

S盒實現(xiàn)了局部的混亂和擴散；這種局部的混亂和擴散通過E盒和P盒並借助於多次迭代實現(xiàn)了整個密碼演算法的混亂和擴散。S盒只要稍有改變，其密碼強度就會大大降低，因此，不要試圖改變一個密碼演算法中的任何細節(jié)！14三、DES演算法的互補對稱性證明：由於DES的F函數(shù)具有性質(zhì)：從而DES演算法的圈函數(shù)滿足圈變換Qk故若記,則有,令D是左右塊對換,則證畢定理15互補對稱性的缺點:

結(jié)論:

利用DES演算法的互補對稱性,利用選擇明文進行窮舉攻擊時可將密鑰的加密測試量降低一半.攻擊方案:

Step1

選擇兩個明密對和

Step2

令K(0)是最低位為0的所有密鑰構(gòu)成的集合.

Step3

對K(0)中的每個元k,計算c`=Ek(m),並檢驗c`=c1是否成立.若成立,則判定k為候選密鑰;若不成立,基於利用明密對檢驗

是否為正確密鑰,即檢驗是否成立.若成立,則判定為候選密鑰,否則返回Step3檢驗K(0)中的下個元.16四、DES的加強方法

DES演算法從一出生就受到密鑰太短的責難,但NSA卻聲稱它具有足夠的安全性。儘管如此,人們?nèi)韵Ｍ麑⑵涿荑€變長。將DES演算法的密鑰變長的一個可能方法是重新設(shè)計密鑰生成演算法，但這時的密碼演算法就不再是DES了，其密碼強度必須重新分析，而且如此修改的密碼演算法無法與別人使用的DES互通，因而是不可取的。此外，DES演算法已經(jīng)做成了一個加密晶片或加密模組，如果基於這個已有的產(chǎn)品來加強DES，就可降低成本。使用不同的密鑰利用DES演算法對明文連續(xù)加密就是一種選擇方案，這就產(chǎn)生了二重DES和三重DES。171.雙重DES

雙重DES是分別用兩個不同的密鑰k1和k2對明文進行兩次DES變換以實現(xiàn)對數(shù)據(jù)的加密保護，即18

雙重DES的密鑰長度是56×2=112比特。但是,雙重DES可利用計算複雜性和存儲複雜性都為256的中間相遇攻擊方案攻破.中間相遇攻擊是一種以空間換時間的攻擊方法.雙重DES的分析19對雙重DES的中間相遇攻擊

Step1以k1的256個可能值k1為DES的密鑰對m加密,並將所得的256個加密結(jié)果DESk1(m)與所用密鑰k1一起,按加密結(jié)果的大小排序,得到有序表L={(DESk1(m),k1):k1∈{0,1}56}.

Step2對k2的每個可能值k2為DES的密鑰對c脫密,並檢查脫密結(jié)果DESk2-1

(c)是否在表L中.如果DESk2-1(c)=DESk1(m)則判定(k1,k2)為候選密鑰,否則返回Step2檢驗下個可能密鑰.直到檢驗找到正確密鑰為止.成功率=1;存儲複雜性為256,最大計算複雜性為257.數(shù)據(jù)複雜性為2個已知的明文分組.原理:20雙重DES的解密212.三重DES

該加密方案使用兩個不同的密鑰k1和k2對明文進行三次DES加