信息安全理論與技術(shù) 4、認(rèn)證與數(shù)字簽名

信息安全基本原理與技術(shù)目錄信息安全概述常見(jiàn)攻擊手段密碼學(xué)知識(shí)認(rèn)證與數(shù)字簽名網(wǎng)絡(luò)安全防御體系訪問(wèn)控制可信計(jì)算概念認(rèn)證(Authentication)：即鑒別、確認(rèn)，它是證實(shí)某事是否名副其實(shí)，或是否有效的一個(gè)過(guò)程。認(rèn)證與加密的區(qū)別：加密用以確保數(shù)據(jù)的保密性，阻止對(duì)手的被動(dòng)攻擊，如截取、竊聽(tīng)。認(rèn)證用以確保報(bào)文發(fā)送者和接受者的真實(shí)性以及報(bào)文的完整性，阻止對(duì)手的主動(dòng)攻擊，如冒充、篡改、重播等。認(rèn)證往往是應(yīng)用系統(tǒng)中安全保護(hù)的第一道防線，極為重要?；舅枷胪ㄟ^(guò)驗(yàn)證稱謂者(人或事)的一個(gè)或多個(gè)參數(shù)的真實(shí)性和有效性，來(lái)達(dá)到驗(yàn)證稱謂者是否名副其實(shí)的目的。常用的參數(shù)有：口令、標(biāo)識(shí)符、密鑰、信物、智能卡、指紋、視網(wǎng)紋等。利用人的生理特征參數(shù)進(jìn)行認(rèn)證的安全性高，但技術(shù)要求也高，至今尚未普及。目前廣泛應(yīng)用的還是基于密碼的認(rèn)證技術(shù)。沒(méi)有消息認(rèn)證的通信系統(tǒng)是極為危險(xiǎn)的消息認(rèn)證(MessageAuthentication)消息認(rèn)證用于抗擊主動(dòng)攻擊驗(yàn)證接收消息的真實(shí)性和完整性真實(shí)性的確是由所聲稱的實(shí)體發(fā)過(guò)來(lái)的完整性未被篡改、插入和刪除驗(yàn)證消息的順序性和時(shí)間性（未重排、重放和延遲）需求泄密：將消息透露給沒(méi)有合法秘密鑰的任何人或程序。傳輸分析：分析通信雙方的通信模式，如連接頻率，時(shí)間等偽裝：攻擊者產(chǎn)生一條消息并聲稱來(lái)自某合法實(shí)體內(nèi)容修改：對(duì)消息進(jìn)行插入、刪除、轉(zhuǎn)化、修改順序修改：對(duì)消息順序進(jìn)行插入、刪除、重新排序計(jì)時(shí)修改：對(duì)消息的延時(shí)和重放發(fā)送方否認(rèn)接受方否認(rèn)對(duì)付1、2可用加密；對(duì)付3、4、5、6可用消息認(rèn)證；對(duì)付7、8可用數(shù)字簽名消息認(rèn)證的基本概念消息認(rèn)證：驗(yàn)證所收到的消息確定是來(lái)自真正的發(fā)送方且未被修改過(guò)。認(rèn)證符：一個(gè)用來(lái)認(rèn)證消息的值。由消息的發(fā)送方產(chǎn)生認(rèn)證符，并傳遞給接收方。認(rèn)證函數(shù)：產(chǎn)生認(rèn)證符的函數(shù)，認(rèn)證函數(shù)實(shí)際上代表了一種產(chǎn)生認(rèn)證符的方法。消息加密消息認(rèn)證碼Hash函數(shù)消息加密---在對(duì)稱加密體制下由于攻擊者不知道密鑰K，他也就不知道如何改變密文中的信息位才能在明文中產(chǎn)生預(yù)期的改變。接收方可以根據(jù)解密后的明文是否具有合理的語(yǔ)法結(jié)構(gòu)來(lái)進(jìn)行消息認(rèn)證。但有時(shí)發(fā)送的明文本身并沒(méi)有明顯的語(yǔ)法結(jié)構(gòu)或特征，例如二進(jìn)制文件，因此很難確定解密后的消息就是明文本身。MEKEK(M)DKM根據(jù)明文M和公開(kāi)的函數(shù)F產(chǎn)生FCS，即錯(cuò)誤檢測(cè)碼，或幀校驗(yàn)序列，校驗(yàn)和。把M和FCS合在一起加密，并傳輸。接收端把密文解密，得到M。根據(jù)得到的M，按照F計(jì)算FCS，并與接收到的FCS比較是否相等。MFFMFCS比較EKDKMFCS內(nèi)部錯(cuò)誤控制攻擊者可以構(gòu)造具有正確錯(cuò)誤控制碼的消息，雖然攻擊者不知道解密后的明文，但可以造成混淆并破壞通信。MFFCSEKDKM外部錯(cuò)誤控制F比較消息加密---在公鑰加密體制下由于大家都知道B的公鑰，所以這種方式不提供認(rèn)證，只提供加密。MEKUbEKUb(M)DKRbMI.普通加密AB消息加密---在公鑰加密體制下由于只有A有用于產(chǎn)生EKRa(M)的密鑰，所以此方法提供認(rèn)證。由于大家都有KUa

