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

1、DES算法的平安性分析王 濱2005年3月18日1主要內(nèi)容 窮舉攻擊分析 Feistel模型分析 S盒的設計規(guī)范 DES算法的互補對稱性 DES算法的加強方案-多重DES2窮舉攻擊分析 窮舉攻擊就是對一切能夠的密鑰逐個進展脫密測試, 直到找到正確密鑰為止的一種攻擊方法. 窮舉攻擊判別正確密鑰的方法： 將利用實驗密鑰脫密得到的能夠明文與已掌握的明文的信息相比較，并將最吻合的那個實驗密鑰作為算法輸出的正確密鑰。 窮舉攻擊又稱為窮盡攻擊、強力攻擊、蠻干攻擊等。只需明文不是隨機的，就可實施窮舉攻擊。3窮舉攻擊的算法 知條件：知密文c及對應的明文m. Step 1 對每個能夠密鑰k,計算c=D(k,m)

2、,并判別c=c能否成立.不成立時前往Step1檢驗下一個能夠密鑰,成立時將k作為候選密鑰,并執(zhí)行Step 2. Step 2 利用其它條件對作k進一步確認.確認經(jīng)過時輸出,算法終止.否那么前往Step1檢驗下一個能夠密鑰.4窮舉攻擊算法的計算復雜性定理 設密鑰在密鑰空間K中服從均勻分布，且沒有等效密鑰,那么窮舉攻擊平均需求檢驗完 個密鑰后才找到正確密鑰。結(jié)論: 對DES算法的窮舉攻擊平均計算復雜性為255.5一、 Feistel模型分析Li32位Ri32位Li-132位Ri-132位f 1. 設計容易:f 函數(shù)不要求可逆,加、脫密脫算法構(gòu)造一樣； 2.強度高：假設f 函數(shù)是隨機的,那么延續(xù)假設

3、干圈復合構(gòu)成的函數(shù)與隨機置換是無法區(qū)分的.優(yōu)點:6Li32位Ri32位Li-132位Ri-132位f 每圈加密時輸入有一半沒有改動; 左右塊的加密處置不能并行實施缺陷:7Feistel模型實現(xiàn)完全性的性能分析 定義2 假設對每個密鑰k,迭代次數(shù)為m的加密變換Ek(x)的每個輸入比特的變化都能夠會影響到每個輸出比特的變化,那么稱 Ek(x)是完全的. 意義: 實現(xiàn)了Shannon提出的分散性原那么. 分散原那么(Diffusion) 讓明文中的每一位影響密文中的盡能夠多的位，或者說讓密文中的每一位都遭到明文中的盡能夠多位的影響。 由于在檢驗完全性時,無法對一切的密鑰都來檢驗影響的必然性, 只好退

4、而求其次,來分析這種能夠性. 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)完全性. 證明: 設(x,y)是Feistel模型的輸入,那么其第1圈至第3圈的輸出依次為 假設函數(shù)f是完全的, 當不思索變換結(jié)果的抵消時,那么無論改動x或y的一個比特, 第3圈的輸出的左半和右半的每個比特都能夠改動,這闡明此

5、時3圈可以實現(xiàn)完全性.10二、DES的S盒的設計規(guī)范 DES算法的設計者迫于公眾壓力公布的S盒的設計規(guī)范為 1. S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。 3. 當固定S盒的1位輸入時，S盒的每一位輸出中0和1的個數(shù)盡能夠平衡。 2. S盒的輸入發(fā)生1比特變化，輸出至少有2比特發(fā)生變化。11 1. S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。 仿射函數(shù)的定義 設 f是n元布爾函數(shù),假設那么稱f 是仿射函數(shù);又假設仿射函數(shù)滿足f(0)=0,那么 f 為線性函數(shù). 等價定義: 設 f是n元布爾函數(shù),那么 f是仿射函數(shù)等價于存在常數(shù)c1,c2,cn和a使對一切x,都有此時,假設a=0,那么 f為

6、線性函數(shù). 仿射函數(shù)的缺陷: (1) 輸入與輸出之間的代數(shù)關系太簡單; (2) 輸入的變化與輸出的變化之間的代數(shù)關系太簡單. 仿射函數(shù)的優(yōu)點: 實現(xiàn)簡單12線性性質(zhì)是密碼設計的大敵!13 S盒是DES算法中獨一的非線性變換，是在DES算法起中心作用的密碼變換! S盒的設計規(guī)范對于實現(xiàn)DES算法的完全性，對于實現(xiàn)混亂和分散原那么，對于確保DES算法的密碼強度，具有非常重要的作用。 S盒實現(xiàn)了部分的混亂和分散；這種部分的混亂和分散經(jīng)過E盒和P盒并借助于多次迭代實現(xiàn)了整個密碼算法的混亂和分散。 S盒只需稍有改動，其密碼強度就會大大降低，因此，不要試圖改動一個密碼算法中的任何細節(jié)！14三、DES算法的

7、互補對稱性證明：由于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)中的下個元.

8、16四、DES的加強方法 DES算法從一出生就遭到密鑰太短的責難,但NSA卻聲稱它具有足夠的平安性。雖然如此,人們?nèi)韵Ｍ麑⑵涿荑€變長。 將DES算法的密鑰變長的一個能夠方法是重新設計密鑰生成算法，但這時的密碼算法就不再是DES了，其密碼強度必需重新分析，而且如此修正的密碼算法無法與他人運用的DES互通，因此是不可取的。 此外，DES算法曾經(jīng)做成了一個加密芯片或加密模塊，假設基于這個已有的產(chǎn)品來加強DES，就可降低本錢。 運用不同的密鑰利用DES算法對明文延續(xù)加密就是一種選擇方案，這就產(chǎn)生了二重DES和三重DES。171. 雙重DES雙重DES是分別用兩個不同的密鑰k1和k2對明文進展兩次DES

9、變換以實現(xiàn)對數(shù)據(jù)的加密維護，即18 雙重DES的密鑰長度是562=112比特。 但是,雙重DES可利用計算復雜性和存儲復雜性都為256的中間相遇攻擊方案攻破.中間相遇攻擊是一種以空間換時間的攻擊方法.雙重DES的分析19對雙重DES 的中間相遇攻擊 Step1 以k1的256個能夠值k1為DES的密鑰對m加密,并將所得的256個加密結(jié)果DESk1(m)與所用密鑰k1一同,按加密結(jié)果的大小排序,得到有序表 L=(DESk1(m) ,k1):k10,156. 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加密