信息與通信網(wǎng)安全：第二講 密碼學(xué)概論

第二講密碼學(xué)概論密碼學(xué)發(fā)展起源于軍事、外交的需求。早期密碼學(xué)是門藝術(shù)，是技巧與經(jīng)驗(yàn)的綜合。1949年Shannon：“Communicationtheoryofsecrecysystem”標(biāo)志密碼學(xué)稱為學(xué)科。公鑰密碼學(xué)，1976年，Diffie&Hellman,“密碼學(xué)新方向”。國內(nèi)發(fā)展50年代以前側(cè)重于黨、政、軍用的密表、密碼、密語研究。1960年保密通信專業(yè)研究室（通信兵部、電子科學(xué)研究所），1966年建立保密通信專業(yè)研究所（成都30所）。70年代以后，10多個(gè)大學(xué)、研究所加入研究行列。1993年國務(wù)院學(xué)位辦批準(zhǔn)設(shè)置密碼學(xué)博士學(xué)位點(diǎn)。(西電、解放軍信息工程學(xué)院)近20年來，進(jìn)行了綜合業(yè)務(wù)保密通信的網(wǎng)間安全互聯(lián)、新的密碼算法與協(xié)議、防火墻、安全接入、安全管理等網(wǎng)絡(luò)安全技術(shù)的研究和產(chǎn)品開發(fā)。密碼學(xué)特點(diǎn)有堅(jiān)實(shí)的理論基礎(chǔ)公開研究密碼廣泛應(yīng)用破譯密碼=解數(shù)學(xué)難題（復(fù)雜度）密碼學(xué)研究發(fā)展的經(jīng)驗(yàn)不應(yīng)該低估對(duì)手的能力。每個(gè)設(shè)計(jì)密碼體制的機(jī)構(gòu)也應(yīng)該要以破譯密碼體制為任務(wù)。對(duì)手知道所用的密碼體制。表面上的復(fù)雜性可能是虛假的。人會(huì)發(fā)生密碼錯(cuò)誤和違反安全紀(jì)律的情況?；靖拍蠲魑?、密文加密算法、解密算法密鑰、加密密鑰、解密密鑰單鑰、雙鑰c=Ek1(m)m=Dk2(c)保密系統(tǒng)非法接入者信源M加密器c=Ek1(m)解密器m=Dk2(c)密碼分析員（竊聽者）接收者密鑰源H1密鑰源H2搭線信道（主動(dòng)攻擊）搭線信道（被動(dòng)攻擊）信道密鑰信道單鑰體制下H1=H2mm密鑰k1密鑰k2cc保密系統(tǒng)系統(tǒng)即使達(dá)不到理論上是不可破的，也應(yīng)當(dāng)是實(shí)際上不可破的。系統(tǒng)保密性不依賴于對(duì)加密體制或算法的保密，而依賴于密鑰。(Kerckoff原則)加密和解密算法適用于所有密鑰空間中的元素。系統(tǒng)便于實(shí)現(xiàn)和使用方便。密碼體制分類單鑰體制加密器Ek明文解密器Dk密文解密后明文密鑰產(chǎn)生器密鑰信道kk雙鑰保密體制用戶A在公鑰本上查到用戶B的公鑰，用它對(duì)消息進(jìn)行加密得到密文，而后送給用戶B，用戶B收到后以自己的密鑰進(jìn)行解密變換得到原來的消息。用公鑰和密文不能推算出明文。但是任何人都可以用公鑰給B發(fā)信息，缺少認(rèn)證。EkB1用戶AmcDkB2D’k用戶Bmm’搭線信道受保護(hù)的m=DkB2(c)=DkB2(EkB1(m))用戶A以自己的密鑰對(duì)消息m進(jìn)行專用變換，得到密文c送給用戶B，B收到c后可用A的公開鑰對(duì)c進(jìn)行公開變換。其他偽造的c得不到有意義的消息m。雙鑰認(rèn)證體制DkA1用戶AmcEkA1D’k用戶Bmm’搭線信道受保護(hù)的m=EkA1(c)=EkA1(DkA2(m))DkA2受保護(hù)的雙鑰保密認(rèn)證體制用戶AmDkB2用戶Bm保密m=EkA1(DkB2(c))=EkA1(DkB2(EkB1(DkA2(m))))=EkA1(DkA2(m))DkA2保密EkB1公開EkA1公開保密認(rèn)證信息安全的核心不安全環(huán)境/信道信息安全性：

信息保密、數(shù)據(jù)完整性、實(shí)體認(rèn)證、不可否認(rèn)性密碼技術(shù)是信息安全技術(shù)的核心密碼編碼學(xué)密碼分析學(xué)1、機(jī)密性:提供只允許特定用戶訪問和閱讀信息，任何非授權(quán)用戶對(duì)信息都不可理解的服務(wù)[通過數(shù)據(jù)加密實(shí)現(xiàn)]2、鑒別:提供與數(shù)據(jù)和身份識(shí)別有關(guān)的服務(wù)。[通過數(shù)據(jù)加密、數(shù)據(jù)散列或數(shù)字簽名來實(shí)現(xiàn)]3、數(shù)據(jù)完整性:提供確保數(shù)據(jù)在存儲(chǔ)和傳輸過程中不被未授權(quán)修改（竄改、刪除、插入和重放等）的服務(wù)。[通過數(shù)據(jù)加密、數(shù)據(jù)散列或數(shù)字簽名來實(shí)現(xiàn)]4、抗否認(rèn)性:提供阻止用戶否認(rèn)先前的言論或行為的服務(wù)。[通過對(duì)稱加密或非對(duì)稱加密，以及數(shù)字簽名等，并借助可信的注冊(cè)機(jī)構(gòu)或證書機(jī)構(gòu)的輔助，提供這種服務(wù)]密碼學(xué)的作用總結(jié)密碼學(xué)古典密碼學(xué)

代換密碼，置換密碼密碼分析現(xiàn)代密碼學(xué)

流密碼，分組密碼，公鑰密碼體系理論基礎(chǔ)和應(yīng)用偽隨機(jī)數(shù)，數(shù)論，函數(shù)論第三講古典密碼學(xué)代換/置換密碼例Caesar密碼

abcdefghijklmnopqrstuvwxyz

DEFGHIJKLMNOPQRSTUVWXYZABCm=CaesarcipherisashiftsubstitutionE(m)=FDHVDUFLSKHULVDVKLIW

VXEVWLWXWLRQ移位代換Shiftsubstitutioncipher基本變換公式Ek(i)=(i+k)=jmodq,0<=i,j<q加密Key={k|0<=k<q}—密鑰空間（q個(gè)元素）解密D(j)=Eq-k(j)=j+q-k=i+k-k=imodq乘數(shù)密碼Multiplicativecipher稱采樣密碼（decimationcipher）加密Ek(i)=ik=jmodq,0<=j<q.可用密鑰數(shù)量：q為素?cái)?shù)，有q-2個(gè)。當(dāng)<k,q>=1(互素)，一一對(duì)應(yīng)。解密i=Dk(j)=k-1j(modq)乘數(shù)密碼Multiplicativecipher例q=26,k=9,對(duì)應(yīng)為abcdefghijklmnopqrstuvwxyzAJSBKTCLUDMVENWFOXGPYHQZIRm=multiplicationcipherE(m)=EYVPUFVUSAPUHKSUFLKX其他單表代換密碼仿射密碼Ek(i)=ik1+k0=jmodq解密i=Dk(c)=k1-1(j-k0)modqk1k1-1modq=1多項(xiàng)式密碼Ek(x)=ktxt+…+k1x+k0modq例：密鑰k=(3,7)，則加密函數(shù)Ek(m)=3+7m(mod26)，相應(yīng)的解密函數(shù)是Dk(c)=7-1(c-3)(mod26)=15(c-3)(mod26)=15c-19(mod26)7×15=105=1（mod26）若加密明文為HOT，則：解密：加密：密鑰短語密碼需要密鑰子或密鑰短語如：HAPPYNEWYEAR去掉重復(fù)字母得HAPYNEWRabcdefghijklmnopqrstuvwxyzHAPYNEWRBCDFGIJKLMOQSTUVXZ加密c＝Ek(m)=π(m)解密m=Dk(c)=π-1(c)置換π的表示：

π＝密鑰空間很大，|π|=26!≈4×1026

