【安全課件】第9講--des安全性

1、王王 濱濱2002005 5年年3 3月月1818日日主要內(nèi)容主要內(nèi)容 窮舉攻擊分析窮舉攻擊分析 FeistelFeistel模型分析模型分析 S S盒的設(shè)計標(biāo)準(zhǔn)盒的設(shè)計標(biāo)準(zhǔn) DESDES算法的互補對稱性算法的互補對稱性 DESDES算法的加強方案算法的加強方案-多重多重DESDES122K一、一、 FeistelFeistel模型分析模型分析Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f 1.1. 設(shè)計容易設(shè)計容易: :f f 函數(shù)不要求可逆函數(shù)不要求可逆, ,加、脫密脫算法加、脫密脫算法結(jié)構(gòu)相同；結(jié)構(gòu)相同； 2. 2.強度高：如果強度高：如果f f 函數(shù)是隨機的函數(shù)是隨

2、機的, ,則連續(xù)若干圈復(fù)則連續(xù)若干圈復(fù)合形成的函數(shù)與隨機置換是無法區(qū)分的合形成的函數(shù)與隨機置換是無法區(qū)分的. .優(yōu)點優(yōu)點:Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f 每圈加密時輸入有一半沒有改變每圈加密時輸入有一半沒有改變; 左右塊的加密處理不能并行實施左右塊的加密處理不能并行實施缺點缺點:Feistel模型實現(xiàn)完全性的性能分析模型實現(xiàn)完全性的性能分析 定義定義2 如果對每個密鑰如果對每個密鑰k,迭代次數(shù)為迭代次數(shù)為m的加密變的加密變換換Ek(x)的每個輸入比特的變化都的每個輸入比特的變化都可能可能會影響到每個輸會影響到每個輸出比特的變化出比特的變化,則稱則稱 Ek(x

3、)是完全的是完全的. 意義意義: 實現(xiàn)了實現(xiàn)了Shannon提出的擴散性原則提出的擴散性原則. 讓明文中的每一位影響密文中的盡可能多的位，讓明文中的每一位影響密文中的盡可能多的位，或者說讓密文中的每一位都受到明文中的盡可能多位或者說讓密文中的每一位都受到明文中的盡可能多位的影響。的影響。 因為在檢驗完全性時因為在檢驗完全性時,無法對所有的密鑰都來檢驗無法對所有的密鑰都來檢驗影響的必然性影響的必然性, 只好退而求其次只好退而求其次,來分析這種可能性來分析這種可能性. 結(jié)論結(jié)論: (1) Feistel模型至少需要模型至少需要3圈才可實現(xiàn)圈才可實現(xiàn)完全性完全性. (2) 如果如果Feistel模型

4、的模型的 f 函數(shù)需要函數(shù)需要T圈圈迭代才能實現(xiàn)完全性迭代才能實現(xiàn)完全性,則則Feistel模型經(jīng)模型經(jīng)T+2圈圈迭代可實現(xiàn)完全性迭代可實現(xiàn)完全性. (3) DES算法需且只需算法需且只需5圈即可實現(xiàn)完圈即可實現(xiàn)完全性全性! 結(jié)論結(jié)論: (1) Feistel模型至少需要模型至少需要3圈才可實現(xiàn)完全性圈才可實現(xiàn)完全性,且當(dāng)其且當(dāng)其f 函數(shù)具有完全性時函數(shù)具有完全性時,只需只需3圈即可實現(xiàn)完全性圈即可實現(xiàn)完全性. 證明證明: 設(shè)設(shè)(x,y)是是Feistel模型的輸入模型的輸入,則其第則其第1圈至第圈至第3圈圈的輸出依次為的輸出依次為11212113211: ( ,( )2: ( ),( )3:

5、( ),( )( )kkkkkkkkkky xfyxfyyfxfyyfxfyxfyfyfxfy第圈輸出第圈輸出第圈輸出 如果函數(shù)如果函數(shù)f是完全的是完全的, 當(dāng)不考慮變換結(jié)果的抵消時當(dāng)不考慮變換結(jié)果的抵消時,則無則無論改變論改變x或或y的一個比特的一個比特, 第第3圈的輸出的左半和右半的每個圈的輸出的左半和右半的每個比特都可能改變比特都可能改變,這說明此時這說明此時3圈能夠?qū)崿F(xiàn)完全性圈能夠?qū)崿F(xiàn)完全性.二、二、DES的的S盒的設(shè)計標(biāo)準(zhǔn)盒的設(shè)計標(biāo)準(zhǔn) DES算法的設(shè)計者迫于公眾壓力公布的算法的設(shè)計者迫于公眾壓力公布的S盒的設(shè)計標(biāo)盒的設(shè)計標(biāo)準(zhǔn)為準(zhǔn)為 1. S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。盒

