信息與通信網安全：第二講 密碼學概論

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

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

代換密碼，置換密碼密碼分析現代密碼學

流密碼，分組密碼，公鑰密碼體系理論基礎和應用偽隨機數，數論，函數論第三講古典密碼學代換/置換密碼例Caesar密碼

abcdefghijklmnopqrstuvwxyz

DEFGHIJKLMNOPQRSTUVWXYZABCm=CaesarcipherisashiftsubstitutionE(m)=FDHVDUFLSKHULVDVKLIW

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

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

移位密碼體制是置換密碼體制的一個特例，它僅含26個置換做為密鑰空間。(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=1時退化為單表代換維吉尼亞密碼k=(k1,k2,…kd)Ci+td=Eki(mi+td)=mi+td+kimodq例子q=26,k=RADIO,d=5m=polyalphabeticcipherk=RADIORADIORADIORADIOc=GOOGOCPKTPNTLKQZPKMF其他多表代換密碼博福特密碼與維吉尼亞密碼互為逆變換滾動密鑰密碼周期長度和明文一樣長弗納姆密碼

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

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

ZWPFUPZUDTMOHMQ字母ABCDEFGHIJKLMNOPQRSTUVWXYZ頻數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為密鑰字多表代換密碼分析確定識別多表密碼的參數（粗糙度、重合指數）確定密表個數（重碼分析法）確定各代換表完善保密性令明文熵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)越大，竊聽者從密文提取關于M,C的信息越小對于合法用戶H(M|CK)=0則有I(M,CK)=H(M)完善保密性定理：對于任意保密系統(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)完善保密性定理：對于任意保密系統(tǒng)I(M,C)≥H(M)-H(K)（1）保密系統(tǒng)的密鑰量越小，其密文中含有明文的信息量就越大。（2）若使I(M,C)=0，保密系統(tǒng)為完善的或無條件保密系統(tǒng)（這是唯密文攻擊而言的安全性）。（3）由平均互信息量的非負性，可推出H(M)≤H(K)是完善保密系統(tǒng)存在的必要條件。第四講對稱密碼體系對稱密鑰加密從加密密鑰可以計算出解密密鑰（或反之）（也稱為單鑰或傳統(tǒng)加密）主要密碼體制流密碼、分組密碼優(yōu)缺點加密效率高；密鑰短；可靈活構造各種密碼機制、建造安全性更強的密碼；雙方都必須保持密碼的秘密性；用戶多時密鑰個數巨大；需要常更換密鑰。

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

ki

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

=ci

ki

(mod2)，i0流密碼的實現例：設明文M=(0110010011)2，密鑰K=(0111001001)2。在A，B兩方通信前，A首先通過安全信道（比如信使）把密鑰K送給B，現在要把明文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)點：在出現傳輸錯誤的時候，流密碼加密不會產生錯誤傳播；每次只加密1位，所以可以在沒有存儲器或數據緩沖區(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與明文消息無關，密鑰流獨立于明文，加密變換是無記憶的。自同步流密碼密鑰流不獨立于明文。同步和自同步流密碼Eki()…kI有限記憶kici加密器mi密鑰流生成器同步流密碼

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

長度為l的串

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

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

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

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

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

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

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

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

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

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

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

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

93

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

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

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

加密密鑰PK對明文X加密后，再用解密密鑰SK解密，即可恢復出明文，或寫為：

DSK（EPK（X））=X

②

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

DPK（EPK（X））≠X

③

在計算機上可以容易地產生成對的PK和SK。

④

從已知的PK實際上不可能推導出SK。

⑤

加密和解密的運算可以對調，即：

EPK（DSK（X））=X

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

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

f(x)=(xb)modn

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

而且當給定z后容易找到一種算法Fz，對所有x∈A，易于檢驗是否x∈Az（Az屬于A）

。Az是可用的明文集,

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

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

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

判斷一個大奇數n是否為素數的有效算法，大約需要計算量，當n為256或512位二元數時，用當前計算機可在10分鐘內完成。

已知二大素數p和q，求n=pq只需要一次乘法。但若由n求p和q，則是幾世紀來數論專家的攻關對象！RSA算法

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

1)