移位密碼體制是置換密碼體制的一個(gè)特例，它僅含26個(gè)置換做為密鑰空間。(0123..2324250'1'2'3'..23'24'25')置換密碼（單表）多表代換密碼π=(π1,π2,…)C=Ek(m)=π(m)=π1(m1)π2(m2)…若π為非周期無限序列，可稱作一次一密鑰密碼，理論上是唯一不可破的密碼。周期多表代換密碼π=π1π2…πdπ1π2…πd…C=Ek(m)=π1(m1)π2(m2)…πd(md)π1(md+1)…πd(m2d)當(dāng)d=1時(shí)退化為單表代換維吉尼亞密碼k=(k1,k2,…kd)Ci+td=Eki(mi+td)=mi+td+kimodq例子q=26,k=RADIO,d=5m=polyalphabeticcipherk=RADIORADIORADIORADIOc=GOOGOCPKTPNTLKQZPKMF其他多表代換密碼博福特密碼與維吉尼亞密碼互為逆變換滾動(dòng)密鑰密碼周期長度和明文一樣長弗納姆密碼

q=2時(shí)的滾動(dòng)密鑰密碼轉(zhuǎn)輪密碼長周期密碼，二戰(zhàn)德軍發(fā)明多字母代換密碼矩陣變換密碼mK=ccK-1=m優(yōu)點(diǎn)是容易將字母的自然頻度隱蔽或均勻化，從而有利于抗擊統(tǒng)計(jì)分析。多字母代換密碼q=26,L=4先做置亂abcdefghijklmnopqrstuvwxyz523220101584182501613731196122421171422119m=delayoperation,前4個(gè)字母x=(20,10,16,5)y=(25,2,3,14)c=JCOMZLVBDVIEQMXC（不足4字母加上虛字母補(bǔ)齊）初等密碼分析密碼分析過程分析（統(tǒng)計(jì)截獲報(bào)文材料）、假設(shè)、推斷和證實(shí)。窮舉破譯法分析法分析破譯法確定性分析法統(tǒng)計(jì)分析法Shannon首先指出密碼分析根本是依賴于明文的冗余度來破譯密碼的。破譯條件惟密文攻擊：僅知道密文已知明文攻擊：除了密文還獲得一定明文密文對(duì)選擇明文攻擊：獲得任何明文-密文對(duì)選擇密文攻擊：利用解密機(jī)選擇密文解密出明文，雙鑰體制下類似選擇明文攻擊語言統(tǒng)計(jì)特性對(duì)100000個(gè)以上字母統(tǒng)計(jì)得出，英文字母按頻率大小排序如下：ETAOINSHRDLCUMWFGYPBVKJXQZ頻率高的前10個(gè)雙字母組如下：

THHEINERANREEDONESST頻率高的前10個(gè)三字母組如下：THEINGANDHEREREENTTHANTHWASETH單表代換密碼分析對(duì)截獲密文進(jìn)行統(tǒng)計(jì)得到單字母頻率分布表試圖區(qū)分元音和輔音字母利用模式詞或模式短語密文UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMB

ZWPFUPZUDTMOHMQ字母ABCDEFGHIJKLMNOPQRSTUVWXYZ頻數(shù)220664271100809163010310545214Z->tP->eQ,T單詞首字母->{c,w,p,b,f}UZ,MB,ZWP->M,U,P元音和B,Z,D,W輔音ZWSZ->that,ZWP->theWSFPAPPD->h..e.ee.(havebeen)Itwas.is..se..este..a.thatseve.a.In….a.b.t..i.e.t..nta.tshavebeen.a.ewith…iti.a..e..esentatives..Theviet..n.in..s..wItwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow.SPUT.I.AB.DEFGHJ.MOQ.VWXYZ---SPUTNIK為密鑰字多表代換密碼分析確定識(shí)別多表密碼的參數(shù)（粗糙度、重合指數(shù)）確定密表個(gè)數(shù)（重碼分析法）確定各代換表完善保密性令明文熵H(M)，密鑰熵H(K)，密文熵H(C)，唯密文攻擊要提取I(M,C)=H(M)-H(M|C)I(K,C)=H(K)-H(K|C)明文含糊度H(M|C)和密鑰含糊度H(K|C)越大，竊聽者從密文提取關(guān)于M,C的信息越小對(duì)于合法用戶H(M|CK)=0則有I(M,CK)=H(M)完善保密性定理：對(duì)于任意保密系統(tǒng)I(M,C)≥H(M)-H(K)證明：H(K|C)=H(K|C)+H(M|CK)=H(MK|C)=H(M|C)+H(K|MC)≥H(M|C)I(M,C)=H(M)-H(M|C)H(K)≥H(K|C)完善保密性定理：對(duì)于任意保密系統(tǒng)I(M,C)≥H(M)-H(K)（1）保密系統(tǒng)的密鑰量越小，其密文中含有明文的信息量就越大。（2）若使I(M,C)=0，保密系統(tǒng)為完善的或無條件保密系統(tǒng)（這是唯密文攻擊而言的安全性）。（3）由平均互信息量的非負(fù)性，可推出H(M)≤H(K)是完善保密系統(tǒng)存在的必要條件。第四講對(duì)稱密碼體系對(duì)稱密鑰加密從加密密鑰可以計(jì)算出解密密鑰（或反之）（也稱為單鑰或傳統(tǒng)加密）主要密碼體制流密碼、分組密碼優(yōu)缺點(diǎn)加密效率高；密鑰短；可靈活構(gòu)造各種密碼機(jī)制、建造安全性更強(qiáng)的密碼；雙方都必須保持密碼的秘密性；用戶多時(shí)密鑰個(gè)數(shù)巨大；需要常更換密鑰。

流密碼是一種單鑰體制密碼，是一種對(duì)明文消息字符逐位加密的私鑰密碼體制。秘密信道密鑰流產(chǎn)生器信道明文序列m0m1m2…y密鑰序列k0k1k2…密鑰源密文序列c0c1c2…密文序列c0c1c2…明文序列m0m1m2…密鑰流產(chǎn)生器kkk密鑰序列k0k1k2…流密碼序列加密變換：ci=mi

ki

(mod2)，i0序列解密變換:mi

=ci

ki

(mod2)，i0流密碼的實(shí)現(xiàn)例：設(shè)明文M=(0110010011)2，密鑰K=(0111001001)2。在A，B兩方通信前，A首先通過安全信道（比如信使）把密鑰K送給B，現(xiàn)在要把明文M通過公開信道送給B，加、解密過程如圖。

C=EK(m)=M⊕K=(0110010011)2⊕(0111001001)2=(0001011010)2M=DK(C)=C⊕K=(0001011010)2⊕(0111001001)2=(0110010011)2流密碼可以看成是塊長度為1的分組密碼。優(yōu)點(diǎn)：在出現(xiàn)傳輸錯(cuò)誤的時(shí)候，流密碼加密不會(huì)產(chǎn)生錯(cuò)誤傳播；每次只加密1位，所以可以在沒有存儲(chǔ)器或數(shù)據(jù)緩沖區(qū)比較小的情況下使用。流密碼密鑰生成器fs(kI,σi-1)σif(kI,σi-1)Eki(mi)kicici=Eki(m)mi=Dki(ci)ki=f(kI,σi)σi=fs(kI,σi-1)流密碼分類同步流密碼σi與明文消息無關(guān)，密鑰流獨(dú)立于明文，加密變換是無記憶的。自同步流密碼密鑰流不獨(dú)立于明文。同步和自同步流密碼Eki()…kI有限記憶kici加密器mi密鑰流生成器同步流密碼

在第一步傳送前必須將密鑰生成器同步。啟動(dòng)/終止連接以及同步密鑰流需要經(jīng)過通信協(xié)議完成。優(yōu)點(diǎn)：沒有差錯(cuò)傳播。缺點(diǎn)：必須保持收發(fā)兩端精確同步，一旦失步就不能正確解密，要等到重新同步后才能恢復(fù)工作。自同步流密碼ki=f(kI,mi-n,mi-n+1,…,mi)f:kI×Mi-1ki傳輸過程中一位出錯(cuò)，會(huì)影響其后n位密鑰的正確性，相應(yīng)恢復(fù)的明文消息連續(xù)n位會(huì)受到影響，差錯(cuò)傳播是有限的。具有自同步能力。對(duì)主動(dòng)攻擊不敏感，但是抗統(tǒng)計(jì)分析能力較強(qiáng)。序列的偽隨機(jī)性定義1:序列周期p定義2：串

長度為l的串

定義3：周期自相關(guān)函數(shù)當(dāng)j是p的倍數(shù)時(shí)R(j)=1,稱為同相自相關(guān)函數(shù)當(dāng)j不是p的倍數(shù)時(shí)R(j)稱為異相自相關(guān)函數(shù)例：二元序列111001011100101110010…Golomb隨機(jī)性假設(shè)G1：若p為偶，則0,1出現(xiàn)個(gè)數(shù)相等，皆為p/2。若p為奇，則0出現(xiàn)個(gè)數(shù)為(p±1)/2。G2：長為l的串占1/2l，且“0”串和“1”串個(gè)數(shù)相等或至多差一個(gè)。G3：R(j)為雙值，即所有異相自相關(guān)函數(shù)值相等。這與白噪聲的自相關(guān)函數(shù)相近，這種序列又稱為雙值序列。滿足上述三條的序列稱為偽噪聲序列（PN序列）。密碼體制要求C1:周期p足夠大，如遠(yuǎn)大于1050。C2：序列的產(chǎn)生易于高速生成。C3：當(dāng)序列任何部分暴露時(shí)，要分析整個(gè)序列，提取產(chǎn)生它的電路結(jié)構(gòu)信息，在計(jì)算上是不可行的，稱為不可預(yù)測性。六條歸結(jié)起來就是要求密鑰流序列盡可能近于實(shí)現(xiàn)均勻分布、各相繼碼元統(tǒng)計(jì)獨(dú)立、完全不可預(yù)測的真正隨機(jī)序列或白噪聲序列。

分組密碼，也稱為塊密碼，它是將明文消息經(jīng)編碼表示后的數(shù)字序列劃分為若干固定長度的組，每組分別在密鑰的控制下轉(zhuǎn)換成等長度的密文分組輸出。分組密碼易于構(gòu)造擬隨機(jī)數(shù)生成器、流密碼、消息認(rèn)證碼和雜湊函數(shù)等，還可進(jìn)而成為消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)構(gòu)、實(shí)體認(rèn)證協(xié)議以及單鑰數(shù)字簽名體制的核心組成部分。分組密碼密文僅與給定的密碼算法和密鑰有關(guān)；與被處理的明文數(shù)據(jù)段在整個(gè)明文（或密文）中所處的位置無關(guān)；總是以大于等于64比特的數(shù)據(jù)塊作為加密單位，給定相同的明文數(shù)據(jù)塊加密后得到相同的密文數(shù)據(jù)塊；具有代表性的分組加密算法有DES、IDEA等分組密碼主要特點(diǎn)：分組密碼密文分組C=C0C1C2…明文分組m=m0m1m2…密鑰k=k0k1k2…Ek密鑰k=k0k1k2…密文分組C=C0C1C2…明文分組m=m0m1m2…Dk分組密碼的設(shè)計(jì)在于找到一種算法，能在密鑰控制下從一個(gè)足夠大且足夠好的代換子集中，簡單而迅速地選出一個(gè)代換，用來對(duì)當(dāng)前輸入的數(shù)字組進(jìn)行加密變換。分組密碼算法要求分組長度n要足夠大，防止明文窮舉攻擊密鑰量足夠大，防止密鑰窮舉攻擊由密鑰確定置換的算法要足夠復(fù)雜加密和解密運(yùn)算簡單，易于軟硬件的快速實(shí)現(xiàn)數(shù)據(jù)擴(kuò)展差錯(cuò)傳播盡可能小擴(kuò)散和混淆擴(kuò)散，將每一位明文及密鑰數(shù)字的影響盡可能迅速地散布到較多個(gè)輸出的密文數(shù)字中，以便隱蔽明文數(shù)字的統(tǒng)計(jì)特性?；煜?，使作用于明文的密鑰和密文之前的關(guān)系復(fù)雜化，使明文和密文之間、密文和密鑰之間的統(tǒng)計(jì)相關(guān)性極小化，從而使統(tǒng)計(jì)分析攻擊不能湊效。代換代換：設(shè)S為一有限集合，為S到S的一一映射，則

