密碼學課件 Feistel結(jié)構(gòu)分組密碼

密碼學導論IntroductiontoCryptology主講教師：李衛(wèi)海第3章Feistel結(jié)構(gòu)分組密碼分組密碼Feistel結(jié)構(gòu)數(shù)據(jù)加密標準DES其它Feistel結(jié)構(gòu)分組密碼分組密碼Feistel結(jié)構(gòu)數(shù)據(jù)加密標準DES其它Feistel結(jié)構(gòu)分組密碼分組密碼分組密碼(BlockCipher)：通常以大于等于64位的數(shù)據(jù)塊為處理單位密文僅與算法和密鑰有關，與明文數(shù)據(jù)塊的位置無關例如：DES、AES等n比特的明文分組，加密產(chǎn)生n比特的密文分組2n個不同的明文分組，各自產(chǎn)生2n個唯一的密文分組本質(zhì)上是一個巨大的代換表完美安全的分組映射對密鑰量的需求：n位的分組就有2n種輸入每種輸入需要n位“密鑰”控制，確定映射到哪一個密文共需n×2n

位“密鑰”24個明文4比特分組在一個密鑰下的映射24個密文Feistel結(jié)構(gòu)Feistel結(jié)構(gòu)通過復雜運算，達到近似的理想很多分組密碼基于Feistel結(jié)構(gòu)采用了乘積加密器的思想，交替使用代換S-box

和置亂P-box稱為S-P網(wǎng)絡（Substitution-PermutationNetwork）加密算法：將輸入等分為兩段，進行若干輪運算，每輪中對左半段數(shù)據(jù)進行代換，依據(jù)輪函數(shù)F（右半段數(shù)據(jù)和子密鑰）然后置換：交換左右兩段數(shù)據(jù)HorstFeistelFeistel結(jié)構(gòu)——解密

Feistel結(jié)構(gòu)的參數(shù)參數(shù)：分組長度：長度越大，安全性越高，處理速度也越低密鑰長度：長度越大，安全性越高，可能降低處理速度迭代輪數(shù)：單輪不能提供足夠的安全性；輪數(shù)越多，安全性越高，處理時間也成倍增加子密鑰產(chǎn)生算法：算法越復雜，密碼分析攻擊越難，會降低處理速度輪函數(shù)：算法越復雜，安全性越高，處理速度也降低特點：快速軟件加/解密分析簡單：利于脆弱性的分析與測試但隨著輪數(shù)的增加，分析的復雜度急劇上升Feistel結(jié)構(gòu)對輪函數(shù)的要求

分組密碼Feistel結(jié)構(gòu)數(shù)據(jù)加密標準DES其它Feistel結(jié)構(gòu)分組密碼DES的起源IBM設計出Lucifer密碼(1971)由HorstFeistel帶領的團隊用128比特密鑰加密64比特數(shù)據(jù)分組Tuchman-Mayer牽頭開發(fā)商業(yè)密碼適合于單芯片實現(xiàn)密鑰長度56比特，抗密碼分析能力更強美國國家安全局介入1973年美國國家標準局征求國家密碼標準方案，IBM將上述方案提交，并被采用，稱為數(shù)據(jù)加密標準DES（DataEncryptionStandard）DES的應用民間研究顯示DES安全性很強廣泛應用在金融、遺產(chǎn)等領域雖然差分攻擊和線性分析攻擊在理論上有效，但實現(xiàn)起來計算量仍很大安全性曾爭議頗多美國國家安全局的介入用56比特密鑰加密64比特數(shù)據(jù)設計標準列入機密曾是應用最廣泛的分組密碼技術(shù)AES正取而代之DES算法：整體結(jié)構(gòu)64比特明文分組輸入64比特密文分組輸出64比特密鑰實際只使用56位其它可用作奇偶校驗等Feistel密碼框架16輪操作IP：初始置亂IP-1：逆初始置亂PC1、PC2：壓縮置亂IP64比特密文64比特明文K1K1664比特密鑰第1輪第2輪第16輪32比特置換IP-1PC1分組左移分組左移分組左移PC2PC2PC2646464484848645656565656DES算法：初始置亂IP與逆初始置亂IP-1置亂表中的每個元素表明了輸入位在

