第講數(shù)據(jù)加密算法優(yōu)秀文檔

《數(shù)據(jù)通信與計算機網(wǎng)絡(luò)（第二版）》電子教案 笫卄八講 數(shù)據(jù)加密算法本講內(nèi)容第十章網(wǎng)絡(luò)管理與信息安全

10.3數(shù)據(jù)加密算法

10.3.2對稱密鑰算法

10.3.3公開密鑰算法

10.3.2對稱密鑰算法基本原理舉例說明假設(shè)Alice和Bob使用對稱密鑰進行通信，則：Alice和Bob同意使用同一個密碼系統(tǒng)；Alice和Bob同意使用同一個密鑰；Alice取她的明文，用加密算法和密鑰加密明文信息，產(chǎn)生一個密文信息；Alice發(fā)密文給Bob；Bob用相同的算法和密鑰解密密文信息然后閱讀。10.3.2對稱密鑰算法（續(xù)）在Alice和Bob之間有一個竊聽者Eve，他只竊聽到步驟（4）的傳輸，則他必須試圖對密文進行密碼分析。但是，如果Eve知道步驟（1）和（2），他就成功了。用對稱算法，Alice和Bob可以公開完成步驟（1），但必須秘密地完成步驟（2）。協(xié)議前后及執(zhí)行當中，密鑰必須保待安全；否則，信息將不安全。10.3.2對稱密鑰算法（續(xù)）DES算法DES基本構(gòu)架10.3.2對稱密鑰算法（續(xù)）基本概念：DES使用相同的算法來對數(shù)據(jù)進行加密和解密，所使用的加密密鑰和解密密鑰是相同的，算法的輸入有64位的明文，使用56位的密鑰，輸出是64位的密文，它使用16輪的混合操作，目標是徹底地打亂明文的信息，使得密文的每一位都依賴于明文的每一位和密鑰的每一位。算法的組成：10.3.2對稱密鑰算法（續(xù)）共有19個階段；第一個階段是一個與密鑰無關(guān)的變換；最后一個階段是第一個階段的反向變換；最后第二個階段是對左右32位進行交換的簡單變換；其它16個階段在功能上是相同的，但是它們的參數(shù)是密鑰的不同的函數(shù)。中間階段過程如下圖所示：10.3.2對稱密鑰算法（續(xù)）DES中間變換過程DES加密標準L0R0L1=R0IPL2=R1L15=R14R1=L0f(R0,K1)R2=L1f(R1,K2)R15=L14f(R14,K15)L16=R15R16=L15f(R15,K16)IP1fff輸出密文Y(64bit)明文X(64bit)輸入K16(48bit)K2(48bit)K1(48bit)X0的左半邊

(32bit)X0(64bit)X0的右半邊(32bit)R16L16(64bit)10.3.2對稱密鑰算法（續(xù)）每一輪的關(guān)鍵是f函數(shù)，以及這一階段的子密鑰Ki，用來產(chǎn)生右邊的32位的輸出，這個函數(shù)有四個步驟：把Ri-1按預(yù)先規(guī)定的規(guī)則擴展成48位的Ei

321234545678989101112131213141516171617181920212021222324252425262728292829303132110.3.2對稱密鑰算法（續(xù)）進行Ei

Ki操作（異或）把上一步的結(jié)果分為6位的小組，共8組，記為B1到B8，每一組通過各自的S-Box形成4位的輸出。具體做法如下（參見書上表格）：把Bj的前一位和最后一位組合的數(shù)值記為m，把Bj的第2位到第5位組成的數(shù)值記為n，這個（n,m）數(shù)對用來選擇S-Box的行和列，產(chǎn)生一個新的4位輸出。S-Box與Bj相對應(yīng)，共有8個。10.3.2對稱密鑰算法（續(xù)）上述8組4位輸出（共32位）通過一個變換，產(chǎn)生32位的輸出，如下所示：167202129122817115232651831102824143227391913306221142510.3.2對稱密鑰算法（續(xù)）

Ki的計算方法如下：

把帶奇偶校驗位的64位密鑰舍棄其中的奇偶校驗位，根據(jù)下表進行變位得到56位的密鑰，在變位時，奇偶校驗位已被舍棄。即56位密鑰的第1位是原64位密鑰的第57位，第2位是原64位密鑰的第49位等等，直到第56位為原64位密鑰的第4位。5749413325179158504234261810259514335271911360524436635547393123157625446383022146615345372921135282012410.3.2對稱密鑰算法（續(xù)）把56位的密鑰分成兩個部分，前面的28位稱為C0，后面的28位稱為D0，

