消息認(rèn)證和數(shù)字簽名講義課件

消息認(rèn)證和數(shù)字簽名中山大學(xué)信息科學(xué)與技術(shù)學(xué)院王常吉

副教授2006年11月.消息認(rèn)證和數(shù)字簽名消息認(rèn)證（MessageAuthentication）驗證所收到的消息確實是來自真正的發(fā)送方，并且未被篡改的消息的過程Hash函數(shù)（HashFunction）散列函數(shù)是以變長的報文作為輸入，產(chǎn)生一個定長的散列值（也稱消息摘要）作為輸出.2|9/24/2020認(rèn)證信息與網(wǎng)絡(luò)安全系統(tǒng)一方面需要防范攻擊者對系統(tǒng)進(jìn)行被動攻擊（采用加密機制來保護消息的機密性，使其不被破譯），另一方面需要防范攻擊者對系統(tǒng)進(jìn)行主動攻擊（如偽造，篡改信息等）。認(rèn)證（authentication）是防止主動攻擊的重要技術(shù)，它對于開放網(wǎng)絡(luò)中的各種信息系統(tǒng)的安全性有重要作用，認(rèn)證的目的：驗證信息的發(fā)送者是真正的，而不是冒充的，此為信源識別；驗證信息的完整性，在傳送或存儲過程中未被篡改，重放或延遲等.3|9/24/2020消息認(rèn)證模型保密和認(rèn)證是信息系統(tǒng)安全的兩個方面，認(rèn)證不能自動提供保密性，而保密性也不能自然提供認(rèn)證功能。一個純認(rèn)證系統(tǒng)的模型如下圖所示：竄擾者認(rèn)證編碼器認(rèn)證譯碼器信道安全信道密鑰源信宿信源.4|9/24/2020消息認(rèn)證模型在這個系統(tǒng)中的發(fā)送者通過一個公開的無擾信道將消息發(fā)送給接收者，接收者不僅想收到消息本身，而且還要驗證消息是否來自合法的發(fā)送者及消息是否經(jīng)過篡改。系統(tǒng)中的密碼分析者不僅要截收和破譯信道中傳送的密報，而且可偽造密文送給接收者進(jìn)行欺詐，將其稱為系統(tǒng)的竄擾者（tamper）更加合適。實際認(rèn)證系統(tǒng)可能還要防止收方、發(fā)方之間的相互欺詐上述標(biāo)出的認(rèn)證編碼器和認(rèn)證譯碼器可抽象為認(rèn)證函數(shù)一個安全的認(rèn)證系統(tǒng)，首先要選好恰當(dāng)?shù)恼J(rèn)證函數(shù)，然后在此基礎(chǔ)上，給出合理的認(rèn)證協(xié)議（AuthenticationProtocol）.5|9/24/2020消息認(rèn)證模型消息認(rèn)證和數(shù)字簽名方法在功能上分為兩層：下層中有產(chǎn)生認(rèn)證符（一個用來認(rèn)證消息的值）的函數(shù)，上層協(xié)議中將該函數(shù)作原語使接收方可以驗證消息的真實性可用來產(chǎn)生認(rèn)證符的函數(shù)可分為三類：消息加密：整個消息的密文作為認(rèn)證符消息認(rèn)證碼MAC：它是消息和密鑰的公開函數(shù)，產(chǎn)生一個固定長度的值作為認(rèn)證符，MAC

