信息安全原理與技術(shù)ch03-對(duì)稱加密技術(shù)

信息平安原理與技術(shù)郭亞軍宋建華李莉清華大學(xué)出版社2025/3/111Ch3(1)-對(duì)稱加密技術(shù)第3章對(duì)稱加密技術(shù)(1)主要知識(shí)點(diǎn)：

--對(duì)稱密碼模型

--密碼攻擊

--古典加密技術(shù)

--數(shù)據(jù)加密標(biāo)準(zhǔn)

--高級(jí)加密標(biāo)準(zhǔn)

--RC6

--流密碼

--分組密碼工作模式

--隨機(jī)數(shù)的產(chǎn)生

--對(duì)稱密碼的密鑰分配

2025/3/112Ch3(1)-對(duì)稱加密技術(shù)密碼技術(shù)主要分為對(duì)稱密碼技術(shù)和非對(duì)稱密碼技術(shù)對(duì)稱密碼技術(shù)中，加密密鑰和解密密鑰相同，或者一個(gè)密鑰可以從另一個(gè)導(dǎo)出非對(duì)稱密碼技術(shù)那么使用兩個(gè)密鑰,加密密鑰和解密密鑰不同,非對(duì)稱密碼技術(shù)那么產(chǎn)生于20世紀(jì)70年代20世紀(jì)70年代以前的加密技術(shù)都是對(duì)稱加密技術(shù)，這個(gè)時(shí)期的加密技術(shù)也稱為古典加密技術(shù)。古典加密技術(shù)一般將加密算法保密，而現(xiàn)代的對(duì)稱加密技術(shù)那么公開加密算法，加密算法的平安性只取決于密鑰，不依賴于算法2025/3/113Ch3(1)-對(duì)稱加密技術(shù)密碼學(xué)的根本概念密碼學(xué)〔Cryptology〕包括密碼編碼學(xué)〔Cryptography〕,和密碼分析學(xué)〔Cryptanalysis〕密碼編碼學(xué)是研究加密原理與方法，使消息保密的技術(shù)和科學(xué)，它的目的是掩蓋消息內(nèi)容密碼分析學(xué)那么是研究破解密文的原理與方法密碼分析者〔Cryptanalyst〕是從事密碼分析的專業(yè)人員被偽裝的原始的消息(Message)稱為明文〔Plaintext〕將明文轉(zhuǎn)換為密文過程稱為加密〔Encryption〕2025/3/114Ch3(1)-對(duì)稱加密技術(shù)加了密的消息稱為密文〔Ciphertext〕把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密〔Decryption〕從明文到密文轉(zhuǎn)換的算法稱為密碼(Cipher)一個(gè)加密系統(tǒng)采用的根本工作方式叫做密碼體制(Cryptosystem)在密碼學(xué)中見到“系統(tǒng)或體制〞(System)、“方案〞(Scheme)和“算法〞(Algorithm)等術(shù)語本質(zhì)上是一回事加密和解密算法通常是在一組密鑰〔Key〕控制下進(jìn)行的,分別稱為加密密鑰和解密密鑰如果加密密鑰和解密密鑰相同，那么密碼系統(tǒng)為對(duì)稱密碼系統(tǒng)2025/3/115Ch3(1)-對(duì)稱加密技術(shù)對(duì)稱密碼模型對(duì)稱密碼也稱傳統(tǒng)密碼，它的特點(diǎn)是發(fā)送方和接收方共享一個(gè)密鑰對(duì)稱密碼分為兩類：分組密碼(BlockCiphers)和流密碼(StreamCiphers)分組密碼也稱為塊密碼，它是將信息分成一塊(組)，每次操作(如加密和解密)是針對(duì)一組而言流密碼也稱序列密碼，它是每次加密(或者解密)一位或者一個(gè)字節(jié)2025/3/116Ch3(1)-對(duì)稱加密技術(shù)一個(gè)對(duì)稱密碼系統(tǒng)(也稱密碼體制)有五個(gè)組成局部組成。用數(shù)學(xué)符號(hào)來描述為S＝{M,C,K,E,D}，如圖3.2所示。(1)明文空間M，是全體明文的集合。(2)密文空間C，表示全體密文的集合。(3)密鑰空間K，表示全體密鑰的集合，包括加密密鑰和解密密鑰。(4)加密算法E，表示由明文到密文的變換。(5)解密算法D，表示由密文到文明的變換。2025/3/117Ch3(1)-對(duì)稱加密技術(shù)明文加密算法解密算法明文傳輸通道MMCC攻擊者接收方發(fā)送方密鑰源安全通道KK圖3.2對(duì)稱密碼系統(tǒng)模型2025/3/118Ch3(1)-對(duì)稱加密技術(shù)對(duì)明文M用密鑰K，使用加密算法E進(jìn)行加密常常表示為Ek(M)，同樣用密鑰K使用解密算法D對(duì)密文C進(jìn)行解密表示為Dk(C)在對(duì)稱加密體制中，密解密密鑰相同,有：C＝Ek(M)M＝Dk(C)＝Dk(Ek(M))2025/3/119Ch3(1)-對(duì)稱加密技術(shù)密碼體制至少滿足的條件(1)明文M和加密密鑰K時(shí)，計(jì)算C＝Ek(M)容易(2)加密算法必須足夠強(qiáng)大，使破譯者不能僅根據(jù)密文破譯消息，即在不知道解密密鑰K時(shí)，由密文C計(jì)算出明文M是不可行的(3)由于對(duì)稱密碼系統(tǒng)雙方使用相同的密鑰，因此還必須保證能夠平安地產(chǎn)生密鑰，并且能夠以平安的形式將密鑰分發(fā)給雙方(4)對(duì)稱密碼系統(tǒng)的平安只依賴于密鑰的保密，不依賴于加密和解密算法的保密2025/3/1110Ch3(1)-對(duì)稱加密技術(shù)密碼攻擊

