密碼學-信息安全概論課件

密碼學基礎2計算機學院信息安全課題組 信息安全概論 信息安全概論1

回顧上次課的內容對稱密碼的兩個基本運算代替和置換(Substitution&permutation)對稱密碼分析的兩個基本方法系統(tǒng)分析法（統(tǒng)計分析法）窮舉法對稱密碼的兩個基本設計原則:混亂和擴散密碼分析攻擊的方式

回顧上次課的內容對稱密碼的兩個基本運算2討論議題分組密碼的操作模式實用中數據格式的多樣性安全的工作模式分組密碼的分析方法現(xiàn)代常規(guī)分組加密算法TripleDESRC5、RC6AES……加密的位置：鏈路方式和端到端的方式討論議題分組密碼的操作模式3分組密碼的操作模式電子密碼本ECB(electroniccodebookmode)密碼分組鏈接CBC(cipherblockchaining)密碼反饋CFB(cipherfeedback)輸出反饋OFB(outputfeedback)美國NSB在[FIPSPUB74和81]中規(guī)定ANSI在[ANSIX3.106]中規(guī)定ISO和ISO/IEC在[ISO9732ISO/IEC10116]中規(guī)定分組密碼的操作模式電子密碼本ECB(electronic4電子密碼本（ECB）Ci=EK(Pi)Pi=DK(Ci)電子密碼本（ECB）Ci=EK(Pi)Pi=D5ECB特點簡單和有效可以并行實現(xiàn)不能隱藏明文的模式信息相同明文相同密文同樣信息多次出現(xiàn)造成泄漏對明文的主動攻擊是可能的信息塊可被替換、重排、刪除、重放誤差傳遞：密文塊損壞僅對應明文塊損壞適合于傳輸短信息ECB特點簡單和有效6密碼分組鏈接CBCCi=EK(Ci-1Pi)Pi=EK(Ci)Ci-1密碼分組鏈接CBCCi=EK(Ci-1Pi)Pi=E7CBC特點沒有已知的并行實現(xiàn)算法能隱藏明文的模式信息需要共同的初始化向量IV相同明文不同密文初始化向量IV可以用來改變第一塊對明文的主動攻擊是不容易的信息塊不容易被替換、重排、刪除、重放誤差傳遞：密文塊損壞兩明文塊損壞安全性好于ECB適合于傳輸長度大于64位的報文，還可以進行用戶鑒別,是大多系統(tǒng)的標準如SSL、IPSecCBC特點沒有已知的并行實現(xiàn)算法8密碼反饋CFBCFB:分組密碼流密碼Si為移位寄存器,j為流單元寬度

加密:Ci=Pi(EK(Si)的高j位)Si+1=(Si<<j)|Ci解密:Pi=Ci(EK(Si)的高j位)Si+1=(Si<<j)|Ci

密碼反饋CFBCFB:分組密碼流密碼9

CFB加密示意圖Ci=Pi(EK(Si)的高j位);Si+1=(Si<<j)|Ci

CFB加密示意圖Ci=Pi(EK(Si)的高j位);10

CFB解密示意圖Pi=Ci(EK(Si)的高j位);Si+1=(Si<<j)|Ci

CFB解密示意圖Pi=Ci(EK(Si)的高j位);11CFB特點分組密碼流密碼沒有已知的并行實現(xiàn)算法隱藏了明文模式需要共同的移位寄存器初始值IV對于不同的消息，IV必須唯一誤差傳遞：一個單元損壞影響多個單元

CFB特點分組密碼流密碼12輸出反饋OFBOFB:分組密碼流密碼Si為移位寄存器,j為流單元寬度

加密:Ci=Pi(EK(Si)的高j位)Si+1=(Si<<j)|(EK(Si)的高j位)解密:Pi=Ci(EK(Si)的高j位)Si+1=(Si<<j)|(EK(Si)的高j位)輸出反饋OFBOFB:分組密碼流密碼13

OFB加密示意圖Ci=Pi(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位)OFB加密示意圖Ci=Pi(EK(Si)的高j位);14

OFB解密示意圖Pi=Ci(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位)OFB解密示意圖Pi=Ci(EK(Si)的高j位);S15OFB特點OFB:分組密碼流密碼沒有已知的并行實現(xiàn)算法隱藏了明文模式需要共同的移位寄存器初始值IV誤差傳遞：一個單元損壞只影響對應單元對明文的主動攻擊是可能的信息塊可被替換、重排、刪除、重放安全性較CFB差OFB特點OFB:分組密碼流密碼16運行模式總結種類有無反饋有無并行算法P=>C影響C=>P影響結構相關性主動攻擊有無IV安全性ECBCBCCFBOFB運行模式總結種類有無有無并行算法P=>C影響C=>P影響結構17分組密碼的分析方法根據攻擊者所掌握的信息,可將分組密碼的攻擊分為以下幾類:唯密文攻擊已知明文攻擊選擇明文攻擊攻擊的復雜度數據復雜度:實施該攻擊所需輸入的數據量處理復雜度:處理這些數據所需要的計算量分組密碼的分析方法根據攻擊者所掌握的信息,可將分組密碼的攻擊18分組密碼的典型攻擊方法最可靠的攻擊辦法:強力攻擊最有效的攻擊:差分密碼分析,通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特.線性密碼分析:本質上是一種已知明文攻擊方法,通過尋找一個給定密碼算法的有效的線性近似表達式來破譯密碼系統(tǒng)插值攻擊方法密鑰相關攻擊分組密碼的典型攻擊方法最可靠的攻擊辦法:強力攻擊19現(xiàn)代常規(guī)分組加密算法一種是對DES進行復合，強化它的抗攻擊能力；另一種是開辟新的方法，即象DES那樣加解密速度快，又具有抗差分攻擊和其他方式攻擊的能力?，F(xiàn)代常規(guī)分組加密算法一種是對DES進20現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES其他一些較實用的算法，如Blowfish，CAST，以及RC2。現(xiàn)代常規(guī)分組加密算法1.TripleDES211.TRIPLEDES由于已經證明DES不能成為群，見K.W.CampbellandM.J.WienerProofthatDESisnotagroupInAdvancesinCryptology——Crpto’92.Springer-Verlag,NewYork,1993.于是多重DES，尤其是三重DES還在普遍使用。1.TRIPLEDES由于已經證明DES不能成為群，22雙重DES(DoubleDES)

C=EK2(EK1(P))P=DK1(DK2(C))

雙重DES(DoubleDES)

C=EK2(EK23雙重DES的討論假設對于DES和所有56比特密鑰，給定任意兩個密鑰K1和K2，都能找到一個密鑰K3使得EK2(EK1(P))=EK3(P)。如果這個假設是事實，則DES的兩重加密或者多重加密都將等價于用一個56比特密鑰的一次加密。

從直觀上看，上面的假設不可能為真。因為DES的加密事實上就是做一個從64比特分組到一個64分組的置換，而64比特分組共有264可能的狀態(tài)，因而可能的置換個數為另一方面，DES的每個密鑰確定了一個置換，因而總的置換個數為。直到1992年才有人證明了這個結果。雙重DES的討論假設對于DES和所有56比特密鑰，給定任意24中間相遇(meet-in-the-middle)攻擊

C=EK2(EK1(P))X=EK1(P)=DK2(C)給定明文密文對(P,C)對所有256個密鑰,加密P,對結果排序對所有256個密鑰,解密C,對結果排序逐個比較,找出K1,K2使得EK1(P)=DK2(C)中間相遇(meet-in-the-middle)攻擊

C=25對雙重DES的中間相遇攻擊的分析已知，給定一個明文P，經二重DES加密有264個可能的密文。而二重DES所用密鑰的長度應是112bits，所以選擇密鑰有2112個可能性。于是對給定一個明文P加密成一定的密文方式有2112/264=248種可能。給定兩個明密文對,虛警率降為248-64=2-16。換句話說，對已知2個明文-密文對的中間相遇攻擊成功的概率為1-2-16。攻擊用的代價{加密或解密所用運算次數}≦2256需要大量的存儲器:256

64=1017字節(jié)=230*232對雙重DES的中間相遇攻擊的分析已知，給定一個明文P，經二重26Triple-DES的四種模型DES-EEE3：三個不同密鑰，順序使用三次加密算法DES-EDE3：三個不同密鑰，依次使用加密-解密-加密算法DES-EEE2：K1=K3，同上DES-EDE2：K1=K3，同上Triple-DES的四種模型DES-EEE3：三個不同密鑰27雙密鑰的三重DES

（TripleDESwithTwoKeys)C=EK1(DK2(EK1(P)))P=DK1(EK2(DK1(C)))雙密鑰的三重DES

（TripleDESwithTwo28對雙密鑰的三重DES的分析-i該模式由IBM設計,可與常規(guī)加密算法兼容這種替代DES的加密較為流行并且已被采納用于密鑰管理標準（TheKeyManagerStandardsANSX9.17和ISO8732).交替使用K1和K2可以抵抗中間相遇攻擊.如果C=EK2(EK1(EK1(P))),只需要256+2次加密到目前為止，還沒有人給出攻擊三重DES的有效方法。對其密鑰空間中密鑰進行蠻干搜索，那么由于空間太大為2112=5×1033，這實際上是不可行的。若用差分攻擊的方法，相對于單一DES來說復雜性以指數形式增長，要超過1052。對雙密鑰的三重DES的分析-i該模式由IBM設計,可與常規(guī)29對雙密鑰的三重DES的分析-ii目前還沒有針對兩個密鑰三重DES的實用攻擊方法。但對兩個密鑰三重DES的攻擊有一些設想，以這些設想為基礎將來可能設計出更成功的攻擊技術。

