第3講-對(duì)稱(chēng)密鑰密碼體制

第3講

對(duì)稱(chēng)密鑰密碼體制1按加解密采用的密鑰不同按密碼出現(xiàn)的時(shí)間不同古典密碼現(xiàn)代密碼密碼學(xué)（Cryptology）(Symmetriccipher)(Asymmetriccipher)分組密碼流密碼公鑰密碼按加密的方式對(duì)稱(chēng)密碼非對(duì)稱(chēng)密碼(Classicalcipher)(Moderncipher)(Blockcipher)(Streamcipher)(Public-Keycipher)什么是流密碼一次一密：指在流密碼當(dāng)中使用與消息長(zhǎng)度等長(zhǎng)的隨機(jī)密鑰,密鑰本身只使用一次流密碼的研究現(xiàn)狀當(dāng)前對(duì)流密碼的研究主要集中在以下兩個(gè)方向：（1）什么樣的序列可以作為安全可靠的密鑰序列？即衡量密鑰流序列好壞的標(biāo)準(zhǔn)。（2）如何構(gòu)造線(xiàn)性復(fù)雜度高、周期大的密鑰流序列？在保密強(qiáng)度要求高的場(chǎng)合如大量軍事密碼系統(tǒng)，仍多采用流密碼，美軍的核心密碼仍是“一次一密”的流密碼體制。鑒于流密碼的分析和設(shè)計(jì)在軍事和外交保密通信中有重要價(jià)值，流密碼的設(shè)計(jì)基本上都是保密的，國(guó)內(nèi)外少有專(zhuān)門(mén)論述流密碼學(xué)的著作，公開(kāi)的文獻(xiàn)也不多。盡管如此，由于流密碼長(zhǎng)度可靈活變化，且具有運(yùn)算速度快、密文傳輸中沒(méi)有差錯(cuò)或只有有限的錯(cuò)誤傳播等優(yōu)點(diǎn)，目前仍是國(guó)際密碼應(yīng)用的主流，而基于偽隨機(jī)序列的流密碼是當(dāng)今最通用的密碼系統(tǒng)。流密碼的研究現(xiàn)狀3.1

流密碼在流密碼中，將明文消息按一定長(zhǎng)度分組（長(zhǎng)度較小，通常按字或字節(jié)），然后對(duì)各組用相關(guān)但不同的密鑰進(jìn)行加密，產(chǎn)生相應(yīng)的密文，相同的明文分組會(huì)因在明文序列中的位置不同而對(duì)應(yīng)于不同的密文分組。相對(duì)分組密碼而言，流密碼主要有以下優(yōu)點(diǎn)：第一，在硬件實(shí)施上，流密碼的速度一般要比分組密碼快，而且不需要有很復(fù)雜的硬件電路：第二，在某些情況下（例如對(duì)某些電信上的應(yīng)用），當(dāng)緩沖不足或必須對(duì)收到的字符進(jìn)行逐一處理時(shí)，流密碼就顯得更加必要和恰當(dāng)；第三，流密碼能較好地隱藏明文的統(tǒng)計(jì)特征等。流密碼的原理在流密碼中，明文按一定長(zhǎng)度分組后被表示成一個(gè)序列，并稱(chēng)為明文流，序列中的一項(xiàng)稱(chēng)為一個(gè)明文字。加密時(shí)，先由主密鑰產(chǎn)生一個(gè)密鑰流序列，該序列的每一項(xiàng)和明文字具有相同的比特長(zhǎng)度，稱(chēng)為一個(gè)密鑰字。然后依次把明文流和密鑰流中的對(duì)應(yīng)項(xiàng)輸入加密函數(shù)，產(chǎn)生相應(yīng)的密文字，由密文字構(gòu)成密文流輸出。即 設(shè)明文流為：M=m1

m2…mi…

密鑰流為：K=k1

k2…ki…

則加密為：C=c1

c2…ci…=Ek1(m1)Ek2(m2)…Eki(mi)…

解密為：M=m1

m2…mi…=Dk1(c1)Dk2(c2)…Dki(ci)…流密碼通信模式框圖加密算法E密文ci=Ek(mi)解密算法D明文mi=Dk(ci)明文mi密鑰ki密鑰ki流密碼的原理例

設(shè)明文、密鑰、密文都是F2上的二元數(shù)字序列，明文m=m1m2···，密鑰為k=k1k2···，若加密變換與解密變換都是F2中的模2加法，試寫(xiě)出加密過(guò)程與解密過(guò)程。

[解]經(jīng)加密變換得密文：

C=Ek(m)=Ek1(m1)Ek2(m2)···=(k1+m1)(k2+m2)···

經(jīng)解密變換得：

Dk(C)=Dk((k1+m1)(k2+m2)···)=(k1+k1+m1)(k2+k2+m2)···

