第3講_對稱密鑰密碼體制

1、1第第3講講對稱密鑰密碼體制對稱密鑰密碼體制按加解密采用的密鑰不同按加解密采用的密鑰不同按密碼出現(xiàn)的時間不同按密碼出現(xiàn)的時間不同古典密碼古典密碼現(xiàn)代密碼現(xiàn)代密碼密碼學密碼學（Cryptology）(Symmetric cipher)(Asymmetric cipher)分組密碼分組密碼流密碼流密碼公鑰密碼公鑰密碼按加密的方式按加密的方式對稱密碼對稱密碼非對稱密碼非對稱密碼(Classical cipher)(Modern cipher)(Block cipher)(Stream cipher)(Public-Key cipher)什么是流密碼什么是流密碼一次一密：指在流密碼當中使用與消息長度等

2、長的隨機密鑰一次一密：指在流密碼當中使用與消息長度等長的隨機密鑰, , 密鑰本身只使用一次密鑰本身只使用一次流密碼的研究現(xiàn)狀流密碼的研究現(xiàn)狀 當前對流密碼的研究主要集中在以下兩個方向：當前對流密碼的研究主要集中在以下兩個方向：（1 1）什么樣的序列可以作為安全可靠的密鑰序列？即衡量密什么樣的序列可以作為安全可靠的密鑰序列？即衡量密鑰流序列好壞的標準。鑰流序列好壞的標準。（2 2）如何構造線性復雜度高、周期大的密鑰流序列？如何構造線性復雜度高、周期大的密鑰流序列？ 在保密強度要求高的場合如大量軍事密碼系統(tǒng)，仍多采用在保密強度要求高的場合如大量軍事密碼系統(tǒng)，仍多采用流密碼，美軍的核心密碼仍是流密碼

3、，美軍的核心密碼仍是“一次一密一次一密”的的流密碼體制流密碼體制。鑒。鑒于流密碼的分析和設計在軍事和外交保密通信中有重要價值，于流密碼的分析和設計在軍事和外交保密通信中有重要價值，流密碼的設計基本上都是保密的流密碼的設計基本上都是保密的，國內外少有專門論述流密碼，國內外少有專門論述流密碼學的著作，公開的文獻也不多。盡管如此，由于流密碼長度可學的著作，公開的文獻也不多。盡管如此，由于流密碼長度可靈活變化，且具有運算速度快、密文傳輸中沒有差錯或只有有靈活變化，且具有運算速度快、密文傳輸中沒有差錯或只有有限的錯誤傳播等優(yōu)點，目前仍是國際密碼應用的主流，而基于限的錯誤傳播等優(yōu)點，目前仍是國際密碼應用的

4、主流，而基于偽隨機序列的流密碼是當今最通用的密碼系統(tǒng)。偽隨機序列的流密碼是當今最通用的密碼系統(tǒng)。流密碼的研究現(xiàn)狀流密碼的研究現(xiàn)狀3.1 流密碼流密碼v在流密碼中，將明文消息按一定長度分組（長度較小，通常按在流密碼中，將明文消息按一定長度分組（長度較小，通常按字或字節(jié)），然后對各組用相關但不同的密鑰進行加密，產生字或字節(jié)），然后對各組用相關但不同的密鑰進行加密，產生相應的密文，相同的明文分組會因在明文序列中的位置不同而相應的密文，相同的明文分組會因在明文序列中的位置不同而對應于不同的密文分組。對應于不同的密文分組。v相對分組密碼而言，流密碼主要有以下優(yōu)點：相對分組密碼而言，流密碼主要有以下優(yōu)點：

5、第一，在硬件實施上，流密碼的速度一般要比分組密碼快，而且不需第一，在硬件實施上，流密碼的速度一般要比分組密碼快，而且不需要有很復雜的硬件電路：要有很復雜的硬件電路：第二，在某些情況下（例如對某些電信上的應用），當緩沖不足或必第二，在某些情況下（例如對某些電信上的應用），當緩沖不足或必須對收到的字符進行逐一處理時，流密碼就顯得更加必要和恰當；須對收到的字符進行逐一處理時，流密碼就顯得更加必要和恰當；第三，流密碼能較好地隱藏明文的統(tǒng)計特征等。第三，流密碼能較好地隱藏明文的統(tǒng)計特征等。流密碼的原理流密碼的原理v在流密碼中，明文按一定長度分組后被表示成一個序列，并在流密碼中，明文按一定長度分組后被表示

6、成一個序列，并稱為稱為明文流明文流，序列中的一項稱為一個，序列中的一項稱為一個明文字明文字。加密時，先由。加密時，先由主密鑰產生一個密鑰流序列，該序列的每一項和明文字具有主密鑰產生一個密鑰流序列，該序列的每一項和明文字具有相同的比特長度，稱為一個相同的比特長度，稱為一個密鑰字密鑰字。然后依次把明文流和密。然后依次把明文流和密鑰流中的對應項輸入加密函數(shù)，產生相應的鑰流中的對應項輸入加密函數(shù)，產生相應的密文字密文字，由密文，由密文字構成密文流輸出。即字構成密文流輸出。即 設明文流為：設明文流為：M=m1 m2mi 密鑰流為：密鑰流為：K=k1 k2ki 則加密為：則加密為：C=c1 c2ci=Ek

7、1(m1)Ek2(m2)Eki(mi) 解密為：解密為：M=m1 m2mi=Dk1(c1)Dk2(c2)Dki(ci)流密碼通信模式框圖流密碼通信模式框圖加密算法加密算法E密文密文ci=Ek(mi)解密算法解密算法D明文明文mi=Dk(ci)明文明文mi密鑰密鑰ki密鑰密鑰ki流密碼的原理流密碼的原理例例 設明文、密鑰、密文都是設明文、密鑰、密文都是F2上的二元數(shù)字序列，明文上的二元數(shù)字序列，明文m=m1m2，密鑰為，密鑰為k=k1k2，若加密變換與解密變換都是，若加密變換與解密變換都是F2中的模中的模2加法，試寫出加密過程與加法，試寫出加密過程與解密過程。解密過程。 解解 經加密變換得密文：

