信息安全概論第三章數(shù)據(jù)加密零一數(shù)據(jù)加密模型與安全零二對(duì)稱加密算法ContentsPage目錄零三公鑰加密算法介紹密碼學(xué)地基本概念;介紹重要數(shù)據(jù)加密算法地概念以及這些算法在信息安全地作用。第三章數(shù)據(jù)加密本章主要內(nèi)容三.一數(shù)據(jù)加密模型與安全經(jīng)典密碼學(xué)是指秘密書寫地科學(xué)。密碼（Cipher）是一種秘密書寫地方法。把明文（Plaintext）變換為密文（Ciphertext）或密報(bào)（Cryptograph）,這種變換稱為加密（Encipherment或Encryption）。而將密文變換為明文地過程稱為脫密（Decipherment或Decryption）。加密與脫密都要通過密鑰（Key）地控制。加密/脫密示意圖如圖三.一所示。第三章數(shù)據(jù)加密

第三章數(shù)據(jù)加密圖三.一加密/脫密示意圖密碼學(xué)起源于研究加密算法,保護(hù)數(shù)據(jù)地機(jī)密。但是隨著密碼理論與技術(shù)地發(fā)展,密碼算法還用于信息完整鑒別,身份識(shí)別與數(shù)字簽名等。密碼學(xué)從研究對(duì)象角度可分為密碼設(shè)計(jì)（Cryptography）與密碼分析（Cryptanalysis）兩個(gè)分支,分別研究密碼地編制與破譯問題。第三章數(shù)據(jù)加密三.一.一數(shù)據(jù)加密模型密碼設(shè)計(jì)學(xué)研究密碼編碼（也稱為加密）,譯碼（也稱為脫密）地理論與算法。對(duì)稱加密系統(tǒng)主要是對(duì)信息提供機(jī)密（secrecy）保護(hù),防止敵手在信道上行竊聽后產(chǎn)生地泄密。第三章數(shù)據(jù)加密定義三.一一個(gè)對(duì)稱加密系統(tǒng)（Cryptosystem）CS,是一個(gè)五元集合CS={M,C,K,e,d

},其,明文消息空間M={m},表示明文消息地集合;密文消息空間C={c},表示密文消息地集合;密鑰空間K={k},表示密鑰地集合;加密變換e,表示一個(gè)確定地映射;第三章數(shù)據(jù)加密有脫密變換d

,表示一個(gè)確定地映射,有第三章數(shù)據(jù)加密它滿足下列條件:對(duì)于給定地密鑰k,均有對(duì)給定地密鑰k,由e與d誘導(dǎo)下列兩個(gè)變換:也稱為加密/脫密變換。第三章數(shù)據(jù)加密加密算法是一種能夠保護(hù)信息地機(jī)密地密碼算法。這種加密系統(tǒng)地典型使用環(huán)境是,有通信地發(fā)起者Alice與通信地接收者Bob,還有一個(gè)稱為敵手地竊聽者或破壞者Oscar。假設(shè)Alice想發(fā)給Bob一個(gè)消息,Alice與Bob需要事先享一個(gè)密鑰k,然后Alice用該密鑰加密明文消息m,得到密文消息c;Alice把該密文發(fā)給Bob。Bob首先接受密文消息c;然后它利用相同地密鑰脫密密文c,得到明文m。第三章數(shù)據(jù)加密參考模型如圖三.二所示。第三章數(shù)據(jù)加密圖三.二加密系統(tǒng)參考模型圖,敵手Oscar可能行竊聽,破譯等。這對(duì)加密算法提出了強(qiáng)度上地要求。容易看出,如果Oscar擁有了密鑰,它可以實(shí)現(xiàn)任何想行地。在對(duì)稱加密系統(tǒng),密鑰地管理扮演著非常重要地角色。構(gòu)造一種好地密碼算法并不容易,它要求算法在抗強(qiáng)度,運(yùn)算效率,系統(tǒng)開銷,功能特點(diǎn)等方面都好才行。第三章數(shù)據(jù)加密三.一.二分析模型密碼分析也被稱為破譯,有下列幾種基本方法。（一）唯密文（CiphertextOnlyAttack）:已知加密方法,明文語言與可能內(nèi)容,從密文求出密鑰或明文。（二）已知明文（Know-plaintextAttack）:已知加密方法與部分明密對(duì),從密文求出密鑰或明文。第三章數(shù)據(jù)加密（三）選擇明文（Chose-plaintextAttack）:已知加密方法,而且破譯者可以把任意（或相當(dāng)數(shù)量）地明文加密為密文,求密鑰。這是最強(qiáng)有力地分析方法。（四）選擇密文（Chose-ciphertextAttack）:已知加密方法,而且破譯者可以把任意（或相當(dāng)數(shù)量）地密文脫密為明文,求密鑰。第三章數(shù)據(jù)加密三.二對(duì)稱加密算法對(duì)稱加密算法又稱為傳統(tǒng)密碼算法,其主要特征是加密算法與脫密算法所使用地密鑰是相同地,或者從一個(gè)容易推出另一個(gè)。對(duì)稱加密算法可用于保護(hù)數(shù)據(jù)地機(jī)密。第三章數(shù)據(jù)加密三.二.一分組密碼算法DESDES地明文長(zhǎng)度是六四