MerkleR.andHellman,M.“Onthesecurityofmultipleencryption”.CommunicationoftheACM,July1981Oorschot,PandWiener,M.“AKnown-plaintextattackontwo-keytripleencryption”Proceedings,EUROCrypt’90,1990:publishedbySpringer-Verlag對雙密鑰的三重DES的分析-ii目前還沒有針對兩個密鑰三重D30三密鑰的三重DES

（TripleDESwithThreeKeys)C=EK3(DK2(EK1(P)))P=DK3(EK2(DK1(C)))三密鑰的三重DES

（TripleDESwithThr31三密鑰的三重DES分析密鑰的有效長度為168位與DES的兼容性可以通過令K3=K2或K1=K2得到許多基于Internet的應用里用到：PGP和S/MIME三密鑰的三重DES分析密鑰的有效長度為168位32現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES33國際數據加密IDEA（InternationalDataEncryptionAlgorithm)算法1990年瑞士聯(lián)邦技術學院的來學嘉和Massey提出，PES，91年修訂，92公布細節(jié)設計目標從兩個方面考慮加密強度易實現(xiàn)性強化了抗差分分析的能力，PGP國際數據加密IDEA（InternationalData34IDEA算法特點64位分組,128位密鑰運算:XOR,模216（65536）加,模(216+1)（65537）乘三種運算均不滿足分配律與結合律有大量弱密鑰難以直接擴展到128位塊IDEA算法特點64位分組,128位密鑰35IDEA設計思想得到confusion的途徑按位異或以216(65536)為模的加法以216+1

(65537)為模的乘法互不滿足分配律、結合律得到diffusion的途徑乘加(MA)結構實現(xiàn)上的考慮軟件和硬件實現(xiàn)上的考慮IDEA設計思想得到confusion的途徑36IDEA加密算法IDEA加密算法37IDEA

每一輪

IDEA

每一輪38IDEA輸出變換階段IDEA輸出變換階段39IDEA的子密鑰IDEA的子密鑰40