64位輸出中的位置兩表互逆IP表中第1個是58，表示明文的第58位被

移到第1位IP-1表中第58個是1，表示輸入的第1位被

移到第58位IP-1表很有規(guī)律IP和IP-1表與密鑰無關，不提供安全性DES算法：輪函數(shù)結(jié)構(gòu)64位數(shù)據(jù)分為L、R各32位子密鑰K為48位輪函數(shù)：將32位R通過E擴展為48位與密鑰K異或由8個S盒子緊縮為32位由置亂P作用后輸出S盒代換擴展置換E置亂PKiRi-1Li-1RiLiF3232323232484848DES算法：擴展置換E將32位輸入分為8組，每組4位從相鄰兩組的鄰近位置各取1位組成6位8組共48位最后一步置亂3212345456789891011121312131415161716171819202120212223242524252627282928293031321S盒代換擴展置換E置亂PK323232484848DES算法：S盒代換8組數(shù)據(jù)，每組6位每組輸入到一個S盒子中，輸出為4位輸出連接為32位S1S2S3S4S5S6S7S848324444444466666666S盒代換擴展置換E置亂PK323232484848DES算法：S盒代換每個S盒子為4行16列的矩陣，每行定義一個可逆置換輸入6位，輸出4位輸入的第1位和第6位組成一個2位二進制數(shù)，選擇行輸入的第2位至第5位組成一個4位二進制數(shù)，選擇列將選中的數(shù)字以二進制數(shù)輸出例：S1盒子輸入011001選擇行1（01）；選擇列12（1100）將選中的9輸出1001。S盒子的行、列從0開始計數(shù)DES算法：輪函數(shù)的擴散/混淆作用擴散/混淆擴散之前位于每個4比特分組中間的兩個比特，一輪操作后會擴散到

本分組的4個比特擴散之前位于每個4比特分組兩側(cè)的兩個比特，一輪操作后會擴散到

兩個分組共8個比特若干輪后，會迅速擴散到整個64位分組混淆主要依賴S盒子的非線性S盒代換擴展置換E置亂PK323232484848123456789101112131415161718192021222324252627282930313232123454567898910111213121314151617161718192021202122232425242526272829282930313211234567891011121314151617181920212223242526272829303132DES算法：密鑰的初始置亂選擇輸入64位密鑰，保留56位置亂選擇PC1將64位原始密鑰置亂輸出56位注意：若用大寫英文字母作為密鑰，常用它們

的ASCII碼作為二進制密鑰。這是危險的，因為

它們的ASCII碼最高位均為0，而DES舍棄的是