分析一個(gè)密碼系統(tǒng)是否是平安，一般是在假定攻擊者知道所使用的密碼系統(tǒng)情況下進(jìn)行分析的如:密碼分析者可以得到密文，知道明文的統(tǒng)計(jì)特性，加密體制，密鑰空間及其統(tǒng)計(jì)特性這個(gè)假設(shè)稱為Kerckhoff假設(shè)分析一個(gè)密碼系統(tǒng)的平安性一般是建立在這個(gè)假設(shè)的根底上對(duì)稱密碼體制的攻擊有兩種方法：密碼分析和窮舉攻擊(BruteForceSearch)2025/3/1111Ch3(1)-對(duì)稱加密技術(shù)密碼分析是依賴加密算法的性質(zhì)和明文的一般特征等試圖破譯密文得到明文或試圖獲得密鑰的過程窮舉攻擊那么是試遍所有可能的密鑰對(duì)所獲密文進(jìn)行解密，直至得到正確的明文；或者用一個(gè)確定的密鑰對(duì)所有可能的明文進(jìn)行加密，直至得到所獲得的密文2025/3/1112Ch3(1)-對(duì)稱加密技術(shù)窮舉攻擊窮舉攻擊是最根本也是比較有效的一種攻擊方法從理論上講，可以嘗試所有的密鑰窮舉攻擊的代價(jià)與密鑰大小成正比密碼算法可以通過增大密鑰位數(shù)或加大解密〔加密〕算法的復(fù)雜性來對(duì)抗窮舉攻擊表3.1是窮盡密鑰空間所需的時(shí)間。從表中我們可以發(fā)現(xiàn)，當(dāng)密鑰長度到達(dá)128位以上時(shí)，以目前的資源來說，窮舉攻擊將不成功2025/3/1113Ch3(1)-對(duì)稱加密技術(shù)2025/3/1114Ch3(1)-對(duì)稱加密技術(shù)密碼攻擊類型密碼分析是基于Kerckhoff假設(shè)密碼分析者所使用的策略取決于加密方案的性質(zhì)以及可供密碼分析者使用的信息根據(jù)密碼分析者所知的信息量,把對(duì)密碼的攻擊分為:唯密文攻擊,明文攻擊,選擇明文攻擊,選擇密文攻擊,選擇文本攻擊2025/3/1115Ch3(1)-對(duì)稱加密技術(shù)唯密文攻擊〔Ciphertext-OnlyAttack〕:密碼分析者知道：加密算法和待破譯的密文.明文攻擊〔Known-PlaintextAttack〕:密碼分析者除知道加密算法和待破譯的密文外，而且也知道，有一些明文和同一個(gè)密鑰加密的這些明文所對(duì)應(yīng)的密文即知道一定數(shù)量的明文和對(duì)應(yīng)的密文選擇明文攻擊〔Chosen-PlaintextAttack〕:密碼分析者知道加密算法和待破譯的密文，并且可以得到所需要的任何明文所對(duì)應(yīng)的密文，這些明文和待破譯的密文是用同一密鑰加密得來的，即知道選擇的明文和對(duì)應(yīng)的密文。如在公鑰密碼體制中，攻擊者可以利用公鑰加密他任意選定的明文2025/3/1116Ch3(1)-對(duì)稱加密技術(shù)選擇密文攻擊〔Chosen-CiphertextAttack〕:密碼分析者知道加密算法和待破譯的密文，密碼分析者能選擇不同的被加密的密文，并可得到對(duì)應(yīng)的解密的明文，即知道選擇的密文和對(duì)應(yīng)的明文。解密這些密文所使用的密鑰與解密待破解的密文的密鑰是一樣的。這種攻擊主要用于公鑰密碼算法。選擇文本攻擊〔ChosenTextAttack〕：選擇文本攻擊是選擇明文攻擊和選擇密文攻擊的結(jié)合。密碼分析者知道加密算法和待破譯的密文，并且知道任意選擇的明文和它對(duì)應(yīng)的密文，這些明文和待破譯的密文是用同一密鑰加密得來的，以及有目的選擇的密文和它對(duì)應(yīng)的明文，解密這些密文所使用的密鑰與解密待破解的密文的密鑰是一樣的。2025/3/1117Ch3(1)-對(duì)稱加密技術(shù)如果一個(gè)密碼系統(tǒng)能夠抵抗選擇明文攻擊，那么它也能抵抗唯密文攻擊和明文攻擊在這幾種攻擊類型中，唯密文攻擊難度最大，因?yàn)楣粽呖衫玫男畔⒆钌賹?duì)密碼設(shè)計(jì)者而言，被設(shè)計(jì)的加密算法一般要能經(jīng)受得住明文的攻擊如果無論攻擊者有多少密文，由一個(gè)加密算法產(chǎn)生的這些密文中包含的信息缺乏以唯一決定對(duì)應(yīng)的明文，也無論用什么技術(shù)方法進(jìn)行攻擊都不能被攻破，這種加密算法是絕對(duì)平安(UnconditionalSecurity)除一次一密〔One-TimePad〕外，沒有絕對(duì)平安的加密算法2025/3/1118Ch3(1)-對(duì)稱加密技術(shù)一般來說,加密算法的使用者應(yīng)該挑選滿足以下標(biāo)準(zhǔn)中的一個(gè)或兩個(gè)的算法：(1)破譯該密碼的本錢超過被加密信息的價(jià)值。(2)破譯該密碼的時(shí)間超過該信息有用的生命周期。如果滿足上述的兩個(gè)準(zhǔn)那么，一個(gè)加密算法就可認(rèn)為是在計(jì)算上平安〔ComputationalSecurity〕的計(jì)算上平安是指在計(jì)算能力有限的的情況下(如計(jì)算所需時(shí)間比宇宙生存時(shí)間還長)，無法破解此密文目前的加密算法一般是計(jì)算上平安的2025/3/1119Ch3(1)-對(duì)稱加密技術(shù)密碼分析方法當(dāng)密鑰長度增加到一定的大小時(shí)，窮舉攻擊變得不實(shí)際比較流行的密碼分析方法是線性密碼分析和差分密碼分析線性分析是一種明文攻擊線性分析是一種統(tǒng)計(jì)攻擊，它以求線性近似為根底。通過尋找現(xiàn)代密碼算法變換的線性近似來攻擊用這種方法只需要知道243個(gè)明文的情況下就可以找到DES的密鑰2025/3/1120Ch3(1)-對(duì)稱加密技術(shù)差分密碼分析在許多方面與線性密碼分析相似它與線性密碼分析的主要區(qū)別在于差分密碼分析包含了將兩個(gè)輸入的異或與其相對(duì)應(yīng)的兩個(gè)輸出的異或相比較差分密碼分析也是一個(gè)選擇明文攻擊差分密碼分析出現(xiàn)于20世紀(jì)70年代，但在1990年才公開發(fā)表它的根本思想是：通過分析明文對(duì)的差值與密文對(duì)的差值的影響來恢復(fù)某些密鑰位差分分析可用來攻擊任何由迭代一個(gè)固定的輪函數(shù)的結(jié)構(gòu)的密碼2025/3/1121Ch3(1)-對(duì)稱加密技術(shù)古典加密技術(shù)古典加密技術(shù)主要使用代換或者置換技術(shù)代換是將明文字母替換成其他字母、數(shù)字或者符號(hào)置換那么保持明文的所有字母不變，只是打亂明文字母的位置和次序古典代換加密技術(shù)分為兩類:單字母代換密碼，它將明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替。多字母代換密碼,它是對(duì)多于一個(gè)字母進(jìn)行代換單字母代換密碼中又分為單表代換密碼和多表代換密碼2025/3/1122Ch3(1)-對(duì)稱加密技術(shù)單表代換密碼只使用一個(gè)密文字母表，并且用密文字母表中的一個(gè)字母來代替一個(gè)明文字母表中的一個(gè)字母多表代換密碼是將明文消息中出現(xiàn)的同一個(gè)字母，在加密時(shí)不是完全被同一個(gè)固定的字母代換，而是根據(jù)其出現(xiàn)的位置次序，用不同的字母代換2025/3/1123Ch3(1)-對(duì)稱加密技術(shù)單表代換密碼設(shè)M和C分別表示為含n個(gè)字母的明文字母表和密文字母表。

M={m0,m1,…,mn-1}

C={c0,c1,…,cn-1}如果f為一種代換方法，那么密文為C=Ek(m)=c0c1…cn-1=f(m0)f(m1)…f(mn-1)單表代換密碼常見的方法有加法密碼，乘法密碼和仿射密碼

2025/3/1124Ch3(1)-對(duì)稱加密技術(shù)加法密碼

