密碼學(xué)基礎(chǔ)課件：第六講 對稱密碼學(xué)

1、第六講 對稱密碼學(xué)-1代換-置換網(wǎng)絡(luò)線性分析差分分析DES預(yù)熱代換-置換網(wǎng)絡(luò)在Shannon 1949 的文章中，介紹了代換-置換網(wǎng)絡(luò)的思想 (S-P) networks 這種思想形成了現(xiàn)代密碼的基礎(chǔ)S-P network 代換-置換乘積密碼的現(xiàn)代形式S-P networks 是基于下列兩種最基本的密碼運(yùn)算（前面介紹過）：代換（ Substitution ）置換（ Permutation ）代換運(yùn)算 一個(gè)二進(jìn)制字用其它二進(jìn)制字代換這種代換函數(shù)就構(gòu)成密鑰 可以看作是一個(gè)大的查表運(yùn)算，叫做 S-boxes 代換運(yùn)算注意左側(cè)有0，0，1三個(gè)符號，右側(cè)是1，1，0三個(gè)符號，發(fā)生了代換置換運(yùn)算二進(jìn)制字次

2、序被打亂 重新排序的方法構(gòu)成密鑰 叫這種變換為 P-boxes 置換運(yùn)算注意左側(cè)和右側(cè)0，1的個(gè)數(shù)是相同的，只是位置發(fā)生了變化Substitution-Permutation Network Shannon 把這兩種運(yùn)算組合在一起 一些 S-boxes 由 P-box 連接這種變換叫做混合變換（mixing transformations ）實(shí)際使用的替換-置換網(wǎng)絡(luò)實(shí)際中，我們需要加密，也需要解密因此，有兩種方法：1。定義每個(gè)替換、置換的逆，這樣增加了復(fù)雜度2。定義一種結(jié)構(gòu)，容易求逆，這樣可以使用基本的相同編碼或硬件用于加密和解密（啞謎）基本設(shè)計(jì)原理Shannons 混合變換形成一種特殊的乘積

3、密碼 組成部分一起工作: S-Boxes （S-盒)提供輸入bits混淆作用 (confusion)P-Boxes 提供擴(kuò)散作用(diffusion across S-box inputs) 這種效果進(jìn)一步解釋為”雪崩”與”完備性” (Avalanche and Completeness )by Webster & Tavares On the Design of S-boxes, in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Science, No 218, Springer-Verlag, 1985, pp

4、 523-534 雪崩與完備性雪崩效應(yīng)(Avalanche effect )輸入改變1bit, 導(dǎo)致輸出近一半的比特發(fā)生變化完備性效應(yīng)(Completeness effect )每個(gè)輸出比特是所有輸入比特的復(fù)雜函數(shù)的輸出線性密碼分析線性密碼分析一個(gè)示例的S和P線性密碼分析上述SP下的SPN示例輸入x輪密鑰為K輪密鑰作用后輸出為uS代換后為VP置換后為W迭代3次最后代換后輸出線性密碼分析S代換的線性逼近（下面這個(gè)圖是例3.1S代換的二進(jìn)制寫法）線性密碼分析考慮X1X4Y2取0的情況有_種？考慮X3X4Y1Y4取0的情況有_種？完善保密的情況是明文空間和密文空間_？所以理想情況下取0的情況應(yīng)該是_

5、?線性密碼分析考慮右圖的四個(gè)S盒即X1X3X4Y2(12個(gè)0)X2Y2Y4(4個(gè)0)X2Y2Y4(4個(gè)0)X2Y2Y4(4個(gè)0)為什么選這四個(gè)上式T1T2T3T4有什么用？注意T1到T4都是有偏差的，那么猜想T1T2T3T4也是有偏差的。此時(shí)用已知明文攻擊，假設(shè)已知同一密鑰加密的許多對明文密文，那么 應(yīng)當(dāng)是有偏差的。注意到6，8，14，16僅對應(yīng)了最后一輪第2和第4個(gè)S盒。有什么用？對于第2個(gè)和第4個(gè)S盒，最后一輪的輪密鑰僅有4+4個(gè)比特，256種可能，那么對每一個(gè)輪密鑰，所有的明-密文對，解密最后一層，得到第2，4個(gè)S盒的輸出，查表找到輸入，即第4層U的值，然后計(jì)算偏差有什么用如果最后一輪的

6、輪密鑰不正確，那么對于所有的明密文對，式 的偏差接近0；（例如100對明-密文中，取0的約50對）如果輪密鑰是對的，那么應(yīng)當(dāng)有顯著偏差如此可以區(qū)分正確的輪密鑰。線性密碼分析差分分析差分分析已知明密文對明文異或值相同（差值固定）經(jīng)過S盒之后y和y*的異或值分布不均勻如果明密文空間獨(dú)立，應(yīng)當(dāng)是均勻的0010差分分析1011對應(yīng)B行，可以看到2(0010)出現(xiàn)8次差分分析第一層S2輸入差分1011（B），輸出選0100(出現(xiàn)8次)0100置換到S3，輸出選0110(出現(xiàn)6次).最后找到第4層u的第2個(gè)和第4個(gè)S盒的輸入0110出現(xiàn)概率應(yīng)該較高差分分析DES 美國數(shù)據(jù)加密標(biāo)準(zhǔn)DES（Data Encr

