1、1第二章第二章 常規加密的經典技術常規加密的經典技術密碼學基本概念常規加密模型隱寫術替代加密和轉置加密簡單的XOR一次一用密碼本 21. 1. 密碼學基本概念密碼學基本概念 發送者和接收者 在信息傳送過程中，主動提供信息的一方稱發送者，得到信息的一方稱接收者。發送者要確保信息安全傳送，使竊聽者不能盜取信息。 31. 1. 密碼學基本概念密碼學基本概念 密碼技術 目的： 使不知道如何解密的黑客不可能由其截獲的亂碼中得到任何有意義的信息； 使黑客不可能偽造任何亂碼型的信息。 密碼學(密碼技術 ) 分類 密碼編碼學：對信息進行編碼實現信息隱蔽 密碼分析學：研究分析破譯密碼41. 1. 密碼學基本概念

2、密碼學基本概念 密碼通信系統模型 非法 侵入者 信源 M 加密器 c=Ek1(m) 解密器 m=Dk2(c) 接收者 密碼分析員 (竊聽者) 密鑰源 K1 密鑰源 K2 搭線信道 (主動攻擊) 搭線信道 (被動攻擊) 密鑰信道 m c m k1 k2 c m 51. 1. 密碼學基本概念密碼學基本概念 被隱蔽的消息稱作明文明文 密碼可將明文變換成另一種隱蔽形式，稱為密文密文。 由明文到密文的變換稱為加密加密。由合法接收者從密文恢復出明文的過程稱為解密解密（或脫密脫密）。 非法接收者試圖從密文分析出明文的過程稱為破譯破譯。 對明文進行加密時采用的一組規則稱為加密算法加密算法。 對密文解密時采用的

3、一組規則稱為解密算法解密算法。 加密算法和解密算法是在一組僅有合法用戶知道的秘密信息，稱為密鑰密鑰的控制下進行的。 加密和解密過程中使用的密鑰分別稱為加密密鑰加密密鑰和解解密密鑰密密鑰。 61. 1. 密碼學基本概念密碼學基本概念 明文消息空間明文消息空間M； 密文消息空間密文消息空間C； 密鑰空間密鑰空間K1和和K2； 加密交換加密交換Ek1：MC，其中其中k1K1； 解密變換解密變換Dk2：CM，其中其中k2K2； 稱總體（稱總體（M，C，K1，K2，Ek1，Dk2）為密碼為密碼系統。對于給定明文消息系統。對于給定明文消息mM，密鑰密鑰k1K1，加密交換將明文加密交換將明文m變換為密文變換

4、為密文c：cf(m,k1)Ek1(m) mM，k1K171. 1. 密碼學基本概念密碼學基本概念 合法接收者，利用其知道的解密密鑰合法接收者，利用其知道的解密密鑰k2對收到對收到的密文進行變換，恢復出明文消息的密文進行變換，恢復出明文消息mDk2(c) mM，k2K2 黑客則利用其選定的變換函數黑客則利用其選定的變換函數h，對截獲的密對截獲的密文文c進行變換，得到的明文是明文空間的某個進行變換，得到的明文是明文空間的某個元素元素mh(c) mM，k2K2一般一般mm。如果如果mm，則黑客破譯成功。則黑客破譯成功。 81. 1. 密碼學基本概念密碼學基本概念 認證，完整性和不許抵賴認證，完整性和

5、不許抵賴 認證：信息接受者應有可能核查信息來源，任何闖認證：信息接受者應有可能核查信息來源，任何闖入者無力裝扮成原有的發送者。入者無力裝扮成原有的發送者。 完整性：信息接收者應有可能驗證信息在傳播中未完整性：信息接收者應有可能驗證信息在傳播中未經修改，闖入者無力用假信息代替合法的原有信息。經修改，闖入者無力用假信息代替合法的原有信息。 不可抵賴：發送者在發送出信息后無法抵賴他所發不可抵賴：發送者在發送出信息后無法抵賴他所發出的信息。出的信息。91. 1. 密碼學基本概念密碼學基本概念 算法和密鑰 密碼算法，稱為加密算法，是用來加密和解密的數學函數。為給明文信息加密，用加密算法函數。為給密文信息

