《通信原理教程》(第3版) 樊昌信 編著第十三章PPT課件

1、1通信安全的基礎(chǔ)通信安全的基礎(chǔ) 密碼學(xué)密碼學(xué)n密碼編碼學(xué)密碼編碼學(xué)n密碼分析學(xué)密碼分析學(xué)通信不安全因素通信不安全因素n被破譯被破譯n被攻擊被攻擊 被偽造和篡改被偽造和篡改認(rèn)證認(rèn)證 防止被攻擊的手段防止被攻擊的手段認(rèn)證的目的：認(rèn)證的目的：n驗(yàn)證信息發(fā)送者真?zhèn)悟?yàn)證信息發(fā)送者真?zhèn)蝞驗(yàn)證接收信息的完整性驗(yàn)證接收信息的完整性 是否被篡改了？是否被重復(fù)接收是否被篡改了？是否被重復(fù)接收了？是否被拖延了？了？是否被拖延了？認(rèn)證技術(shù)：包括消息認(rèn)證、身份驗(yàn)證和數(shù)字簽字。認(rèn)證技術(shù)：包括消息認(rèn)證、身份驗(yàn)證和數(shù)字簽字。2密碼編碼學(xué)內(nèi)容：密碼編碼學(xué)內(nèi)容：n將消息加密的方法將消息加密的方法n將已加密的消息解密的方法將已加密

2、的消息解密的方法密碼分析學(xué)內(nèi)容：如何破譯密文和偽造密文。密碼分析學(xué)內(nèi)容：如何破譯密文和偽造密文。密碼學(xué)的基本術(shù)語(yǔ)密碼學(xué)的基本術(shù)語(yǔ)n明文明文 待加密的消息待加密的消息n密文密文 加密后的消息加密后的消息n密碼密碼 用于加密的數(shù)據(jù)變換集合用于加密的數(shù)據(jù)變換集合n密鑰密鑰 用于表示加密變換的參數(shù)用于表示加密變換的參數(shù)密碼種類：密碼種類：n單密鑰密碼單密鑰密碼n公共密鑰密碼：也稱為雙密鑰密碼公共密鑰密碼：也稱為雙密鑰密碼3例：例：n密鑰密鑰Z m序列序列n加密算法加密算法 模模2加法加法n解密算法解密算法 仍是模仍是模2加法加法 一般算法：一般算法：令令F為產(chǎn)生密文為產(chǎn)生密文Y 的可逆變換，即有的可逆

3、變換，即有Y = F(X, Z) = FZ(X)在接收端，密文在接收端，密文Y 用逆變換用逆變換F-1恢復(fù)成原來(lái)的明文恢復(fù)成原來(lái)的明文X ，即，即X = F-1(Y, Z) = FZ-1(Y) = FZ-1FZ(X)密鑰密鑰安全信道安全信道信源信源加密加密解密解密信道信道XYZX敵方敵方發(fā)送端發(fā)送端 信道信道 接收端接收端4分組密碼分組密碼n加密過(guò)程加密過(guò)程n原理原理p連續(xù)的分組用相同的密鑰加密。連續(xù)的分組用相同的密鑰加密。p若有一個(gè)特定的分組明文和以前的一個(gè)分組相同，則加若有一個(gè)特定的分組明文和以前的一個(gè)分組相同，則加密后兩者的密文也相同。密后兩者的密文也相同。p目標(biāo)是使明文的任目標(biāo)是使明文

4、的任1比特都不會(huì)直接出現(xiàn)在密文中。比特都不會(huì)直接出現(xiàn)在密文中。串行串行-分組分組變換器變換器密碼加密密碼加密邏輯邏輯分組分組-串行串行變換器變換器密鑰密鑰串行串行明文明文串行串行明文明文5流密碼流密碼n原理：對(duì)明文的逐個(gè)比特進(jìn)行不同的變換。原理：對(duì)明文的逐個(gè)比特進(jìn)行不同的變換。 n例：二進(jìn)制加性流密碼例：二進(jìn)制加性流密碼p令令xn, yn和和zn分別表示在分別表示在n時(shí)刻明文比特、密文比特和密時(shí)刻明文比特、密文比特和密鑰流比特，則有鑰流比特，則有式中，式中，N是密鑰流的長(zhǎng)度。是密鑰流的長(zhǎng)度。因?yàn)樵谀Ｒ驗(yàn)樵谀?運(yùn)算中加法和減法是一樣的，所以上式也運(yùn)算中加法和減法是一樣的，所以上式也可以寫(xiě)為可以寫(xiě)