6、的每一位輸出都不是輸入的線性或仿射函數(shù)。 3. 當(dāng)固定當(dāng)固定S盒的盒的1位輸入時，位輸入時，S盒的每一位輸出中盒的每一位輸出中0和和1的的個數(shù)盡可能平衡。個數(shù)盡可能平衡。 2. S盒的輸入發(fā)生盒的輸入發(fā)生1比特變化，輸出至少有比特變化，輸出至少有2比特發(fā)生變比特發(fā)生變化。化。 1. S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。盒的每一位輸出都不是輸入的線性或仿射函數(shù)。 仿射函數(shù)的仿射函數(shù)的定義定義 設(shè)設(shè) f是是n元布爾函數(shù)元布爾函數(shù),如果如果則稱則稱f 是仿射函數(shù)是仿射函數(shù);又若仿射函數(shù)滿足又若仿射函數(shù)滿足f(0)=0,則則 f 為線性函數(shù)為線性函數(shù).,x 都有()( )( )(0)f xf

7、xf af 等價定義等價定義: 設(shè)設(shè) f是是n元布爾函數(shù)元布爾函數(shù),則則 f是仿射函數(shù)等價于是仿射函數(shù)等價于存在常數(shù)存在常數(shù)c1,c2,cn和和a使對所有使對所有x,都有都有此時此時,如果如果a=0,則則 f為線性函數(shù)為線性函數(shù).1 12 2( )n nf xcxc xc xa 仿射函數(shù)的缺點仿射函數(shù)的缺點: (1) 輸入與輸出之間的代數(shù)關(guān)系太簡單輸入與輸出之間的代數(shù)關(guān)系太簡單; (2) 輸入的輸入的變化變化與輸出的與輸出的變化變化之間的代數(shù)關(guān)系太簡單之間的代數(shù)關(guān)系太簡單. 仿射函數(shù)的優(yōu)點仿射函數(shù)的優(yōu)點: 實現(xiàn)簡單實現(xiàn)簡單線性性質(zhì)是密碼設(shè)計的大敵線性性質(zhì)是密碼設(shè)計的大敵! S盒是盒是DES算法

8、中唯一的非線性變換，是在算法中唯一的非線性變換，是在DES算法起核心作用的密碼變換算法起核心作用的密碼變換! S盒的設(shè)計標(biāo)準(zhǔn)對于實現(xiàn)盒的設(shè)計標(biāo)準(zhǔn)對于實現(xiàn)DES算法的完全性，對算法的完全性，對于實現(xiàn)混亂于實現(xiàn)混亂和擴散和擴散原則，對于確保原則，對于確保DES算法的密碼算法的密碼強度，具有十分重要的作用。強度，具有十分重要的作用。 S盒實現(xiàn)了局部的混亂和擴散；這種局部的混盒實現(xiàn)了局部的混亂和擴散；這種局部的混亂和擴散通過亂和擴散通過E盒和盒和P盒并借助于多次迭代實現(xiàn)了整盒并借助于多次迭代實現(xiàn)了整個密碼算法的混亂和擴散。個密碼算法的混亂和擴散。 S盒只要稍有改變，其密碼強度就會大大降低，盒只要稍有改

