DES算法的安全性分析课件.ppt

**DES演算法的安全性分析*窮舉攻擊分析窮舉攻擊就是對所有可能的密鑰逐個進行脫密測試,直到找到正確密鑰為止的一種攻擊方法.窮舉攻擊判斷正確密鑰的方法：將利用試驗密鑰脫密得到的可能明文與已掌握的明文的資訊相比較，並將最吻合的那個試驗密鑰作為演算法輸出的正確密鑰。窮舉攻擊又稱為窮盡攻擊、強力攻擊、蠻幹攻擊等。只要明文不是隨機的，就可實施窮舉攻擊。*窮舉攻擊的演算法已知條件：已知密文c及對應的明文m.Step1對每個可能密鑰k,計算c’=D(k,m),並判斷c’=c是否成立.不成立時返回Step1檢驗下一個可能密鑰,成立時將k作為候選密鑰,並執行Step2.Step2利用其他條件對作k進一步確認.確認通過時輸出,演算法終止.否則返回Step1檢驗下一個可能密鑰.*窮舉攻擊演算法的計算複雜性定理設密鑰在密鑰空間K中服從均勻分佈，且沒有等效密鑰,則窮舉攻擊平均需要檢驗完個密鑰後才找到正確密鑰。結論:對DES演算法的窮舉攻擊平均計算複雜性為255.*一、Feistel模型分析Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f1.設計容易:f函數不要求可逆,加、脫密脫演算法結構相同；2.強度高：如果f函數是隨機的,則連續若干圈複合形成的函數與隨機置換是無法區分的.優點:*Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f每圈加密時輸入有一半沒有改變;左右塊的加密處理不能並行實施缺點:*Feistel模型實現完全性的性能分析定義2如果對每個密鑰k,迭代次數為m的加密變換Ek(x)的每個輸入比特的變化都可能會影響到每個輸出比特的變化,則稱Ek(x)是完全的.意義:實現了Shannon提出的擴散性原則.擴散原則(Diffusion)讓明文中的每一位影響密文中的盡可能多的位，或者說讓密文中的每一位都受到明文中的盡可能多位的影響。因為在檢驗完全性時,無法對所有的密鑰都來檢驗影響的必然性,只好退而求其次,來分析這種可能性.*結論:(1)Feistel模型至少需要3圈才可實現完全性.(2)如果Feistel模型的f函數需要T圈迭代才能實現完全性,則Feistel模型經T+2圈迭代可實現完全性.(3)DES演算法需且只需5圈即可實現完全性!*結論:(1)Feistel模型至少需要3圈才可實現完全性,且當其f函數具有完全性時,只需3圈即可實現完全性.證明:設(x,y)是Feistel模型的輸入,則其第1圈至第3圈的輸出依次為如果函數f是完全的,當不考慮變換結果的抵消時,則無論改變x或y的一個比特,第3圈的輸出的左半和右半的每個比特都可能改變,這說明此時3圈能夠實現完全性.*二、DES的S盒的設計標準DES演算法的設計者迫於公眾壓力公佈的S盒的設計標準為1.S盒的每一位輸出都不是輸入的線性或仿射函數。3.當固定S盒的1位輸入時，S盒的每一位輸出中0和1的個數盡可能平衡。2.S盒的輸入發生1比特變化，輸出至少有2比特發生變化。*1.S盒的每一位輸出都不是輸入的線性或仿射函數。仿射函數的定義設f是n元布爾函數,如果則稱f是仿射函數;又若仿射函數滿足f(0)=0,則f為線性函數.等價定義:設f是n元布爾函數,則f是仿射函數等價於存在常數c1,c2,…,cn和a使對所有x,都有此時,如果a=0,則f為線性函數.仿射函數的缺點:(1)輸入與輸出之間的代數關係太簡單;(2)輸入的變化與輸出的變化之間的代數關係太簡單.仿射函數的優點:實現簡單*線性性質是密碼設計的大敵!*S盒是DES演算法中唯一的非線性變換，是在DES演算法起核心作用的密碼變換!S盒的設計標準對於實現DES演算法的完全性，對於實現混亂和擴散原則，對於確保DES演算法的密碼強度，具有十分重要的作用。S盒實現了局部的混亂和擴散；這種局部的混亂和擴散通過E盒和P盒並借助於多次迭代實現了整個密碼演算