DES算法的安全性分析課件

1DES演算法的安全性分析

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

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

窮舉攻擊又稱為窮盡攻擊、強(qiáng)力攻擊、蠻幹攻擊等。只要明文不是隨機(jī)的，就可實(shí)施窮舉攻擊。3窮舉攻擊的演算法

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

Step1

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

Step2

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

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

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

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

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

定義2

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

意義:

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

擴(kuò)散原則(Diffusion)

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

因?yàn)樵跈z驗(yàn)完全性時(shí),無(wú)法對(duì)所有的密鑰都來(lái)檢驗(yàn)影響的必然性,只好退而求其次,來(lái)分析這種可能性.

8結(jié)論:

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

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

(3)

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

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

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

DES演算法的設(shè)計(jì)者迫於公眾壓力公佈的S盒的設(shè)計(jì)標(biāo)準(zhǔn)為

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

結(jié)論:

利用DES演算法的互補(bǔ)對(duì)稱性,利用選擇明文進(jìn)行窮舉攻擊時(shí)可將密鑰的加密測(cè)試量降低一半.攻擊方案:

Step1

選擇兩個(gè)明密對(duì)和

Step2

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

Step3

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

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

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

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

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

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

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

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

該加密方案使用兩個(gè)不同的密鑰k1和k2對(duì)明文進(jìn)行三次DES加