《北京大學(xué)網(wǎng)絡(luò)信息安全課件-身份認(rèn)證》由會員分享，可在線閱讀，更多相關(guān)《北京大學(xué)網(wǎng)絡(luò)信息安全課件-身份認(rèn)證（127頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,*,,,,,,,網(wǎng)絡(luò)與信息平安第五講,,密碼學(xué)根底(四),,,王 昭,,北京大學(xué)信息科學(xué)技術(shù)學(xué)院,,軟件研究所--信息平安研究室wangzhao@infosec.pku.edu,2003年春季北京大學(xué)碩士研究生課程,,回憶與總結(jié),,對稱密碼算法,,運算速度快、密鑰短、多種用途〔隨機數(shù)產(chǎn)生、Hash函數(shù)〕、歷史悠久,,密鑰管理困難〔分發(fā)、更換〕,,非對稱密碼算法,,只需保管私鑰、可以相當(dāng)長的時間保持不變、需要的數(shù)目較小,,運算速度慢、密鑰尺寸大、歷史短,,,信息平安的需求,,保密性〔 Conf

2、identiality〕,,完整性 〔Integrity〕,,數(shù)據(jù)完整性，未被未授權(quán)篡改或者損壞,,系統(tǒng)完整性，系統(tǒng)未被非授權(quán)操縱，按既定的功能運行,,可用性 〔Availability〕,,鑒別 〔Authenticity〕,,實體身份的鑒別，適用于用戶、進程、系統(tǒng)、信息等,,不可否認(rèn)性 〔 Non-repudiation〕,,防止源點或終點的抵賴,,??,,討論議題,,消息鑒別〔Message Authentication),,,,散列函數(shù)〔 Hash Functions),,,,數(shù)字簽名〔Digital Signature〕,,,,定義,,消息鑒別〔Message Authenticat

3、ion)：,,是一個證實收到的消息來自可信的源點且未被篡改的過程。,,散列函數(shù)〔 Hash Functions)：,,一個散列函數(shù)以一個變長的報文作為輸入，并產(chǎn)生一個定長的散列碼，有時也稱報文摘要，作為輸出。,,數(shù)字簽名〔Digital Signature〕,,是一種防止源點或終點抵賴的鑒別技術(shù)。,,,,,通信系統(tǒng)典型攻擊,,1),竊聽,,2)業(yè)務(wù)流分析,,3)消息篡改,,內(nèi)容修改：消息內(nèi)容被插入、刪除、修改。,,順序修改：插入、刪除或重組消息序列。,,時間修改：消息延遲或重放。,,4)冒充：從一個假冒信息源向網(wǎng)絡(luò)中插入消息,,5)抵賴：接受者否認(rèn)收到消息；發(fā)送者否認(rèn)發(fā)送過消息。,,,兩個概念

4、,,鑒別(Authentication):,,真?zhèn)涡?,認(rèn)證(Certification),,資格審查,,,,,消息鑒別,鑒別的目的,,鑒別模型,,鑒別函數(shù),,,鑒別的目的,,鑒別的主要,目的,有二：,,第一，驗證信息的發(fā)送者是真正的，而不是冒充的，此為信源識別；,,第二，驗證信息的完整性，在傳送或存儲過程中未被篡改，重放或延遲等。,,,鑒別模型,,一個單純,鑒別系統(tǒng),的模型,竄擾者,,信宿,,,信源,,鑒別編碼器,鑒別譯碼器,信道,平安信道,密鑰源,,鑒別系統(tǒng)的組成,,鑒別編碼器和鑒別譯碼器可抽象為鑒別函數(shù)。,,一個平安的鑒別系統(tǒng)，需滿足,,〔1〕意定的接收者能夠檢驗和證實消息的合法性、真實