6、解密，用解密算法函數。 如果算法的安全性基于算法工作的保安，這是一個受約算法受約算法。 近代密碼術用密鑰來解決安全性問題。101. 1. 密碼學基本概念密碼學基本概念 算法和密鑰 加密和解密函數表示EK(M)=CDK(C)=M 若加密和解密密鑰相同： DK(EK(M)M 若加密和解密密鑰不同：EK1(M)CDK2(C)=MDK2(EK1(M)=M 111. 1. 密碼學基本概念密碼學基本概念 密碼系統分類 用于將明文轉換為密文操作的類型。所有加密算法基于兩個基本原則：替代，即明文中的每個元素（比特、字母、比特組合或字母組合）被映射為另一個元素；轉置，即在明文中的元素被重排列，對它們的基本要求是

7、不丟失信息（即所有操作都是可逆轉的）。被稱為乘積系統的多數系統涉及多個階段的替代和轉置。 所使用密鑰的數量。如果發送者和接收者雙方使用相同的密鑰，該系統稱為對稱加密、單密鑰加密、秘密密鑰加密或常規加密。如果發送者和接收者各自使用一個不同的密鑰，則該系統稱為非對稱加密、雙密鑰加密或公開密鑰加密。 明文處理的方式。分組加密一次處理一塊元素的輸入，對每個輸入塊產生一個輸出塊。流（序列）加密連續地處理輸入元素，并隨著該過程的進行，一次產生一個元素的輸出。 121. 1. 密碼學基本概念密碼學基本概念 單鑰密碼的特點 是無論加密還是解密都使用同一個密鑰，因此，此密碼體制的安全性就是密鑰的安全。如果密鑰泄

8、露，則此密碼系統便被攻破。最有影響的單鑰密碼是1977年美國國家標準局頒布的DES算法。 優點：安全性高、加解密速度快。 缺點：1)隨著網絡規模的擴大，密鑰的管理成為一個難點；2)無法解決消息確認問題；3)缺乏自動檢測密鑰泄露的能力。 131. 1. 密碼學基本概念密碼學基本概念 雙鑰體制特點 加密密鑰與解密密鑰不同，此時不需要安全信道來傳送密鑰而只需利用本地密鑰發生器產生解密密鑰k2K2。并以此來控制解密操作D。雙鑰密碼是1976年W.Diffie和M.E.Hellman提出的一種新型密碼體制。 優點：由于雙鑰密碼體制的加密和解密不同，且能公開加密密鑰，而僅需保密解密密鑰，所以雙鑰密碼不存在

9、密鑰管理問題。雙鑰密碼還有一個優點是可以擁有數字簽名等新功能。最有名的雙鑰密碼是1977年由Rivest，Shamir和Adleman三人提出的RSA密碼體制。 缺點：雙鑰密碼算法一般比較復雜，加解密速度慢。 141. 1. 密碼學基本概念密碼學基本概念 序列密碼 加密過程是把明文序列與等長的密鑰序列進行逐位模2加。 解密過程則是把密文序列與等長的密鑰序列進行逐位模2加。 安全性：主要依賴于密鑰序列。最著名的序列密碼是“一次一密密碼”，它的密鑰序列是真正的隨機二元序列。 優點：1)處理速度快，實時性好；2)錯誤傳播小；3)不存在串破譯問題；4)適用于軍事、外交等保密信道。 缺點：1)明文擴散性

10、差；2)插入信息的敏感性差；3)需要密鑰同步。 151. 1. 密碼學基本概念密碼學基本概念 分組密碼 加密方式是首先將明文序列以固定長度進行分組，每一組明文用相同的密鑰和加密函數進行運算。為了減少存儲量和提高運算速度，密鑰的長度一般不大，因而加密函數的復雜性成為系統安全的關鍵。分組密碼設計的核心是構造既具有可逆性又有很強的非線性的算法。加密函數重復地使用代替和置換兩種基本的加密變換。 優點：1)明文信息良好的擴散性；2)對插入的敏感性；3)不需要密鑰同步；4)較強的適用性，適宜作為加密標準。 缺點：1)加密速度慢；2)錯誤易擴散和傳播。 161. 1. 密碼學基本概念密碼學基本概念 密碼破譯