5、為因此，同樣的裝置既可以用于加密，也可以用于解密。因此，同樣的裝置既可以用于加密，也可以用于解密。密鑰流密鑰流產(chǎn)生器產(chǎn)生器明文明文 xn密文密文 yn密鑰流密鑰流 zn密鑰密鑰(a)加密裝置加密裝置密鑰流密鑰流產(chǎn)生器產(chǎn)生器密文密文 yn明文明文 xn密鑰流密鑰流 zn密鑰密鑰(b)解密裝置解密裝置Nnzxynnn, 2, 1,Nnzyxnnn, 2, 1,6p密鑰流應(yīng)當(dāng)盡可能地近似于一個(gè)完全隨機(jī)的序列。密鑰流應(yīng)當(dāng)盡可能地近似于一個(gè)完全隨機(jī)的序列。p若密鑰流是一個(gè)若密鑰流是一個(gè)m序列，則圖中的密鑰流產(chǎn)生器就是一序列，則圖中的密鑰流產(chǎn)生器就是一個(gè)個(gè)m序列產(chǎn)生器；密鑰則是控制此序列產(chǎn)生器；密鑰則是控

6、制此m序列的生成多項(xiàng)式序列的生成多項(xiàng)式和同步信息等。和同步信息等。p二進(jìn)制加性流密碼沒(méi)有錯(cuò)誤傳播；在密文中一個(gè)錯(cuò)誤比二進(jìn)制加性流密碼沒(méi)有錯(cuò)誤傳播；在密文中一個(gè)錯(cuò)誤比特解密后只影響輸出中的相應(yīng)比特。特解密后只影響輸出中的相應(yīng)比特。（分組密碼可能有錯(cuò)誤傳播，使明文分組中很少幾個(gè)比（分組密碼可能有錯(cuò)誤傳播，使明文分組中很少幾個(gè)比特的改變?cè)诿芪妮敵鲋挟a(chǎn)生很多比特的變化。分組密碼特的改變?cè)诿芪妮敵鲋挟a(chǎn)生很多比特的變化。分組密碼的這種錯(cuò)誤傳播性質(zhì)在認(rèn)證中很有價(jià)值，因?yàn)樗箶撤降倪@種錯(cuò)誤傳播性質(zhì)在認(rèn)證中很有價(jià)值，因?yàn)樗箶撤降钠谱g人員不可能修改加密后的數(shù)據(jù)，除非知道密鑰。）的破譯人員不可能修改加密后的數(shù)據(jù)，

7、除非知道密鑰。）p 流密碼通常較適用于通過(guò)易出錯(cuò)的通信信道傳輸數(shù)據(jù)，流密碼通常較適用于通過(guò)易出錯(cuò)的通信信道傳輸數(shù)據(jù)，用于要求高數(shù)據(jù)率的應(yīng)用中，例如視頻保密通信，或者用于要求高數(shù)據(jù)率的應(yīng)用中，例如視頻保密通信，或者用于要求傳輸延遲很小的場(chǎng)合。用于要求傳輸延遲很小的場(chǎng)合。7對(duì)通信安全的基本要求對(duì)通信安全的基本要求n假設(shè)：敵方破譯人員知道所用加密法的全部機(jī)理，只是假設(shè)：敵方破譯人員知道所用加密法的全部機(jī)理，只是不知道密鑰。不知道密鑰。 n密碼分析性攻擊的形式：密碼分析性攻擊的形式：p僅對(duì)密文的攻擊僅對(duì)密文的攻擊p對(duì)已知明文的攻擊對(duì)已知明文的攻擊p對(duì)選定的明文的攻擊對(duì)選定的明文的攻擊p對(duì)選定的密文的攻

8、擊對(duì)選定的密文的攻擊 n實(shí)際中常發(fā)生的是僅對(duì)密文的攻擊：實(shí)際中常發(fā)生的是僅對(duì)密文的攻擊：p例：使用語(yǔ)言的統(tǒng)計(jì)結(jié)構(gòu)知識(shí)（例如，英文字母例：使用語(yǔ)言的統(tǒng)計(jì)結(jié)構(gòu)知識(shí)（例如，英文字母e的的出現(xiàn)概率是出現(xiàn)概率是13%，以及字母，以及字母q的后面總跟隨著的后面總跟隨著u）和關(guān)）和關(guān)于某些可能的字的知識(shí)（例如，一封信的開(kāi)頭中可能于某些可能的字的知識(shí)（例如，一封信的開(kāi)頭中可能有有“先生先生”或或“女士女士”兩字）。兩字）。 n僅對(duì)密文的攻擊是一個(gè)密碼系統(tǒng)受到的最輕的威脅。因僅對(duì)密文的攻擊是一個(gè)密碼系統(tǒng)受到的最輕的威脅。因此，任何系統(tǒng)若不能戰(zhàn)勝這種攻擊，則被認(rèn)為是完全不此，任何系統(tǒng)若不能戰(zhàn)勝這種攻擊，則被認(rèn)為是

