DES加密算法的特性及其破解方案

來(lái)源：超時(shí)代軟件     更新時(shí)間：2013年01月05日 17:42:19

作者：周緋菲 潘杰；整理：超時(shí)代軟件

超時(shí)代視頻加密軟件、手機(jī)視頻加密軟件均采用比DES強(qiáng)度更高的AES加密算法加密，但是DES加密算法，仍然能給我們以啟示，學(xué)習(xí)和了解它也是非常有必要的。

 

1. DES算法原理及內(nèi)在特性

這種算法把要傳輸?shù)拿魑囊?4比特為單位進(jìn)行分組，使用64位密鑰(密鑰的實(shí)際有效位數(shù)是56位)．

 

1.1 DES算法描述

I.1.1 加密過(guò)程

首先對(duì)明文進(jìn)行初始置換；再將所得結(jié)果進(jìn)16輪處理，這16輪處理完全依賴于密鑰——先將64比特的數(shù)據(jù)等分為兩半，其中一半數(shù)據(jù)作為某個(gè)復(fù)雜函數(shù)廠(包括通過(guò)確定的8個(gè)s盒的非線性代換)的輸入，并將輸出結(jié)果和另一半數(shù)據(jù)進(jìn)行異或；*后再應(yīng)用一個(gè)末位置換獲得密文．

 

I.1.2 DES算法密鑰的生成

DES算法中每一輪迭代運(yùn)算都會(huì)使用一個(gè)子密鑰，它由用戶輸人的密鑰K產(chǎn)生．取64位K作為初始密鑰(主密鑰)，每8位中有1位奇偶檢驗(yàn)位，經(jīng)過(guò)排列選擇1(PC—1)，等分成C0和D0兩部分．將C0，D|0各循環(huán)左移1位得到cl，D1，再經(jīng)過(guò)排列選擇2(PC～2)得到密鑰K1；對(duì)C1，D1作循環(huán)左移1位后得到C2，D2，經(jīng)過(guò)PC-2得到子密鑰K2……直到產(chǎn)生子密鑰K16。

 

I.1.3 解密運(yùn)算

解密運(yùn)算與加密運(yùn)算一樣，只是所取子密鑰的順序不同．加密時(shí)候的順序是K1-K2-...-k16，解密時(shí)的順序則為Kl6-K15一...一K1。

 

1.2 DES算法的內(nèi)在特性

(1)密鑰有效長(zhǎng)度是56位(第8，l6，...，64位為校驗(yàn)位)．分組明文長(zhǎng)度為64位，而且明文、密文與密鑰存在互補(bǔ)關(guān)系．

(2)僅用16次循環(huán)迭代，使得相同明文會(huì)產(chǎn)生相同密文．

(3)存在著很好的并行結(jié)構(gòu)：產(chǎn)生內(nèi)部密鑰的左移次數(shù)存在著準(zhǔn)對(duì)稱性(即內(nèi)部密鑰生成過(guò)程存在并行性)．DES屬于傳統(tǒng)的Feistel網(wǎng)絡(luò)結(jié)構(gòu)，在DES的基本單元中能夠?qū)嵤┎⑿胁僮鳎?/p>

(4)DES有16輪加密，如果將第i輪的P置換移至下一輪后會(huì)與下一輪的E擴(kuò)展操作進(jìn)行合并，簡(jiǎn)化算法的基本操作．(5)可以通過(guò)S盒與P置換合并的方法節(jié)省P置換的基本操作時(shí)間·

 

2. 常見(jiàn)的DES算法破解方法

2.1 利用密鑰的使用誤區(qū)進(jìn)行攻擊