，所以此方法不提供加密。MEKRaEKRa(M)DKUaMII.認(rèn)證和簽名AB消息加密---在公鑰加密體制下提供認(rèn)證和加密。一次通信中要執(zhí)行四次復(fù)雜的公鑰算法。MEKRaEKRa(M)DKUaMIII.加密認(rèn)證和簽名ABEKUbEKUb(EKRa(M))DKRbEKRa(M)消息認(rèn)證碼(MAC)MessageAuthenticaionCode消息認(rèn)證碼是消息和密鑰的公開(kāi)函數(shù)，它產(chǎn)生定長(zhǎng)的值，以該值作為認(rèn)證符。利用密鑰和消息生成一個(gè)固定長(zhǎng)度的短數(shù)據(jù)塊，并將其附加在消息之后。通信雙方共享密鑰K消息認(rèn)證碼用于認(rèn)證A和B共享密鑰KA計(jì)算MAC=Ck(M),M和MAC一起發(fā)送到BB對(duì)收到的M，計(jì)算MAC，比較兩個(gè)MAC是否相同。MCMACKC比較KMAC如果兩個(gè)MAC相等，則：接收方可以相信消息未被修改，因?yàn)槿绻粽吒淖兞讼?，由于不知道k，無(wú)法生成正確的MAC。接收方可以相信消息的確來(lái)自確定的發(fā)送方。因?yàn)槠渌瞬荒苌珊驮枷⑾鄳?yīng)的MAC。MAC函數(shù)與加密函數(shù)的區(qū)別MAC函數(shù)與加密函數(shù)類似，都需要明文、密鑰和算法的參與。但MAC算法不要求可逆性，而加密算法必須是可逆的。例如：使用100比特的消息和10比特的MAC，那么總共有2100個(gè)不同的消息，但僅有210個(gè)不同的MAC。也就是說(shuō)，平均每290個(gè)消息使用的MAC是相同的。因此，認(rèn)證函數(shù)比加密函數(shù)更不易被攻破，因?yàn)榧幢愎テ埔矡o(wú)法驗(yàn)證其正確性。關(guān)鍵就在于加密函數(shù)是一對(duì)一的，而認(rèn)證函數(shù)是多對(duì)一的。消息認(rèn)證碼的基本用途只提供消息認(rèn)證，不提供保密性。（見(jiàn)前）提供消息認(rèn)證和保密性：M||CK1CMCK(M)K1比較EK2DK2ABA和B共享K1和K2K1：用于生成MACK2：用于加密與明文有關(guān)的認(rèn)證消息認(rèn)證碼的基本用途提供消息認(rèn)證和保密性：ABA和B共享K1和K2K1：用于生成MACK2：用于加密與密文有關(guān)的認(rèn)證M||CK1CK1比較EK2DK2對(duì)MAC的攻擊—攻擊密鑰已知消息M1和MAC算法C，以及MAC1=

Ck1(M1)

，現(xiàn)要破解k1。密鑰為k個(gè)bit，MAC為n個(gè)bit。當(dāng)k>n：可能的密鑰個(gè)數(shù)為2k。可能的MAC個(gè)數(shù)為2n個(gè)。

所以許多不同的密鑰(約2k-n個(gè))，計(jì)算出來(lái)的MAC都等于MAC1。這些密鑰中哪一個(gè)是正確的密鑰不得而知。這時(shí)需要新的M-MAC對(duì)來(lái)測(cè)試這2k-n個(gè)密鑰，于是有如下的重復(fù)攻擊：重復(fù)攻擊Step1:給定M1和MAC1=

Ck1(M1)

對(duì)所有2k個(gè)密鑰，判斷MACi=

Cki(M1)

匹配數(shù)約為：2k-nStep2:給定M2和MAC2=

Ck2(M1)對(duì)所有2k個(gè)密鑰，判斷MACi=

Cki(M2)匹配數(shù)約為：2k-2n平均來(lái)講，若k=x*n，則需x次循環(huán)才能找到正確的密鑰。所以，用窮舉法攻破MAC比攻破加密算法要困難得多。對(duì)MAC的攻擊—攻擊算法考慮下面的算法：

消息M=(X1‖X2‖…‖Xm)是由64比特長(zhǎng)的分組Xi(i=1,…,m)鏈接而成

MAC算法是：加密算法是DES。因此，密鑰長(zhǎng)為56比特。如果敵手得到M‖CK(M)，那么敵手使用窮搜索攻擊尋找K將需做256次加密。很困難!但攻擊者可以改變M的內(nèi)容，卻使MAC正確。方法如下：用Y1替換X1，Y2替換X2，…，Ym替換Xm，其中Y1

，Y2

，…，Ym

是攻擊者編造的假消息。且