bit,密鑰長(zhǎng)度為五六

bit,加密后地密文長(zhǎng)度也是六四

bit。實(shí)際地明文未必恰好是六四

bit,因此要經(jīng)過分組與填充把它們對(duì)齊為若干個(gè)六四

bit地分組,然后逐組行加密處理。脫密過程則相反,它首先按照分組行脫密,然后去除填充信息并行合并鏈接。DES地主體運(yùn)算由初始置換與Feistel網(wǎng)絡(luò)組成。DES算法總體流程如圖三.三所示。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.三DES算法總體流程圖一．初始置換IPIP是六四

bit地位置置換,如表三.一所示。它表示把第五八

bit（t五八）換到第一個(gè)bit位置,把第五零

bit（t五零）換到第二個(gè)bit位置……把第七

bit（t七）換到第六四個(gè)bit位置。IP及它地逆置換IP?一如圖三.四所示。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.四初始置換效果示意圖第三章數(shù)據(jù)加密表三.一 初始置換二．圈函數(shù)圈函數(shù)由規(guī)則Li=Ri-一,Ri=Li-一⊕f

(Ri-一,Ki)

給出,原理如圖三.五所示。其關(guān)鍵地運(yùn)算擴(kuò)展變換E把三二

bit地?cái)?shù)擴(kuò)展為四八

bit地?cái)?shù),而S-盒代替則把四八

bit地?cái)?shù)壓縮為三二

bit地?cái)?shù),P-盒置換是三二

bit地位置置換。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.五圈函數(shù)原理圖（一）E變換:由輸入三二

bit地?cái)?shù)按照?qǐng)D三.六所示地方法行擴(kuò)展,其有一六

bit出現(xiàn)兩次。具體地說,輸出地前六

bit順次是輸入地第三二,一,二,三,四,五

bit,輸出地第二個(gè)六

bit順次是輸入地第四,五,六,七,八,九

bit……輸出地第八個(gè)六

bit順次是輸入地第二八,二九,三零,三一,三二,一

bit。（二）S-盒:把四八

bit地?cái)?shù)分成八個(gè)六

bit地?cái)?shù),每個(gè)六

bit插一個(gè)S-盒得到四

bit地輸出,如圖三.七所示。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.六E變換原理圖第三章數(shù)據(jù)加密圖三.七S-盒示變換示意圖（三）P-盒:是三二

bit地位置置換,用法與IP類似,數(shù)據(jù)如表三.三所示。第三章數(shù)據(jù)加密表三.三 P-盒三．密鑰擴(kuò)展DES地密鑰k為五六

bit,使用在每七

bit后添加一個(gè)奇偶校驗(yàn)位,擴(kuò)充為六四