由于ki∈F2，則ki+ki=0，i=1,2,···，故Dk(C)=m1m2···=m。密文C可由明文m與密鑰k進(jìn)行模2加獲得。因此要用該密碼系統(tǒng)通信就要求每發(fā)送一條消息都要產(chǎn)生一個(gè)新的密鑰并在一個(gè)安全的信道上傳送，習(xí)慣上人們稱(chēng)這種通信系統(tǒng)為“一次一密系統(tǒng)”。流密碼的時(shí)變性--隨時(shí)間而變化流密碼采用了類(lèi)似于一次一密的思想，但加密各明文字的密鑰字不是獨(dú)立隨機(jī)選取的，而是由一個(gè)共同的較短的主密鑰按一個(gè)算法產(chǎn)生的。因此，它不具有一次一密的無(wú)條件安全性，但增加了實(shí)用性，只要算法設(shè)計(jì)得當(dāng)，其安全性可以滿(mǎn)足實(shí)際應(yīng)用的需要。密鑰流中的元素的產(chǎn)生由i時(shí)刻的流密碼內(nèi)部狀態(tài)（記作）和種子密鑰（記作k）決定，即；加密變換與解密變換也和i時(shí)刻的流密碼內(nèi)部狀態(tài)有關(guān)。流密碼分類(lèi)用狀態(tài)轉(zhuǎn)移函數(shù)描述流密碼加密器中存儲(chǔ)器的狀態(tài)隨時(shí)間變化的過(guò)程。同步流密碼：如果某個(gè)流密碼中的狀態(tài)轉(zhuǎn)移函數(shù)不依賴(lài)被輸入加密器存儲(chǔ)器的明文，即密鑰流的生成獨(dú)立于明文流和密文流的流密碼稱(chēng)為同步流密碼。使用最廣泛。自同步流密碼也叫異步流密碼：狀態(tài)轉(zhuǎn)移函數(shù)與輸入明文有關(guān)，即其中密鑰流的產(chǎn)生并不是獨(dú)立于明文流和密文流的。通常第i個(gè)密鑰字的產(chǎn)生不僅與主密鑰有關(guān)，而且與前面已經(jīng)產(chǎn)生的若干個(gè)密文字（與明文字）有關(guān)。加密算法E密鑰流發(fā)生器解密算法D密鑰流發(fā)生器安全通道密鑰k密文流ci密鑰流ki密鑰流ki明文流mi明文流mi圖1同步流密碼模型內(nèi)部狀態(tài)輸出函數(shù)內(nèi)部狀態(tài)輸出函數(shù)密鑰發(fā)生器密鑰發(fā)生器明文流mi密文流ci明文流mi種子k種子kkk圖2自同步流密碼模型同步流密碼中，消息的發(fā)送者和接收者必須同步才能做到正確地加密解密，即雙方使用相同的密鑰，并用其對(duì)同一位置進(jìn)行操作。一旦由于密文字符在傳輸過(guò)程中被插入或刪除而破壞了這種同步性，那么解密工作將失敗。否則，需要在密碼系統(tǒng)中采用能夠建立密鑰流同步的輔助性方法。分解后的同步流密碼密鑰流生成器密鑰流生成器設(shè)計(jì)中，在考慮安全性要求的前提下還應(yīng)考慮以下兩個(gè)因素：

密鑰k易于分配、保管、更換簡(jiǎn)單；易于實(shí)現(xiàn)，快速。目前密鑰流生成器大都是基于移位寄存器的。因?yàn)橐莆患拇嫫鹘Y(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)且運(yùn)行速度快。這種基于移位寄存器的密鑰流序列稱(chēng)為移位寄存器序列。密鑰流生成器一個(gè)反饋移位寄存器由兩部分組成：移位寄存器和反饋函數(shù),構(gòu)成一個(gè)密鑰流生成器。每次輸出一位，移位寄存器中所有位都右移一位，新的最左端的位根據(jù)寄存器中其它位計(jì)算得到。移位寄存器輸出的一位常常是最低有效位。移位寄存器的周期是指輸出序列從開(kāi)始到重復(fù)時(shí)的長(zhǎng)度。這種方法通過(guò)一個(gè)種子（有限長(zhǎng)）產(chǎn)生具有足夠長(zhǎng)周期的、隨機(jī)性良好的序列。只要生成方法和種子都相同，就會(huì)產(chǎn)生完全相同的密鑰流。反饋函數(shù)若，則該LFSR生成的序列為周期序列。又稱(chēng)為n階線(xiàn)性遞歸關(guān)系密鑰流生成器最簡(jiǎn)單的反饋移位寄存器是線(xiàn)性移位寄存器（LFSR），反饋函數(shù)是寄存器中某些位的簡(jiǎn)單異或。如教材P64圖4.5。異或(XOR)運(yùn)算，異或密文和相同的密鑰流就可以完成解密操作。流密碼基于XOR運(yùn)算具有下列屬性：如果B=A⊕K，那么A=B⊕K。n級(jí)移位寄存器（見(jiàn)下圖）開(kāi)始時(shí)，設(shè)第1級(jí)內(nèi)容是an-1，第2級(jí)內(nèi)容是an-2,···,第n級(jí)內(nèi)容是a0，則稱(chēng)這個(gè)寄存器的初始狀態(tài)是(a0,a1,···,an-1)。當(dāng)加上一個(gè)脈沖時(shí)，每個(gè)寄存器的內(nèi)容移給下一級(jí)，第n級(jí)內(nèi)容輸出，同時(shí)將各級(jí)內(nèi)容送給運(yùn)算器f(x0,x1,···,xn-1)，并將運(yùn)算器的結(jié)果an=f(a0,a1,…,an-1)反饋到第一級(jí)去。這樣這個(gè)移位寄存器的狀態(tài)就是(a1,a2,···,an)，而輸出是a0。不斷地加脈沖，上述

n

級(jí)移位寄存器的輸出就是一個(gè)二元(或q元)序列：a0,a1,a2,···寄存器1寄存器2寄存器3寄存器nf(x0,x1,···,xn-1)···密鑰流生成器移位寄存器產(chǎn)生的序列都是周期序列，周期都不大于2n。例