Ym=Y1Y2…Ym-1Δ(M)，當(dāng)接收者收到這個(gè)消息：M’=(Y1‖Y2‖…‖Ym)

則Δ(M’)=Y1Y2…Ym

=

Δ(M)所以：CK(M)=CK(M’)通過(guò)了驗(yàn)證，攻擊得逞。MAC函數(shù)應(yīng)具有的性質(zhì)若攻擊者已知M和CK(M)，則他構(gòu)造滿足：

CK(M)=CK(M’)的消息M’在計(jì)算上不可行CK(M)應(yīng)試均勻分布的，即對(duì)于隨機(jī)消息M和M’，

CK(M)=CK(M’)的概率是2-n，n是MAC的位數(shù)基于DES的消息認(rèn)證碼使用最廣泛的MAC算法之一：數(shù)據(jù)認(rèn)證算法過(guò)程：把需要認(rèn)證的數(shù)據(jù)分成連續(xù)的64位的分組。若最后一個(gè)分組不是64位，則填0利用DES加密算法E和密鑰K，計(jì)算認(rèn)證碼。數(shù)據(jù)認(rèn)證算法似乎可以滿足前面提出的要求。DACM-bits(16to64bits)為什么不直接使用加密而使用分離的消息認(rèn)證碼？保密性與真實(shí)性是兩個(gè)不同的概念根本上,信息加密提供的是保密性而非真實(shí)性加密代價(jià)大(公鑰算法代價(jià)更大)鑒別函數(shù)與保密函數(shù)的分離能提供功能上的靈活性某些信息只需要真實(shí)性,不需要保密性廣播的信息難以使用加密(信息量大)網(wǎng)絡(luò)管理信息等只需要真實(shí)性政府/權(quán)威部門(mén)的公告Hash函數(shù)(雜湊函數(shù)、散列函數(shù))Hash的特點(diǎn)：與消息認(rèn)證碼一樣，hash函數(shù)的輸入是可變的消息M，輸出是固定大小的hash碼H(M)，或稱消息摘要(MessageDigest)

、hash值。與消息認(rèn)證碼不同的是，hash碼的產(chǎn)生過(guò)程中并不使用密鑰。Hash碼是所有消息的函數(shù)，改變消息的任何一位或多位，都會(huì)導(dǎo)致hash碼的改變。Hash算法通常是公開(kāi)的。又稱為：哈希函數(shù)、數(shù)字指紋（Digitalfingerprint)、壓縮（Compression)函數(shù)、緊縮（Contraction）函數(shù)、數(shù)據(jù)鑒別碼DAC（Dataauthenticationcode）、篡改檢驗(yàn)碼MDC(Manipulationdetectioncode)h=H(M)假定兩次輸入同樣的數(shù)據(jù)，那么散列函數(shù)應(yīng)該能夠生成相同的散列值。輸入數(shù)據(jù)中的一位發(fā)生了變化，會(huì)導(dǎo)致生成的散列值完全不一樣。散列函數(shù)有個(gè)非常重要的特性為單向性，也就是從M計(jì)算h容易，而從h計(jì)算M不可能。

散列函數(shù)H必須滿足以下幾個(gè)性質(zhì)H對(duì)于任何大小的數(shù)據(jù)分組，都能產(chǎn)生定長(zhǎng)的輸出。對(duì)于任何給定的M，H(M)要相對(duì)易于計(jì)算。單向性：對(duì)于任何給定的hash值h，計(jì)算出M在計(jì)算上不可行。弱無(wú)碰撞性：對(duì)任何給定的M1，尋找M2，使H(M1)=H(M2)在計(jì)算上不可行。強(qiáng)無(wú)碰撞性：尋找任何的（M1，M2），使H(M1)=H(M2)在計(jì)算上不可行。Hash與MAC的區(qū)別MAC需要對(duì)全部數(shù)據(jù)進(jìn)行加密MAC速度慢Hash是一種直接產(chǎn)生鑒別碼的方法Hash可用于數(shù)字簽名常用Hash算法迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L(zhǎng)個(gè)分組Y0,Y1,…,YL-1b:明文分組長(zhǎng)度n:輸出hash長(zhǎng)度CV：各級(jí)輸出，最后一個(gè)輸出值是hash值無(wú)碰撞壓縮函數(shù)f是設(shè)計(jì)的關(guān)鍵迭代型hash函數(shù)這種結(jié)構(gòu)的hash函數(shù)已被證明是合理的，如果采用其他結(jié)構(gòu)，不一定安全。設(shè)計(jì)新的hash函數(shù)只是改進(jìn)這種結(jié)構(gòu)，或者增加hash碼長(zhǎng)。算法的核心技術(shù)是設(shè)計(jì)無(wú)碰撞的壓縮函數(shù)f，而敵手對(duì)算法的攻擊重點(diǎn)是f的內(nèi)部結(jié)構(gòu)，由于f和分組密碼一樣是由若干輪處理過(guò)程組成，所以對(duì)f的攻擊需通過(guò)對(duì)各輪之間的位模式的分析來(lái)進(jìn)行，分析過(guò)程常常需要先找出f的碰撞。由于f是壓縮函數(shù)，其碰撞是不可避免的，因此在設(shè)計(jì)f時(shí)就應(yīng)保證找出其碰撞在計(jì)算上是不可行的。MD5hash算法