5、性和完整性,,〔2〕消息的發(fā)送者和接收者不能抵賴,,〔3〕除了合法的消息發(fā)送者，其它人不能偽造合法的消息,,,首先要選好恰當(dāng)?shù)蔫b別函數(shù)，該函數(shù)產(chǎn)生一個鑒別標(biāo)識，然后在此根底上，給出合理的鑒別協(xié)議(Authentication Protocol)，使接收者完成消息的鑒別。,,鑒別函數(shù),,可用來做鑒別的函數(shù)分為三類：,,(1),消息加密函數(shù),(Message encryption),,,用完整信息的密文作為對信息的鑒別。,,(2),消息鑒別碼MAC,(Message Authentication Code),,公開函數(shù)+密鑰產(chǎn)生一個固定長度的值作為鑒別標(biāo)識,,(3),散列函數(shù),(Hash Func

6、tion),,是一個公開的函數(shù)，它將任意長的信息映射成一個固定長度的信息。,,,消息加密,,消息的自身加密可以作為一個鑒別的度量。,,對稱密鑰模式和公開密鑰模式有所不同。,,,(a) 對稱加密：保密性與鑒別,,提供保密,,提供鑒別,,僅來自,A,,傳輸中沒有被更改,,需要某種結(jié)構(gòu)或冗余,,不提供簽名,,,,如何自動確定是否收到的明文可解密為可懂的明文?,,,一種解決方法是強制明文有某種結(jié)構(gòu).,,,過失控制：Error Control,,(b) 公鑰加密：保密性,,提供保密,,不提供鑒別,,(c) 公鑰加密：鑒別與簽名,,提供鑒別和簽名,,僅,A,有,Kra,可以進行加密,,傳輸中沒有被更改,,

7、需要某種結(jié)構(gòu)或冗余,,任何一方均可以使用,Kua,驗證簽名,,(d)公鑰加密：保密、鑒別與簽名,,KUb,提供保密性,,Kra,提供鑒別和簽名,,消息,鑒別,碼MAC,使用一個密鑰生成一個固定大小的小數(shù)據(jù)塊，并參加到消息中，稱MAC， 或密碼校驗和〔cryptographic checksum〕,1、接收者可以確信消息M未被改變。,2、接收者可以確信消息來自所聲稱的發(fā)送者；,3、如果消息中包含順序碼〔如HDLC,X.25,TCP〕，那么接收者可以保證消息的正常順序；,MAC函數(shù)類似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比加密算法被攻擊的弱點要少。,,MAC的根本用法(a),,消息鑒別,Pr

8、ovides 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,,通過加密得到信息真實性

9、: 問題,保密性與真實性是兩個不同的概念,,根本上,信息加密提供的是保密性而非真實性,,加密代價大(公鑰算法代價更大),,鑒別函數(shù)與保密函數(shù)的別離能提供功能上的靈活性,,某些信息只需要真實性,不需要保密性,,播送的信息難以使用加密(信息量大),,網(wǎng)絡(luò)管理信息等只需要真實性,,政府/權(quán)威部門的公告,,散列函數(shù),Hash Function,,H(M): 輸入為任意長度的消息M; 輸出為一個固定長度的散列值，稱為消息摘要Message Digest〕。,,這個散列值是消息M的所有位的函數(shù)并提供錯誤檢測能力：消息中的任何一位或多位的變化都將導(dǎo)致該散列值的變化。,,又稱為：哈希函數(shù)、數(shù)字指紋〔Digit

10、al finger print)、壓縮〔Compression)函數(shù)、緊縮〔Contraction 〕函數(shù)、數(shù)據(jù)鑒別碼DAC〔Data authentication code〕、篡改檢驗碼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 crypto

11、graphically 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),,Pr

12、ovides 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)點,,加密軟件很慢,,加密硬件的開銷很大,,加密是對大長度數(shù)據(jù)進行優(yōu)化的,,加密算法可能受專利保護,,加密算法可能受出口的限制.,,,MAC函數(shù)的特性與實現(xiàn),,MAC函數(shù)為多對一映射,,包含所有可能的MAC和所有可能的密鑰,,n-bit MAC： 有2,n,個可能的MAC；,,k-bit 密鑰：

13、有2,k,個可能的密鑰；,,N個可能的消息：有 N>>2,n,,,攻擊者如何用強力攻擊方法攻擊MAC？,,假設(shè)：用戶A和B通信時沒有增加保密性實現(xiàn)，攻擊者可以看到明文， k > n (k為密鑰長度位數(shù)，n為MAC長度位數(shù),),,給定：M,1,和MAC,1,， MAC,1,= C,K1,(M,1,),,密碼分析員可以計算MAC,i,= C,Ki,(M,1,) 對所有可能的Ki，至少有一個Ki保證產(chǎn)生 MAC,i,= MAC,1,注意：總共會產(chǎn)生2k個MAC結(jié)果，但只有2n< 2k個不同的MAC值，因此，有假設(shè)干個key將產(chǎn)生相同的MAC，而攻擊者無法確定哪一個是正確的key。,平均來說， 2k