對(duì)每個(gè)c,m∈Zn，加法密碼的加密和解密算法是：C=Ek(m)=(m+k)modnM=Dk(c)=(c-k)modnk是滿足0<k<n的正整數(shù)。假設(shè)n是26個(gè)字母，加密方法是用明文字母后面第k個(gè)字母代替明文字母Caesar密碼是典型的加法密碼,由JuliusCaesar創(chuàng)造，最早用在軍方。將字母表中的每個(gè)字母，用它后面的第3個(gè)字母代替2025/3/1125Ch3(1)-對(duì)稱加密技術(shù)Caesar密碼舉例明文：meetmeafterthetogaparty密文：PHHWPHDIWHUWKHWRJDSDUWB對(duì)每個(gè)明文字母m，用密文字母c代換，那么Caesar密碼算法如下：加密：C=E(m)=(m+3)mod26解密：M=D(c)=(c–3)mod26移位可以是任意的，如果用k〔1≤k≤25〕表示移位數(shù)，那么通用的Caesar密碼算法表示為：加密：C=Ek(m)=(m+k)mod26解密：M=Dk(c)=(c–k)mod262025/3/1126Ch3(1)-對(duì)稱加密技術(shù)Caesar密碼平安性對(duì)密碼的分析是基于Kerckhoff假設(shè)假設(shè)攻擊者知道使用Caesar密碼加密。如果攻擊者只知道密文，即唯密文攻擊，只要窮舉測(cè)試所有可能字母移位的距離，最多嘗試25次如果攻擊者知道一個(gè)字符以及它對(duì)應(yīng)的密文，即明文攻擊，那么攻擊者很快就通過明文字符和對(duì)應(yīng)的密文字符之間的距離推出密鑰這個(gè)例子說明一個(gè)密碼體制平安至少要能夠抵抗窮舉密鑰搜索攻擊，普通的做法是將密鑰空間變得足夠大。但是，很大的密鑰空間并不是保證密碼體制平安的充分條件，下面的例子可以說明這一點(diǎn)2025/3/1127Ch3(1)-對(duì)稱加密技術(shù)對(duì)Caesar密碼進(jìn)行改進(jìn)，假設(shè)密文是26個(gè)字母的任意代換，密鑰是明文字母到密文字母的一個(gè)字母表，密鑰長度是26字長下面用一個(gè)密鑰句子構(gòu)造一個(gè)字母代換表密鑰句子為themessagewastransmittedanhourago，按照密鑰句子中的字母依次填入字母表〔重復(fù)的字母只用一次〕，未用的字母按自然順序排列原字母表abcdefghijklmnopqrstuvwxyz代換字母表THEMSAGWRNIDOUBCFJKLPQVXYZ2025/3/1128Ch3(1)-對(duì)稱加密技術(shù)假設(shè)明文為pleaseconfirmreceipt使用上面的代換字母表，那么密文為CDSTKSEBUARJOJSESRCL使用上面的方法代換，總共有26!=4x1026種密鑰從表3.1可以看到窮舉搜索這么多的密鑰很困難但這并不表示該密碼不容易破解破解這類密碼的突破點(diǎn)是由于語言本身的特點(diǎn)是充滿冗余的，每個(gè)字母使用的頻率不相等單表代換密碼沒有改變字母相對(duì)出現(xiàn)的頻率明文字母的統(tǒng)計(jì)特性在密文中能夠反映出來,當(dāng)通過統(tǒng)計(jì)密文字母的出現(xiàn)頻率，可以確定明文字母和密文字母之間的對(duì)應(yīng)關(guān)系2025/3/1129Ch3(1)-對(duì)稱加密技術(shù)英文字母中單字母出現(xiàn)的頻率

2025/3/1130Ch3(1)-對(duì)稱加密技術(shù)單字母按照出現(xiàn)頻率的大小可以分為下面5類：(1)e：出現(xiàn)的頻率大約為0.127(2)t,a,o,I,n,s,h,r：出現(xiàn)的頻率大約在之間(3)d,l：出現(xiàn)的頻率約為0.04(4)c,u,m,w,f,g,y,p,b：出現(xiàn)的頻率大約在之間(5)v,k,j,x,q,z：出現(xiàn)的頻率小于0.01雙字母和三字母組合都有現(xiàn)成的統(tǒng)計(jì)數(shù)據(jù)，常見的雙字母組合和三字母組合統(tǒng)計(jì)表能夠幫助破解密文。頻率最高的30個(gè)雙字母〔按照頻率從大到小排列〕：thheineranreedonesstenattonthandoueangasortiisetitartesehiof頻率最高的20個(gè)3字母〔按照頻率從大到小排列〕：theingandherereentthanthwasethfordthhatsheioninthissthersver2025/3/1131Ch3(1)-對(duì)稱加密技術(shù)破解舉例例3.1下面的密文式由單表代換生產(chǎn)的：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ，試破譯該密文首先統(tǒng)計(jì)密文中字母出現(xiàn)的頻率，然后與英文字母出現(xiàn)頻率比較。密文中字母的相對(duì)頻率統(tǒng)計(jì)如下：2025/3/1132Ch3(1)-對(duì)稱加密技術(shù)2025/3/1133Ch3(1)-對(duì)稱加密技術(shù)將統(tǒng)計(jì)結(jié)果與圖3.3進(jìn)行比較，可以猜測(cè)密文中P與Z可能是e和t，密文中的S,U,O,M出現(xiàn)頻率比較高，可能與明文字母中出現(xiàn)頻率相對(duì)較高的a,o,I,n,s,h,r這些字母對(duì)應(yīng)密文中出現(xiàn)頻率很低的幾個(gè)字母C,K,L,N,R,I,J可能與明文字母中出現(xiàn)頻率較低的字母v,k,j,x,q,z對(duì)應(yīng)。就這樣邊試邊改，最后得到明文如下：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow在嘗試過程中，如果同時(shí)使用雙字母和三字母的統(tǒng)計(jì)規(guī)律，那么更容易破譯密文。如上面的密文中出現(xiàn)最多的雙字母是ZW，它可能對(duì)應(yīng)明文雙字母出現(xiàn)頻率較大的th，那么ZWP就可能是the，這樣就更容易試出明文。2025/3/1134Ch3(1)-對(duì)稱加密技術(shù)乘法密碼

對(duì)每個(gè)c,m∈Zn，乘法密碼的加密和解密算法是：C=Ek(m)=(mk)modnM=Dk(c)=(ck-1)modn其中k和n互素，即gcd(k,n)=1，否那么不存在模逆元，不能正確解密乘法密碼的密碼空間大小是φ(n)，φ(n)是歐拉函數(shù)。乘法密碼的密鑰空間很小，當(dāng)n為26字母，那么與26互素的數(shù)是1、3、5、7、9、11、15、17、19、21、23、25，即φ(n)=12因此乘法密碼的密鑰空間為12。乘法密碼也稱采樣密碼，因?yàn)槊芪淖帜副硎菍⒚魑淖帜赴凑障聵?biāo)每隔k位取出一個(gè)字母排列而成。2025/3/1135Ch3(1)-對(duì)稱加密技術(shù)乘法密碼舉例例3.2

假設(shè)選取密鑰為9，使用乘法密碼的加密算法，那么明文字母和密文字母的代換表構(gòu)造如下

假設(shè)明文為amanliberalinhisviews那么密文為AENVUJKXUNLUGHUKQG2025/3/1136Ch3(1)-對(duì)稱加密技術(shù)仿射密碼

加法密碼和乘法密碼結(jié)合就構(gòu)成仿射密碼，仿射密碼的加密和解密算法是：C=Ek(m)=(k1m+k2)modn

M=Dk(c)=k1-1(c-k2)modn仿射密碼具有可逆性的條件是gcd(k,n)=1。當(dāng)k1=0時(shí)，仿射密碼變?yōu)榧臃艽a，當(dāng)k2=0時(shí)，仿射密碼變?yōu)槌朔艽a。仿射密碼中的密鑰空間的大小為nφ(n)，當(dāng)n為26字母，φ(n)=12，因此仿射密碼的密鑰空間為12×26=312。2025/3/1137Ch3(1)-對(duì)稱加密技術(shù)仿射密碼舉例例3.3設(shè)密鑰K=(7,3),用仿射密碼加密明文hot。三個(gè)字母對(duì)應(yīng)的數(shù)值是7、14和19。分別加密如下：

(7×7+3)mod26=52mod26=0(7×14+3)mod26=101mod26=23(7×19+3)mod26=136mod26=6三個(gè)密文數(shù)值為0、23和6，對(duì)應(yīng)的密文是AXG。2025/3/1138Ch3(1)-對(duì)稱加密技術(shù)多表代換密碼

