密碼學(xué)基礎(chǔ)介紹

1、密碼學(xué)基礎(chǔ)介紹目目 錄錄消息鑒別與散列函數(shù)消息鑒別與散列函數(shù)散列算法散列算法1.數(shù)字簽名數(shù)字簽名 網(wǎng)絡(luò)通信的攻擊威網(wǎng)絡(luò)通信的攻擊威脅脅泄露：把消息內(nèi)容發(fā)布給任何人或沒(méi)有合法密鑰的進(jìn)程泄露：把消息內(nèi)容發(fā)布給任何人或沒(méi)有合法密鑰的進(jìn)程流量分析：發(fā)現(xiàn)通信雙方之間信息流的結(jié)構(gòu)模式，可以用來(lái)確流量分析：發(fā)現(xiàn)通信雙方之間信息流的結(jié)構(gòu)模式，可以用來(lái)確定連接的頻率、持續(xù)時(shí)間長(zhǎng)度；還可以發(fā)現(xiàn)報(bào)文數(shù)量和長(zhǎng)度等定連接的頻率、持續(xù)時(shí)間長(zhǎng)度；還可以發(fā)現(xiàn)報(bào)文數(shù)量和長(zhǎng)度等偽裝：從一個(gè)假冒信息源向網(wǎng)絡(luò)中插入消息偽裝：從一個(gè)假冒信息源向網(wǎng)絡(luò)中插入消息內(nèi)容篡改：消息內(nèi)容被插入、刪除、變換、修改內(nèi)容篡改：消息內(nèi)容被插入、刪除、變換

2、、修改順序修改：插入、刪除或重組消息序列順序修改：插入、刪除或重組消息序列時(shí)間修改：消息延遲或重放時(shí)間修改：消息延遲或重放否認(rèn)：接受者否認(rèn)收到消息；發(fā)送者否認(rèn)發(fā)送過(guò)消息否認(rèn)：接受者否認(rèn)收到消息；發(fā)送者否認(rèn)發(fā)送過(guò)消息鑒別和認(rèn)證鑒別和認(rèn)證鑒別：鑒別：authentication 真?zhèn)涡哉鎮(zhèn)涡?(1) A process used to verify the integrity of transmitted data, especially a message 用來(lái)驗(yàn)證發(fā)送的數(shù)據(jù),特別是一個(gè)信息的完整性的過(guò)程 (2) The act of establishing the identity of u

3、sers when they start to use the system 在用戶(hù)開(kāi)始使用系統(tǒng)時(shí)對(duì)其身份進(jìn)行的確認(rèn)認(rèn)證：認(rèn)證：Certification 資格審查資格審查 In computer security, the technical evaluation made as part of and in support of the accreditation process, that established the extent to which a particular computer system or network design and implementation me

4、et prespecified security requirements 計(jì)算安全學(xué)用語(yǔ),指為了鑒定一個(gè)計(jì)算機(jī)系統(tǒng)或網(wǎng)絡(luò)的設(shè)計(jì)和它提供的手段在多大程度上能滿(mǎn)足預(yù)定的安全要求而進(jìn)行的技術(shù)評(píng)估鑒別的結(jié)構(gòu)鑒別的結(jié)構(gòu)任何消息認(rèn)證或數(shù)字簽名機(jī)制可以看到兩個(gè)層次：任何消息認(rèn)證或數(shù)字簽名機(jī)制可以看到兩個(gè)層次：底層必須有某種函數(shù)產(chǎn)生一個(gè)認(rèn)證標(biāo)識(shí)：一個(gè)用底層必須有某種函數(shù)產(chǎn)生一個(gè)認(rèn)證標(biāo)識(shí)：一個(gè)用于認(rèn)證一個(gè)報(bào)文的值于認(rèn)證一個(gè)報(bào)文的值高層認(rèn)證協(xié)議以底層函數(shù)為原語(yǔ)，使接收者完成高層認(rèn)證協(xié)議以底層函數(shù)為原語(yǔ)，使接收者完成報(bào)文的鑒別報(bào)文的鑒別鑒別的目的鑒別的目的信源識(shí)別：驗(yàn)證信息的發(fā)送者是真正的，而不是信源識(shí)別：驗(yàn)證信

