1、第7章加密編碼 加密編碼的基礎知識 數(shù)據(jù)加密標準DES公開密鑰加密法7.1 密碼學的基礎知識 人們希望把重要信息通過某種變換轉換成秘密形式的信息。轉換方法可以分為兩大類：隱寫術，隱蔽信息載體信號的存在，古代常用。編碼術，將載荷信息的信號進行各種變換使它們不為非授權者所理解。 在利用現(xiàn)代通訊工具的條件下，隱寫術受到很大限制，但編碼術卻以計算機為工具取得了很大的發(fā)展。 Cryptography before ShannonFrom http:/ Ancient Ciphers I Atbash cipher used in old testament “ = “ Of course, anyone

2、 whod ever heard of this cipher could easily crack it. This is also true for another famous cipher, the Caesar cipher.ABCXYZDEFABCKdssb qhz bhdx!7.1.1 密碼學中的基本概念 真實數(shù)據(jù)稱為明文M 對真實數(shù)據(jù)施加變化的過程稱為加密EK 加密后輸出的數(shù)據(jù)稱為密文C 從密文恢復出明文的過程稱為解密DK完成加密和解密的算法稱為密碼體制。變換過程中使用的參數(shù)叫密鑰K。加密時使用的密鑰與解密時使用的密鑰可以相同（單密鑰），也可以不同（雙密鑰） ciphertex

3、t密碼體制（1）對稱（單密鑰）體制：加密密鑰和解密密鑰相同或者很容易相互推導出。 由于我們假定加密方法是眾所周知的，所以這就意味著變換EK和DK很容易互相推導。因此，如果對EK和DK都保密，則保密性和真實性就都有了保障。但這種體制中EK和DK只要暴露其中一個，另一個也就暴露了。所以，對稱密碼體制必須同時滿足保密性和真實性的全部要求。用于加密私人文件。非對稱（雙密鑰）密碼體制：加密密鑰和解密密鑰中至少有一個在計算上不可能被另一個導出。因此，在變換EK或DK中有一個可公開而不影響另一個的保密。 通過保護兩個不同的變換分別獲得保密性和真實性。保護DK獲得保密性，保護EK獲得真實性。公開密鑰體制即是這

4、種。接收者通過保密自己的解密密鑰來保障他接收信息的保密性，但不能保證真實性，因為任何知道他的加密密鑰的人都可以將虛假消息發(fā)給他。發(fā)送者通過保密自己的解密密鑰來保障他發(fā)送信息的真實性。但任何知道他的加密密鑰的人都可以破譯消息，保密性不能保證。用于數(shù)字簽名。密碼體制（2）EB DB M C M保障保密性保障真實性 M C MDA EADA EBDB EA M C C C M保密性真實性密碼分類根據(jù)加密明文數(shù)據(jù)時的加密單位的不同，分為分組密碼和序列密碼兩大類。分組密碼：設M為密碼消息，將M分成等長的連續(xù)區(qū)組M1,M2,，分組的長度一般是幾個字符，并且用同一密鑰K為各區(qū)組加密，即 序列密碼：若將M分成

5、連續(xù)的字符或位m1,m2,，并用密鑰序列KK1K2的第i個元素給mi加密，即常用分組密碼。 熵概念密碼系統(tǒng)的安全問題與噪聲信道問題進行類比。噪聲相當于加密變換，接收的失真消息相當于密文，破譯者則可類比于噪聲信道中的計算者。 隨機變量的不確定性可以通過給予附加信息而減少。正如前面介紹過條件熵一定小于無條件熵。例如，令X是32位二進制整數(shù)并且所有值的出現(xiàn)概率都相等，則X的熵H(X)32比特。假設已經知道X是偶數(shù)，那么熵就減少了一位，因為X的最低位肯定是零。 疑義度 對于給定密文，密鑰的疑義度可表示為對于給定密文，明文的疑義度可表示為 破譯者的任務是從截獲的密文中提取有關明文的信息或從密文中提取有關

6、密鑰的信息 I(M；C)H(M)H(M/C) I(K；C)H(K)H(K/C)H(M/C)和H(K/C)越大，破譯者從密文能夠提取出有關明文和密鑰的信息就越小。對于合法的接收者，在已知密鑰和密文條件下提取明文信息：H(M/CK)0 I(M；CK)H(M)H(M/CK)H(M) 疑義度 因為 H(K/C)H(M/KC) H(M/C)H(K/MC)（M和K交換） H(M/C) （熵值H(K/MC)總是大于等于零）H(M/CK)0，上式得 H(K/C) H(M/C)即已知密文后，密鑰的疑義度總是大于等于明文的疑義度。我們可以這樣來理解，由于可能存在多種密鑰把一個明文消息M加密成相同的密文消息C，即滿