為S上的一個(gè)代換。代換網(wǎng)絡(luò)：實(shí)現(xiàn)代換的網(wǎng)絡(luò)。一一映射保證密文可唯一恢復(fù)出明文。代換網(wǎng)絡(luò)左循環(huán)移位（λ）右循環(huán)移位（ρ）模2n加1（σ）線性變換A定義了GF(2n)上的變換T，使換位（γ）仿射變換連線交叉或坐標(biāo)置換（P盒）序號(hào)x2x1x0y2y1y0000001110011112010000301111041000105101100611010171110010123456701234567代換網(wǎng)絡(luò)S盒隨著n增大，布爾代數(shù)關(guān)系式中的小項(xiàng)也增大，難以處理?？蛇xn=rn0選，將設(shè)計(jì)n個(gè)變量的代換網(wǎng)絡(luò)轉(zhuǎn)化為設(shè)計(jì)r個(gè)較小的子代換網(wǎng)絡(luò)。稱每個(gè)子代換網(wǎng)絡(luò)為代換盒（S盒）。S盒DES體制中，將輸入為48bit，輸出為32bit的代換用8個(gè)S盒實(shí)現(xiàn)，每個(gè)盒的輸入端數(shù)僅為6bit，輸出端數(shù)為4bit。S盒設(shè)計(jì)準(zhǔn)則P1S盒的輸出都不是其輸入的線性或仿射函數(shù)P2改變S盒的一個(gè)輸入比特，其輸出至少有兩比特產(chǎn)生變化，即近一半產(chǎn)生變化。P3當(dāng)S盒的任一輸入位保持不變，其他5位輸入變化時(shí)（25＝32種情況），輸出數(shù)字中的0和1的總數(shù)近于相等。DES的S盒012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613輸入二進(jìn)制數(shù)字x5x4x3x2x1x0101100x5x0

10輸出二進(jìn)制數(shù)字0010S盒和P盒P盒是線性的，其作用是打亂各S盒輸出數(shù)字的次序，將各S盒的輸出分到下一級(jí)不同的各S盒的輸入端，起到Shannon所謂的擴(kuò)散作用。S盒提供非線性變換，將來自上一級(jí)不同的S盒的輸出進(jìn)行混淆。分組密碼DES(dataencryptionstandard)1972.NBS(美國商業(yè)部國家標(biāo)準(zhǔn)局)開發(fā)1973.NBS征集密碼算法1975.批準(zhǔn)加密標(biāo)準(zhǔn)FIPS-46，之后每5年NSA（國家安全局）評(píng)估確定是否繼續(xù)當(dāng)前加密標(biāo)準(zhǔn)，直至1994.最后一次評(píng)估。1998年后不再作為加密標(biāo)準(zhǔn)。

為二進(jìn)制編碼數(shù)據(jù)設(shè)計(jì)的，可以對(duì)計(jì)算機(jī)數(shù)據(jù)進(jìn)行密碼保護(hù)的數(shù)學(xué)運(yùn)算。DES算法是對(duì)稱的，既可用于加密又可用于解密。DES的保密性僅取決于對(duì)密鑰的保密，而算法是公開的。DES算法64位明文64位密文64位密鑰（56位有效）DES算法64位碼64位碼初始變換逆初始變換乘積變換明文密文輸入輸出IPIP-1DES的結(jié)構(gòu)圖DES算法Li=Ri-1Ri=Li-1f(Ri-1，Ki)加密：DES算法DES算法明文X，左32位L0，右32位R0，經(jīng)過16次迭代，Li=Ri-1,Ri=Li-1(+)f(Ri-1,Ki)i=1,2,…,16.(+)為異或運(yùn)算Ki—48位子密鑰（64微密鑰中經(jīng)過若干次變換得到）每一輪迭代經(jīng)過函數(shù)f變換異或和左右兩邊交換（最后一次迭代不做左右交換）輪函數(shù)f的實(shí)現(xiàn)原理擴(kuò)展置換32位->48位48位子密鑰KiS盒替代48位->32位P盒置換子密鑰產(chǎn)生器密鑰64位置換選擇1除去第8、16、…、64位校驗(yàn)位Ci28位Di28位循環(huán)左移循環(huán)左移置換選擇2除去第7、9、15、26位除去第9、18、22、25位子密鑰48位DES算法DES的解密過程與加密過程對(duì)稱DES解密時(shí)密碼運(yùn)用與加密時(shí)是反過來的。（可逆性證明）體現(xiàn)出DES為（分組）對(duì)稱密鑰算法。加密過程解密過程DES算法可逆證明令則有同理則有加密過程可寫成解密過程可寫成因而可證得

