網(wǎng)絡(luò)安全 介紹hash函數(shù)

1、 回顧與總結(jié)n對稱密碼算法運算速度快、密鑰短、多種用途（隨機數(shù)產(chǎn)生、Hash函數(shù)）、歷史悠久密鑰管理困難（分發(fā)、更換）n非對稱密碼算法只需保管私鑰、可以相當(dāng)長的時間保持不變、需要的數(shù)目較小運算速度慢、密鑰尺寸大、歷史短需要PKI網(wǎng)絡(luò)通信的攻擊威脅網(wǎng)絡(luò)通信的攻擊威脅泄露：把消息內(nèi)容發(fā)布給任何人或沒有合法密鑰的進程泄露：把消息內(nèi)容發(fā)布給任何人或沒有合法密鑰的進程流量分析：發(fā)現(xiàn)通信雙方之間信息流的結(jié)構(gòu)模式，可以用來確流量分析：發(fā)現(xiàn)通信雙方之間信息流的結(jié)構(gòu)模式，可以用來確定連接的頻率、持續(xù)時間長度；還可以發(fā)現(xiàn)報文數(shù)量和長度等定連接的頻率、持續(xù)時間長度；還可以發(fā)現(xiàn)報文數(shù)量和長度等偽裝：從一個假冒信息源向

2、網(wǎng)絡(luò)中插入消息偽裝：從一個假冒信息源向網(wǎng)絡(luò)中插入消息內(nèi)容篡改：消息內(nèi)容被插入、刪除、變換、修改內(nèi)容篡改：消息內(nèi)容被插入、刪除、變換、修改順序修改：插入、刪除或重組消息序列順序修改：插入、刪除或重組消息序列時間修改：消息延遲或重放時間修改：消息延遲或重放否認(rèn)：接受者否認(rèn)收到消息；發(fā)送者否認(rèn)發(fā)送過消息否認(rèn)：接受者否認(rèn)收到消息；發(fā)送者否認(rèn)發(fā)送過消息信息安全的需求n保密性（ Confidentiality）n完整性 （Integrity）n數(shù)據(jù)完整性，未被未授權(quán)篡改或者損壞n系統(tǒng)完整性，系統(tǒng)未被非授權(quán)操縱，按既定的功能運行n可用性 （Availability）n鑒別 （Authenticity）n實體

3、身份的鑒別，適用于用戶、進程、系統(tǒng)、信息等n不可否認(rèn)性 （ Non-repudiation）n防止源點或終點的抵賴n目目 錄錄1.消息鑒別與散列函數(shù)消息鑒別與散列函數(shù)2.散列算法散列算法3.數(shù)字簽名數(shù)字簽名定義n消息鑒別（Message Authentication)： 是一個證實收到的消息來自可信的源點且未被篡改的過程。n散列函數(shù)（ Hash Functions)： 一個散列函數(shù)以一個變長的報文作為輸入，并產(chǎn)生一個定長的散列碼，有時也稱報文摘要，作為輸出。n數(shù)字簽名（Digital Signature） 是一種防止源點或終點抵賴的鑒別技術(shù)。 鑒別和認(rèn)證鑒別和認(rèn)證鑒別鑒別：authentica

4、tion 真?zhèn)涡哉鎮(zhèn)涡?(1) 用來驗證發(fā)送的數(shù)據(jù),特別是一個信息的完整性的過程 (2) 在用戶開始使用系統(tǒng)時對其身份進行的確認(rèn)認(rèn)證：認(rèn)證：Certification 資格審查資格審查 計算安全學(xué)用語,指為了鑒定一個計算機系統(tǒng)或網(wǎng)絡(luò)的設(shè)計和它提供的手段在多大程度上能滿足預(yù)定的安全要求而進行的技術(shù)評估鑒別的結(jié)構(gòu)鑒別的結(jié)構(gòu)任何消息認(rèn)證或數(shù)字簽名機制可以看到兩個層次：任何消息認(rèn)證或數(shù)字簽名機制可以看到兩個層次：底層底層必須有某種函數(shù)產(chǎn)生一個認(rèn)證標(biāo)識：一個必須有某種函數(shù)產(chǎn)生一個認(rèn)證標(biāo)識：一個用于認(rèn)證一個報文的值用于認(rèn)證一個報文的值高層高層認(rèn)證協(xié)議以底層函數(shù)為原語，使接收者完認(rèn)證協(xié)議以底層函數(shù)為原語，使

