第二講 對稱密鑰密碼體系

第二講對稱密鑰密碼體系1本章導讀密碼編碼是對付各種安全威脅的最強有力的工具，加密技術(shù)是信息安全的核心技術(shù)。本章介紹密碼體系的原理和一些基本概念，介紹對稱密鑰加密的幾種常用算法：數(shù)據(jù)加密標準(DES)、3DES、IDEA、序列密碼A5以及AES。

2內(nèi)容2.1密碼體系的原理和基本概念2.2數(shù)據(jù)加密標準(DES)2.3高級加密標準（AES）2.4序列密碼2.5其它對稱密碼算法小結(jié)32.1密碼體系的原理和基本概念

專業(yè)術(shù)語消息和加密：消息被稱為明文。用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密，加了密的消息稱為密文，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密。4加密解密公式

明文用M（消息）或P（明文）表示，密文用C表示。加密函數(shù)E作用于M得到密文C，用數(shù)學式子表示為：E（M）=C相反地，解密函數(shù)D作用于C產(chǎn)生MD（C）=M先加密后再解密消息，原始的明文將恢復出來，下面的等式必須成立：D（E（M））=M52.1密碼體系的原理和基本概念

專業(yè)術(shù)語鑒別：消息的接收者應該能夠確認消息的來源；入侵者不可能偽裝成他人完整性：消息的接收者應該能夠驗證在傳送過程中消息沒有被修改；入侵者不可能用假消息代替合法消息抗抵賴：發(fā)送者事后不可能虛假地否認他發(fā)送的消息算法：密碼算法是用于加密和解密的數(shù)學函數(shù)。一般情況下，有兩個相關(guān)的函數(shù)：一個用作加密，另一個用作解密62.1密碼體系的原理和基本概念

安全密碼

如果密碼的保密性是基于保持算法的秘密，這種密碼算法稱為受限制的算法。密鑰用K表示.K可以是很多數(shù)值里的任意值。密鑰K的可能值的范圍叫做密鑰空間。加密和解密運算都使用這個密鑰（即運算都依賴于密鑰，并用K作為下標表示），這樣，加/解密函數(shù)現(xiàn)在變成：EK（M）=CDK（C）=M72.1密碼體系的原理和基本概念

安全密碼82.1密碼體系的原理和基本概念

安全密碼算法安全性所有這些算法的安全性都基于密鑰的安全性，而不是基于算法的細節(jié)的安全性只有公開的算法才是安全的9對稱算法有時又叫傳統(tǒng)密碼算法，就是加密密鑰能夠從解密密鑰中推算出來，反過來也成立在大多數(shù)對稱算法中，加/解密密鑰是相同的對稱算法可分為兩類分組算法（分組密碼）序列算法（序列密碼,流密碼）2.1密碼體系的原理和基本概念

對稱密碼和非對稱密碼

10112.1密碼體系的原理和基本概念

對稱密碼和非對稱密碼非對稱算法用作加密的密鑰不同于用作解密的密鑰，而且解密密鑰不能根據(jù)加密密鑰計算出來（至少在合理假定的有限時間內(nèi)）

非對稱算法也叫做公開密鑰算法，是因為加密密鑰能夠公開，即陌生者能用加密密鑰加密信息，但只有用相應的解密密鑰才能解密信息12132.1密碼體系的原理和基本概念

密碼分析密碼分析學是在不知道密鑰的情況下恢復出明文的科學對密碼進行分析的嘗試稱為密碼分析攻擊唯密文攻擊已知明文攻擊選擇明文攻擊自適應選擇明文攻擊142.1密碼體系的原理和基本概念

密碼分析學者LarsKnudsen把破譯算法分為不同的類別全部破譯：密碼分析者找出了密鑰全盤推導：密碼分析者找到一個代替算法，在不知道密鑰的情況下，可用它得到明文實例推導：密碼分析者從截獲的密文中找出明文信息推導：密碼分析者獲得一些有關(guān)密鑰或明文的信息這些信息可能是密鑰的幾個比特、有關(guān)明文格式的信息等等152.1密碼體系的原理和基本概念

密碼分析幾乎所有密碼系統(tǒng)在唯密文攻擊中都是可破的，只要簡單地一個接一個地去試每種可能的密鑰，并且檢查所得明文是否有意義。這種方法叫做蠻力攻擊。不同方式衡量攻擊方法的復雜性：數(shù)據(jù)復雜性：用作攻擊輸入所需要的數(shù)據(jù)量時間復雜性：完成攻擊所需要的時間存儲復雜性：進行攻擊所需要的存儲量16內(nèi)容2.1密碼體系的原理和基本概念2.2數(shù)據(jù)加密標準(DES)2.3高級加密標準（AES）2.4序列密碼2.5其它對稱密碼算法小結(jié)