和是對和按如下左移產(chǎn)生：再把按如下變換產(chǎn)生：輪數(shù)(i)12345678910111213141516左移位數(shù)1122222212222221具體做法如下（參見書上表格）：這表明：私有密鑰和公開密鑰具有互換性，即公開密鑰與私有密鑰只是概念的不同，其實質(zhì)是沒有區(qū)別的。明文X(64bit)作為解密指數(shù)。解密密鑰是接收者專用的秘密密鑰，對其他人都保密。Alice和Bob同意使用同一個密鑰；再把按如下變換產(chǎn)生：算法中的反向變換方法如下：R16L16(64bit)EPK(DSK(X))X3公開密鑰算法（續(xù)）用公開密鑰加密時，先計算K2(48bit)K1(48bit)在Alice和Bob之間有一個竊聽者Eve，他只竊聽到步驟（4）的傳輸，則他必須試圖對密文進行密碼分析。數(shù)據(jù)加密中，有一個比較重要的問題需要解決，即如何把密鑰送到對方，由對方來進行解密。用戶把加密密鑰公開，使得系統(tǒng)中任何其他用戶都可使用，而對解密密鑰中的d則保密。10.3.2對稱密鑰算法（續(xù)）1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932同樣是指的第1位是

的第14位，

的第2位是

的第17位等等，直到

的第48位為

的第32位。10.3.2對稱密鑰算法（續(xù)）整個算法的初始變換方法如下：算法中的反向變換方法如下：

58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157DES

的保密性DES

的保密性僅取決于對密鑰的保密，而算法是公開的。盡管人們在破譯DES方面取得了許多進展，但至今仍未能找到比窮舉搜索密鑰更有效的方法。DES是世界上第一個公認的實用密碼算法標準，它曾對密碼學(xué)的發(fā)展做出了重大貢獻。目前較為嚴重的問題是DES的密鑰的長度。現(xiàn)在已經(jīng)設(shè)計出來搜索DES密鑰的專用芯片。

三重DES

(TripleDES)三重DES使用兩個密鑰，執(zhí)行三次DES算法。下圖中的方框E和D分別表示執(zhí)行加密和解密算法。因此加密時是E-D-E，解密時是D-E-D。EDEK1K2K1明文密文DEDK1K2K1密文明文加密解密10.3.2對稱密鑰算法（續(xù)）在加密或解密過程中，如果需要加密的明文信息超過64位，這時，可以采用四種方式：電碼薄方式（ECB：ElectronicCodeBook）；密碼塊鏈方式（CBC：CipherBlockChaining）；密碼反饋方式（CFB：CipherFeedBack）；輸出反饋方式（OFB：OutputFeedBack）10.3.2對稱密鑰算法（續(xù)）Rijndael算法步驟：在初始塊和密鑰之間進行逐位異或，加密第1輪的輸入，結(jié)果稱為狀態(tài)（state）。接著進行10輪類似的運算，每一輪都用特定的矩陣操作來改變它的輸入，從而產(chǎn)生輸出狀態(tài)（本質(zhì)上是另一個矩陣），并以此作為下一輪活動的輸入如果塊或密鑰大小更大，需要更多輪次，但是基本的步驟還是一樣的。10.3.3公開密鑰算法公開密鑰密碼體制使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導(dǎo)出解密密鑰在計算上是不可行的”密碼體制。公開密鑰密碼體制的產(chǎn)生主要是因為兩個方面的原因，一是由于常規(guī)密鑰密碼體制的密鑰分配問題，另一是由于對數(shù)字簽名的需求?，F(xiàn)有三種公開密鑰密碼體制，其中最著名的是RSA體制，它基于數(shù)論中大數(shù)分解問題的體制，由美國三位科學(xué)家Rivest,Shamir和Adleman于1976年提出并在1978年正式發(fā)表的加密密鑰與解密密鑰在公開密鑰密碼體制中，加密密鑰(即公開密鑰)PK是公開信息，而解密密鑰(即秘密密鑰)SK是需要保密的。加密算法E和解密算法D也都是公開的。雖然秘密密鑰SK是由公開密鑰PK決定的，但卻不能根據(jù)PK計算出SK。應(yīng)當注意任何加密方法的安全性取決于密鑰的長度，以及攻破密文所需的計算量。在這方面，公開密鑰密碼體制并不具有比傳統(tǒng)加密體制更加優(yōu)越之處。由于目前公開密鑰加密算法的開銷較大，在可見的將來還看不出來要放棄傳統(tǒng)的加密方法。公開密鑰還需要密鑰分配協(xié)議，具體的分配過程并不比采用傳統(tǒng)加密方法時更為簡單。公開密鑰算法的特點(1)發(fā)送者用加密密鑰PK對明文X加密后，在接收者用解密密鑰SK解密，即可恢復(fù)出明文，或?qū)憺椋?/p>