DES的設(shè)計(jì)是密碼學(xué)歷史上的一個(gè)創(chuàng)新。自從DES問世至今，對(duì)它多次的分析研究，從未發(fā)現(xiàn)其算法上的破綻。利用窮舉法搜索攻擊，只能說明密鑰長度可能太少，DES的迭代次數(shù)可能太少。但直到1998年，電子邊境基金會(huì)（EFF）動(dòng)用一臺(tái)價(jià)值25萬美元的高速電腦，在56小時(shí)內(nèi)利用窮盡搜索的方法破譯密鑰56位的DES，才證明上述論斷。

1982年，已經(jīng)有辦法攻破4次迭代的DES系統(tǒng)了。1985年，對(duì)于6次迭代的DES系統(tǒng)也已破譯。1990年，以色列學(xué)者發(fā)明并運(yùn)用差分分析方法證明，通過已知明文攻擊，任何少于16次迭代的DES算法都可以用比窮舉法更有效的方法。DES的安全性討論DES的脆弱性：1）函數(shù)構(gòu)造與作用域加密強(qiáng)度取決于函數(shù)F的復(fù)雜度(S、P)和F的執(zhí)行次數(shù)。

64位固定分組，短組模式，易造成密文重復(fù)組塊；有限的函數(shù)作用域（ASCII碼0~127）；子密鑰只參與異或簡單的運(yùn)算，有可能損害變換精度。2）迭代問題無法證明迭代16次最好；在有限的作用域中存在封閉性；迭代次數(shù)多不僅費(fèi)時(shí)，還可能被一次簡單的變換所代替。DES的安全性討論3）S盒中的重復(fù)因子及密鑰多值問題

S盒對(duì)不同輸入可能產(chǎn)生相同輸出，使加密、解密變換的密鑰具有多值性；子密鑰長度48位，只影響32位輸出，因此加密強(qiáng)度達(dá)不到256，實(shí)際只有232x16=236；4）S盒是精心設(shè)計(jì)的，其原理至今未公開，其中可能隱藏陷門，它有利于設(shè)計(jì)者破譯密碼。5）提高加密強(qiáng)度（如增加密鑰長度），系統(tǒng)開銷呈指數(shù)增，提高硬件、并行處理外，算法本身和軟件技術(shù)無法提高加密強(qiáng)度。DES的安全性討論解決密鑰長度的問題的辦法之一是采用多重DES。雙重DES使用兩個(gè)長度為56位DES密鑰，先用密鑰K1進(jìn)行DES加密，對(duì)加密后的密文再使用密鑰K2進(jìn)行DES加密，得到最終密文。雙重DES很難抵抗中間相遇攻擊。三重DES使用三個(gè)長度為56位DES密鑰，先用密鑰K1進(jìn)行DES加密，對(duì)加密后的密文再使用密鑰K2進(jìn)行DES解密，最后用密鑰K3進(jìn)行DES加密，得到最終密文。最常用的三重DES,算法中選取K1＝K3。多重DES三重DES是Tuchman提出的，并在1985年成為美國的一個(gè)商用加密標(biāo)準(zhǔn)[RFC2420]。三重DES使用兩個(gè)（或三個(gè)）密鑰，執(zhí)行三次DES算法。其做法有許多的方式：

DES-EEE3、DES-EDE3、DES-EEE2、DES-EDE2EDEK1K2K3MCDEDCMDES-EDE3多重DES國際數(shù)據(jù)加密算法(IDEA)與DES一樣，也是一種使用一個(gè)密鑰對(duì)64位數(shù)據(jù)塊進(jìn)行加密的單鑰加密算法，它是瑞士聯(lián)邦技術(shù)學(xué)院開發(fā)的一種面向數(shù)據(jù)分組塊的數(shù)據(jù)加密標(biāo)準(zhǔn)。相對(duì)于DES的56位密鑰，它使用128位密鑰，每次加密一個(gè)64位的數(shù)據(jù)塊，這么長的密鑰被認(rèn)為即使在多年后仍是有效的。

IDEA算法通過一系列的加密輪次進(jìn)行操作，每輪都使用從完整的加密密鑰中生成的一個(gè)子密鑰，使用一個(gè)稱為“壓碼”的函數(shù)在每輪中對(duì)數(shù)據(jù)位進(jìn)行編碼。與DES不同的是IDEA不使用置換。IDEAIDEA使用128位密鑰，在64位明文分組進(jìn)行加密得到64位密文分組。加密算法的函數(shù)在每個(gè)分組上運(yùn)行8個(gè)回合。每個(gè)回合都包含3個(gè)不同運(yùn)算：異或運(yùn)算、模加運(yùn)算和模乘運(yùn)算。加密與解密也相同，只是密鑰各異。IDEA算法加密速度快，密鑰產(chǎn)生方法簡單，硬件、軟件都能實(shí)現(xiàn)。IDEA

IDEA的加密運(yùn)算的回合數(shù)雖然比DES的16回合少，但其每一回合的運(yùn)算復(fù)雜度相當(dāng)于兩個(gè)回合DES的運(yùn)算，且其密鑰長度為128位，為DES的兩倍多，在暴力搜尋攻擊法下，其安全性較DES高。但已有研究發(fā)現(xiàn)IDEA的2128把密鑰中存在有251把的弱密鑰，雖然對(duì)于整個(gè)密鑰空間而言還屬少數(shù)，但在運(yùn)行時(shí)必須小心規(guī)避。IDEA

93

IDEA算法的安全性相對(duì)DES算法有很大的提高，其密鑰是128位，在窮舉攻擊的情況下，需要經(jīng)過2128次加密才能恢復(fù)出密鑰。假設(shè)一臺(tái)計(jì)算機(jī)每秒產(chǎn)生和運(yùn)行10億個(gè)密鑰，它將檢測1013年。至今IDEA還沒有明顯的安全漏洞，就連PGP（安全電子郵件）中也采用IDEA作為數(shù)據(jù)加密。IDEAMD5報(bào)文摘要算法任意長的報(bào)文作為輸入，128位報(bào)文摘要作為輸出，輸入按照512位分組進(jìn)行。步驟：1.附加填充位。2.附加長度值。3.初始化MD緩存。4.處理512位（16個(gè)字）報(bào)文分組序列。5.輸出。MD5報(bào)文摘要算法其它典型密碼算法RC5,1994AES(advancedencryptionstandard)2000單鑰密碼算法存在的主要問題第一，密鑰量問題。在單鑰密碼系統(tǒng)中，每一對(duì)通信者就需要一對(duì)密鑰，當(dāng)用戶增加時(shí)，必然會(huì)帶來密鑰量的成倍增長，因此在網(wǎng)絡(luò)通信中，大量密鑰的產(chǎn)生﹑存放和分配將是一個(gè)難以解決的問題。單鑰密碼算法存在的主要問題第二，密鑰分發(fā)問題。單鑰密碼系統(tǒng)中，加密的安全性完全依賴于對(duì)密鑰的保護(hù)，但是由于通信雙方使用的是相同的密鑰，人們又不得不相互交流密鑰，所以為了保證安全，人們必須使用一些另外的安全信道來分發(fā)密鑰，例如用專門的信使來傳送密鑰，這種做法的代價(jià)是相當(dāng)大的，甚至可以說是非常不現(xiàn)實(shí)的。第五講非對(duì)稱密碼體系公鑰密碼體系產(chǎn)生的動(dòng)機(jī)正因?yàn)閱舞€密碼系統(tǒng)存在如此難以解決的缺點(diǎn)，發(fā)展一種新的﹑更有效﹑更先進(jìn)的密碼體制顯得更為迫切和必要。在這種情況下，出現(xiàn)了一種新的公鑰密碼體制，它突破性地解決了困擾著無數(shù)科學(xué)家的密鑰分發(fā)問題。這一全新的思想是上世紀(jì)70年代，美國斯坦福大學(xué)的兩名學(xué)者Diffie和Hellman提出的。公鑰體系算法的原理

兩個(gè)在不安全信道中通信的人，假設(shè)為Alice（收信者）和Bob（發(fā)信者），他們希望能夠安全的通信而不被他們的敵手Oscar破壞。