右圖是一個(gè)4級(jí)線(xiàn)性移位寄存器。給定初狀態(tài)(0001)，求該移位寄存器產(chǎn)生的周期序列。

[解]易見(jiàn)f(x0，x1，x2，x3)=x0+x1，因此對(duì)k≥4有ak=ak-3+ak-4

從而該4級(jí)移位寄存器產(chǎn)生的序列是周期15的序列：

000100110101111…線(xiàn)性移存器序列的最長(zhǎng)周期為2n－1由上例知，移位寄存器(簡(jiǎn)記SR，ShiftedRegister)可由短的序列生成具有一定規(guī)律的長(zhǎng)序列。這種序列便可以作為密鑰流序列，但抗攻擊能力較差。+密鑰流生成器狀態(tài)轉(zhuǎn)移和相應(yīng)輸出

時(shí)刻狀態(tài)輸出32100000011110000201000300100410011511000601100710111801011910100101101111111001211111130111114001111500011

多項(xiàng)式以L(fǎng)FSR的反饋系數(shù)所決定的多項(xiàng)式

又稱(chēng)反饋多項(xiàng)式、連接多項(xiàng)式。式中，c0=cn=1互反多項(xiàng)式

稱(chēng)作是LFSR的特征多項(xiàng)式。cn0稱(chēng)之為非奇異LFSR。

收縮密鑰流生成器（見(jiàn)右圖）通常的密鑰流生成器都是由若干個(gè)移位寄存器并聯(lián)，并且與特殊的電子電路組合而成。上圖為由兩個(gè)移位寄存器構(gòu)成的收縮密鑰流生成器，通過(guò)SR1的輸出選擇SR2的輸出來(lái)生成密鑰流，其工作模式如下：輸入?yún)?shù)：兩個(gè)移位寄存器的級(jí)數(shù)及反饋函數(shù)密鑰：兩個(gè)移位寄存器的初始狀態(tài)

(1)移位SR1

并產(chǎn)生yi(1)

；同時(shí)移位SR2

并產(chǎn)生yi(2)

；

(2)如果yi(1)=1，則輸出密鑰元素ki=yi(2)

；如果yi(1)=0，則刪去

yi(2)，i=1,2,…，不輸出。由此收縮生成器產(chǎn)生的密鑰流為{ki|i≥1}。SR1SR2yi(1)輸出kiyi(2)密鑰流生成器流密碼對(duì)密鑰流的要求沒(méi)有絕對(duì)不可破的密碼，比如窮搜索總能破譯，只是破譯所需時(shí)間是否超過(guò)信息的有效期以及破譯所需代價(jià)是否值得。若一個(gè)加密算法沒(méi)有比窮搜索更好的破譯方法，則被認(rèn)為是不可破的。實(shí)際使用的密鑰流序列（簡(jiǎn)稱(chēng)密鑰）都是按一定算法生成的，因而不可能是完全隨機(jī)的，所以也就不可能是完善保密系統(tǒng)。為了盡可能提高系統(tǒng)的安全強(qiáng)度，就必須要求所產(chǎn)生的密鑰流序列盡可能具有隨機(jī)序列的某些特征。如極大的周期、良好的統(tǒng)計(jì)特性。3.2

分組密碼其他分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)DESFeistel密碼結(jié)構(gòu)分組密碼的設(shè)計(jì)原則分組密碼的原理分組密碼的典型攻擊方法1.分組密碼的原理密文中的每位數(shù)字不僅僅與某時(shí)刻輸入的明文數(shù)字有關(guān)，而是與該明文中一定組長(zhǎng)的明文數(shù)字有關(guān)。分組密碼將明文按一定的位長(zhǎng)分組，輸出是固定長(zhǎng)度的密文。加密算法解密算法明文x=(x1,x2,···)密文y=(y1,y2,···,yn)明文x=(x1,x2,···)密鑰k=(k1,k2,···)密鑰k=(k1,k2,···)分組密碼的基本模型分組密碼的長(zhǎng)度明文為分組長(zhǎng)度為m的序列，密文為分組長(zhǎng)度為n的序列：n>m，稱(chēng)其為有數(shù)據(jù)擴(kuò)展的分組密碼；n<m，稱(chēng)其為有數(shù)據(jù)壓縮的分組密碼；n=m，稱(chēng)其為無(wú)數(shù)據(jù)擴(kuò)展與壓縮的分組密碼。我們一般所說(shuō)的分組密碼為無(wú)數(shù)據(jù)擴(kuò)展與壓縮的分組密碼。典型的分組是64位或128位分組密碼的特點(diǎn)主要優(yōu)點(diǎn)：易于標(biāo)準(zhǔn)化；易于實(shí)現(xiàn)同步。主要缺點(diǎn)：不善于隱藏明文的數(shù)據(jù)模式、對(duì)于重放、插入、刪除等攻擊方式的抵御能力不強(qiáng)。分組密碼的數(shù)學(xué)表示記明文空間和密文空間為（明文與密文分組的長(zhǎng)度均為m），密鑰空間為（是的子集，r為密鑰長(zhǎng)度）：密鑰k下的加密函數(shù)為，m表示待加密的信息，k為密鑰，則可將該映射記為，這個(gè)映射應(yīng)滿(mǎn)足：，是的一個(gè)置換；密鑰k下的解密函數(shù)記為，它是的逆。2.分組密碼的設(shè)計(jì)原則安全性角度：“混亂原則”：為了避免密碼分析者利用明文與密文之間的依賴(lài)關(guān)系進(jìn)行破譯，密碼的設(shè)計(jì)應(yīng)該保證這種依賴(lài)關(guān)系足夠復(fù)雜?！皵U(kuò)散原則”：為避免密碼分析者對(duì)密鑰逐段破譯，密碼的設(shè)計(jì)應(yīng)該保證密鑰的每位數(shù)字能夠影響密文中的多位數(shù)字；同時(shí)，為了避免避免密碼分析者利用明文的統(tǒng)計(jì)特性，密碼的設(shè)計(jì)應(yīng)該保證明文的每位數(shù)字能夠影響密文中的多位數(shù)字，從而隱藏明文的統(tǒng)計(jì)特性。2.分組密碼的設(shè)計(jì)原則可實(shí)現(xiàn)性角度：應(yīng)該具有標(biāo)準(zhǔn)的組件結(jié)構(gòu)（子模塊），以適應(yīng)超大規(guī)模集成電路的實(shí)現(xiàn)。分組密碼的運(yùn)算能在子模塊上通過(guò)簡(jiǎn)單的運(yùn)算進(jìn)行。3.3Feistel密碼結(jié)構(gòu)加密:

Li=Ri-1

Ri=Li-1F(Ri-1,Ki)解密:

Ri-1=Li

Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel結(jié)構(gòu)依賴(lài)參數(shù)和特征分組長(zhǎng)度：分組長(zhǎng)度越長(zhǎng)意味著安全性越高（其他條件不變），但是會(huì)降低加解密的速度。一般64位的分組長(zhǎng)度。密鑰長(zhǎng)度：密鑰較長(zhǎng)意味著安全性較高，但會(huì)降低加解密的速度。一般需要128位密鑰，64位密鑰通常不夠。迭代輪數(shù)：Feistel密碼的本質(zhì)在于單輪不能提供足夠的安全性，多輪可取得很高安全性。迭代輪數(shù)的典型值為16。子密鑰產(chǎn)生算法：子密鑰越復(fù)雜，密碼分析攻擊越困難。輪函數(shù)：輪函數(shù)越復(fù)雜，抗攻擊的能力就越強(qiáng)。3.4數(shù)據(jù)加密標(biāo)準(zhǔn)DES

（DataEncryptionStandard）DES（DataEncryptionStandard）算法于1977年得到美國(guó)政府的正式許可，是一種用56位密鑰來(lái)加密64位數(shù)據(jù)的方法，其密文的長(zhǎng)度也為64位。國(guó)內(nèi)隨著三金工程尤其是金卡工程的啟動(dòng)，DES算法在ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費(fèi)站等領(lǐng)域被廣泛應(yīng)用，以此來(lái)實(shí)現(xiàn)關(guān)鍵數(shù)據(jù)的保密。如信用卡持卡人的PIN的加密傳輸，IC卡與POS間的雙向認(rèn)證、金融交易數(shù)據(jù)包的MAC校驗(yàn)等，均用到DES算法。DES(DataEncryptionStandard)是由IBM公司在20世紀(jì)70年代研制的，經(jīng)過(guò)政府的加密標(biāo)準(zhǔn)篩選后，于1976年11月被美國(guó)政府采用，隨后被美國(guó)國(guó)家標(biāo)準(zhǔn)局和美國(guó)國(guó)家標(biāo)準(zhǔn)協(xié)會(huì)(ANSI)所認(rèn)可。DES算法具有以下特點(diǎn)：（1）DES算法是分組加密算法：以64位為分組。（2）DES算法是對(duì)稱(chēng)算法：加密和解密用同一密鑰。（3）DES算法的有效密鑰長(zhǎng)度為56位。（4）換位和置換。（5）易于實(shí)現(xiàn)。1.DES的產(chǎn)生背景DES的生命期NBS最終采納了IBM的LUCIFER方案，于1975年公開(kāi)發(fā)表。1977年正式頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)（DES-DataEncryptionStandard）。1979年，美國(guó)銀行協(xié)會(huì)批準(zhǔn)使用DES。1980年，DES成為美國(guó)標(biāo)準(zhǔn)化協(xié)會(huì)(ANSI)標(biāo)準(zhǔn)。1984年，ISO開(kāi)始在DES基礎(chǔ)上制定數(shù)據(jù)加密的國(guó)際標(biāo)準(zhǔn)。美國(guó)國(guó)家安全局NSA每隔年對(duì)該算法進(jìn)行評(píng)估，1994年，決定1998年12月之后不再使用DES。現(xiàn)已經(jīng)確定了選用Rijndael算法作為高級(jí)加密算法AES。2.DES算法要點(diǎn)算法設(shè)計(jì)中采用的基本變換和操作：置換（P）：重新排列輸入的比特位置。交換（SW）：將輸入的左右兩部分的比特進(jìn)行互換。循環(huán)移位：將輸入中的比特進(jìn)行循環(huán)移位，作為輸出。一個(gè)復(fù)雜變換（fK

）通常是一個(gè)多階段的乘積變換；與密鑰Key相關(guān)；必須是非線(xiàn)性變換；實(shí)現(xiàn)對(duì)密碼分析的擾亂；是密碼設(shè)計(jì)安全性的關(guān)鍵。3.DES的加密過(guò)程第一步：初始置換IP。對(duì)于給定的明文m，通過(guò)初始置換IP獲得，并將分為兩部分，前面32位記為，后面32位記為，即第二步：乘積變換（