DSK(EPK(X))X(9-5)解密密鑰是接收者專用的秘密密鑰，對其他人都保密。此外，加密和解密的運算可以對調(diào)，即

EPK(DSK(X))X公開密鑰算法的特點(2)加密密鑰是公開的，但不能用它來解密，即

DPK(EPK(X))X(9-6)(3)在計算機上可容易地產(chǎn)生成對的PK和SK。(4)從已知的PK實際上不可能推導(dǎo)出SK，即從PK到SK是“計算上不可能的”。(5)加密和解密算法都是公開的。公開密鑰密碼體制接收者發(fā)送者E加密算法D解密算法加密密鑰PK解密密鑰SK明文X密文Y=EPK(X)密鑰對產(chǎn)生源明文X=DSK(EPK(X))9.3.2RSA公開密鑰密碼體制RSA公開密鑰密碼體制所根據(jù)的原理是：根據(jù)數(shù)論，尋求兩個大素數(shù)比較簡單，而將它們的乘積分解開則極其困難。每個用戶有兩個密鑰：加密密鑰PK{e,n}和解密密鑰SK{d,n}。用戶把加密密鑰公開，使得系統(tǒng)中任何其他用戶都可使用，而對解密密鑰中的d則保密。N為兩個大素數(shù)p和q之積（素數(shù)p和q一般為100位以上的十進數(shù)），e和d滿足一定的關(guān)系。當敵手已知e和n時并不能求出d。(1)加密算法若用整數(shù)X表示明文，用整數(shù)Y表示密文（X和Y均小于n），則加密和解密運算為：加密：YXemodn(9-7)

解密：XYdmodn(9-8)(2)密鑰的產(chǎn)生①計算n。用戶秘密地選擇兩個大素數(shù)p和q，計算出n

pq。n稱為RSA算法的模數(shù)。明文必須能夠用小于n的數(shù)來表示。實際上n是幾百比特長的數(shù)。②計算(n)。用戶再計算出n的歐拉函數(shù)(n)(p

1)(q

1)(9-9)(n)定義為不超過n并與n互素的數(shù)的個數(shù)。③選擇e。用戶從[0,(n)1]中選擇一個與(n)互素的數(shù)e作為公開的加密指數(shù)。在加密或解密過程中，如果需要加密的明文信息超過64位，這時，可以采用四種方式：Ki的計算方法如下：這表明：私有密鑰和公開密鑰具有互換性，即公開密鑰與私有密鑰只是概念的不同，其實質(zhì)是沒有區(qū)別的。這表明：私有密鑰和公開密鑰具有互換性，即公開密鑰與私有密鑰只是概念的不同，其實質(zhì)是沒有區(qū)別的。接著進行10輪類似的運算，每一輪都用特定的矩陣操作來改變它的輸入，從而產(chǎn)生輸出狀態(tài)（本質(zhì)上是另一個矩陣），并以此作為下一輪活動的輸入數(shù)據(jù)加密算法RSA公開密鑰密碼體制所根據(jù)的原理是：根據(jù)數(shù)論，尋求兩個大素數(shù)比較簡單，而將它們的乘積分解開則極其困難。因此加密時是E-D-E，解密時是D-E-D。假設(shè)明文為P，加密算法（包括密鑰）為E，解密算法（包括密鑰）為D，要求滿足以下三個條件：的第17位等等，直到的第48位為的第32位。(2)加密密鑰是公開的，但不能用它來解密，即⑤得出所需要的公開密鑰和秘密密鑰：R16L16(64bit)(2)密鑰的產(chǎn)生（續(xù)）④計算d。用戶計算出滿足下式的d

edmod(n)=1(9-10)

作為解密指數(shù)。⑤得出所需要的公開密鑰和秘密密鑰：公開密鑰（即加密密鑰）PK{e,n}

秘密密鑰（即解密密鑰）SK{d,n}(3)正確性的例子說明設(shè)選擇了兩個素數(shù)，p

7,q

17。計算出n

pq

717119。計算出(n)(p

1)(q

1)96。從[0,95]中選擇一個與96互素的數(shù)e。選e

5。然后根據(jù)(9-10)式，