11、密碼破譯則是無須取得密鑰而能將密文信息恢復成明文的科學。密碼破譯成功，不僅恢復明文也可得到密鑰。并且發現密碼系統中導致上述結果的弱點。 僅知密文攻擊 已知明文攻擊 選擇明文攻擊 選擇文本（自適應選擇明文攻擊） 選擇密文攻擊 選擇密鑰攻擊 牛皮筋式破譯 171. 1. 密碼學基本概念密碼學基本概念 僅知密文攻擊在這種攻擊中，密碼破譯員有幾個信息的密文，所有的信息使用相同加密算法加密。為將相同密鑰加密的信息解密，密碼破譯員會盡可能多地恢復信息的明文，或者更好地是導出用于加密信息的密鑰。已知：C1=EK(P1)，C2=EK(P2)，Ci=EK(Pi)導出：P1、P2Pi、K或導出從Ci+1=EK(P

12、i+1)得知Pi+1的算法 已知明文攻擊 密碼破譯員不但利用幾個信息的密文，而且有這些信息的明文。導出用于加密信息的密鑰或用相同的密鑰加密任何新的信息的解密算法。已知：P1，C1=EK(P1)，P2，C2=EK(P2)，Pi，Ci=EK(Pi)導出：K或導出從Ci+1=EK(Pi+1)得知Pi+1的算法 181. 1. 密碼學基本概念密碼學基本概念 選擇明文攻擊 密碼破譯員不但利用密文和涉及到的信息的明文，而且能選擇加密的明文。這比已知明文攻擊更強有力，因為密碼破譯員能選擇專用的明文塊加密，可能產生更多關于密鑰的信息。導出用于加密信息的密鑰或用相同的密鑰加密任何新的信息的解密算法。已知：P1，

13、C1=EK(P1)，P2，C2=EK(P2)，Pi，Ci=EK(Pi)其中密碼分析者選擇P1、P2Pi導出：K或導出從Ci+1=EK(Pi+1)得知Pi+1的算法 選擇文本（自適應選擇明文攻擊）這是選擇明文攻擊的一個特例。密碼破譯員不但選擇加密的明文，而且能依據以前加密的結果修改選擇。在選擇明文攻擊中，密碼破譯員可以選擇一大塊明文加密；在自適應選擇明文攻擊中，選擇一個較小的明文塊，然后依據第一次的結果選擇另一塊，等等。 191. 1. 密碼學基本概念密碼學基本概念選擇密文攻擊密碼破譯員能選擇不同的將要解密的密文和已解的明文，將它們放入一個自動解密的分解判別的工具箱中，導出密鑰。已知：C1，P1

14、=DK(C1)，C2，P2=DK(C2)，Ci，Pi=DK(Ci)導出：K這種攻擊主要應用于公開密鑰加密系統。選擇密文攻擊有時對對稱算法一樣有效。選擇密鑰攻擊 這種攻擊并不意味破譯員能選擇密鑰。只不過破譯員對不同密鑰之間的關系有所了解。它較新奇和含混但并不實用。 牛皮筋式破譯 破譯員威脅、寫黑信或折磨某人直至給出密鑰，或用金錢收買，所以也稱購買密鑰攻擊，這已不是科學技術的內容了，但在現實社會中卻也常有奏效。 201. 1. 密碼學基本概念密碼學基本概念攻擊的類型 密碼破譯者己知的東西 僅有密文 加密算法待破譯的密文已知明文 加密算法待破譯的密文由密鑰形成的一個或多個明文密文對 選擇明文 加密算