9、完全不安全的系統(tǒng)。安全的系統(tǒng)。 8香農(nóng)模型的假定：香農(nóng)模型的假定：n敵方破譯人員具有無(wú)限的時(shí)間和無(wú)限的計(jì)算能力；敵方破譯人員具有無(wú)限的時(shí)間和無(wú)限的計(jì)算能力；n敵方僅限于對(duì)密文攻擊。敵方僅限于對(duì)密文攻擊。香農(nóng)的密碼分析定義：給定密文以及各種明文和密鑰的先驗(yàn)香農(nóng)的密碼分析定義：給定密文以及各種明文和密鑰的先驗(yàn)概率，搜尋密鑰的過(guò)程。當(dāng)敵方破譯人員獲得密文的唯一解概率，搜尋密鑰的過(guò)程。當(dāng)敵方破譯人員獲得密文的唯一解時(shí)，就成功地解密了。時(shí)，就成功地解密了。香農(nóng)對(duì)安全性的基本度量香農(nóng)對(duì)安全性的基本度量 互信息量互信息量I(X; Y) n令令X = (X1, X2, , XN)表示一個(gè)表示一個(gè)N 比特的明文

10、消息比特的明文消息; Y = (Y1, Y2, , YN)表示相應(yīng)的表示相應(yīng)的N 比特密文。比特密文。n假定：假定：p密鑰密鑰Z服從某種概率分布服從某種概率分布pH(X) X的不確定性的不確定性pH(X/Y) 給定給定Y后后X的不確定性的不確定性pI (X; Y) = H(X) H(X/Y) X和和Y之間的互信息量。之間的互信息量。9 13.4.1 完善安全性完善安全性完善安全性定義完善安全性定義 假定：破譯人員只能夠看到密文假定：破譯人員只能夠看到密文Y，則一個(gè)保密系統(tǒng)的完，則一個(gè)保密系統(tǒng)的完善安全性定義為：明文善安全性定義為：明文X和密文和密文Y之間是統(tǒng)計(jì)獨(dú)立的，即有之間是統(tǒng)計(jì)獨(dú)立的，即有

11、I(X; Y) = 0于是，由于是，由I (X; Y) = H(X) H(X/Y)，可以求出，可以求出H(X/Y) = H(X) 上式表明，敵方破譯人員最多只能，按照所有可能消息上式表明，敵方破譯人員最多只能，按照所有可能消息的概率分布，從給定的密文的概率分布，從給定的密文Y，去猜測(cè)明文消息，去猜測(cè)明文消息X。 10香農(nóng)基本界香農(nóng)基本界給定密鑰給定密鑰Z后，有后，有H(X/Y) H(X, Z/Y) = H(Z/Y) + H(X/Y, Z)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Y 和和 Z 共同唯一地決定共同唯一地決定X 時(shí)，時(shí)，H(X/Y, Z) = 0；當(dāng)使用已知密鑰當(dāng)使用已知密鑰 Z 解密時(shí)，這是一個(gè)很有價(jià)值的

12、假定。解密時(shí)，這是一個(gè)很有價(jià)值的假定。 因此，我們可以將式因此，我們可以將式H(X/Y) H(X, Z/Y) = H(Z/Y) + H(X/Y, Z)簡(jiǎn)化如下：簡(jiǎn)化如下：H(X/Y) H(Z/Y) H(Z)將上式代入式將上式代入式H(X/Y) = H(X)得知：為使一個(gè)保密系統(tǒng)給出完善的安全性，必須滿足條件得知：為使一個(gè)保密系統(tǒng)給出完善的安全性，必須滿足條件H(Z) H(X) 它表明為了達(dá)到完善安全性，密鑰它表明為了達(dá)到完善安全性，密鑰Z的不確定性必須的不確定性必須不小于被此密鑰所隱蔽的明文不小于被此密鑰所隱蔽的明文X的不確定性。的不確定性。 11一次一密密碼一次一密密碼n原理方框圖：一種流密