14、/2n= 2(k-n)個key將產(chǎn)生匹配的MAC，所以，攻擊者需要循環(huán)屢次攻擊，以確定K:,,第一輪：給定 M1和MAC1= CK(M1)，對所有2k個key，計算,,MACi = CKi(M1) ，匹配的數(shù)量? 2(k-n),,第二輪：給定 M2和MAC2= CK(M2)，對所有2(k-n)個key，計算,,MACi = CKi(M2) ，匹配的數(shù)量? 2(k-2?n),,平均來說，如果k=a?n，那么需要a輪。,例：k=80, MAC 32-bit,那么：,,第一輪：248可能的key；,,第二輪：216個；,,第三輪：1 個；,由此可見，強力攻擊企圖發(fā)現(xiàn)authentication k

15、ey不小于甚至大于對同樣長度的解密key的攻擊。,如果 k≤n，那么第一輪就可以產(chǎn)生一個唯一對應(yīng)。仍然可以有多于一個key產(chǎn)生這一配對，這時攻擊者只需對一個新的(message, MAC)進行相同的測試。,,考慮以下的MAC算法,M = (X,1,|| X,2,|| … || Xm) 是一個由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,,強力攻擊需要至少2,5

16、6,次加密來決定K。,但攻擊者可以不用找到 K就可以實施攻擊。,,設(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),,這時,,消息M’ 和 MAC= C,K,(M) = E,K,[?(M)],是一對可被接收者認(rèn)證,,的消息。,C,K,(M ?) = E,K,[?(M ?)],,= E,K,[,Y,1,?,Y,2,?,, …,,?,Ym-,1,?,,Ym ],,= E,K,

17、[,Y,1,?,Y,2,?,, …,,?,Ym-,1,?,(Y,1,?,Y,2,?,, …,,?,Ym-,1,?,,?(M)) ],,= E,K,[?(M)],用此方法，任何長度為64,?(m-1),位的消息可以作為欺騙性,,信息被插入！,,為了防止以上可能的攻擊，MAC函數(shù)應(yīng)具有以下性質(zhì)：,如果一個攻擊者得到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ù)。,,令M ?為M的某些變換，即：M ? =f(M)，〔例如：f可以涉及

18、M中一個或多個給定位的反轉(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ù)據(jù)塊用0向右填充。運用DES算法E，密鑰K,,,數(shù)據(jù)鑒別碼(DAC)的計算如下：,,O,1,= E,K,(D,1,),,O,2,

19、= E,K,(D,2,?,O,1,),,O,3,= E,K,(D,3,?,O,2,),,…,,O,N,= E,K,(D,N,?,O,N-1,),,,M的大小可由通信雙方約定。美國聯(lián)邦電信建議采用,,24bit[見FTSC-1026],而美國金融系統(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,

20、O,N,,+,DAC M-bits,,(16 to 64 bits),,},...,(16<=M<=64),,工作于CFB模式下DES,,,64bit存放器,DES,選左邊k位,選左邊M位,+,y,i,x,i,k,,問題,,假設(shè)對相當(dāng)長的文件通過簽名認(rèn)證怎么辦？如一個合法文件有數(shù)兆字節(jié)長。自然按64比特分劃成一塊一塊，用相同的密鑰獨立地簽每一個塊。然而，這樣太慢。,,解決方法,,解決方法：引入可公開的密碼散列函數(shù)(Hash function)。它將取任意長度的消息做自變量，結(jié)果產(chǎn)生規(guī)定長度的消息摘要。[如，使用數(shù)字簽名標(biāo)準(zhǔn)DSS，消息摘要為160比特]，然后簽名消息摘要。對數(shù)字簽名來說，散列

21、函數(shù)h是這樣使用的：,,消息： x 任意長,,消息摘要： Z=h(x) 160bits,,簽名： y=sigk(Z) 320 bits (簽名一個消息摘要),,,驗證簽名:(x,y),其中y= sigk(h(x))，使用公開的散列函數(shù)h，重構(gòu)作Z ? =h(x)。然后Verk(y)=Z,來看Z?=Z',,新的問題,,用以鑒別的散列函數(shù)，能否減弱認(rèn)證方案的平安性？這個問題是要分析的。簽名的對象由完整消息變成消息摘要，這就有可能出現(xiàn)偽造。,,平安威脅一,,(a)偽造方式一：Oscar以一個有效簽名(x,y)開始，此處y= sigk(h