任意選取兩個不同的大質數p和q，計算乘積r=p*q；2)

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

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

4)

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

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

C=Pemodr6)

將密文C解密為明文P，計算方法為：

P=Cdmodr

然而只根據r和e（不是p和q）要計算出d是不可能的。因此，任何人都可對明文進行加密，但只有授權用戶（知道d）才可對密文解密。RSA原理證明歐拉函數值Φ(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，設明文P=3,加密C=Pemodr,得到密文C=45,解密P=Cdmodr=3.RSA實質上是一種單表代換:對P≠P’，必有C≠C’；定義域中任一元素（0,p,q除外）是一個明文，也是某個明文相對應的一個密文。不知陷門信息下，極難確定對應關系，同時模指數算法容易實現。RSA的安全RSA算法是第一個既能用于數據加密也能用于數字簽名的算法，因此它為公用網絡上信息的加密和鑒別提供了一種基本的方法。它通常事先生成一對RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網絡服務器中注冊，人們用公鑰加密文件發(fā)送給個人，個人就可以用私鑰解密接受。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。

RSA的安全下面的兩個事實保證了RSA算法的安全有效性：

1)已有確定一個數是不是質數的快速算法；

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

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

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

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

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

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

xR=k2-xP-xQ；

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

P＋P＝θ；（稱P是一個階為2的點）

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

xR=k2-2xP；

-yR=-(kx+b)；橢圓曲線倍點是將橢圓曲線上的點自身相加得到的點。若將E上的一個點自身相加若干次，稱之為點乘操作。xP=P+P+…+P三、點乘操作橢圓曲線橢圓曲線密碼算法離散問題是給定P,Q屬于E求整數n使得Q=nP(nP=P+P+…+P,n個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,計算量O(logn)但已知P,Q求n是非常困難的。ECC加密設A向B發(fā)送信息m

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

2)B選隨機整數KB（私鑰），計算GB=KB*G作為公鑰

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

身份認證又稱作識別(Identification)、實體認證(EntityAuthentication)、身份證實(IdentityVerification)等。

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

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

144

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

146

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

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

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

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

消息認證的內容應包括：

(1)證實報文的源和宿；

(2)報文內容是否曾受到偶然的或有意的篡改；

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

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

PKbMEESKa(M)DMA方B方PKa

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

(MessageAuthenticationCode)是一種實現消息認證的方法。MAC是由消息M和密鑰K的一個函數值

MAC=Ck(M)

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

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

消息認證方案KM

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

MAC消息認證通信雙方A和B共享密鑰K。當A要向B發(fā)消息，確信或已知消息正確的，計算MAC，并將它附加在消息的后面。發(fā)往預定的接收者B。接收者使用相同的密鑰K，對收到的消息M計算得出新的MAC。將收到的MAC與計算得出的MAC進行比較。1）接收者確信消息未被更改過如果一個攻擊者更改消息而未更改MAC，那么接收者計算出的消息將不同于接收到的MAC。因為假定攻擊者不知道該密鑰，因此攻擊者不可能更改MAC來對應后更改后的消息。2）接收者確信消息來自所謂的發(fā)送者因為沒有其他人知道該密鑰，因此沒有人能為一個消息準備合適的MAC。3）接收者確信該序號的正確性如果消息包括一個序號(如用于HDLC，X.25和TCP)，那么，因為攻擊者無法成功地更改該序列號。MAC消息認證MAC消息認證方案消息認證與加密，認證與明文連接用戶ACK1(M)K1比較EK2DCK1(M)CCM

||M

M

M

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

M

M

M

MAC消息認證方案消息認證與加密，認證與密文連接

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

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

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

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

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

將消息M分成N個定長分組：M1M2M3M4…MN

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

輸入消息分組輸出哈希值

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

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

M

M

M

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

M

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

M

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

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