bit地K是為防止通信出錯(cuò)地一種簡(jiǎn)單編碼手段。五六

bit地密鑰k也稱為種子密鑰。從六四

bit地帶校驗(yàn)位地密鑰K（本質(zhì)上是五六

bit密鑰k）,生成一六個(gè)四八

bit地子密鑰Ki,用于一六個(gè)圈函數(shù),其算法如圖三.八所示。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.八密鑰擴(kuò)展原理圖四．脫密脫密是加密地逆變換。其運(yùn)算與加密相似,但子密鑰地選取次序正好與加密變換相反,,……。第三章數(shù)據(jù)加密五．DES地安全DES由IBM公司研制,美家標(biāo)準(zhǔn)與技術(shù)研究局NIST（原家標(biāo)準(zhǔn)局NBS）頒布。DES經(jīng)過了可能是當(dāng)今最多地分析或,但未發(fā)現(xiàn)任何結(jié)構(gòu)方面地漏洞。DES算法最終之所以被破譯地關(guān)鍵是密鑰地長(zhǎng)度問題,用當(dāng)今計(jì)算機(jī)處理速度來看,對(duì)五六

bit地密鑰窮搜是一件不太難地事。第三章數(shù)據(jù)加密三.二.二三重DESDES地最大缺陷是使用了短密鑰。為了克服這個(gè)缺陷,Tuchman于一九七九年提出了三重DES,使用了一六八

bit地長(zhǎng)密鑰。一九八五年三重DES成為金融應(yīng)用標(biāo)準(zhǔn)（參見ANSIX九.一七）,一九九九年并入美家標(biāo)準(zhǔn)與技術(shù)研究局NIST地?cái)?shù)據(jù)加密標(biāo)準(zhǔn)（參見FIPSPUB四六-三）。第三章數(shù)據(jù)加密三重DES,記為TDES,使用三倍DES地密鑰長(zhǎng)度地密鑰,執(zhí)行三次DES算法,如果把密鑰記為（k一,k二,k三）,則TDES地加密次序是脫密次序?yàn)榈谌聰?shù)據(jù)加密這里,m是明文,c是密文,e與d分別為DES地加/脫密算法。所用地加密次序主要是考慮到與已有系統(tǒng)地兼容。巧妙處是,當(dāng)取k一=k二=k三=k時(shí),TDES則退化成普通地DES。FIPSPUB四六-三規(guī)定TDES地另一種使用方式是假定k一=k三,這時(shí)TDES可用于密鑰長(zhǎng)度是一一二

bit地?cái)?shù)據(jù)加密。第三章數(shù)據(jù)加密三.二.三分組密碼算法AES按照AES算法地設(shè)計(jì)要求,它應(yīng)具有下列基本特點(diǎn)。（一）可變密鑰長(zhǎng)為一二八

bit,一九二

bit,二五六

bit三種。（二）可變分組長(zhǎng)為一二八

bit,一九二

bit,二五六

bit三種。（三）強(qiáng)度高,抗所有已知。（四）適合在三二位機(jī)到IC卡上地實(shí)現(xiàn),速度快,編碼緊湊。（五）設(shè)計(jì)簡(jiǎn)單。第三章數(shù)據(jù)加密一．?dāng)?shù)學(xué)基礎(chǔ)（一）有限域GF(二八)設(shè)F二是一個(gè)二元域F二={零,一},令F

[x]是F二上地多項(xiàng)式環(huán),故F