8、經加密變換得密文： C = Ek (m) = Ek1(m1)Ek2(m2) = (k1+m1) (k2+m2) 經解密變換得：經解密變換得： Dk (C) = Dk (k1+m1)(k2+m2) = (k1+k1+m1)(k2+k2+m2) 由于由于kiF2，則，則 ki+ki=0，i=1,2,，故，故 Dk (C)= m1m2 = m 。 v 密文密文C 可由明文可由明文m與密鑰與密鑰k進行進行模模2加加獲得。因此要用該密碼系統(tǒng)通信就要獲得。因此要用該密碼系統(tǒng)通信就要求每發(fā)送一條消息都要產生一個新的密鑰并在一個安全的信道上傳送，習求每發(fā)送一條消息都要產生一個新的密鑰并在一個安全的信道上傳送，

9、習慣上人們稱這種通信系統(tǒng)為慣上人們稱這種通信系統(tǒng)為“一次一密系統(tǒng)一次一密系統(tǒng)”。流密碼的時變性流密碼的時變性-隨時間而變化隨時間而變化 流流密碼采用了類似于一次一密的思想，但加密各明文字的密鑰密碼采用了類似于一次一密的思想，但加密各明文字的密鑰字不是獨立隨機選取的，而是由一個共同的較短的主密鑰按一個算字不是獨立隨機選取的，而是由一個共同的較短的主密鑰按一個算法產生的。因此，它不具有一次一密的無條件安全性，但增加了實法產生的。因此，它不具有一次一密的無條件安全性，但增加了實用性，只要算法設計得當，其安全性可以滿足實際應用的需要。用性，只要算法設計得當，其安全性可以滿足實際應用的需要。 密密鑰流中