用單表代換密碼加密后的密文具有明文的特征，通過統(tǒng)計(jì)密文中字母出現(xiàn)的頻率能夠比較方便地破解密文要提高密碼的強(qiáng)度，應(yīng)該讓明文結(jié)構(gòu)在密文中盡量少出現(xiàn)多表代換密碼和多字母代換密碼能夠減少這種密文字母和明文字母之間的對(duì)應(yīng)關(guān)系多表代換密碼是對(duì)每個(gè)明文字母信息采用不同的單表代換2025/3/1139Ch3(1)-對(duì)稱加密技術(shù)如果明文字母序列為m=m1m2…，令f=f1,f2,…為代換序列，那么對(duì)應(yīng)的密文字母序列為：C=Ek(m)=f1(m1)f2(m2)…假設(shè)代換系列為非周期無限序列,那么相應(yīng)的密碼為非周期多表代換密碼這類密碼對(duì)每個(gè)明文字母都采用不同的代換表或密鑰進(jìn)行加密，稱作是一次一密密碼(one-timepadcipher),這是一種在理論上唯一不可破的密碼實(shí)際中經(jīng)常采用周期多表代換密碼，它通常只使用有限的代換表，代換表被重復(fù)使用以完成對(duì)消息的加密2025/3/1140Ch3(1)-對(duì)稱加密技術(shù)周期多表代換密碼此時(shí)代換表系列為：

f=f1,f2,…,fd,f1,f2,…,fd,…在對(duì)明文字母序列為m=m1m2…進(jìn)行加密時(shí)，相應(yīng)的密文字母系列為：

C=Ek(m)=f1(m1)f2(m2)…fd(md)f1(md+1)f2(md+2)…fd(m2d)…

當(dāng)d=1時(shí)，多表代換密碼變?yōu)閱伪泶鷵Q密碼。2025/3/1141Ch3(1)-對(duì)稱加密技術(shù)維吉尼亞密碼

維吉尼亞(Vigenère)密碼是一種周期多表代換密碼,由1858年法國密碼學(xué)家維吉尼亞提出維吉尼亞密碼常常使用英文單詞作為密鑰字，密鑰那么是密鑰字的重復(fù)比方密鑰字是computer，用它加密明文senderandrecipientshareacommonkey。那么密鑰為：明文：senderandrecipientshareacommonkey密鑰：computercomputercomputercomputerc2025/3/1142Ch3(1)-對(duì)稱加密技術(shù)維吉尼亞密碼加密過程簡(jiǎn)述如下：--寫下明文，表示為數(shù)字形式；--在明文之上重復(fù)寫下密鑰字，也表示為數(shù)字形式；--加密相對(duì)應(yīng)的明文：給定一個(gè)密鑰字母k和一個(gè)明文字母m，那么密文字母那么是(m+k)mod26計(jì)算結(jié)果所對(duì)應(yīng)的字母2025/3/1143Ch3(1)-對(duì)稱加密技術(shù)維吉尼亞密碼舉例例3.5設(shè)密鑰字是cipher，明文串是thiscryptosystemisnotsecure,求密文。在明文下面重復(fù)寫密鑰字，組成密鑰。明文M：thiscryptosystemisnotsecure

密鑰K：cipherciphercipherciphercip將明文和密鑰轉(zhuǎn)化為數(shù)字明文M=(19,7,8,18,2,17,24,15,19,14,18,24,18,19,4,12,8,18,13,14,19,18,4,2,20,17,4)密鑰K=(2,8,15,7,4,17,2,8,15,7,4,17,2,8,15,7,4,17,2,8,15,7,4,17,2,8,15)2025/3/1144Ch3(1)-對(duì)稱加密技術(shù)對(duì)每個(gè)明文數(shù)字和對(duì)應(yīng)的密鑰數(shù)字，使用ci=(mi+ki

)mod26加密得到密文數(shù)字為C=(21,15,23,25,6,8,0,23,8,21,22,15,21,1,19,19,12,9,15,22,8,25,8,19,22,25,19)于是密文為：VPXZGIAXIVWPUBTTMJPWIZITWZT

2025/3/1145Ch3(1)-對(duì)稱加密技術(shù)維吉尼亞密碼的平安性維吉尼亞密碼是將每個(gè)明文字母映射為幾個(gè)密文字母如果密鑰字的長度是m，明文中的一個(gè)字母能夠映射成這m個(gè)可能的字母中的一個(gè)密文中字母出現(xiàn)的頻率被隱蔽了，它的平安性明顯比單表代換密碼提高了維吉尼亞密碼的密鑰空間比較大，對(duì)于長度是m的密鑰字，密鑰空間為26m當(dāng)m=5，密鑰空間所含密鑰的數(shù)量大于1.1x1072025/3/1146Ch3(1)-對(duì)稱加密技術(shù)一次一密

一次一密是非周期多表代換密碼使用與明文一樣長且無重復(fù)的隨機(jī)密鑰來加密明文，并且該密鑰使用一次后就不再使用一次一密的平安性是取決于密鑰的隨機(jī)性但產(chǎn)生大規(guī)模隨機(jī)密鑰是一件很困難的事情，目前還沒有很好的方法來解決這個(gè)問題密鑰分配也是一個(gè)難點(diǎn)，由于密鑰不允許重復(fù)使用，因此存在大量的密鑰分配問題。一次一密在實(shí)際中很少使用，主要是用于高度機(jī)密的低帶寬信道2025/3/1147Ch3(1)-對(duì)稱加密技術(shù)多字母代換密碼

前面介紹的密碼都是以單字母作為代換對(duì)象多字母代換密碼每次對(duì)多個(gè)字母進(jìn)行代換多字母代換的優(yōu)點(diǎn)是容易隱藏字母的自然出現(xiàn)頻率，有利于對(duì)抗統(tǒng)計(jì)分析Playfair密碼和Hill密碼都是多字母代換密碼2025/3/1148Ch3(1)-對(duì)稱加密技術(shù)Playfair密碼

Playfair密碼是將明文中雙字母音節(jié)作為一個(gè)代換單元Playfair算法是基于一個(gè)由密鑰組成的一個(gè)5×5階矩陣假設(shè)密鑰是monarchy，構(gòu)建矩陣的方法是將密鑰〔去掉重復(fù)的字母〕從左到右、從上到下填入矩陣中，再將剩余的字母按照字母表的順序依次填入在該矩陣中，字母i和j暫且當(dāng)一個(gè)字母。這樣可以構(gòu)成如下的密鑰矩陣。2025/3/1149Ch3(1)-對(duì)稱加密技術(shù)MONARCHYBDEFGI/JKLPQSTUVWXZ2025/3/1150Ch3(1)-對(duì)稱加密技術(shù)Playfair的加密原那么每次以兩個(gè)字母為一個(gè)單位進(jìn)行操作。(1)如果這兩個(gè)字母一樣，那么在中間插入一個(gè)字母x(事先約定的一個(gè)字母),如“balloon〞變成“balxloon〞。(2)如果明文長度不是2的倍數(shù)，那么在最后填入一個(gè)實(shí)現(xiàn)約定的字母x。如“table〞變?yōu)椤皌ablex〞。(3)如果兩個(gè)字母在矩陣的同一行，用它右邊的字母來代替(最后一個(gè)字母的右邊是第1個(gè)字母),如“ar〞加密變?yōu)椤癛M〞。(4)如果兩個(gè)字母在同一列，用它下面的字母來代替它(最底下的字母的下一個(gè)是該列第1個(gè)字母),如“mu〞加密變?yōu)椤癈M〞。(5)其他的字母都用它同一行，另一個(gè)字母的同一列相交的字母代替，如“hs〞加密變?yōu)椤癇P〞,“ea〞變?yōu)椤癐M〞或者“JM〞(由加密者自行決定)2025/3/1151Ch3(1)-對(duì)稱加密技術(shù)Playfair加密舉例例3.6假設(shè)密鑰是cipher，使用Playfair算法加密Playfaircipherwasactuallyinventedbywheatston由密鑰詞cipher可構(gòu)建密鑰矩陣：將明文按照兩個(gè)字母分組為playfaircipherwasactualxlyinventedbywheatstonx那么密文為BSDWRBCAIPHECFIKQBHOQFSPMXEKZCMUHFDXYIIFUTUQLZCIPHERABDFGKLMNOQSTUVWXYZ2025/3/1152Ch3(1)-對(duì)稱加密技術(shù)Playfair密碼的平安性Playfair密碼的平安性比單表代換密碼提高了許多雙字母共有26x26=676組合，因此頻率統(tǒng)計(jì)分析表中需要676條統(tǒng)計(jì)數(shù)據(jù)Playfair密碼中比單表代換更好地隱藏了明文中單字母的結(jié)構(gòu)在第一次世界大戰(zhàn)中被英軍作為最好的密碼系統(tǒng)使用，在第二次世界大戰(zhàn)中也曾經(jīng)被美軍和盟軍大量使用當(dāng)然現(xiàn)在看來，該密碼的平安性是很低的，它還明文的局部特征，只要給定幾百個(gè)字母的密文情況下，該加密方法就可以破解2025/3/1153Ch3(1)-對(duì)稱加密技術(shù)Hill密碼