16輪）。在每一輪中依據(jù)下列方法計(jì)算（）（16輪中的計(jì)算方法相同）：，其中，為第i輪使用的子密鑰，各均為的一個(gè)置換選擇，所有構(gòu)成密鑰方案。函數(shù)中的變量為32位字符串，為48位字符串，函數(shù)輸出的結(jié)果為32位字符串。DES的加密過(guò)程第三步：初始置換的逆置換。應(yīng)用初始置換的逆置換對(duì)進(jìn)行置換，得到密文c，即。Li-1Ri-1LiRikif+一輪DES加密過(guò)程IPL0R0L1=R0R1=L0⊕f(R0,K1)R2=L1⊕f(R1,K2)L2=R1明文L15=R14R16=L15⊕f(R15,K16)R15=L14⊕f(R14,K15)L16=R15IP-1密文fK1fK2fK16DES加密流程圖LRexpandshiftshiftkeykeyS-boxescompressLR28282828282848324832323232OneRoundofDES4832KiPbox（1）IP置換表和IP-1逆置換表輸入的64位數(shù)據(jù)按IP表置換進(jìn)行重新組合，并把輸出分為L(zhǎng)0和R0兩部分，每部分各32位，其IP表置換如表3-1所示表3-1IP置換表5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315741

初始置換IP和IP-1IPIP-1將輸入的64位明文的第58位換到第1位，第50位換到第2位，依此類(lèi)推，最后一位是原來(lái)的第7位。L0和R0則是換位輸出后的兩部分，L0是輸出的左32位，R0是右32位。比如：置換前的輸入值為D1D2D3…D64，則經(jīng)過(guò)初始置換后的結(jié)果為：L0=D58D50…D8，R0=D57D49…D7。經(jīng)過(guò)16次迭代運(yùn)算后。得到L16和R16，將此作為輸入進(jìn)行逆置換，即得到密文輸出。表3-2IP-1逆置換表逆置換正好是初始置的逆運(yùn)算，例如，第1位經(jīng)過(guò)初始置換后，處于第40位，而通過(guò)逆置換IP-1，又將第40位換回到第1位，其逆置換IP-1規(guī)則表如3-2所示。40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725(2)函數(shù)f的內(nèi)部流程Ri-1（32bit）ES1S2S8PKi（48bit）48bit32bitf(Ri-1,ki)(32bit)E變換的算法是從Ri-1的32位中選取某些位，構(gòu)成48位，即E將32位擴(kuò)展為48位。變換規(guī)則根據(jù)E位選擇表，如表3-3所示。表3-3E位選擇表3212345456789891011121312131415161716171819202120212223242524252627282928293031321每個(gè)S盒輸出4位，共32位，S盒的工作原理將在第4步介紹。S盒的輸出作為P變換的輸入，P的功能是對(duì)輸入進(jìn)行置換，P換位表如表3-4所示。Ki是由密鑰產(chǎn)生的48位比特串，具體的算法是：將E的選位結(jié)果與Ki作異或操作，得到一個(gè)48位輸出。分成8組，每組6位，作為8個(gè)S盒的輸入。表3-4P換位表如表1672021291228171152326518311028241432273919133062211425（3）DES的密鑰Ki計(jì)算DES在各輪中所用的密鑰均為由初始密鑰（即種子密鑰）導(dǎo)出的48位密鑰。初始密鑰為64位，其中第8、16、24、32、40、48、56、64位均為校驗(yàn)位。如此設(shè)置校驗(yàn)位的目的是使每8個(gè)字節(jié)所含的字符“1”個(gè)數(shù)為奇數(shù)，以便能夠檢測(cè)出每個(gè)字節(jié)中的錯(cuò)誤。子密鑰ki產(chǎn)生流程圖PC-1C0D0LS1LS1C1D1LS2LS2C2D2LS16LS16C16D16PC-2PC-2PC-2K(64bit)K1(48bit)K2(48bit)K16(48bit)假設(shè)初始密鑰為K，長(zhǎng)度為64位，但是其中第8，16，24，32，40，48，64作奇偶校驗(yàn)位，實(shí)際密鑰長(zhǎng)度為56位。K下標(biāo)i的取值范圍是1到16，用16輪來(lái)構(gòu)造。構(gòu)造過(guò)程如圖所示。50子密鑰的產(chǎn)生產(chǎn)生子密鑰Ki具體描述為：首先，對(duì)于給定的密鑰K，應(yīng)用PC1變換進(jìn)行選位，選定后的結(jié)果是56位，設(shè)其前28位為C0，后28位為D0。PC1選位如表3-5所示。表3-5PC-1選位表57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124第1輪：對(duì)C0作左移LS1得到C1，對(duì)D0作左移LS1得到D1，對(duì)C1D1應(yīng)用PC2進(jìn)行選位，得到K1。其中LS1是左移的位數(shù)，如表3-6所示。第2輪：對(duì)C1和D1作左移LS2得到C2和D2，進(jìn)一步對(duì)C2D2應(yīng)用PC2進(jìn)行選位，得到K2。如此繼續(xù)，分別得到K3，K4，…，K16。表3-6LS移位表輪數(shù)循環(huán)左移位數(shù)輪數(shù)循環(huán)左移位數(shù)輪數(shù)循環(huán)左移位數(shù)輪數(shù)循環(huán)左移位數(shù)115291132216210214232721121524282122161表3-7PC-2選位表1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932（4）S盒的工作原理S盒以6位作為輸入，而以4位作為輸出，現(xiàn)在以S1為例說(shuō)明其過(guò)程。假設(shè)輸入為A=a1a2a3a4a5a6，則a2a3a4a5所代表的數(shù)是0到15之間的一個(gè)數(shù)，記為：k=a2a3a4a5；由a1a6所代表的數(shù)是0到3間的一個(gè)數(shù)，記為h=a1a6。在S1的h行，k列找到一個(gè)數(shù)B，B在0到15之間，它可以用4位二進(jìn)制表示，為B=b1b2b3b4，這就是S1的輸出。S盒由8張數(shù)據(jù)表組成，如教材P84-85所示。S-盒的構(gòu)造