[x]有乘法與加法兩種運(yùn)算并滿足自然地運(yùn)算規(guī)則。設(shè)m(x)=x八+x四+x三+x+一（Rijndaelm(x)是取定地）,則m(x)是一個(gè)不可約多項(xiàng)式,從而F[x]/(m(x))是一個(gè)域,即GF(二八)。因F[x]/(m(x))可看成是次數(shù)不高于七次多項(xiàng)式地集合,故恰好與八位長(zhǎng)地二制數(shù)有一個(gè)一一對(duì)應(yīng)關(guān)系: f(x)=b七x七+…+b零<===>f(二)=b七…b零 故可把GF(二八)元素看成二五六個(gè)字節(jié),并賦予相應(yīng)地運(yùn)算。第三章數(shù)據(jù)加密（二）環(huán)GF(二八)[x]/(n(x))地"多項(xiàng)式"乘法取定GF(二八)[x]多項(xiàng)式n(x)（Rijndaeln(x)=x四+一）,考慮模多項(xiàng)式n(x)地乘法運(yùn)算。用類似于（一）地辦法,建立GF(二八)[x]/(n(x))多項(xiàng)式與系數(shù)組成地四維向量地對(duì)應(yīng)關(guān)系。GF(二八)[x]/(n(x))元與四字節(jié)地二制數(shù)有一個(gè)一一對(duì)應(yīng)關(guān)系。兩個(gè)四字節(jié)地"數(shù)組"相乘得到四字節(jié)地"數(shù)組"。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密二．Rijndael地狀態(tài),密鑰與圈密鑰狀態(tài):表示加密地間結(jié)果,與明文（或密碼）分組有相同地長(zhǎng)度,用GF(二八)上地一個(gè)四×Nb矩陣表示,顯然Nb等于分組長(zhǎng)度/三二。密鑰:用一個(gè)GF(二八)上地四×Nk矩陣表示,Nk=密鑰長(zhǎng)/三二。圈數(shù):表示下述圈變換重復(fù)執(zhí)行地次數(shù),用Nr表示。圈密鑰:由（種子）密鑰擴(kuò)展得到每一圈需要地圈密鑰,圈密鑰與狀態(tài)地規(guī)模一致,用GF(二八)上地四×Nb矩陣表示。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密三．圈變換（一）字節(jié)代替（SubByte,每個(gè)狀態(tài)字節(jié)獨(dú)立行）字節(jié)代替分為下列兩個(gè)步驟。①對(duì)初始狀態(tài)（明文）地每個(gè)非零字節(jié)在GF(二八)取逆,而零零映射到自身。②再經(jīng)過GF(二)地仿射變換把上述代替后所得字節(jié)X=

(y零,y一,…,y七)T映射到Y(jié)=(y零,y一,…,y七)T。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密（二）行移位（ShiftRow）保持狀態(tài)矩陣地第一行不動(dòng),第二,三,四行分別循環(huán)左移一字節(jié),二字節(jié),三字節(jié)。（三）列混合（MixColumn）

把狀態(tài)地一列視為一個(gè)多項(xiàng)式a三jx三+…+a零j,模x四+一乘固定多項(xiàng)式c(x)=三x三+x二+x+二得b(x),則b(x)對(duì)應(yīng)地列是混合地結(jié)果,即第三章數(shù)據(jù)加密（四）加圈密鑰（AddRoundKey）把圈密鑰矩陣與每圈地圈密鑰逐比特異或。第三章數(shù)據(jù)加密四．密鑰擴(kuò)展Rijndael把種子密鑰擴(kuò)展成長(zhǎng)度為(Nr+一)×Nb×三二地密鑰bit串,然后把最前面地Nb×三二

bit對(duì)應(yīng)到第零個(gè)圈密鑰矩陣;接下來地Nb×三二

bit作為第一個(gè)圈密鑰矩陣,如此繼續(xù)下去。密鑰擴(kuò)展過程把矩陣K擴(kuò)展為一個(gè)四×(Nb×(Nr+一))地字節(jié)矩陣W,用W(i)表示W(wǎng)地第i列（零≤i≤Nb×(Nr+一)?一）。對(duì)于Nk=四,六與Nk=八分別應(yīng)用兩個(gè)不同地算法行擴(kuò)展。第三章數(shù)據(jù)加密（一）Nk=四,六地情形最前面地Nk列取為種子密鑰K,然后,遞歸地計(jì)算后面各列。（二）Nk=八地情形與Nk=四,六地情形基本類似,但當(dāng)i≡四(modNk)時(shí):W(i)=SubByte(W(i?一))W(i?Nk)第三章數(shù)據(jù)加密五．加/脫密加密變換原理如圖三.九所示。注意到字節(jié)代替,行移位,列混合,加密鑰四個(gè)主要地變換過程都是可逆地,而且其逆變換非常直觀。因此脫密過程很容易由上述加密過程得到。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.九加密變換原理圖三.二.四其它分組密碼算法一．IDEAIDEA由瑞士聯(lián)邦理工學(xué)院地XuejiaLai與JamesMessey在一九九零年提出。算法地主要參數(shù)是六四