MD5HashAlgorithm

MD4是MD5雜湊算法的前身，由RonRivest于1990年10月作為RFC提出，1992年4月公布的MD4的改進(jìn)（RFC1320，1321）稱為MD5。MD5的算法框圖輸入消息可任意長(zhǎng)，壓縮后輸出為128bits。算法步驟(1)－分組填充

消息100…064bit消息長(zhǎng)度填充圖樣L×512bitKbit如果消息長(zhǎng)度大于264，則取其對(duì)264的模。執(zhí)行完后，消息的長(zhǎng)度為512的倍數(shù)（設(shè)為L(zhǎng)倍），則可將消息表示為分組長(zhǎng)為512的一系列分組Y0，Y1，…，YL-1，而每一分組又可表示為16個(gè)32比特長(zhǎng)的字，這樣消息中的總字?jǐn)?shù)為N=L×16，因此消息又可按字表示為M[0,…,N-1]。算法步驟(2)－緩沖區(qū)初始化hash函數(shù)的中間結(jié)果和最終結(jié)果保存于128位的緩沖區(qū)中，緩沖區(qū)用32位的寄存器表示?？捎?個(gè)32bits字表示：A,B,C,D。初始存數(shù)以十六進(jìn)制表示為A=01234567B=89ABCDEFC=FEDCBA98D=76543210算法步驟(3)-HMD5運(yùn)算以分組為單位對(duì)消息進(jìn)行處理每一分組Yq(q=0,…,L-1)都經(jīng)一壓縮函數(shù)HMD5處理。HMD5是算法的核心，其中又有4輪處理過(guò)程。HMD5的4輪處理過(guò)程結(jié)構(gòu)一樣，但所用的邏輯函數(shù)不同，分別表示為F、G、H、I。每輪的輸入為當(dāng)前處理的消息分組Yq和緩沖區(qū)的當(dāng)前值A(chǔ)、B、C、D，輸出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。每輪又要進(jìn)行16步迭代運(yùn)算，4輪共需64步完成。第四輪的輸出與第一輪的輸入相加得到最后的輸出。壓縮函數(shù)中的一步迭代基本邏輯函數(shù)定義