DES加密范例已知明文m=computer，密鑰k=program。

m=0110001101101111011011010111000001110101011101000110010101110010

k=01110000011100100110111101100111011100100110000101101101這里k只有56bit，必須插入第8，16，24，32，40，48，56，64這8個(gè)奇偶校驗(yàn)位成為64比特。k=0111000*0011100*1001101*1110110*0111011*1001001*1000010*1101101*m經(jīng)過(guò)IP置換后得

L0=11111111101110000111011001010111

R0=00000000111111110000011010000011

密鑰k經(jīng)PC-1置換得

C0=1110110010011001000110111011

D0=1011010001011000100011100111C0和

D0各循環(huán)左移一位后通過(guò)PC-2得到48bit的子密鑰k1。

C1=1101100100110010001101110111

D1=0110100010110001000111001111k1=001111011000111111001101001101110011111101001000DES加密范例R0經(jīng)過(guò)E變換后擴(kuò)展為48bit。100000000001011111111110100000001101010000000110再和k1

作異或運(yùn)算，得101111011001100000110011101101111110101101001110分成8組

101111011001100000110011101101111110101101001110經(jīng)過(guò)S盒后輸出32bit01110110110101000010011010100001再經(jīng)過(guò)P置換得01000100001000011001111110011011DES加密范例所以第一輪迭代的結(jié)果為

=10111011100110011110100111001100DES加密范例4.DES的解密過(guò)程采用與加密相同的算法。以逆序（即）使用密鑰。實(shí)現(xiàn)效果

不同微處理器上的DES軟件實(shí)現(xiàn)速度

處理器處理器速度（MHz）每秒處理的DES分組個(gè)數(shù)80884.7370680007.69008028661,10068020163,50068030163,90080286255,000680305010,000680402516,000680404023,000804866643,000雪崩效應(yīng)明文或密鑰的微小改變將對(duì)密文產(chǎn)生很大的影響是任何算法所期望的一個(gè)好性質(zhì)。明文或密鑰的某一位發(fā)生變化會(huì)導(dǎo)致密文的很多位發(fā)生變化。如果相應(yīng)的改變很小，可能會(huì)給分析者提供縮小搜索密鑰或明文空間的渠道。DES顯示出很強(qiáng)的雪崩效應(yīng)：如下兩條僅有一位不同的明文：00000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000密鑰：00000011001011010010011000100011100001100000111000110010結(jié)果表明僅經(jīng)過(guò)3輪迭代后，兩段數(shù)據(jù)有21位不同。全部迭代完成后得到的兩段密文則有34位不同。DES的雪崩效應(yīng)(a)明文的變化(b)密鑰的變化輪數(shù)改變的位數(shù)輪數(shù)改變的位數(shù)0116221335439534632731829...0012214328432530632735834...

5.DES的安全性分析DES的安全性完全依賴(lài)于密鑰，與算法本身沒(méi)有關(guān)系。主要研究?jī)?nèi)容：密鑰的互補(bǔ)性；弱密鑰與半弱密鑰；密文-明文相關(guān)性；密文-密鑰相關(guān)性；S-盒的設(shè)計(jì)；密鑰搜索。密鑰的互補(bǔ)性DES算法具有互補(bǔ)性，即：若、是的補(bǔ)、是的補(bǔ)，則。使用DES算法時(shí)不要使用互補(bǔ)的密鑰，否則當(dāng)密碼攻擊者選擇明文攻擊時(shí)，他們僅需試驗(yàn)一半密鑰。弱密鑰弱密鑰：由密鑰k

確定的加密函數(shù)與解密函數(shù)相同，即。DES的弱密鑰：如果各輪產(chǎn)生的子密鑰一樣，則加密函數(shù)與解密函數(shù)相同。DES至少有4個(gè)弱密鑰：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe半弱密鑰半弱密鑰：對(duì)于密鑰

k