Alice想到了一種辦法，她使用了一種鎖（相當(dāng)于公鑰），這種鎖任何人只要輕輕一按就可以鎖上，但是只有Alice的鑰匙（相當(dāng)于私鑰）才能夠打開。與密鑰密碼體系的不同點(diǎn)非對(duì)稱密鑰在公鑰密碼系統(tǒng)中，加密和解密使用的是不同的密鑰（相對(duì)于對(duì)稱密鑰，人們把它叫做非對(duì)稱密鑰），這兩個(gè)密鑰之間存在著相互依存關(guān)系：即用其中任一個(gè)密鑰加密的信息只能用另一個(gè)密鑰進(jìn)行解密。與密鑰密碼體系的不同點(diǎn)公開性加密密鑰和算法是對(duì)外公開的，人人都可以通過這個(gè)密鑰加密文件然后發(fā)給收信者，這個(gè)加密密鑰又稱為公鑰。與密鑰密碼體系的不同點(diǎn)密鑰分發(fā)通信雙方無需事先交換密鑰就可進(jìn)行保密通信。而收信者收到加密文件后,它可以使用他的解密密鑰解密，這個(gè)密鑰是由他自己私人掌管的，并不需要分發(fā)，因此又成稱為私鑰，這就解決了密鑰分發(fā)的問題。實(shí)現(xiàn)所需條件①

加密密鑰PK對(duì)明文X加密后，再用解密密鑰SK解密，即可恢復(fù)出明文，或?qū)憺椋?/p>

DSK（EPK（X））=X

②

加密密鑰不能用來解密，即

DPK（EPK（X））≠X

③

在計(jì)算機(jī)上可以容易地產(chǎn)生成對(duì)的PK和SK。

④

從已知的PK實(shí)際上不可能推導(dǎo)出SK。

⑤

加密和解密的運(yùn)算可以對(duì)調(diào)，即：

EPK（DSK（X））=X

算法可行性這種體制思想是簡單的，但是因?yàn)榧热籔k和SK是一對(duì)存在著相互關(guān)系的密鑰，那么從其中一個(gè)推導(dǎo)出另一個(gè)就是很有可能的，如果敵手Oscar能夠從PK推導(dǎo)出SK，那么這個(gè)系統(tǒng)就不再安全了。因此如何找到一個(gè)合適的算法生成合適的PK和SK，并且使得從PK不可能推導(dǎo)出SK，正是迫切需要密碼學(xué)家們解決的一道難題。這個(gè)難題甚至使得公鑰密碼系統(tǒng)的發(fā)展停滯了很長一段時(shí)間。單向函數(shù)定義：一個(gè)可逆函數(shù)f:AB，若滿足（1）對(duì)所有x∈A，易于計(jì)算f(x)

（2）對(duì)幾乎所有x∈A，由f(x)求x極為困難，以至實(shí)際上不可能做到，則稱f為單向函數(shù)。單向函數(shù)例如，有如下一個(gè)函數(shù)被認(rèn)為是單向的，假定n為兩個(gè)大素?cái)?shù)p和q的乘積，b為一個(gè)正整數(shù)，那么定義f：

f(x)=(xb)modn

n=7X9=63,b=3f(0)=0,f(1)=3,…,f(10)=30,…,f(20)=60,f(21)=0單向函數(shù)公開加密函數(shù)應(yīng)該是容易計(jì)算的，而計(jì)算其逆函數(shù)（即解密函數(shù)）對(duì)于除Alice以外的人應(yīng)該是困難的。在加密過程中，希望加密函數(shù)E為一個(gè)單向的單射函數(shù)，以便可以解密。陷門單向函數(shù)目標(biāo)：在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后，求逆是易于實(shí)現(xiàn)。陷門函數(shù)其實(shí)不是單向函數(shù)，單向函數(shù)任何條件下求逆都困難。陷門可能不止一個(gè)。陷門單向函數(shù)定義：陷門單向函數(shù)fz，對(duì)fz:AzBz，z∈Z，Z是陷門信息集，要滿足（1）對(duì)所有z∈Z，容易找到一對(duì)算法Ez和Dz使對(duì)所有x∈A,易于計(jì)算fz及其逆，即fz(x)=Ez(x)Dz(fz(x))=x

而且當(dāng)給定z后容易找到一種算法Fz，對(duì)所有x∈A，易于檢驗(yàn)是否x∈Az（Az屬于A）

。Az是可用的明文集,

Fz為可用消息集鑒別函數(shù)。陷門單向函數(shù)（2）對(duì)幾乎所有z∈Z，當(dāng)只給定Ez和Fz時(shí)，對(duì)幾乎所有x∈Az，很難或?qū)嶋H上不可能從y=Fz(x)算出x。（3）對(duì)任一z，集Az必須是保密系統(tǒng)中明文集中的一個(gè)方便集。即便于實(shí)現(xiàn)明文到它的映射。公鑰系統(tǒng)在一個(gè)公鑰系統(tǒng)中，所有用戶共同選定一個(gè)陷門單向函數(shù)，加密運(yùn)算E及可用消息集鑒別函數(shù)F。用戶i從陷門集中選定zi，并公開Ezi和Fzi。任一要向用戶i送機(jī)密消息者，可用Fzi檢驗(yàn)消息x是否在許用明文之中，而后送y=Ezi(x)給用戶i即可。在僅知y，Ezi和Fzi下，任一用戶不能得到x,但用戶i利用陷門信息zi，易于得到Dzi(y)=x。構(gòu)造雙鑰密碼的單向函數(shù)多項(xiàng)式求根給定a0,a1,…,an-1,p和x最多通過n次乘法和n-1次加法，求y

反之，已知y,a0,a1,…,an-1，求解x需要對(duì)高次方程求根。至少要次乘法。構(gòu)造雙鑰密碼的單向函數(shù)離散對(duì)數(shù)

給定大素?cái)?shù)p，p-1含另一大素?cái)?shù)q。構(gòu)造p-1階循環(huán)群Zp,其生成元為g。已知x，求容易，但已知y,g,p求為離散對(duì)數(shù)問題。最快求解法運(yùn)算次數(shù)漸近值為構(gòu)造雙鑰密碼的單向函數(shù)大整數(shù)分解

判斷一個(gè)大奇數(shù)n是否為素?cái)?shù)的有效算法，大約需要計(jì)算量，當(dāng)n為256或512位二元數(shù)時(shí)，用當(dāng)前計(jì)算機(jī)可在10分鐘內(nèi)完成。

已知二大素?cái)?shù)p和q，求n=pq只需要一次乘法。但若由n求p和q，則是幾世紀(jì)來數(shù)論專家的攻關(guān)對(duì)象！RSA算法

當(dāng)前最著名、應(yīng)用最廣泛的公鑰系統(tǒng)RSA是在1978年，由美國麻省理工學(xué)院(MIT)的Rivest、Shamir和Adleman在題為《獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法》的論文中提出的。它是一個(gè)基于數(shù)論的非對(duì)稱(公開鑰)密碼體制，是一種分組密碼體制。其名稱來自于三個(gè)發(fā)明者的姓名首字母。它的安全性是基于大整數(shù)素因子分解的困難性，而大整數(shù)因子分解問題是數(shù)學(xué)上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA算法的安全性。RSA系統(tǒng)是公鑰系統(tǒng)的最具有典型意義的方法，大多數(shù)使用公鑰密碼進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)使用的都是RSA算法。RSA原理

1)

任意選取兩個(gè)不同的大質(zhì)數(shù)p和q，計(jì)算乘積r=p*q；2)

任意選取一個(gè)大整數(shù)e，e與(p-1)*(q-1)互質(zhì)，整數(shù)e用做加密密鑰。注意：e的選取是很容易的，例如，所有大于p和q的質(zhì)數(shù)都可用。3)

確定解密密鑰d：d*e=1mod（p-1）*（q-1）根據(jù)e、p和q可以容易地計(jì)算出d。RSA原理

4)

公開整數(shù)r和e，但是不公開d；5)

將明文P(假設(shè)P是一個(gè)小于r的整數(shù))加密為密文C，計(jì)算方法為：

C=Pemodr6)

將密文C解密為明文P，計(jì)算方法為：

P=Cdmodr

然而只根據(jù)r和e（不是p和q）要計(jì)算出d是不可能的。因此，任何人都可對(duì)明文進(jìn)行加密，但只有授權(quán)用戶（知道d）才可對(duì)密文解密。RSA原理證明歐拉函數(shù)值Φ(r)=(p-1)(q-1)Cd=(Pe)d,de=1modΦ(r),de=sΦ(r)+1