10、的元素的產生由鑰流中的元素的產生由 i 時刻的流密碼內部狀態(tài)（記作時刻的流密碼內部狀態(tài)（記作 ）和種子密鑰（記作和種子密鑰（記作k）決定）決定 ，即，即 ；加密變換；加密變換 與解與解密變換密變換 也和也和 i 時刻的流密碼內部狀態(tài)有關。時刻的流密碼內部狀態(tài)有關。 i),(iikfkikEikD流密碼分類流密碼分類v 用狀態(tài)轉移函數(shù)用狀態(tài)轉移函數(shù) 描述流密碼加密器中存儲器的狀態(tài)隨時間變化描述流密碼加密器中存儲器的狀態(tài)隨時間變化的過程。的過程。 同步流密碼同步流密碼 ：如果某個流密碼中的狀態(tài)轉移函數(shù)：如果某個流密碼中的狀態(tài)轉移函數(shù) 不依賴被不依賴被輸入加密器存儲器的明文，即密鑰流的生成獨立于明文

11、流和密輸入加密器存儲器的明文，即密鑰流的生成獨立于明文流和密文流的流密碼稱為同步流密碼。文流的流密碼稱為同步流密碼。使用最廣泛。使用最廣泛。自同步流密碼自同步流密碼也叫異步流密碼也叫異步流密碼 ：狀態(tài)轉移函數(shù)：狀態(tài)轉移函數(shù) 與輸入明文與輸入明文有關，即其中密鑰流的產生并不是獨立于明文流和密文流的。有關，即其中密鑰流的產生并不是獨立于明文流和密文流的。通常第通常第i個密鑰字的產生不僅與主密鑰有關，而且與前面已經產個密鑰字的產生不僅與主密鑰有關，而且與前面已經產生的若干個密文字（與明文字）有關。生的若干個密文字（與明文字）有關。sfsfsf加密算法加密算法E密鑰流密鑰流發(fā)生器發(fā)生器解密算法解密算法

12、D密鑰流密鑰流發(fā)生器發(fā)生器安全通道安全通道密鑰密鑰 k密文流密文流 c i密鑰流密鑰流 k i密鑰流密鑰流 k i明文流明文流m i明文流明文流m i圖圖1 同步流密碼模型同步流密碼模型內部狀態(tài)內部狀態(tài)輸出函數(shù)輸出函數(shù)內部狀態(tài)內部狀態(tài)輸出函數(shù)輸出函數(shù)密鑰發(fā)生器密鑰發(fā)生器密鑰發(fā)生器密鑰發(fā)生器明文流明文流 m i密文流密文流 c i明文流明文流 m i種子種子 k種子種子 kkk圖圖2 自同步流密碼模型自同步流密碼模型同步流密碼同步流密碼中，消息的發(fā)送者和接收者必須同步才能做到正確中，消息的發(fā)送者和接收者必須同步才能做到正確地加密解密，即雙方使用相同的密鑰，并用其對同一位置進行地加密解密，即雙方使

13、用相同的密鑰，并用其對同一位置進行操作。一旦由于密文字符在傳輸過程中被插入或刪除而破壞了操作。一旦由于密文字符在傳輸過程中被插入或刪除而破壞了這種同步性，那么解密工作將失敗。否則，需要在密碼系統(tǒng)中這種同步性，那么解密工作將失敗。否則，需要在密碼系統(tǒng)中采用能夠建立密鑰流同步的輔助性方法。采用能夠建立密鑰流同步的輔助性方法。分解后的同步流密碼分解后的同步流密碼密鑰流生成器密鑰流生成器v密鑰流生成器設計中，在考慮安全性要求的前提下還應考慮密鑰流生成器設計中，在考慮安全性要求的前提下還應考慮以下兩個因素：以下兩個因素： 密鑰密鑰k易于分配、保管、易于分配、保管、更換更換簡單；簡單；易于實現(xiàn)，快速易于實

14、現(xiàn)，快速。v目前密鑰流生成器大都是基于移位寄存器的。因為移位寄存目前密鑰流生成器大都是基于移位寄存器的。因為移位寄存器結構簡單，易于實現(xiàn)且運行速度快。這種基于移位寄存器器結構簡單，易于實現(xiàn)且運行速度快。這種基于移位寄存器的密鑰流序列稱為移位寄存器序列。的密鑰流序列稱為移位寄存器序列。密鑰流生成器密鑰流生成器v一個反饋移位寄存器由兩部分組成：移位寄存器和反饋函數(shù)一個反饋移位寄存器由兩部分組成：移位寄存器和反饋函數(shù), , 構構成一個成一個密鑰流生成器密鑰流生成器。 每次輸出一位，移位寄存器中所有位都右每次輸出一位，移位寄存器中所有位都右移一位，新的最左端的位根據(jù)寄存器中其它位計算得到。移位寄移一位

15、，新的最左端的位根據(jù)寄存器中其它位計算得到。移位寄存器輸出的一位常常是最低有效位。存器輸出的一位常常是最低有效位。v移位寄存器的周期是指輸出序列從開始到重復時的長度。移位寄存器的周期是指輸出序列從開始到重復時的長度。v這種方法通過一個種子（有限長）產生具有足夠長周期的、隨機這種方法通過一個種子（有限長）產生具有足夠長周期的、隨機性良好的序列。只要生成方法和種子都相同，就會產生完全相同性良好的序列。只要生成方法和種子都相同，就會產生完全相同的密鑰流。的密鑰流。反饋函數(shù)反饋函數(shù) 0,11jacaninjinj若若 ，則該，則該LFSR生成的序列為周期序列。生成的序列為周期序列。 0nc又稱為又稱為

16、n階線性遞歸關系階線性遞歸關系密鑰流生成器密鑰流生成器v最簡單的反饋移位寄存器是線性移位寄存器（最簡單的反饋移位寄存器是線性移位寄存器（LFSR），反），反饋函數(shù)是寄存器中某些位的簡單異或。如教材饋函數(shù)是寄存器中某些位的簡單異或。如教材P64圖圖4.5。v異或異或(XOR)運算，異或密文和相同的密鑰流就可以完成解密運算，異或密文和相同的密鑰流就可以完成解密操作。操作。v流密碼基于流密碼基于XOR運算具有下列屬性：如果運算具有下列屬性：如果B=A K，那么，那么A=B K。vn 級移位寄存器級移位寄存器 （見下圖）（見下圖）開始時，設第開始時，設第1級內容是級內容是 an-1，第，第2級內容是級

17、內容是 an-2 , , 第第n 級內容是級內容是 a0，則，則稱這個寄存器的初始狀態(tài)是稱這個寄存器的初始狀態(tài)是 (a0, a1, , an-1)。當加上一個脈沖時，每個寄存器的內容移給下一級，第當加上一個脈沖時，每個寄存器的內容移給下一級，第 n 級內容輸出，同級內容輸出，同時將各級內容送給運算器時將各級內容送給運算器 f (x0, x1, , xn-1) ，并將運算器的結果，并將運算器的結果 an= f (a0 , a1 , , an-1) 反饋到第一級去。這樣這個移位寄存器的狀態(tài)就是反饋到第一級去。這樣這個移位寄存器的狀態(tài)就是 (a1 , a2 , , an)，而輸出是，而輸出是a0 。

18、不斷地加脈沖，上述不斷地加脈沖，上述 n 級移位寄存器的輸出就是一個二元級移位寄存器的輸出就是一個二元(或或q元元)序列：序列： a0 , a1, a2 , 寄存器寄存器 1寄存器寄存器 2寄存器寄存器 3寄存器寄存器 nf (x0, x1, , xn-1)密鑰流生成器密鑰流生成器v移位寄存器產生的序列都是周期序列，周期都不大于移位寄存器產生的序列都是周期序列，周期都不大于2n。 例例 右圖是一個右圖是一個4級線性移位寄存器。給定初狀態(tài)級線性移位寄存器。給定初狀態(tài) (0001) ， 求該移位寄存器產生的周期序列。求該移位寄存器產生的周期序列。 解解 易見易見 f (x0，x1，x2，x3) =

19、 x0 + x1， 因此對因此對 k4 有有 ak = ak-3+ ak-4 從而該從而該4級移位寄存器產生的序列是周期級移位寄存器產生的序列是周期15的序列：的序列： 000100110101111 線性移存器序列的最長周期為線性移存器序列的最長周期為2n1v由上例知，移位寄存器由上例知，移位寄存器(簡記簡記SR，Shifted Register)可由短的序列生成可由短的序列生成具有一定規(guī)律的長序列。這種序列便可以作為密鑰流序列，但抗攻擊具有一定規(guī)律的長序列。這種序列便可以作為密鑰流序列，但抗攻擊能力較差。能力較差。+密鑰流生成器密鑰流生成器狀態(tài)轉移和相應輸出狀態(tài)轉移和相應輸出 時刻時刻 狀

20、狀 態(tài)態(tài) 輸輸 出出 3 2 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 0 1 0 0 0 3 0 0 1 0 0 4 1 0 0 1 1 5 1 1 0 0 0 6 0 1 1 0 0 7 1 0 1 1 1 8 0 1 0 1 1 9 1 0 1 0 0 10 1 1 0 1 1 11 1 1 1 0 0 12 1 1 1 1 1 13 0 1 1 1 1 14 0 0 1 1 1 15 0 0 0 1 1 多項式多項式v以以LFSR的反饋系數(shù)所決定的多項式的反饋系數(shù)所決定的多項式 又稱又稱反饋多項式反饋多項式、連接多項式連接多項式。式中，式中，c0=cn=1v互反多

21、項式互反多項式 稱作是稱作是LFSR的的特征多項式特征多項式。cn 0稱之為非奇異稱之為非奇異LFSR。 njjjnnnnxcxcxcxcxccxf0112210.)(nnnnncxcxcxcxfxxfxc1110*.)1()()(v 收縮密鑰流生成器（見右圖）收縮密鑰流生成器（見右圖） 通常的密鑰流生成器都是由若干個移位寄存器并聯(lián)，并且與特殊的電子通常的密鑰流生成器都是由若干個移位寄存器并聯(lián)，并且與特殊的電子電路組合而成。電路組合而成。 上圖為由兩個移位寄存器構成的上圖為由兩個移位寄存器構成的收縮密鑰流生成器收縮密鑰流生成器，通過，通過 SR1 的輸出選的輸出選擇擇 SR2 的輸出來生成密鑰

22、流，其工作模式如下：的輸出來生成密鑰流，其工作模式如下：輸入參數(shù)：兩個移位寄存器的級數(shù)及反饋函數(shù)輸入參數(shù)：兩個移位寄存器的級數(shù)及反饋函數(shù)密鑰：兩個移位寄存器的初始狀態(tài)密鑰：兩個移位寄存器的初始狀態(tài) (1) 移位移位SR1 并產生并產生 yi(1) ；同時移位；同時移位SR2 并產生并產生 yi(2) ； (2) 如果如果 yi(1) =1，則，則輸出輸出密鑰元素密鑰元素ki = yi(2) ； 如果如果 yi(1) =0，則，則刪去刪去 yi(2)，i =1, 2, ，不輸出不輸出。由此收縮生成器產生的密鑰流為由此收縮生成器產生的密鑰流為ki | i1。SR 1SR 2yi (1)輸出輸出k

23、kiyi (2)密鑰流生成器密鑰流生成器流密碼對密鑰流的要求流密碼對密鑰流的要求v沒有絕對不可破的密碼，比如窮搜索總能破譯，只是破譯所沒有絕對不可破的密碼，比如窮搜索總能破譯，只是破譯所需時間是否超過信息的有效期以及破譯所需代價是否值得。需時間是否超過信息的有效期以及破譯所需代價是否值得。v若一個加密算法沒有比窮搜索更好的破譯方法，則被認為是若一個加密算法沒有比窮搜索更好的破譯方法，則被認為是不可破的。不可破的。v實際使用的密鑰流序列（簡稱密鑰）都是按一定算法生成的，實際使用的密鑰流序列（簡稱密鑰）都是按一定算法生成的，因而不可能是完全隨機的，所以也就不可能是完善保密系統(tǒng)。因而不可能是完全隨機

24、的，所以也就不可能是完善保密系統(tǒng)。為了盡可能提高系統(tǒng)的安全強度，就必須要求所為了盡可能提高系統(tǒng)的安全強度，就必須要求所產生的密鑰產生的密鑰流序列盡可能具有隨機序列的某些特征流序列盡可能具有隨機序列的某些特征。如極大的周期、良。如極大的周期、良好的統(tǒng)計特性。好的統(tǒng)計特性。3.2 分組密碼分組密碼其他分組密碼其他分組密碼數(shù)據(jù)加密標準數(shù)據(jù)加密標準 DESFeistel密碼結構密碼結構分組密碼的設計原則分組密碼的設計原則分組密碼的原理分組密碼的原理分組密碼的典型攻擊方法分組密碼的典型攻擊方法1.分組密碼的原理分組密碼的原理 v密文中的每位數(shù)字不僅僅與某時刻輸入的明文數(shù)字有關，而密文中的每位數(shù)字不僅僅與

25、某時刻輸入的明文數(shù)字有關，而是與該明文中一定組長的明文數(shù)字有關。是與該明文中一定組長的明文數(shù)字有關。分組密碼將明文按分組密碼將明文按一定的位長分組，輸出是固定長度的密文。一定的位長分組，輸出是固定長度的密文。 加密算法加密算法解密算法解密算法明文明文x=(x1, x2, )密文密文y=(y1, y2, , yn )明文明文x=(x1, x2, )密鑰密鑰k=(k1, k2, )密鑰密鑰k=(k1, k2, )分組密碼的基本模型分組密碼的基本模型 分組密碼的長度分組密碼的長度明文為分組長度為明文為分組長度為m的序列，密文為分組長度為的序列，密文為分組長度為n的序列：的序列： nm，稱其為有數(shù)據(jù)擴

26、展的分組密碼；，稱其為有數(shù)據(jù)擴展的分組密碼；nm，稱其為有數(shù)據(jù)壓縮的分組密碼；，稱其為有數(shù)據(jù)壓縮的分組密碼；n=m，稱其為無數(shù)據(jù)擴展與壓縮的，稱其為無數(shù)據(jù)擴展與壓縮的分組密碼。分組密碼。我們一般所說的分組密碼為我們一般所說的分組密碼為無數(shù)據(jù)擴展與壓縮的分組密碼無數(shù)據(jù)擴展與壓縮的分組密碼。 典型的分組是典型的分組是64位或位或128位位分組密碼的特點分組密碼的特點v主要主要優(yōu)點優(yōu)點：易于標準化；易于標準化；易于實現(xiàn)同步。易于實現(xiàn)同步。 v主要主要缺點缺點：不善于隱藏明文的數(shù)據(jù)模式、對于重放、插入、刪除等不善于隱藏明文的數(shù)據(jù)模式、對于重放、插入、刪除等攻擊方式的抵御能力不強。攻擊方式的抵御能力不強

27、。 分組密碼的數(shù)學表示分組密碼的數(shù)學表示v記記明文空間和密文空間為明文空間和密文空間為 （明文與密文分組的長度均為（明文與密文分組的長度均為m），密鑰空間為），密鑰空間為 （ 是是 的子集的子集，r為密鑰長度）：為密鑰長度）：v密鑰密鑰k下的加密函數(shù)為下的加密函數(shù)為 ，m表示待加密的信息，表示待加密的信息，k為密為密鑰，則可將該映射記為鑰，則可將該映射記為 ，這個映射應滿，這個映射應滿足：足： ， 是是 的的一個置換；一個置換； v密鑰密鑰k下的解密函數(shù)記為下的解密函數(shù)記為 ，它是，它是 的的逆。逆。 mF2kSkSrF2),(kE mkmFSFE22:kSk ),(kEmmFF22到),(k

28、D ),(kE 2.分組密碼的分組密碼的設計原則設計原則安全性安全性角度：角度：v“混亂原則混亂原則”：為了避免密碼分析者利用明文與密文之間的：為了避免密碼分析者利用明文與密文之間的依賴關系進行破譯，密碼的設計應該保證這種依賴關系足夠依賴關系進行破譯，密碼的設計應該保證這種依賴關系足夠復雜。復雜。 v“擴散原則擴散原則” ” ：為避免密碼分析者對密鑰逐段破譯，密碼的：為避免密碼分析者對密鑰逐段破譯，密碼的設計應該保證密鑰的每位數(shù)字能夠影響密文中的多位數(shù)字設計應該保證密鑰的每位數(shù)字能夠影響密文中的多位數(shù)字 ；同時，為了避免避免密碼分析者利用明文的統(tǒng)計特性，密碼同時，為了避免避免密碼分析者利用明文

29、的統(tǒng)計特性，密碼的設計應該保證明文的每位數(shù)字能夠影響密文中的多位數(shù)字，的設計應該保證明文的每位數(shù)字能夠影響密文中的多位數(shù)字，從而隱藏明文的統(tǒng)計特性。從而隱藏明文的統(tǒng)計特性。 2.分組密碼的設計原則分組密碼的設計原則可實現(xiàn)性可實現(xiàn)性角度：角度：v應該具有標準的組件結構應該具有標準的組件結構 （子模塊），以適應超大規(guī)模集（子模塊），以適應超大規(guī)模集成電路的實現(xiàn)。成電路的實現(xiàn)。v分組密碼的運算能在子模塊上通過簡單的運算進行。分組密碼的運算能在子模塊上通過簡單的運算進行。 3.3 Feistel密碼結構密碼結構 加密加密: Li = Ri-1 Ri = Li-1 F(Ri-1,Ki)解密解密: Ri-

30、1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki)Feistel結構依賴參數(shù)和特征結構依賴參數(shù)和特征v分組長度分組長度：分組長度越長意味著安全性越高（其他條件不：分組長度越長意味著安全性越高（其他條件不變），但是會降低加解密的速度。一般變），但是會降低加解密的速度。一般64位的分組長度。位的分組長度。v密鑰長度密鑰長度：密鑰較長意味著安全性較高，但會降低加解密的：密鑰較長意味著安全性較高，但會降低加解密的速度。一般需要速度。一般需要128位密鑰，位密鑰，64位密鑰通常不夠。位密鑰通常不夠。v迭代輪數(shù)迭代輪數(shù)： Feistel密碼的本質在于單輪不能提供足夠的安全密