，存在一個(gè)不同的密鑰，滿(mǎn)足。DES的半弱密鑰：子密鑰生成過(guò)程中只能產(chǎn)生兩個(gè)不同的子密鑰或四個(gè)不同的子密鑰，互為對(duì)合。DES至少有12個(gè)半弱密鑰。S-盒的設(shè)計(jì)原則S-盒的設(shè)計(jì)原理沒(méi)有公開(kāi)，一些原則如下：所有S-盒的每一行是0,1,…,15的一個(gè)置換；所有S-盒的輸出都不是輸入的線(xiàn)性函數(shù)或仿射函數(shù)；S-盒的輸入改變?nèi)我庖晃欢紩?huì)引起輸出中至少兩位發(fā)生變化；對(duì)于任何輸入x（6位），S(x)與S(x⊕001100)至少有兩位不同；對(duì)于任何輸入x（6位），S(x)與S(x⊕00ef00)不相等，e,f取0或1；對(duì)于任意一個(gè)輸入位保持不變而其他五位變化時(shí)，輸出中0和1的數(shù)目幾乎相等。針對(duì)DES的攻擊方法攻擊DES的方法主要有：密鑰窮搜索攻擊，DES算法總的密鑰量為，1998年使用高級(jí)計(jì)算機(jī)的情況下，破譯DES只需56小時(shí)；差分攻擊；線(xiàn)性攻擊，較有效的方法；相關(guān)密鑰攻擊等。DES遭受攻擊的原因只是因?yàn)槠涿荑€過(guò)短，而不是因?yàn)榇嬖诒雀F舉密鑰更有效的個(gè)攻擊方法。所有DES的攻擊都要嘗試幾乎所有的密鑰70DESCrackerDESCracker:ADESkeysearchmachinecontains1536chipsCost:$250,000.couldsearch88billionkeyspersecondwonRSALaboratory’s“DESChallengeII-2”bysuccessfullyfindingaDESkeyin56hours.DESisfeelingitsage.Amoresecurecipherisneeded.DES加密練習(xí)1、假設(shè)明文和密鑰有相同的位模式，即：用十六進(jìn)制表示：0123456789ABCDEF用二進(jìn)制表示：0000000100100011010001010110011110001001101010111100110111101111a、推導(dǎo)第一輪的子密鑰K1b、推導(dǎo)L0，R0c、擴(kuò)展R0，求E[R0]d、計(jì)算A=E[R0]K1e、把（d）的48位結(jié)果分成6位（數(shù)據(jù)）的集合并求對(duì)應(yīng)S盒代換的值DES加密練習(xí)f、利用（e）的結(jié)論來(lái)求32位的結(jié)果，Bg、應(yīng)用置換求P(B)h、計(jì)算R1=P[B]L0i、寫(xiě)出密文2、為什么說(shuō)研究Feistel密碼很重要？3、分組密碼和流密碼的區(qū)別是什么？由于DES的密鑰長(zhǎng)度相對(duì)于窮舉攻擊過(guò)短，所以一般使用多重DES進(jìn)行加密，一般的是三重DES，定義為：C=E(D(E(P,K1),K2),K1)，即EDE（112bitkey）。P=D(E(D(C,K1),K2),K1)DESDES-1DESDES-1DESDES-1mck1k2k1DES的變形——3-DES3DESWhyEncrypt-Decrypt-Encryptwith2keys?Backwardcompatible:E(D(E(P,K),K),K)=E(P,K)And112bitsisenoughWhynotC=E(E(P,K),K)?Trickquestion---it’sstilljust56bitkeyWhynotC=E(E(P,K1),K2)?A(semi-practical)knownplaintextattack3DESWhynotC=E(E(P,K1),K2)?A(semi-practical)knownplaintextattackPre-computetableofE(P,K1)foreverypossiblekeyK1(resultingtablehas256entries)ThenforeachpossibleK2computeD(C,K2)untilamatchintableisfoundWhenmatchisfound,haveE(P,K1)=D(C,K2)Resultgivesuskeys:C=E(E(P,K1),K2)3.4其他分組密碼IDEA算法RC5算法Rijndael算法1.IDEA

算法IDEA國(guó)際數(shù)據(jù)加密算法（InternationalDataEncryptionAlgorithm）瑞士聯(lián)邦理工學(xué)院：XuejiaLai&JamesMassey,1990；1991改進(jìn)，加強(qiáng)了對(duì)差分密碼分析的抗擊能力；明文分組與密文分組的長(zhǎng)度均為64位，密鑰長(zhǎng)度為128位。IDEA

算法算法的設(shè)計(jì)思想混合使用來(lái)自不同代數(shù)群中的運(yùn)算；通過(guò)對(duì)于兩個(gè)16位的子模塊連續(xù)使用三個(gè)“不相容”的群運(yùn)算（分別是異或、模加、模乘），可以獲得所需的“混亂”；選擇使用的密碼結(jié)構(gòu)可以提供必要的“擴(kuò)散”。IDEA

算法描述IDEA

算法描述加密過(guò)程：長(zhǎng)度為64位的分組被分為4個(gè)長(zhǎng)度為16位的子分組。這些子分組作為算法第1輪的輸入（注：該算法共8輪）。在每一輪中，子分組相互間進(jìn)行異或、模加、模乘運(yùn)算，并且與6個(gè)長(zhǎng)度為16位的子密鑰進(jìn)行異或、模加、模乘運(yùn)算。在各輪之間，第2個(gè)子分組和第3個(gè)子分組進(jìn)行交換。最后，在輸出變換中，子分組與子密鑰進(jìn)行運(yùn)算，將運(yùn)算所得的4個(gè)子分組重新連接便得到密文。IDEA

算法描述子密鑰的產(chǎn)生過(guò)程：將長(zhǎng)度為128位的密鑰分為8個(gè)長(zhǎng)度為16位的子密鑰，作為算法第1輪需要的6個(gè)子密鑰和第2輪中的前兩個(gè)子密鑰；將原來(lái)長(zhǎng)度為128位的密鑰向左環(huán)移25位，再次分為8個(gè)長(zhǎng)度為16位的子密鑰，作為算法第2輪需要的另外4個(gè)子密鑰和第3輪所需的6個(gè)子密鑰；依次類(lèi)推，便得到全部所需的52個(gè)密鑰。解密過(guò)程與加密過(guò)程基本相同。但是需要對(duì)子密鑰進(jìn)行求逆運(yùn)算。