現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES41RC5作者為RonRivest1994設計、1995公開1.適用于軟件或者硬件實現(xiàn)2.運算速度快3.能適應于不同字長的程序（一個字的bit數是RC5的一個參數；）加密的輪數可變（輪數是RC5的第二個參數）密鑰長度是可變的（密鑰長度是RC5的第三個參數）6.對內存要求低7.依賴于數據的循環(huán)移位（增強抗攻擊能力）RC5作者為RonRivest1994設計、1995公42RC5參數三個參數參數w：表示字長，RC5加密兩字長分組，可用值為16、32、64參數r：表示輪數，可用值0,1,…,255參數b：表示密鑰K的字節(jié)數，可用值0,1,…,255RC5版本：RC5-w/r/b算法作者建議標定版本為RC5-32/12/16RC5參數三個參數43RC5基本運算整個加密使用了下述3個基本運算和它們的逆運算：模2w加法運算，表示為“+”；逐比特異或運算，表示為“⊕”；字的循環(huán)左移運算：字x循環(huán)左移y比特，表示為

x<<<y

實際只有y的log2w個低位比特來確定x的循環(huán)數它的逆為循環(huán)右移y比特，表示為

x>>>y如（a0,a1,a2,…,an-1)<<<3=(a3,a4,…,an-1,a0,a1,a2)RC5基本運算整個加密使用了下述3個基本運算和它們的逆運算：44密鑰擴展總計產生t=2r+2

個子密鑰，每個密鑰的長度為一個字長（wbits)。密鑰擴展總計產生t=2r+2個子密鑰，每個密鑰的長度為45密鑰的初始化對于給定的參數r和w，開始初始化運算

