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

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

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

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

4、而求其次,來分析這種能夠性. 8結(jié)論: (1) Feistel模型至少需求3圈才可實(shí)現(xiàn)完全性. (2) 假設(shè)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è)函數(shù)f是完全的, 當(dāng)不思索變換結(jié)果的抵消時(shí),那么無論改動(dòng)x或y的一個(gè)比特, 第3圈的輸出的左半和右半的每個(gè)比特都能夠改動(dòng),這闡明此

5、時(shí)3圈可以實(shí)現(xiàn)完全性.10二、DES的S盒的設(shè)計(jì)規(guī)范 DES算法的設(shè)計(jì)者迫于公眾壓力公布的S盒的設(shè)計(jì)規(guī)范為 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ù),假設(shè)那么稱f 是仿射函數(shù);又假設(shè)仿射函數(shù)滿足f(0)=0,那么 f 為線性函數(shù). 等價(jià)定義: 設(shè) f是n元布爾函數(shù),那么 f是仿射函數(shù)等價(jià)于存在常數(shù)c1,c2,cn和a使對(duì)一切x,都有此時(shí),假設(shè)a=0,那么 f為

6、線性函數(shù). 仿射函數(shù)的缺陷: (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ì)的大敵!13 S盒是DES算法中獨(dú)一的非線性變換，是在DES算法起中心作用的密碼變換! S盒的設(shè)計(jì)規(guī)范對(duì)于實(shí)現(xiàn)DES算法的完全性，對(duì)于實(shí)現(xiàn)混亂和分散原那么，對(duì)于確保DES算法的密碼強(qiáng)度，具有非常重要的作用。 S盒實(shí)現(xiàn)了部分的混亂和分散；這種部分的混亂和分散經(jīng)過E盒和P盒并借助于多次迭代實(shí)現(xiàn)了整個(gè)密碼算法的混亂和分散。 S盒只需稍有改動(dòng)，其密碼強(qiáng)度就會(huì)大大降低，因此，不要試圖改動(dòng)一個(gè)密碼算法中的任何細(xì)節(jié)！14三、DES算法的

7、互補(bǔ)對(duì)稱性證明：由于DES的F函數(shù)具有性質(zhì)：從而DES算法的圈函數(shù)滿足圈變換Qk故假設(shè)記,那么有,令D是左右塊對(duì)換,那么證畢定理15互補(bǔ)對(duì)稱性的缺陷: 結(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能否成立.假設(shè)成立,那么斷定k為候選密鑰;假設(shè)不成立,基于利用明密對(duì) 檢驗(yàn) 能否為正確密鑰,即檢驗(yàn)?zāi)芊癯闪?假設(shè)成立,那么斷定 為候選密鑰,否那么前往Step3檢驗(yàn)K(0)中的下個(gè)元.

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

9、變換以實(shí)現(xiàn)對(duì)數(shù)據(jù)的加密維護(hù)，即18 雙重DES的密鑰長(zhǎng)度是562=112比特。 但是,雙重DES可利用計(jì)算復(fù)雜性和存儲(chǔ)復(fù)雜性都為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):k10,156. Step2 對(duì)k2的每個(gè)能夠值k2為DES的密鑰對(duì)c脫密,并檢查脫密結(jié)果DESk2-1 (c)能否在表L中.假設(shè)DESk2-1(c)= DESk1(m) 那么斷定(k1,k2)為候選密鑰,否那么前往Step2檢驗(yàn)下個(gè)能夠密鑰.直到檢驗(yàn)找到正確密鑰為止. 勝利率=1; 存儲(chǔ)復(fù)雜性為256,最大計(jì)算復(fù)雜性為257.數(shù)據(jù)復(fù)雜性為2個(gè)知的明文分組.原理:20雙重DES的解密212. 三重DES 該加密方案運(yùn)用兩個(gè)不同的密鑰k1和k2對(duì)明文進(jìn)展三次DES加密