5、息的發(fā)送者是真正的，而不是冒充的冒充的驗(yàn)證信息的完整性，在傳送或存儲(chǔ)過(guò)程中未被篡驗(yàn)證信息的完整性，在傳送或存儲(chǔ)過(guò)程中未被篡改，重放或延遲等改，重放或延遲等鑒別模型鑒別模型鑒別系統(tǒng)的組成鑒別系統(tǒng)的組成鑒別編碼器和鑒別譯碼器可抽象為鑒別函數(shù)鑒別編碼器和鑒別譯碼器可抽象為鑒別函數(shù)一個(gè)安全的鑒別系統(tǒng)，需滿(mǎn)足一個(gè)安全的鑒別系統(tǒng)，需滿(mǎn)足（1）指定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性、真實(shí)性和完）指定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性、真實(shí)性和完整性整性（2）消息的發(fā)送者和接收者不能抵賴(lài)）消息的發(fā)送者和接收者不能抵賴(lài)（3）除了合法的消息發(fā)送者，其它人不能偽造合法的消息）除了合法的消息發(fā)送者，其它人不能偽造合法

6、的消息鑒別函數(shù)分類(lèi)鑒別函數(shù)分類(lèi)消息加密：整個(gè)消息的密文作為認(rèn)證標(biāo)識(shí)消息加密：整個(gè)消息的密文作為認(rèn)證標(biāo)識(shí)消息鑒別碼消息鑒別碼(MAC)：公開(kāi)函數(shù)：公開(kāi)函數(shù)+密鑰產(chǎn)生一個(gè)固密鑰產(chǎn)生一個(gè)固定長(zhǎng)度的值作為認(rèn)證標(biāo)識(shí)定長(zhǎng)度的值作為認(rèn)證標(biāo)識(shí)散列函數(shù)：一個(gè)公開(kāi)函數(shù)將任意長(zhǎng)度的消息映射散列函數(shù)：一個(gè)公開(kāi)函數(shù)將任意長(zhǎng)度的消息映射到一個(gè)固定長(zhǎng)度的哈希值，作為認(rèn)證標(biāo)識(shí)到一個(gè)固定長(zhǎng)度的哈希值，作為認(rèn)證標(biāo)識(shí)鑒別函數(shù)分類(lèi)鑒別函數(shù)分類(lèi)消息加密：整個(gè)消息的密文作為認(rèn)證標(biāo)識(shí)消息加密：整個(gè)消息的密文作為認(rèn)證標(biāo)識(shí)消息鑒別碼消息鑒別碼(MAC)：公開(kāi)函數(shù)：公開(kāi)函數(shù)+密鑰產(chǎn)生一個(gè)固密鑰產(chǎn)生一個(gè)固定長(zhǎng)度的值作為認(rèn)證標(biāo)識(shí)定長(zhǎng)度的值作為認(rèn)證標(biāo)

7、識(shí)散列函數(shù)：一個(gè)公開(kāi)函數(shù)將任意長(zhǎng)度的消息映射散列函數(shù)：一個(gè)公開(kāi)函數(shù)將任意長(zhǎng)度的消息映射到一個(gè)固定長(zhǎng)度的哈希值，作為認(rèn)證標(biāo)識(shí)到一個(gè)固定長(zhǎng)度的哈希值，作為認(rèn)證標(biāo)識(shí)消息加密消息加密對(duì)稱(chēng)加密保密和鑒別對(duì)稱(chēng)加密保密和鑒別AB:():()kkABkA E MBB D MM與 共享密鑰，查看是否為有意義的明文對(duì)稱(chēng)加密保密和鑒別對(duì)稱(chēng)加密保密和鑒別A 提 供 保 密 僅 A 和 B 共 享 k 提 供 一 定 程 度 的 鑒 別 僅 來(lái) 自 傳 輸 中 不 會(huì) 被 更 改 需 要 某 種 結(jié) 構(gòu) 和 冗 余 不 提 供 簽 名 接 收 人 可 以 偽 造 報(bào) 文 發(fā) 送 人 可 以 偽 造 報(bào) 文明文明文M的自

8、動(dòng)確定的自動(dòng)確定M定義為有意義的明文序列，便于自動(dòng)識(shí)別定義為有意義的明文序列，便于自動(dòng)識(shí)別強(qiáng)制定義明文的某種結(jié)構(gòu)，這種結(jié)構(gòu)是易于識(shí)別但又強(qiáng)制定義明文的某種結(jié)構(gòu)，這種結(jié)構(gòu)是易于識(shí)別但又不能復(fù)制且無(wú)需借助加密的不能復(fù)制且無(wú)需借助加密的可以在加密前對(duì)每個(gè)報(bào)文附加檢錯(cuò)碼，即所謂的幀檢可以在加密前對(duì)每個(gè)報(bào)文附加檢錯(cuò)碼，即所謂的幀檢驗(yàn)序列號(hào)或檢驗(yàn)和驗(yàn)序列號(hào)或檢驗(yàn)和FCS內(nèi)部差錯(cuò)控制和外部差錯(cuò)控制內(nèi)部差錯(cuò)控制和外部差錯(cuò)控制差錯(cuò)控制差錯(cuò)控制更難于構(gòu)造更難于構(gòu)造公鑰加密保密性公鑰加密保密性ABbKUb 提供保密 僅B有KR 能解密 不提供鑒別 任何一方均可以使用加密報(bào)文而假稱(chēng)它是發(fā)自A的公鑰加密鑒別和簽名公鑰加

