北京大學(xué)網(wǎng)絡(luò)信息安全課件-身份認(rèn)證

單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,*,,,,,,,網(wǎng)絡(luò)與信息平安第五講,,密碼學(xué)根底(四),,,王 昭,,北京大學(xué)信息科學(xué)技術(shù)學(xué)院,,軟件研究所--信息平安研究室wangzhao@infosec.pku.edu,2003年春季北京大學(xué)碩士研究生課程,,回憶與總結(jié),,對(duì)稱密碼算法,,運(yùn)算速度快、密鑰短、多種用途〔隨機(jī)數(shù)產(chǎn)生、Hash函數(shù)〕、歷史悠久,,密鑰管理困難〔分發(fā)、更換〕,,非對(duì)稱密碼算法,,只需保管私鑰、可以相當(dāng)長(zhǎng)的時(shí)間保持不變、需要的數(shù)目較小,,運(yùn)算速度慢、密鑰尺寸大、歷史短,,,信息平安的需求,,保密性〔 Confidentiality〕,,完整性 〔Integrity〕,,數(shù)據(jù)完整性，未被未授權(quán)篡改或者損壞,,系統(tǒng)完整性，系統(tǒng)未被非授權(quán)操縱，按既定的功能運(yùn)行,,可用性 〔Availability〕,,鑒別 〔Authenticity〕,,實(shí)體身份的鑒別，適用于用戶、進(jìn)程、系統(tǒng)、信息等,,不可否認(rèn)性 〔 Non-repudiation〕,,防止源點(diǎn)或終點(diǎn)的抵賴,,??,,討論議題,,消息鑒別〔Message Authentication),,,,散列函數(shù)〔 Hash Functions),,,,數(shù)字簽名〔Digital Signature〕,,,,定義,,消息鑒別〔Message Authentication)：,,是一個(gè)證實(shí)收到的消息來(lái)自可信的源點(diǎn)且未被篡改的過(guò)程。,,散列函數(shù)〔 Hash Functions)：,,一個(gè)散列函數(shù)以一個(gè)變長(zhǎng)的報(bào)文作為輸入，并產(chǎn)生一個(gè)定長(zhǎng)的散列碼，有時(shí)也稱報(bào)文摘要，作為輸出。,,數(shù)字簽名〔Digital Signature〕,,是一種防止源點(diǎn)或終點(diǎn)抵賴的鑒別技術(shù)。,,,,,通信系統(tǒng)典型攻擊,,1),竊聽(tīng),,2)業(yè)務(wù)流分析,,3)消息篡改,,內(nèi)容修改：消息內(nèi)容被插入、刪除、修改。,,順序修改：插入、刪除或重組消息序列。,,時(shí)間修改：消息延遲或重放。,,4)冒充：從一個(gè)假冒信息源向網(wǎng)絡(luò)中插入消息,,5)抵賴：接受者否認(rèn)收到消息；發(fā)送者否認(rèn)發(fā)送過(guò)消息。,,,兩個(gè)概念,,鑒別(Authentication):,,真?zhèn)涡?,認(rèn)證(Certification),,資格審查,,,,,消息鑒別,鑒別的目的,,鑒別模型,,鑒別函數(shù),,,鑒別的目的,,鑒別的主要,目的,有二：,,第一，驗(yàn)證信息的發(fā)送者是真正的，而不是冒充的，此為信源識(shí)別；,,第二，驗(yàn)證信息的完整性，在傳送或存儲(chǔ)過(guò)程中未被篡改，重放或延遲等。,,,鑒別模型,,一個(gè)單純,鑒別系統(tǒng),的模型,竄擾者,,信宿,,,信源,,鑒別編碼器,鑒別譯碼器,信道,平安信道,密鑰源,,鑒別系統(tǒng)的組成,,鑒別編碼器和鑒別譯碼器可抽象為鑒別函數(shù)。,,一個(gè)平安的鑒別系統(tǒng)，需滿足,,〔1〕意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性、真實(shí)性和完整性,,〔2〕消息的發(fā)送者和接收者不能抵賴,,〔3〕除了合法的消息發(fā)送者，其它人不能偽造合法的消息,,,首先要選好恰當(dāng)?shù)蔫b別函數(shù)，該函數(shù)產(chǎn)生一個(gè)鑒別標(biāo)識(shí)，然后在此根底上，給出合理的鑒別協(xié)議(Authentication Protocol)，使接收者完成消息的鑒別。,,鑒別函數(shù),,可用來(lái)做鑒別的函數(shù)分為三類：,,(1),消息加密函數(shù),(Message encryption),,,用完整信息的密文作為對(duì)信息的鑒別。,,(2),消息鑒別碼MAC,(Message Authentication Code),,公開(kāi)函數(shù)+密鑰產(chǎn)生一個(gè)固定長(zhǎng)度的值作為鑒別標(biāo)識(shí),,(3),散列函數(shù),(Hash Function),,是一個(gè)公開(kāi)的函數(shù)，它將任意長(zhǎng)的信息映射成一個(gè)固定長(zhǎng)度的信息。,,,消息加密,,消息的自身加密可以作為一個(gè)鑒別的度量。,,對(duì)稱密鑰模式和公開(kāi)密鑰模式有所不同。,,,(a) 對(duì)稱加密：保密性與鑒別,,提供保密,,提供鑒別,,僅來(lái)自,A,,傳輸中沒(méi)有被更改,,需要某種結(jié)構(gòu)或冗余,,不提供簽名,,,,如何自動(dòng)確定是否收到的明文可解密為可懂的明文?,,,一種解決方法是強(qiáng)制明文有某種結(jié)構(gòu).,,,過(guò)失控制：Error Control,,(b) 公鑰加密：保密性,,提供保密,,不提供鑒別,,(c) 公鑰加密：鑒別與簽名,,提供鑒別和簽名,,僅,A,有,Kra,可以進(jìn)行加密,,傳輸中沒(méi)有被更改,,需要某種結(jié)構(gòu)或冗余,,任何一方均可以使用,Kua,驗(yàn)證簽名,,(d)公鑰加密：保密、鑒別與簽名,,KUb,提供保密性,,Kra,提供鑒別和簽名,,消息,鑒別,碼MAC,使用一個(gè)密鑰生成一個(gè)固定大小的小數(shù)據(jù)塊，并參加到消息中，稱MAC， 或密碼校驗(yàn)和〔cryptographic checksum〕,1、接收者可以確信消息M未被改變。,2、接收者可以確信消息來(lái)自所聲稱的發(fā)送者；,3、如果消息中包含順序碼〔如HDLC,X.25,TCP〕，那么接收者可以保證消息的正常順序；,MAC函數(shù)類似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比加密算法被攻擊的弱點(diǎn)要少。,,MAC的根本用法(a),,消息鑒別,Provides authentication ---- only A and B share K,,MAC的根本用法(b),,消息鑒別與保密，鑒別與明文連接,Provides authentication -- only A and B share K1,,Provides confidentiality -- only A and B share K2,,MAC的根本用法(c),,消息鑒別與保密，鑒別與密文連接,,Provides authentication -- Using K1,,Provides confidentiality -- Using K2,,通過(guò)加密得到信息真實(shí)性: 問(wèn)題,保密性與真實(shí)性是兩個(gè)不同的概念,,根本上,信息加密提供的是保密性而非真實(shí)性,,加密代價(jià)大(公鑰算法代價(jià)更大),,鑒別函數(shù)與保密函數(shù)的別離能提供功能上的靈活性,,某些信息只需要真實(shí)性,不需要保密性,,播送的信息難以使用加密(信息量大),,網(wǎng)絡(luò)管理信息等只需要真實(shí)性,,政府/權(quán)威部門的公告,,散列函數(shù),Hash Function,,H(M): 輸入為任意長(zhǎng)度的消息M; 輸出為一個(gè)固定長(zhǎng)度的散列值，稱為消息摘要Message Digest〕。,,這個(gè)散列值是消息M的所有位的函數(shù)并提供錯(cuò)誤檢測(cè)能力：消息中的任何一位或多位的變化都將導(dǎo)致該散列值的變化。,,又稱為：哈希函數(shù)、數(shù)字指紋〔Digital finger print)、壓縮〔Compression)函數(shù)、緊縮〔Contraction 〕函數(shù)、數(shù)據(jù)鑒別碼DAC〔Data authentication code〕、篡改檢驗(yàn)碼MDC(Manipulation detection code),,散列函數(shù)的根本用法〔a、b),,Provides confidentiality -- only A and B share K,,Provides authentication -- H(M) is cryptographically protected,Provides authentication -- H(M) is cryptographically protected,,散列函數(shù)的根本用法〔c),,Provides authentication and digital signature,,-- H(M) is cryptographically protected,,-- only A could create E,KRa,[H(M)],,散列函數(shù)的根本用法(d),,,(d) A,?,B: E,K,[M||E,KRa,[H(M)]],Provides authentication and digital signature,,Provides confidentiality,,散列函數(shù)的根本用法(e、f),,Provides authentication -- only A and B share S,Provides authentication -- only A and B share S,,Provides confidentiality -- only A and B share K,,方法e的優(yōu)點(diǎn),,加密軟件很慢,,加密硬件的開(kāi)銷很大,,加密是對(duì)大長(zhǎng)度數(shù)據(jù)進(jìn)行優(yōu)化的,,加密算法可能受專利保護(hù),,加密算法可能受出口的限制.,,,MAC函數(shù)的特性與實(shí)現(xiàn),,MAC函數(shù)為多對(duì)一映射,,包含所有可能的MAC和所有可能的密鑰,,n-bit MAC： 有2,n,個(gè)可能的MAC；,,k-bit 密鑰： 有2,k,個(gè)可能的密鑰；,,N個(gè)可能的消息：有 N>>2,n,,,攻擊者如何用強(qiáng)力攻擊方法攻擊MAC？,,假設(shè)：用戶A和B通信時(shí)沒(méi)有增加保密性實(shí)現(xiàn)，攻擊者可以看到明文， k > n (k為密鑰長(zhǎng)度位數(shù)，n為MAC長(zhǎng)度位數(shù),),,給定：M,1,和MAC,1,， MAC,1,= C,K1,(M,1,),,密碼分析員可以計(jì)算MAC,i,= C,Ki,(M,1,) 對(duì)所有可能的Ki，至少有一個(gè)Ki保證產(chǎn)生 MAC,i,= MAC,1,注意：總共會(huì)產(chǎn)生2k個(gè)MAC結(jié)果，但只有2n< 2k個(gè)不同的MAC值，因此，有假設(shè)干個(gè)key將產(chǎn)生相同的MAC，而攻擊者無(wú)法確定哪一個(gè)是正確的key。,平均來(lái)說(shuō)， 2k/2n= 2(k-n)個(gè)key將產(chǎn)生匹配的MAC，所以，攻擊者需要循環(huán)屢次攻擊，以確定K:,,第一輪：給定 M1和MAC1= CK(M1)，對(duì)所有2k個(gè)key，計(jì)算,,MACi = CKi(M1) ，匹配的數(shù)量? 2(k-n),,第二輪：給定 M2和MAC2= CK(M2)，對(duì)所有2(k-n)個(gè)key，計(jì)算,,MACi = CKi(M2) ，匹配的數(shù)量? 2(k-2?n),,平均來(lái)說(shuō)，如果k=a?n，那么需要a輪。,例：k=80, MAC 32-bit,那么：,,第一輪：248可能的key；,,第二輪：216個(gè)；,,第三輪：1 個(gè)；,由此可見(jiàn)，強(qiáng)力攻擊企圖發(fā)現(xiàn)authentication key不小于甚至大于對(duì)同樣長(zhǎng)度的解密key的攻擊。,如果 k≤n，那么第一輪就可以產(chǎn)生一個(gè)唯一對(duì)應(yīng)。仍然可以有多于一個(gè)key產(chǎn)生這一配對(duì)，這時(shí)攻擊者只需對(duì)一個(gè)新的(message, MAC)進(jìn)行相同的測(cè)試。,,考慮以下的MAC算法,M = (X,1,|| X,2,|| … || Xm) 是一個(gè)由64位Xi數(shù)據(jù)塊連接而成，,,定義,,,?(M) = X,1,?X,2,?...?Xm,,C,K,(M) = E,K,[?(M)],,其中,,? 為異或操作；E為 ECB工作模式的DES算法。,,,Key length = 56 bit,,MAC length = 64 bit,,強(qiáng)力攻擊需要至少2,56,次加密來(lái)決定K。,但攻擊者可以不用找到 K就可以實(shí)施攻擊。,,設(shè) M,?,= ( Y,1,|| Y,2,|| … || Ym-,1,|| Ym),,其中 Y,1,, Y,2,, …, Ym-,1,是替換 X,1,, X,2,,…,Xm-,1,的任意值，而,,Ym = Y,1,?,Y,2,?,, …,,?,Ym-,1,?,,?(M),,這時(shí),,消息M’ 和 MAC= C,K,(M) = E,K,[?(M)],是一對(duì)可被接收者認(rèn)證,,的消息。,C,K,(M ?) = E,K,[?(M ?)],,= E,K,[,Y,1,?,Y,2,?,, …,,?,Ym-,1,?,,Ym ],,= E,K,[,Y,1,?,Y,2,?,, …,,?,Ym-,1,?,(Y,1,?,Y,2,?,, …,,?,Ym-,1,?,,?(M)) ],,= E,K,[?(M)],用此方法，任何長(zhǎng)度為64,?(m-1),位的消息可以作為欺騙性,,信息被插入！,,為了防止以上可能的攻擊，MAC函數(shù)應(yīng)具有以下性質(zhì)：,如果一個(gè)攻擊者得到M和CK(M)，那么攻擊者構(gòu)造一個(gè)消息M ?使得CK(M ?)=CK(M)應(yīng)在計(jì)算上不可行。,,CK(M)應(yīng)均勻分布，即：隨機(jī)選擇消息M和M ? ， CK(M)= CK(M ?)的概率是2-n，其中n是MAC的位數(shù)。,,令M ?為M的某些變換，即：M ? =f(M)，〔例如：f可以涉及M中一個(gè)或多個(gè)給定位的反轉(zhuǎn)〕，在這種情況下，Pr[CK(M)= CK(M ?)] = 2-n。,,基于DES的MAC,,Data Authentication Algorithm,,FIPS publication (FIPS PUB 113),,ANSI standard (X9.17),,,使用CBC(Cipher Block Chaining)方式，初始向量為0。,,,最廣泛的用法,,將數(shù)據(jù)按64位分組，D,1,, D,2,, … , D,N,，必要時(shí)最后一個(gè)數(shù)據(jù)塊用0向右填充。運(yùn)用DES算法E，密鑰K,,,數(shù)據(jù)鑒別碼(DAC)的計(jì)算如下：,,O,1,= E,K,(D,1,),,O,2,= E,K,(D,2,?,O,1,),,O,3,= E,K,(D,3,?,O,2,),,…,,O,N,= E,K,(D,N,?,O,N-1,),,,M的大小可由通信雙方約定。美國(guó)聯(lián)邦電信建議采用,,24bit[見(jiàn)FTSC-1026],而美國(guó)金融系統(tǒng)采用32bit [ABA,1986],,,,D,1,,(64bits),Time = 1,DES,,encrypt,K,,(56bits),O,1,,(64bits),D,2,,(64bits),Time = 2,DES,,encrypt,K,O,2,,(64bits),+,D,N,,(64bits),Time = N,DES,,encrypt,K,O,N,,+,DAC M-bits,,(16 to 64 bits),,},...,(16<=M<=64),,工作于CFB模式下DES,,,64bit存放器,DES,選左邊k位,選左邊M位,+,y,i,x,i,k,,問(wèn)題,,假設(shè)對(duì)相當(dāng)長(zhǎng)的文件通過(guò)簽名認(rèn)證怎么辦？如一個(gè)合法文件有數(shù)兆字節(jié)長(zhǎng)。自然按64比特分劃成一塊一塊，用相同的密鑰獨(dú)立地簽每一個(gè)塊。然而，這樣太慢。,,解決方法,,解決方法：引入可公開(kāi)的密碼散列函數(shù)(Hash function)。它將取任意長(zhǎng)度的消息做自變量，結(jié)果產(chǎn)生規(guī)定長(zhǎng)度的消息摘要。[如，使用數(shù)字簽名標(biāo)準(zhǔn)DSS，消息摘要為160比特]，然后簽名消息摘要。對(duì)數(shù)字簽名來(lái)說(shuō)，散列函數(shù)h是這樣使用的：,,消息： x 任意長(zhǎng),,消息摘要： Z=h(x) 160bits,,簽名： y=sigk(Z) 320 bits (簽名一個(gè)消息摘要),,,驗(yàn)證簽名:(x,y),其中y= sigk(h(x))，使用公開(kāi)的散列函數(shù)h，重構(gòu)作Z ? =h(x)。然后Verk(y)=Z,來(lái)看Z?=Z',,新的問(wèn)題,,用以鑒別的散列函數(shù)，能否減弱認(rèn)證方案的平安性？這個(gè)問(wèn)題是要分析的。簽名的對(duì)象由完整消息變成消息摘要，這就有可能出現(xiàn)偽造。,,平安威脅一,,(a)偽造方式一：Oscar以一個(gè)有效簽名(x,y)開(kāi)始，此處y= sigk(h(x))。首先他計(jì)算Z=h(x)，并企圖找到一個(gè)x'滿足h(x')=h(x)。假設(shè)他做到這一點(diǎn)，那么(x',y)也將為有效簽名。為防止這一點(diǎn)，要求函數(shù)h具有無(wú)碰撞特性。,,定義1(弱無(wú)碰撞)，散列函數(shù)h稱為是弱無(wú)碰撞的，是指對(duì)給定消息x ∈ X，在計(jì)算上幾乎找不到異與x的x' ∈ X使h(x)=h(x')。,,平安威脅二,,(b)偽造方式二：Oscar首先找到兩個(gè)消息x=x',滿足h(x)=h(x'),然后Oscar把x 給Bob且使他對(duì)x的摘要h(x)簽名，從而得到y(tǒng),那么(x',y)是一個(gè)有效的偽造,。,,,定義2(強(qiáng)無(wú)碰撞),散列函數(shù)h被稱為是強(qiáng)無(wú)碰撞的,是指在計(jì)算上幾乎不可能找到相異的x，x'使得h(x)=h(x')。,,,注：強(qiáng)無(wú)碰撞自然含弱無(wú)碰撞！,,,平安威脅三,,(c)偽造方式三：在散列函數(shù)的用法(e)中, 秘密值S本身并不發(fā)送, 如果散列函數(shù)不是單向的,攻擊者截獲到M和H(M||S). 然后通過(guò)某種逆變換獲得M||S, 因而攻擊者就可以得到S.,,,定義3(單向的),稱散列函數(shù)h為單向的，是指計(jì)算h的逆函數(shù)h,-1,在計(jì)算上不可行。,,,HASH 函數(shù) h = H(M),,滿足：,,1、H可以作用于一個(gè)任意長(zhǎng)度的數(shù)據(jù)塊；,,2、H產(chǎn)生一個(gè)固定長(zhǎng)度的輸出；,,3、對(duì)任意給定的x ,H(x) 計(jì)算相對(duì)容易，無(wú)論是軟件還是硬件實(shí)現(xiàn)。,,4、對(duì)任意給定碼h，找到x滿足H(x)=h具有計(jì)算不可行性；〔單向性〕,,5、對(duì)任意給定的數(shù)據(jù)塊x，找到滿足H(y)=H(x)的y?x具有計(jì)算不可行,,性。,,6、找到任意數(shù)據(jù)對(duì)(x,y)，滿足H(x) = H(y)是計(jì)算不可行的。,前三條要求具有實(shí)用性，第4條是單向性質(zhì)，即給定消息可以產(chǎn)生一個(gè),,散列碼，而給定散列碼不可能產(chǎn)生對(duì)應(yīng)的消息。第5條性質(zhì)是保證一個(gè),,給定的消息的散列碼不能找到與之相同的另外的消息。即防止偽造。,,第6條是對(duì)的生日攻擊方法的防御能力。,目的：“fingerprint〞 of messgae,,Hash函數(shù)的分類,,根據(jù)平安水平：,,定義1(弱無(wú)碰撞)，散列函數(shù)h稱為是弱無(wú)碰撞的，是指對(duì)給定消息x ∈ X，在計(jì)算上幾乎找不到異于x的x' ∈ X使h(x)=h(x')。,,定義2(強(qiáng)無(wú)碰撞)，散列函數(shù)h被稱為是強(qiáng)無(wú)碰撞的,是指在計(jì)算上幾乎不可能找到相異的x，x'使得h(x)=h(x')。,,注：強(qiáng)無(wú)碰撞自然含弱無(wú)碰撞！,,Hash函數(shù)的分類,,根據(jù)是否使用密鑰,,帶秘密密鑰的Hash函數(shù):,消息的散列值由只有通信雙方知道的秘密密鑰K來(lái)控制。此時(shí)，散列值稱作MAC。,,不帶秘密密鑰的Hash函數(shù)：,消息的散列值的產(chǎn)生無(wú)需使用密鑰。此時(shí)，散列值稱作MDC。,,,Hash與MAC的區(qū)別,,MAC,需要對(duì)全部數(shù)據(jù)進(jìn)行加密,,MAC,速度慢,,Hash,是一種直接產(chǎn)生鑒別碼的方法,,,生日攻擊,,假定使用64位的散列碼,是否平安?,,如果采用傳輸加密的散列碼和不加密的報(bào)文M,對(duì)手需要找到M ?,使得H(M?)=H(M),以便使用替代報(bào)文來(lái)欺騙接收者.,,一種基于生日悖論的攻擊可能做到這一點(diǎn).,,,生日悖論,,生日問(wèn)題：一個(gè)教室中，最少應(yīng)有多少學(xué)生，才使至少有兩人具有相同生日的概率不小于1/2？,,概率結(jié)果與人的直覺(jué)是相違背的.,,實(shí)際上只需23人,即任找23人，從中總能選出兩人具有相同生日的概率至少為1/2。,,,,,,相關(guān)問(wèn)題,,給定一個(gè)散列函數(shù),有n個(gè)可能的輸出,輸出值為H(x),如果H有k個(gè)隨機(jī)輸入, k必須為多大才能使至少存在一個(gè)輸入y,使得H(y)=H(x)的概率大于0.5.,,對(duì)單個(gè)y, H(y)=H(x)的概率為1/n,反過(guò)來(lái)H(y)?H(x)的概率為1-(1/n).,,如果產(chǎn)生k個(gè)隨機(jī)值y,他們之間兩兩不等的概率等于每個(gè)個(gè)體不匹配概率的乘積,即[1-(1/n)]k,這樣,至少有一個(gè)匹配的概率為1-[1-(1/n)]k?1-[1-(k/n)]=k/n.要概率等于0.5,只需k=n/2.,,對(duì)長(zhǎng)度為m位的散列碼，共有2m個(gè)可能的散列碼，假設(shè)要使任意的x,y 有H(x)=H(y)的概率為0.5,只需,,k=2m/2,,,,,,Birthday Attacks: example,A,準(zhǔn)備兩份合同,M,和,M,?,，,一份,B,會(huì)同意，一份會(huì)取走他的財(cái)產(chǎn)而被拒絕,,A,對(duì),M,和,M,?,各做32處微小變化(保持原意),分別產(chǎn)生2,32,個(gè)64位,hash,值,,根據(jù)前面的結(jié)論,超過(guò)0.5的概率能找到一個(gè),M,和一個(gè),M,?,,它們的,hash,值相同,,A,提交,M,,經(jīng),B,審閱后產(chǎn)生64位,hash,值并對(duì)該值簽名,返回給,A,,A,用,M,?,替換,M,,Hash,必須足夠長(zhǎng)(64,?,128,?,160),,散列函數(shù)的平安性,,強(qiáng)行攻擊：生日攻擊,,,,,,MD5 128位， 24小時(shí)找到一個(gè)沖突,,,單向,2,n,弱無(wú)碰撞,2,n,強(qiáng)無(wú)碰撞,2,n/2,,Hash函數(shù)的構(gòu)造,,基于數(shù)學(xué)難題的構(gòu)造方法：,,計(jì)算速度慢，不實(shí)用,,利用對(duì)稱密碼體制來(lái)設(shè)計(jì)Hash,,直接設(shè)計(jì),,,,,分組鏈接 Block Chaining,用對(duì)稱加密算法構(gòu)造hash函數(shù),,M=(M1,M2,…,Mt), H0=Initial value,,Hi=f(Mi,Hi-1), 例如Hi=EMi(Hi-1),,hash: Ht,,速度慢,且許多這樣的hash函數(shù)被證明不平安(與E的平安性無(wú)關(guān)),,下面的四種可能是平安的:,,?Hi=EHi-1(Mi)?Mi,,?Hi=EHi-1(Mi)?Mi?Hi-1,,?Hi=EHi-1(Mi?Hi-1)?Mi,,?Hi=EHi-1(Mi?Hi-1)?Mi?Hi-1,,現(xiàn)在很少使用,,,hash函數(shù)通用結(jié)構(gòu),由,Merkle,于1989年提出,,Ron,Rivest,于1990年提出,MD4,,幾乎被所有,hash,函數(shù)使用,,具體做法:,,把原始消息,M,分成一些固定長(zhǎng)度的塊,Y,i,,最后一塊,padding,并使其包含消息,M,長(zhǎng)度,,設(shè)定初始值,CV,0,,壓縮函數(shù),f, CV,i,=f(CV,i-1,,Y,i-1,),,最后一個(gè),CV,i,為,hash,值,,,,,b,Y,0,n,IV=,,CV,0,f,,b,Y,1,n,f,,b,Y,L-1,n,CV,L-1,f,CV,1,n,n,IV = initial value 初始值,,CV = chaining value 鏈接值,,Yi = ith input block (第i 個(gè)輸入數(shù)據(jù)塊),,f = compression algorithm (壓縮算法〕,,n = length of hash code (散列碼的長(zhǎng)度),,b = length of input block(輸入塊的長(zhǎng)度),General,Structure of Secure Hash Code,CV,L,,CV,0,=IV=,initial n-bit value,,CV,i,=f(CV,i-1,, Y,i-1,),(1,?,i,?,L),,H(M) = CV,L,,討論幾種常用的HASH算法,,MD5,,,SHA-1,,,RIPEMD-160,,,HMAC,,,,,,MD5簡(jiǎn)介,Merkle于1989年提出hash function模型,,Ron Rivest于1990年提出MD4,,1992年, MD5 (RFC 1321) developed by Ron Rivest at MIT,,MD5把數(shù)據(jù)分成512-bit塊,,MD5的hash值是128-bit,,在最近數(shù)年之前,MD5是最主要的hash算法,,現(xiàn)行美國(guó)標(biāo)準(zhǔn)SHA-1以MD5的前身MD4為根底,,,,,MD5: padding,Step 1: Padding M ? M1,,|M1| ? 448 mod 512,,|M1| > |M| ?,,如果|M| ? 448 mod 512,那么|M1| = |M|+512,,Padding內(nèi)容: 100…0,,Step 2: Append 64-bit length M1 ? M2,,假設(shè)|M| > 264,那么僅取低64位,,低字節(jié)在前 (little-endian),,|M2|為512的倍數(shù): Y0,Y1,…,YL-1,,,,,MD5: 示意圖,,,,,MD5: compression,Step 3: Initialize MD buffer (little-endian),,A = 01 23 45 67 (0x67452301),,B = 89 AB CD EF (0xEFCDAB89),,C = FE DC BA 98 (0x98BADCFE),,D = 76 54 32 10 (0x10325476),,Step 4: Compression,,CV,0,=IV,,,CV,i,=H,MD5,(CV,i-1,,Y,i,),,Step 5: Output,,MD = CV,L,,,,,MD5 Step 4: 示意圖,,,,,MD5 Step 4: overview,Step 4: CV0=IV, CVi=HMD5(CVi-1,Yi),,(A0,B0,C0,D0)?(A,B,C,D),,RoundOne(A,B,C,D,T[1…16],X[0…15]),,RoundTwo(A,B,C,D,T[17…32],X[0…15]),,RoundThree(A,B,C,D,T[33…48],X[0…15]),,RoundFour(A,B,C,D,T[49…64],X[0…15]),,(A,B,C,D)?(A+A0,B+B0,C+C0,D+D0),,512-bit塊(X[…]為32-bit表示)在四個(gè)Round使用,,每個(gè)Round包含16次循環(huán),每次處理一個(gè)32-bit,,T[j]= [sin(j)*232]的整數(shù)局部, 1 ? j ? 64,,MD5 Compression Function,每一輪包含對(duì)緩沖區(qū)ABCD的16步操作所組成的一個(gè)序列。,,,a?b + (( a + g(b,c,d) + X[k] +T[i])<<<s),,,其中，,,a,b,c,d = 緩沖區(qū)的四個(gè)字，以一個(gè)給定的次序排列；,,g = 根本邏輯函數(shù)F,G,H,I之一；,,<<<s = 對(duì)32位字循環(huán)左移s位,,X[k] = M[q?16 + k] = 在第q個(gè)512位數(shù)據(jù)塊中的第k個(gè)32位字,,T[i] = 表T中的第i個(gè)32位字；,,+ = 模 232的加；,,A,B,C,D,A,B,C,D,+,+,+,CLSs,+,g,X[k],T[i],Function g g(b,c,d),,1 F(b,c,d) (b,?c)?(b?d),,2 G(b,c,d) (b?d)?(c?d),,3 H(b,c,d) b?c?d,,4 I(b,c,d) c?(b?d),?,2,i = (1+5i) mod 16,,?,3,i = (5+3i) mod 16,,?,2,i = 7i mod 16,,MD5 Step 4: RoundOne,For(k = 0; k < 16; ++k) {,,A?B + ((A+g,1,(B,C,D)+X[?,1,(k)]+T[16?0+k+1]) <<< s,1,[k mod 4]),,(A,B,C,D),?,(A,B,C,D),>>>32,,},,g,1,(B,C,D) = (B & C) | (B & D),,?,1,(k) = k, 0 ? k < 16,,s,1,[0…3] = [7,12,17,22],,MD5 Step 4: RoundTwo,For(k = 0; k < 16; ++k) {,,A?B + ((A+g,2,(B,C,D)+X[?,2,(k)]+T[16?1+k+1]) <<< s,2,[k mod 4]),,(A,B,C,D),?,(A,B,C,D),>>>32,,},,g,2,(B,C,D) = (B & D) | (C & D),,?,2,(k) = (1+5k) mod 16, 0 ? k < 16,,s,2,[0…3] = [5,9,14,20],,MD5 Step 4: RoundThree,For(k = 0; k < 16; ++k) {,,A?B + ((A+g,3,(B,C,D)+X[?,3,(k)]+T[16?2+k+1]) <<< s,3,[k mod 4]),,(A,B,C,D),?,(A,B,C,D),>>>32,,},,g,3,(B,C,D) = B ? C ? D,,?,3,(k) = (5+3k) mod 16, 0 ? k < 16,,s,3,[0…3] = [4,11,16,23],,MD5 Step 4: RoundFour,For(k = 0; k < 16; ++k) {,,A?B + ((A+g,4,(B,C,D)+X[?,4,(k)]+T[16?3+k+1]) <<< s,4,[k mod 4]),,(A,B,C,D),?,(A,B,C,D),>>>32,,},,g,4,(B,C,D) = C ? (B | D),,?,4,(k) = 7k mod 16, 0 ? k < 16,,s,4,[0…3] = [6,10,15,21],,CV0 = IV,,CVq+1 = SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]),,MD = CVL,,,其中：IV = ABCD的初始值〔見(jiàn)步驟3〕,,Yq = 消息的第q個(gè)512位數(shù)據(jù)塊,,L = 消息中數(shù)據(jù)塊數(shù)；,,CVq = 鏈接變量，用于第q個(gè)數(shù)據(jù)塊的處理,,RFx = 使用根本邏輯函數(shù)x的一輪功能函數(shù)。,,MD = 最終消息摘要結(jié)果,,SUM32=分別按32位字計(jì)算的模232加法結(jié)果。,,,,,MD5: 總結(jié),MD5使用小數(shù)在前,,生日攻擊+64位可計(jì)算 ? 128位hash值太短,,Dobbertin在1996年找到了兩個(gè)不同的512-bit塊,它們?cè)贛D5計(jì)算下產(chǎn)生相同的hash,,至今還沒(méi)有真正找到兩個(gè)不同的消息,它們的MD5的hash相等,,MD5不是足夠平安的,,Secure Hash Algorithm簡(jiǎn)介,1992年NIST制定了SHA(128位),,1993年SHA成為標(biāo)準(zhǔn)〔FIPS PUB 180〕,,1994年修改產(chǎn)生SHA-1(160位),,1995年SHA-1成為新的標(biāo)準(zhǔn),作為SHA-1(FIPS PUB 180-1),,SHA-1要求輸入消息長(zhǎng)度<264,,輸入按512位的分組進(jìn)行處理的,,SHA-1的摘要長(zhǎng)度為160位,,根底是MD4,,SHA-1: padding,與MD5相同,,Step 1: Padding M ? M1,,|M1| ? 448 mod 512,,|M1| > |M| ?,,如果|M| ? 448 mod 512,那么|M1| = |M|+512,,Padding內(nèi)容: 100…0,,Step 2: Append 64-bit length M1 ? M2,,|M| < 264,,高字節(jié)在前 (big-endian),,|M2|為512的倍數(shù): Y0,Y1,…,YL-1,,SHA-1: compress,Step 3: Initialize MD buffer (big-endian),,A = 67 45 23 01 (0x67452301),,B = EF CD AB 89 (0xEFCDAB89),,C = 98 BA DC FE (0x98BADCFE),,D = 10 32 54 76 (0x10325476),,E = C3 D2 E1 F0 (0xC3D2E1F0),,Step 4: Compression,,CV,0,=IV,,,CV,i,=H,SHA-1,(CV,i-1,,Y,i,),,Step 5: Output,,MD = CV,L,,SHA-1 step 4: 示意圖,,SHA-1 step 4: overview,Step 4: CV,0,=IV,,CV,i,=H,SHA-1,(CV,i-1,,Y,i,),,(A0,B0,C0,D0,E0)?(A,B,C,D,E), t ? 0,,Round(A,B,C,D,E,K[t],W[t]) 0 ? t < 80,,(A,B,C,D,E)?(A+A0,B+B0,C+C0,D+D0,E+E0),,整個(gè),Round,包含,80,次循環(huán),每次處理一個(gè)32-,bit,,W[t] = Y,i,[t] 0 ? t < 16,,W[t] =(W[t-16]?W[t-14]?W[t-8]?W[t-3])<<<1,,16 ? t < 80,,每組(16個(gè)),W[t],可由前一組,W[t],直接計(jì)算,,SHA-1: compression function,Four rounds: 0 ? t < 80,,E ? E+f(t,B,C,D)+(A<<<5)+W[t]+K[t],,B ? B<<<30,,(A,B,C,D,E)?(A,B,C,D,E)>>>32,,f(t,B,C,D) = (B&C)|(B&D) 0 ? t < 20,,K[t] = 2,30,? sqrt(2),,f(t,B,C,D) = B ? C ? D 20 ? t < 40,,K[t] = 2,30,? sqrt(3),,f(t,B,C,D) = (B&C)|(B&D)|(C&D) 30 ? t < 60,,K[t] = 2,30,? sqrt(5),,f(t,B,C,D) = B ? C ? D 60 ? t < 80,,K[t] = 2,30,? sqrt(10),,SHA-1,壓縮函數(shù),,,A,B,C,D,E,? (E + f(t,B,C,D)+S,5,(A) +Wt + Kt),A,S,30,(B),C,D,其中，,,A,B,C,D,E = 緩沖區(qū)的5個(gè)字；,,t = 步數(shù)，0<= t <= 79；,,f(t,B,C,D) = 步t的根本邏輯函數(shù)；,,Sk = 循環(huán)左移k位給定的32位字；,,Wt = 一個(gè)從當(dāng)前512數(shù)據(jù)塊導(dǎo)出的32位字；,,Kt = 一個(gè)用于加法的常量，四個(gè)不同的值，如前所述,,+ = 加模232。,,A,B,C,D,A,B,C,D,+,+,+,+,f,t,T[i],E,E,S,5,W,t,K,t,S,30,,SHA-1總結(jié),SHA-1使用big-endian,,抵抗生日攻擊: 160位hash值,,沒(méi)有發(fā)現(xiàn)兩個(gè)不同的512-bit塊,它們?cè)赟HA-1計(jì)算下產(chǎn)生相同的“hash〞,,速度慢于MD5,,平安性優(yōu)于MD5,,RIPEMD-160簡(jiǎn)介,歐洲RIPE工程的結(jié)果,,RIPEMD為128位,,更新后成為RIPEMD-160,,根底是MD5,,RIPEMD-160: padding,Step 1: Padding M ? M1,,|M1| ? 448 mod 512,,|M1| > |M| ?,,如果|M| ? 448 mod 512,那么|M1| = |M|+512,,Padding內(nèi)容: 100…0,,Step 2: Append 64-bit length M1 ? M2,,|M| < 264,,低字節(jié)在前 (little-endian),,|M2|為512的倍數(shù): Y0,Y1,…,YL-1,,RIPEMD-160: compression,Step 3: Initialize MD buffer (little-endian),,A = 01 23 45 67 (0x67452301),,B = 89 AB CD EF (0xEFCDAB89),,C = FE DC BA 98 (0x98BADCFE),,D = 76 54 32 10 (0x10325476),,E = F0 E1 D2 C3 (0xC3D2E1F0),,Step 4: Compression,,CV,0,=IV,,,CV,i,=H,RIPE,(CV,i-1,,Y,i,),,Step 5: Output,,MD = CV,L,,RIPEMD-160 step 4: 示意圖,,RIPEMD-160: compression function,,(A0,B0,C0,D0,E0)?(A,B,C,D,E),,Five rounds: 0 ? t < 16,,,A ? ((A+,f,(B,C,D)+X[,p,[t]]+,K,)<<<,s,)+E,,C ? C<<<10,,(A,B,C,D,E)?(A,B,C,D,E)>>>32,,A??((A?+,f?,(B?,C?,D?)+X[,p?,[t]]+,K?,)<<<,s?,)+E?,,C??C?<<<10,,(A?,B?,C?,D?,E?)?(A?,B?,C?,D?,E?)>>>32,,(A,B,C,D,E) ? (B0+C+D?, C0+D+E?, D0+E+A?, E0+A+B?, A0+B+C?),,RIPEMD-160 step 4: f,i,,,,?, ?,Function f,1,,f,2,,f,3,,f,4,,f,5,:,,f,1,(B,C,D) = B ? C ? D,,f,2,(B,C,D) = (B&C)|(!B&D),,f,3,(B,C,D) = (B|!C) ? D,,f,4,(B,C,D) = (B&C)|(C&!D),,f,5,(B,C,D) = B ? (C|!D),,?: 7,4,13,1,10,6,15,3,12,0,9,5,2,14,11,8,,?: 5,14,7,0,9,2,11,4,13,6,15,8,1,10,3,12,,RIPEMD-160總結(jié),RIPEMD-160使用little-endian,,抵抗生日攻擊: 160位hash值,,沒(méi)有發(fā)現(xiàn)兩個(gè)不同的512-bit塊,它們?cè)赗IPEMD-160計(jì)算下產(chǎn)生相同的“hash〞,,速度略慢于SHA-1,,平安性優(yōu)于MD5,,對(duì)密碼分析的抵抗力好于SHA-1,,比較：,,,MD5 SHA-1 RIPEMD-160,,摘要長(zhǎng)度 128位 160位 160位,,根本處理單位 512位 512位 512位,,步數(shù) 64(4 of 16) 80(4 of 20) 160(5 paired of 16),,最大消息長(zhǎng)度 無(wú)限 264-1位 264-1位,,根本邏輯函數(shù) 4 4 5,,加法常數(shù) 64 4 9,,Endianness Little-endian Big-endian Little-endian,性能 32.4 Mbps 14.4Mbps 13.6Mbps,,Http:// eskimo /~weidai/benchmarks.txt, C++ on Pentium 266Mhz,,hash函數(shù)小結(jié),hash,函數(shù)把變長(zhǎng)信息映射到定長(zhǎng)信息,,hash,函數(shù)不具備可逆性,,hash,函數(shù)速度較快,,hash,函數(shù)與對(duì)稱密鑰加密算法有某種相似性,,對(duì),hash,函數(shù)的密碼分析比對(duì)稱密鑰密碼更困難,,hash,函數(shù)可用于消息摘要,,hash,函數(shù)可用于數(shù)字簽名,,HMAC簡(jiǎn)介,MAC,可用分組加密算法產(chǎn)生,,ANSI,標(biāo)準(zhǔn)(,X9.17): M=(X,1,,X,2,,…,X,t,),,?,M,1,=E,K,(X,1,),,?,M,j+1,=E,K,(X,j+1,??,M,j,), 1,?j<t,,速度慢,,加密算法出口受限制,,hash,函數(shù)可用來(lái)構(gòu)造,MAC: HMAC,為其中之一,,HMAC,作為,RFC2104,并在,SSL,中使用,,HMAC設(shè)計(jì)目標(biāo),,無(wú)需修改地使用現(xiàn)有的散列函數(shù),,當(dāng)出現(xiàn)新的散列函數(shù)時(shí),要能輕易地替換,,保持散列函數(shù)的原有性能不會(huì)導(dǎo)致算法性能的降低,,使用和處理密鑰的方式簡(jiǎn)單,,對(duì)鑒別機(jī)制的平安強(qiáng)度容易分析,與hash函數(shù)有同等的平安性,,HMAC示意圖,,HMAC的定義與特征,?,?,對(duì)密鑰K左邊補(bǔ)0以產(chǎn)生一個(gè)hash用塊K,+,,?,K,+,每個(gè)字節(jié)與ipad(00110110)作XOR以產(chǎn)生S,i,,?,對(duì)(S,i,||M)進(jìn)行hash,,?,K,+,每個(gè)字節(jié)與opad(01011010)作XOR以產(chǎn)生S,o,,?,HMAC=f[IV,S,o,||f(IV,S,i,||M)],,,數(shù)字簽名,,Message authentication用以保護(hù)雙方之間的數(shù)據(jù)交換不被第三方侵犯；但它并不保證雙方自身的相互欺騙。假定A發(fā)送一個(gè)認(rèn)證的信息給B，雙方之間的爭(zhēng)議可能有多種形式：,,B偽造一個(gè)不同的消息，但聲稱是從A,收到的。,,A可以否認(rèn)發(fā)過(guò)該消息，B無(wú)法證明A確實(shí)發(fā)了該消息。,,例如：EFT中改大金額；股票交易指令虧損后抵賴。,,,,數(shù)字簽名,傳統(tǒng)簽名的根本特點(diǎn):,,?能與被簽的文件在物理上不可分割,,?簽名者不能否認(rèn)自己的簽名,,?簽名不能被偽造,,?容易被驗(yàn)證,,數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化,根本要求:,,?能與所簽文件“綁定〞,,?簽名者不能否認(rèn)自己的簽名,,?簽名不能被偽造,,?容易被自動(dòng)驗(yàn)證,,數(shù)字簽名應(yīng)具有的性質(zhì),,必須能夠驗(yàn)證作者及其簽名的日期時(shí)間；,,必須能夠認(rèn)證簽名時(shí)刻的內(nèi)容；,,簽名必須能夠由第三方驗(yàn)證，以解決爭(zhēng)議；,,因此，數(shù)字簽名功能包含了鑒別的功能,,數(shù)字簽名的設(shè)計(jì)要求,,簽名必須是依賴于被簽名信息的一個(gè)位串模式；,,簽名必須使用某些對(duì)發(fā)送者是唯一的信息，以防止雙方的偽造與否認(rèn)；,,必須相對(duì)容易生成該數(shù)字簽名；,,必須相對(duì)容易識(shí)別和驗(yàn)證該數(shù)字簽名；,,偽造該數(shù)字簽名在計(jì)算復(fù)雜性意義上具有不可行性，既包括對(duì)一個(gè)已有的數(shù)字簽名構(gòu)造新的消息，也包括對(duì)一個(gè)給定消息偽造一個(gè)數(shù)字簽名；,,在存儲(chǔ)器中保存一個(gè)數(shù)字簽名副本是現(xiàn)實(shí)可行的。,,數(shù)字簽名分類,以方式分,,?直接數(shù)字簽名direct digital signature,,?仲裁數(shù)字簽名arbitrated digital signature,,以平安性分,,?無(wú)條件平安的數(shù)字簽名,,?計(jì)算上平安的數(shù)字簽名,,以可簽名次數(shù)分,,?一次性的數(shù)字簽名,,?屢次性的數(shù)字簽名,,直接數(shù)字簽名〔DDS〕,,(1) A,?,B: E,KRa,[M],,,提供了鑒別與簽名：,,只有,A,具有,KRa,進(jìn)行加密;,,傳輸中沒(méi)有被篡改；,,需要某些格式信息/冗余度；,,任何第三方可以用,KUa,驗(yàn)證簽名,(1’) A,?,B: E,KUb,[E,KRa,(M)],,,提供了保密(KUb)、鑒別與簽名(KRa)：,,直接數(shù)字簽名,,(2) A,?,B: M||E,KRa,[H(M)],提供鑒別及數(shù)字簽名,,-- H(M) 受到密碼算法的保護(hù)；,,-- 只有 A 能夠生成 E,KRa,[H(M)],(2’) A,?,B: E,K,[M||E,KRa,[H(M)]],提供保密性、鑒別和數(shù)字簽名。,,直接數(shù)字簽名的缺點(diǎn),,驗(yàn)證模式依賴于發(fā)送方的保密密鑰；,,發(fā)送方要抵賴發(fā)送某一消息時(shí)，可能會(huì)聲稱其私有密鑰喪失或被竊，從而他人偽造了他的簽名。,,通常需要采用與私有密鑰平安性相關(guān)的行政管理控制手段來(lái)制止或至少是削弱這種情況，但威脅在某種程度上依然存在。,,改進(jìn)的方式例如可以要求被簽名的信息包含一個(gè)時(shí)間戳〔日期與時(shí)間〕，并要求將已暴露的密鑰報(bào)告給一個(gè)授權(quán)中心。,,X的某些私有密鑰確實(shí)在時(shí)間T被竊取，敵方可以偽造X的簽名及早于或等于時(shí)間T的時(shí)間戳。,,仲裁數(shù)字簽名,,引入仲裁者。,,通常的做法是所有從發(fā)送方X到接收方Y(jié)的簽名消息首先送到仲裁者A，A將消息及其簽名進(jìn)行一系列測(cè)試，以檢查其來(lái)源和內(nèi)容，然后將消息加上日期并與已被仲裁者驗(yàn)證通過(guò)的指示一起發(fā)給Y。,,仲裁者在這一類簽名模式中扮演敏感和關(guān)鍵的角色。,,所有的參與者必須極大地相信這一仲裁機(jī)制工作正常?！瞭rusted system〕,,仲裁數(shù)字簽名技術(shù),(a) 單密鑰加密方式，仲裁者可以看見(jiàn)消息,,(1) X,?A：M||E,K,xa,[ID,x,|| H(M)],,(2),A,?Y：E,K,ay,[ID,x,|| M || E,K,xa,[ID,x,|| H(M)] || T],X與A之間共享密鑰K,xa,，Y,與A之間共享密鑰K,ay,；,,X：,準(zhǔn)備消息M，計(jì)算其散列碼H(M)，用X的標(biāo)識(shí)符,ID,x,和散列值構(gòu)成,,簽名，并將消息及簽名經(jīng)K,xa,加密后發(fā)送給A；,,A：解密簽名，用H(M)驗(yàn)證消息M，然后將ID,x,，M，簽名，和時(shí)間戳,,一起經(jīng)K,ay,加密后發(fā)送給Y；,,Y：解密A發(fā)來(lái)的信息，并可將M和簽名保存起來(lái)。,解決糾紛：,,Y：向A發(fā)送 EKay[IDx|| M || EKxa[IDx|| H(M)]],,A：用Kay恢復(fù)IDx，M，和簽名〔 EKxa[IDx|| H(M)]〕，然后用Kxa解密簽,,名并驗(yàn)證散列碼,,注意：,,在這種模式下Y不能直接驗(yàn)證X的簽名，Y認(rèn)為A的消息正確，只,,因?yàn)樗鼇?lái)自A。因此，雙方都需要高度相信A:,,X必須信任A沒(méi)有暴露Kxa，并且沒(méi)有生成錯(cuò)誤的簽名,,EKxa[IDx|| H(M)],,Y必須信任A僅當(dāng)散列值正確并且簽名確實(shí)是X產(chǎn)生的情況下才,,發(fā)送的 EKay[IDx|| M || EKxa[IDx|| H(M)] || T],,雙方都必須信任A處理爭(zhēng)議是公正的。,,只要A遵循上述要求，那么X相信沒(méi)有人可以偽造其簽名；Y相信X不,,能否認(rèn)其簽名。,,上述情況還隱含著A可以看到X給Y的所有信息，因而所有的竊聽(tīng)者,,也能看到。,,(b) 單密鑰加密方式，仲裁者不可以看見(jiàn)消息,,(1) X,?A： ID,x,|| E,K,xy,[M]||E,K,xa,[ID,x,|| H(E,K,xy,[M])],,(2),A,?Y：E,K,ay,[ID,x,||E,K,xy,[M] || E,K,xa,[ID,x,|| H(E,K,xy,[M])] || T],在這種情況下，X與Y之間共享密鑰K,xy,，,,X：將標(biāo)識(shí)符,ID,x,,,密文 E,K,xy,[M]，以及對(duì)ID,x,和密文消息的散列碼用,,K,xa,加密后形成簽名,發(fā)送給A。,,A：解密簽名，用散列碼驗(yàn)證消息，這時(shí)A只能驗(yàn)證消息的密文而不,,能讀取其內(nèi)容。然后A將來(lái)自X的所有信息加上時(shí)間戳并用K,ay,加,,密后發(fā)送給Y。,(a),和(b)共同存在一個(gè)共性問(wèn)題：,,A和發(fā)送方聯(lián)手可以否認(rèn)簽名的信息；,,A和接收方聯(lián)手可以偽造發(fā)送方的簽名；,,(c) 雙密鑰加密方式，仲裁者不可以看見(jiàn)消息,,(1) X,?A： ID,x,|| E,KR,x,[ID,x,|| E,KU,y,(E,KR,x,[M])],,(2),A,?Y： E,KR,a,[ID,x,|| E,KU,y,[E,KR,x,[M]] || T],X：對(duì)消息M雙重加密：首先用X的私有密鑰KRx，然后用Y的公開(kāi),,密鑰KUy。形成一個(gè)簽名的、保密的消息。然后將該信息以及,,X的標(biāo)識(shí)符一起用KRx簽名后與IDx 一起發(fā)送給A。這種內(nèi)部、,,雙重加密的消息對(duì)A以及對(duì)除Y以外的其它人都是平安的。,,A：檢查X的公開(kāi)/私有密鑰對(duì)是否仍然有效，是，那么確認(rèn)消息。并,,將包含IDx、雙重加密的消息和時(shí)間戳構(gòu)成的 消息用KRa簽名后,,發(fā)送給Y。,本模式比上述兩個(gè)模式具有以下好處：,,1、在通信之前各方之間無(wú)須共享任何信息，從而防止了聯(lián)手作弊；,,2、即使KRx 暴露，只要KRa 未暴露，不會(huì)有錯(cuò)誤標(biāo)定日期的消息,,被發(fā)送；,,3、從X發(fā)送給Y的消息的內(nèi)容對(duì)A和任何其他人是保密的。,,數(shù)字簽名算法,,普通數(shù)字簽名算法,,RSA,,EIGamal,,DSS/DSA,,不可否認(rèn)的數(shù)字簽名算法,,群簽名算法,,盲簽名算法,,RSA簽名方案,,,RSA簽名,A,的公鑰私鑰對(duì){,KU,a,||,KR,a,},,A,對(duì)消息,M,簽名:,S,A,=,E,KRa,(M),,問(wèn)題:,,速度慢,,信息量大,,第三方仲裁時(shí)必須暴露明文信息,,漏洞:,E,KRa,(x,?,y),?,E,KRa,(x),?,E,KRa,(y) mod n,,先做摘要:,H,M,= hash(M),,再對(duì),H,M,簽名,S,A,=,E,KRa,(H,M,),,hash,函數(shù)的無(wú)碰撞性保證了簽名的有效性,,簽名與加密,簽名提供真實(shí)性(authentication),,加密提供保密性(confidentiality),,“簽名+加密〞提供“真實(shí)性+保密性〞,,兩種實(shí)現(xiàn)方式: (A?B),,?先簽名,后加密: EKUb{M||SigA(M)},,