7、yption Standard）。 1.美國制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡況 通信與計(jì)算機(jī)相結(jié)合是人類步入信息社會的一個(gè)階梯，它始于六十年代末，完成于90年代初。計(jì)算機(jī)通信網(wǎng)的形成與發(fā)展，要求信息作業(yè)標(biāo)準(zhǔn)化，安全保密亦不例外。 美國NBS在1973年5月15公布了征求建議。1974年8月27日NBS再次出公告征求建議，對建議方案提出如下要求：（1）算法必須完全確定而無含糊之處；（2）算法必須有足夠高的保護(hù)水準(zhǔn)，即可以檢測到威脅，恢復(fù)密鑰所必須的運(yùn)算時(shí)間或運(yùn)算次數(shù)足夠大；（3）保護(hù)方法必須只依賴于密鑰的保密；（4）對任何用戶或產(chǎn)品供應(yīng)者必須是不加區(qū)分的。二、DES，標(biāo)準(zhǔn)簡況 IBM公司從60年代末即看到通信

8、網(wǎng)對于這種加密標(biāo)準(zhǔn)算法的需求，投入了相當(dāng)?shù)难芯苛α块_發(fā)，成立了以Tuchman博士為領(lǐng)導(dǎo)的研究新密碼體制的小組，H. Fistel進(jìn)行設(shè)計(jì)，并在1971年完成的LUCIFER密碼 (64 bit分組，代換-置換，128 bit密鑰)的基礎(chǔ)上，改進(jìn)成為建議的DES體制。 1975年3月17日NBS公布了這個(gè)算法，并說明要以它作為聯(lián)邦信息處理標(biāo)準(zhǔn)，征求各方意見。1977年1月15日建議被批準(zhǔn)為聯(lián)邦標(biāo)準(zhǔn)FIPS PUB 46，并設(shè)計(jì)推出DES芯片。DES開始在銀行、金融界廣泛應(yīng)用。1981年美國ANSI 將其作為標(biāo)準(zhǔn)，稱之為DEAANSI X3.92。1983年國際標(biāo)準(zhǔn)化組織(ISO)采用它作為標(biāo)準(zhǔn)

9、，稱作DEA-1。 二、DES ，標(biāo)準(zhǔn)簡況1984年9美國總統(tǒng)簽署145號國家安全決策令(NSDD)，命令NSA著手發(fā)展新的加密標(biāo)準(zhǔn)，用于政府系統(tǒng)非機(jī)密數(shù)據(jù)和私人企事業(yè)單位。1998年DES不再用。雖然DES不會長期地作為數(shù)據(jù)加密標(biāo)準(zhǔn)算法，但它仍是迄今為止得到最廣泛應(yīng)用的一種算法，也是一種最有代表性的分組加密體制。1993年4月，Clinton政府公布了一項(xiàng)建議的加密技術(shù)標(biāo)準(zhǔn)，稱作密鑰托管加密技術(shù)標(biāo)準(zhǔn)EES(Escrowed Encryption Standard)。其開發(fā)設(shè)計(jì)始于1985年，由NSA負(fù)責(zé)研究。1990年完成評價(jià)工作。其算法為SKIPJACK。已由Mykotronix公司開發(fā)芯

10、片產(chǎn)品，編程后為MYK-78。算法屬美國政府SECRET密級。二、DES ，標(biāo)準(zhǔn)簡況 DES發(fā)展史確定了發(fā)展公用標(biāo)準(zhǔn)算法模式，而EES的制定路線與DES的背道而馳。1995年5月AT&T Bell Lab的M. Blaze博士在PC機(jī)上用45分鐘時(shí)間使SKIPJACK的 LEAF協(xié)議失敗，偽造ID碼獲得成功。雖NSA 聲稱已彌補(bǔ)，但喪失了公眾對此體制的信心。1995年7月美國政府宣布放棄用EES來加密數(shù)據(jù)。重新回到制定DES標(biāo)準(zhǔn)立場。1997年1月美國NIST著手進(jìn)行AES（Advanced Encryption Standard）的研究，成立了標(biāo)準(zhǔn)工作室。1997年4月15日討論了AES的評估標(biāo)準(zhǔn)，開始在世界范圍征集AES的建議算法，截止時(shí)間為1998年6月15日。1998年8月2022日經(jīng)評審選定并公布了15個(gè)候選算法，后來意大利密碼學(xué)家提交的算法成為AES。Feistel網(wǎng)絡(luò)Horst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，設(shè)計(jì)了這樣的結(jié)構(gòu)，我們現(xiàn)在叫做feistel cipher 思想是把輸入塊分成左右兩部分 L(i-1) 和R(i-1),