13、碼，其密鑰和密鑰流相同，并且密原理方框圖：一種流密碼，其密鑰和密鑰流相同，并且密鑰只使用一次。鑰只使用一次。 n密文密文 yn = xn zn,n = 1, 2, 式中，式中，xn 消息比特序列；消息比特序列； zn 統(tǒng)計(jì)獨(dú)立和均勻分布的密鑰比特序列。統(tǒng)計(jì)獨(dú)立和均勻分布的密鑰比特序列。n一次一密密碼是完善安全的，因?yàn)橄⒑兔芪闹g的互信一次一密密碼是完善安全的，因?yàn)橄⒑兔芪闹g的互信息量為息量為0；所以它是完全不可解密的。；所以它是完全不可解密的。 消息消息xn密文密文yn密鑰密鑰zn密文密文yn消息消息xn密鑰密鑰zn(a) 加密加密(b) 解密解密12 13.4.2 唯一解距離唯一解距離

14、對(duì)于一個(gè)用非完善密碼加密的密文，可以預(yù)期，當(dāng)截獲的文對(duì)于一個(gè)用非完善密碼加密的密文，可以預(yù)期，當(dāng)截獲的文件量隨時(shí)間增大到某一點(diǎn)時(shí)，破譯人員用無(wú)限的時(shí)間和無(wú)限件量隨時(shí)間增大到某一點(diǎn)時(shí)，破譯人員用無(wú)限的時(shí)間和無(wú)限的計(jì)算能力，將能夠找到密鑰并從而破譯了密文。的計(jì)算能力，將能夠找到密鑰并從而破譯了密文。 在香農(nóng)的模型中，破譯人員能破譯此密文的臨界點(diǎn)稱為唯一在香農(nóng)的模型中，破譯人員能破譯此密文的臨界點(diǎn)稱為唯一解距離。解距離。唯一解距離的定義：唯一解距離的定義： 使條件熵使條件熵H(Z/Y1, Y2, , YN)近似為近似為0的最小的最小N。對(duì)于一類特殊的對(duì)于一類特殊的“隨機(jī)密文隨機(jī)密文”，唯一解距離近似

15、由下式給出：，唯一解距離近似由下式給出：式中，式中，H(Z) 密鑰密鑰Z的熵，的熵， Ly 密文字符集的大小，密文字符集的大小， r N比特密文中所含信息的冗余度百分比，即比特密文中所含信息的冗余度百分比，即式中，式中，H(X)為明文為明文X的熵。的熵。 yLrHN20log)(ZyLNHr2log)(1X13 在大多數(shù)保密系統(tǒng)中，密文字符集的大小在大多數(shù)保密系統(tǒng)中，密文字符集的大小Ly和明文字符和明文字符集的大小集的大小Lx一樣。在這種情況下，一樣。在這種情況下，r就是明文本身的冗余度百就是明文本身的冗余度百分比。分比。求求H(Z) 令令 K = 密鑰密鑰Z中的數(shù)字?jǐn)?shù)目，這些數(shù)字是從大小為中