該密碼是1929年由數(shù)學(xué)家lesterHill創(chuàng)造的一種多字母代換密碼加密算法將m個(gè)明文字母替換成m個(gè)密文字母(Hillm密碼表示m個(gè)明文字母為一組)這種代換由m個(gè)線性方程決定如果m=3，那么該密碼系統(tǒng)可以表示為：2025/3/1154Ch3(1)-對(duì)稱加密技術(shù)用向量或者矩陣表示為：其中C和M是長度為3的列向量，分別代表密文和明文，K是一個(gè)3×3的矩陣，代表加密密鑰運(yùn)算按照模26執(zhí)行。2025/3/1155Ch3(1)-對(duì)稱加密技術(shù)Hillm

密碼加密過程

將明文字母以m個(gè)字母為單位進(jìn)行分組，假設(shè)最后一組沒有m個(gè)字母，那么補(bǔ)足沒有任何實(shí)際意義的啞字母〔雙方事先可以約定這些字母〕，并用數(shù)字表示這些字母；選擇一個(gè)m階可逆方陣K，稱為Hillm密碼的加密矩陣；對(duì)每m個(gè)字母為一組的明文字母，用它對(duì)應(yīng)的值構(gòu)成一個(gè)m維向量；計(jì)算密文的值C=kmmod26，然后反查字母表的值，得到對(duì)應(yīng)的m個(gè)密文字母；同樣明文的其他組的密文。2025/3/1156Ch3(1)-對(duì)稱加密技術(shù)置換密碼代換密碼是將明文字母用不同的密文字母代替置換密碼那么保持明文的所有字母不變,只是打亂明文字母的位置和次序置換密碼實(shí)現(xiàn)方法有很多.下面介紹一種列置換加密方法假設(shè)用密鑰network，加密明文permutationcipherhidethemessagebyrearrangingtheletterorder2025/3/1157Ch3(1)-對(duì)稱加密技術(shù)將明文按照密鑰的長度一行一行地寫成一個(gè)矩陣，然后按照密鑰字母對(duì)應(yīng)的數(shù)值從小到大，按照列讀出即為密文

2025/3/1158Ch3(1)-對(duì)稱加密技術(shù)在密鑰network中，字母對(duì)應(yīng)的數(shù)字從小到大排列是eknortw，按照這個(gè)順序讀出上面矩陣的列即是密文:EIEHGRGTRAPESEIEDPTHTAANTEUCIEYNEOTIDSRGLRROREERTEMNHMBAHR置換密碼比較簡(jiǎn)單，經(jīng)不起明文攻擊但是置換密碼與代換密碼相結(jié)合，可以得到效果很好的密碼。2025/3/1159Ch3(1)-對(duì)稱加密技術(shù)數(shù)據(jù)加密標(biāo)準(zhǔn)美國國家標(biāo)準(zhǔn)局(NBS)，即現(xiàn)在的國家標(biāo)準(zhǔn)和技術(shù)研究所(NIST)于1973年5月向社會(huì)公開征集標(biāo)準(zhǔn)加密算法并公布了它的設(shè)計(jì)要求：--算法必須提供高度的平安性--算法必須有詳細(xì)的說明，并易于理解--算法的平安性取決于密鑰，不依賴于算法--算法適用于所有用戶--算法適用于不同應(yīng)用場(chǎng)合--算法必須高效、經(jīng)濟(jì)--算法必須能被證實(shí)有效2025/3/1160Ch3(1)-對(duì)稱加密技術(shù)1974年8月27日,NBS開始第二次征集，IBM提交了算法LUCIFER，該算法由Feistel領(lǐng)導(dǎo)的團(tuán)隊(duì)研究開發(fā)，采用64位分組以及128位密鑰IBM用改版的Lucifer算法參加競(jìng)爭(zhēng)，最后獲勝，成為數(shù)據(jù)加密標(biāo)準(zhǔn)(DataEncryptionStandard,DES)1976年11月23日，采納為聯(lián)邦標(biāo)準(zhǔn)，批準(zhǔn)用于非軍事場(chǎng)合的各種政府機(jī)構(gòu)。1977年1月15日，數(shù)據(jù)加密標(biāo)準(zhǔn)，即FIPSPUB46正式發(fā)布DES是分組密碼的典型代表，也是第一個(gè)被公布出來的加密標(biāo)準(zhǔn)算法?，F(xiàn)代大多數(shù)對(duì)稱分組密碼也是基于Feistel密碼結(jié)構(gòu)2025/3/1161Ch3(1)-對(duì)稱加密技術(shù)DES加密過程DES同時(shí)使用了代換和置換兩種技巧它用56位密鑰加密64位明文，最后輸出64位密文整個(gè)過程分為兩大局部組成：一是加密過程，另一是子密鑰產(chǎn)生過程圖3.4是DES加密算法簡(jiǎn)圖2025/3/1162Ch3(1)-對(duì)稱加密技術(shù)2025/3/1163Ch3(1)-對(duì)稱加密技術(shù)圖3.4左半邊的處理過程可以分三個(gè)局部：(1)64位明文經(jīng)過初始置換被重新排列，然后分左右兩半，每半各32位；(2)左右兩半經(jīng)過16輪置換和代換迭代，即16次實(shí)施相同的變換。然后再左右兩半互換；(3)互換后的左右兩半合并，再經(jīng)過逆初始置換輸出64位密文。圖3.4右半部那么由56位密鑰，產(chǎn)生16個(gè)48位子密鑰，分別供左半邊的16輪迭代加密使用2025/3/1164Ch3(1)-對(duì)稱加密技術(shù)初始置換

初始置換(InitialPermutation,IP)是數(shù)據(jù)加密的第1步將64位的明文按照?qǐng)D3.5置換。置換表中的數(shù)字表示輸入位在輸出中的位置

2025/3/1165Ch3(1)-對(duì)稱加密技術(shù)置換后將數(shù)據(jù)M分成兩局部：左半局部L0和右半局部R0各32位。劃分方法原那么是偶數(shù)位移到左半部，奇數(shù)位移到右半部，即：2025/3/1166Ch3(1)-對(duì)稱加密技術(shù)DES每輪結(jié)構(gòu)

上一輪的右邊Ri-1直接變換為下一輪的左邊Li上一輪的左邊Li-1與加密函數(shù)F異或后作為下一輪的右邊Ri加密函數(shù)F那么是上一輪右邊Ri-1和子密鑰Ki的函數(shù)。即Li=Ri–1Ri=Li–1⊕F(Ri–1,Ki)2025/3/1167Ch3(1)-對(duì)稱加密技術(shù)圖3.6DES每一輪結(jié)構(gòu)Li-1Ri-1LiRiKiF+2025/3/1168Ch3(1)-對(duì)稱加密技術(shù)加密函數(shù)F本質(zhì)上是Ri-1和子密鑰Ki的異或，如圖3.7所示但由于它們的位數(shù)不一樣，不能直接運(yùn)算從上式可以看出加密函數(shù)F是32位，而Ri-1是32位，子密鑰Ki是48位，因此Ri-1和Ki不能直接異或DES這樣處理這個(gè)問題，先用擴(kuò)展置換E(如圖3.8所示)將Ri-1擴(kuò)展為48位，與48位子密鑰異或，輸出48位，再使用8個(gè)S盒壓縮成32位，然后經(jīng)置換函數(shù)P(如圖3.9所示)輸出32位的加密函數(shù)F。2025/3/1169Ch3(1)-對(duì)稱加密技術(shù)