15、法待破譯的密文由密碼破譯者選擇的明文消息，連同它對應的由其密鑰生成的密文 選擇文本 加密算法待破譯的密文由密碼破譯者選擇的明文消息，連同它對應的由密鑰生成的密文 由密碼破譯者選擇的猜測性的密文，連同它對應的由密鑰生成的已破譯的明文 加密算法待破譯的密文由密碼破譯者選擇的猜測性的密文，連同它對應的由密鑰生成的已破譯的明文 密碼破譯方法小結211. 1. 密碼學基本概念密碼學基本概念 算法安全性算法根據攻破的難易標定了不同的安全程度。如攻破某算法的費用大于加密數據的代價，該算法認為是安全的。如攻破某算法的時間長于數據的保密期，該算法也認為是安全的。同樣如攻破某算法所需的數據量多于密鑰加密的數據量，

16、該算法仍認為是安全的。以上所說的安全并非絕對，因為在密碼破譯中新的攻破機遇頻頻發生，另一方面大部分數據的價值會隨時間流逝而貶低。所以，安全的要點是數據的價值要繼續保持低于攻破安全屏障所花的代價。 221. 1. 密碼學基本概念密碼學基本概念Lars Knudsen按攻破算法難易的遞降順序，分類如下： 全攻破，密碼破譯員找到密鑰K，于是解密DK(C)=M。 全局推導，密碼破譯員找到另一算法A，無須知道K，因為A等價于DK(C)而解密。 局部推導，密碼破譯員找到竊聽來的密文的明文而解密。 信息推導，密碼破譯員得到關于密鑰信息或是有關明文格式的信息。利用這些信息而解密。如果無論破譯員有多少密文，仍無

17、足夠信息能恢復明文，這樣的算法是無條件安全的。事實上只有一次一用的密碼本是不可攻破的。其它所有密碼系統在惟密文攻擊下都是可以攻破的。231. 1. 密碼學基本概念密碼學基本概念加密算法的安全準則： 破譯該密碼的成本超過被加密信息的價值。 破譯該密碼的時間超過該信息有用的生命周期。攻擊復雜性的度量： 數據復雜性，為攻擊所需數據的攻擊量。 處理復雜性，執行攻擊所須的時間，又稱工作因子。 存儲需求，做攻擊所須的存儲量。 241. 1. 密碼學基本概念密碼學基本概念 自然界常用大數物理類似物 數字 到下個冰世紀的時間 14,000（214）年 到太陽銷毀的時間 109（230）年 行星的壽命 109（

18、230）年 宇宙的壽命 （如果宇宙是開放的 ）1011（267）年 到小質量恒星冷卻時間 1016（261）秒 到行星脫離恒星時間 1015（230）年 到所有恒星離開銀河的時間 1019（264）年 到天體軌道因向心輻射而消逝時間 1020（267）年 到黑洞因Hawking過程而消逝時間 1064（2213）年 到所有物質冷卻成零度液體的時間 1065（2216）年 到所有物質衰變成鐵的時間 101026年 到所有物質陷落到黑洞的時間 101076年 251. 1. 密碼學基本概念密碼學基本概念 密鑰長度與安全性評估 密鑰長度（bit） 密鑰數量 每微秒加密1次所需時間 每微秒加密100萬

19、次所需時間 32 232 = 4.3 x 109 231us = 35.8分 2.15微秒 56 256 = 7.2 x 1016 255us =1142年 10.01小時 128 2128 = 3.4 x 1038 2127us = 5.4 x 1024年 5.4 x 1018年 26字符（排列） 26! = 4 x 1026 2 x 1026us = 6.4 x 1012年 6.4 x 106年 262. 2. 常規加密模型常規加密模型 常規加密的簡化模型272. 2. 常規加密模型常規加密模型 常規密碼系統的模型 秘密通道 X X Y X K K 密鑰源 加密算法 消息源 解密算法 目的