16、的數(shù)字?jǐn)?shù)目，這些數(shù)字是從大小為L(zhǎng)z的字的字符集中選用的；則可以將密鑰符集中選用的；則可以將密鑰 Z 的熵表示如下：的熵表示如下：當(dāng)且僅當(dāng)密鑰是完全隨機(jī)的時(shí)，上式等號(hào)成立。當(dāng)且僅當(dāng)密鑰是完全隨機(jī)的時(shí)，上式等號(hào)成立。 令令Lz = Ly，并完全隨機(jī)地選擇密鑰以使唯一解距離最大。，并完全隨機(jī)地選擇密鑰以使唯一解距離最大。然后，將然后，將H(Z) = K log2 Lz代入代入得到：得到：N0 K / r yLNHr2log)(1XzKzLKLH22loglog)(ZyLrHN20log)(Z14N0 K / r 例：考察一個(gè)例：考察一個(gè)Lx = Ly = Lz保密系統(tǒng)，它用于對(duì)英文文本加密保密系統(tǒng)，

17、它用于對(duì)英文文本加密 典型英文文本的典型英文文本的 r 大約等于大約等于75。因此，按照上式，一個(gè)。因此，按照上式，一個(gè)破譯人員在僅截獲約破譯人員在僅截獲約1.333K比特的密文數(shù)據(jù)后，就能破譯此比特的密文數(shù)據(jù)后，就能破譯此密碼，其中密碼，其中K是密鑰長(zhǎng)度。是密鑰長(zhǎng)度。值得注意，非完善密碼仍然有實(shí)用價(jià)值。值得注意，非完善密碼仍然有實(shí)用價(jià)值。 15 13.4.3 數(shù)據(jù)壓縮在密碼編碼中的作用數(shù)據(jù)壓縮在密碼編碼中的作用數(shù)據(jù)壓縮能除去冗余度，因此增大了唯一解距離。數(shù)據(jù)壓縮能除去冗余度，因此增大了唯一解距離。 13.4.4 擴(kuò)散與混淆擴(kuò)散與混淆擴(kuò)散：將明文中一個(gè)比特的影響擴(kuò)散到密文中很多比特，從擴(kuò)散：將

18、明文中一個(gè)比特的影響擴(kuò)散到密文中很多比特，從而將明文的統(tǒng)計(jì)結(jié)構(gòu)隱藏起來(lái)。而將明文的統(tǒng)計(jì)結(jié)構(gòu)隱藏起來(lái)。 混淆：采用數(shù)據(jù)變換，使密文的統(tǒng)計(jì)特性與明文的統(tǒng)計(jì)特性混淆：采用數(shù)據(jù)變換，使密文的統(tǒng)計(jì)特性與明文的統(tǒng)計(jì)特性之間的關(guān)系更為復(fù)雜。之間的關(guān)系更為復(fù)雜。 乘積密碼：由一些簡(jiǎn)單的密碼分量相繼加密構(gòu)成；這些較簡(jiǎn)乘積密碼：由一些簡(jiǎn)單的密碼分量相繼加密構(gòu)成；這些較簡(jiǎn)單的密碼分量分別能使最終的密碼有適度的擴(kuò)散和混淆。單的密碼分量分別能使最終的密碼有適度的擴(kuò)散和混淆。 例：乘積密碼用例：乘積密碼用“替代密碼替代密碼”和和“置換密碼置換密碼”作為基本分作為基本分量。量。16替代密碼：明文的每個(gè)字符用一種固定的替代所

19、代替；代替替代密碼：明文的每個(gè)字符用一種固定的替代所代替；代替的字符仍為同一字符表中的字符；特定的替代規(guī)則由密鑰決的字符仍為同一字符表中的字符；特定的替代規(guī)則由密鑰決定。定。 若明文為若明文為X = (x1, x2, x3, x4, ) 式中，式中，x1, x2, x3, x4, 為相繼的字符，則為相繼的字符，則變換后的密文為變換后的密文為Y = (y1, y2, y3, y4, ) = f(x1), f(x2), f(x3), f(x4),式中，式中，f ( )是一個(gè)可逆函數(shù)。是一個(gè)可逆函數(shù)。 例：密文的字符表例：密文的字符表 從此表中可以看到，第一個(gè)字符從此表中可以看到，第一個(gè)字符U替代替

20、代A，第二個(gè)字符，第二個(gè)字符H替代替代B，等等。，等等。 使用替代密碼可以得到混淆。使用替代密碼可以得到混淆。明文字符明文字符ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字符密文字符UHNACSVYDXEKQJRWGOZITPFMBL17置換密碼：明文被分為具有固定周期置換密碼：明文被分為具有固定周期 d 的組，對(duì)每組作同樣的組，對(duì)每組作同樣的交換。特定的交換規(guī)則是由密鑰決定的。的交換。特定的交換規(guī)則是由密鑰決定的。n若周期若周期d4，交換規(guī)則為，交換規(guī)則為則明文中的字符則明文中的字符 x 將從位置將從位置 1 移至密文中的位置移至密文中的位置 4。 一般而言，明文一般而言，明文X

21、 = (x1, x2, x3, x4, x5, x6, x7, x8, )將變換成密文將變換成密文Y = (x3, x4, x2, x1, x7, x8, x6, x5, )n雖然密文雖然密文Y 中單個(gè)字符的統(tǒng)計(jì)特性和明文中單個(gè)字符的統(tǒng)計(jì)特性和明文X 中的一樣，但中的一樣，但是高階統(tǒng)計(jì)特性卻改變了。是高階統(tǒng)計(jì)特性卻改變了。n使用置換密碼可以得到擴(kuò)散。使用置換密碼可以得到擴(kuò)散。明文字符明文字符x1 x2 x3 x4密文字符密文字符x3 x4 x2 x118將替代和置換作交織，并將交織過(guò)程重復(fù)多次，就能得到具將替代和置換作交織，并將交織過(guò)程重復(fù)多次，就能得到具有良好擴(kuò)散和混淆性能的保密性極強(qiáng)的密碼

22、。有良好擴(kuò)散和混淆性能的保密性極強(qiáng)的密碼。例：例： 設(shè)明文消息為設(shè)明文消息為T(mén)HE APPLES ARE GOOD使用交換字符表使用交換字符表作為替代密碼，則此明文將變換為如下密文：作為替代密碼，則此明文將變換為如下密文：IYC UWWKCZ UOC VRRA 下一步我們將交換規(guī)則下一步我們將交換規(guī)則用于置換密碼，則從替代密碼得到的密文將進(jìn)一步變換成用于置換密碼，則從替代密碼得到的密文將進(jìn)一步變換成UCI YCKWWC OZU ARVR這樣，上面的密文和原來(lái)的明文相比，毫無(wú)共同之處。這樣，上面的密文和原來(lái)的明文相比，毫無(wú)共同之處。明文字符明文字符ABCDEFGHIJKLMNOPQRSTUVWX

23、YZ密文字符密文字符UHNACSVYDXEKQJRWGOZITPFMBL明文字符明文字符x1 x2 x3 x4密文字符密文字符x3 x4 x2 x11913.5 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn) 美國(guó)政府標(biāo)準(zhǔn)算法美國(guó)政府標(biāo)準(zhǔn)算法DES DES采用擴(kuò)散和混淆算法，是一種保密性很強(qiáng)的密碼。采用擴(kuò)散和混淆算法，是一種保密性很強(qiáng)的密碼。它對(duì)它對(duì)64 b長(zhǎng)的明文數(shù)據(jù)分組運(yùn)算，所用的密鑰長(zhǎng)度為長(zhǎng)的明文數(shù)據(jù)分組運(yùn)算，所用的密鑰長(zhǎng)度為56 b。 DES算法中：算法中：n總變換總變換 = P -1FP(X)，其中其中 X 明文，明文，P 某種交換，某種交換，F(xiàn) 包括替代和置換；由某些函數(shù)包括替代和置換；由某些函數(shù) f