歐拉定理若(P,r)=1,則PΦ(r)=1modrCd=Pde=PsΦ(r)+1=P·PsΦ(r)=P·1=Pmodr簡單示例選取p=7,q=9,r=63,(p-1)(q-1)=48,選取加密密鑰e=13,由d*e=1mod48,解密密鑰d=37,公開r和e，設(shè)明文P=3,加密C=Pemodr,得到密文C=45,解密P=Cdmodr=3.RSA實(shí)質(zhì)上是一種單表代換:對(duì)P≠P’，必有C≠C’；定義域中任一元素（0,p,q除外）是一個(gè)明文，也是某個(gè)明文相對(duì)應(yīng)的一個(gè)密文。不知陷門信息下，極難確定對(duì)應(yīng)關(guān)系，同時(shí)模指數(shù)算法容易實(shí)現(xiàn)。RSA的安全RSA算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，因此它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。它通常事先生成一對(duì)RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個(gè)為公開密鑰，可對(duì)外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)，人們用公鑰加密文件發(fā)送給個(gè)人，個(gè)人就可以用私鑰解密接受。為提高保密強(qiáng)度，RSA密鑰至少為500位長，一般推薦使用1024位。

RSA的安全下面的兩個(gè)事實(shí)保證了RSA算法的安全有效性：

1)已有確定一個(gè)數(shù)是不是質(zhì)數(shù)的快速算法；

2)尚未找到確定一個(gè)合數(shù)的質(zhì)因子的快速算法。密鑰長（bit）所需MIPS-年11640012950005123000076820000000010243000000000002048300000000000000000000MIPS-年：以每秒執(zhí)行1000000條指令的計(jì)算機(jī)運(yùn)行一年單鑰體制RSA體制56bit384bit64bit512bit80bit768bit112bit1792bit128bit2304bit破譯RSA體制與窮舉搜索破譯單鑰體制的等價(jià)密鑰長度橢圓曲線密碼算法橢圓曲線是國際密碼學(xué)會(huì)推薦的密碼體制之一，（RSA是推薦的另一個(gè)體制，但為了防攻擊，密鑰越來越長，給加密速度、密鑰管理帶來麻煩），橢圓曲線（ECC）因?yàn)橛屑用芩俣瓤?、?qiáng)度高等特點(diǎn)而受重視。橢圓曲線令Fp表示p個(gè)元素的有限域，p3為素?cái)?shù)，a,b∈Fp，滿足4a3+27b2≠0，由參數(shù)a和b定義Fp上的一個(gè)橢圓曲線：

y2=x3+ax+b它的所有解(x,y)，(xFp，yFp)，連同一個(gè)稱為“無窮遠(yuǎn)點(diǎn)”(記為θ或O)的元素組成的集合為定義在Fp上的一個(gè)橢圓曲線，記為E(Fp)。橢圓曲線定理：橢圓曲線E上的點(diǎn)及其無窮遠(yuǎn)點(diǎn)θ形成一個(gè)Abel群。設(shè)P、Q是E上的任意兩點(diǎn)，則其加法規(guī)則為：

θθ=θ，-θ=θ；（單位元素）若-P是P的逆元，則P-P=θ；(3)對(duì)任意P(x,y)，有Pθ=P且θP=P，即θ為恒元；(4)如果P≠θ,Q≠θ,Q≠-P,R是P、Q連線與E的交點(diǎn)，或E在點(diǎn)P的切線交E所得的另一點(diǎn)R，則有：

P＋Q＝－R；橢圓曲線若P(xP,yP)、Q(xQ,yQ)是橢圓曲線E：y2=x3+ax+b上的任意兩點(diǎn)，且P≠θ,Q≠θ,Q≠-P,R(xR,yR)是P、Q連線與E的交點(diǎn),如果沿x軸作關(guān)于R的對(duì)稱點(diǎn)，將得到另一個(gè)對(duì)稱點(diǎn)，該點(diǎn)稱為：

P＋Q＝－R；－R＝(xR,-yR)

一、點(diǎn)加公式設(shè)過P、Q的直線L為y=kx+b;則k=(yQ-yP)/(xQ-xP),代入曲線方程。經(jīng)比較得到：

xR=k2-xP-xQ；

-yR=-yP-k(xP-xR)；橢圓曲線當(dāng)P＝Q時(shí)，P＋Q＝P＋P＝2P，稱點(diǎn)2P為P的倍點(diǎn)。過P作E的切線，則必定與E相交于且化相交于另一點(diǎn)R，作R關(guān)于x軸的對(duì)稱點(diǎn)，得到另一點(diǎn)，也就是P的倍點(diǎn)2P。若過P的E地切線垂直于x軸，那么切線交E于無窮遠(yuǎn)點(diǎn)，則有

P＋P＝θ；（稱P是一個(gè)階為2的點(diǎn)）

二、倍點(diǎn)公式對(duì)方程求導(dǎo)，得k=(3xP2+a)/2y,代入曲線方程得：

xR=k2-2xP；

-yR=-(kx+b)；橢圓曲線倍點(diǎn)是將橢圓曲線上的點(diǎn)自身相加得到的點(diǎn)。若將E上的一個(gè)點(diǎn)自身相加若干次，稱之為點(diǎn)乘操作。xP=P+P+…+P三、點(diǎn)乘操作橢圓曲線橢圓曲線密碼算法離散問題是給定P,Q屬于E求整數(shù)n使得Q=nP(nP=P+P+…+P,n個(gè)P)，已知P，n求Q是容易的（可以將n=n0+n1?2+…+nk-1?2k-1,ni=0or1,nP=((…(nk-1P)2+nk-2P)2+…)2+n1P)2+n0P,計(jì)算量O(logn)但已知P,Q求n是非常困難的。ECC加密設(shè)A向B發(fā)送信息m

1)有限整數(shù)域Fq上橢圓曲線E(Fq)，在其上取點(diǎn)G作為公鑰，選函數(shù)f:E(Fq)Fq

2)B選隨機(jī)整數(shù)KB（私鑰），計(jì)算GB=KB*G作為公鑰

3)A另選一隨機(jī)整數(shù)KA(私鑰)，計(jì)算GA=KA*G和m+f(KA*GB)屬于信息單位組成的群s,發(fā){GA,m+f(KA*GB)}給B

4)B收到信息后由f(KB*GA)=f(KB*KA*G)=f(KA*GB)求f(KA*GB)，并從收到信息中減去它，恢復(fù)出mECC加密截取密文的人不知道KA,KB,僅僅根據(jù)G,KB*G和KA*G無法求解KA,KB，也就求不出KB*GA=KB*KA*G=KA*GB,進(jìn)而不能恢復(fù)明文。ECC加密與RSA比較，對(duì)同樣長度密鑰，計(jì)算工作量相差無幾。同樣安全強(qiáng)度時(shí)橢圓密碼體系(ECC)密鑰長度較短。ECC密鑰長度RSA密鑰長度MIPS-年1601024101232051201036600210001078120012000010168第六講認(rèn)證網(wǎng)絡(luò)系統(tǒng)安全要考慮兩個(gè)方面。一方面，用密碼保護(hù)傳送的信息使其不被破譯；另一方面，就是防止對(duì)手對(duì)系統(tǒng)進(jìn)行主動(dòng)攻擊，如偽造，篡改信息等。認(rèn)證的主要目的：第一，驗(yàn)證信息的發(fā)送者是真的，而不是冒充的，此為身份認(rèn)證，包括信源、信宿等的認(rèn)證和識(shí)別；第二，驗(yàn)證信息的完整性，此為消息認(rèn)證，驗(yàn)證數(shù)據(jù)在傳送或存儲(chǔ)過程中未被篡改，重放或延遲等。認(rèn)證（authentication）則是防止主動(dòng)攻擊的重要技術(shù)，它對(duì)于開放的網(wǎng)絡(luò)中的各種信息系統(tǒng)的安全性有重要作用。認(rèn)證身份認(rèn)證

身份認(rèn)證又稱作識(shí)別(Identification)、實(shí)體認(rèn)證(EntityAuthentication)、身份證實(shí)(IdentityVerification)等。

它與消息認(rèn)證的區(qū)別在于：身份認(rèn)證一般都是實(shí)時(shí)的，而消息認(rèn)證本身不提供時(shí)間性；另一方面，身份認(rèn)證通常證實(shí)身份本身，而消息認(rèn)證除了認(rèn)證消息的合法性和完整性外，還要知道消息的含義。