5、接收者完成報文的鑒別成報文的鑒別鑒別的目的鑒別的目的信源識別：驗證信息的發(fā)送者是真正的，而不信源識別：驗證信息的發(fā)送者是真正的，而不是冒充的是冒充的驗證信息的完整性，在傳送或存儲過程中未被驗證信息的完整性，在傳送或存儲過程中未被篡改，重放或延遲等篡改，重放或延遲等鑒別模型鑒別模型鑒別系統(tǒng)的組成鑒別系統(tǒng)的組成鑒別編碼器和鑒別譯碼器可抽象為鑒別函數(shù)鑒別編碼器和鑒別譯碼器可抽象為鑒別函數(shù)一個安全的鑒別系統(tǒng)，需滿足一個安全的鑒別系統(tǒng)，需滿足（1）指定的接收者能夠檢驗和證實消息的合法性、真實性和完）指定的接收者能夠檢驗和證實消息的合法性、真實性和完整性整性（2）消息的發(fā)送者和接收者不能抵賴）消息的發(fā)送者

6、和接收者不能抵賴（3）除了合法的消息發(fā)送者，其它人不能偽造合法的消息）除了合法的消息發(fā)送者，其它人不能偽造合法的消息鑒別函數(shù)分類鑒別函數(shù)分類消息加密消息加密：整個消息的密文作為認(rèn)證標(biāo)識：整個消息的密文作為認(rèn)證標(biāo)識消息鑒別碼消息鑒別碼(MAC)：公開函數(shù)：公開函數(shù)+密鑰產(chǎn)生一個密鑰產(chǎn)生一個固定長度的值作為認(rèn)證標(biāo)識固定長度的值作為認(rèn)證標(biāo)識散列函數(shù)：一個公開函數(shù)將任意長度的消息映散列函數(shù)：一個公開函數(shù)將任意長度的消息映射到一個固定長度的哈希值，作為認(rèn)證標(biāo)識射到一個固定長度的哈希值，作為認(rèn)證標(biāo)識簽名函數(shù)分類簽名函數(shù)分類 （1）消息加密）消息加密對稱加密保密和鑒別對稱加密保密和鑒別AB:():()kkA

7、BkA E MBB D MM與 共享密鑰，查看是否為有意義的明文對稱加密保密和鑒別對稱加密保密和鑒別A 提 供 保 密 僅 A 和 B 共 享 k 提 供 一 定 程 度 的 鑒 別 僅 來 自 傳 輸 中 不 會 被 更 改 需 要 某 種 結(jié) 構(gòu) 和 冗 余 不 提 供 簽 名 接 收 人 可 以 偽 造 報 文 發(fā) 送 人 可 以 偽 造 報 文明文明文M的自動確定的自動確定M定義為有意義的明文序列，便于自動識別定義為有意義的明文序列，便于自動識別強制定義明文的某種結(jié)構(gòu)，這種結(jié)構(gòu)是易于識別但又強制定義明文的某種結(jié)構(gòu)，這種結(jié)構(gòu)是易于識別但又不能復(fù)制且無需借助加密的不能復(fù)制且無需借助加密的可

8、以在加密前對每個報文附加檢錯碼，即所謂的可以在加密前對每個報文附加檢錯碼，即所謂的幀檢幀檢驗序列號驗序列號或或檢驗和檢驗和FCS內(nèi)部差錯控制和外部差錯控制內(nèi)部差錯控制和外部差錯控制差錯控制差錯控制更難于構(gòu)造更難于構(gòu)造公鑰加密保密性公鑰加密保密性ABbKUb 提供保密 僅B有KR 能解密 不提供鑒別 任何一方均可以使用加密報文而假稱它是發(fā)自A的公鑰加密鑒別和簽名公鑰加密鑒別和簽名ABaAa 提 供 鑒 別 和 簽 名 僅有 KR 可 進 行 加 密 傳 輸 中 不 會 被 更 改 需 要 某 種 結(jié) 構(gòu) 或 冗 余 任 何 一 方 均 能 使 用 KU 驗 證 簽 名公鑰加密保密、鑒別和簽名公鑰

9、加密保密、鑒別和簽名ABab KR 提供鑒別和簽名 KU 可提供保密性（2）消息鑒別碼）消息鑒別碼MAC消息鑒別碼消息鑒別碼使用一個密鑰生成一個固定大小的小數(shù)據(jù)塊，并加入到消息中，使用一個密鑰生成一個固定大小的小數(shù)據(jù)塊，并加入到消息中，稱稱MAC， 或密碼校驗和（或密碼校驗和（cryptographic checksum） 1、接收者可以確信消息接收者可以確信消息M未被改變未被改變 2、接收者可以確信消息來自所聲稱的發(fā)送者、接收者可以確信消息來自所聲稱的發(fā)送者 3、如果消息中包含順序碼（如、如果消息中包含順序碼（如HDLC,X.25,TCP），則接收者），則接收者可以保證消息的正常順序可以保證