Pw=Odd((e-2)2w)Qw=Odd((Φ-1)2w)這里e=2.718281828459…(自然對數的底）Φ=1.618033988749…（黃金分割比率）并且Odd[x]表示最接近x且可左可右的奇整數。例：Odd[e]=3,Odd[Φ]=1用上述兩個常數，按下述方式得到初始化的陣列S:

S[0]=PwFori=1tot-1do S[i]=S[i-1]+Qw

其中的加法是模2w的加法運算。密鑰的初始化對于給定的參數r和w，開始初始化運算46密鑰擴展1*.為了增強復雜性，可對陣列S,L做多次處理：

i=j=x=y=0do3×max(t,c)times:{S[i]=(S[i]+X+Y)<<<3；X=S[i]；i=(i+1)(modt);L[j]=(L[j]+X+Y)<<<(X+Y)；Y=L[j]；j=(j+1)(modc);}2*.Rivest聲稱，這個擴張函數具有單向性。密鑰擴展1*.為了增強復雜性，可對陣列S,L做多次處理：47加解密運算圖加解密運算圖48加密算法加密：將明文分組為左右A,B；用變量Lei，Rei參與運算程序為：

LE0=A+S[0]RE0=B+S[1]fori=1tordoLEi=((LEi-1⊕REi-1)<<<REi-1)+S[2×i];REi=((REi-1⊕LEi)<<<LEi)+S[2×i+1];加密算法加密：將明文分組為左右A,B；用變量Lei，Rei參49解密算法對兩個1-字變量LDr和RDr。用變量LDi和RDi從r到1做：

fori=rdownto1doRDi-1=((RDi-S[2*i+1]>>>LDi)⊕LDi);LDi-1=((LDi-S[2*i]>>>RDi-1)⊕RDi-1);B=RD0-S[1];A=LD0-S[0].RC5操作模式[RFC2040]Baldwin,R.,andRivest,R.TheRC5,RC5-CBC,RC5-CBC-Pad,andRC5-CTSalgorithms.Oct.1996P96~96解密算法對兩個1-字變量LDr和RDr。用變量LDi和RDi50

現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES51RC6被選為21世紀加密標準算法。RC6是RC5的進一步改進。像RC5那樣，RC6實際上是利用數據的循環(huán)移位。RC5自1995年公布以來，盡管至今為止還沒有發(fā)現(xiàn)實際攻擊的有效手段，然而一些理論攻擊的文章先后也分析出RC5的一些弱點。RC6的加密程序：RC6-w/r/bRC6被選為21世紀加密標準算法。RC6是RC5的進一步改進52DesignPhilosophyLeverageourexperiencewithRC5:usedata-dependentrotationstoachieveahighlevelofsecurity.AdaptRC5tomeetAESrequirementsTakeadvantageofanewprimitiveforincreasedsecurityandefficiency:32x32multiplication,whichexecutesquicklyonmodernprocessors,tocomputerotationamounts.DesignPhilosophyLeverageour53DescriptionofRC6RC6-w/r/b

parameters:Wordsizeinbits:w

(32)(lg(w)=5)Numberofrounds:r

(20)Numberofkeybytes:b

(16,24,or32)KeyExpansion:ProducesarrayS[0…2r

+3]ofw-bitroundkeys.EncryptionandDecryption:Input/Outputin32-bitregistersA,B,C,DDescriptionofRC6RC6-w/r/bp54RC6的基本運算

A+B

Additionmodulo2wA-B

Subtractionmodulo2wA

B

Exclusive-OrA<<<B RotateA

leftbyamountin

low-orderlg(w

)bitsofB

A>>>B

RotateA

right,similarly(A,B,C,D)=(B,C,D,A)ParallelassignmentAxB

Multiplicationmodulo2w

RC5RC6的基本運算A+B Additionmodul55

RC6-w/r/b加密圖，其中f(x)=x×(2x+1):

A⊕<<<B+f<<<C⊕<<<++D+<<<f++S[2r+2]S[2r+3]ABCDRepeatForrrounds…………S[2i]S[2i+1]S[0]S[1]log2wlog2wlog2wRC6-w/r/b加密圖，其中f(x)=x×(2x+156

RC6Encryption(Generic)

B=B+S[0]

D=D+S[1]

fori=1tordo

{

t=(Bx(2B+1))<<<lg(w

)

u=(Dx(2D+1))<<<lg(w

)

A=((At)<<<u)+S[2i

]

C=((Cu)<<<t)+S[2i

+1]

(A,B,C,D)=(B,C,D,A)

}

A=A+S[2r

+2]

C=C+S[2r

+3]

RC6Encryption(Generic)57RC6Encryption(forAES)

B=B+S[0]

D=D+S[1]

fori=1to20do

{

t=(Bx(2B+1))<<<5

u=(Dx(2D+1))<<<5

A=((At)<<<u)+S[2i]

C=((Cu)<<<t)+S[2i

+1]

(A,B,C,D)=(B,C,D,A)

}

A=A+S[42]

C=C+S[43]

RC6Encryption(forAES)B58RC6Decryption(forAES)

C=C-S[43]

A=A-S[42]

fori=20downto1do

{

(A,B,C,D)=(D,A,B,C)

u=(Dx(2D+1))<<<5

t=(Bx(2B+1))<<<5

C=((C-S[2i+1])>>>t)u

A=((A-S[2i])>>>u)t

}

D=D-S[1]

B=B-S[0]

RC6Decryption(forAES)C59KeyExpansion(SameasRC5’s)Input:arrayL[0…c-1]ofinputkeywordsOutput:arrayS[0…43]ofroundkeywordsProcedure:

S[0]=0xB7E15163

fori=1to43doS[i]=S[i-1]+0x9E3779B9

A=B=i=j=0

fors=1to132do

{A=S[i]=(S[i]+A+B)<<<3

B=L[j]=(L[j]+A+B)<<<(A+B)

i=(i+1)mod44

j=(j+1)modc}

KeyExpansion(SameasRC5’s)I60SecurityofKeyExpansionKeyexpansionisidenticaltothatofRC5;noknownweaknesses.Noknownweakkeys.Noknownrelated-keyattacks.Roundkeysappeartobea“random”functionofthesuppliedkey.keyexpansionisquite“one-way”---difficulttoinfersuppliedkeyfromroundkeys.SecurityofKeyExpansionKeye61RC6小結RC6morethanmeetstherequirementsfortheAES;itissimple,fast,andsecure.RC6小結RC6morethanmeetsther62

現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES63AES背景-i1997年4月15日，（美國）國家標準技術研究所（NIST）發(fā)起征集高級加密標準（AdvancedEncryptionStandard）AES的活動，活動目的是確定一個非保密的、可以公開技術細節(jié)的、全球免費使用的分組密碼算法，作為新的數據加密標準。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。作為進入AES候選過程的一個條件，開發(fā)者承諾放棄被選中算法的知識產權。對AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數據分組長度為128比特、密鑰長度為128/192/256比特。AES背景-i1997年4月15日，（美國）國家標準技術研究64AES背景-ii1998年8月12日，在首屆AES會議上指定了15個候選算法。1999年3月22日第二次AES會議上，將候選名單減少為5個，這5個算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES會議上，對這5個候選算法的各種分析結果進行了討論。2000年10月2日，NIST宣布了獲勝者—Rijndael算法，2001年11月出版了最終標準FIPSPUB197。AES背景-ii1998年8月12日，在首屆AES會議上指定65Rijndael簡介不屬于Feistel結構加密、解密相似但不對稱支持128/32=Nb數據塊大小支持128/192/256(/32=Nk)密鑰長度有較好的數學理論作為基礎結構簡單、速度快Rijndael簡介不屬于Feistel結構66AES參數AES參數67SP網絡結構在這種密碼的每一輪中，輪輸入首先被一個由子密鑰控制的可逆函數S作用，然后再對所得結果用置換（或可逆線性變換）P作用。S和P分別被稱為混亂層和擴散層，主要起混亂和擴散作用。

SP網絡結構在這種密碼的每一輪中，輪輸入首先被一個由子密鑰控68AES算法結構-iAES算法的輪變換中沒有Feistel結構，輪變換是由三個不同的可逆一致變換組成，稱之為層，

線性混合層：確保多輪之上的高度擴散。非線性層：具有最優(yōu)最差-情形非線性性的S-盒的并行應用。密鑰加層：輪密鑰簡單地異或到中間狀態(tài)上。AES算法結構-iAES算法的輪變換中沒有Feistel結構69AES算法結構-iiAES算法結構-ii70AES-128加解密過程AES-128加解密過程71AES算法描述假設：State表示數據，以及每一輪的中間結果

RoundKey表示每一輪對應的子密鑰算法如下：第一輪之前執(zhí)行AddRoundKey(State,RoundKey)Round(State,RoundKey){ ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey);

}FinalRound(State,RoundKey){ ByteSub(State); ShiftRow(State); AddRoundKey(State,RoundKey);

}AES算法描述假設：State表示數據，以及每一輪的中間結果72狀態(tài)、密鑰狀態(tài)/密鑰的矩陣表示S00S01S02S03S04S05S06S07S08S09S10S11S12S13S14S15k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33狀態(tài)、密鑰狀態(tài)/密鑰的矩陣表示S00S01S02S03S0473字節(jié)代替(SubstituteBytes)變換字節(jié)代替是一個非線性的字節(jié)代替，獨立地在每個狀態(tài)字節(jié)上進行運算。代替表（S-盒）是可逆的，是一個1616的矩陣。字節(jié)代替(SubstituteBytes)變換字節(jié)代替是74

75exampleexample76行移位(ShiftRow)變換簡單的置換行移位(ShiftRow)變換簡單的置換77exampleexample78列混合MixColumn變換代替操作，將狀態(tài)的列看作有限域GF（28）上的4維向量并被有限域GF（28）上的一個固定可逆方陣A乘列混合MixColumn變換代替操作，將狀態(tài)的列看作有限域79

80exampleexample81輪密鑰加（AddRoundKey)一個簡單地按位異或的操作輪密鑰加（AddRoundKey)一個簡單地按位異或的操82AES的密鑰調度輪密鑰是通過密鑰調度算法從密鑰中產生，包括兩個組成部分：密鑰擴展和輪密鑰選取?；驹砣缦拢核休喢荑€比特的總數等于分組長度乘輪數加1。（如128比特的分組長度和10輪迭代，共需要1408比特的密鑰）。將密碼密鑰擴展成一個擴展密鑰。輪密鑰按下述方式從擴展密鑰中選?。旱谝粋€輪密鑰由開始Nb個字組成，第二個輪密鑰由接下來的Nb個字組成，如此繼續(xù)下去。AES的密鑰調度輪密鑰是通過密鑰調度算法從密鑰中產生，包括兩83AES的密鑰擴展AES的密鑰擴展84密鑰擴展的偽代碼密鑰擴展的偽代碼85偽代碼之二偽代碼之二86