輪基本函數(shù)gg(b,c,d)fFF(b,c,d)(b^c)V(bˉ^d)fGG(b,c,d)(b^d)V(c^dˉ)fHH(b,c,d)b?c?dfII(b,c,d)c?(bV

dˉ)X[k]當(dāng)前分組的第k個(gè)32位的字。第1輪x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x[8]x[9]x[10]x[11]x[12]x[13]x[14]x[15]第2輪x[1]x[6]x[11]x[0]x[5]x[10]x[15]x[4]x[9]x[14]x[3]x[8]x[13]x[2]x[7]x[12]第3輪x[5]x[8]x[11]x[14]x[1]x[4]x[7]x[10]x[13]x[0]x[3]x[6]x[9]x[12]x[15]x[2]第4輪x[0]x[7]x[14]x[5]x[12]x[3]x[10]x[1]x[8]x[15]x[6]x[13]x[4]x[11]x[2]x[9]T[i]T[1,…,64]為64個(gè)元素表，分四組參與不同輪的計(jì)算。T[i]為232×abs(Sin(i))的整數(shù)部分，i是弧度。T[i]可用32bit二元數(shù)表示，T是32bit隨機(jī)數(shù)源。T[1]=d76aa478T[17]=f61e2562T[33]=fffa3942T[49]=f4292244T[2]=e8c7b756T[18]=c040b340T[34]=8771f681T[50]=432aff97T[3]=242070dbT[19]=265e5a51T[35]=6d9d6122T[51]=ab9423a7T[4]=c1bdceeeT[20]=e9b6c7aaT[36]=fde5380cT[52]=fc93a039T[5]=f57c0fafT[21]=d62f105dT[37]=a4beea44T[53]=655b59c3T[6]=4787c62aT[22]=02441453T[38]=4bdecfa9T[54]=8f0ccc92T[7]=a8304613T[23]=d8a1e681T[39]=f6bb4b60T[55]=ffeff47dT[8]=fd469501T[24]=e7d3fbc8T[40]=bebfbc70T[56]=85845dd1T[9]=698098d8T[25]=21e1cde6T[41]=289b7ec6T[57]=6fa87e4fT[10]=8b44f7afT[26]=c33707d6T[42]=eaa127faT[58]=fe2ce6e0T[11]=ffff5bb1T[27]=f4d50d87T[43]=d4ef3085T[59]=a3014314T[12]=895cd7beT[28]=455a14edT[44]=04881d05T[60]=4e0811a1T[13]=6b901122T[29]=a9e3e905T[45]=d9d4d039T[61]=f7537e82T[14]=fd987193T[30]=fcefa3f8T[46]=e6db99e5T[62]=bd3af235T[15]=a679438eT[31]=676f02d9T[47]=1fa27cf8T[63]=2ad7d2bbT[16]=49b40821T[32]=8d2a4c8aT[48]=c4ac5665T[63]=eb86d391CLSs：循環(huán)左移s位第一輪：7、12、17、22第二輪：5、9、14、20第三輪：4、11、16、23第四輪：6、10、15、21MD-5的安全性MD-5的輸出為128-bit，若采用純強(qiáng)力攻擊尋找一個(gè)消息具有給定Hash值的計(jì)算困難性為2128，用每秒可試驗(yàn)1000000000個(gè)消息的計(jì)算機(jī)需時(shí)1.07×1022年。采用生日攻擊法，找出具有相同雜湊值的兩個(gè)消息需執(zhí)行264次運(yùn)算。SHA算法SecureHashAlgorithm算法簡(jiǎn)介美國(guó)標(biāo)準(zhǔn)與技術(shù)研究所NIST設(shè)計(jì)1993年成為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPSPUB180)基于MD4算法，與之非常類似。輸入為小于264比特長(zhǎng)的任意消息分組512bit長(zhǎng)輸出160bit迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L(zhǎng)個(gè)分組Y0,Y1,…,YL-1b:明文分組長(zhǎng)度n:輸出hash長(zhǎng)度CV：各級(jí)輸出，最后一個(gè)輸出值是hash值無(wú)碰撞壓縮函數(shù)f是設(shè)計(jì)的關(guān)鍵算法描述消息填充：與MD5完全相同附加消息長(zhǎng)度：64bit長(zhǎng)度緩沖區(qū)初始化A＝67452301B＝EFCDAB89C＝98BADCFBD＝10325476E＝C3D2E1F0分組處理模232加SHA-1壓縮函數(shù)（單步）ft----基本邏輯函數(shù)CLS5：32位的變量循環(huán)左移5位。CLS30：32位的變量循環(huán)左移30位。Wt---從當(dāng)前512位輸入分組導(dǎo)出的32位字前16個(gè)值（即W0,W1,…,W15）直接取為輸入分組的16個(gè)相應(yīng)的字，其余值（即W16,W17,…,W79）取為Kt---加法常量步驟十六進(jìn)制0≤t≤19Kt=5A82799920≤t≤39Kt=6ED9EBA140≤t≤59Kt=8F1BBCDC60≤t≤79Kt=CA62C1D6SHA與MD5的比較抗窮舉搜索能力尋找指定hash值，SHA：O(2160)，MD5：O(2128)生日攻擊：SHA：O(280)，MD5：O(264)抗密碼分析攻擊的強(qiáng)度SHA似乎高于MD5速度SHA較MD5慢簡(jiǎn)捷與緊致性描述都比較簡(jiǎn)單，都不需要大的程序和代換表其它hash算法MD4MD4使用三輪運(yùn)算，每輪16步；MD5使用四輪運(yùn)算，每輪16步。MD4的第一輪沒(méi)有使用加法常量，第二輪運(yùn)算中每步迭代使用的加法常量相同，第三輪運(yùn)算中每步迭代使用的加法常量相同，但不同于第二輪使用的加法常量；MD5的64步使用的加法常量T[i]均不同。MD4使用三個(gè)基本邏輯函數(shù)，MD5使用四個(gè)。MD5中每步迭代的結(jié)果都與前一步的結(jié)果相加，MD4則沒(méi)有。MD5比MD4更復(fù)雜，所以其執(zhí)行速度也更慢，Rivest認(rèn)為增加復(fù)雜性可以增加安全性。RIPEMD-160歐共體RIPE項(xiàng)目組研制。輸入可以是任意長(zhǎng)的報(bào)文，輸出160位摘要。對(duì)輸入按512位分組。以分組為單位處理。算法的核心是具有十輪運(yùn)算的模塊，十輪運(yùn)算分成兩組，每組五輪，每輪16步迭代。對(duì)Hash函數(shù)的攻擊對(duì)一個(gè)hash算法的攻擊可分三個(gè)級(jí)別：預(yù)映射攻擊（PreimageAttack）：給定Hash值h，找到其所對(duì)應(yīng)的明文M，使得Hash(M)=h，這種攻擊是最徹底的，如果一個(gè)hash算法被人找出預(yù)映射，那這種算法是不能使用的。次預(yù)映射攻擊（SecondPreimageAttack）：給定明文M1，找到另一明文M2（M1≠M(fèi)2），使得hash(M1)=hash(M2)，這種攻擊其實(shí)就是要尋找一個(gè)弱碰撞；碰撞攻擊(CollisionAttack)：找到M1和M2，使得hash(M1)=hash(M2)，這種攻擊其實(shí)就是要尋找一個(gè)強(qiáng)碰撞。生日攻擊給定一個(gè)散列函數(shù)H和某hash值H(x)，假定H有n個(gè)可能的輸出。如果H有k個(gè)隨機(jī)輸入,k必須為多大才能使至少存在一個(gè)輸入y,使得H(y)=H(x)的概率大于0.5？K=n/2結(jié)論如果hash碼為m位，則有2m個(gè)可能的hash碼。如果給定h=H(X)，要想找到一個(gè)y，使H(y)=h的概率為0.5，則要進(jìn)行多次的嘗試，嘗試的次數(shù)k=2m/2=2m-1所以，對(duì)于一個(gè)使用64位的hash碼，攻擊者要想找到滿足H(M’)=H(M)的M’來(lái)替代M，平均來(lái)講，他要找到這樣的消息大約要進(jìn)行263次嘗試。但是，存在一種攻擊，稱為“生日攻擊”，卻可以大大減小嘗試的次數(shù)，對(duì)于64位的hash碼，所需的代價(jià)僅為232次。生日悖論一個(gè)教室中，最少應(yīng)有多少學(xué)生，才使至少有兩人具有相同生日的概率不小于1/2？概率結(jié)果與人的直覺(jué)是相違背的.實(shí)際上只需23人,即任找23人，從中總能選出兩人具有相同生日的概率至少為1/2。一個(gè)不等式：(1-x)≤e-x(x≥0)當(dāng)x很小，趨近于0時(shí)，(1-x)≈e-x兩個(gè)集合中元素的重復(fù)給定兩個(gè)集合X和Y，每個(gè)集合有k個(gè)元素：