7、足的K值不止一個。但用同一個密鑰對不同明文加密而得到相同的密文則較困難。又因為 H(K) H(K/C) H(M/C)，則 上式說明，保密系統(tǒng)的密鑰量越少，密鑰熵H(K)就越小，其密文中含有的關于明文的信息量I(M;C)就越大。至于破譯者能否有效地提取出來，則是另外的問題了。作為系統(tǒng)設計者，自然要選擇有足夠多的密鑰量才行。 7.2 數(shù)據(jù)加密標準DES 1977年7月美國國家標準局公布了采納IBM公司設計的方案作為非機密數(shù)據(jù)的正式數(shù)據(jù)加密標準（DESData Encryption Standard）。DES密碼是一種采用傳統(tǒng)加密方法的區(qū)組密碼，它的算法是對稱的，既可用于加密又可用于解密。 7.2.

8、1 換位和替代密碼 換位密碼：對數(shù)據(jù)中的字符或更小的單位（如位）重新組織，但并不改變它們本身。替代密碼：改變數(shù)據(jù)中的字符，但不改變它們之間的相對位置。 P盒 0 15 15 0 0 14 14 0 0 13 13 0 0 12 12 0輸 0 11 11 0 輸 0 10 10 0入 0 9 9 0 出 0 8 8 0數(shù) 0 7 7 0 數(shù) 0 6 6 0據(jù) 0 5 5 1 據(jù) 0 4 4 0 0 3 3 0 0 2 2 0 1 1 1 0輸入第i位輸出第j位151413121110987654321741210152111914638135換位盒(P盒) S盒n=3 2n=8 2n=8 0

9、00 1 1 1 2 21 3 3 1 4 41 5 5 1 6 6 7 7輸入輸出000001010011100101110111101010100111000110011001替代盒（S盒） 0 P s P s P s P 0 0 1 0 0 0 0輸 0 s s s 0 輸 0 1入 0 1 出 0 s s s 1數(shù) 0 1 數(shù) 0 0據(jù) 0 s s s 0 據(jù) 0 0 0 1 0 s s s 1 1 0P盒和S盒的結合使用 7.2.2 DES密碼算法 DES密碼就是在上述換位和替代密碼的基礎上發(fā)展的。將輸入明文序列分成區(qū)組，每組64比特。 64比特的密鑰源循環(huán)移位產生16個子密鑰密鑰表