31、碼的本質在于單輪不能提供足夠的安全性，多輪可取得很高安全性。迭代輪數(shù)的典型值為性，多輪可取得很高安全性。迭代輪數(shù)的典型值為16。v子密鑰產生算法子密鑰產生算法：子密鑰越復雜，密碼分析攻擊越困難。：子密鑰越復雜，密碼分析攻擊越困難。v輪函數(shù)輪函數(shù)：輪函數(shù)越復雜，抗攻擊的能力就越強。：輪函數(shù)越復雜，抗攻擊的能力就越強。3.4 數(shù)據(jù)加密標準數(shù)據(jù)加密標準 DES （ Data Encryption Standard ）vDES（Data Encryption Standard）算法于）算法于1977年得到美國政年得到美國政府的正式許可，是一種用府的正式許可，是一種用56位密鑰來加密位密鑰來加密64位數(shù)

32、據(jù)的方法，位數(shù)據(jù)的方法，其密文的長度也為其密文的長度也為64位。位。v國內隨著三金工程尤其是金卡工程的啟動，國內隨著三金工程尤其是金卡工程的啟動，DES算法在算法在ATM、磁卡及智能卡（磁卡及智能卡（IC卡）、加油站、高速公路收費站等領域被卡）、加油站、高速公路收費站等領域被廣泛應用，以此來實現(xiàn)關鍵數(shù)據(jù)的保密。如信用卡持卡人的廣泛應用，以此來實現(xiàn)關鍵數(shù)據(jù)的保密。如信用卡持卡人的PIN的加密傳輸，的加密傳輸，IC卡與卡與POS間的雙向認證、金融交易數(shù)據(jù)包間的雙向認證、金融交易數(shù)據(jù)包的的MAC校驗等，均用到校驗等，均用到DES算法。算法。vDES (Data Encryption Standard

33、) 是由是由IBM公司在公司在20世紀世紀70年年代研制的，經過政府的加密標準篩選后，于代研制的，經過政府的加密標準篩選后，于1976年年11月被美月被美國政府采用，隨后被美國國家標準局和美國國家標準協(xié)會國政府采用，隨后被美國國家標準局和美國國家標準協(xié)會(ANSI)所認可。所認可。 vDES算法具有以下特點：算法具有以下特點： （1）DES算法是分組加密算法：以算法是分組加密算法：以64位為分組。位為分組。 （2）DES算法是對稱算法：加密和解密用同一密鑰。算法是對稱算法：加密和解密用同一密鑰。 （3）DES算法的有效密鑰長度為算法的有效密鑰長度為56位。位。 （4）換位和置換。）換位和置換。