20、地 密碼破譯者 282. 2. 隱寫術隱寫術字符標記：印刷或打印的文本字母經選擇用鉛筆重寫。該標記通常不可見，除非該紙以一定的角度對著亮光看。不可見墨水：使用一些物質來書寫，但不留下任何可見痕跡，除非加熱該紙或在該紙上涂上某種化學藥品。扎小孔：在所選的字母上扎小孔，這些小孔通常不可見，除非把該紙放在光的前面。打字機改正帶：用于行間與一根黑帶一同打印，用改正帶打印的結果僅在強光下才可見。格孔密寫卡：將它覆蓋在一張紙上從格孔中寫入密件，然后在紙上余下部分填入其它字句，使它像一般信件。292. 2. 隱寫術隱寫術示例： 情 報 在 雨 傘 中 王先生： 來信收悉，你的盛情真是難以報答。我已在昨天抵達

21、廣州。秋雨連 綿，每天需備傘一把方能上街，苦誒。大約本月中旬我才能返回，屆時 再見。 弟 李明 明文 密文 303. 3. 替代加密和置換加密替代加密和置換加密 替代技術置換技術 轉子機（Rotor Machine） 313. 3. 替代加密和置換加密替代加密和置換加密 替代技術替代技術替代技術是這樣一種技術，其中明文的字母由其他字母或數字或符號所代替 。如果該明文被視為一個比特序列，則替代涉及到用密文比特模式代替明文比特模式。在經典密碼學中，替代加密算法有四種基本類型：簡單替代加密算法或稱單字符加密，明文每一字符被替代成密文中的相應字符。新聞密電就是用這種方法。同音替代加密算法，類似于簡單替

22、代加密算法，但明文中的單一字符能對應密文中的幾個字符。例如“A”可能相應于5、13、25或“B”可能相應于7、19、31或42等等。多元替代加密算法，成塊的字符加密成一組其它字符。如“ABA”相應于“RTQ”，“ABB”相應于“SLL”等等。1.多字母替代加密算法，由多次簡單替代加密組成。例如用5次不同的簡單替代加密，具體所用的次數隨每一字符在明文中的位置而變化。323.1 3.1 替代加密替代加密 移位密碼體制移位密碼體制設P=C=K=Z/(26),對k K,定義ek(x)=x+k (mod 26)=y C 同時dk(y) = y - k (mod 26)注1*：26個英文字母與模26剩余類

23、集合0,.,25建立一一對應： A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2*.當k=3時，為Caesar密碼： 明文：meet me after the toga party 密文：PHHW PH DIWHO WKH WRJD SDUWB 實際算法為： 有 同時有，d3(y)=y-3 (mod 26)yxxe)26(mod3)(3Px333.1 3.1 替代加密替代加密 替換密碼體制替換密碼體制設

24、P=C=Z/(26)，K是由26個符號0，1,.,25的所有可能置換組成。任意K，定義e (x)= (x)=y 且 d (y)=-1(y)=x, -1是的逆置換。 注：1*. 置換的表示： 2*密鑰空間K很大，|k|=26! 41026，破譯者窮舉搜索是不行的，然而，可由統計的方式破譯它。3*移位密碼體制是替換密碼體制的一個特例，它僅含26個置換做為密鑰空間(0 1 2 3 .23 24 250 1 2 3 .23 24 25)343.1 3.1 替代加密替代加密 仿射密碼體制仿射密碼體制替換密碼的另一個特例就是仿射密碼。加密函數取形式為 e(x)=ax+b (mod 26), a,bZ/(2

25、6) 要求唯一解的充要條件是gcd( a,26)=1 該體制描述為： 設P=C=Z/(26) K=(a,b) Z/(26)Z/(26)|gcd(a,26)=1, 對k=(a,b) K, 定義 ek(x)=ax+b (mod 26)和dk(y)=a-1(y-b)(mod 26) x,y Z/(26)35 例子，設k（7，3），注意到7-1(mod 26)=15,加密函數是ek(x)=7x+3,相應的解密函數是dk(y)=15(y-3)=15y-19 , 易見 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x (mod 26) 若加密明文：hot ，首先轉換字母h

26、,o,t成為數字7,14,19,然后加密：解密：);26(mod6230333191477GXA19147191919623015363.1 3.1 替代加密替代加密 Hill密碼體制密碼體制設為某個固定的正整數，P=C=(Z/(26)m, K=Z/(26)上的mm可逆矩陣 對每一個k K,定義ek(x)=xK (mod 26)和 dk(y)=yK-1 (mod 26)注：明文與密文都是 m元的向量（x1, x2 , xm );(y1, y2,ym)，Z/(26)為同余類環。在這個環上的可逆矩陣Amxm,是指行列式detAmxm的值 Z*/(26),它為Z/(26)中全體可逆元的集合。Z*/(

27、26)= a Z/(26)|(a,26)=1， Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25例子：當 m=2時，明文元素x=(x1,x2),密文元素y=(y1,y2) (y1,y2)=(x1,x2) K7381137 事實上yi為x1,x2的線性組合，y1=11x1+3x2;y2=8x1+7x2，一般，將取mm的矩陣K作為我們的密鑰：有 y=(y1, y2, ym,)=(x1, x2, xm) 換言之，y=xK;且有x=yK-1 若K= ,可得K-1 = 若對明文july加密，它分成2個元素（j,u),(l,y),分別對應于（9,20）,（11,24）,有mmm