22、(x))。首先他計算Z=h(x)，并企圖找到一個x'滿足h(x')=h(x)。假設(shè)他做到這一點，那么(x',y)也將為有效簽名。為防止這一點，要求函數(shù)h具有無碰撞特性。,,定義1(弱無碰撞)，散列函數(shù)h稱為是弱無碰撞的，是指對給定消息x ∈ X，在計算上幾乎找不到異與x的x' ∈ X使h(x)=h(x')。,,平安威脅二,,(b)偽造方式二：Oscar首先找到兩個消息x=x',滿足h(x)=h(x'),然后Oscar把x 給Bob且使他對x的摘要h(x)簽名，從而得到y(tǒng),那么(x',y)是一個有效的偽造,。,,,定義2(強無碰撞),散列函數(shù)h被稱為是強無碰撞的,是指在計算上幾乎不可能找到相異的

23、x，x'使得h(x)=h(x')。,,,注：強無碰撞自然含弱無碰撞！,,,平安威脅三,,(c)偽造方式三：在散列函數(shù)的用法(e)中, 秘密值S本身并不發(fā)送, 如果散列函數(shù)不是單向的,攻擊者截獲到M和H(M||S). 然后通過某種逆變換獲得M||S, 因而攻擊者就可以得到S.,,,定義3(單向的),稱散列函數(shù)h為單向的，是指計算h的逆函數(shù)h,-1,在計算上不可行。,,,HASH 函數(shù) h = H(M),,滿足：,,1、H可以作用于一個任意長度的數(shù)據(jù)塊；,,2、H產(chǎn)生一個固定長度的輸出；,,3、對任意給定的x ,H(x) 計算相對容易，無論是軟件還是硬件實現(xiàn)。,,4、對任意給定碼h，找到x滿足

24、H(x)=h具有計算不可行性；〔單向性〕,,5、對任意給定的數(shù)據(jù)塊x，找到滿足H(y)=H(x)的y?x具有計算不可行,,性。,,6、找到任意數(shù)據(jù)對(x,y)，滿足H(x) = H(y)是計算不可行的。,前三條要求具有實用性，第4條是單向性質(zhì)，即給定消息可以產(chǎn)生一個,,散列碼，而給定散列碼不可能產(chǎn)生對應(yīng)的消息。第5條性質(zhì)是保證一個,,給定的消息的散列碼不能找到與之相同的另外的消息。即防止偽造。,,第6條是對的生日攻擊方法的防御能力。,目的：“fingerprint〞 of messgae,,Hash函數(shù)的分類,,根據(jù)平安水平：,,定義1(弱無碰撞)，散列函數(shù)h稱為是弱無碰撞的，是指對給定消息x

25、 ∈ X，在計算上幾乎找不到異于x的x' ∈ X使h(x)=h(x')。,,定義2(強無碰撞)，散列函數(shù)h被稱為是強無碰撞的,是指在計算上幾乎不可能找到相異的x，x'使得h(x)=h(x')。,,注：強無碰撞自然含弱無碰撞！,,Hash函數(shù)的分類,,根據(jù)是否使用密鑰,,帶秘密密鑰的Hash函數(shù):,消息的散列值由只有通信雙方知道的秘密密鑰K來控制。此時，散列值稱作MAC。,,不帶秘密密鑰的Hash函數(shù)：,消息的散列值的產(chǎn)生無需使用密鑰。此時，散列值稱作MDC。,,,Hash與MAC的區(qū)別,,MAC,需要對全部數(shù)據(jù)進行加密,,MAC,速度慢,,Hash,是一種直接產(chǎn)生鑒別碼的方法,,,生日攻擊,,

26、假定使用64位的散列碼,是否平安?,,如果采用傳輸加密的散列碼和不加密的報文M,對手需要找到M ?,使得H(M?)=H(M),以便使用替代報文來欺騙接收者.,,一種基于生日悖論的攻擊可能做到這一點.,,,生日悖論,,生日問題：一個教室中，最少應(yīng)有多少學(xué)生，才使至少有兩人具有相同生日的概率不小于1/2？,,概率結(jié)果與人的直覺是相違背的.,,實際上只需23人,即任找23人，從中總能選出兩人具有相同生日的概率至少為1/2。,,,,,,相關(guān)問題,,給定一個散列函數(shù),有n個可能的輸出,輸出值為H(x),如果H有k個隨機輸入, k必須為多大才能使至少存在一個輸入y,使得H(y)=H(x)的概率大于0.5.