24、的級(jí)連構(gòu)成。的級(jí)連構(gòu)成。20DES算法流程圖算法流程圖n第第1次初始交換后：次初始交換后：64 b的明文分為左的明文分為左半部半部L0和右半部和右半部R0，每半部長(zhǎng)，每半部長(zhǎng)32 b。 n完成完成16輪交換，其中第輪交換，其中第 i 輪交換：輪交換： Li = Ri1， i = 1，2，16Ri = Li-1 f(Ri-1, Zi)，i = 1，2，16式中，式中，Zi 在第在第i 輪中使用的密鑰；輪中使用的密鑰；此密鑰的長(zhǎng)度為此密鑰的長(zhǎng)度為48 b。 n第第16輪運(yùn)算的結(jié)果，經(jīng)過(guò)顛倒后，輪運(yùn)算的結(jié)果，經(jīng)過(guò)顛倒后，得到得到R16L16。 n再經(jīng)過(guò)最后一次交換再經(jīng)過(guò)最后一次交換P -1，就產(chǎn)生出

25、就產(chǎn)生出64 b的密文。的密文。n為了解密，函數(shù)為了解密，函數(shù)f( , )不必須是可逆的，不必須是可逆的，因?yàn)橐驗(yàn)?Li-1, Ri-1)能夠從能夠從(Li, Ri)直接恢復(fù)：直接恢復(fù)： Ri-1 = Li i = 1，2，16Li-1 = Ri f(Li, Zi) i = 1，2，1664 b密文密文f(R0, Z1)R16L16最后一次交換最后一次交換Z164 b 明文明文初始交換初始交換32 b L032 b R0f(R0, Z1)R1L1f(R0, Z1)R2L2R15L15Z2Z1621計(jì)算計(jì)算f( , )的流程圖的流程圖n擴(kuò)展：擴(kuò)展：R(32b) R (48b) 方法：重復(fù)每個(gè)相繼

26、的方法：重復(fù)每個(gè)相繼的4 比特字的兩端比特。比特字的兩端比特。若若 R = r1r2r3r4 r5r6r7r8 r29r30r31r32則擴(kuò)展后則擴(kuò)展后R r32r1r2r3r4r5 r4r5r6r7r8r9 r28r29r30r31r32r1nR 和和 Zi 模模2相加，再將相加相加，再將相加結(jié)果分成結(jié)果分成8個(gè)個(gè)6 b的字：的字： B1B2 B8 = R Zi 32 b的的R擴(kuò)擴(kuò) 展展48 b的的R 48 b的的ZiS2S8S1交換交換 P 32 b f(R, Zi)第1個(gè)4 b的字第2個(gè)4 b的字第8個(gè)4 b的字第1個(gè)6 b的字第2個(gè)6 b的字第8個(gè)6 b的字22n每個(gè)每個(gè)6 b的字的字