10、消息的正常順序MACMAC函數(shù)類似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比函數(shù)類似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比加密算法被攻擊的弱點要少加密算法被攻擊的弱點要少MKMAC函數(shù)域：任意長度的報文函數(shù)域：任意長度的報文值域：所有可能的值域：所有可能的MAC和所有可能的密鑰和所有可能的密鑰MAC一般為多對一函數(shù)一般為多對一函數(shù)消息鑒別消息鑒別ABkkMACC (M) kABMAB:MC (M)；為和 共享的密鑰，為明文 提供鑒別 僅A和B共享密鑰k 消息鑒別與保密，鑒別與明文連接消息鑒別與保密，鑒別與明文連接ABk 2k 1AB : E MC( M ) 12 提 供 鑒 別 僅 A 和

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

12、提供功能上的靈活性某些信息只需要真實性某些信息只需要真實性,不需要保密性不需要保密性 廣播的信息難以使用加密廣播的信息難以使用加密(信息量大信息量大) 網(wǎng)絡(luò)管理信息等只需要真實性網(wǎng)絡(luò)管理信息等只需要真實性 政府政府/權(quán)威部門的公告權(quán)威部門的公告函數(shù)域：任意長度的報文函數(shù)域：任意長度的報文值域：所有可能的值域：所有可能的MAC和所有可能的密鑰和所有可能的密鑰假設(shè)假設(shè)假設(shè)攻擊者使用強行攻擊，且已經(jīng)獲得報文的明文和相應(yīng)的假設(shè)攻擊者使用強行攻擊，且已經(jīng)獲得報文的明文和相應(yīng)的MAC,MAC,即即 假設(shè)假設(shè) 222nnkMACnMACNNk長度為 比特個可能的個報文，其中密鑰的長度為個可能的密鑰對對MAC

13、的強行攻擊的強行攻擊11(,)M MACkn對對MAC的強行攻擊的強行攻擊11111,()(),ikkMMACCMMACCMk(k-n)第1輪 給定： for i=1 to 2 : 試探 匹配數(shù)2無法確定真正的密鑰k22222,()(),ikkMMACCMMACCM(k-n)(k-2 n)第2輪 給定： for i=1 to 2: 試探 匹配數(shù)2無法確定真正的密鑰kka na 若，則需要進行 輪，比尋找等長度的解密密鑰強度還高對對MAC的強行攻擊的強行攻擊如果如果 knkn，則第一輪就可以產(chǎn)生一個唯一對應(yīng)。仍然可，則第一輪就可以產(chǎn)生一個唯一對應(yīng)。仍然可以有多于一個以有多于一個keykey產(chǎn)生這

14、一配對，這時攻擊者只需對一個新產(chǎn)生這一配對，這時攻擊者只需對一個新的的(message, MAC)(message, MAC)進行相同的測試進行相同的測試由此可見，強力攻擊企圖發(fā)現(xiàn)由此可見，強力攻擊企圖發(fā)現(xiàn)authentication keyauthentication key不小于不小于甚至大于對同樣長度的解密甚至大于對同樣長度的解密keykey的攻擊的攻擊對對MAC的其它攻擊的其它攻擊設(shè)設(shè)M = (X1 | X2 | | Xm) 是一個由是一個由64位位Xi數(shù)據(jù)塊連接而成數(shù)據(jù)塊連接而成 定義定義 (M) = X1 X2 . Xm CK(M) = EK (M) 其中其中 為異或操作；為異或操