9、變，其密碼強度就會大大降低，因此，不要試圖改變一個密碼算法中的任何細節(jié)！因此，不要試圖改變一個密碼算法中的任何細節(jié)！()()kkDESmDESm證明：證明：由于由于DES的的F函數(shù)具有性質(zhì)：函數(shù)具有性質(zhì)：( , )( )( )( , )F k RPS kE RPS kE RF k R從而從而DES算法的圈函數(shù)滿足算法的圈函數(shù)滿足),(RLQk( ,( , )R LF k R( ,( , )R LF k R圈變換圈變換Q( ,)Q L R( ,)L Rk故若記故若記,則則有有)()(xQxQkk),(RLx,令令D是左右塊對換是左右塊對換,則則1621( )kkkD QQ Q x11621162

10、( )( )( )kkkkkkkE xD QQ Q xD QQ Q x證畢證畢1621( )kkkD QQ Q x( )kE x定理定理),(RLQk( ,( , )R LF k R),(RLQk互補對稱性的缺點互補對稱性的缺點: : 結(jié)論結(jié)論: 利用利用DES算法的互補對稱性算法的互補對稱性,利用選擇明文利用選擇明文進行窮舉攻擊時可將密鑰的加密測試量降低一半進行窮舉攻擊時可將密鑰的加密測試量降低一半.攻擊方案攻擊方案: :12(,) (,)m cm c Step1 選擇兩個明密對選擇兩個明密對 和和 Step2 令令K(0)是最低位為是最低位為0的所有密鑰構(gòu)成的集合的所有密鑰構(gòu)成的集合. S

11、tep3 對對K(0)中的每個元中的每個元k,計算計算c=Ek(m),并檢驗并檢驗c=c1是否成立是否成立.若成立若成立,則判定則判定k為候選密鑰為候選密鑰;若不成立若不成立,基于基于( )( )kkE mE mc利用明密對利用明密對 檢驗檢驗 是否為正確密鑰是否為正確密鑰,即檢驗即檢驗是否成立是否成立.若成立若成立,則判定則判定 為候選密鑰為候選密鑰,否則返回否則返回Step3檢檢驗驗K(0)中的下個元中的下個元.2( , )m ck2cck DES算法從一出生就受到密鑰太短的責(zé)難算法從一出生就受到密鑰太短的責(zé)難,但但NSA卻聲卻聲稱它具有足夠的安全性。盡管如此稱它具有足夠的安全性。盡管如此

12、,人們?nèi)韵Ｍ麑⑵涿荑€變?nèi)藗內(nèi)韵Ｍ麑⑵涿荑€變長。長。 將將DES算法的密鑰變長的一個可能方法是重新設(shè)計密鑰算法的密鑰變長的一個可能方法是重新設(shè)計密鑰生成算法，但這時的密碼算法就不再是生成算法，但這時的密碼算法就不再是DES了，其密碼強度了，其密碼強度必須重新分析，而且如此修改的密碼算法無法與別人使用必須重新分析，而且如此修改的密碼算法無法與別人使用的的DES互通，因而是不可取的?；ネǎ蚨遣豢扇〉?。 此外，此外，DES算法已經(jīng)做成了一個加密芯片或加密模塊，算法已經(jīng)做成了一個加密芯片或加密模塊，如果基于這個已有的產(chǎn)品來加強如果基于這個已有的產(chǎn)品來加強DES，就可降低成本。，就可降低成本。 使用不

13、同的密鑰利用使用不同的密鑰利用DES算法對明文連續(xù)加密就是一種算法對明文連續(xù)加密就是一種選擇方案，這就產(chǎn)生了二重選擇方案，這就產(chǎn)生了二重DES和三重和三重DES。21( )kkcDESDESm21( )kkcDESDESm Step1 以以k1的的256個可能值個可能值k1為為DES的密鑰的密鑰對對m加密加密,并將所并將所得的得的256個加密結(jié)果個加密結(jié)果DESk1(m)與所用密鑰與所用密鑰k1一起一起,按加密結(jié)果的按加密結(jié)果的大小排序大小排序,得到有序表得到有序表 L=(DESk1(m) ,k1):k10,156. Step2 對對k2的每個可能值的每個可能值k2為為DES的密鑰對的密鑰對c

14、脫密脫密,并檢查并檢查脫密結(jié)果脫密結(jié)果DESk2-1 (c)是否在表是否在表L中中.如果如果DESk2-1(c)= DESk1(m) 則判定則判定(k1,k2)為候選密鑰為候選密鑰,否則返回否則返回Step2檢驗下個可能密鑰檢驗下個可能密鑰.直到檢驗找到正確密鑰為止直到檢驗找到正確密鑰為止. 成功率成功率=1; 存儲復(fù)雜性為存儲復(fù)雜性為256,最大計算復(fù)雜性為最大計算復(fù)雜性為257.數(shù)據(jù)復(fù)雜性為數(shù)據(jù)復(fù)雜性為2個已知的明文分組個已知的明文分組.211( )( )kkDEScDES m21( )kkDESDESmc12( )kkmDESDESc 該加密方案使用兩個不同的密鑰該加密方案使用兩個不同的密鑰k1和和k2對明文進行對明文進行三次三次DES加密或加密或DES脫密變換，加密函數(shù)采用一個加密脫密變換，加密函數(shù)采用一個加密-脫密脫密-加密序列：加密序列：1211( )kkkcDESDESDESm 兩個密鑰的三重兩個密鑰的三重DES的有效密鑰長度是的有效密鑰長度是112比特。比特。它是一種較受歡迎的它是一種較受歡迎的DE