《信息論與編碼》課件第7章

1、第7章加密編碼 加密編碼的基礎(chǔ)知識(shí) 數(shù)據(jù)加密標(biāo)準(zhǔn)DES公開密鑰加密法7.1 密碼學(xué)的基礎(chǔ)知識(shí) 人們希望把重要信息通過某種變換轉(zhuǎn)換成秘密形式的信息。轉(zhuǎn)換方法可以分為兩大類：隱寫術(shù)，隱蔽信息載體信號(hào)的存在，古代常用。編碼術(shù)，將載荷信息的信號(hào)進(jìn)行各種變換使它們不為非授權(quán)者所理解。 在利用現(xiàn)代通訊工具的條件下，隱寫術(shù)受到很大限制，但編碼術(shù)卻以計(jì)算機(jī)為工具取得了很大的發(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 密碼學(xué)中的基本概念 真實(shí)數(shù)據(jù)稱為明文M 對(duì)真實(shí)數(shù)據(jù)施加變化的過程稱為加密EK 加密后輸出的數(shù)據(jù)稱為密文C 從密文恢復(fù)出明文的過程稱為解密DK完成加密和解密的算法稱為密碼體制。變換過程中使用的參數(shù)叫密鑰K。加密時(shí)使用的密鑰與解密時(shí)使用的密鑰可以相同（單密鑰），也可以不同（雙密鑰） ciphertex

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

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

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

6、密鑰的信息 I(M；C)H(M)H(M/C) I(K；C)H(K)H(K/C)H(M/C)和H(K/C)越大，破譯者從密文能夠提取出有關(guān)明文和密鑰的信息就越小。對(duì)于合法的接收者，在已知密鑰和密文條件下提取明文信息：H(M/CK)0 I(M；CK)H(M)H(M/CK)H(M) 疑義度 因?yàn)?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)即已知密文后，密鑰的疑義度總是大于等于明文的疑義度。我們可以這樣來理解，由于可能存在多種密鑰把一個(gè)明文消息M加密成相同的密文消息C，即滿

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

8、1 換位和替代密碼 換位密碼：對(duì)數(shù)據(jù)中的字符或更小的單位（如位）重新組織，但并不改變它們本身。替代密碼：改變數(shù)據(jù)中的字符，但不改變它們之間的相對(duì)位置。 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盒的結(jié)合使用 7.2.2 DES密碼算法 DES密碼就是在上述換位和替代密碼的基礎(chǔ)上發(fā)展的。將輸入明文序列分成區(qū)組，每組64比特。 64比特的密鑰源循環(huán)移位產(chǎn)生16個(gè)子密鑰密鑰表

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

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

12、64比特的密文塊。破譯者可利用這個(gè)性質(zhì)來破譯DES。 改進(jìn)方法：密碼塊鏈接、密碼反饋方式密碼塊鏈接 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 公開密鑰加密法 前面介紹的秘密密鑰加密法，算法公開，密鑰是保密的（對(duì)稱密鑰）。如果要進(jìn)行通信，必須在這之前把密鑰通過非?？煽康姆绞椒峙浣o所有接收者，這在某些場(chǎng)合是很難做到的。因而提出了公開密鑰加密法PKC（Public Key Cryptography）密 鑰使用兩個(gè)不同密鑰（非對(duì)稱密鑰體制）；一個(gè)公開(公鑰)，另一個(gè)為用戶專用(私鑰)；通信雙方無需事先交換密鑰就可進(jìn)行保密通信；要從公鑰或密文分析出明文或私鑰，在計(jì)算上是不可能的。應(yīng) 用保密通信： 多個(gè)用戶將信息傳給某用戶，可用該用戶的公鑰加密，唯有該用戶可用自己的私鑰解讀。數(shù)字簽名： 用自己的私鑰加密信息，而以公鑰作為解密

14、密鑰，用來確認(rèn)發(fā)送者。PKC算法的關(guān)鍵 加密函數(shù)yF(x)的單向性 加密計(jì)算容易：對(duì)任意給定的x值，容易計(jì)算yF(x)的值；破譯難：已知F和y，不可能求出對(duì)應(yīng)的x值；用私鑰容易解密：若知道F的某種特殊性質(zhì)（竅門trapdoor ），就容易計(jì)算出x值。構(gòu)造和使用使用者構(gòu)造出單向函數(shù)F（公鑰）和它的逆函數(shù)F1（私鑰）。破譯者：已知F和密文不能推導(dǎo)出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算法由美國麻省理工學(xué)院（MIT）的研究小組提出的，該體制的名稱是用了三位作者（Rivest，Shamir和Adleman）英文名字的第一個(gè)字母拼合而成。理論基礎(chǔ)：利用數(shù)論 正：要求得到兩個(gè)大素?cái)?shù)（如大到1

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

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