15、作；E為為 ECB工作模式的工作模式的DES算法算法則則Key length = 56 bitMAC length = 64 bit強力攻擊需要至少強力攻擊需要至少256次加密來決定次加密來決定K對對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 Y2 , , Ym-1 Ym = EKY1 Y2 , , Ym-1 (Y1 Y2 , , Ym-1 (

16、M) = EK (M)這時消息這時消息M 和和 MAC= CK(M) = EK (M)是一對可被接收者認(rèn)證的消息是一對可被接收者認(rèn)證的消息用此方法，任何長度為用此方法，任何長度為64 (m-1)位的消息可以被插入任意的欺騙性位的消息可以被插入任意的欺騙性信息信息MAC應(yīng)具備的性質(zhì)應(yīng)具備的性質(zhì)n如果一個攻擊者得到如果一個攻擊者得到M和和CK(M)，則攻擊者構(gòu)造一個消息，則攻擊者構(gòu)造一個消息M使使得得CK(M)=CK(M)應(yīng)具有計算復(fù)雜性意義下的不可行性應(yīng)具有計算復(fù)雜性意義下的不可行性nCK(M)應(yīng)均勻分布，即：隨機選擇消息應(yīng)均勻分布，即：隨機選擇消息M和和M， CK(M)= CK(M)的概率是的

17、概率是2-n，其中，其中n是是MAC的位數(shù)的位數(shù)n令令M為為M的某些變換，即：的某些變換，即：M=f(M)，（例如：，（例如：f可以涉及可以涉及M中中一個或多個給定位的反轉(zhuǎn)），在這種情況下，一個或多個給定位的反轉(zhuǎn)），在這種情況下，PrCK(M)= CK(M) = 2-n例子：基于例子：基于DES的報文鑒別碼的報文鑒別碼n算法來源算法來源nFIPS publication (FIPS PUB 113)nANSI standard (X9.17)n使用使用CBC(Cipher Block Chaining)方式，初方式，初始向量為始向量為IV=0基于基于DES的報文鑒別碼的報文鑒別碼將數(shù)據(jù)按將數(shù)據(jù)

18、按64位分組，位分組，D1, D2, , DN，必要時最后一個數(shù)據(jù)塊用，必要時最后一個數(shù)據(jù)塊用0向右填向右填充充運用運用DES算法算法E，密鑰，密鑰K數(shù)據(jù)認(rèn)證碼數(shù)據(jù)認(rèn)證碼(DAC)的計算如下：的計算如下：O1 = EK(D1)O2 = EK(D2O1)O3 = EK(D3O2)ON = EK(DNON-1)FIPS PUB 113基于基于DES的報文鑒別碼的報文鑒別碼將數(shù)據(jù)按將數(shù)據(jù)按64位分組，位分組，D1, D2, , DN，必要時最后一個數(shù)據(jù)塊用，必要時最后一個數(shù)據(jù)塊用0向右填向右填充充運用運用DES算法算法E，密鑰，密鑰K數(shù)據(jù)認(rèn)證碼數(shù)據(jù)認(rèn)證碼(DAC)的計算如下：的計算如下：O1 = E

19、K(D1)O2 = EK(D2O1)O3 = EK(D3O2)ON = EK(DNON-1)目目 錄錄1.消息鑒別與散列函數(shù)消息鑒別與散列函數(shù)2.散列算法散列算法3.數(shù)字簽名數(shù)字簽名散列函數(shù)散列函數(shù)H(M): 輸入為任意長度的消息輸入為任意長度的消息M; 輸出為一個固定長輸出為一個固定長度的散列值，稱為消息摘要度的散列值，稱為消息摘要( (MessageDigest）H(M)是消息是消息M的所有位的函數(shù)并提供錯誤檢測能力：的所有位的函數(shù)并提供錯誤檢測能力：消息中的任何一位或多位的變化都將導(dǎo)致該散列值的消息中的任何一位或多位的變化都將導(dǎo)致該散列值的變化變化H(M)又稱為：哈希函數(shù)、數(shù)字指紋（又稱

20、為：哈希函數(shù)、數(shù)字指紋（Digital finger print)、壓縮（、壓縮（Compression)函數(shù)、數(shù)據(jù)鑒別碼函數(shù)、數(shù)據(jù)鑒別碼（Dataauthentication code）等）等散列函數(shù)的定義散列函數(shù)的定義散列函數(shù)：散列函數(shù)：M:變長報文變長報文H(M):定長的散列值定長的散列值主要用于為文件、報文或其它分組數(shù)據(jù)產(chǎn)生指紋主要用于為文件、報文或其它分組數(shù)據(jù)產(chǎn)生指紋()hH M散列函數(shù)基本用法散列函數(shù)基本用法(1)kAB :EMH (M ) 提 供 鑒 別 加 密 保 護 H ( M ) 提 供 保 密 僅 A 和 B 共 享 密 鑰 k 散列函數(shù)基本用法散列函數(shù)基本用法(2)kA

21、B:ME H(M) 提供鑒別 加密保護H(M)散列函數(shù)基本用法散列函數(shù)基本用法(3)aKR 提供鑒別和數(shù)字簽名 加密保護H(M) 僅A能生成E H(M)散列函數(shù)基本用法散列函數(shù)基本用法(4)akK RAB: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 HASH 安全性：安全威脅一安全

22、性：安全威脅一(a)偽造方式一：Oscar以一個有效簽名(x,y)開始，此處y= sigk(h(x)。首先他計算Z=h(x)，并企圖找到一個x滿足h(x)=h(x)。若他做到這一點，則(x,y)也將為有效簽名。為防止這一點，要求函數(shù)h具有無碰撞特性。 散列函數(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)是一個有效的偽造。 散列函數(shù)h被稱為是強無碰撞的,是指使得h(x)=h(x)的偶對(

23、x, x)在計算上不可行。 安全威脅三(c)偽造方式三：在散列函數(shù)的用法(e)中, 秘密值S本身并不發(fā)送, 如果散列函數(shù)不是單向的,攻擊者截獲到M和H(M|S). 然后通過某種逆變換獲得M|S, 因而攻擊者就可以得到S. 稱散列函數(shù)h為單向的，是指計算h的逆函數(shù)h-1在計算上不可行。散列函數(shù)的要求散列函數(shù)的要求H能用于任意大小的分組能用于任意大小的分組H能產(chǎn)生定長的輸出能產(chǎn)生定長的輸出對任何給定的對任何給定的x，H(x)要相對易于計算，使得硬件和軟件實現(xiàn)成為實要相對易于計算，使得硬件和軟件實現(xiàn)成為實際可能際可能對任何給定的碼對任何給定的碼h，尋找，尋找x使得使得H(x)=h在計算上是不可行的，

24、即單向在計算上是不可行的，即單向性性對任何給定的分組對任何給定的分組x，尋找不等于，尋找不等于x的的y，使得，使得H(x)=H(y)在計算上是在計算上是不可行的，即弱抗沖突性不可行的，即弱抗沖突性尋找對任何的尋找對任何的(x,y)對使得對使得H(x)=H(y)在計算上是不可行的，即強抗沖在計算上是不可行的，即強抗沖突性突性Hash函數(shù)的分類n根據(jù)安全水平：散列函數(shù)h稱為是弱無碰撞的，是指對給定消息x X，在計算上幾乎找不到異于x的x X使h(x)=h(x)。散列函數(shù)h被稱為是強無碰撞的,是指在計算上幾乎不可能找到相異的x，x使得h(x)=h(x)。 Hash函數(shù)的分類n根據(jù)是否使用密鑰n帶秘密

25、密鑰的Hash函數(shù):消息的散列值由只有通信雙方知道的秘密密鑰K來控制。此時，散列值稱作MAC。n不帶秘密密鑰的Hash函數(shù)：消息的散列值的產(chǎn)生無需使用密鑰。此時，散列值稱作MDC。安全威脅四：生日攻擊安全威脅四：生日攻擊n攻擊者的主要攻擊目標(biāo)是找到一對或更多對碰撞消息。n攻擊Hash算法和計算碰撞消息的方法。（1）一般的方法，攻擊任何類型的Hash算法，比如“生日攻擊”；（2）特殊的方法，只能用于攻擊某些特殊的Hash算法。 n題目描述題目描述n密碼學(xué)中有種很有意思的攻擊方式叫做生日攻擊。其原理是基于這樣一個神奇的結(jié)論：如果一個房間里有23個人，那么其中兩個人生日相同的概率超過50%，當(dāng)人數(shù)上

26、升到40人時，這一概率提高到了89%以上。注意生日相同指的是兩個人的出生月份和日期相同，不考慮年份。這個結(jié)論聽上去很神奇，因為一年有365天，但是，事實上你可以通過概率知識驗證這個結(jié)論。n計算機率的方法是，首先找出 表示 n 個人中，每個人的生日日期都不同的概率。n上式等于np(n)表示n個人中2人生日相同的概率n當(dāng) n=23發(fā)生的概率大約是0.507( )p n生日攻擊n假定使用64位的散列碼,是否安全?n如果采用傳輸加密的散列碼和不加密的報文M,對手需要找到M ,使得H(M)=H(M),以便使用替代報文來欺騙接收者.n一種基于生日悖論的攻擊可能做到這一點.相關(guān)問題n給定一個散列函數(shù),有n個

27、可能的輸出,輸出值為H(x),如果H有k個隨機輸入, k必須為多大才能使至少存在一個輸入y,使得H(y)=H(x)的概率大于0.5.n對單個y, H(y)=H(x)的概率為1/n,反過來H(y)H(x)的概率為1-(1/n).n如果產(chǎn)生k個隨機值y,他們之間兩兩不等的概率等于每個個體不匹配概率的乘積,即1-(1/n)k,這樣,至少有一個匹配的概率為1-1-(1/n)k.要概率等于0.5,只需k=n1/2n對長度為m位的散列碼，共有2m個可能的散列碼，若要使任意的x,y 有H(x)=H(y)的概率為0.5,只需 k=2m/2nM越長攻擊上計算越接近不可行性；n例如：對于SHA-1算法，269次運

28、算需要年左右的時間，在實際計算上仍然是不可行的 n堅固的哈希函數(shù)可通過設(shè)計有效的碰撞處理機制，或增加數(shù)字摘要的位數(shù)來增加復(fù)雜度，以減少碰撞出現(xiàn)的概率， Birthday Attacks: exampleA準(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必須足夠長(64 128 160)Hash vs MACMAC需要對全部數(shù)據(jù)進行加密需要對全部數(shù)據(jù)進行加

29、密MAC速度慢速度慢Hash是一種直接產(chǎn)生鑒別碼的方法是一種直接產(chǎn)生鑒別碼的方法常用常用Hash算法算法SHA-1MD5 RIPEMD-160 HMACMD5nMD5即Message-Digest Algorithm 5，用于確保信息傳輸完整一致。是計算機廣泛使用的散列算法之一（又譯摘要算法摘要算法、哈希算法），主流編程語言普遍已有MD5實現(xiàn)。n將數(shù)據(jù)（如漢字）運算為另一固定長度值，是散列算法的基礎(chǔ)原理，MD5的前身有MD2、MD3和MD4。nMD5一度被廣泛應(yīng)用于安全領(lǐng)域。但是由于MD5的弱點被不斷發(fā)現(xiàn)以及計算機能力不斷的提升，現(xiàn)在已經(jīng)可以構(gòu)造兩個具有相同MD5的信息，使本算法不再適合當(dāng)前的

30、安全環(huán)境。目前，MD5計算廣泛應(yīng)用于錯誤檢查。例如在一些BitTorrent下載中，軟件通過計算MD5和檢驗下載到的碎片的完整性。nMD5算法應(yīng)用算法應(yīng)用n其典型應(yīng)用是對一段Message（字節(jié)串）產(chǎn)生Fingerprint（指紋），以防止被篡改。比如，在UNIX下有很多軟件在下載的時候都有一個文件名相同，文件擴展名為.md5的文件，在這個文件中通常只有一行文本，大致結(jié)構(gòu)為： MD5 (httpd-2.2.0.tar.bz2) = n402b90a2e47205f94b3b1d91e1a8c459，這就是httpd-2.2.0.tar.bz2文件的數(shù)字簽名。n如果在以后傳播這個文件的過程中，無

31、論文件的內(nèi)容發(fā)生了任何形式的改變（包括人為修改，如Repack進木馬病毒，或者下載過程中線路不穩(wěn)定引起的傳輸錯誤等），只要你對這個文件重新計算MD5時就會發(fā)現(xiàn)信息摘要不相同，由此可以確定你得到的只是一個不正確的文件。nMD5還廣泛用于加密和解密技術(shù)上。 例如在UNIX系統(tǒng)中用戶的密碼就是以MD5（或其它類似算法）經(jīng)加密后存儲在文件系統(tǒng)中。MD5算法描述算法描述 - step 1n在MD5算法中，首先需要對信息進行填充，使其字節(jié)長度對512求余的結(jié)果等于448。因此，信息的字節(jié)長度（Bits Length）將被擴展至N*512+448，即N*64+56個字節(jié)（Bytes），N為一個正整數(shù)。填充的

32、方法如下，在信息的后面填充一個1和無數(shù)個0，直到滿足上面的條件時才停止用0對信息的填充。然后，在在這個結(jié)果后面附加一個以64位二進制表示的填充前信息長度。經(jīng)過這兩步的處理，現(xiàn)在的信息字節(jié)長度=N*512+448+64=(N+1)*512，即長度恰好是512的整數(shù)倍。這樣做的原因是為滿足后面處理中對信息長度的要求。MD5描述描述step 2初始化初始化MD緩存緩存MD為為128bit，用于存放散列函數(shù)的中間及最終結(jié)果，用于存放散列函數(shù)的中間及最終結(jié)果MD可表示為可表示為4個個32bit的寄存器的寄存器(A,B,C,D)，初始化如下，初始化如下：MD5描述描述step 3壓縮：壓縮：4個循環(huán)的壓縮

33、算法個循環(huán)的壓縮算法n步驟4：處理消息塊(512位=16個32位字)。一個壓縮n函數(shù)是本算法的核心(HMD5)，它包括4輪處理。四輪處理具n有相似的結(jié)構(gòu)，但每次使用不同的基本邏輯函數(shù)，記為F，G，H，lMD5描述描述step 4輸出輸出HMD5單個單個512bit分組的分組的MD5處理過程處理過程(MD5壓縮函數(shù)）壓縮函數(shù)）當(dāng)前正在處當(dāng)前正在處理的理的512比特分組比特分組128bit的緩存值的緩存值更新緩存更新緩存T0,16432(2(sin( ),0(sin( )13232iiTINTabsiiabsiTbitbit的單位為弧度能用表示，提供了隨機化的模式，消除了規(guī)律性每步操作形式每步操作

34、形式單個單個512bit分組的分組的MD5處理過程處理過程(MD5壓縮函數(shù)）壓縮函數(shù)）116( )(15 ) mod16( )(53 ) mod16( )5 mod16iiiiiii234X0.15:保存當(dāng)前保存當(dāng)前512bit待處理輸入分組的值待處理輸入分組的值Xk = Mq16 + k = 在第在第q個個512位數(shù)據(jù)塊中的第位數(shù)據(jù)塊中的第k個個32位字位字每次循環(huán)每次循環(huán)(4)的每步的每步(16)內(nèi)，內(nèi)，Xi的使用循序各不相同的使用循序各不相同MD5的安全性的安全性Berson表明，對單循環(huán)表明，對單循環(huán)MD5，使用不用的密碼分析可能在合理的，使用不用的密碼分析可能在合理的時間內(nèi)找出能夠產(chǎn)

35、生相同摘要的兩個報文，這個結(jié)果被證明對四時間內(nèi)找出能夠產(chǎn)生相同摘要的兩個報文，這個結(jié)果被證明對四個循環(huán)中的任意一個循環(huán)也成立，但作者沒有能夠提出如何攻擊個循環(huán)中的任意一個循環(huán)也成立，但作者沒有能夠提出如何攻擊包含全部包含全部4個循環(huán)個循環(huán)MD5的攻擊的攻擊Boer和和Bosselaers顯示了即使緩存顯示了即使緩存ABCD不同，不同，MD5對單個對單個512bit分組的執(zhí)行將得到相同的輸出分組的執(zhí)行將得到相同的輸出(偽沖突）偽沖突）Dobbertin的攻擊技術(shù)：使的攻擊技術(shù)：使MD5的壓縮函數(shù)產(chǎn)生沖突，即尋找的壓縮函數(shù)產(chǎn)生沖突，即尋找MD5被認(rèn)為是易受攻擊的，逐漸被被認(rèn)為是易受攻擊的，逐漸被S

36、HA-1和和RIPEMD-160替代替代,( )( )xy xyH xH y、但Hash小結(jié)小結(jié)Hash函數(shù)把變長信息映射到定長信息函數(shù)把變長信息映射到定長信息Hash函數(shù)不具備可逆性函數(shù)不具備可逆性Hash函數(shù)速度較快函數(shù)速度較快Hash函數(shù)與對稱密鑰加密算法有某種相似性函數(shù)與對稱密鑰加密算法有某種相似性對對Hash函數(shù)的密碼分析比對稱密鑰密碼更困難函數(shù)的密碼分析比對稱密鑰密碼更困難Hash函數(shù)可用于消息摘要函數(shù)可用于消息摘要Hash函數(shù)可用于數(shù)字簽名函數(shù)可用于數(shù)字簽名目目 錄錄1.消息鑒別與散列函數(shù)消息鑒別與散列函數(shù)2.散列算法散列算法3.數(shù)字簽名數(shù)字簽名報文鑒別的局限性報文鑒別的局限性用

37、于保護通信雙方免受第三方攻擊用于保護通信雙方免受第三方攻擊無法防止通信雙方的相互攻擊無法防止通信雙方的相互攻擊n信宿方偽造報文信宿方偽造報文n信源方否認(rèn)已發(fā)送的報文信源方否認(rèn)已發(fā)送的報文引入數(shù)字簽名，是筆跡簽名的模擬引入數(shù)字簽名，是筆跡簽名的模擬數(shù)字簽名的性質(zhì)數(shù)字簽名的性質(zhì)傳統(tǒng)簽名的基本特點傳統(tǒng)簽名的基本特點n能與被簽的文件在物理上不可分割能與被簽的文件在物理上不可分割n簽名者不能否認(rèn)自己的簽名簽名者不能否認(rèn)自己的簽名n簽名不能被偽造簽名不能被偽造n容易被驗證容易被驗證數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化數(shù)字簽名是傳統(tǒng)簽名的數(shù)字化n能與所簽文件能與所簽文件“綁定綁定”n簽名者不能否認(rèn)自己的簽名簽名者不能

38、否認(rèn)自己的簽名n容易被自動驗證容易被自動驗證n簽名不能被偽造簽名不能被偽造數(shù)字簽名的性質(zhì)數(shù)字簽名的性質(zhì)必須能夠驗證作者及其簽名的日期時間必須能夠驗證作者及其簽名的日期時間必須能夠認(rèn)證簽名時刻的內(nèi)容必須能夠認(rèn)證簽名時刻的內(nèi)容簽名必須能夠由第三方驗證，以解決爭議簽名必須能夠由第三方驗證，以解決爭議數(shù)字簽名分類數(shù)字簽名分類簽名方式簽名方式n直接數(shù)字簽名直接數(shù)字簽名direct digital signaturen仲裁數(shù)字簽名仲裁數(shù)字簽名arbitrated digital signature安全性安全性 無條件安全的數(shù)字簽名無條件安全的數(shù)字簽名 計算上安全的數(shù)字簽名計算上安全的數(shù)字簽名可簽名次數(shù)可簽

39、名次數(shù)一次性的數(shù)字簽名一次性的數(shù)字簽名 多次性的數(shù)字簽名多次性的數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名直接數(shù)字簽名的缺點直接數(shù)字簽名的缺點驗證模式依賴于發(fā)送方的保密密鑰驗證模式依賴于發(fā)送方的保密密鑰 發(fā)送方要抵賴發(fā)送某一消息時，可能會聲稱其私有密鑰丟失或被發(fā)送方要抵賴發(fā)送某一消息時，可能會聲稱其私有密鑰丟失或被竊，從而他人偽造了他的簽名竊，從而他人偽造了他的簽名 通常需要采用與私有密鑰安全性相關(guān)的行政管理控制手段來制止通常需要采用與私有密鑰安全性相關(guān)的行政管理控制手段來制止或至少是削弱這種情況，但威脅在某種程度上依然存在或至少是削弱這種情況，但威脅在某

40、種程度上依然存在 改進的方式例如可以要求被簽名的信息包含一個時間戳（日期與時改進的方式例如可以要求被簽名的信息包含一個時間戳（日期與時間），并要求將已暴露的密鑰報告給一個授權(quán)中心間），并要求將已暴露的密鑰報告給一個授權(quán)中心X的某些私有密鑰確實在時間的某些私有密鑰確實在時間T被竊取，敵方可以偽造被竊取，敵方可以偽造X的簽名及的簽名及早于或等于時間早于或等于時間T的時間戳的時間戳仲裁數(shù)字簽名仲裁數(shù)字簽名仲裁數(shù)字簽名仲裁數(shù)字簽名引入仲裁者引入仲裁者 所有從發(fā)送方所有從發(fā)送方X到接收方到接收方Y(jié)的簽名消息首先送到仲裁者的簽名消息首先送到仲裁者A A將消息及其簽名進行一系列測試，以檢查其來源和內(nèi)容將消息

41、及其簽名進行一系列測試，以檢查其來源和內(nèi)容 A將消息加上日期并與已被仲裁者驗證通過的指示一起發(fā)給將消息加上日期并與已被仲裁者驗證通過的指示一起發(fā)給Y仲裁者在這一類簽名模式中扮演敏感和關(guān)鍵的角色仲裁者在這一類簽名模式中扮演敏感和關(guān)鍵的角色 所有的參與者必須極大地相信這一仲裁機制工作正常所有的參與者必須極大地相信這一仲裁機制工作正常仲裁數(shù)字簽名單密鑰加密方式仲裁數(shù)字簽名單密鑰加密方式1數(shù)字簽名數(shù)字簽名仲裁數(shù)字簽名單密鑰加密方式仲裁數(shù)字簽名單密鑰加密方式仲裁數(shù)字簽名單密鑰加密方式仲裁數(shù)字簽名單密鑰加密方式2仲裁數(shù)字簽名雙密鑰加密方式仲裁數(shù)字簽名雙密鑰加密方式仲裁數(shù)字簽名雙密鑰加密方式仲裁數(shù)字簽名雙密

42、鑰加密方式數(shù)字簽名算法數(shù)字簽名算法普通數(shù)字簽名算法普通數(shù)字簽名算法 EIGamal RSA DSS/DSA不可否認(rèn)的數(shù)字簽名算法不可否認(rèn)的數(shù)字簽名算法群簽名算法群簽名算法盲簽名算法盲簽名算法RSA簽名方案簽名與加密簽名提供真實性(authentication)加密提供保密性(confidentiality)“簽名+加密”提供“真實性+保密性”兩種實現(xiàn)方式: (AB)先簽名,后加密: EKUbM|SigA(M)先加密,后簽名: EKUb(M)|SigA(EKUb(M)方式的問題:發(fā)生爭議時,B需要向仲裁者提供自己的私鑰安全漏洞: 攻擊者E截獲消息,把SigA(EKUb(M)換成SigE(EKUb

43、(M),讓B以為該消息來自E保存信息多:除了M,SigA(EKUb(M), 還要保存EKUb(M) (KUb可能過期)DSS數(shù)字簽名n是由美國國家標(biāo)準(zhǔn)化研究院和國家安全局共同開發(fā)的。由于它是由美國政府頒布實施的，主要用于與美國政府做生意的公司，其他公司則較少使用，它只是一個簽名系統(tǒng)，而且美國政府不提倡使用任何削弱政府竊聽能力的加密軟件，認(rèn)為這才符合美國的國家利益。 n 公布于1994年5月19日的聯(lián)邦記錄上，并于1994年12月1日采納為標(biāo)準(zhǔn)DSS。DSS為EIGamal簽名方案的改進。DSS(Digital Signature Standard) DSS簽名方案算法自閱DSS簽名和驗證DSS的特點DSS的簽名比驗證快得多DSS不能用于加密或者密鑰分配s-1 mod q