9、密鑒別和簽名ABaAa 提 供 鑒 別 和 簽 名 僅有 KR 可 進(jìn) 行 加 密 傳 輸 中 不 會(huì) 被 更 改 需 要 某 種 結(jié) 構(gòu) 或 冗 余 任 何 一 方 均 能 使 用 KU 驗(yàn) 證 簽 名公鑰加密保密、鑒別和簽名公鑰加密保密、鑒別和簽名ABab KR 提供鑒別和簽名 KU 可提供保密性消息鑒別碼消息鑒別碼MAC消息鑒別碼消息鑒別碼使用一個(gè)密鑰生成一個(gè)固定大小的小數(shù)據(jù)塊，并加入到消息中，使用一個(gè)密鑰生成一個(gè)固定大小的小數(shù)據(jù)塊，并加入到消息中，稱(chēng)稱(chēng)MAC， 或密碼校驗(yàn)和（或密碼校驗(yàn)和（cryptographic checksum） 1、接收者可以確信消息接收者可以確信消息M未被改變

10、未被改變 2、接收者可以確信消息來(lái)自所聲稱(chēng)的發(fā)送者、接收者可以確信消息來(lái)自所聲稱(chēng)的發(fā)送者 3、如果消息中包含順序碼（如、如果消息中包含順序碼（如HDLC,X.25,TCP），則接收者），則接收者可以保證消息的正常順序可以保證消息的正常順序MACMAC函數(shù)類(lèi)似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比函數(shù)類(lèi)似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比加密算法被攻擊的弱點(diǎn)要少加密算法被攻擊的弱點(diǎn)要少消息鑒別消息鑒別ABkkMACC (M) kABMAB:MC (M)；為和 共享的密鑰，為明文 提供鑒別 僅A和B共享密鑰k 消息鑒別與保密，鑒別與明文連接消息鑒別與保密，鑒別與明文連接ABk 2k 1