172.2數(shù)據(jù)加密標準(DES)

分組密碼數(shù)據(jù)加密標準DES屬于分組密碼分組密碼將明文消息劃分成固定長度的分組，各分組分別在密鑰的控制下變換成等長度的密文分組182.2數(shù)據(jù)加密標準(DES)

分組密碼分組密碼的工作原理19DES的歷史1973年5月15日,NBS開始公開征集標準加密算法,并公布了它的設計要求:

(1)算法必須提供高度的安全性(2)算法必須有詳細的說明,并易于理解(3)算法的安全性取決于密鑰,不依賴于算法(4)算法適用于所有用戶(5)算法適用于不同應用場合(6)算法必須高效、經(jīng)濟(7)算法必須能被證實有效(8)算法必須是可出口的202.2數(shù)據(jù)加密標準(DES)對稱密碼算法有兩種類型：分組密碼(BlockCipher)和流密碼(StreamCipher)。分組密碼一次處理一塊輸入，每個輸入塊生成一個輸出塊，而流密碼對輸入元素進行連續(xù)處理，同時產(chǎn)生連續(xù)單個輸出元素。數(shù)據(jù)加密標準DES屬于分組密碼。分組密碼將明文消息劃分成固定長度的分組，各分組分別在密鑰的控制下變換成等長度的密文分組。分組密碼的工作原理如圖2-2所示。21圖2-2分組密碼的工作原理22DES的歷史數(shù)據(jù)加密標準成為世界范圍內(nèi)的標準已經(jīng)20多年了。1973年，美國國家標準局(NBS)在認識到建立數(shù)據(jù)保護標準既明顯又急迫需要的情況下，開始征集聯(lián)邦數(shù)據(jù)加密標準的方案。1975年3月17日，NBS公布了IBM公司提供的密碼算法，以標準建議的形式在全國范圍內(nèi)征求意見。經(jīng)過兩年多的公開討論之后，1977年7月15日，NBS宣布接受這個建議，作為聯(lián)邦信息處理標準46號[2]，數(shù)據(jù)加密標準(DataEncryptionStandard)，即DES正式頒布，供商業(yè)界和非國防性政府部門使用。23DES算法的描述

DES加密算法如圖所示，由以下四個部分組成。

1.初始置換函數(shù)IPDES對64位明文分組進行操作。首先，64位明文分組x經(jīng)過一個初始置換函數(shù)IP，產(chǎn)生64位的輸出x0，再將分組x0分成左半部分L0和右半部分R0，即：

x0=IP(x)=L0R0

置換表如表2-1所示。此表順序為從上到下，從左至右。如初始置換把明文的第58位換至第1位，把第50位換至第二位，以此類推。24DES的歷史1974年8月27日,美國國家標準局(NBS)開始第二次征集,IBM提交了算法LUCIFER，該算法由IBM的工程師在1971~1972年研制。1975年3月17日,NBS公開了全部細節(jié)。1976年，NBS指派了兩個小組進行評價。1976年11月23日，采納為聯(lián)邦標準，批準用于非軍事場合的各種政府機構(gòu)。1977年1月15日,“數(shù)據(jù)加密標準”FIPSPUB46發(fā)布,同年7月15日開始生效。該標準規(guī)定每五年審查一次，計劃十年后采用新標準。最近的一次評估是在1994年1月，已決定1998年12月以后，DES將不再作為聯(lián)邦加密標準。252.2數(shù)據(jù)加密標準(DES)

DES的應用1979年，美國銀行協(xié)會批準使用1980年，美國國家標準局（ANSI）贊同DES作為私人使用的標準,稱之為DEA（ANSIX.392）1983年，國際化標準組織ISO贊同DES作為國際標準，稱之為DEA-1262.2數(shù)據(jù)加密標準(DES)

DES的算法DES加密算法由以下四個部分組成：初始置換函數(shù)IP獲取子密鑰Ki密碼函數(shù)F末置換函數(shù)IP-127282.2數(shù)據(jù)加密標準(DES)

DES的算法-初始置換函數(shù)IP

DES對64位明文分組進行操作。首先，64位明文分組x經(jīng)過一個初始置換函數(shù)IP，產(chǎn)生64位的輸出x0，再將分組x0分成左半部分L0和右半部分R0，即：

x0=IP(x)=L0R0

292.2數(shù)據(jù)加密標準(DES)

DES的算法-初始置換函數(shù)IPM20