28、mmmkkkkkkkkk21222211121173811112318738（9,20） （9960,72140）（3,4） 且（11,24 ） (12172,88168) （11,22）于是對 july加密的結果為DELW。 為了解密，Bob計算 且 因此，得到了正確的明文“july”7381173811 )20, 9(1123187)4 , 3()24,11(1123187)22,11(393.1 3.1 替代加密替代加密 維吉尼亞密碼維吉尼亞密碼 (Vigenere)設m為一固定的正整數，定義P=C=K=(Z/(26)m,對一個密鑰K（ k1,k2,km),定義 ek(x1,x2,xm)

29、=(x1+k1,x2+k2,xm+km)=y dk(y1,y2,ym)= (x1-k1,x2-k2,xm-km) =x這里的所有的運算都是在（mod 26)中進行的。注：維吉尼亞密碼是多表替換體制，分析起來更困難。密鑰空間大，如當m=5時，密鑰空間所含密鑰的數量是1.1107403. 3. 替代加密和置換加密替代加密和置換加密 置換技術通過執行對明文字母的某種置換，取得一種類型完全不同的映射。這種技術稱為置換密碼。 413.1 3.1 置換加密置換加密 示例： COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE 密文：CAELP OPSEE

30、MHLAN PIOSS UCWTI TSBIU EMUTE RATSG YAERB TX 明文：COMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST ITS EXPENSIVE 423.1 3.1 置換加密置換加密 設m為固定的正整數，P=C=(Z/(26)m, K是由1,2,.,m的所有置換構成，對一個密鑰K，定義 e (x1, x2,., xm)=(x(1),.,x(m) 和 d (y1, y2,., ym)=(y(1),.,y(m) 這里1為的逆置換。注：這里的加密與解密僅僅用了置換，無代數運算。例子： 設m=6, 取密鑰 而) 6452)(31 (264

31、564135231) 5462)(31 (462554136231143若給定的明文是：cryptography 首先找分成6個字母長的明文組：crypto|graphy 求得的密文是：YTCOPRAHGYPR注：事實上，置換密碼是Hill密碼的特例。給定一個集合1,2,.,m的置換矩陣K =(kij)mm（置換矩陣是每一行和每一列剛好在一個“1”，而其余元素為“0”的矩陣。）YTCOPRroptopcytryccryptoAHGYPRryphypgahraggraphy否則若0)(1ijkij44對上面例子決定的置換 對應：0000100010001000000000010100000001

32、00K00100000001001000000000110000000010011KK453. 3. 替代加密和置換加密替代加密和置換加密 轉子機（Rotor Machine） A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 慢轉子 (b)在一次擊鍵后的設置 (a)最初設置 快轉子 中轉子 運動方向 慢轉子 快轉子 中轉子 運動方向 24 25 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3 4