27、,,對單個y, H(y)=H(x)的概率為1/n,反過來H(y)?H(x)的概率為1-(1/n).,,如果產(chǎn)生k個隨機值y,他們之間兩兩不等的概率等于每個個體不匹配概率的乘積,即[1-(1/n)]k,這樣,至少有一個匹配的概率為1-[1-(1/n)]k?1-[1-(k/n)]=k/n.要概率等于0.5,只需k=n/2.,,對長度為m位的散列碼，共有2m個可能的散列碼，假設(shè)要使任意的x,y 有H(x)=H(y)的概率為0.5,只需,,k=2m/2,,,,,,Birthday Attacks: example,A,準(zhǔn)備兩份合同,M,和,M,?,，,一份,B,會同意，一份會取走他的財產(chǎn)而被拒絕,,A

28、,對,M,和,M,?,各做32處微小變化(保持原意),分別產(chǎn)生2,32,個64位,hash,值,,根據(jù)前面的結(jié)論,超過0.5的概率能找到一個,M,和一個,M,?,,它們的,hash,值相同,,A,提交,M,,經(jīng),B,審閱后產(chǎn)生64位,hash,值并對該值簽名,返回給,A,,A,用,M,?,替換,M,,Hash,必須足夠長(64,?,128,?,160),,散列函數(shù)的平安性,,強行攻擊：生日攻擊,,,,,,MD5 128位， 24小時找到一個沖突,,,單向,2,n,弱無碰撞,2,n,強無碰撞,2,n/2,,Hash函數(shù)的構(gòu)造,,基于數(shù)學(xué)難題的構(gòu)造方法：,,計算速度慢，不實用,,利用對稱密碼體