→M'14IP302.2數(shù)據(jù)加密標準(DES)

DES的算法-獲取子密鑰KiDES加密算法的密鑰長度為56位，但一般表示為64位，其中，每個第8位用于奇偶校驗。在DES加密算法中，將用戶提供的64位初始密鑰經(jīng)過一系列的處理得到K1，K2，…，K16，分別作為1～16輪運算的16個子密鑰31322.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F函數(shù)F的操作步驟

密碼函數(shù)F的輸入是32比特數(shù)據(jù)和48比特的子密鑰332.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F擴展置換(E)。將數(shù)據(jù)的右半部分Ri從32位擴展為48位。位選擇函數(shù)(也稱E盒)342.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F異或。擴展后的48位輸出E(Ri)與壓縮后的48位密鑰Ki作異或運算S盒替代。將異或得到的48位結(jié)果分成八個6位的塊，每一塊通過對應的一個S盒產(chǎn)生一個4位的輸出352.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)FS盒的具體置換過程為：某個Si盒的6位輸入的第1位和第6位形成一個2位的二進制數(shù)(從0～3)，對應表中的某一行；同時，輸入的中間4位構(gòu)成4位二進制數(shù)(從0～15)對應表中的某一列(注意：行和列均從0開始計數(shù))例如，第6個S盒的輸入為110011，前后2位形成的二進制數(shù)為11，對應第8個S盒的第3行；中間4位為1001，對應同一S盒的第9列

3637S－盒置換輸入6比特:b1b2b3b4b5b6輸出4比特：S(b1b6,b2b3b4b5)S1b1b2b3b4b5b60123456789101112131415S101441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S2015181461134972131205101..........23舉例：S1(100110)=1000382.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F-P盒置換將八個S盒的輸出連在一起生成一個32位的輸出，輸出結(jié)果再通過置換P產(chǎn)生一個32位的輸出即：F(Ri,Ki)。至此，密碼函數(shù)F的操作就完成了最后，將P盒置換的結(jié)果與最初的64位分組的左半部分異或，然后左、右半部分交換，接著開始下一輪計算。39P-盒置換32比特輸入，32比特輸出123456789303132167202129122817115......11425P-盒的輸出：40P盒置換

1672021291228171152326518311028241432273919133062211425412.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F-函數(shù)F的設計函數(shù)F是DES加密的核心，它依賴于S盒的設計。這也適用于其它的對稱分組加密算法F的設計準則

函數(shù)F的基本功能就是“擾亂(confusion)”輸入，因此，對于F來說，其非線性越高越好，也就是說，要恢復F所做的“擾亂”操作越難越好422.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F-函數(shù)F的設計雪崩準則(SAC)

就是要求算法具有良好的雪崩效應，輸入當中的一個比特發(fā)生變化都應當使輸出產(chǎn)生盡可能多的比特變化。嚴格地說，就是當任何單個輸入比特位i發(fā)生變換時，一個S盒的第j比特輸出位發(fā)生變換的概率應為1/2，且對任意的i,j都應成立比特獨立準則(BIC)

BIC的意思是當單個輸入比特位i發(fā)生變化時，輸出比特位j,k的變化應當互相獨立，且對任意的i,j,k均應成立432.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F-函數(shù)F的設計S盒設計本質(zhì)上S盒的作用就是對輸入向量進行處理，使得輸出看起來更具隨機性，輸入和輸出之間應當是非線性的，很難用線性函數(shù)來逼近S盒的尺寸是一個很重要的特性。一個S盒其輸入為n比特，輸出為m比特。DES的S盒大小為6×4。S盒越大，就越容易抵制差分和線性密碼分析442.2數(shù)據(jù)加密標準(DES)

DES的算法-密碼函數(shù)F-函數(shù)F的設計Nyberg提出了以下幾種S盒的設計和實踐原則：

隨機性：采用某些偽隨機數(shù)發(fā)生器或隨機數(shù)表格來產(chǎn)生S盒的各個項

隨機測試：隨機選擇S盒各個項，然后按照不同準則測試其結(jié)果

數(shù)學構(gòu)造：根據(jù)某些數(shù)學原理來產(chǎn)生S盒。其好處就是可以根據(jù)數(shù)學上的嚴格證明來抵御差分和線性密碼分析，并且可以獲得很好的擴散(Diffusion)特性452.2數(shù)據(jù)加密標準(DES)

DES的算法-末置換函數(shù)IP-1末置換是初始置換的逆變換.經(jīng)過一個末置換函數(shù)就可得到64位的密文c，即：

c=IP-1(R16L16)46IPIP-1472.2數(shù)據(jù)加密標準(DES)