最低位！K1K1664比特密鑰PC1分組左移分組左移分組左移PC2PC2PC24848485656565656DES算法：子密鑰的產(chǎn)生56位密鑰分為C和D兩組每輪分別循環(huán)左移1位或2位循環(huán)后結(jié)果經(jīng)置亂選擇PC2，輸出48位作為該輪子密鑰循環(huán)結(jié)果進入下一輪16輪后，C和D累計移位28位，恢復原位LS-iPC2KiCi-1LS-i28284828282828Di-1CiDiDES算法：解密解密是加密的逆過程對Feistel結(jié)構(gòu)密碼，采用相同算法，但是子密鑰使用的次序正好相反：IP變換抵消加密的最后一步IP-1第一輪使用密鑰K16第二輪使用密鑰K15……第十六輪使用密鑰K1IP-1變換抵消加密的第一步IP獲得解密明文DES的安全性密鑰的長度問題56bits密鑰有2^56=72,057,584,037,927,936≈7.2億億之多蠻力搜索(bruteforcesearch)似乎很困難，20世紀70年代估計要1000－2000年技術(shù)進步使蠻力搜索成為可能1997年網(wǎng)絡合作破譯耗時96天。1998年在一臺專用機上(EFF)只要三天時間即可1999年在超級計算機上只要22小時!S-box問題其設計標準沒有公開但迄今并沒有發(fā)現(xiàn)S盒存在致命弱點DES的安全性：弱密鑰至少有4個“弱密鑰”：E(k,E(k,m))=m 0101010101010101,1F1F1F1F0E0E0E0E E0E0E0E0F1F1F1F1,FEFEFEFEFEFEFEFE至少有6對“半弱密鑰”：E(k,E(k',m))=m 01FE01FE01FE01FE?FE01FE01FE01FE01 1FE01FE00EF10EF1?E01FE01FF10EF10E 01E001E001F101F1?E001E001F101F101 1FFE1FFE0EFE0EFE?FE1FFE1FFE0EFE0E 011F011F010E010E?1F011F010E010E01 E0FEE0FEF1FEF1FE?FEE0FEE0FEF1FEF1這里每字節(jié)的最低位用作奇偶校驗位C和D分組全0或全1C和D分組數(shù)據(jù)類似010101...DES的安全性：雪崩效應AvalancheEffect雪崩效應：明文或密鑰的一比特的變化，引起密文許多比特的改變加密算法的關鍵性能之一希望明文或密鑰的1比特變化，會使大約半數(shù)密文比特發(fā)生變化；否則，可能存在方法減小待搜索的明文和密鑰空間DES密碼有良好的雪崩效應明文或密鑰相差一個比特，3輪后就已經(jīng)達到了

良好的雪崩效應效果DES的安全性：能量攻擊通過分析電子設備執(zhí)行計算過程中的能量消耗來尋找有關密鑰的信息指令執(zhí)行時（例如在智能卡中）所消耗的能量與其執(zhí)行的指令和數(shù)據(jù)的存取有關能量攻擊可分為簡單能量分析攻擊SPA（SimplePowerAnalysis）和差分能量分析攻擊DPA（DifferentialPowerAnalysis）通過觀測密碼算法在執(zhí)行過程（例如在智能卡中）中任何特定時間所消耗的能量來獲得一些有用的信息。執(zhí)行乘法比執(zhí)行加法消耗更多的能量向存儲器中寫1比寫0消耗更多的能量某智能卡用DES算法加密時的能量追蹤圖DES的安全性：統(tǒng)計分析類型的攻擊主要利用了加密器的一些深層結(jié)構(gòu)搜集加密相關信息設法恢復部分或全部子密鑰的位如果必要的話對其余部分再輔以窮舉搜索這些攻擊本質(zhì)上是統(tǒng)計分析，包括差分分析、線性分析、相關密鑰攻擊DES不能抵御差分分析、線性分析差分密碼分析DifferentialCryptanalysis歷史1990年，Murphy、Biham和Shamir首次提出用差分密碼分析攻擊分組密碼和散列函數(shù)，是第一種可以以少于2^55的復雜性對DES進行破譯的方法需要2^47個選擇明文及對應密文1974年IBM的DES研究團隊就發(fā)現(xiàn)了差分攻擊，并在S盒子和置換P的設計中加以考慮差分密碼分析攻擊是一種選擇明文攻擊分析明文對的差異和密文對的差異之間的關系確定輪運算的子密鑰，從而恢復某些密鑰比特差分分析：方法概述

差分分析：方法概述第1步：查出一個r-1輪的輪特征ΔY0,ΔY1,

…,ΔYr-1，它的概率最大或幾乎最大第2步：固定輸入差分為ΔY0，均勻隨機地選擇明文Y0，并計算Y0*，加密Y0和

Y0*

（r輪）得到密文Yr和Yr*第3步：窮舉最后一輪子密鑰。為每一個子密鑰Krt設置一個計數(shù)器Λt（假設子密鑰為m比特，0≤t≤2m-1），用每個Krt解密Yr和Yr*，得Yr-1和Yr-1*，若它們的差分與輪特征中的

Yr-1相等，則認為是一個正確對，給相應的計數(shù)器Λt加1第4步：重復第2、3步，直到一個或幾個計數(shù)器的值明顯高于其它計數(shù)器的值。這就是最后一輪子密鑰第5步：窮舉密鑰的剩余比特線性密碼分析LinearCryptanalysis

線性密碼分析：建立關于密鑰的方程組

分組密碼Feistel結(jié)構(gòu)數(shù)據(jù)加密標準DES其它Feistel結(jié)構(gòu)分組密碼雙重DES密碼DES不夠安全設計新算法使用多個密鑰，多次加密雙重DES算法：C=E(K2,E(K1,P))P=D(K1,D(K2,C))密鑰112位一般而言，雙重DES不會等效為一次DES找不到k3使得E(K2,E(K1,P))=E(K3,P)EEPXK1K2CDDCXK2K1P中間相遇攻擊攻擊雙重DES，平均工作量僅為256思路：尋找X=E[K1,P]=D[K2,C]算法：若已知(P,C)，則對256個可能的K1加密P，結(jié)果存入表中，按X值排序?qū)?56個可能的K2解密C，在表中尋找匹配如果產(chǎn)生匹配，則用另一個明文密文對檢測所得兩個密鑰如果兩密鑰產(chǎn)生正確的密文，則接受為正確中間相遇攻擊得到錯誤密鑰的概率是1-2-16對任意明文P，雙重DES產(chǎn)生的密文有264種可能，密鑰有2112種可能平均而言，對一個給定的明文P和密文C，有2112/264=248個滿足它們的112位密鑰，即虛警為248用另一個64位已知明文密文對檢測，虛警降低到248/264=2-16EEPXK1K2CEDPXK1K2C3DES（TDEA）常常只使用兩個密鑰：C=E(K1,D(K2,E(K1,P)))P=D(K1,E(K2,D(K1,C)))加密、解密交替使用，為了與單次DES兼容已用于密鑰管理標準ANSX9.17和ISO8732中沒有可行的攻擊方法使用三個密鑰的TDEA已應用在基于Internet的應用：PGP和S/MIMEEDPAK1K2CEBK1DECBK1K2PDAK1Blowfish密碼Blowfish，1993年由BruceSchneier提出，特性：64比特分組快速：在32位處理器上加密每字節(jié)18時鐘周期緊湊：可在少于5K的內(nèi)存上運行簡單：結(jié)構(gòu)簡單、容易實現(xiàn)可變的安全性：密鑰長度可變，從32位到448位子密鑰和S盒的產(chǎn)生32位到448位可變長密鑰，存儲在K數(shù)組中[Kj]，用來產(chǎn)生18個32-bit的子密鑰，存儲在P數(shù)組中[Pj]4個8

32的32位項的S盒，存儲在[Si,j]Blowfish密碼：初始化產(chǎn)生P數(shù)組和S數(shù)組的步驟：用常數(shù)π的小數(shù)部分初始化P數(shù)組和4個S盒用K數(shù)組（循環(huán)使用）對P數(shù)組逐位異或?qū)?4位全零分組加密，用所得密文替代P1和P2對第三步的輸出加密，用所得密文替代P3和P4重復這個過程以更新P和S數(shù)組的所有元素，每一步都使用不斷變化的Blowfish算法的輸出為產(chǎn)生全部子密鑰P和S盒，總共執(zhí)行521次加密算法，所有產(chǎn)生的P和S存儲在存儲器中Blowfish對密鑰經(jīng)常變化的應用不合適，也不適合存儲空間有限的應用Blowfish密碼：加密算法Blowfish的加密兩個基本操作:模232的加和逐位異或數(shù)據(jù)被分成左右兩部分L0&R0fori=1to16doRi=Li-1