87G變換Rotword執(zhí)行一字節(jié)循環(huán)左移[b0,b1,b2,b3][b1,b2,b3,b0]Subword執(zhí)行使用S-盒實行字節(jié)替換前兩步的結果XOR與輪常數Rcon[j]G變換Rotword執(zhí)行一字節(jié)循環(huán)左移88exampleexample89Rijndael安全性沒有發(fā)現(xiàn)弱密鑰或補密鑰能有效抵抗目前已知的攻擊算法線性攻擊差分攻擊Rijndael安全性沒有發(fā)現(xiàn)弱密鑰或補密鑰90先進對稱分組加密算法的特點可變的密鑰長度:RC5混合的運算IDEA數據相關的圈數RC5密鑰相關的圈數CAST-128密鑰相關的S盒:Blowfish冗長密鑰調度算法：Blowfish可變的F：CAST-128可變長明文/密文塊長度可變圈數每圈操作作用于全部數據先進對稱分組加密算法的特點可變的密鑰長度:RC591分組密碼的一般設計原理針對安全性的一般原則:混亂擴散重要的設計原理:必須能抵抗現(xiàn)有的攻擊方法針對實現(xiàn)的原則軟件硬件分組密碼的一般設計原理針對安全性的一般原則:92分組密碼的整體結構Feistel網絡SP網絡分組密碼的整體結構Feistel網絡93S盒的設計準則S-盒首次出現(xiàn)在Lucifer算法中,因DES的使用而流行.S-盒是許多密碼算法的唯一非線性部件,因此,它的密碼強度決定了整個算法的安全強度.提供了密碼算法所必須的混亂作用.如何全面準確地度量S-盒的密碼強度和設計有效的S-盒是分組密碼設計和分析中的難題.非線性度、差分均勻性、嚴格雪崩準則、可逆性、沒有陷門S盒的設計準則S-盒首次出現(xiàn)在Lucifer算法中,因DES94P置換的設計準則P置換的目的是提供雪崩效應（明文或密鑰的一點小的變動都引起密文的較大變化）P置換的設計準則P置換的目的是提供雪崩效應（明文或密鑰的一點95輪函數的設計準則安全性速度靈活性：能在多種平臺實現(xiàn)輪函數的設計準則安全性96輪函數的構造加法、減法和異或固定循環(huán)/移位數據依賴循環(huán)乘法輪函數的構造加法、減法和異或97密鑰擴展算法的設計設計目標：子密鑰的統(tǒng)計獨立性和靈活性實現(xiàn)簡單速度不存在簡單關系：(給定兩個有某種關系的種子密鑰,能預測它們輪子密鑰之間的關系)種子密鑰的所有比特對每個子密鑰比特的影響大致相同從一些子密鑰比特獲得其他的子密鑰比特在計算上是難的沒有弱密鑰密鑰擴展算法的設計設計目標：子密鑰的統(tǒng)計獨立性和靈活性98思考和練習(推薦)四種模式(ECB,CBC,CFB和OFB)的加解密特點思考和練習(推薦)四種模式(ECB,CBC,CFB和OF99Reference/encryption/aes//rsalabs/rc6//Crypto3e.htmlWilliamStallings,Cryptographyandnetworksecurity:principlesandpractice,SecondEdition.Reference/100

密碼學基礎2計算機學院信息安全課題組 信息安全概論 信息安全概論101

回顧上次課的內容對稱密碼的兩個基本運算代替和置換(Substitution&permutation)對稱密碼分析的兩個基本方法系統(tǒng)分析法（統(tǒng)計分析法）窮舉法對稱密碼的兩個基本設計原則:混亂和擴散密碼分析攻擊的方式

回顧上次課的內容對稱密碼的兩個基本運算102討論議題分組密碼的操作模式實用中數據格式的多樣性安全的工作模式分組密碼的分析方法現(xiàn)代常規(guī)分組加密算法TripleDESRC5、RC6AES……加密的位置：鏈路方式和端到端的方式討論議題分組密碼的操作模式103分組密碼的操作模式電子密碼本ECB(electroniccodebookmode)密碼分組鏈接CBC(cipherblockchaining)密碼反饋CFB(cipherfeedback)輸出反饋OFB(outputfeedback)美國NSB在[FIPSPUB74和81]中規(guī)定ANSI在[ANSIX3.106]中規(guī)定ISO和ISO/IEC在[ISO9732ISO/IEC10116]中規(guī)定分組密碼的操作模式電子密碼本ECB(electronic104電子密碼本（ECB）Ci=EK(Pi)Pi=DK(Ci)電子密碼本（ECB）Ci=EK(Pi)Pi=D105ECB特點簡單和有效可以并行實現(xiàn)不能隱藏明文的模式信息相同明文相同密文同樣信息多次出現(xiàn)造成泄漏對明文的主動攻擊是可能的信息塊可被替換、重排、刪除、重放誤差傳遞：密文塊損壞僅對應明文塊損壞適合于傳輸短信息ECB特點簡單和有效106密碼分組鏈接CBCCi=EK(Ci-1Pi)Pi=EK(Ci)Ci-1密碼分組鏈接CBCCi=EK(Ci-1Pi)Pi=E107CBC特點沒有已知的并行實現(xiàn)算法能隱藏明文的模式信息需要共同的初始化向量IV相同明文不同密文初始化向量IV可以用來改變第一塊對明文的主動攻擊是不容易的信息塊不容易被替換、重排、刪除、重放誤差傳遞：密文塊損壞兩明文塊損壞安全性好于ECB適合于傳輸長度大于64位的報文，還可以進行用戶鑒別,是大多系統(tǒng)的標準如SSL、IPSecCBC特點沒有已知的并行實現(xiàn)算法108密碼反饋CFBCFB:分組密碼流密碼Si為移位寄存器,j為流單元寬度

加密:Ci=Pi(EK(Si)的高j位)Si+1=(Si<<j)|Ci解密:Pi=Ci(EK(Si)的高j位)Si+1=(Si<<j)|Ci

密碼反饋CFBCFB:分組密碼流密碼109

CFB加密示意圖Ci=Pi(EK(Si)的高j位);Si+1=(Si<<j)|Ci

CFB加密示意圖Ci=Pi(EK(Si)的高j位);110

CFB解密示意圖Pi=Ci(EK(Si)的高j位);Si+1=(Si<<j)|Ci

CFB解密示意圖Pi=Ci(EK(Si)的高j位);111CFB特點分組密碼流密碼沒有已知的并行實現(xiàn)算法隱藏了明文模式需要共同的移位寄存器初始值IV對于不同的消息，IV必須唯一誤差傳遞：一個單元損壞影響多個單元

CFB特點分組密碼流密碼112輸出反饋OFBOFB:分組密碼流密碼Si為移位寄存器,j為流單元寬度

加密:Ci=Pi(EK(Si)的高j位)Si+1=(Si<<j)|(EK(Si)的高j位)解密:Pi=Ci(EK(Si)的高j位)Si+1=(Si<<j)|(EK(Si)的高j位)輸出反饋OFBOFB:分組密碼流密碼113

OFB加密示意圖Ci=Pi(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位)OFB加密示意圖Ci=Pi(EK(Si)的高j位);114

OFB解密示意圖Pi=Ci(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位)OFB解密示意圖Pi=Ci(EK(Si)的高j位);S115OFB特點OFB:分組密碼流密碼沒有已知的并行實現(xiàn)算法隱藏了明文模式需要共同的移位寄存器初始值IV誤差傳遞：一個單元損壞只影響對應單元對明文的主動攻擊是可能的信息塊可被替換、重排、刪除、重放安全性較CFB差OFB特點OFB:分組密碼流密碼116運行模式總結種類有無反饋有無并行算法P=>C影響C=>P影響結構相關性主動攻擊有無IV安全性ECBCBCCFBOFB運行模式總結種類有無有無并行算法P=>C影響C=>P影響結構117分組密碼的分析方法根據攻擊者所掌握的信息,可將分組密碼的攻擊分為以下幾類:唯密文攻擊已知明文攻擊選擇明文攻擊攻擊的復雜度數據復雜度:實施該攻擊所需輸入的數據量處理復雜度:處理這些數據所需要的計算量分組密碼的分析方法根據攻擊者所掌握的信息,可將分組密碼的攻擊118分組密碼的典型攻擊方法最可靠的攻擊辦法:強力攻擊最有效的攻擊:差分密碼分析,通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特.線性密碼分析:本質上是一種已知明文攻擊方法,通過尋找一個給定密碼算法的有效的線性近似表達式來破譯密碼系統(tǒng)插值攻擊方法密鑰相關攻擊分組密碼的典型攻擊方法最可靠的攻擊辦法:強力攻擊119現(xiàn)代常規(guī)分組加密算法一種是對DES進行復合，強化它的抗攻擊能力；另一種是開辟新的方法，即象DES那樣加解密速度快，又具有抗差分攻擊和其他方式攻擊的能力。現(xiàn)代常規(guī)分組加密算法一種是對DES進120現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES其他一些較實用的算法，如Blowfish，CAST，以及RC2。現(xiàn)代常規(guī)分組加密算法1.TripleDES1211.TRIPLEDES由于已經證明DES不能成為群，見K.W.CampbellandM.J.WienerProofthatDESisnotagroupInAdvancesinCryptology——Crpto’92.Springer-Verlag,NewYork,1993.于是多重DES，尤其是三重DES還在普遍使用。1.TRIPLEDES由于已經證明DES不能成為群，122雙重DES(DoubleDES)

C=EK2(EK1(P))P=DK1(DK2(C))

雙重DES(DoubleDES)

C=EK2(EK123雙重DES的討論假設對于DES和所有56比特密鑰，給定任意兩個密鑰K1和K2，都能找到一個密鑰K3使得EK2(EK1(P))=EK3(P)。如果這個假設是事實，則DES的兩重加密或者多重加密都將等價于用一個56比特密鑰的一次加密。

從直觀上看，上面的假設不可能為真。因為DES的加密事實上就是做一個從64比特分組到一個64分組的置換，而64比特分組共有264可能的狀態(tài)，因而可能的置換個數為另一方面，DES的每個密鑰確定了一個置換，因而總的置換個數為。直到1992年才有人證明了這個結果。雙重DES的討論假設對于DES和所有56比特密鑰，給定任意124中間相遇(meet-in-the-middle)攻擊

C=EK2(EK1(P))X=EK1(P)=DK2(C)給定明文密文對(P,C)對所有256個密鑰,加密P,對結果排序對所有256個密鑰,解密C,對結果排序逐個比較,找出K1,K2使得EK1(P)=DK2(C)中間相遇(meet-in-the-middle)攻擊

C=125對雙重DES的中間相遇攻擊的分析已知，給定一個明文P，經二重DES加密有264個可能的密文。而二重DES所用密鑰的長度應是112bits，所以選擇密鑰有2112個可能性。于是對給定一個明文P加密成一定的密文方式有2112/264=248種可能。給定兩個明密文對,虛警率降為248-64=2-16。換句話說，對已知2個明文-密文對的中間相遇攻擊成功的概率為1-2-16。攻擊用的代價{加密或解密所用運算次數}≦2256需要大量的存儲器:256

64=1017字節(jié)=230*232對雙重DES的中間相遇攻擊的分析已知，給定一個明文P，經二重126Triple-DES的四種模型DES-EEE3：三個不同密鑰，順序使用三次加密算法DES-EDE3：三個不同密鑰，依次使用加密-解密-加密算法DES-EEE2：K1=K3，同上DES-EDE2：K1=K3，同上Triple-DES的四種模型DES-EEE3：三個不同密鑰127雙密鑰的三重DES

（TripleDESwithTwoKeys)C=EK1(DK2(EK1(P)))P=DK1(EK2(DK1(C)))雙密鑰的三重DES

（TripleDESwithTwo128對雙密鑰的三重DES的分析-i該模式由IBM設計,可與常規(guī)加密算法兼容這種替代DES的加密較為流行并且已被采納用于密鑰管理標準（TheKeyManagerStandardsANSX9.17和ISO8732).交替使用K1和K2可以抵抗中間相遇攻擊.如果C=EK2(EK1(EK1(P))),只需要256+2次加密到目前為止，還沒有人給出攻擊三重DES的有效方法。對其密鑰空間中密鑰進行蠻干搜索，那么由于空間太大為2112=5×1033，這實際上是不可行的。若用差分攻擊的方法，相對于單一DES來說復雜性以指數形式增長，要超過1052。對雙密鑰的三重DES的分析-i該模式由IBM設計,可與常規(guī)129對雙密鑰的三重DES的分析-ii目前還沒有針對兩個密鑰三重DES的實用攻擊方法。但對兩個密鑰三重DES的攻擊有一些設想，以這些設想為基礎將來可能設計出更成功的攻擊技術。

MerkleR.andHellman,M.“Onthesecurityofmultipleencryption”.CommunicationoftheACM,July1981Oorschot,PandWiener,M.“AKnown-plaintextattackontwo-keytripleencryption”Proceedings,EUROCrypt’90,1990:publishedbySpringer-Verlag對雙密鑰的三重DES的分析-ii目前還沒有針對兩個密鑰三重D130三密鑰的三重DES

（TripleDESwithThreeKeys)C=EK3(DK2(EK1(P)))P=DK3(EK2(DK1(C)))三密鑰的三重DES