5dmod96=1解出d。不難得出，d

77,因為ed

57738549611mod96。于是，公開密鑰PK(e,n){5,119},

秘密密鑰SK{77,119}。(3)正確性的例子說明（續(xù)）對明文進行加密。先把明文劃分為分組，使每個明文分組的二進制值不超過n,即不超過119。設(shè)明文X19。用公開密鑰加密時，先計算

Xe

195

2476099。再除以119，得出商為20807，余數(shù)為66。這就是對應(yīng)于明文19的密文Y的值。在用秘密密鑰SK{77,119}進行解密時，先計算

Yd

6677

1.27...10140。再除以119，得出商為1.06...10138，余數(shù)為19。此余數(shù)即解密后應(yīng)得出的明文X。RSA算法舉例明文

1919==20807公開密鑰={5,119}加密52476099119及余數(shù)

66密文

6610秘密密鑰={77,119}解密771.27...10119及余數(shù)

19

明文

1914013810.3.3公開密鑰算法問題的提出數(shù)據(jù)加密中，有一個比較重要的問題需要解決，即如何把密鑰送到對方，由對方來進行解密。不管一個加密方法如何強壯，一旦解密密鑰被入侵者獲得，那么加密也就沒有意義。公開密鑰算法

體制思想： 要求密鑰成對出現(xiàn)，一個為加密密鑰(Ke)，另一個為解密密鑰(Kd)，加密密鑰和解密密鑰不同，且不可能從其中一個推導(dǎo)出另一個。P=D(d,E(e,P))（1）對P加密就是計算C=Pemodn2)若取d=27,則最小的e是多少?第十章網(wǎng)絡(luò)管理與信息安全具體做法如下（參見書上表格）：每一輪的關(guān)鍵是f函數(shù)，以及這一階段的子密鑰Ki，用來產(chǎn)生右邊的32位的輸出，這個函數(shù)有四個步驟：且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。把上一步的結(jié)果分為6位的小組，共8組，記為B1到B8，每一組通過各自的S-Box形成4位的輸出。3公開密鑰算法（續(xù)）密碼反饋方式（CFB：CipherFeedBack）；算法中的反向變換方法如下：然后根據(jù)(9-10)式，(3)正確性的例子說明這表明：私有密鑰和公開密鑰具有互換性，即公開密鑰與私有密鑰只是概念的不同，其實質(zhì)是沒有區(qū)別的。在這方面，公開密鑰密碼體制并不具有比傳統(tǒng)加密體制更加優(yōu)越之處。第一個階段是一個與密鑰無關(guān)的變換；10.3.3公開密鑰算法（續(xù)）假設(shè)明文為P，加密算法（包括密鑰）為E，解密算法（包括密鑰）為D，要求滿足以下三個條件：D(E(P))=P；從E推導(dǎo)D是極其困難的；E不能通過部分明文來解破。優(yōu)點： 不需要經(jīng)安全渠道傳遞密鑰，大大簡化了密鑰管理。10.3.3公開密鑰算法（續(xù)）RSA算法理論基礎(chǔ)即將兩個大的質(zhì)數(shù)合成一個大數(shù)很容易，而相反的過程則非常困難。在當今技術(shù)條件下，當n足夠大時，欲從n中通過質(zhì)因子分解試圖找到與d對應(yīng)的p、q是極其困難甚至是不可能的。例如：分解一個200位的整數(shù)需要40億年的計算機時間，而分解一個500位的整數(shù)需要1025年的計算機時間10.3.3公開密鑰算法（續(xù)）步驟：選擇兩個大整數(shù)p和q，一般要求大于10100；計算n=pq和z=(p-1)(q-1)；選擇一個與z互素的整數(shù)，記為d；計算滿足下列條件的e，（ed）modz=1加密：把待加密的明文分割成一定大小的塊P，這個P可以看成是一個整數(shù)，要求0Pn，我們可以把P的長度設(shè)為k，則要求2k<n。對P加密就是計算C=Pemodn10.3.3公開密鑰算法（續(xù)）解密： 解密計算P=Cdmodn

注意： 為了加密，我們需要e和n，為了解密，我們需要d和n，這樣，加密密鑰（即公開密鑰）為（e，n），解密密鑰（即秘密密鑰）為（d，n）。舉例說明假設(shè)p=3，q=11；=>n=33，z=2010.3.3公開密鑰算法（續(xù)）選擇與20互素的d=7；對于e，要求7emod20=1，可以選擇e=3。加密過程為C=P3mod33，解密為P=C7mod33。