加密函數(shù)F的計(jì)算過程

Ki(48bits)Ri-1(32bits)48bitsE+S1S2S3S4S5S8S6S7F(32bits)P2025/3/1170Ch3(1)-對(duì)稱加密技術(shù)圖3.8擴(kuò)展置換E圖3.9置換函數(shù)P2025/3/1171Ch3(1)-對(duì)稱加密技術(shù)S盒

在加密函數(shù)計(jì)算過程中使用了8個(gè)S盒S盒是DES保密性的關(guān)鍵所在S盒是一種非線性變換，也是DES中唯一的非線性運(yùn)算S盒有6位輸入，4位輸出48位數(shù)據(jù)經(jīng)過8個(gè)S盒后輸出32位數(shù)據(jù)每個(gè)S盒都由4行(表示為0,1,2,3)和16列(0,1,…,15)組成，如圖3.10所示2025/3/1172Ch3(1)-對(duì)稱加密技術(shù)2025/3/1173Ch3(1)-對(duì)稱加密技術(shù)每行都是全部的16個(gè)長為4比特串的一個(gè)全排列每個(gè)比特串用它對(duì)應(yīng)的二進(jìn)制整數(shù)表示,如1001用9表示。對(duì)每個(gè)S盒，將6位輸入的第一位和最后一位組成一個(gè)二進(jìn)制數(shù)，用于選擇S盒中的一行。用中間的4位選擇S盒16列中的某一列，行列交叉處的十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)可得到4位輸出。例如對(duì)于S1盒而言,如果輸入為011001，那么行是01(十進(jìn)制1，即S盒的第2行)，列1100(12，即S盒的第13列)，該處的值是9，轉(zhuǎn)換為二進(jìn)制數(shù)為1001，即為該S盒的輸出2025/3/1174Ch3(1)-對(duì)稱加密技術(shù)DES子密鑰產(chǎn)生

DES加密過程共迭代16輪，每輪用一個(gè)不同的48位子密鑰子密鑰由算法的56位密鑰產(chǎn)生DES算法的輸入密鑰長度是64位，但只用了其中的56位如圖3.11所示,圖中無陰影局部，也就是每行的第8位被忽略，主要用于奇偶校驗(yàn)，也可以是隨意設(shè)置子密鑰的產(chǎn)生過程如圖3.12所示2025/3/1175Ch3(1)-對(duì)稱加密技術(shù)圖3.11DES的輸入密碼2025/3/1176Ch3(1)-對(duì)稱加密技術(shù)2025/3/1177Ch3(1)-對(duì)稱加密技術(shù)56位密鑰首先經(jīng)過置換選擇1(如圖3.13所示)將其位置打亂重排將前28位作為C0(如圖3.13的上面局部)，后28位D0(如圖3.13的下面局部)2025/3/1178Ch3(1)-對(duì)稱加密技術(shù)接下來經(jīng)過16輪，產(chǎn)生16個(gè)子密鑰每一輪迭代中,Ci-1和Di-1循環(huán)左移1位或者2位，如圖3.14所示Ci-1和Di-1循環(huán)左移后變?yōu)镃i和Di，將Ci和Di合在一起的56位，經(jīng)過置換選擇2(如圖3.15所示)，從中挑出48位作為這一輪的子密鑰再將Ci和Di循環(huán)左移后，使用置換選擇2產(chǎn)生下一輪的子密鑰，如此繼續(xù)，產(chǎn)生所有16個(gè)子密鑰。2025/3/1179Ch3(1)-對(duì)稱加密技術(shù)圖3.14每輪左移次數(shù)的規(guī)定圖3.15置換選擇22025/3/1180Ch3(1)-對(duì)稱加密技術(shù)DES解密

DES解密過程與加密過程本質(zhì)上一致加密和解密使用同一個(gè)算法，使用相同的步驟和相同的密鑰主要不同點(diǎn)是將密文作為算法的輸入，但是逆序使用子密鑰ki，即第1輪使用子密鑰k16，第2輪使用子密鑰k15，最后一輪使用子密鑰k1

2025/3/1181Ch3(1)-對(duì)稱加密技術(shù)DES的強(qiáng)度

從發(fā)布時(shí)起，DES就備受爭(zhēng)議爭(zhēng)論的焦點(diǎn)主要集中在密鑰的長度、迭代次數(shù)以及S盒的設(shè)計(jì)等方面DES的平安性是依賴S盒,但是S盒設(shè)計(jì)詳細(xì)標(biāo)準(zhǔn)至今沒有公開有人疑心S盒里隱藏了陷門〔trapdoors〕。然而到目前為止也沒有任何證據(jù)證明DES里確實(shí)存在陷門。事實(shí)上，后來說明S盒是被設(shè)計(jì)成能夠防止差分密碼分析DES是將Lucifer算法作為標(biāo)準(zhǔn)，Lucifer算法的密鑰長度128位，但DES將密鑰長度改為56位,這不能抵抗窮盡密鑰搜索攻擊2025/3/1182Ch3(1)-對(duì)稱加密技術(shù)1997年，克羅拉多州的程序員Verser在Inrernet上數(shù)萬名志愿者的協(xié)作下用96天的時(shí)間找到了密鑰長度為40位和48位的DES密鑰1998年電子邊境基金會(huì)〔EFF〕使用一臺(tái)價(jià)值25萬美元的計(jì)算機(jī)在56小時(shí)之內(nèi)破譯了56位的DES1999年，電子邊境基金會(huì)〔EFF〕通過互聯(lián)網(wǎng)上的10萬臺(tái)計(jì)算機(jī)合作，僅用22小時(shí)15分破譯了56位的DES另外，DES存在弱密鑰。如果一個(gè)密鑰所產(chǎn)生的所有子密鑰都是一樣的，那么這個(gè)外部密鑰就稱為弱密鑰DES的密鑰置換后分成兩半，每一半各自獨(dú)立移位。如果每一半的所有位都是“0〞或者“1〞，那么在算法的任意一輪所有的子密鑰都是相同的2025/3/1183Ch3(1)-對(duì)稱加密技術(shù)三重DES

DES由于平安問題，美國政府于1998年12月宣布DES不再作為聯(lián)邦加密標(biāo)準(zhǔn)新的美國聯(lián)邦加密標(biāo)準(zhǔn)是高級(jí)加密標(biāo)準(zhǔn)(ASE)在新的加密標(biāo)準(zhǔn)實(shí)施之前，為了使已有的DES算法投資不浪費(fèi)，NIST在1999年發(fā)布了一個(gè)新版本的DES標(biāo)準(zhǔn)〔FIPSPUB46-3〕，該標(biāo)準(zhǔn)指出DES僅能用于遺留的系統(tǒng)，同時(shí)將三重DES〔簡(jiǎn)寫為3DES〕取代DES成為新的標(biāo)準(zhǔn)3DES存在幾個(gè)優(yōu)點(diǎn)。首先它的密鑰長度是168位，足以抵抗窮舉攻擊。其次，3DES的底層加密算法與DES的加密算法相同，該加密算法比任何其它加密算法受到分析的時(shí)間要長得多，也沒有發(fā)現(xiàn)有比窮舉攻擊更有效的密碼分析攻擊方法2025/3/1184Ch3(1)-對(duì)稱加密技術(shù)但是雙重DES不平安雙重DES存在中間相遇攻擊，使它的強(qiáng)度跟一個(gè)56位DES強(qiáng)度差不多如果C=EK2[EK1[M]]，令X=EK1[M]=DK2[C]。假設(shè)(M,C)，攻擊方法如下：--先用256個(gè)可能的K1加密M，得到256個(gè)可能的值，將這些值從小到大存入一個(gè)表中--再對(duì)256個(gè)可能的K2解密C，每次做完解密，將所得的值與表中的值比較，如果產(chǎn)生匹配，那么它們對(duì)應(yīng)的密鑰可能是K1和K2--用一個(gè)新的明文密文對(duì)檢測(cè)所得兩個(gè)密鑰，如果兩密鑰產(chǎn)生正確的密文，那么它們是正確的密鑰2025/3/1185Ch3(1)-對(duì)稱加密技術(shù)為防止中間相遇攻擊，可以采用3次加密方式，如圖3.17所示這是使用兩個(gè)密鑰的三重EDS，采用加密—解密—加密(E-D-E)方案注意的是,加密與解密在平安性上來說是等價(jià)的。這種加密方案窮舉攻擊代價(jià)是2112EEK1K1CMB加密解密DK2ADDK1K1MCAEK2B2025/3/1186Ch3(1)-對(duì)稱加密技術(shù)目前還沒有針對(duì)兩個(gè)密鑰的三重DES實(shí)際的攻擊方法但是感覺它不大可靠，如果采用三把密鑰的三重DES那么比較放心三把密鑰的三重DES的密鑰長度是168位，采用加密—解密—加密(E-D-E)方案其加密過程為C=EK3[DK2[EK1[M]]]，解密過程為M=DK1[EK2[DK3[C]]]這種加密方式已經(jīng)被一些網(wǎng)絡(luò)應(yīng)用采用,如本書后面章節(jié)要討論的PGP和S/MIME采用了這種方案2025/3/1187Ch3(1)-對(duì)稱加密技術(shù)高級(jí)加密標(biāo)準(zhǔn)