=F（K，M）Hash函數(shù)：將任意長的消息映射為定長的Hash值的公開函數(shù)，以Hash值作為認(rèn)證符.6|9/24/2020消息認(rèn)證模型一個安全的消息認(rèn)證系統(tǒng)，需滿足意定的接收者能夠檢驗和證實消息的合法性、真實性和完整性消息的發(fā)送者和接收者不能抵賴除了合法的消息發(fā)送者，其它人不能偽造合法的消息.7|9/24/2020消息加密（對稱）消息加密本身提供了一種認(rèn)證手段（消息的自身加密可以作為一個認(rèn)證的度量）對稱加密方式A與B共享密鑰KA→B：EK[M]=CB：M=DK[C]，查看M是否為有意義的明文（如何區(qū)分真實的明文和隨機的位串，解決的辦法是強制明文具有某種結(jié)構(gòu)）信源MEEk(M)DMKK信宿.8|9/24/2020消息加密（對稱）提供保密：僅A與B共享密鑰K提供一定程度的認(rèn)證僅來自A傳輸中沒有被更改要求明文具有某種易于識別，但不能復(fù)制且無需加密的的結(jié)構(gòu)不提供簽名接收人可以偽造報文發(fā)送人可以偽造報文.9|9/24/2020消息加密（非對稱）KUb(B方的公鑰)MEEKUb(M)DMKRb公鑰加密：機密性MEEKRa(M)DMKRaKUa公鑰加密：認(rèn)證和簽名.10|9/24/2020消息加密（非對稱）MEEkRa(M)EEKUb(EkRa(M))KRaKUbDEkRa(M)DMKRbKUa公鑰加密：機密性，可認(rèn)證和簽名.11|9/24/2020消息認(rèn)證碼MAC，也稱密碼校驗和，是利用密鑰來生成一個固定長度的短數(shù)據(jù)塊，并將該數(shù)據(jù)塊附加在消息之后假定通信雙方A與B共享密鑰K，A向B發(fā)送消息時，計算MAC=CK(M)，然后消息和MAC一起被發(fā)送給B，B對收到的消息用相同的密鑰K進(jìn)行相同的計算，得出新的MAC，并將接收到的MAC與B計算出的MAC進(jìn)行對比，如果相等，則B可以相信消息未被篡改B可以相信消息來自真正的發(fā)送方A如果消息中含序列號，B可以相信消息的順序正確.12|9/24/2020消息認(rèn)證碼MAC函數(shù)類似于加密函數(shù)，但不需要可逆性，因此在數(shù)學(xué)上比加密算法被攻擊的弱點要少MAC的基本用途.13|9/24/2020消息認(rèn)證碼.14|9/24/2020消息認(rèn)證碼為什么使用消息認(rèn)證碼保密性與真實性是兩個不同的概念，從根本上講，信息加密提供的是保密性而非真實性加密代價大（公鑰算法代價更大）認(rèn)證函數(shù)與保密函數(shù)的分離能提供功能上的靈活性認(rèn)證碼可延長報文的保護期限，同時能處理報文內(nèi)容(使用加密，當(dāng)報文解密后，保護就失效了)某些信息只需要真實性，不需要保密性廣播的信息難以使用加密（信息量大）網(wǎng)絡(luò)管理信息等只需要真實性政府/權(quán)威部門的公告.15|9/24/2020消息認(rèn)證碼對MAC的安全要求如果一個攻擊者得到M和CK(M)，則攻擊者構(gòu)造一個消息M-，使得CK(M-)=CK(M)應(yīng)在計算上不可行CK(M)應(yīng)均勻分布，即隨機選擇消息M和M-

，CK(M)=CK(M-)的概率是2-n，其中n是MAC的位數(shù)MAC值應(yīng)平等地依賴于消息中的所有位，令M-