34、 （5）易于實現(xiàn)。）易于實現(xiàn)。1. DES的產生背景的產生背景DES的生命期的生命期 vNBS最終采納了最終采納了 IBM 的的 LUCIFER 方案，于方案，于 1975 年公開發(fā)表。年公開發(fā)表。v1977 年正式頒布為數(shù)據(jù)加密標準（年正式頒布為數(shù)據(jù)加密標準（DES - Data Encryption Standard）。）。v1979 年，美國銀行協(xié)會批準使用年，美國銀行協(xié)會批準使用 DES。v1980 年，年，DES 成為美國標準化協(xié)會成為美國標準化協(xié)會 (ANSI) 標準。標準。v1984 年，年，ISO 開始在開始在 DES 基礎上制定數(shù)據(jù)加密的國際標準?；A上制定數(shù)據(jù)加密的國際標準

35、。v美國國家安全局美國國家安全局NSA每隔年對該算法進行評估每隔年對該算法進行評估 ，1994年，決定年，決定1998年年12月之后不再使用月之后不再使用DES 。v現(xiàn)已經確定了選用現(xiàn)已經確定了選用Rijndael算法作為高級加密算法算法作為高級加密算法AES。 2. DES算法要點算法要點 v 算法設計中采用的基本變換和操作：算法設計中采用的基本變換和操作：置換置換（P）：重新排列輸入的比特位置。）：重新排列輸入的比特位置。交換交換（SW）：將輸入的左右兩部分的比特進行互換。）：將輸入的左右兩部分的比特進行互換。循環(huán)移位循環(huán)移位：將輸入中的比特進行循環(huán)移位，作為輸出。：將輸入中的比特進行循環(huán)