(1)通過(guò)DES密鑰的8位校驗(yàn)位進(jìn)行攻擊．DES算法只用到64位密鑰中的56位，第8,16，…，64等8個(gè)位并未參與DES的運(yùn)算，即計(jì)算密鑰時(shí)第8，l6，…，64位等8個(gè)位被忽略．例：取密鑰Key為8個(gè)0x30，明文為8個(gè)0x31，用DES算法加密后明文變?yōu)?5 5e a6 28?cf 62 58 5f。若加密密鑰Key變?yōu)?個(gè)0x31則執(zhí)行DES后的密文也是如此．同理，若加密密文為65 5e a6 28 cf 62 58 5f，無(wú)論用8個(gè)0x30作為解密密鑰還是用8個(gè)0x31作為解密密鑰，均能還原出8個(gè)0x31的原始明文．由此可見(jiàn)，DES的安全性是依靠除密鑰Key的第8，16，…，64位以外的其余56位組合變化得以保證的．如果在應(yīng)用中使用密鑰的第8，16，…，64位作為有效數(shù)據(jù)位，則容易被黑客利用8位校驗(yàn)位進(jìn)行攻擊．

 

(2)通過(guò)窮舉法攻擊．因?yàn)镈ES算法的明文、密文與密鑰存在互補(bǔ)關(guān)系(若c=DESk(m)，m'為m的補(bǔ)，c'是c的補(bǔ)，則c'=DESk(m'))如果用戶使用互補(bǔ)密鑰，窮舉法破解的工作量會(huì)減少一半．另外，DES產(chǎn)生內(nèi)部密鑰的左移次數(shù)存在準(zhǔn)對(duì)稱性，黑客在基本單元里可以利用窮舉攻擊中的并行原理來(lái)加速搜索密鑰空間的搜索速度．再有，用戶為提高運(yùn)行速度會(huì)將DES中一些基本操作合并、簡(jiǎn)化(如：P排列與擴(kuò)展置換的合并以及S盒與P置換的合并)，這樣會(huì)降低窮舉攻擊的硬件代價(jià)，并且會(huì)提高黑客對(duì)密鑰空間的搜索速度．

 

2.2 通過(guò)比較法攻擊

因?yàn)镈ES算法的迭代次數(shù)少，會(huì)出現(xiàn)相同明文產(chǎn)生相同密文的現(xiàn)象．如果黑客獲得一個(gè)真正的單詞明碼正文列表的字典文件，然后把這些單詞用所有的符合DES標(biāo)準(zhǔn)的加密程序進(jìn)行加密并把每個(gè)加密的單詞與目標(biāo)口令比較——如果匹配，則該目標(biāo)口令很有可能被破解。另外黑客可以使用差分密碼和線性密碼分析方法來(lái)破解．

 

2.3 利用生成子密鑰時(shí)產(chǎn)生的弱密鑰與半弱密鑰攻擊

如果使用者在生成子密鑰時(shí)不注意密鑰的檢查，會(huì)產(chǎn)生弱密鑰或半弱密鑰，黑客可以利用這些弱密鑰與半弱密鑰對(duì)密文進(jìn)行解密．DES算法中，至少有4個(gè)弱密鑰k滿足DESk(DESk(m))=m

 

(因?yàn)樵诋a(chǎn)生子密鑰時(shí)初始密鑰被分為兩半，以后各自獨(dú)立移位．如果每一半都是0或1，則所有子密鑰都相同)．這些弱密鑰是

0101010101010101

1F1F1F1F0E0E0E0E

E0E0EOEOF1F1F1F1

FEFEFEFEFEFEFEFE

如果加密過(guò)程中出現(xiàn)弱密鑰，則下一次加密的結(jié)果是將本次加密后的密文還原．另外，DES算法中存在至少l2個(gè)半弱密鑰對(duì)(滿足DESk(m)=DESk的-1次方(m)的密鑰對(duì)k與k')，黑客可以利用半弱密鑰將使用其他密鑰加密的信息進(jìn)行解密．所以使用者在使用DES進(jìn)行加密的時(shí)候要注意子密鑰的檢查，以防產(chǎn)生弱密鑰與半弱密鑰．

 

如今傳統(tǒng)的DES算法雖然已經(jīng)被攻破，但其提供的加密算法思路仍可為今后設(shè)計(jì)其他加密算法提供借鑒．之后出現(xiàn)的加密算法如RSA等密鑰位已經(jīng)達(dá)到2048位以上，安全性有所提升，破解方法有所不同．