27、 Bi 輸入到一個(gè)替代方框輸入到一個(gè)替代方框Si；后者用查表的方法；后者用查表的方法產(chǎn)生出一個(gè)產(chǎn)生出一個(gè)4 b的輸出的輸出Si(Bi)。 Si(Bi)是是6 b字字Bi的布爾函數(shù)。的布爾函數(shù)。n 8個(gè)輸出個(gè)輸出Si 輸入到交換方框輸入到交換方框P 。n交換所得就是所要求的交換所得就是所要求的32 b的函數(shù)的函數(shù)f(R, Zi) : f(R, Zi) PS1(B1)S2(B2)S8(B8)32 b的的R擴(kuò)擴(kuò) 展展48 b的的R 48 b的的ZiS2S8S1交換交換 P 32 b f(R, Zi)23密鑰進(jìn)程計(jì)算密鑰進(jìn)程計(jì)算 決定每個(gè)決定每個(gè)Zi所用的過(guò)程所用的過(guò)程n流程圖流程圖 n各各Zi使用密

28、鑰使用密鑰Z0的的不同子集。不同子集。 n密鑰密鑰Z0在位置在位置8, 16, , 64上有上有8個(gè)監(jiān)督個(gè)監(jiān)督比特，用于在對(duì)應(yīng)比特，用于在對(duì)應(yīng)的的8 b字節(jié)中進(jìn)行錯(cuò)字節(jié)中進(jìn)行錯(cuò)誤檢測(cè)。誤檢測(cè)。n“交換選擇交換選擇1”丟掉丟掉Z0的監(jiān)督比特。的監(jiān)督比特。n然后存入兩個(gè)然后存入兩個(gè)28 b的的移存器中。移存器中。64 b密鑰密鑰交換選擇交換選擇156 b密鑰密鑰28 b C028 b D0左左 移移左左 移移C1D1左左 移移左左 移移交換選擇交換選擇2C2D2左左 移移左左 移移交換選擇交換選擇2C16D16交換選擇交換選擇2移存器移存器Z1Z2Z1624n作作16次迭代運(yùn)算，每次迭代包括一次或

29、兩次循環(huán)左移，然次迭代運(yùn)算，每次迭代包括一次或兩次循環(huán)左移，然后進(jìn)行后進(jìn)行“交換選擇交換選擇2”。n輸出就是第輸出就是第1次至第次至第16次迭代用的不同的次迭代用的不同的48 b密鑰分組密鑰分組Z1, Z2, , Z16。64 b密鑰密鑰交換選擇交換選擇156 b密鑰密鑰28 b C028 b D0左左 移移左左 移移C1D1左左 移移左左 移移交換選擇交換選擇2C2D2左左 移移左左 移移交換選擇交換選擇2C16D16交換選擇交換選擇2移存器移存器Z1Z2Z162513.6.1 基本原理基本原理公共密鑰系統(tǒng)中，用兩種算法去計(jì)算兩個(gè)不可逆函數(shù)（變公共密鑰系統(tǒng)中，用兩種算法去計(jì)算兩個(gè)不可逆函數(shù)（

30、變換）。令這兩種算法用換）。令這兩種算法用Ez和和Dz表示：表示：Ez: fz(x) = y 公共密鑰（公鑰）公共密鑰（公鑰）Dz: fz-1(y) = x 秘密密鑰（私鑰）秘密密鑰（私鑰）式中，式中，x 在某個(gè)函數(shù)在某個(gè)函數(shù)fz的域中的一個(gè)輸入消息，的域中的一個(gè)輸入消息，y 在在fz取值范圍內(nèi)相應(yīng)的密文。取值范圍內(nèi)相應(yīng)的密文?；疽螅汉瘮?shù)基本要求：函數(shù)fz必須是一個(gè)單向函數(shù)。必須是一個(gè)單向函數(shù)。公鑰和私鑰的兩個(gè)基本性質(zhì)：公鑰和私鑰的兩個(gè)基本性質(zhì)：n消息被這對(duì)密鑰之一加密后，能夠用另一個(gè)密鑰解密。消息被這對(duì)密鑰之一加密后，能夠用另一個(gè)密鑰解密。n知道公鑰后，不可能計(jì)算出私鑰。知道公鑰后，不可

31、能計(jì)算出私鑰。將此系統(tǒng)的用戶姓名、地址和公鑰列于一本將此系統(tǒng)的用戶姓名、地址和公鑰列于一本“電話簿電話簿”中。中。當(dāng)一個(gè)用戶需要向另一個(gè)用戶發(fā)送保密消息時(shí)，查此當(dāng)一個(gè)用戶需要向另一個(gè)用戶發(fā)送保密消息時(shí)，查此“電話電話簿簿”，用對(duì)方的公鑰對(duì)消息加密。加密的消息只能由持有對(duì)，用對(duì)方的公鑰對(duì)消息加密。加密的消息只能由持有對(duì)應(yīng)私鑰的用戶閱讀。應(yīng)私鑰的用戶閱讀。 26 13.6.2 Diffie-Hellman 公共密鑰分配系統(tǒng)公共密鑰分配系統(tǒng)基本原理：令離散指數(shù)函數(shù)為基本原理：令離散指數(shù)函數(shù)為 Y = X mod p1 X p 1式中，式中， 一個(gè)整數(shù)，并且是一個(gè)本原元。一個(gè)整數(shù)，并且是一個(gè)本原元。因