（TripleDESwithThr131三密鑰的三重DES分析密鑰的有效長度為168位與DES的兼容性可以通過令K3=K2或K1=K2得到許多基于Internet的應用里用到：PGP和S/MIME三密鑰的三重DES分析密鑰的有效長度為168位132現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES133國際數據加密IDEA（InternationalDataEncryptionAlgorithm)算法1990年瑞士聯(lián)邦技術學院的來學嘉和Massey提出，PES，91年修訂，92公布細節(jié)設計目標從兩個方面考慮加密強度易實現(xiàn)性強化了抗差分分析的能力，PGP國際數據加密IDEA（InternationalData134IDEA算法特點64位分組,128位密鑰運算:XOR,模216（65536）加,模(216+1)（65537）乘三種運算均不滿足分配律與結合律有大量弱密鑰難以直接擴展到128位塊IDEA算法特點64位分組,128位密鑰135IDEA設計思想得到confusion的途徑按位異或以216(65536)為模的加法以216+1

(65537)為模的乘法互不滿足分配律、結合律得到diffusion的途徑乘加(MA)結構實現(xiàn)上的考慮軟件和硬件實現(xiàn)上的考慮IDEA設計思想得到confusion的途徑136IDEA加密算法IDEA加密算法137IDEA

每一輪