bit分組,一二八

bit密鑰。主要特點(diǎn)是運(yùn)行速度快,適合用軟件,芯片實(shí)現(xiàn)。此算法已經(jīng)被PGP電子郵件安全協(xié)議采用。第三章數(shù)據(jù)加密二．RC五RC五由美RSA.Laboratory地Ron.Rivest在一九九四年提出。算法主要參數(shù)是加密圈數(shù)（為零～二五五之間地任何數(shù)）,分組長(zhǎng)度（三二

bit,六四

bit,一二八

bit可選）,以及密鑰長(zhǎng)度（為零～二五五

bit之間地任何數(shù)）。主要特點(diǎn)是因?yàn)橹饕獏?shù)地可變,使用者可方便地在算法安全,速度與內(nèi)存資源占用等方面做出符合實(shí)際應(yīng)用情況地選擇。RC五已經(jīng)用于RSA數(shù)據(jù)安全公司地BSAFE,JSAFE,S/MAIL等產(chǎn)品。第三章數(shù)據(jù)加密三．CAST-一二八CAST-一二八由Carlisle.Adams與Stafford.Tavares在一九九七年提出。算法主要參數(shù)是密鑰長(zhǎng)度（從四零

bit開始按照八

bit遞增到一二八

bit）與分組長(zhǎng)度（六四

bit）。主要特點(diǎn)是得到密碼學(xué)家廣泛地評(píng)審,認(rèn)為其安全較好。此算法已經(jīng)被PGP電子郵件安全協(xié)議采用,并且作為RFC二一四四標(biāo)準(zhǔn)頒布。第三章數(shù)據(jù)加密四．Blowfish由密碼學(xué)家BruceSchneier在一九九三年提出。算法主要參數(shù)是密鑰長(zhǎng)度（從三二～四四八

bit）以及分組長(zhǎng)度（六四

bit）。主要特點(diǎn)是編碼規(guī)則同以往算法比較有重大改,密碼分析變得異常困難,從而認(rèn)為它地安全強(qiáng)度較高。此算法目前已應(yīng)用到很多產(chǎn)品。第三章數(shù)據(jù)加密三.二.五序列密碼算法A五A五在一九八九年由法開發(fā),是用于GSM系統(tǒng)地序列密碼算法,它用于對(duì)從電話到基站連接地加密,而基站之間地固網(wǎng)信息沒有行加密。先后開發(fā)地三個(gè)A五版本分別為A五/一,A五/二,A五/三。A五地特點(diǎn)是效率高,適合硬件上高效實(shí)現(xiàn),它能通過已知地統(tǒng)計(jì)檢驗(yàn)。第三章數(shù)據(jù)加密A五算法由三個(gè)線反饋移位寄存器（LFSR）R一,R二,R三組成,寄存器地長(zhǎng)度分別是n一=一九,n二=二二與n三=二三。它們地特征多項(xiàng)式分別是 f一(x)=x一九+x五+x二+x+一 f二(x)=x二二+x+一 f三(x)=x二三+x一五+x二+x+一 所有地反饋多項(xiàng)系數(shù)都較少。三個(gè)LFSR地異或值作為輸出。A五通過"停/走"式鐘控方式相連。A五原理如圖三.一零所示。第三章數(shù)據(jù)加密第三章數(shù)據(jù)加密圖三.一零A五原理圖A五算法地密鑰K是六四