29、制來設(shè)計Hash,,直接設(shè)計,,,,,分組鏈接 Block Chaining,用對稱加密算法構(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的平安性無關(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

30、,于1989年提出,,Ron,Rivest,于1990年提出,MD4,,幾乎被所有,hash,函數(shù)使用,,具體做法:,,把原始消息,M,分成一些固定長度的塊,Y,i,,最后一塊,padding,并使其包含消息,M,長度,,設(shè)定初始值,CV,0,,壓縮函數(shù),f, CV,i,=f(CV,i-1,,Y,i-1,),,最后一個,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 = it

31、h input block (第i 個輸入數(shù)據(jù)塊),,f = compression algorithm (壓縮算法〕,,n = length of hash code (散列碼的長度),,b = length of input block(輸入塊的長度),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,,,RIP

32、EMD-160,,,HMAC,,,,,,MD5簡介,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)行美國標(biāo)準(zhǔn)SHA-1以MD5的前身MD4為根底,,,,,MD5: padding,Step 1: Padding M ? M1,,|M1| ? 448 mod 512,,|M1| > |M| ?,,如果|M|

33、 ? 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),

34、,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,

35、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表示)在四個Round使用,,每個Round包含16次循環(huán),每次處理一個32-bit,,T[j]= [sin(j)*232]的整數(shù)局部, 1 ? j ? 64,,MD5 Compression Function,每一輪包含對緩沖區(qū)ABCD的16步操作所組成的一個序列。,,,a?b + (( a

36、 + g(b,c,d) + X[k] +T[i])<<

37、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,(

38、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,

39、[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; ++

40、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的初始值〔見步驟3〕,,Yq

41、 = 消息的第q個512位數(shù)據(jù)塊,,L = 消息中數(shù)據(jù)塊數(shù)；,,CVq = 鏈接變量，用于第q個數(shù)據(jù)塊的處理,,RFx = 使用根本邏輯函數(shù)x的一輪功能函數(shù)。,,MD = 最終消息摘要結(jié)果,,SUM32=分別按32位字計算的模232加法結(jié)果。,,,,,MD5: 總結(jié),MD5使用小數(shù)在前,,生日攻擊+64位可計算 ? 128位hash值太短,,Dobbertin在1996年找到了兩個不同的512-bit塊,它們在MD5計算下產(chǎn)生相同的hash,,至今還沒有真正找到兩個不同的消息,它們的MD5的hash相等,,MD5不是足夠平安的,,Secure Hash Algorith

42、m簡介,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要求輸入消息長度<264,,輸入按512位的分組進行處理的,,SHA-1的摘要長度為160位,,根底是MD4,,SHA-1: padding,與MD5相同,,Step 1: Padding M ? M1,,|M1| ? 448 mod 512,,|M1| > |M| ?,,如果|M| ? 448 mod 512,那么|M1| = |M|+512,,P

43、adding內(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

44、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+B

45、0,C+C0,D+D0,E+E0),,整個,Round,包含,80,次循環(huán),每次處理一個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個),W[t],可由前一組,W[t],直接計算,,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

46、(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)

47、 +Wt + Kt),A,S,30,(B),C,D,其中，,,A,B,C,D,E = 緩沖區(qū)的5個字；,,t = 步數(shù)，0<= t <= 79；,,f(t,B,C,D) = 步t的根本邏輯函數(shù)；,,Sk = 循環(huán)左移k位給定的32位字；,,Wt = 一個從當(dāng)前512數(shù)據(jù)塊導(dǎo)出的32位字；,,Kt = 一個用于加法的常量，四個不同的值，如前所述,,+ = 加模232。,,A,B,C,D,A,B,C,D,+,+,+,+,f,t,T[i],E,E,S,5

48、,W,t,K,t,S,30,,SHA-1總結(jié),SHA-1使用big-endian,,抵抗生日攻擊: 160位hash值,,沒有發(fā)現(xiàn)兩個不同的512-bit塊,它們在SHA-1計算下產(chǎn)生相同的“hash〞,,速度慢于MD5,,平安性優(yōu)于MD5,,RIPEMD-160簡介,歐洲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

49、,,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 (0x1

50、0325476),,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

51、,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) = (

52、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值,,沒有發(fā)現(xiàn)兩個不同的512-bit塊,它們在RIPEMD-160計算下產(chǎn)生相同的“hash〞,,速度略慢于SHA-1,,平安性優(yōu)于

53、MD5,,對密碼分析的抵抗力好于SHA-1,,比較：,,,MD5 SHA-1 RIPEMD-160,,摘要長度 128位 160位 160位,,根本處理單位 512位 512位 512位,,步數(shù) 64(4 of 16) 80(4 of 20) 160(5 paired of 16),,最大消息長度 無限 264-1位 264-1位,,根本邏輯函數(shù) 4 4 5,,加法常數(shù) 64 4 9,,Endianness Little-endian Big-endian Little-endian,性能 32.4 Mb

54、ps 14.4Mbps 13.6Mbps,,Http:// eskimo /~weidai/benchmarks.txt, C++ on Pentium 266Mhz,,hash函數(shù)小結(jié),hash,函數(shù)把變長信息映射到定長信息,,hash,函數(shù)不具備可逆性,,hash,函數(shù)速度較快,,hash,函數(shù)與對稱密鑰加密算法有某種相似性,,對,hash,函數(shù)的密碼分析比對稱密鑰密碼更困難,,hash,函數(shù)可用于消息摘要,,hash,函數(shù)可用于數(shù)字簽名,,HMAC簡介,MAC,可用分組加密算法產(chǎn)生,,ANSI,標(biāo)準(zhǔn)(,X9.17): M=(X,1,,X,2,,…,X,t,),,?,M,1,

55、=E,K,(X,1,),,?,M,j+1,=E,K,(X,j+1,??,M,j,), 1,?j

56、pad(00110110)作XOR以產(chǎn)生S,i,,?,對(S,i,||M)進行hash,,?,K,+,每個字節(jié)與opad(01011010)作XOR以產(chǎn)生S,o,,?,HMAC=f[IV,S,o,||f(IV,S,i,||M)],,,數(shù)字簽名,,Message authentication用以保護雙方之間的數(shù)據(jù)交換不被第三方侵犯；但它并不保證雙方自身的相互欺騙。假定A發(fā)送一個認(rèn)證的信息給B，雙方之間的爭議可能有多種形式：,,B偽造一個不同的消息，但聲稱是從A,收到的。,,A可以否認(rèn)發(fā)過該消息，B無法證明A確實發(fā)了該消息。,,例如：EFT中改大金額；股票交易指令虧損后抵賴。,,,,數(shù)字簽名,傳統(tǒng)

57、簽名的根本特點:,,?能與被簽的文件在物理上不可分割,,?簽名者不能否認(rèn)自己的簽名,,?簽名不能被偽造,,?容易被驗證,,數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化,根本要求:,,?能與所簽文件“綁定〞,,?簽名者不能否認(rèn)自己的簽名,,?簽名不能被偽造,,?容易被自動驗證,,數(shù)字簽名應(yīng)具有的性質(zhì),,必須能夠驗證作者及其簽名的日期時間；,,必須能夠認(rèn)證簽名時刻的內(nèi)容；,,簽名必須能夠由第三方驗證，以解決爭議；,,因此，數(shù)字簽名功能包含了鑒別的功能,,數(shù)字簽名的設(shè)計要求,,簽名必須是依賴于被簽名信息的一個位串模式；,,簽名必須使用某些對發(fā)送者是唯一的信息，以防止雙方的偽造與否認(rèn)；,,必須相對容易生成該數(shù)字簽名；,

58、,必須相對容易識別和驗證該數(shù)字簽名；,,偽造該數(shù)字簽名在計算復(fù)雜性意義上具有不可行性，既包括對一個已有的數(shù)字簽名構(gòu)造新的消息，也包括對一個給定消息偽造一個數(shù)字簽名；,,在存儲器中保存一個數(shù)字簽名副本是現(xiàn)實可行的。,,數(shù)字簽名分類,以方式分,,?直接數(shù)字簽名direct digital signature,,?仲裁數(shù)字簽名arbitrated digital signature,,以平安性分,,?無條件平安的數(shù)字簽名,,?計算上平安的數(shù)字簽名,,以可簽名次數(shù)分,,?一次性的數(shù)字簽名,,?屢次性的數(shù)字簽名,,直接數(shù)字簽名〔DDS〕,,(1) A,?,B: E,KRa,[M],,,提供了鑒別與簽名：

59、,,只有,A,具有,KRa,進行加密;,,傳輸中沒有被篡改；,,需要某些格式信息/冗余度；,,任何第三方可以用,KUa,驗證簽名,(1’) A,?,B: E,KUb,[E,KRa,(M)],,,提供了保密(KUb)、鑒別與簽名(KRa)：,,直接數(shù)字簽名,,(2) A,?,B: M||E,KRa,[H(M)],提供鑒別及數(shù)字簽名,,-- H(M) 受到密碼算法的保護；,,-- 只有 A 能夠生成 E,KRa,[H(M)],(2’) A,?,B: E,K,[M||E,KRa,[H(M)]],提供保密性、鑒別和數(shù)字簽名。,,直接數(shù)字簽名的缺點,,驗證模式依賴于發(fā)送方的保密密鑰；,,發(fā)送方要抵賴發(fā)送

60、某一消息時，可能會聲稱其私有密鑰喪失或被竊，從而他人偽造了他的簽名。,,通常需要采用與私有密鑰平安性相關(guān)的行政管理控制手段來制止或至少是削弱這種情況，但威脅在某種程度上依然存在。,,改進的方式例如可以要求被簽名的信息包含一個時間戳〔日期與時間〕，并要求將已暴露的密鑰報告給一個授權(quán)中心。,,X的某些私有密鑰確實在時間T被竊取，敵方可以偽造X的簽名及早于或等于時間T的時間戳。,,仲裁數(shù)字簽名,,引入仲裁者。,,通常的做法是所有從發(fā)送方X到接收方Y(jié)的簽名消息首先送到仲裁者A，A將消息及其簽名進行一系列測試，以檢查其來源和內(nèi)容，然后將消息加上日期并與已被仲裁者驗證通過的指示一起發(fā)給Y。,,仲裁者在這一

61、類簽名模式中扮演敏感和關(guān)鍵的角色。,,所有的參與者必須極大地相信這一仲裁機制工作正常。〔trusted system〕,,仲裁數(shù)字簽名技術(shù),(a) 單密鑰加密方式，仲裁者可以看見消息,,(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，計算其散列碼H(M)，用X的標(biāo)識符,ID,x,和散列值構(gòu)成,,簽名，并將消息及簽名經(jīng)K,xa,加密后發(fā)送給A；,,A：解密簽名，用H(M)驗證消

62、息M，然后將ID,x,，M，簽名，和時間戳,,一起經(jīng)K,ay,加密后發(fā)送給Y；,,Y：解密A發(fā)來的信息，并可將M和簽名保存起來。,解決糾紛：,,Y：向A發(fā)送 EKay[IDx|| M || EKxa[IDx|| H(M)]],,A：用Kay恢復(fù)IDx，M，和簽名〔 EKxa[IDx|| H(M)]〕，然后用Kxa解密簽,,名并驗證散列碼,,注意：,,在這種模式下Y不能直接驗證X的簽名，Y認(rèn)為A的消息正確，只,,因為它來自A。因此，雙方都需要高度相信A:,,X必須信任A沒有暴露Kxa，并且沒有生成錯誤的簽名,,EKxa[IDx|| H(M)],,Y必須信任A僅當(dāng)散列值正確并且簽名確實是X產(chǎn)生的情

63、況下才,,發(fā)送的 EKay[IDx|| M || EKxa[IDx|| H(M)] || T],,雙方都必須信任A處理爭議是公正的。,,只要A遵循上述要求，那么X相信沒有人可以偽造其簽名；Y相信X不,,能否認(rèn)其簽名。,,上述情況還隱含著A可以看到X給Y的所有信息，因而所有的竊聽者,,也能看到。,,(b) 單密鑰加密方式，仲裁者不可以看見消息,,(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

64、])] || T],在這種情況下，X與Y之間共享密鑰K,xy,，,,X：將標(biāo)識符,ID,x,,,密文 E,K,xy,[M]，以及對ID,x,和密文消息的散列碼用,,K,xa,加密后形成簽名,發(fā)送給A。,,A：解密簽名，用散列碼驗證消息，這時A只能驗證消息的密文而不,,能讀取其內(nèi)容。然后A將來自X的所有信息加上時間戳并用K,ay,加,,密后發(fā)送給Y。,(a),和(b)共同存在一個共性問題：,,A和發(fā)送方聯(lián)手可以否認(rèn)簽名的信息；,,A和接收方聯(lián)手可以偽造發(fā)送方的簽名；,,(c) 雙密鑰加密方式，仲裁者不可以看見消息,,(1) X,?A： ID,x,|| E,KR,x,[ID,x,|| E,KU,

65、y,(E,KR,x,[M])],,(2),A,?Y： E,KR,a,[ID,x,|| E,KU,y,[E,KR,x,[M]] || T],X：對消息M雙重加密：首先用X的私有密鑰KRx，然后用Y的公開,,密鑰KUy。形成一個簽名的、保密的消息。然后將該信息以及,,X的標(biāo)識符一起用KRx簽名后與IDx 一起發(fā)送給A。這種內(nèi)部、,,雙重加密的消息對A以及對除Y以外的其它人都是平安的。,,A：檢查X的公開/私有密鑰對是否仍然有效，是，那么確認(rèn)消息。并,,將包含IDx、雙重加密的消息和時間戳構(gòu)成的 消息用KRa簽名后,,發(fā)送給Y。,本模式比上述兩個模式具有以下好處：,,1、在通信之前各方之間無須共享任