DES的算法-總結(jié)子密鑰生成：

C[0]D[0]=PC–1(K)for1<=i<=16{C[i]=LS[i](C[i?1])D[i]=LS[i](D[i?1])K[i]=PC–2(C[i]D[i])}482.2數(shù)據(jù)加密標準(DES)

DES的算法-總結(jié)加密過程：

L[0]R[0]=IP(x)for1<=i<=16{L[i]=R[i?1]R[i]=L[i?1]XORf?(R[i?1],K[i])}c=IP?1(R[16]L[16])492.2數(shù)據(jù)加密標準(DES)

DES的算法-總結(jié)解密過程：

R[16]L[16]=IP(c)for1<=i<=16{R[i?1]=L[i]L[i?1]=R[i]XORf?(L[i],K[i])}x=IP?1(L[0]R[0])502.2數(shù)據(jù)加密標準(DES)

DES的工作模式電子編碼本ECB密碼分組鏈接CBC密碼反饋CFB輸出反饋OFB51ECB52CBC53OFBCFB54OFB55對DES的攻擊典型的DES處理時間（8字節(jié)字組）56對DES的攻擊目前，最快可用的DES元件需要64ns的時間來完成一個字組的加密。如果有10000個計算模塊并行匯集在一起，每個能獨立試驗密鑰空間的一小部分，又假定平均要搜索一半的密鑰空間以找到正確的密鑰，我們可以算得處理時間如下：572.2數(shù)據(jù)加密標準(DES)

DES的算法-三重DES三重DES是DES的一種變形的實現(xiàn)方式

加/解密運算為：

加密：c=EK3(DK2(EK1(m)))

解密：m=DK1(EK2(DK3(c)))

其中，K1、K2、K3為56位DES密鑰。為了獲得更高的安全性，三個密鑰應該選擇為互不相同。但在某些情況下，如與原來的DES保持兼容，則可以選擇K1=K2或K2=K3582.2數(shù)據(jù)加密標準(DES)

DES的算法-三重DES59內(nèi)容2.1密碼體系的原理和基本概念2.2數(shù)據(jù)加密標準(DES)2.3高級加密標準（AES）2.4序列密碼2.5其它對稱密碼算法小結(jié)60AES背景-i1997年4月15日，（美國）國家標準技術(shù)研究所（NIST）發(fā)起征集高級加密標準（AdvancedEncryptionStandard）AES的活動，活動目的是確定一個非保密的、可以公開技術(shù)細節(jié)的、全球免費使用的分組密碼算法，作為新的數(shù)據(jù)加密標準。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。作為進入AES候選過程的一個條件，開發(fā)者承諾放棄被選中算法的知識產(chǎn)權(quán)。對AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度128/192/256比特。61AES背景-ii1998年8月12日，在首屆AES會議上指定了15個候選算法。1999年3月22日第二次AES會議上，將候選名單減少為5個，這5個算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES會議上，對這5個候選算法的各種分析結(jié)果進行了討論。2000年10月2日，NIST宣布了獲勝者—Rijndael算法，2001年11月出版了最終標準FIPSPUB197。622.3高級加密標準（AES）

Rijndael算法Rijndael算法是比利時的JoanDaemen和VincentRijmen設計的一個算法，該算法的原形是Square算法。它的設計策略是寬軌跡策略。寬軌跡策略是針對差分分析和線性分析提出的一種新的策略，其最大優(yōu)點是可以給出算法的最佳差分特性的概率及最佳線性逼近的偏差的界。由上述條件可以分析算法抵抗差分密碼分析和線性密碼分析的能力。63內(nèi)容2.1密碼體系的原理和基本概念2.2數(shù)據(jù)加密標準(DES)2.3高級加密標準（AES）2.4序列密碼2.5其它對稱密碼算法小結(jié)642.4序列密碼

一次一密亂碼本

序列密碼又稱流密碼，它將明文劃分成字符(如單個字母)或其編碼的基本單元(如0、1)，然后將其與密鑰流作用以加密，解密時以同步產(chǎn)生的相同密鑰流實現(xiàn)。652.4序列密碼

一次一密亂碼本序列密碼強度完全依賴于密鑰流產(chǎn)生器所產(chǎn)生的序列的隨機性和不可預測性，其核心問題是密鑰流生成器的設計。而保持收發(fā)兩端密鑰流的精確同步是實現(xiàn)可靠解密的關(guān)鍵技術(shù)迄今為止，只有一種理論上不可破的加密方案，叫做一次一密亂碼本，這是一種序列密碼。其基本思想是讓密鑰和明文一樣長，密鑰稱為