為M的某些變換，即M-=f(M)，例如f可以涉及M中一個或多個給定位的反轉(zhuǎn)），在這種情況下，Pr[CK(M-)=CK(M)]=2-n.16|9/24/2020消息認(rèn)證碼DataAuthenticationAlgorithmFIPSpublication(FIPSPUB113)ANSIstandard(X9.17)有兩種使用廣泛的基于DES的MAC，一種按CFB模式，一種按CBC模式運行。在CBC模式下，消息按64bit分組，不足時以0補齊，初始向量為0，送入DES系統(tǒng)加密，但不輸出密文，只取加密結(jié)果最左邊的r位作為認(rèn)證符，r取大小可由通信雙方約定。美國聯(lián)邦電信建議采用24bit[FTSC-1026]，而美國金融系統(tǒng)采用32bit[ABA，1986].17|9/24/2020哈希函數(shù)H（M）:輸入為任意長度的消息M，輸出為一個固定長度的散列值，稱為消息摘要（MessageDigest），該散列值是消息M的所有位的函數(shù)并提供錯誤檢測能力（消息中的任何一位或多位的變化都將導(dǎo)致該散列值的變化）又稱為哈希函數(shù)、散列函數(shù)、數(shù)字指紋（Digitalfingerprint）、壓縮（Compression）函數(shù)、緊縮（Contraction）函數(shù)、數(shù)據(jù)認(rèn)證碼DAC（Dataauthenticationcode）、篡改檢驗碼MDC（Manipulationdetectioncode）.18|9/24/2020哈希函數(shù)H可應(yīng)用于任意大小的數(shù)據(jù)塊H產(chǎn)生定長的輸出對于任意給定的x，容易計算出H（x）H是單向（one-way）函數(shù)給定h，找到滿足h=H（x）的x在計算上是不可行的complexityoffindingxoutofhis2n，wherenisthenumberofbitsinthehashoutput抗弱碰撞性（Weakcollisionresistance）對于任意給定的x，找到滿足x≠y且H（x）=H（y）的y在計算上是不可行的complexityofattackis2n.19|9/24/2020哈希函數(shù)強抗碰撞性（Strongcollisionresistance）找到任何滿足H（x）=H（y）的偶對（x，y）在計算上是不可行的complexityis2n/2前三條是Hash函數(shù)實際應(yīng)用于消息認(rèn)證中所必須滿足的，第四條單向性是指，由消息很容易計算出Hash碼，但由Hash碼卻不能計算出相應(yīng)的消息，第五條性質(zhì)是保證不能找到與給定消息具有相同Hash值的另一消息，可以在使用時對Hash值加密的方法中防止偽造，第六條性質(zhì)涉及Hash函數(shù)抗生日攻擊的能力強弱.20|9/24/2020哈希函數(shù)分類根據(jù)安全水平弱無碰撞強無碰撞注：強無碰撞自然含弱無碰撞！根據(jù)是否使用密鑰帶秘密密鑰的Hash函數(shù)：消息的散列值由只有通信雙方知道的秘密密鑰K來控制，此時散列值稱作MAC不帶秘密密鑰的Hash函數(shù)：消息的散列值的產(chǎn)生無需使用密鑰，此時散列值稱作MDC.21|9/24/2020哈希函數(shù)-生日攻擊如果采用傳輸加密的散列值和不加密的報文M，攻擊者需要找到M-，使得H(M-)=H(M)，以便使用替代報文來欺騙接收者一種基于生日悖論的攻擊可能做到這一點，生日問題一個教室中，最少應(yīng)有多少個學(xué)生，才使至少有兩人具有相同生日的概率不小于1/2？概率結(jié)果與人的直覺是相違背的實際上只需23人，即任找23人，從中總能選出兩人具有相同生日的概率至少為1/2.22|9/24/2020生日攻擊實例A準(zhǔn)備兩份合同M和M-，一份B會同意，一份會取走他的財產(chǎn)而被拒絕A對M和M-

各做32處微小變化（保持原意），分別產(chǎn)生232個64位hash值根據(jù)前面的結(jié)論，超過0.5的概率能找到一個M和一個M-

，它們的hash值相同A提交M，經(jīng)B審閱后產(chǎn)生64位hash值并對該值簽名，返回給AA用M-