IDEA

每一輪138IDEA輸出變換階段IDEA輸出變換階段139IDEA的子密鑰IDEA的子密鑰140

現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES141RC5作者為RonRivest1994設計、1995公開1.適用于軟件或者硬件實現(xiàn)2.運算速度快3.能適應于不同字長的程序（一個字的bit數是RC5的一個參數；）加密的輪數可變（輪數是RC5的第二個參數）密鑰長度是可變的（密鑰長度是RC5的第三個參數）6.對內存要求低7.依賴于數據的循環(huán)移位（增強抗攻擊能力）RC5作者為RonRivest1994設計、1995公142RC5參數三個參數參數w：表示字長，RC5加密兩字長分組，可用值為16、32、64參數r：表示輪數，可用值0,1,…,255參數b：表示密鑰K的字節(jié)數，可用值0,1,…,255RC5版本：RC5-w/r/b算法作者建議標定版本為RC5-32/12/16RC5參數三個參數143RC5基本運算整個加密使用了下述3個基本運算和它們的逆運算：模2w加法運算，表示為“+”；逐比特異或運算，表示為“⊕”；字的循環(huán)左移運算：字x循環(huán)左移y比特，表示為

x<<<y

實際只有y的log2w個低位比特來確定x的循環(huán)數它的逆為循環(huán)右移y比特，表示為

x>>>y如（a0,a1,a2,…,an-1)<<<3=(a3,a4,…,an-1,a0,a1,a2)RC5基本運算整個加密使用了下述3個基本運算和它們的逆運算：144密鑰擴展總計產生t=2r+2

個子密鑰，每個密鑰的長度為一個字長（wbits)。密鑰擴展總計產生t=2r+2個子密鑰，每個密鑰的長度為145密鑰的初始化對于給定的參數r和w，開始初始化運算