36、移位，作為輸出。一個復雜變換一個復雜變換（ fK ）通常是一個多階段的乘積變換；通常是一個多階段的乘積變換；與密鑰與密鑰 Key 相關；相關；必須是非線性變換；必須是非線性變換；實現(xiàn)對密碼分析的擾亂；實現(xiàn)對密碼分析的擾亂；是密碼設計安全性的關鍵。是密碼設計安全性的關鍵。3. DES的加密過程的加密過程第一步：第一步：初始置換初始置換IP。對于給定的明文對于給定的明文m，通過初始置換，通過初始置換IP獲得獲得 ，并將，并將 分為兩部分，分為兩部分，前面前面32位記為位記為 ，后面，后面32位記為位記為 ，即，即第二步：第二步：乘積變換乘積變換（ 16輪）。輪）。在每一輪中依據(jù)下列方法計算在每一輪

37、中依據(jù)下列方法計算 （ ）（）（16輪中的計算方法相輪中的計算方法相同）：同）： ， 其中，其中， 為第為第i輪使用的子密鑰，各輪使用的子密鑰，各 均為均為 的一個置換選擇，所有的一個置換選擇，所有 構成密鑰方案。函數(shù)構成密鑰方案。函數(shù) 中的變量中的變量 為為32位字符串，位字符串， 為為48位字位字符串，符串， 函數(shù)函數(shù) 輸出的結果為輸出的結果為32位字符串。位字符串。 0m0m0L0R000)(RLmIPmiiRL161 i1iiRL),(11iiiiKRfLRiKiKKiK),(21XXf1X2X),(21XXfDES的加密過程的加密過程第三步：初始置換第三步：初始置換 的逆置換的逆置換

38、 。應用初始置換應用初始置換 的逆置換的逆置換 對對 進行置換，得進行置換，得到密文到密文c，即，即 。IP1IP1IP1616RL)(16161RLIPcIPLi-1Ri-1LiRikif+一輪一輪DES加密過程加密過程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-boxescompressLR282828282828483248

39、32323232OneRound ofDES4832KiP box（1）IP置換表和置換表和IP-1逆置換表逆置換表v輸入的輸入的64位數(shù)據(jù)按位數(shù)據(jù)按IP表置換進行重新組合，并把輸出分為表置換進行重新組合，并把輸出分為L0和和R0兩部分，兩部分，每部分各每部分各32位，其位，其IP表置換如表表置換如表3-1所示所示表表3-1 IP置換表置換表5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315741 初始置換初始

40、置換IP和和IP-12014MM1420MMIPIP-1將輸入的將輸入的64位明文的第位明文的第58位換到第位換到第1位，第位，第50位換到第位換到第2位，依位，依此類推，最后一位是原來的第此類推，最后一位是原來的第7位。位。L0和和R0則是換位輸出后的則是換位輸出后的兩部分，兩部分，L0是輸出的左是輸出的左32位，位，R0是右是右32位。比如：置換前的輸位。比如：置換前的輸入值為入值為D1D2D3D64，則經過初始置換后的結果為：，則經過初始置換后的結果為：L0=D58D50D8，R0=D57D49D7。經過經過16次迭代運算后。得到次迭代運算后。得到L16和和R16，將此作為輸入進行逆置，

41、將此作為輸入進行逆置換，即得到密文輸出。換，即得到密文輸出。表表3-2 IP-1逆置換表逆置換表逆置換正好是初始置的逆運算，例如，第逆置換正好是初始置的逆運算，例如，第1位經過初始置換后，位經過初始置換后，處于第處于第40位，而通過逆置換位，而通過逆置換IP-1，又將第，又將第40位換回到第位換回到第1位，其逆位，其逆置換置換IP-1規(guī)則表如規(guī)則表如3-2所示。所示。4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917

42、5725(2) 函數(shù)函數(shù) f的內部流程的內部流程Ri-1（32bit）ES1S2S8PKi（48bit）48bit32bitf( Ri-1,ki ) (32bit)v E變換的算法是從變換的算法是從Ri-1的的32位中選取某些位，構成位中選取某些位，構成48位，即位，即E將將32位擴展為位擴展為48位。變換規(guī)則根據(jù)位。變換規(guī)則根據(jù)E位選擇表，如表位選擇表，如表3-3所示。所示。表表3-3 E位選擇表位選擇表3212345456789891011121312131415161716171819202120212223242524252627282928293031321v每個每個S盒輸出盒輸出4

43、位，共位，共32位，位，S盒的工作原理將在第盒的工作原理將在第4步介紹。步介紹。S盒的輸出作為盒的輸出作為P變換的輸入，變換的輸入，P的功能是對輸入進行置換，的功能是對輸入進行置換，P換位表如表換位表如表3-4所示。所示。vKi是由密鑰產生的是由密鑰產生的48位比特串，具體的算法是：將位比特串，具體的算法是：將E的選位結的選位結果與果與Ki作異或操作，得到一個作異或操作，得到一個48位輸出。分成位輸出。分成8組，每組組，每組6位，位，作為作為8個個S盒的輸入。盒的輸入。表表3-4 P換位表如表換位表如表1672021291228171152326518311028241432273919133

44、062211425（3）DES的密鑰的密鑰Ki計算計算vDES在各輪中所用的密鑰均為由初始密鑰（即種子密鑰）導在各輪中所用的密鑰均為由初始密鑰（即種子密鑰）導出的出的48位密鑰。位密鑰。 v初始密鑰為初始密鑰為64位，其中第位，其中第8、16、24、32、40、48、56、64位均為校驗位。位均為校驗位。 v如此設置校驗位的目的是使每如此設置校驗位的目的是使每8個字節(jié)所含的字符個字節(jié)所含的字符“1”個數(shù)個數(shù)為奇數(shù)，以便能夠檢測出每個字節(jié)中的錯誤。為奇數(shù)，以便能夠檢測出每個字節(jié)中的錯誤。子密鑰子密鑰ki產生流程圖產生流程圖PC-1C0D0LS1LS1C1D1LS2LS2C2D2LS16LS16C

45、16D16PC-2PC-2PC-2K(64bit)K1(48bit)K2(48bit)K16(48bit)假設初始密鑰為假設初始密鑰為K，長度為長度為64位，但是位，但是其中第其中第8，16，24，32，40，48，64作作奇偶校驗位，實際奇偶校驗位，實際密鑰長度為密鑰長度為56位。位。K下標下標i的取值范圍的取值范圍是是1到到16，用，用16輪來輪來構造。構造過程如構造。構造過程如圖所示。圖所示。50子密鑰的產生子密鑰的產生產生子密鑰產生子密鑰Ki具體描述為：具體描述為：v首先，對于給定的密鑰首先，對于給定的密鑰K，應用，應用PC1變換進行選位，選定后變換進行選位，選定后的結果是的結果是56

46、位，設其前位，設其前28位為位為C0，后，后28位為位為D0。PC1選位如選位如表表3-5所示。所示。表表 3-5 PC-1選位表選位表57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124v 第第1輪：對輪：對C0作左移作左移LS1得到得到C1，對，對D0作左移作左移LS1得到得到D1，對，對C1D1應用應用PC2進行選位，得到進行選位，得到K1。其中。其中LS1是左移的位數(shù)，如表是左移的位數(shù)，如表3-6所示。所示。v 第第2輪：對輪：對C

47、1和和D1作左移作左移LS2得到得到C2和和D2，進一步對，進一步對C2D2應用應用PC2進行選進行選位，得到位，得到K2。如此繼續(xù)，分別得到。如此繼續(xù)，分別得到K3，K4，K16。表表3-6 LS移位表移位表輪輪 數(shù)數(shù)循環(huán)左移位循環(huán)左移位數(shù)數(shù)輪輪 數(shù)數(shù)循環(huán)左移位循環(huán)左移位數(shù)數(shù)輪輪 數(shù)數(shù)循環(huán)左移位循環(huán)左移位數(shù)數(shù)輪輪 數(shù)數(shù)循環(huán)左移位循環(huán)左移位數(shù)數(shù)115291132216210214232721121524282122161表表 3-7 PC-2選位表選位表14171124153281562110231912426816727201324152313747553040514533484449395

48、63453464250362932（4）S盒的工作原理盒的工作原理vS盒以盒以6位作為輸入，而以位作為輸入，而以4位作為輸出，現(xiàn)在以位作為輸出，現(xiàn)在以S1為例說明為例說明其過程。其過程。v假設輸入為假設輸入為A=a1a2a3a4a5a6，則，則a2a3a4a5所代表的數(shù)是所代表的數(shù)是0到到15之之間的一個數(shù)，記為：間的一個數(shù)，記為：k=a2a3a4a5；由；由a1a6所代表的數(shù)是所代表的數(shù)是0到到3間間的一個數(shù)，記為的一個數(shù)，記為h=a1a6。在。在S1的的h行，行，k列找到一個數(shù)列找到一個數(shù)B，B在在0到到15之間，它可以用之間，它可以用4位二進制表示，為位二進制表示，為B=b1b2b3b4

49、，這就是，這就是S1的輸出。的輸出。vS盒由盒由8張數(shù)據(jù)表組成，如教材張數(shù)據(jù)表組成，如教材P84-85所示。所示。S- -盒的構造盒的構造 DES加密范例加密范例v已知明文已知明文m=computer，密鑰，密鑰k=program。 m=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010 k=01110000 01110010 01101111 01100111 01110010 01100001 01101101v這里這里k只有只有56bit，必須插入第，必須插入第8，16，24，32，40，48，5

50、6，64這這8個奇偶校驗位成為個奇偶校驗位成為64比特。比特。 k= 0111000* 0011100* 1001101* 1110110* 0111011* 1001001* 1000010* 1101101*vm經過經過IP置換后得置換后得 L0 =11111111 10111000 01110110 01010111 R0 =00000000 11111111 00000110 10000011v 密鑰密鑰k經經PC-1置換得置換得 C0 =11101100 10011001 00011011 1011 D0 =10110100 01011000 10001110 0111vC0和和 D

51、0各循環(huán)左移一位后通過各循環(huán)左移一位后通過PC-2得到得到48bit的子密鑰的子密鑰k1。 C1=11011001 00110010 00110111 0111 D1 =01101000 10110001 00011100 1111 k1 =00111101 10001111 11001101 00110111 00111111 01001000DES加密范例加密范例vR0經過經過E變換后擴展為變換后擴展為48bit。 10000000 00010111 11111110 10000000 11010100 00000110v再和再和k1 作異或運算，得作異或運算，得 10111101 100

52、11000 00110011 10110111 11101011 01001110v分成分成8組組 101111 011001 100000 110011 101101 111110 101101 001110v經過經過S盒后輸出盒后輸出32bit 0111 0110 1101 0100 0010 0110 1010 0001v再經過再經過P置換得置換得 01000100 00100001 10011111 1001101101(,)f R kDES加密范例加密范例v所以第一輪迭代的結果為所以第一輪迭代的結果為v =10111011 10011001 11101001 1100110010LR

53、1001(,)RLf R kDES加密范例加密范例4. DES的解密過程的解密過程v采用與加密相同的算法。采用與加密相同的算法。v以逆序（即以逆序（即 ）使用密鑰。）使用密鑰。11516,KKK 111 216( )( )DEScIP TTTIP c實現(xiàn)實現(xiàn)效果效果不同微處理器上的不同微處理器上的DES軟件實現(xiàn)速度軟件實現(xiàn)速度 處理器處理器處理器速度（處理器速度（MHz）每秒處理的每秒處理的DES分組個數(shù)分組個數(shù)80884.7370680007.69008028661,10068020163,50068030163,90080286255,000680305010,000680402516,0

54、00680404023,000804866643,000雪崩效應雪崩效應v明文或密鑰的微小改變將對密文產生很大的影響是任何算法明文或密鑰的微小改變將對密文產生很大的影響是任何算法所期望的一個好性質。明文或密鑰的某一位發(fā)生變化會導致所期望的一個好性質。明文或密鑰的某一位發(fā)生變化會導致密文的很多位發(fā)生變化。如果相應的改變很小，可能會給分密文的很多位發(fā)生變化。如果相應的改變很小，可能會給分析者提供縮小搜索密鑰或明文空間的渠道。析者提供縮小搜索密鑰或明文空間的渠道。vDES顯示出很強的雪崩效應：如下兩條僅有一位不同的明文：顯示出很強的雪崩效應：如下兩條僅有一位不同的明文：00000000 000000

55、00 00000000 00000000 00000000 00000000 00000000 0000000010000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000密鑰：密鑰：0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010v結果表明僅經過結果表明僅經過3輪迭代后，兩段數(shù)據(jù)有輪迭代后，兩段數(shù)據(jù)有21位不同。全部迭代位不同。全部迭代完成后得到的兩段密文則有完成后得到的兩段密文則有34位不同。位不同。DES的雪崩效應的雪崩效應(a)

56、 明文的變化明文的變化(b)密鑰的變化密鑰的變化輪數(shù)輪數(shù) 改變的位數(shù)改變的位數(shù)輪數(shù)輪數(shù) 改變的位數(shù)改變的位數(shù)0 11 62 213 354 395 346 327 318 29 . . .0 01 22 143 284 325 306 327 358 34 . . . 5. DES的安全性分析的安全性分析 vDES的安全性完全依賴于密鑰，與算法本身沒有關系。的安全性完全依賴于密鑰，與算法本身沒有關系。 v主要研究內容：主要研究內容：密鑰的互補性；密鑰的互補性；弱密鑰與半弱密鑰；弱密鑰與半弱密鑰；密文密文- -明文相關性；明文相關性；密文密文- -密鑰相關性；密鑰相關性；S-S-盒的設計；盒的設

57、計；密鑰搜索。密鑰搜索。 密鑰的互補性密鑰的互補性vDES算法具有互補性，即：若算法具有互補性，即：若 、 是是 的的補、補、 是是 的補，則的補，則 。v使用使用DES算法時不要使用互補的密鑰，否則當密碼算法時不要使用互補的密鑰，否則當密碼攻擊者選擇明文攻擊時，他們僅需試驗一半密鑰。攻擊者選擇明文攻擊時，他們僅需試驗一半密鑰。 )(mDESckccmm)(mDESck弱密鑰弱密鑰v弱密鑰：由密鑰弱密鑰：由密鑰 k 確定的加密函數(shù)與解密函數(shù)相同確定的加密函數(shù)與解密函數(shù)相同 ，即即 。vDES的弱密鑰：的弱密鑰： 如果各輪產生的子密鑰一樣，則加密函數(shù)與如果各輪產生的子密鑰一樣，則加密函數(shù)與解密函

58、數(shù)相同。解密函數(shù)相同。 vDES至少有至少有4個弱密鑰個弱密鑰 ：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe)()(1kkDESDES半弱密鑰半弱密鑰 v半弱密鑰：對于密鑰半弱密鑰：對于密鑰 k ，存在一個不同的密鑰，存在一個不同的密鑰 ，滿，滿足足 。 vDES的半弱密鑰：子密鑰生成過程中只能產生兩個不同的子的半弱密鑰：子密鑰生成過程中只能產生兩個不同的子密鑰或四個不同的子密鑰，互為對合。密鑰或四個不同的子密鑰，互為對合。 vDES至少有至少有12個半弱密鑰。個半弱密鑰。 *k)()(*kkDESDESS-

59、 -盒的設計原則盒的設計原則 S -盒的設計原理沒有公開，一些原則如下：盒的設計原理沒有公開，一些原則如下：v所有所有S-盒的每一行是盒的每一行是0,1,15的一個置換；的一個置換；v所有所有S-盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)；盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)；vS-盒的輸入改變任意一位都會引起輸出中至少兩位發(fā)生變化；盒的輸入改變任意一位都會引起輸出中至少兩位發(fā)生變化；v對于任何輸入對于任何輸入x（6位），位），S(x)與與S(x 001100)至少有兩位不同；至少有兩位不同；v對于任何輸入對于任何輸入x（6位），位），S(x)與與S(x 00ef00)不相等，不相等，e, f取

60、取0或或1；v對于任意一個輸入位保持不變而其他五位變化時，輸出中對于任意一個輸入位保持不變而其他五位變化時，輸出中0和和1的的數(shù)目幾乎相等。數(shù)目幾乎相等。 針對針對DES的攻擊方法的攻擊方法攻擊攻擊DES的方法主要有：的方法主要有：密鑰窮搜索攻擊，密鑰窮搜索攻擊，DES算法總的密鑰量為算法總的密鑰量為 ，1998年使用高級計算機的情況下，破譯年使用高級計算機的情況下，破譯DES只需只需56小時；小時； 差分攻擊；差分攻擊；線性攻擊，較有效的方法；線性攻擊，較有效的方法；相關密鑰攻擊等。相關密鑰攻擊等。DES遭受攻擊的原因只是因為其密鑰過短，而不是因為遭受攻擊的原因只是因為其密鑰過短，而不是因為存在比