一方是出示證件的人，稱作示證者P（Prover），提出某種要求；另一方為驗(yàn)證者V（Verifier），檢驗(yàn)示證者提出的證件的正確性和合法性，決定是否滿足其要求；第三方是攻擊者，可以竊聽和偽裝示證者，騙取驗(yàn)證者的信任。認(rèn)證系統(tǒng)在必要時(shí)也會(huì)有第四方，即可信賴者參與調(diào)解糾紛。身份認(rèn)證系統(tǒng)組成（1）驗(yàn)證者正確識(shí)別合法示證者的概率極大化。（2）不具可傳遞性，驗(yàn)證者B不可能重用示證者A提供給他的信息來偽裝示證者A，而成功地騙取其他人的驗(yàn)證，從而得到信任。（3）攻擊者偽裝示證者欺騙驗(yàn)證者成功的概率要小到可以忽略的程度，特別是要能抗擊已知密文攻擊，即能抗攻擊者在截獲到示證者和驗(yàn)證者多次通信下偽裝示證者欺騙驗(yàn)證者。身份認(rèn)證系統(tǒng)的要求（4）計(jì)算有效性，為實(shí)現(xiàn)身份證明所需的計(jì)算量要小。（5）通信有效性，為實(shí)現(xiàn)身份證明所需通信次數(shù)和數(shù)據(jù)量要小。（6）秘密參數(shù)能安全存儲(chǔ)。（7）交互識(shí)別，有些應(yīng)用中要求雙方能互相進(jìn)行身份認(rèn)證。（8）第四方的實(shí)時(shí)參與，如在線公鑰檢索服務(wù)。（9）第四方的可信賴性。（10）可證明安全性。身份認(rèn)證系統(tǒng)的要求

144

最簡單、最普遍的身份識(shí)別技術(shù)，如：各類系統(tǒng)的登錄等口令具有共享秘密的屬性，口令有時(shí)由用戶選擇，有時(shí)由系統(tǒng)分配。通常情況下，用戶先輸入某種標(biāo)志信息，比如用戶名和ID號(hào)，然后系統(tǒng)詢問用戶口令，若口令與用戶文件中的相匹配，用戶即可進(jìn)入訪問。口令有多種，如一次性口令；還有基于時(shí)間的口令?？诹钫J(rèn)證這種方法的缺點(diǎn)是：1、安全性僅僅基于用戶口令的保密性，而用戶口令一般較短且容易猜測，因此這種方案不能抵御口令猜測攻擊。2、大多數(shù)系統(tǒng)的口令是明文傳送到驗(yàn)證服務(wù)器的，容易被截獲。3、口令維護(hù)的成本較高。為保證安全性口令應(yīng)當(dāng)經(jīng)常更換。為避免對(duì)口令的字典攻擊，口令應(yīng)當(dāng)保證一定的長度，并且盡量采用隨機(jī)的字符。但缺點(diǎn)是難于記憶。4、口令容易在輸入時(shí)被攻擊者偷窺，且用戶無法及時(shí)發(fā)現(xiàn)。口令認(rèn)證

146

網(wǎng)絡(luò)一般是通過用戶用智能卡或其它特殊形式來標(biāo)志，這類標(biāo)志可以從連接到計(jì)算機(jī)上的讀取器讀出來。訪問不但需要口令，也需要使用物理智能卡。智能卡技術(shù)將成為用戶接入和用戶身份認(rèn)證等安全要求的首選技術(shù)。用戶將從持有認(rèn)證執(zhí)照的可信發(fā)行者手里取得智能卡安全設(shè)備，也可從其他公共密鑰密碼安全方案發(fā)行者那里獲得。這樣智能卡的讀取器必將成為用戶接入和認(rèn)證安全解決方案的一個(gè)關(guān)鍵部分。智能卡

目前已有的設(shè)備包括：視網(wǎng)膜掃描儀、聲音驗(yàn)證設(shè)備、手型識(shí)別器等。安全性高。例如：系統(tǒng)中存儲(chǔ)了他的指紋，他接入網(wǎng)絡(luò)時(shí)，就必須在連接到網(wǎng)絡(luò)的電子指紋機(jī)上提供他的指紋（這就防止他以假的指紋或其它電子信息欺騙系統(tǒng)），只有指紋相符才允許他訪問系統(tǒng)。更普通的是通過視網(wǎng)膜膜血管分布圖來識(shí)別，原理與指紋識(shí)別相同，聲波紋識(shí)別也是商業(yè)系統(tǒng)采用的一種識(shí)別方式。主體特征認(rèn)證攻擊分析A發(fā)送給B的報(bào)文的被加密，使用的是對(duì)稱密鑰KAB。B收到此報(bào)文后，用共享對(duì)稱密鑰KAB進(jìn)行解密，因而鑒別了實(shí)體A的身份。ABA,口令KAB明顯的漏洞入侵者C可以從網(wǎng)絡(luò)上截獲A發(fā)給B的報(bào)文。C并不需要破譯這個(gè)報(bào)文（因?yàn)檫@可能很花很多時(shí)間）而可以直接把這個(gè)由A加密的報(bào)文發(fā)送給B，使B誤認(rèn)為C就是A。然后B就向偽裝是A的C發(fā)送應(yīng)發(fā)給A的報(bào)文。這就叫做重放攻擊(replayattack)。C甚至還可以截獲A的IP地址，然后把A的IP地址冒充為自己的IP地址（這叫做IP欺騙），使B更加容易受騙。使用不重?cái)?shù)為了對(duì)付重放攻擊，可以使用不重?cái)?shù)(nonce)。不重?cái)?shù)就是一個(gè)不重復(fù)使用的大隨機(jī)數(shù)，即“一次一數(shù)”。使用不重?cái)?shù)進(jìn)行鑒別ABA,RARBKABRARBKAB,時(shí)間中間人攻擊AB我是A中間人C我是ARBRBSKC請(qǐng)把公鑰發(fā)來PKCRBRBSKA請(qǐng)把公鑰發(fā)來PKADATAPKCDATAPKA時(shí)間中間人攻擊說明A向B發(fā)送“我是A”的報(bào)文，并給出了自己的身份。此報(bào)文被“中間人”C截獲，C把此報(bào)文原封不動(dòng)地轉(zhuǎn)發(fā)給B。B選擇一個(gè)不重?cái)?shù)RB發(fā)送給A，但同樣被C截獲后也照樣轉(zhuǎn)發(fā)給A。中間人C用自己的私鑰SKC對(duì)RB加密后發(fā)回給B，使B誤以為是A發(fā)來的。A收到RB后也用自己的私鑰SKA對(duì)RB加密后發(fā)回給B，中途被C截獲并丟棄。B向A索取其公鑰，此報(bào)文被C截獲后轉(zhuǎn)發(fā)給A。C把自己的公鑰PKC冒充是A的發(fā)送給B，而C也截獲到A發(fā)送給B的公鑰PKA。B用收到的公鑰PKC（以為是A的）對(duì)數(shù)據(jù)加密發(fā)送給A。C截獲后用自己的私鑰SKC解密，復(fù)制一份留下，再用A的公鑰PKA對(duì)數(shù)據(jù)加密后發(fā)送給A。A收到數(shù)據(jù)后，用自己的私鑰SKA解密，以為和B進(jìn)行了保密通信。其實(shí)，B發(fā)送給A的加密數(shù)據(jù)已被中間人C截獲并解密了一份。但A和B卻都不知道。

消息認(rèn)證是一種過程，它使得通信的接收方能夠驗(yàn)證所收到的報(bào)文（發(fā)送者和報(bào)文內(nèi)容、發(fā)送時(shí)間、序列等）在傳輸?shù)倪^程中沒有被假冒、偽造和篡改，是否感染上病毒等，即保證信息的完整性和有效性。消息認(rèn)證的在于如何讓接收?qǐng)?bào)文的目的站來鑒別報(bào)文的真?zhèn)?。消息認(rèn)證

保密和認(rèn)證同時(shí)是信息系統(tǒng)安全的兩個(gè)方面，但它們是兩個(gè)不同屬性的問題，認(rèn)證不能自動(dòng)地提供保密性，而保密也不能自然地提供認(rèn)證功能。密鑰源竄擾者信宿信源認(rèn)證編碼器認(rèn)證譯碼器信道安全信道一個(gè)純認(rèn)證系統(tǒng)的模型消息認(rèn)證

消息認(rèn)證的內(nèi)容應(yīng)包括：

(1)證實(shí)報(bào)文的源和宿；

(2)報(bào)文內(nèi)容是否曾受到偶然的或有意的篡改；

(3)報(bào)文的序號(hào)和時(shí)間欄?？傊?，消息認(rèn)證使接收者能識(shí)別：消息的源，內(nèi)容的真?zhèn)?，時(shí)間性和意定的信宿。認(rèn)證只在相應(yīng)通信的雙方之間進(jìn)行，而不允許第三者進(jìn)行上述認(rèn)證。認(rèn)證不一定是實(shí)時(shí)的。消息認(rèn)證內(nèi)容(1)信息加密函數(shù)