X:{x1,x2,…,xk},Y:{y1,y2,…,yk},其中，各元素的取值是1~n之間的均勻分布的隨機(jī)值(k<n)那么，這兩個(gè)集合中至少有一個(gè)元素相同(重復(fù))的概率R(n,k)是多少呢？給定x1，那么y1=x1的概率為1/n，所以y1≠x1的概率為1-1/n。那么Y中的k個(gè)值都不等于x1的概率為(1-1/n)k同理，給定x2，那么Y中的k個(gè)值都不等于x2的概率為(1-1/n)k同理，給定xk，那么Y中的k個(gè)值都不等于xk的概率為(1-1/n)k所以，Y中沒(méi)有元素與X中元素相同的概率為：那么，Y中至少有一個(gè)元素與X中元素相同的概率為：根據(jù)不等式：(1-x)≤e-x(x≥0)可知：

實(shí)施生日攻擊前面提到過(guò)，對(duì)于一個(gè)使用64位的hash碼，攻擊者要想找到滿足H(M’)=H(M)的M’來(lái)替代M，平均來(lái)講，他要找到這樣的消息大約要進(jìn)行263次嘗試。這太困難了！設(shè)M和hash算法生成64位的hash值。攻擊者可以根據(jù)M，產(chǎn)生232個(gè)表達(dá)相同含義的變式(例如在詞與詞之間多加一個(gè)空格)。同時(shí)準(zhǔn)備好偽造的消息M’，產(chǎn)生232個(gè)表達(dá)相同含義的變式。在這兩個(gè)集合中，找出產(chǎn)生相同hash碼的一對(duì)消息M1和M1’。根據(jù)生日悖論，找到這樣一對(duì)消息的概率大于0.5。最后，攻擊者將拿M1給發(fā)送者簽名，但發(fā)送時(shí)，把M1’和經(jīng)加密的hash碼一起發(fā)送。BirthdayAttacks:exampleA準(zhǔn)備兩份合同M和M′，一份B會(huì)同意，一份會(huì)取走他的財(cái)產(chǎn)而被拒絕A對(duì)M和M′各做32處微小變化(保持原意),分別產(chǎn)生232個(gè)64位hash值根據(jù)前面的結(jié)論,超過(guò)0.5的概率能找到一個(gè)M和一個(gè)M′,它們的hash值相同A提交M,經(jīng)B審閱后產(chǎn)生64位hash值并對(duì)該值簽名,返回給AA用M′替換M身份認(rèn)證身份認(rèn)證是驗(yàn)證主體的真實(shí)身份與其所聲稱的身份是否符合的過(guò)程。認(rèn)證的結(jié)果只有兩個(gè)：符合和不符合。適用于用戶、進(jìn)程、系統(tǒng)、信息等。身份認(rèn)證的例子郵件登錄Client與Server之間的鑒別Telnet遠(yuǎn)程登錄Ftp服務(wù)登錄到某臺(tái)電腦上身份認(rèn)證系統(tǒng)的組成出示證件的人，稱作示證者P(Prover)，又稱聲稱者(Claimant)。驗(yàn)證者V（Verifier),檢驗(yàn)聲稱者提出的證件的正確性和合法性，決定是否滿足要求。第三方是可信賴者TP（Trustedthirdparty)，參與調(diào)解糾紛。在許多應(yīng)用場(chǎng)合下沒(méi)有第三方。身份認(rèn)證的物理基礎(chǔ)Somethingtheuserknow(例如口令)簡(jiǎn)單，但不安全設(shè)計(jì)依據(jù)安全水平、系統(tǒng)通過(guò)率、用戶可接受性、成本等身份認(rèn)證的物理基礎(chǔ)Somethingtheuserpossesses(例如證件)認(rèn)證系統(tǒng)相對(duì)復(fù)雜身份認(rèn)證的物理基礎(chǔ)Somethingtheuseris(例如指紋識(shí)別)更復(fù)雜,而且有時(shí)會(huì)牽涉到本人意愿身份認(rèn)證方式單向認(rèn)證（One-wayAuthentication）雙向認(rèn)證（Two-wayAuthentication）信任的第三方認(rèn)證（TrustedThird-partyAuthentication）單向認(rèn)證通信的一方認(rèn)證另一方的身份用對(duì)稱密碼體制來(lái)實(shí)現(xiàn)單向認(rèn)證某函數(shù)變換f雙方共享的密鑰KS隨機(jī)數(shù)RA用非對(duì)稱密碼體制來(lái)實(shí)現(xiàn)單向認(rèn)證隨機(jī)數(shù)RAB的私鑰KSB雙向認(rèn)證