⊕Pi;Li=F[Ri]⊕Ri-1;R17=L16

⊕P17;L17=R16

⊕P18;單輪結(jié)構(gòu)輪函數(shù)F[a,b,c,d]=((S1,a+S2,b)⊕S3,c)+S4,dBlowfish密碼：評價Blowfish的S盒依賴于密鑰，子密鑰和S盒通過重復使用Blowfish本身產(chǎn)生，使得各比特徹底糾纏在一起，密碼分析非常困難在每一循環(huán)中對數(shù)據(jù)的兩部分進行操作，增大了密碼強度通過選擇適當?shù)拿荑€長度(最長448位)，對窮舉攻擊來說，Blowfish幾乎是不可破的Blowfish的算法執(zhí)行是很快的有人評價Blowfish可能是最難破譯的常規(guī)加密算法RC5密碼RC5是RonaldRivest設計的一種對稱加密算法，具有如下特點適于軟件和硬件實現(xiàn)快速：設計成面向字的簡單算法，加快運算速度可用于字長不同的處理器迭代次數(shù)可變密鑰長度可變簡單，易于實現(xiàn)和確定算法強度對存儲量要求低安全性高與數(shù)據(jù)相關的循環(huán)RC5密碼RC5包含一族密碼：RC5-w/r/bw=以比特為單位的字大小(16,32,64)，每個分組包含兩個字r=迭代輪數(shù)(0..255)b=密鑰字節(jié)數(shù)(0..255)常用版本是RC5-32/12/16每字32比特，分組大小64比特12輪迭代16字節(jié)（128比特）密鑰RC5密碼：子密鑰產(chǎn)生RC5使用2r+2個子密鑰字(w-bits)，存儲于數(shù)組S[i],i=0..t-1根據(jù)常數(shù)e和Φ(黃金分割比)初始化數(shù)組SPw=Odd[(e-2)2w];Qw=Odd[(Φ-2)2w];e=2.718281828459;Φ=1.618033988749Odd[x]表示與x最接近的奇數(shù)S[0]=Pw;fori=1tot-1doS[i]=S[i-1]+Qw;密鑰字節(jié)存放（低位在前）于一個c個字的數(shù)組L中通過一個混合運算將L和S合成為最終的Si=j=X=Y=0;do3×max(t,c)timesS[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;RC5密碼：加密算法明文分組分為A、B兩部分L0=A+S[0];R0=B+S[1];fori=1tordoLi=((Li-1

Ri-1)<<<Ri-1)+S[2×i];Ri=((Ri-1

Li)<<<Li)+S[2×i+1];這里“<<<”表示循環(huán)左移每輪迭代類似于兩次DES輪迭代循環(huán)移位是非線性的主要來源輪數(shù)不能過少（例如12-16輪）SMS4密碼無線局域網(wǎng)產(chǎn)品使用我國第一個公開商用密碼標準分組長度128比特，密鑰長度128比特加密算法與密鑰擴展算法都采用32輪非線性迭代結(jié)構(gòu)解密算法與加密算法結(jié)構(gòu)相同，輪密鑰的使用順序相反輸入明文為4個字(X0,X1,X2,X3)輸出密文為4個字(Y0,Y1,Y2,Y3)密鑰為4個字(MK0,MK1,MK2,MK3)擴展輪密鑰為rki(i=0,…,31)，每個輪密鑰為字FK=(FK0,FK1,FK2,FK3)為系統(tǒng)參數(shù)CK=(CK0,CK1,…,CK31)為固定參數(shù)SMS4密碼：加密解算法加密算法 Xi+4=F(Xi,Xi+1,Xi+2,Xi+3,rki)=Xi

T(Xi+1

Xi+2

Xi+3

rki) (Y0,Y1,Y2,Y3)=(X35,X34,X33,X32)解密算法結(jié)構(gòu)與加密算法相同，但密鑰使用順序相反XiTrkiXi+1Xi+2Xi+3Xi+4Xi+3Xi+2Xi+1SMS4密碼：輪函數(shù)F輪函數(shù)F(X0,X1,X2,X3,rk)=X0

T(X1

X2

X3

rk)T是可逆變換，由非線性變換τ和線性變換L復合而成T(.)=L(τ(.))非線性變換τ由4個S盒構(gòu)成設輸入為4個字節(jié)(a0,a1,a2,a3)，輸出為(b0,b1,b2,b3) (b0,b1,b2,b3)=τ((a0,a1,a2,a3))=(S(a0),S(a1),S(a2),S(a3))線性變換L設輸入為B，輸出為C，均為字 C=B

(B<<<2)

(B<<<10)

(B<<<18)

(B<<<24)“<<<”是循環(huán)左移每輪4次查表，4次循環(huán)移位，8次異或SMS4密碼：S盒S盒8位輸入，8位輸出輸入的前4位選擇行，后4位選擇列SMS4密碼：密鑰擴展密鑰擴展算法(K0,K1,K2,K3)=(MK0

FK0,MK1

FK1,MK2

FK2,MK3

FK3)fori=0,1,…,31rki=Ki+4=Ki

T'(Ki+1

Ki+2

Ki+3

CKi)說明：可以事先計算、存儲以備用T'與加密算法輪函數(shù)中的T基本相同，但須將線性變換L變?yōu)長'(B)=B

(B<<<13)

(B<<<23)系統(tǒng)參數(shù)FK0=(A3B1BAC6)16