用完整信息的密文作為對(duì)信息的認(rèn)證。(2)信息認(rèn)證碼MAC(MessageAuthenticationCode)是對(duì)信源消息的一個(gè)編碼函數(shù)。(3)Hash函數(shù)是一個(gè)公開的函數(shù)，它將任意長的信息映射成一個(gè)固定長度的信息。消息認(rèn)證函數(shù)分為：對(duì)稱密鑰加密函數(shù)，非對(duì)稱密鑰加密函數(shù)信源信宿MEEk(M)DMA方B方kkDk(Ek(M))信息加密函數(shù)(a)常規(guī)加密：具有機(jī)密性，可認(rèn)證(b)公鑰加密：具有機(jī)密性(c)公鑰加密：認(rèn)證和簽名MEEPKb(M)DMA方B方SKb

PKbMEESKa(M)DMA方B方PKa

SKa信息加密函數(shù)(d)公鑰加密：機(jī)密性，可認(rèn)證和簽名MEESKa(M)EEPKb(ESKa(M))A方SKaPKbDESKa(M)DMB方SKbPKa信息加密函數(shù)消息認(rèn)證碼

(MessageAuthenticationCode)是一種實(shí)現(xiàn)消息認(rèn)證的方法。MAC是由消息M和密鑰K的一個(gè)函數(shù)值

MAC=Ck(M)

其中M是變長的消息，K是僅由收發(fā)雙方共享的密鑰，Ck（M）是定長的認(rèn)證碼。MAC消息認(rèn)證設(shè)S為通信中的發(fā)方A發(fā)送的所有可能的信源集合。雙方設(shè)計(jì)一個(gè)編碼法則。發(fā)方A根據(jù)規(guī)則對(duì)信源S進(jìn)行編碼，M表示所有可能的消息集合。發(fā)方A通信時(shí)，發(fā)送的是消息。用簡單的例子說明：設(shè)S={0,1},M={00,01,10,11},定義四個(gè)不同的編碼法則e0,e1,e2,e3。這就構(gòu)成一個(gè)認(rèn)證碼MAC。MAC消息認(rèn)證編碼規(guī)則00011011e001e101e201e301

收發(fā)雙方在通信前先秘密約定使用的編碼法則。（例如，若決定采用e0，則以發(fā)送消息00代表信源0；發(fā)送消息10代表信源1，我們稱消息00和10在e0之下是合法的。而消息01和11在e0之下不合法，收方將拒收這二個(gè)消息。）信息的認(rèn)證和保密是不同的兩個(gè)方面，一個(gè)認(rèn)證碼可具有保密功能，也可沒有保密功能。認(rèn)證編碼的基本方法是要在發(fā)送的消息中引入冗余度，使通過信道傳送的可能序列集Y大于消息集X。MAC消息認(rèn)證

消息認(rèn)證方案KM

用戶B終點(diǎn)C比較||CKCK(M)用戶A源點(diǎn)CM

MAC消息認(rèn)證通信雙方A和B共享密鑰K。當(dāng)A要向B發(fā)消息，確信或已知消息正確的，計(jì)算MAC，并將它附加在消息的后面。發(fā)往預(yù)定的接收者B。接收者使用相同的密鑰K，對(duì)收到的消息M計(jì)算得出新的MAC。將收到的MAC與計(jì)算得出的MAC進(jìn)行比較。1）接收者確信消息未被更改過如果一個(gè)攻擊者更改消息而未更改MAC，那么接收者計(jì)算出的消息將不同于接收到的MAC。因?yàn)榧俣ü粽卟恢涝撁荑€，因此攻擊者不可能更改MAC來對(duì)應(yīng)后更改后的消息。2）接收者確信消息來自所謂的發(fā)送者因?yàn)闆]有其他人知道該密鑰，因此沒有人能為一個(gè)消息準(zhǔn)備合適的MAC。3）接收者確信該序號(hào)的正確性如果消息包括一個(gè)序號(hào)(如用于HDLC，X.25和TCP)，那么，因?yàn)楣粽邿o法成功地更改該序列號(hào)。MAC消息認(rèn)證MAC消息認(rèn)證方案消息認(rèn)證與加密，認(rèn)證與明文連接用戶ACK1(M)K1比較EK2DCK1(M)CCM

||M

M

M

用戶BK2K1CK1[EK2(M)]比較EK2(M)K1EK2K1C||CDK2M

M

M

M

MAC消息認(rèn)證方案消息認(rèn)證與加密，認(rèn)證與密文連接

如一個(gè)合法文件有數(shù)兆字節(jié)長，為了進(jìn)行簽名認(rèn)證，自然按160比特分劃成一塊一塊，用相同的密鑰獨(dú)立地簽每一個(gè)塊。然而，這樣太慢。解決辦法：引入可公開的密碼Hash函數(shù)。它將取任意長度的消息做自變量，結(jié)果產(chǎn)生規(guī)定長度的消息摘要。(如使用數(shù)字簽名標(biāo)準(zhǔn)DSS，消息摘要為160比特)，然后簽名消息摘要。對(duì)數(shù)字簽名來說，Hash函數(shù)h這樣使用：消息：x任意長消息摘要：Z=h(x)160bits

簽名：y=sigk(Z)320bitsHash函數(shù)

哈希函數(shù)可以接受可變長度的數(shù)據(jù)輸入，并生成定長數(shù)據(jù)輸出的函數(shù)。這個(gè)定長的輸出是輸入數(shù)據(jù)的哈希值或稱消息摘要。由于哈希函數(shù)具有單向性的屬性，有時(shí)也叫單向函數(shù)。有時(shí)把消息摘要（哈希）叫做輸入數(shù)據(jù)的數(shù)字指紋。哈希值以函數(shù)H產(chǎn)生：h=H(M)

其中:M是變長的消息，H是一個(gè)將任意長度的消息M映射為一個(gè)較短定長的哈希值h的哈希函數(shù)，H(M)是定長的哈希值。Hash函數(shù)1）H可以作用于一個(gè)任意長度的數(shù)據(jù)分組，產(chǎn)生一個(gè)固定長度的輸出。2）任意給定消息M，計(jì)算h=H（M）容易。3）任意給定h，找到M滿足H（M）=h很難，計(jì)算上不可行性，即單向性。4）任意給定的數(shù)據(jù)塊M，找到不等于M的M’，使H(M)=H(M’)在計(jì)算是不可行性。有時(shí)也稱弱抗沖突。5）找到任意數(shù)據(jù)對(duì)（x,y），滿足H(x)=H(y)是計(jì)算不可行的。有時(shí)也稱強(qiáng)抗沖突。Hash函數(shù)性質(zhì)

簡單哈希函數(shù)的操作即：輸入消息序列。輸入的處理方式是，以迭代的方式每次處理一個(gè)分組。一個(gè)最簡單的哈希函數(shù)是每個(gè)分組按比特異或（XOR）。

將消息M分成N個(gè)定長分組：M1M2M3M4…MN

M1M2M3M4…MN⊕M1⊕M2⊕M3⊕M4⊕…⊕MN

輸入消息分組輸出哈希值

簡單Hash算法簡單Hash算法例如：對(duì)于如下9個(gè)關(guān)鍵字{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dai}設(shè)哈希函數(shù)H(key)=

(Ord(第一個(gè)字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei若添加關(guān)鍵字Zhou,則會(huì)產(chǎn)生沖突比較用戶BKKH||EHEk[M‖H(M)]M‖H(M)H(M)D用戶AM

M

M

M

消息認(rèn)證方案（a）對(duì)附加哈希值的消息進(jìn)行加密HEk[H(M)]KEK比較H||DM

M

(b）對(duì)附加的哈希值進(jìn)行單鑰加密消息認(rèn)證方案用戶AHERa[H(M)]KUaEKRa比較H||DM

M

用戶B(c)對(duì)附加的哈希值進(jìn)行雙鑰加密消息認(rèn)證方案(d）同時(shí)提供保密性和數(shù)字簽名

消息認(rèn)證方案e）各方共享一個(gè)公共的秘密值S的哈希認(rèn)證碼消息認(rèn)證方案（f）通過包含消息和哈希值的整體進(jìn)行加密就能對(duì)方法(e)增加保密功能消息認(rèn)證方案對(duì)Hash函數(shù)的攻擊有兩類(1)強(qiáng)力攻擊（或窮舉攻擊）典型防范：生日攻擊任找23