11、AB : E MC( M ) 12 提 供 鑒 別 僅 A 和 B 共 享 密 鑰 k 提 供 保 密 僅 A 和 B 共 享 密 鑰 k 消息鑒別與保密，鑒別與密文連接消息鑒別與保密，鑒別與密文連接ABk 2k 1k 2AB :EMC(E(M )12 提 供 鑒 別 僅 A 和 B 共 享 密 鑰 k 提 供 保 密 僅 A 和 B 共 享 密 鑰 k 消息鑒別消息鑒別 VS 常規(guī)加密常規(guī)加密保密性與真實(shí)性是兩個(gè)不同的概念保密性與真實(shí)性是兩個(gè)不同的概念根本上根本上,信息加密提供的是保密性而非真實(shí)性信息加密提供的是保密性而非真實(shí)性加密代價(jià)大加密代價(jià)大(公鑰算法代價(jià)更大公鑰算法代價(jià)更大)鑒別函數(shù)

12、與保密函數(shù)的分離能提供功能上的靈活性鑒別函數(shù)與保密函數(shù)的分離能提供功能上的靈活性某些信息只需要真實(shí)性某些信息只需要真實(shí)性,不需要保密性不需要保密性 廣播的信息難以使用加密廣播的信息難以使用加密(信息量大信息量大) 網(wǎng)絡(luò)管理信息等只需要真實(shí)性網(wǎng)絡(luò)管理信息等只需要真實(shí)性 政府政府/權(quán)威部門(mén)的公告權(quán)威部門(mén)的公告散列函數(shù)散列函數(shù)Hash Function散列函數(shù)散列函數(shù)H(M): 輸入為任意長(zhǎng)度的消息輸入為任意長(zhǎng)度的消息M; 輸出為一個(gè)固定長(zhǎng)度輸出為一個(gè)固定長(zhǎng)度的散列值，稱(chēng)為消息摘要的散列值，稱(chēng)為消息摘要( (MessageDigest）H(M)是消息是消息M的所有位的函數(shù)并提供錯(cuò)誤檢測(cè)能力：的所有位

13、的函數(shù)并提供錯(cuò)誤檢測(cè)能力：消息中的任何一位或多位的變化都將導(dǎo)致該散列值的消息中的任何一位或多位的變化都將導(dǎo)致該散列值的變化變化H(M)又稱(chēng)為：哈希函數(shù)、數(shù)字指紋（又稱(chēng)為：哈希函數(shù)、數(shù)字指紋（Digital finger print)、壓縮（、壓縮（Compression)函數(shù)、數(shù)據(jù)鑒別碼函數(shù)、數(shù)據(jù)鑒別碼（Dataauthentication code）等）等散列函數(shù)基本用法散列函數(shù)基本用法(1)kAB :EMH (M ) 提 供 鑒 別 加 密 保 護(hù) H ( M ) 提 供 保 密 僅 A 和 B 共 享 密 鑰 k 散列函數(shù)基本用法散列函數(shù)基本用法(2)kAB:ME H(M) 提供鑒別 加

14、密保護(hù)H(M)散列函數(shù)基本用法散列函數(shù)基本用法(3)aKR 提供鑒別和數(shù)字簽名 加密保護(hù)H(M) 僅A能生成E H(M)散列函數(shù)基本用法散列函數(shù)基本用法(4)akKRAB:E MEH(M ) 提 供 鑒 別 和 數(shù) 字 簽 名 提 供 保 密 僅 A和 B共 享 密 鑰 k 散列函數(shù)基本用法散列函數(shù)基本用法(5)AB: MH(MS) 提供鑒別 僅A和B共享消息S 散列函數(shù)基本用法散列函數(shù)基本用法(6)kAB : EMH (MS ) 提 供 鑒 別 僅 A 和 B 共 享 S 提 供 保 密 僅 A 和 B 共 享 密 鑰 k 消息鑒別碼消息鑒別碼MACMKMAC函數(shù)域：任意長(zhǎng)度的報(bào)文函數(shù)域：任

15、意長(zhǎng)度的報(bào)文值域：所有可能的值域：所有可能的MAC和所有可能的密鑰和所有可能的密鑰MAC一般為多對(duì)一函數(shù)一般為多對(duì)一函數(shù)函數(shù)域：任意長(zhǎng)度的報(bào)文函數(shù)域：任意長(zhǎng)度的報(bào)文值域：所有可能的值域：所有可能的MAC和所有可能的密鑰和所有可能的密鑰假設(shè)假設(shè)假設(shè)攻擊者使用強(qiáng)行攻擊，且已經(jīng)獲得報(bào)文的明文和相應(yīng)的假設(shè)攻擊者使用強(qiáng)行攻擊，且已經(jīng)獲得報(bào)文的明文和相應(yīng)的MAC,MAC,即即 222nnkMACnMACNNk長(zhǎng)度為 比特個(gè)可能的個(gè)報(bào)文，其中密鑰的長(zhǎng)度為個(gè)可能的密鑰對(duì)對(duì)MAC的強(qiáng)行攻擊的強(qiáng)行攻擊11(,)M MAC假設(shè)假設(shè)假設(shè)攻擊者已經(jīng)獲得報(bào)文的明文和相應(yīng)的假設(shè)攻擊者已經(jīng)獲得報(bào)文的明文和相應(yīng)的MAC,MAC

16、,即即 假設(shè)假設(shè) 222nnkMACnMACNNk長(zhǎng)度為 比特個(gè)可能的個(gè)報(bào)文，其中密鑰的長(zhǎng)度為個(gè)可能的密鑰對(duì)對(duì)MAC的強(qiáng)行攻擊的強(qiáng)行攻擊11(,)M MACkn對(duì)對(duì)MAC的強(qiáng)行攻擊的強(qiáng)行攻擊11111,()(),ikkMMACCMMACCMk(k-n)第1輪 給定： for i=1 to 2 : 試探 匹配數(shù)2無(wú)法確定真正的密鑰k22222,()(),ikkMMACCMMACCM(k-n)(k-2 n)第2輪 給定： for i=1 to 2: 試探 匹配數(shù)2無(wú)法確定真正的密鑰kka na 若，則需要進(jìn)行 輪，比尋找等長(zhǎng)度的解密密鑰強(qiáng)度還高對(duì)對(duì)MAC的強(qiáng)行攻擊的強(qiáng)行攻擊如果如果 knkn，則第

17、一輪就可以產(chǎn)生一個(gè)唯一對(duì)應(yīng)。仍然可，則第一輪就可以產(chǎn)生一個(gè)唯一對(duì)應(yīng)。仍然可以有多于一個(gè)以有多于一個(gè)keykey產(chǎn)生這一配對(duì)，這時(shí)攻擊者只需對(duì)一個(gè)新產(chǎn)生這一配對(duì)，這時(shí)攻擊者只需對(duì)一個(gè)新的的(message, MAC)(message, MAC)進(jìn)行相同的測(cè)試進(jìn)行相同的測(cè)試由此可見(jiàn)，強(qiáng)力攻擊企圖發(fā)現(xiàn)由此可見(jiàn)，強(qiáng)力攻擊企圖發(fā)現(xiàn)authentication keyauthentication key不小于不小于甚至大于對(duì)同樣長(zhǎng)度的解密甚至大于對(duì)同樣長(zhǎng)度的解密keykey的攻擊的攻擊對(duì)對(duì)MAC的其它攻擊的其它攻擊設(shè)設(shè)M = (X1 | X2 | | Xm) 是一個(gè)由是一個(gè)由64位位Xi數(shù)據(jù)塊連接而成數(shù)據(jù)

18、塊連接而成 定義定義 (M) = X1 X2 . Xm CK(M) = EK (M) 其中其中 為異或操作；為異或操作；E為為 ECB工作模式的工作模式的DES算法算法則則Key length = 56 bitMAC length = 64 bit強(qiáng)力攻擊需要至少?gòu)?qiáng)力攻擊需要至少256次加密來(lái)決定次加密來(lái)決定K對(duì)對(duì)MAC的其它攻擊的其它攻擊設(shè)設(shè)M = ( Y1 | Y2 | | Ym-1 | Ym) 其中其中 Y1, Y2, , Ym-1是替換是替換 X1, X2,Xm-1的任意值，而的任意值，而 Ym = Y1 Y2 , , Ym-1 (M) 則則 CK(M) = EK (M) = EKY1