2.RC5算法RSA公司的Rivest所設(shè)計(jì)的一種參數(shù)（分組大小、密鑰長(zhǎng)度、加密輪數(shù)）可變的分組密碼算法。一個(gè)RC5算法通常被記為：RC5-w/r/b。其中，“w”為分組大小（w=16,32,64），“r”為加密輪數(shù)（），“b”為密鑰長(zhǎng)度（）。該算法實(shí)際上包含三部分：密鑰擴(kuò)展算法、加密算法、解密算法。3.Rijndael算法不屬于Feistel結(jié)構(gòu)，Adi

Shamir相信“永遠(yuǎn)安全的”。已被美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所選定作為高級(jí)加密算法AES。迭代分組密碼算法。密鑰128/192/256，分組128/192/256，循環(huán)次數(shù)10/12/14。速度快、對(duì)內(nèi)存要求小，操作簡(jiǎn)單。算法的抗攻擊能力強(qiáng)。3.5

分組密碼的工作模式為了將DES應(yīng)用于實(shí)際，已經(jīng)提出的分組密碼工作模式有：密碼分組鏈接（CBC）模式；密碼反饋（CFB）模式；輸出反饋（OFB）模式；級(jí)連（CM）模式（又稱(chēng)多重加密模式）；計(jì)數(shù)器模式；擴(kuò)散密碼分組鏈連（PCBC）模式。模式描述典型應(yīng)用電碼本（ECB）用相同的密鑰分別對(duì)明文組加密單個(gè)數(shù)據(jù)的安全傳輸（如下一個(gè)加密密鑰）密碼分組鏈接（CBC）加密算法的輸入是上一個(gè)密文組和下一個(gè)明文組的異或普通目的面向分組的傳輸認(rèn)證密碼反饋（CFB）一次處理J位。上一個(gè)分組密文作為產(chǎn)生一個(gè)偽隨機(jī)數(shù)輸出的加密算法的輸入，該輸出與明文異或，作為下一個(gè)分組的輸入普通目的的向分組的傳輸認(rèn)證輸出反饋（OFB）與CFB基本相同，只是加密算法的輸入是上一次DES的輸出噪聲通道上的數(shù)據(jù)流的傳輸（如衛(wèi)星通信）計(jì)數(shù)器（CTR）每個(gè)明文組是加密的計(jì)數(shù)器的異或。對(duì)每個(gè)后續(xù)的組，計(jì)算器是累加的普通目的面向分組的傳輸用于高速需求3.5

分組密碼的工作模式

86電碼本（ECB）Ci=EK(Pi)

Pi=DK(Ci)ECB特點(diǎn)簡(jiǎn)單和有效可以并行實(shí)現(xiàn)不能隱藏明文的模式信息相同明文相同密文同樣信息多次出現(xiàn)造成泄漏對(duì)明文的主動(dòng)攻擊是可能的信息塊可被替換、重排、刪除、重放誤差傳遞：密文塊損壞僅對(duì)應(yīng)明文塊損壞適合于傳輸短信息AliceHatesECBModeAlice’suncompressedimage,andECBencrypted(TEA)Whydoesthishappen?Sameplaintextyieldssameciphertext!密碼分組鏈接（CBC）模式密文分組被反饋到輸入端，明文分組與的異或結(jié)果被作為DES加密算法的輸入，從而得到下一個(gè)密文分組，即。解密過(guò)程為。密文分組為無(wú)須保密的事先設(shè)定的初值，不同的明文x（而非明文分組）對(duì)應(yīng)不同的。各密文分組不僅與與之對(duì)應(yīng)的明文分組有關(guān)，也和此前的所有明文分組（即）有關(guān)。Ci=EK(Ci-1Pi)

Pi=EK(Ci

)Ci-1密碼分組鏈接（CBC）模式密碼分組鏈接（CBC）模式優(yōu)點(diǎn):能夠隱蔽明文的數(shù)據(jù)模式，相同的明文不一定產(chǎn)生相同的密文；能夠在一定程度上防止分組的重放、插入和刪除等攻擊。缺點(diǎn)：易導(dǎo)致錯(cuò)誤傳播。由于任何一個(gè)明文或密文分組出錯(cuò)都會(huì)導(dǎo)致其后的密文分組出錯(cuò)AliceLikesCBCModeAlice’suncompressedimage,AliceCBCencrypted(TEA)Whydoesthishappen?Sameplaintextyieldsdifferentciphertext!密碼反饋（CFB）模式實(shí)質(zhì)上是一種自同步流密碼。適用于必須按比特或者字符對(duì)明文進(jìn)行加密的情況。采用該模式實(shí)現(xiàn)DES算法時(shí)，反饋的密文分組的長(zhǎng)度與此前的密文分組長(zhǎng)度不同，而是通常為事先設(shè)定的n值（），與明文相加的只是密文分組的最左邊n位，反饋的密文分組同時(shí)反饋到密鑰產(chǎn)生器。密碼反饋（CFB）模式基本原理如圖：輸出反饋（OFB）模式優(yōu)點(diǎn)：能夠克服錯(cuò)誤傳播。缺點(diǎn)：很難發(fā)現(xiàn)密文被篡改；不具備自同步能力。

輸出反饋（OFB）模式基本原理如圖

:級(jí)連（CM）模式基本原理如圖：主要是為了增加密鑰