bit。A五地弱點(diǎn)可能是因?yàn)槠湟莆患拇嫫鞯丶夹g(shù)太短所致。第三章數(shù)據(jù)加密三.三公鑰加密算法三.三.一RSA加密算法RSA加密算法（一九七七）,下面簡(jiǎn)稱為RSA,是建立在大整數(shù)分解這個(gè)NP問題之上地公鑰密碼系統(tǒng)。RSA是一種分組密碼,其地明文與密文都是對(duì)于某個(gè)n地從零～n?一之間地整數(shù)。第三章數(shù)據(jù)加密（一）系統(tǒng)建立過程Bob選定兩個(gè)不同地素?cái)?shù)p與q,令n=pq,再選取一個(gè)整數(shù)e,使得。從而可以計(jì)算出。Bob公開(e,n)作為公開密鑰,而保存(d,n)作為自己地私有密鑰。第三章數(shù)據(jù)加密（二）加密過程RSA算法地明文空間與密文空間均為Zn。加密采用下列變換。（三）脫密過程可以證明,脫密變換是加密變換地逆變換。第三章數(shù)據(jù)加密三.三.二有限域乘法群密碼與橢圓曲線密碼另一類重要地公開密鑰密碼算法地構(gòu)造依賴于一個(gè)階數(shù)很大地有限群。特別是階數(shù)含大素因子地群。事實(shí)上,有限域乘法群與橢圓曲線加法群是非常方便地候選對(duì)象。用這兩種群可構(gòu)造Diffie-Hellman密鑰換算法,ElGamal加密算法等。第三章數(shù)據(jù)加密按照抽象代數(shù)地有限域地構(gòu)造理論,對(duì)于給定地任意一個(gè)素?cái)?shù)p與一個(gè)正整數(shù)n,存在且僅存在一個(gè)pn階地有限域,記為GF(pn),則G=GF(pn)×是一個(gè)s=pn?一階地循環(huán)群。若g是它地一個(gè)生成元,則可記為G=<g>。第三章數(shù)據(jù)加密圖三.一一原理圖第三章數(shù)據(jù)加密圖三.一二實(shí)數(shù)域上橢圓曲線地軌跡有限域上地橢圓曲線之所以成為構(gòu)造ElGamal加密算法地基礎(chǔ),是因?yàn)橐话銠E圓曲線上地離散對(duì)數(shù)問題是難解地。在給定有限域地規(guī)模地情況下,其上橢圓曲線離散對(duì)數(shù)地求解難度遠(yuǎn)遠(yuǎn)高于基域上地離散對(duì)數(shù)地求解難度。第三章數(shù)據(jù)加密有兩類橢圓曲線上地離散對(duì)數(shù)問題沒有預(yù)期地那樣難解。一類稱為超奇異（supersingular）曲線,其離散對(duì)數(shù)求解稍比其基域（有限域）上地困難一些。另一類稱為反常（anomalous）曲線,其上地離散對(duì)數(shù)問題可以通過形式指數(shù)-形式對(duì)數(shù)映射為十分簡(jiǎn)單地問題。用橢圓曲線構(gòu)造密碼系統(tǒng)時(shí),絕對(duì)要避免反常曲線地情形。密碼研究原來對(duì)超奇異曲線不感興趣,但是近年來們又發(fā)現(xiàn)超奇異曲線有一些非常好地質(zhì):主要是通過Weil配對(duì),給出地E到基域乘法群上地雙線映射,提供了一種可以構(gòu)造基于身份地密碼系統(tǒng)地方法。而且這種密碼經(jīng)常是在較基本地假設(shè)下可以證明其安全,從而成為近年來學(xué)術(shù)界追逐地對(duì)象之一。第三章數(shù)據(jù)加密三.三.三公鑰密碼算法難度地比較對(duì)于同等規(guī)模（指相同地密鑰長(zhǎng)度）地密碼算法安全而言,橢圓曲線公鑰密碼算法比RSA密碼算法以及有限域上地公鑰密碼具有更高地強(qiáng)度。要想達(dá)到相同地安全強(qiáng)度,ECC比RSA及有限域上地公鑰密碼具有更短地密