19、 Y2 , , Ym-1 Ym = EKY1 Y2 , , Ym-1 (Y1 Y2 , , Ym-1 (M) = EK (M)這時(shí)消息這時(shí)消息M 和和 MAC= CK(M) = EK (M)是一對(duì)可被接收者認(rèn)證的消息是一對(duì)可被接收者認(rèn)證的消息用此方法，任何長(zhǎng)度為用此方法，任何長(zhǎng)度為64 (m-1)位的消息可以被插入任意的欺騙性位的消息可以被插入任意的欺騙性信息信息MAC應(yīng)具備的性質(zhì)應(yīng)具備的性質(zhì) 如果一個(gè)攻擊者得到如果一個(gè)攻擊者得到M和和CK(M)，則攻擊者構(gòu)造一個(gè)消息，則攻擊者構(gòu)造一個(gè)消息M使使得得CK(M)=CK(M)應(yīng)具有計(jì)算復(fù)雜性意義下的不可行性應(yīng)具有計(jì)算復(fù)雜性意義下的不可行性 CK(M

20、)應(yīng)均勻分布，即：隨機(jī)選擇消息應(yīng)均勻分布，即：隨機(jī)選擇消息M和和M， CK(M)= CK(M)的概率是的概率是2-n，其中，其中n是是MAC的位數(shù)的位數(shù) 令令M為為M的某些變換，即：的某些變換，即：M=f(M)，（例如：，（例如：f可以涉及可以涉及M中中一個(gè)或多個(gè)給定位的反轉(zhuǎn)），在這種情況下，一個(gè)或多個(gè)給定位的反轉(zhuǎn)），在這種情況下，PrCK(M)= CK(M) = 2-n基于基于DES的報(bào)文鑒別碼的報(bào)文鑒別碼基于基于DES的報(bào)文鑒別碼的報(bào)文鑒別碼算法來(lái)源算法來(lái)源FIPS publication (FIPS PUB 113)ANSI standard (X9.17)使用使用CBC(Cipher

21、Block Chaining)方式，初始向方式，初始向量為量為IV=0基于基于DES的報(bào)文鑒別碼的報(bào)文鑒別碼算法來(lái)源算法來(lái)源FIPS publication (FIPS PUB 113)ANSI standard (X9.17)使用使用CBC(Cipher Block Chaining)方式，初始向方式，初始向量為量為IV=0基于基于DES的報(bào)文鑒別碼的報(bào)文鑒別碼將數(shù)據(jù)按將數(shù)據(jù)按64位分組，位分組，D1, D2, , DN，必要時(shí)最后一個(gè)數(shù)據(jù)塊用，必要時(shí)最后一個(gè)數(shù)據(jù)塊用0向右填向右填充充運(yùn)用運(yùn)用DES算法算法E，密鑰，密鑰K數(shù)據(jù)認(rèn)證碼數(shù)據(jù)認(rèn)證碼(DAC)的計(jì)算如下：的計(jì)算如下：O1 = EK(

22、D1)O2 = EK(D2O1)O3 = EK(D3O2)ON = EK(DNON-1)FIPS PUB 113目目 錄錄消息鑒別與散列函數(shù)消息鑒別與散列函數(shù)散列算法散列算法1.數(shù)字簽名數(shù)字簽名散列函數(shù)散列函數(shù)散列函數(shù)的定義散列函數(shù)的定義散列函數(shù)：散列函數(shù)：M:變長(zhǎng)報(bào)文變長(zhǎng)報(bào)文H(M):定長(zhǎng)的散列值定長(zhǎng)的散列值主要用于為文件、報(bào)文或其它分組數(shù)據(jù)產(chǎn)生指紋主要用于為文件、報(bào)文或其它分組數(shù)據(jù)產(chǎn)生指紋()hH M散列函數(shù)的要求散列函數(shù)的要求H能用于任意大小的分組能用于任意大小的分組H能產(chǎn)生定長(zhǎng)的輸出能產(chǎn)生定長(zhǎng)的輸出對(duì)任何給定的對(duì)任何給定的x，H(x)要相對(duì)易于計(jì)算，使得硬件和軟件實(shí)現(xiàn)成為實(shí)際要相對(duì)易于

23、計(jì)算，使得硬件和軟件實(shí)現(xiàn)成為實(shí)際可能可能對(duì)任何給定的碼對(duì)任何給定的碼h，尋找，尋找x使得使得H(x)=h在計(jì)算上是不可行的，即單向性在計(jì)算上是不可行的，即單向性對(duì)任何給定的分組對(duì)任何給定的分組x，尋找不等于，尋找不等于x的的y，使得，使得H(x)=H(y)在計(jì)算上是不在計(jì)算上是不可行的，即弱抗沖突性可行的，即弱抗沖突性尋找對(duì)任何的尋找對(duì)任何的(x,y)對(duì)使得對(duì)使得H(x)=H(y)在計(jì)算上是不可行的，即強(qiáng)抗沖突在計(jì)算上是不可行的，即強(qiáng)抗沖突性性Hash vs MACMAC需要對(duì)全部數(shù)據(jù)進(jìn)行加需要對(duì)全部數(shù)據(jù)進(jìn)行加MAC速度慢速度慢Hash是一種直接產(chǎn)生鑒別碼的方法是一種直接產(chǎn)生鑒別碼的方法Has

24、h函數(shù)通用結(jié)構(gòu)函數(shù)通用結(jié)構(gòu)由由Ron Rivest于于1990年提出年提出MD4幾乎被所有幾乎被所有hash函數(shù)使用函數(shù)使用具體做法具體做法: 把原始消息把原始消息M分成一些固定長(zhǎng)度的塊分成一些固定長(zhǎng)度的塊Yi 最后一塊最后一塊padding并使其包含消息并使其包含消息M長(zhǎng)度長(zhǎng)度 設(shè)定初始值設(shè)定初始值CV0 壓縮函數(shù)壓縮函數(shù)f, CVi=f(CVi-1,Yi-1) 最后一個(gè)最后一個(gè)CVi為為hash值值MD5MD5描述描述Merkle于于1989年提出年提出hash function模型模型Ron Rivest于于1990年提出年提出MD41992年年, Ron Rivest 完成完成MD5

25、(RFC 1321) 在最近數(shù)年之前在最近數(shù)年之前,MD5是最主要的是最主要的hash算法算法現(xiàn)行美國(guó)標(biāo)準(zhǔn)現(xiàn)行美國(guó)標(biāo)準(zhǔn)SHA-1以以MD5的前身的前身MD4為基礎(chǔ)為基礎(chǔ)MD5描述描述 輸入：任意長(zhǎng)度的報(bào)文輸入：任意長(zhǎng)度的報(bào)文輸入分組長(zhǎng)度：輸入分組長(zhǎng)度：512 bit 輸出：輸出：128 bit 報(bào)文報(bào)文MD5描述描述step 1 附加長(zhǎng)度值附加長(zhǎng)度值對(duì)報(bào)文進(jìn)行填充，使其比特?cái)?shù)與對(duì)報(bào)文進(jìn)行填充，使其比特?cái)?shù)與448模模512同余，即填同余，即填充長(zhǎng)度為充長(zhǎng)度為512的整數(shù)倍減去的整數(shù)倍減去64填充方法：填充比特串的最高位為填充方法：填充比特串的最高位為1，其余各位均為，其余各位均為011| 448