替換MHash必須足夠長（128，160，224，256，…）.23|9/24/2020Hash函數(shù)和MAC的安全性窮舉攻擊對MAC的窮舉攻擊由于需要知道消息-MAC對，窮舉攻擊更加困難密碼分析理想的Hash函數(shù)和MAC算法要求密碼分析供給所需的代價大于或等于窮舉攻擊所需的代價單向性2n抗弱碰撞性2n抗強碰撞性2n/2.24|9/24/2020哈希函數(shù)的構(gòu)造Merkle于1989年提出通用的迭代結(jié)構(gòu)構(gòu)造Hash函數(shù)，幾乎被所有hash函數(shù)使用RonRivest于1990年提出MD4具體做法:把原始消息M分成一些固定長度的塊Yi最后一塊padding并使其包含消息M長度設(shè)定初始值CV0壓縮函數(shù)f，CVi=f(CVi-1,Yi-1)最后一個CVi為hash值.25|9/24/2020哈希函數(shù)的通用結(jié)構(gòu).26|9/24/2020常用的Hash算法幾種重要的Hash函數(shù)MD5SHA-1RIPEMD-160消息認(rèn)證碼HMAC.27|9/24/2020MD5Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年，RonRivest提出MD5（RFC1321）在最近數(shù)年之前，MD5是最主要的hash算法現(xiàn)行美國標(biāo)準(zhǔn)SHA-1以MD5的前身MD4為基礎(chǔ)輸入：任意長度消息輸出：128bit消息摘要處理：以512bit輸入數(shù)據(jù)塊為單位.28|9/24/2020SHA1992年NIST制定了SHA（128位）1993年SHA成為標(biāo)準(zhǔn)（FIPSPUB180）1994年修改產(chǎn)生SHA-1（160位）1995年SHA-1成為新的標(biāo)準(zhǔn)，作為SHA-1（FIPSPUB180-1/RFC3174），為兼容AES的安全性，NIST發(fā)布FIPSPUB180-2，標(biāo)準(zhǔn)化SHA-256，SHA-384和SHA-512輸入：消息長度<264輸出：160bit消息摘要處理：以512bit輸入數(shù)據(jù)塊為單位基礎(chǔ)是MD4.29|9/24/2020哈希函數(shù)MD5SHA-1RIPEMD-160Digestlength128bits160bits160bitsBasicunitofprocessing512bits512bits512bitsNumberofsteps64(4roundsof16)80(4roundsof20)160(5pairedroundsof16)Maximummessagesize∞264-1bits∞.30|9/24/2020參考網(wǎng)址山東大學(xué)信息安全實驗室/hash.htmNISTSecureHashPages/cryptval/shs.htm/CryptoToolkit/tkhash.html.31|9/24/2020消息認(rèn)證的局限性消息認(rèn)證可以保護信息交換雙方不受第三方的攻擊，但是它不能處理通信雙方的相互攻擊信宿方可以偽造消息并稱消息發(fā)自信源方，信源方產(chǎn)生一條消息，并用和信源方共享的密鑰產(chǎn)生認(rèn)證碼，并將認(rèn)證碼附于消息之后信源方可以否認(rèn)曾發(fā)送過某消息，因為信宿方可以偽造消息，所以無法證明信源方確實發(fā)送過該消息在收發(fā)雙方不能完全信任的情況下，引入數(shù)字簽名來解決上述問題數(shù)字簽名的作用相當(dāng)于手寫簽名.32|9/24/2020數(shù)字簽名在公鑰體制中，用接受者的公鑰加密消息得到密文，接受者用自己的私鑰解密密文得到消息。加密過程任何人都能完成，解密過程只有接受者能夠完成。考慮一種相反的過程，發(fā)送者用自己的私鑰“加密”消息得到“密文”，然后利用發(fā)送者的公鑰“解密”密文得到消息。很顯然，加密只有發(fā)送者能夠完成，而解密任何人都可以完成。所以，任何人都可相信是特定的發(fā)送者產(chǎn)生了該消息，這就相當(dāng)于“簽名”，證明一個消息的所屬.33|9/24/2020數(shù)字簽名隨著計算機通信網(wǎng)的發(fā)展，人們希望通過電子設(shè)備實現(xiàn)快速、遠(yuǎn)距離的交易，數(shù)字(或電子)簽名法應(yīng)運而生，并開始用于商業(yè)通信系統(tǒng)，如電子郵遞、電子轉(zhuǎn)賬和辦公自動化等系統(tǒng)。隨著計算機網(wǎng)絡(luò)的發(fā)展，過去依賴于手書簽名的各種業(yè)務(wù)都可用這種電子數(shù)字簽名代替，它是實現(xiàn)電子貿(mào)易、電子支票、電子貨幣、電子購物、電子出版及知識產(chǎn)權(quán)保護等系統(tǒng)安全的重要保證.34|9/24/2020數(shù)字簽名傳統(tǒng)簽名的基本特點與被簽的文件在物理上不可分割簽名者不能否認(rèn)自己的簽名簽名不能被偽造容易被驗證數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化能與所簽文件“綁定”簽名者不能否認(rèn)自己的簽名容易被自動驗證簽名不能被偽造.35|9/24/2020數(shù)字簽名數(shù)字簽名必須具有下述特征收方能夠確認(rèn)或證實發(fā)方的簽名，但不能偽造，簡記為R1-條件（unforgeable）發(fā)方發(fā)出簽名的消息給收方后，就不能再否認(rèn)他所簽發(fā)的消息，簡記為S-條件(non-repudiation)收方對已收到的簽名消息不能否認(rèn)，即有收報認(rèn)證，簡記作R2-條件第三者可以確認(rèn)收發(fā)雙方之間的消息傳送，但不能偽造這一過程，簡記作T-條件.36|9/24/2020數(shù)字簽名與手書簽名的區(qū)別：手書簽名是模擬的，且因人而異。數(shù)字簽名是0和1的數(shù)字串，因消息而異與消息認(rèn)證的的區(qū)別：消息認(rèn)證使收方能驗證消息發(fā)送者及所發(fā)消息內(nèi)容是否被竄改過。當(dāng)收發(fā)者之間沒有利害沖突時，這對于防止第三者的破壞來說是足夠了。但當(dāng)收者和發(fā)者之間有利害沖突時，就無法解決他們之間的糾紛，此時須借助滿足前述要求的數(shù)字簽名技術(shù)與消息加密區(qū)別：消息加密和解密可能是一次性的，它要求在解密之前是安全的；而一個簽名的消息可能作為一個法律上的文件，如合同等，很可能在對消息簽署多年之后才驗證其簽名，且可能需要多次驗證此簽名。因此，簽名的安全性和防偽造的要求更高些，且要求證實速度比簽名速度還要快，特別是聯(lián)機在線實時驗證.37|9/24/2020數(shù)字簽名根據(jù)簽名的內(nèi)容分對整體消息的簽名對壓縮消息的簽名按明、密文的對應(yīng)關(guān)系劃分確定性(Deterministic)數(shù)字簽名，其明文與密文一一對應(yīng)，它對一特定消息的簽名不變化，如RSA、Rabin等簽名；隨機化的(Randomized)或概率式數(shù)字簽名.38|9/24/2020數(shù)字簽名算法普通數(shù)字簽名算法RSAElGamal/DSS/DSAECDSA盲簽名算法群簽名算法.39|9/24/2020RSA簽名方案密鑰的生成（同加密系統(tǒng)）公鑰Pk={e,n}；私鑰Sk={d,n}簽名過程(用私鑰d,n)明文：M<n密文：S=Mdmodn驗證過程(用公鑰e,n)給定M，S，Ver(M,S)為真，當(dāng)且僅當(dāng)M=Semodn安全性由于只有簽名者知道d，其他人不能偽造簽名，但可易于證實所給任意（M，S）對是否是消息M和相應(yīng)簽名構(gòu)成的合法對.40|9/24/2020數(shù)字簽名標(biāo)準(zhǔn)美國國家標(biāo)準(zhǔn)與技術(shù)研究所NIST發(fā)布的聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS186，稱為數(shù)字簽名標(biāo)準(zhǔn)DSS(DigitalSignatureStandard)于1991年最初提出，1994年12月1日采納為標(biāo)準(zhǔn)DSS，2000年發(fā)布DSS的擴充版，即FIPS186-2DSS為EIGamal和Schnorr簽名方案的改進(jìn)，其使用的算法記為DSA（DigitalSignatureAlgorithm)。此算法由D.W.Kravitz設(shè)計。DSS使用了SHA，安全性是基于求離散對數(shù)的困難性只能用于數(shù)字簽名，不能用于加密或密鑰分配安全性基于基于離散對數(shù)難題DSS是一個產(chǎn)生簽名比驗證簽名快得多的方案，驗證簽名太慢！.41|9/24/2020DSA算法描述全局公鑰（p，q，g）p為512～1024bit的大素數(shù)，q是（q－1）的素因子，為160比特的素數(shù)g=h(p-1)/qmodp，且1<h<(p-1)，使得h(p-1)/qmodp>1用戶私鑰x：x為0<x<q內(nèi)的隨機數(shù)用戶公鑰y：y=gxmodp.42|9/24/2020DSA算法描述用戶每個消息用的秘密隨機數(shù)k：0<k<q簽名過程：對報文M，簽名為（r，s）r=(gkmodp)modqs=(k-1(H(M)+xr))modq驗證：w＝s-1modqa=(H(M)w)modqb=rwmodqv=((gayb)modp)modqVer（M，r，s）＝真iffv=r.43|9/24/2020數(shù)字簽名標(biāo)準(zhǔn)針對DSS的主要批評意見有：DSA不能用于加密或密鑰分配DSA由NSA開發(fā)的，算法中可能設(shè)有陷門

DSA比RSA慢

RSA已是一個實際上標(biāo)準(zhǔn)，DSS與現(xiàn)行國際標(biāo)準(zhǔn)不相容

DSA未經(jīng)公開選擇過程，還沒有足夠的時間進(jìn)行分析證明DSA可能侵犯了其它專利（Schnorr簽名算法，Diffie-Hellman算法由512bit所限定密鑰量太小，現(xiàn)已改