雙方都要提供用戶名和密碼給對(duì)方，才能通過(guò)認(rèn)證。

用對(duì)稱密碼體制來(lái)實(shí)現(xiàn)雙向認(rèn)證A產(chǎn)生一個(gè)隨機(jī)數(shù)RA雙方共享的密鑰KSB產(chǎn)生一個(gè)隨機(jī)數(shù)RB用非對(duì)稱密碼體制來(lái)實(shí)現(xiàn)雙向認(rèn)證A產(chǎn)生一個(gè)隨機(jī)數(shù)RAB產(chǎn)生一個(gè)隨機(jī)數(shù)RBB的私鑰KSBA的私鑰KSA信任的第三方認(rèn)證

當(dāng)兩端欲進(jìn)行連線時(shí)，彼此必須先通過(guò)信任第三方的認(rèn)證，然后才能互相交換密鑰，而后進(jìn)行通信一種第三方認(rèn)證機(jī)制SKAU：管理員的私鑰PKB：B的公鑰PKA：A的公鑰N1：A的臨時(shí)交互號(hào)N2：B產(chǎn)生的新臨時(shí)交互號(hào)Kerberos協(xié)議Kerberos是在80年中期作為美國(guó)麻省理工學(xué)院“雅典娜計(jì)劃”（ProjectAthena）的一部分被開(kāi)發(fā)的。Kerberos是一個(gè)分布式的認(rèn)證服務(wù)，它允許一個(gè)進(jìn)程（或客戶）代表一個(gè)主體（或用戶）向驗(yàn)證者證明他的身份，而不需要通過(guò)網(wǎng)絡(luò)發(fā)送那些有可能會(huì)被攻擊者用來(lái)假冒主體身份的數(shù)據(jù)。Kerberos協(xié)議的應(yīng)用環(huán)境

KerberosClientServerKerberos系統(tǒng)架構(gòu)Kerberosv4認(rèn)證協(xié)議的流程(1)客戶端認(rèn)證Kerberosv4認(rèn)證協(xié)議的流程(2)取得與服務(wù)器通信的票據(jù)Kerberosv4認(rèn)證協(xié)議的流程(3)客戶端與服務(wù)器通信零知識(shí)證明Alice:“我知道聯(lián)邦儲(chǔ)備系統(tǒng)計(jì)算的口令”Bob:“不，你不知道”Alice：我知道Bob：你不知道Alice：我確實(shí)知道Bob：請(qǐng)你證實(shí)這一點(diǎn)Alice：好吧，我告訴你。（她悄悄說(shuō)出了口令）Bob：太有趣了！現(xiàn)在我也知道了。我要告訴《華盛頓郵報(bào)》Alice：啊呀！零知識(shí)證明技術(shù)零知識(shí)證明技術(shù)可使信息的擁有者無(wú)需泄露任何信息就能夠向驗(yàn)證者或任何第三方證明它擁有該信息。零知識(shí)證明的基本協(xié)議

設(shè)P知道咒語(yǔ)，可打開(kāi)C和D之間的秘密門(mén)，不知道者都將走向死胡同中。ABCD零知識(shí)證明的基本協(xié)議

(1)V站在A點(diǎn)；

(2)P進(jìn)入洞中任一點(diǎn)C或D；

(3)當(dāng)P進(jìn)洞之后，V走到B點(diǎn)；

(4)V叫P：(a)從左邊出來(lái)，或(b)從右邊出來(lái)；

(5)P按要求實(shí)現(xiàn)(以咒語(yǔ)，即解數(shù)學(xué)難題幫助)；