DES存在平安問題，而三重DES算法運(yùn)行速度比較慢其次三重DES的分組長度為64位，就效率和平安性而言，分組長度應(yīng)該更長美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)在1997年公開征集新的高級(jí)加密標(biāo)準(zhǔn)〔AdvancedEncryptionStandards,AES〕要求AES比3DES快而且至少和3DES一樣平安，并特別提出高級(jí)加密標(biāo)準(zhǔn)的分組長度為128位的對(duì)稱分組密碼，密鑰長度支持128位、192位、256位。2025/3/1188Ch3(1)-對(duì)稱加密技術(shù)1997年9月給出的選擇高級(jí)加密標(biāo)準(zhǔn)的評(píng)估準(zhǔn)那么是：--平安性--代價(jià)：指計(jì)算效率方面--算法和執(zhí)行特征：指算法的靈活性、簡(jiǎn)潔性以及硬件與軟件平臺(tái)的適應(yīng)性等方面1998年6月NIST共收到21個(gè)提交的算法，在同年的8月首先選出15個(gè)候選算法1999年NIST從15個(gè)AES候選算法中遴選出5個(gè)候選算法2025/3/1189Ch3(1)-對(duì)稱加密技術(shù)它們是：MARS〔由IBM公司研究部門的一個(gè)龐大團(tuán)隊(duì)發(fā)布，對(duì)它的評(píng)價(jià)是算法復(fù)雜、速度快、平安性高〕RC6〔由RSA實(shí)驗(yàn)室發(fā)布，對(duì)它的評(píng)價(jià)是極簡(jiǎn)單、速度極快、平安性低〕Rijndael〔由JoanDaemen和VincentRijmen兩位比利時(shí)密碼專家發(fā)布，對(duì)它的評(píng)價(jià)是算法簡(jiǎn)潔、速度快、平安性好〕Serpent〔由RossAnderson,EliBiham和LarsKnudsen發(fā)布，對(duì)它的評(píng)價(jià)是算法簡(jiǎn)潔、速度慢、平安性極高〕Twofish〔由Counterpane公司一個(gè)龐大的團(tuán)隊(duì)發(fā)布，對(duì)它的評(píng)價(jià)是算法復(fù)雜、速度極快、平安性高〕2025/3/1190Ch3(1)-對(duì)稱加密技術(shù)從全方位考慮，Rijndael(讀成RainDoll〕會(huì)聚了平安，性能，效率，易用和靈活等優(yōu)點(diǎn)，使它成為AES最適宜的選擇2000年10月Rijndael算法被選為高級(jí)加密標(biāo)準(zhǔn)2001年11月發(fā)布為聯(lián)邦信息處理標(biāo)準(zhǔn)(FederalInformationProcessingStandard，F(xiàn)IPS),用于美國政府組織保護(hù)敏感信息的一種特殊的加密算法，即FIPSPUB197標(biāo)準(zhǔn)2025/3/1191Ch3(1)-對(duì)稱加密技術(shù)AES的根本運(yùn)算AES算法中有些是以字節(jié)為單位進(jìn)行運(yùn)算也有的是以4個(gè)字節(jié)〔即一個(gè)字〕為單位的AES將一個(gè)字節(jié)看作是在有限域GF(28)上的一個(gè)元素一個(gè)字看成是系數(shù)取自GF(28)，并且次數(shù)小于4的多項(xiàng)式。2025/3/1192Ch3(1)-對(duì)稱加密技術(shù)AES中的字節(jié)運(yùn)算

AES中一個(gè)字節(jié)是用有限域GF(28)上的元素表示有限域上的元素有多種表示方法，AES主要采用多項(xiàng)式表示有限域GF(28)上的加法定義為二進(jìn)制多項(xiàng)式的加法,其系數(shù)是模2相加,加法即異或運(yùn)算(記為)對(duì)于兩個(gè)字節(jié)和其和為,

2025/3/1193Ch3(1)-對(duì)稱加密技術(shù)下述表達(dá)式彼此等價(jià)：(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2

-------(多項(xiàng)式記法){01010111}{10000011}={11010100} -------(二進(jìn)制記法){57}{83}={d4} -------(十六進(jìn)制記法)2025/3/1194Ch3(1)-對(duì)稱加密技術(shù)在有限域GF(28)上的乘法(記為)定義為多項(xiàng)式的乘積模一個(gè)次數(shù)為8的不可約多項(xiàng)式：用十六進(jìn)制表示該多項(xiàng)式為{01}{1b}例如，{57}{83}={c1}，因?yàn)?x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=x13+x11+x9+x8+x6+x5+x4+x3+1而(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)=x7+x6+12025/3/1195Ch3(1)-對(duì)稱加密技術(shù)模m(x)確保了所得結(jié)果是次數(shù)小于8的二進(jìn)制多項(xiàng)式，因此可以用一個(gè)字節(jié)表示在AES中的倍乘函數(shù)xtime()是用多項(xiàng)式x乘一個(gè)二進(jìn)制多項(xiàng)式后再模m(x)用多項(xiàng)式x乘以b(x)將得到

將上述結(jié)果模m(x)即可得到xb(x)的結(jié)果。如果b7=0，那么該結(jié)果已經(jīng)是模運(yùn)算后的形式.如果b7=1,那么模運(yùn)算需要異或多項(xiàng)式m(x)完成.由此,乘x(即{00000010}或十六進(jìn)制{02})可通過字節(jié)內(nèi)左移一位,緊接著的一個(gè)與{1B}按位異或來實(shí)現(xiàn).將該操作記為b=xtime(a)通過將中間結(jié)果相加,可以用xtime()實(shí)現(xiàn)任意常數(shù)的乘法。2025/3/1196Ch3(1)-對(duì)稱加密技術(shù)2025/3/1197Ch3(1)-對(duì)稱加密技術(shù)AES中的字運(yùn)算

AES中的32位字表示為系數(shù)在有限域GF(28)上的次數(shù)小于4的多項(xiàng)式考慮含有4個(gè)項(xiàng)、且系數(shù)為有限域元素的多項(xiàng)式，即它可以表示為如下形式[]的字注意這里的多項(xiàng)式與前面有限域元素定義中使用的多項(xiàng)式操作不同這里的系數(shù)本身就是有限域元素，即字節(jié)(bytes)而不是位(bits)另外,該4項(xiàng)多項(xiàng)式的乘法使用了一個(gè)不同于前面的模多項(xiàng)式,將在下面定義

2025/3/1198Ch3(1)-對(duì)稱加密技術(shù)為說明加法和乘法運(yùn)算,令加法是對(duì)x相應(yīng)次數(shù)項(xiàng)的有限域系數(shù)進(jìn)行相加運(yùn)算。該加法對(duì)應(yīng)于相應(yīng)字節(jié)間的異或運(yùn)算乘法要用兩步完成。第一步，對(duì)多項(xiàng)式相乘的結(jié)果進(jìn)行代數(shù)擴(kuò)展2025/3/1199Ch3(1)-對(duì)稱加密技術(shù)所得結(jié)果c(x)并沒有表示為一個(gè)4字節(jié)的字乘法的第二步是模一個(gè)4次多項(xiàng)式來化簡(jiǎn)c(x)，使得結(jié)果化簡(jiǎn)為一個(gè)次數(shù)小于4的多項(xiàng)式在AES算法中，這一模多項(xiàng)式取為2025/3/11100Ch3(1)-對(duì)稱加密技術(shù)2025/3/11101Ch3(1)-對(duì)稱加密技術(shù)當(dāng)a(x)是一個(gè)固定多項(xiàng)式時(shí)，等式中定義的運(yùn)算可以寫成矩陣形式，如由于x4+1不是GF(28)上的不可約多項(xiàng)式，因此被一個(gè)固定的4次多項(xiàng)式相乘的乘法不一定可逆然而，在AES算法中選擇了一個(gè)固定的有逆元的4項(xiàng)多項(xiàng)式的乘法，它按照乘法運(yùn)算有逆元

2025/3/11102Ch3(1)-對(duì)稱加密技術(shù)AES加密

在Rijndael算法中,分組長度和密鑰長度分別可以是128位、192位、256位而在AES中,分組長度只是128位AES算法中根本的運(yùn)算單位是字節(jié),即視為一個(gè)整體的8比特序列如果分組長度和密鑰長度為128位，假設(shè)字節(jié)數(shù)組將表示為如下形式：其字節(jié)排列方式如圖3.18所示。2025/3/11103Ch3(1)-對(duì)稱加密技術(shù)a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15128位〔16個(gè)字節(jié)〕的矩陣排列2025/3/11104Ch3(1)-對(duì)稱加密技術(shù)如果密鑰長度〔或在Rijndael中的明文分組〕為192位、256位時(shí)，組成的兩個(gè)矩陣如圖3.19和圖3.20所示它們的特點(diǎn)是行數(shù)都是4，列數(shù)不同2025/3/11105Ch3(1)-對(duì)稱加密技術(shù)192位〔24個(gè)字節(jié)〕的矩陣排列a0a4a8a12a16a20a1a5a9a13a17a21a2a6a10a14a18a22a3a7a11a15a19a232025/3/11106Ch3(1)-對(duì)稱加密技術(shù)a0a4a8a12a16a20a24a28a1a5a9a13a17a21a25a29a2a6a10a14a18a22a26a30a3a7a11a15a19a23a27a31256位〔32個(gè)字節(jié)〕的矩陣排列2025/3/11107Ch3(1)-對(duì)稱加密技術(shù)這些矩陣有4行，分組的列數(shù)記為Nb，Nb=分組長度〔bits〕÷32(bits)。顯然Nb可以取的值為4、6和8，分別對(duì)應(yīng)的分組長度為128位、192位和256位類似地密鑰的列數(shù)記為Nk，Nk=密鑰長度〔bits〕÷32(bits)。Nk可以取的值為4、6和8，對(duì)應(yīng)的密鑰長度分別為128位、192位和256位。2025/3/11108Ch3(1)-對(duì)稱加密技術(shù)密碼運(yùn)算的中間結(jié)果都是以上面的形式表示，稱之為狀態(tài)〔State〕數(shù)組AES將這些中間結(jié)果復(fù)制到狀態(tài)〔State〕數(shù)組中算法的運(yùn)行過程是將需要加密的分組從一個(gè)狀態(tài)轉(zhuǎn)換為另一個(gè)狀態(tài)，最后該數(shù)組被復(fù)制到輸出矩陣中如對(duì)于128位分組，假設(shè)加密和解密的初始階段將輸入字節(jié)數(shù)組為復(fù)制到如圖3.21所示的狀態(tài)〔State〕矩陣中。加密或解密的運(yùn)算都在該狀態(tài)矩陣上進(jìn)行，最后的結(jié)果將被復(fù)制到輸出字節(jié)數(shù)組。2025/3/11109Ch3(1)-對(duì)稱加密技術(shù)狀態(tài)矩陣中每一列的四個(gè)字節(jié)可以看作一個(gè)32-bit字，用行號(hào)r作為每一個(gè)字中四個(gè)字節(jié)的索引狀態(tài)可以看作32-bit字(列),的一維數(shù)組，用列號(hào)c表示該數(shù)組的索引2025/3/11110Ch3(1)-對(duì)稱加密技術(shù)AES密碼是一種迭代式密碼結(jié)構(gòu)，但不是Feistel密碼結(jié)構(gòu)Rijndael算法迭代的輪數(shù)與分組長度和密鑰長度相關(guān)對(duì)于AES算法，算法的輪數(shù)依賴于密鑰長度將輪數(shù)表示為Nr，當(dāng)Nk=4時(shí)Nr＝10；當(dāng)Nk=6時(shí)Nr＝12；當(dāng)Nk=8時(shí)Nr＝142025/3/11111Ch3(1)-對(duì)稱加密技術(shù)AES加密過程

當(dāng)分組長度和密鑰長度均為128位時(shí)，AES共迭代10輪，需要11個(gè)子密鑰其加密過程如圖3.22所示前面9輪完全相同，每輪包括4階段，分別是字節(jié)代換〔ByteSubstitution〕、行移位〔ShiftRows〕、列混淆〔MixColumns〕和輪密鑰加〔AddRoundKey〕最后一輪只3個(gè)階段，缺少列混淆。2025/3/11112Ch3(1)-對(duì)稱加密技術(shù)輪密鑰加字節(jié)代換行移位列混淆輪密鑰加字節(jié)代換行移位列混淆輪密鑰加密文字節(jié)代換行移位輪密鑰加…明文第1輪第9輪第10輪子密鑰w[0,3]子密鑰w[4,7]子密鑰w[36,39]子密鑰w[40,43]2025/3/11113Ch3(1)-對(duì)稱加密技術(shù)字節(jié)代換

字節(jié)代換(SubBytes())是一個(gè)非線性的字節(jié)代換它獨(dú)立地將狀態(tài)中的每個(gè)字節(jié)利用代換表(S盒)進(jìn)行運(yùn)算S盒被設(shè)計(jì)成能夠抵擋所有的攻擊S盒〔如圖3.24所示〕是由16×16個(gè)字節(jié)組成的矩陣，包含了8位值所能表達(dá)的256種可能的變換State中的每個(gè)字節(jié)按照如下的方式映射為一個(gè)新的字節(jié)：將該字節(jié)的高4位作為行值，低4位作為列值，然后取出S盒中對(duì)應(yīng)行列交叉處的元素作為輸出例如，十六進(jìn)制{95}對(duì)應(yīng)的S盒的行值是9，列值是5，S盒中此處的值是{2A}。因此{(lán)95}被映射為{2A}2025/3/11114Ch3(1)-對(duì)稱加密技術(shù)2025/3/11115Ch3(1)-對(duì)稱加密技術(shù)S盒的構(gòu)造方法

逐行按照上升排列的方式初始化S盒。第一行是{00}，{01}，…，{0F}；第二行是{10}，{11}，…，{1F}等。因此在x行y列的字節(jié)值是{xy}把S盒中的每個(gè)字節(jié)映射為它在有限域GF(28)上的乘法逆；其中，元素{00}映射到它自身{00}把S盒中的每個(gè)字節(jié)表示為()8位，對(duì)S盒中的