Pw=Odd((e-2)2w)Qw=Odd((Φ-1)2w)這里e=2.718281828459…(自然對數的底）Φ=1.618033988749…（黃金分割比率）并且Odd[x]表示最接近x且可左可右的奇整數。例：Odd[e]=3,Odd[Φ]=1用上述兩個常數，按下述方式得到初始化的陣列S:

S[0]=PwFori=1tot-1do S[i]=S[i-1]+Qw

其中的加法是模2w的加法運算。密鑰的初始化對于給定的參數r和w，開始初始化運算146密鑰擴展1*.為了增強復雜性，可對陣列S,L做多次處理：

i=j=x=y=0do3×max(t,c)times:{S[i]=(S[i]+X+Y)<<<3；X=S[i]；i=(i+1)(modt);L[j]=(L[j]+X+Y)<<<(X+Y)；Y=L[j]；j=(j+1)(modc);}2*.Rivest聲稱，這個擴張函數具有單向性。密鑰擴展1*.為了增強復雜性，可對陣列S,L做多次處理：147加解密運算圖加解密運算圖148加密算法加密：將明文分組為左右A,B；用變量Lei，Rei參與運算程序為：

LE0=A+S[0]RE0=B+S[1]fori=1tordoLEi=((LEi-1⊕REi-1)<<<REi-1)+S[2×i];REi=((REi-1⊕LEi)<<<LEi)+S[2×i+1];加密算法加密：將明文分組為左右A,B；用變量Lei，Rei參149解密算法對兩個1-字變量LDr和RDr。用變量LDi和RDi從r到1做：

fori=rdownto1doRDi-1=((RDi-S[2*i+1]>>>LDi)⊕LDi);LDi-1=((LDi-S[2*i]>>>RDi-1)⊕RDi-1);B=RD0-S[1];A=LD0-S[0].RC5操作模式[RFC2040]Baldwin,R.,andRivest,R.TheRC5,RC5-CBC,RC5-CBC-Pad,andRC5-CTSalgorithms.Oct.1996P96~96解密算法對兩個1-字變量LDr和RDr。用變量LDi和RDi150

現(xiàn)代常規(guī)分組加密算法1.TripleDES2.IDEA3.RC54.RC65.AES現(xiàn)代常規(guī)分組加密算法1.TripleDES151RC6被選為21世紀加密標準算法。RC6是RC5的進一步改進。像RC5那樣，RC6實際上是利用數據的循環(huán)移位。RC5自1995年公布以來，盡管至今為止還沒有發(fā)現(xiàn)實際攻擊的有效手段，然而一些理論攻擊的文章先后也分析出RC5的一些弱點。RC6的加密程序：RC6-w/r/bRC6被選為21世紀加密標準算法。RC6是RC5的進一步改進152DesignPhilosophyLeverageourexperiencewithRC5:usedata-dependentrotationstoachieveahighlevelofsecurity.AdaptRC5tomeetAESrequirementsTakeadvantageofanewprimitiveforincreasedsecurityandefficiency:32x32multiplication,whichexecutesquicklyonmodernprocessors,tocomputerotationamounts.DesignPhilosophyLeverageour153DescriptionofRC6RC6-w/r/b

parameters:Wordsizeinbits:w

(32)(lg(w)=5)Numberofrounds:r

(20)Numberofkeybytes:b

(16,24,or32)KeyExpansion:ProducesarrayS[0…2r

+3]ofw-bitroundkeys.EncryptionandDecryption:Input/Outputin32-bitregistersA,B,C,DDescriptionofRC6RC6-w/r/bp154RC6的基本運算

A+B

Additionmodulo2wA-B

Subtractionmodulo2wA

B

Exclusive-OrA<<<B RotateA

leftbyamountin

low-orderlg(w

)bitsofB

A>>>B

RotateA

right,similarly(A,B,C,D)=(B,C,D,A)ParallelassignmentAxB

Multiplicationmodulo2w

RC5RC6的基本運算A+B Additionmodul155

RC6-w/r/b加密圖，其中f(x)=x×(2x+1):

A⊕<<<B+f<<<C⊕<<<++D+<<<f++S[2r+2]S[2r+3]ABCDRepeatForrrounds…………S[2i]S[2i+1]S[0]S[1]log2wlog2wlog2wRC6-w/r/b加密圖，其中f(x)=x×(2x+1156

RC6Encryption(Generic)

B=B+S[0]

D=D+S[1]

fori=1tordo

{

t=(Bx(2B+1))<<<lg(w

)

u=(Dx(2D+1))<<<lg(w

)

A=((At)<<<u)+S[2i

]

C=((Cu)<<<t)+S[2i

+1]

(A,B,C,D)=(B,C,D,A)

}

A=A+S[2r

+2]

C=C+S[2r

+3]

RC6Encryption(Generic)157RC6Encryption(forAES)

B=B+S[0]

D=D+S[1]

fori=1to20do

{

t=(Bx(2B+1))<<<5

u=(Dx(2D+1))<<<5

A=((At)<<<u)+S[2i]

C=((Cu)<<<t)+S[2i

+1]

(A,B,C,D)=(B,C,D,A)

}

A=A+S[42]

C=C+S[43]

RC6Encryption(forAES)B158RC6Decryption(forAES)

C=C-S[43]

A=A-S[42]

fori=20downto1do

{

(A,B,C,D)=(D,A,B,C)

u=(Dx(2D+1))<<<5

t=(Bx(2B+1))<<<5

C=((C-S[2i+1])>>>t)u

A=((A-S[2i])>>>u)t

}

D=D-S[1]

B=B-S[0]

RC6Decryption(forAES)C159KeyExpansion(SameasRC5’s)Input:arrayL[0…c-1]ofinputkeywordsOutput:arrayS[0…43]ofroundkeywordsProcedure:

S[0]=0xB7E15163

fori=1to43doS[i]=S[i-1]+0x9E3779B9

A=B=i=j=0

fors=1to132do

{A=S[i]=(S[i]+A+B)<<<3

B=L[j]=(L[j]+A+B)<<<(A+B)

i=(i+1)mod44

j=(j+1)modc}

KeyExpansion(SameasRC5’s)I160SecurityofKeyExpansionKeyexpansionisidenti