(6)P和V重復(fù)執(zhí)行(1)～(5)共n次。若A不知咒語(yǔ)，則在B點(diǎn)，只有50%的機(jī)會(huì)猜中B的要求，協(xié)議執(zhí)行n次，則只有2-n的機(jī)會(huì)完全猜中，若n=16，則若每次均通過(guò)B的檢驗(yàn)，B受騙機(jī)會(huì)僅為1/65536最簡(jiǎn)單的零知識(shí)證明問(wèn)題要求：假如P想說(shuō)服V，使V相信他確實(shí)知道n的因數(shù)p和q，但不能告訴V最簡(jiǎn)單的步驟：V隨機(jī)選擇一整數(shù)x，計(jì)算x4modn的值，并告訴PP求x2modn并將它告訴VV驗(yàn)證x4modnV知道求x2modn等價(jià)于n的因數(shù)分解，若不掌握n的因數(shù)p和q，求解很困難。數(shù)字簽名消息認(rèn)證碼的不足可以保護(hù)通信雙方以防止第3者攻擊，不能保護(hù)通信雙方中一方防止另一方的欺騙和偽造。B偽造一個(gè)消息并使用與A共享的密鑰產(chǎn)生該消息的認(rèn)證碼，然后聲稱該消息來(lái)自于AB有可能偽造A發(fā)來(lái)的消息，所以A就可以對(duì)自己發(fā)過(guò)的消息予以否認(rèn)數(shù)字簽名的基本概念數(shù)字簽名由公鑰密碼發(fā)展而來(lái)，它在網(wǎng)絡(luò)安全，包括身份認(rèn)證、數(shù)據(jù)完整性、不可否認(rèn)性以及匿名性等方面有著重要應(yīng)用。手寫(xiě)簽名的特征簽名是可信的簽名是不可偽造的簽名不可重用簽名后的文件是不可變的簽名是不可抵賴的簡(jiǎn)單掃描手寫(xiě)簽名是不能滿足要求的對(duì)數(shù)字簽名的要求要保證能夠驗(yàn)證作者及其簽名的日期時(shí)間必須能夠認(rèn)證簽名時(shí)刻的內(nèi)容簽名必須能夠由第三方驗(yàn)證，以解決爭(zhēng)議。更進(jìn)一步的要求依賴性：簽名必須是依賴于被簽名信息來(lái)產(chǎn)生；唯一性：簽名必須使用某些對(duì)發(fā)送者是唯一的信息，以防止雙方的偽造與否認(rèn)；可驗(yàn)性：必須相對(duì)容易識(shí)別和驗(yàn)證該數(shù)字簽名；抗偽造：偽造該數(shù)字簽名在計(jì)算上是不可行的，根據(jù)一個(gè)已有的數(shù)字簽名來(lái)構(gòu)造消息是不可行的；對(duì)一個(gè)給定消息偽造數(shù)字簽名是不可行的；可用性：在存儲(chǔ)器中保存一個(gè)數(shù)字簽名副本是現(xiàn)實(shí)可行的。簽名方法直接數(shù)字簽名方法仲裁數(shù)字簽名方法直接數(shù)字簽名AB消息加密后的摘要消息散列函數(shù)A的私鑰摘要加密算法消息加密后的摘要A的公鑰解密算法解密后的摘要散列函數(shù)摘要比較加密后的摘要直接數(shù)字簽名的缺點(diǎn)直接數(shù)字簽名的執(zhí)行過(guò)程只有通信的雙方參與，并假定雙方有共享的秘密密鑰或者接收一方知道發(fā)送方的公開(kāi)鑰。缺點(diǎn)：方案的有效性取決于發(fā)方密鑰的安全性。發(fā)方可聲稱秘密鑰丟失或被竊仲裁數(shù)字簽名具有仲裁方式的數(shù)字簽名發(fā)方X對(duì)發(fā)往收方Y(jié)的消息簽名將消息和簽名先發(fā)往仲裁者AA對(duì)消息和簽名驗(yàn)證完后，再連同一個(gè)表示已通過(guò)驗(yàn)證的指令一起發(fā)給Y.具有仲裁方式的數(shù)字簽名例1：XA:M||AY:E：?jiǎn)舞€加密算法KXA,KAY:A與X和Y的共享密鑰M：消息T：時(shí)戳IDX：X的身份H(M)：M的雜湊值在1中，X以EKXA[IDX‖H(M)]作為自己對(duì)M的簽名，將M及簽名發(fā)往A。在2中A將從X收到的內(nèi)容和IDX、T一起加密后發(fā)往Y，其中的T用于向Y表示所發(fā)的消息不是舊消息的重放。Y對(duì)收到的內(nèi)容解密后,將解密結(jié)果存儲(chǔ)起來(lái)以備出現(xiàn)爭(zhēng)議時(shí)使用。如果出現(xiàn)爭(zhēng)議，Y可聲稱自己收到的M的確來(lái)自X，并將EKAY[IDX‖M‖EKXA[IDX‖H(M)]]發(fā)給A，由A仲裁，A由KAY解密后，再用KXA對(duì)EKXA[IDX‖H(M)]解密，并對(duì)H(M)加以驗(yàn)證，從而驗(yàn)證了X的簽名。具有仲裁方式的數(shù)字簽名例2XA:IDX||AY:X