32、此，因此，X是是Y的以的以 為底的模為底的模p離散對(duì)數(shù)：離散對(duì)數(shù)： X = log Y mod p 1 Y p 1使用使用“平方的乘積平方的乘積”法，很容易從法，很容易從X計(jì)算計(jì)算Y。例如，對(duì)于例如，對(duì)于X = 16，有，有Y = 16 = ( 2)222 另一方面，從另一方面，從Y計(jì)算計(jì)算X則難得多。則難得多。應(yīng)用方法：假定所有用戶都知道應(yīng)用方法：假定所有用戶都知道 和和p。n若有一用戶若有一用戶i，從一組整數(shù)，從一組整數(shù)1, 2, , p中，均勻地選擇一個(gè)中，均勻地選擇一個(gè)獨(dú)立隨機(jī)數(shù)獨(dú)立隨機(jī)數(shù)Xi，作為私鑰；并將離散指數(shù)，作為私鑰；并將離散指數(shù) Yi = Xi mod p 和用戶姓名及地址

33、一起放在和用戶姓名及地址一起放在“公共電話簿公共電話簿”中。其他用戶中。其他用戶也如此做。也如此做。27n假設(shè)用戶假設(shè)用戶i 和和 j 希望進(jìn)行保密通信。為此，用戶希望進(jìn)行保密通信。為此，用戶i 從從“公共公共電話簿電話簿”中取出中取出Yj，并用私鑰，并用私鑰Xi計(jì)算計(jì)算用戶用戶j 用同樣方法計(jì)算用同樣方法計(jì)算Kij。因?yàn)?。因?yàn)镵ji = Kij所以，用戶所以，用戶i和和j可將可將Kji 看作是普通保密系統(tǒng)中的密鑰?？醋魇瞧胀ūＣ芟到y(tǒng)中的密鑰。n敵方若想得到敵方若想得到Kji，必須用從，必須用從“公共電話簿公共電話簿”中得到的中得到的Yi和和Yj，按照下列公式去計(jì)算，按照下列公式去計(jì)算Kji：

34、上式因?yàn)榘x散對(duì)數(shù)故難于計(jì)算。上式因?yàn)榘x散對(duì)數(shù)故難于計(jì)算。 pppYKijijiXXXXXjjimodmodmodpYKiYjjimodlog2813.7.1 RSA公共密鑰密碼系統(tǒng)公共密鑰密碼系統(tǒng)基本原理：基本原理：RSA算法是一種分組密碼，其理論基礎(chǔ)是，求出算法是一種分組密碼，其理論基礎(chǔ)是，求出一個(gè)隨機(jī)的大素?cái)?shù)不難，但是將兩個(gè)這種數(shù)的乘積分解因子一個(gè)隨機(jī)的大素?cái)?shù)不難，但是將兩個(gè)這種數(shù)的乘積分解因子目前認(rèn)為是不可能的。目前認(rèn)為是不可能的。算法：算法：n隨機(jī)選擇兩個(gè)很大的素?cái)?shù)隨機(jī)選擇兩個(gè)很大的素?cái)?shù)p和和q，p q；n將將p和和q相乘，得到乘積相乘，得到乘積pq = n n使用下式求出歐拉

35、函數(shù)使用下式求出歐拉函數(shù) (n): (n) = (p 1)(q 1)n從歐拉函數(shù)從歐拉函數(shù)(n)的定義可知，上式給出小于的定義可知，上式給出小于n的正整數(shù)的正整數(shù)i的的數(shù)目，且數(shù)目，且i和和n的最大公因子等于的最大公因子等于1，即，即i和和n互為素?cái)?shù)?；樗?cái)?shù)。例：設(shè) p3，q5，則n15，(n) = (3-1)(5-1) = 8。它表示小于15且和15互素的正整數(shù)i共有8個(gè)；它們是：1，2，4，7，8，11，13，14。29n令令e是一個(gè)小于是一個(gè)小于(n)的正整數(shù)，它使的正整數(shù)，它使e和和(n)的最大公因子等于的最大公因子等于1。這樣，求出一個(gè)小于這樣，求出一個(gè)小于(n)的正整數(shù)的正整數(shù)d，它使，它使de 1 mod(n)nRSA的單向函數(shù)由計(jì)算下式中的離散指數(shù)定義：的單向函數(shù)由計(jì)算下