10、計算7.2.3 DES密碼的安全性 DES的出現(xiàn)在密碼學史上是一個創(chuàng)舉。以前的任何設計者對于密碼體制及其設計細節(jié)都是嚴加保密的。而DES算法則公開發(fā)表，任人測試、研究和分析，無須通過許可就可制作DES的芯片和以DES為基礎的保密設備。DES的安全性完全依賴于所用的密鑰。 弱密鑰DES算法中每次迭代所用的子密鑰都相同，即 K1K2K16 ，如111，此時DESk(DESk(x)x，DESk1(DESk1(x)x即以k對x加密兩次或解密兩次都恢復出明文。其加密運算和解密運算沒有區(qū)別。而對一般密鑰只滿足 DESk1(DESk(x)DESk(DESk1(x)x半弱密鑰給定的密鑰k，相應的16個子密鑰只

11、有兩種圖樣，且每種都出現(xiàn)8次。如101010半弱密鑰的特點是成對地出現(xiàn)，且具有下述性質：若k1和k2為一對互逆的半弱密鑰，x為明文組，則有 DESk1(DESk2(x)DESk2(DESk1(x)x 稱k1和k2是互為對合的。 問題DES的密鑰短了些 選擇長的密鑰會使成本提高、運行速度降低。 新算法很可能要采用128比特密鑰。 實現(xiàn)DES算法的產品有：設計專用LSI器件或芯片；用現(xiàn)成的微處理器實現(xiàn)；只限于實現(xiàn)DES算法；可運行各種工作模式。 7.2.4 DES密碼的改進 盡管DES算法十分復雜，但它基本上還是采用64比特字符的單字母表替換密碼。當同樣的64比特明文塊進入編碼器后，得到的是同樣的

12、64比特的密文塊。破譯者可利用這個性質來破譯DES。 改進方法：密碼塊鏈接、密碼反饋方式密碼塊鏈接 M1 M2 M3 M4 C1 C2 C3 C4 V # # # # 密鑰 D D D D 解密箱 加密箱密鑰 E E E E V # # # # 異或 C1 C2 C3 C4 M1 M2 M3 M4 (a) (b) 64位移位寄存器 64位移位寄存器 C2 C3 C4 C5 C6 C7 C8 C9 C2 C3 C4 C5 C6 C7 C8 C9 64 8 密鑰 E 加密箱 C10 密鑰 E 加密箱 C10 選擇最左字節(jié) 選擇最左字節(jié) 8 M10 # C10 C10 # M10 8 (a) (b)

13、密碼反饋方式7.3 公開密鑰加密法 前面介紹的秘密密鑰加密法，算法公開，密鑰是保密的（對稱密鑰）。如果要進行通信，必須在這之前把密鑰通過非?？煽康姆绞椒峙浣o所有接收者，這在某些場合是很難做到的。因而提出了公開密鑰加密法PKC（Public Key Cryptography）密 鑰使用兩個不同密鑰（非對稱密鑰體制）；一個公開(公鑰)，另一個為用戶專用(私鑰)；通信雙方無需事先交換密鑰就可進行保密通信；要從公鑰或密文分析出明文或私鑰，在計算上是不可能的。應 用保密通信： 多個用戶將信息傳給某用戶，可用該用戶的公鑰加密，唯有該用戶可用自己的私鑰解讀。數(shù)字簽名： 用自己的私鑰加密信息，而以公鑰作為解密

14、密鑰，用來確認發(fā)送者。PKC算法的關鍵 加密函數(shù)yF(x)的單向性 加密計算容易：對任意給定的x值，容易計算yF(x)的值；破譯難：已知F和y，不可能求出對應的x值；用私鑰容易解密：若知道F的某種特殊性質（竅門trapdoor ），就容易計算出x值。構造和使用使用者構造出單向函數(shù)F（公鑰）和它的逆函數(shù)F1（私鑰）。破譯者：已知F和密文不能推導出F1或明文；接收者：用竅門信息（解密密鑰Kd）簡單地求解xF1Kd(y)。 7.4.1 公開密鑰密碼體制 保密通信 公開加密密鑰 秘密解密密鑰 B(e，n) B(d，n) A(e，n) A(d，n)B發(fā)到A B M fA(e，n) C A A接收B A

15、C fA(d，n) M A發(fā)到B A M fB(e，n) C BB接收A B C fB(d，n) M7.4.1 公開密鑰密碼體制 數(shù)字簽名 公開加密密鑰 秘密解密密鑰 B(e，n) B(d，n) A(e，n) A(d，n)B發(fā)到A B M fB(d，n) S fA(e，n) C AA收到B A C fA(d，n) S fB(e，n) M RSA密碼體制（1） RSA由來：RSA體制是根據(jù)PKC算法由美國麻省理工學院（MIT）的研究小組提出的，該體制的名稱是用了三位作者（Rivest，Shamir和Adleman）英文名字的第一個字母拼合而成。理論基礎：利用數(shù)論 正：要求得到兩個大素數(shù)（如大到1

16、00位）的 乘積在計算機上很容易實現(xiàn)。 逆：但要分解兩個大素數(shù)的乘積在計算上幾乎 不可能實現(xiàn)。密鑰設計：兩個密鑰：公鑰（e，n） 私鑰（d，n）加密解密： 加密時：解密時： RSA密碼體制（2） 實現(xiàn)步驟：選取兩個很大的素數(shù)p和q，令模數(shù) 求n的歐拉函數(shù) 并從2至(n)1中任選一個數(shù)作為加密指數(shù)e；解同余方程 求得解密指數(shù)d；(e，n)即為公開密鑰，(d，n)即為秘密密鑰。 RSA密碼體制（3） 例題保密通信例7-1 在RSA方法中，令p3，q17，取e5，試計算解密密鑰d并加密M2。解：npq51 (n)(p1)(q1)32 (5d) mod 321，可解得d13 加密 yxe mod n2

17、5 mod 5132 解密 yd mod n3213 mod 512x 若需發(fā)送的報文內容是用英文或其他文字表示的，則可先將文字轉換成等效的數(shù)字，再進行加密運算。 RSA公開密鑰體制用于數(shù)字簽名發(fā)送者A用自己的秘密解密密鑰(dA，nA)計算簽名；用接收者B的公開加密密鑰(eB，nB)再次加密：接收者B用自己的秘密解密密鑰(dB，nB)解密：查發(fā)送者A的公開密鑰(dA，nA)計算，恢復出發(fā)送者的簽名，認證密文的來源。 (dA，nA) (eB，nB) (dB，nB) (eA，nA) Mi Si S Si Mi 例題數(shù)字簽名例7-2 用戶A發(fā)送給用戶B一份密文，用戶A用首字母B02來簽署密文。用戶A知道下列三個密鑰： A B公開密鑰(e，n) (7，123) (13，51)秘密密鑰(d，n) (23，123)A計算他的簽名：再次加密簽名： 接收者B必須恢復出02B認證他接收的密文。接收者也知道三個密鑰： A B公開密鑰(e，n) (7，123) (13，51)秘密密鑰(d，n) (5，51)B用戶用自己的秘密解密密鑰一次解密：