66、何信息，從而防止了聯(lián)手作弊；,,2、即使KRx 暴露，只要KRa 未暴露，不會有錯誤標(biāo)定日期的消息,,被發(fā)送；,,3、從X發(fā)送給Y的消息的內(nèi)容對A和任何其他人是保密的。,,數(shù)字簽名算法,,普通數(shù)字簽名算法,,RSA,,EIGamal,,DSS/DSA,,不可否認(rèn)的數(shù)字簽名算法,,群簽名算法,,盲簽名算法,,RSA簽名方案,,,RSA簽名,A,的公鑰私鑰對{,KU,a,||,KR,a,},,A,對消息,M,簽名:,S,A,=,E,KRa,(M),,問題:,,速度慢,,信息量大,,第三方仲裁時必須暴露明文信息,,漏洞:,E,KRa,(x,?,y),?,E,KRa,(x),?,E,KRa,(y) mod n,,先做摘要:,H,M,= hash(M),,再對,H,M,簽名,S,A,=,E,KRa,(H,M,),,hash,函數(shù)的無碰撞性保證了簽名的有效性,,簽名與加密,簽名提供真實性(authentication),,加密提供保密性(confidentiality),,“簽名+加密〞提供“真實性+保密性〞,,兩種實現(xiàn)方式: (A?B),,?先簽名,后加密: EKUb{M||SigA(M)},,