26、mod512| 448mod512,| | 512MifMthen MMMD5描述描述step 2 附加長(zhǎng)度值附加長(zhǎng)度值|M2|為為512的倍數(shù)的倍數(shù): Y0,Y1,YL-1216464|mod2 ,2MMLengthMMPadding LengthLengthM低位字節(jié)優(yōu)先,表示為64bit長(zhǎng)若初始長(zhǎng)度大于，僅使用該長(zhǎng)度的低64bitMD5描述描述step 3初始化初始化MD緩存緩存MD為為128bit，用于存放散列函數(shù)的中間及最終結(jié)果，用于存放散列函數(shù)的中間及最終結(jié)果MD可表示為可表示為4個(gè)個(gè)32bit的寄存器的寄存器(A,B,C,D)，初始化如下：，初始化如下：MD5描述描述step 4

27、壓縮：壓縮：4個(gè)循環(huán)的壓縮算法個(gè)循環(huán)的壓縮算法MD5描述描述step 5輸出輸出HMD5單個(gè)單個(gè)512bit分組的分組的MD5處理過(guò)程處理過(guò)程(MD5壓縮函數(shù)）壓縮函數(shù)）當(dāng)前正在處當(dāng)前正在處理的理的512比特分組比特分組128bit的緩存值的緩存值更新緩存更新緩存T0,16432(2(sin( ),0(sin( )13232iiTINTabsiiabsiTbitbit的單位為弧度能用表示，提供了隨機(jī)化的模式，消除了規(guī)律性每步操作形式每步操作形式單個(gè)單個(gè)512bit分組的分組的MD5處理過(guò)程處理過(guò)程(MD5壓縮函數(shù)）壓縮函數(shù)）116( )(15 ) mod16( )(53 ) mod16( )5

28、 mod16iiiiiii234X0.15:保存當(dāng)前保存當(dāng)前512bit待處理輸入分組的值待處理輸入分組的值Xk = Mq16 + k = 在第在第q個(gè)個(gè)512位數(shù)據(jù)塊中的第位數(shù)據(jù)塊中的第k個(gè)個(gè)32位字位字每次循環(huán)每次循環(huán)(4)的每步的每步(16)內(nèi)，內(nèi)，Xi的使用循序各不相同的使用循序各不相同MD5的安全性的安全性Berson表明，對(duì)單循環(huán)表明，對(duì)單循環(huán)MD5，使用不用的密碼分析可能在合理的時(shí)，使用不用的密碼分析可能在合理的時(shí)間內(nèi)找出能夠產(chǎn)生相同摘要的兩個(gè)報(bào)文，這個(gè)結(jié)果被證明對(duì)四個(gè)循間內(nèi)找出能夠產(chǎn)生相同摘要的兩個(gè)報(bào)文，這個(gè)結(jié)果被證明對(duì)四個(gè)循環(huán)中的任意一個(gè)循環(huán)也成立，但作者沒(méi)有能夠提出如何攻擊

29、包含全環(huán)中的任意一個(gè)循環(huán)也成立，但作者沒(méi)有能夠提出如何攻擊包含全部部4個(gè)循環(huán)個(gè)循環(huán)MD5的攻擊的攻擊Boer和和Bosselaers顯示了即使緩存顯示了即使緩存ABCD不同，不同，MD5對(duì)單個(gè)對(duì)單個(gè)512bit分分組的執(zhí)行將得到相同的輸出組的執(zhí)行將得到相同的輸出(偽沖突）偽沖突）Dobbertin的攻擊技術(shù)：使的攻擊技術(shù)：使MD5的壓縮函數(shù)產(chǎn)生沖突，即尋找的壓縮函數(shù)產(chǎn)生沖突，即尋找MD5被認(rèn)為是易受攻擊的，逐漸被被認(rèn)為是易受攻擊的，逐漸被SHA-1和和RIPEMD-160替代替代,( )( )xy xyH xH y、但其它常用其它常用Hash算法算法SHA-1 RIPEMD-160 HMACH

30、ash小結(jié)小結(jié)Hash函數(shù)把變長(zhǎng)信息映射到定長(zhǎng)信息函數(shù)把變長(zhǎng)信息映射到定長(zhǎng)信息Hash函數(shù)不具備可逆性函數(shù)不具備可逆性Hash函數(shù)速度較快函數(shù)速度較快Hash函數(shù)與對(duì)稱(chēng)密鑰加密算法有某種相似性函數(shù)與對(duì)稱(chēng)密鑰加密算法有某種相似性對(duì)對(duì)Hash函數(shù)的密碼分析比對(duì)稱(chēng)密鑰密碼更困難函數(shù)的密碼分析比對(duì)稱(chēng)密鑰密碼更困難Hash函數(shù)可用于消息摘要函數(shù)可用于消息摘要Hash函數(shù)可用于數(shù)字簽名函數(shù)可用于數(shù)字簽名目目 錄錄消息鑒別與散列函數(shù)消息鑒別與散列函數(shù)散列算法散列算法1.數(shù)字簽名數(shù)字簽名報(bào)文鑒別的局限性報(bào)文鑒別的局限性用于保護(hù)通信雙方免受第三方攻擊用于保護(hù)通信雙方免受第三方攻擊無(wú)法防止通信雙方的相互攻擊無(wú)法防

31、止通信雙方的相互攻擊信宿方偽造報(bào)文信宿方偽造報(bào)文信源方否認(rèn)已發(fā)送的報(bào)文信源方否認(rèn)已發(fā)送的報(bào)文引入數(shù)字簽名，是筆跡簽名的模擬引入數(shù)字簽名，是筆跡簽名的模擬數(shù)字簽名的性質(zhì)數(shù)字簽名的性質(zhì)傳統(tǒng)簽名的基本特點(diǎn)傳統(tǒng)簽名的基本特點(diǎn) 能與被簽的文件在物理上不可分割能與被簽的文件在物理上不可分割 簽名者不能否認(rèn)自己的簽名簽名者不能否認(rèn)自己的簽名 簽名不能被偽造簽名不能被偽造 容易被驗(yàn)證容易被驗(yàn)證數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化 能與所簽文件能與所簽文件“綁定綁定” 簽名者不能否認(rèn)自己的簽名簽名者不能否認(rèn)自己的簽名 容易被自動(dòng)驗(yàn)證容易被自動(dòng)驗(yàn)證 簽名不能被偽造簽名不能被偽造數(shù)字簽名的性質(zhì)數(shù)字簽

32、名的性質(zhì)必須能夠驗(yàn)證作者及其簽名的日期時(shí)間必須能夠驗(yàn)證作者及其簽名的日期時(shí)間必須能夠認(rèn)證簽名時(shí)刻的內(nèi)容必須能夠認(rèn)證簽名時(shí)刻的內(nèi)容簽名必須能夠由第三方驗(yàn)證，以解決爭(zhēng)議簽名必須能夠由第三方驗(yàn)證，以解決爭(zhēng)議數(shù)字簽名的設(shè)計(jì)要求數(shù)字簽名的設(shè)計(jì)要求 簽名必須是依賴(lài)于被簽名信息的一個(gè)位串模板簽名必須是依賴(lài)于被簽名信息的一個(gè)位串模板 簽名必須使用某些對(duì)發(fā)送者是唯一的信息，以防止雙方的偽造與否簽名必須使用某些對(duì)發(fā)送者是唯一的信息，以防止雙方的偽造與否認(rèn)認(rèn) 必須相對(duì)容易生成該數(shù)字簽名必須相對(duì)容易生成該數(shù)字簽名 必須相對(duì)容易識(shí)別和驗(yàn)證該數(shù)字簽名必須相對(duì)容易識(shí)別和驗(yàn)證該數(shù)字簽名 偽造該數(shù)字簽名在計(jì)算復(fù)雜性意義上具有不

33、可行性，既包括對(duì)一個(gè)偽造該數(shù)字簽名在計(jì)算復(fù)雜性意義上具有不可行性，既包括對(duì)一個(gè)已有的數(shù)字簽名構(gòu)造新的消息，也包括對(duì)一個(gè)給定消息偽造一個(gè)數(shù)已有的數(shù)字簽名構(gòu)造新的消息，也包括對(duì)一個(gè)給定消息偽造一個(gè)數(shù)字簽名字簽名 在存儲(chǔ)器中保存一個(gè)數(shù)字簽名副本是現(xiàn)實(shí)可行的在存儲(chǔ)器中保存一個(gè)數(shù)字簽名副本是現(xiàn)實(shí)可行的數(shù)字簽名分類(lèi)數(shù)字簽名分類(lèi)簽名方式簽名方式直接數(shù)字簽名直接數(shù)字簽名direct digital signature仲裁數(shù)字簽名仲裁數(shù)字簽名arbitrated digital signature安全性安全性 無(wú)條件安全的數(shù)字簽名無(wú)條件安全的數(shù)字簽名 計(jì)算上安全的數(shù)字簽名計(jì)算上安全的數(shù)字簽名可簽名次數(shù)可簽名次數(shù)一次性的數(shù)字簽名一次性的數(shù)字簽名 多次性的數(shù)字簽名多次性的數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名的缺點(diǎn)直接數(shù)字簽名的缺點(diǎn)驗(yàn)證模式依賴(lài)于發(fā)送方的保密密鑰驗(yàn)證模式依賴(lài)于發(fā)送方的保密密鑰 發(fā)送方要抵賴(lài)發(fā)送某一消息時(shí)，可能會(huì)聲稱(chēng)其私有密鑰丟失或被竊，發(fā)送方要抵賴(lài)發(fā)送某一消息時(shí)，可能會(huì)聲稱(chēng)其私有密鑰丟失或被竊，從而他人偽造了他的簽名從而他人偽造了他的