信息安全原理與實(shí)踐-第二版05-哈希函數(shù)及其他課件

1信息安全原理與實(shí)踐InformationSecurity:PrinciplesandPractice,2ndEdition[美]MarkStamp 著張戈 譯1信息安全原理與實(shí)踐InformationSecurity第5章哈希函數(shù)及其他2第5章哈希函數(shù)及其他25.1引言本章內(nèi)容加密哈希函數(shù)加密哈希函數(shù)的標(biāo)準(zhǔn)應(yīng)用哈希函數(shù)的高級(jí)應(yīng)用加密相關(guān)的副作用問(wèn)題35.1引言本章內(nèi)容35.2什么是加密哈希函數(shù)一個(gè)加密哈希函數(shù)h(x)，必須滿(mǎn)足下列所有條件：壓縮——對(duì)于任何長(zhǎng)度的輸入值x，輸出值y=h(x)的長(zhǎng)度都比較小。在實(shí)際使用中，通常輸出值是固定長(zhǎng)度的(比如160位長(zhǎng)度的二進(jìn)制值)，而無(wú)論輸入值的長(zhǎng)度是多少。高效——對(duì)于任何的輸入值x，必須能夠很容易地計(jì)算出h(x)。當(dāng)然，伴隨著輸入值x的長(zhǎng)度增加，計(jì)算h(x)所需要的計(jì)算量也會(huì)隨之增加，但是，這不能增長(zhǎng)得太快。單向——給定任意值y，要想找到一個(gè)值x，使得h(x)=y，將是計(jì)算不可行的。換一種不同的說(shuō)法，即對(duì)于哈希運(yùn)算，沒(méi)有行之有效的逆運(yùn)算。抗弱碰撞性——給定x和h(x)，要想找到任意y，滿(mǎn)足y≠x，并且h(y)=h(x)，這是不可能的?？箯?qiáng)碰撞性——要想找到任意的x和y，使得x≠y，并且h(x)=h(y)，這是不可能的。也就是說(shuō)，我們不能夠找到任何兩個(gè)輸入，使得它們經(jīng)過(guò)哈希后會(huì)產(chǎn)生相同的輸出值。45.2什么是加密哈希函數(shù)一個(gè)加密哈希函數(shù)h(x)，必須滿(mǎn)足哈希函數(shù)在數(shù)字簽名上的應(yīng)用以前Alice對(duì)一條消息M實(shí)施簽名，是通過(guò)使用她自己的私鑰進(jìn)行“加密”計(jì)算得到的，即要計(jì)算S=[M]Alice。如果Alice發(fā)送消息M和簽名S給Bob，Bob就能夠通過(guò)執(zhí)行驗(yàn)證過(guò)程M={S}Alice來(lái)驗(yàn)證該簽名的有效性。但是，如果消息M很大，[M]Alice就是一個(gè)成本很高的計(jì)算，更不用提發(fā)送消息M和簽名S的帶寬需求了，這兩者都會(huì)很大。相比之下，在計(jì)算一個(gè)MAC時(shí)，加密的速度會(huì)很快，而且在發(fā)送時(shí)，我們也僅僅需要伴隨著消息發(fā)送少量附加的校驗(yàn)位(比如MAC)而已。使用哈希函數(shù)之后假設(shè)Alice有一個(gè)加密哈希函數(shù)h。那么，h(M)可以被看做文檔M的一個(gè)“指紋”，也就是說(shuō)，h(M)比M小得多，但是它能夠標(biāo)識(shí)出M。如果M'不同于M，那么即使僅僅相差一個(gè)單獨(dú)的二進(jìn)制位，哈希函數(shù)執(zhí)行的結(jié)果也幾乎肯定會(huì)不同。而且，哈希函數(shù)的抗碰撞特性意味著，想要將消息M替換為任何不同的消息M'，使得h(M)=h(M')是不可能的1.一旦哈希值發(fā)生相同的情況，該怎么辦呢？好的，這說(shuō)明你已經(jīng)發(fā)現(xiàn)了一個(gè)碰撞，也就意味著你已經(jīng)攻破了這個(gè)哈希函數(shù)，于是你就成為一個(gè)著名的密碼破解專(zhuān)家了。所以，這是個(gè)雙贏的好事。5哈希函數(shù)在數(shù)字簽名上的應(yīng)用5簽名的正確方法假設(shè)沒(méi)有碰撞，那么對(duì)h(M)簽名和對(duì)消息M實(shí)施簽名的效果一樣好。事實(shí)上，對(duì)哈希值實(shí)施簽名比起僅僅對(duì)消息本身實(shí)施簽名，實(shí)際上會(huì)更加安全?，F(xiàn)在數(shù)字簽名的安全性不僅依賴(lài)于公鑰系統(tǒng)的安全性，而且也依賴(lài)于哈希函數(shù)本身的安全性——如果二者中有任何一個(gè)比較弱，簽名體制就可能會(huì)被破解。6簽名的正確方法65.3生日問(wèn)題假如你和其他N個(gè)人同在一個(gè)房間里。那么，N必須多大，你才有指望找到至少一個(gè)人和你有相同的生日呢？或者說(shuō)：N必須多大，才會(huì)使得“有某個(gè)人與你生日相同”的概率大于1/2呢？你的生日是在一年中特定的一天。如果一個(gè)人和你的生日不同，那么他或她的生日必定是在其他364天中的一天。假設(shè)所有的生日都是概率相等的，那么“一個(gè)隨機(jī)選擇的人不與你的生日相同”的概率就是364/365。這樣，所有的N個(gè)人都跟你的生日不同的概率就是(364/365)N，于是，至少有一個(gè)人與你的生日相同的概率就是：設(shè)置這個(gè)表達(dá)式等于1/2，并解出N，得到N=253。75.3生日問(wèn)題假如你和其他N個(gè)人同在一個(gè)房間里。那么，N必真正的生日問(wèn)題我們給房間里的N個(gè)人分別編上號(hào)碼1，2，3，…，N。編號(hào)為1的人的生日是一年365天中的一天。如果所有人的生日各不相同，那么編號(hào)為2的人必須與編號(hào)為1的人的生日不相同，也就是說(shuō)，編號(hào)為2的人的生日只能是剩余的364天中的任意一天。同樣，編號(hào)為3的人的生日只能是再剩余的363天中的任意一天，依此類(lèi)推。假設(shè)所有的生日都是概率相等的，考慮上述情況的補(bǔ)集，其最后的概率計(jì)算如下式所示設(shè)置這個(gè)表達(dá)式等于1/2，并解出N，我們得到N=238生日悖論真正的生日問(wèn)題8生日延伸對(duì)于一個(gè)生成N位二進(jìn)制長(zhǎng)度輸出的安全哈希函數(shù)來(lái)說(shuō)，一個(gè)計(jì)算開(kāi)銷(xiāo)大約以2N/2為因子的強(qiáng)力破解方式，就能夠?qū)ζ浒l(fā)起有效的攻擊。相比較而言，對(duì)于一個(gè)密鑰長(zhǎng)度為N位二進(jìn)制數(shù)的安全對(duì)稱(chēng)密鑰加密方案來(lái)說(shuō)，對(duì)其強(qiáng)力破解的計(jì)算開(kāi)銷(xiāo)的因子是2N-l。所以，安全哈希函數(shù)的輸出必須是對(duì)稱(chēng)加密密鑰二進(jìn)制位數(shù)的大約兩倍長(zhǎng)，才能夠獲得與后者基本相當(dāng)?shù)陌踩健?延伸95.4生日攻擊假設(shè)哈希函數(shù)h生成一個(gè)n位二進(jìn)制長(zhǎng)的輸出。Trudy原則上能夠發(fā)起一次生日攻擊，具體如下：Trudy選擇一條“惡意”消息E，這是她想讓Alice簽名的消息，但是Alice并不想對(duì)其簽名。Trudy也創(chuàng)建了一條無(wú)害的消息I，她有信心Alice愿意對(duì)這條消息簽名。然后，Trudy通過(guò)對(duì)消息實(shí)施較小的編輯性修改，生成2n/2條該無(wú)害消息I的變體。這些無(wú)害的消息，我們分別標(biāo)識(shí)為Ii，其中i=0,1,...,2n/2–1，所有消息都與I的含義相同，但是既然消息本身不同，那么它們的哈希值也不一樣。同樣，Trudy創(chuàng)建出2n/2個(gè)惡意消息E的變體，分別標(biāo)識(shí)為Ei，其中i=0,1,...,2n/2–1。這些消息也都與原始的惡意消息E表達(dá)同樣的含義，但是它們的哈希值不一樣。Trudy對(duì)所有的惡意消息Ei以及所有的無(wú)害消息Ii實(shí)施哈希運(yùn)算。根據(jù)上述生日問(wèn)題的討論，她就有希望找到一個(gè)碰撞，比方說(shuō)，h(Ej)=h(Ik)?；谶@樣的一個(gè)碰撞，Trudy將Ik發(fā)送給Alice，并請(qǐng)Alice對(duì)其進(jìn)行簽名。既然這條消息看起來(lái)沒(méi)有問(wèn)題，Alice就對(duì)其進(jìn)行簽名，并將Ik和[h(Ik)]Alice返回給Trudy。既然h(Ej)=h(Ik)，那么由此可以得出[h(Ej)]Alice=[h(Ik)]Alice，于是，Trudy實(shí)際上就已經(jīng)獲得了Alice對(duì)惡意消息Ej的簽名。105.4生日攻擊假設(shè)哈希函數(shù)h生成一個(gè)n位二進(jìn)制長(zhǎng)的輸出。T在這個(gè)攻擊中，Trudy獲得了Alice對(duì)于一條Trudy自選消息的簽名，但是并沒(méi)有以任何方式攻擊潛在的公開(kāi)密鑰加密系統(tǒng)。這個(gè)攻擊是一個(gè)針對(duì)哈希函數(shù)h的強(qiáng)力攻擊，而哈希函數(shù)h是用于計(jì)算數(shù)字簽名的。為了防止此類(lèi)攻擊，我們可以選擇一個(gè)哈希函數(shù)，使得該哈希函數(shù)的輸出值的長(zhǎng)度n足夠大，以至于Trudy無(wú)法完成2n/2個(gè)哈希值的計(jì)算。11在這個(gè)攻擊中，Trudy獲得了Alice對(duì)于一條Trudy自5.5非加密哈希非加密哈希運(yùn)算的例子（1）其中，每個(gè)Xi是一個(gè)字節(jié)，定義哈希函數(shù)h(X)為：這毫無(wú)疑問(wèn)提供了壓縮功能，因?yàn)槿魏伍L(zhǎng)度的輸入都被壓縮為8位二進(jìn)制的輸出。但是，這個(gè)哈希很容易被破解，因?yàn)樯諉?wèn)題的結(jié)論告訴我們，只需對(duì)24=16個(gè)隨機(jī)選擇的輸入執(zhí)行哈希運(yùn)算，我們就有望找到一個(gè)碰撞。對(duì)兩個(gè)字節(jié)進(jìn)行互換，就總是能夠產(chǎn)生一個(gè)碰撞，類(lèi)似如下這種情況：（2）我們將哈希函數(shù)h(X)定義為：雖然該函數(shù)在交換輸入字節(jié)順序的情況下能夠輸出不同的結(jié)果，但是仍然逃不過(guò)生日問(wèn)題帶來(lái)的麻煩。125.5非加密哈希非加密哈希運(yùn)算的例子12循環(huán)冗余校驗(yàn)，或簡(jiǎn)稱(chēng)為CRC循環(huán)冗余校驗(yàn)碼的計(jì)算本質(zhì)上是長(zhǎng)除法，將余數(shù)作為CRC計(jì)算的“哈?！敝?。與常規(guī)的長(zhǎng)除法不同，CRC在計(jì)算中使用XOR運(yùn)算替代了減法。在一個(gè)CRC的計(jì)算過(guò)程中，除數(shù)被指定作為算法的一部分，數(shù)據(jù)作為被除數(shù)。例子假設(shè)給定的除數(shù)是10011，而有趣的是數(shù)據(jù)恰好是10101011。那么，我們先對(duì)數(shù)據(jù)附加上4個(gè)0(附加的位數(shù)要比除數(shù)的二進(jìn)制位數(shù)少1)，然后執(zhí)行如下長(zhǎng)除法運(yùn)算：CRC校驗(yàn)和就是長(zhǎng)除法運(yùn)算的余數(shù)——在這個(gè)例子中，就是1010。13循環(huán)冗余校驗(yàn)，或簡(jiǎn)稱(chēng)為CRC135.6TigerHashMD5MD指的是消息摘要(MessageDigest)，它的前身是MD4，而MD4本身又繼承自MD2。所有的MD系列算法都是由加密領(lǐng)域的大師級(jí)人物RonRivest所發(fā)明。MD5算法生成128位的輸出值。SHA-1算法SHA表示安全哈希算法(SecureHashAlgorithm)，是美國(guó)政府的一個(gè)標(biāo)準(zhǔn)。SHA-1算法實(shí)際上非常類(lèi)似于MD5算法。兩個(gè)算法在實(shí)踐中的主要不同在于SHA-1生成160位二進(jìn)制長(zhǎng)的輸出值，比MD5提供了更可觀的安全邊際。14所謂雪崩效應(yīng)，是所有加密哈希函數(shù)都會(huì)追求的一個(gè)理想特性。其目標(biāo)是：在輸入值中任何小的變化，都應(yīng)該級(jí)聯(lián)傳遞并導(dǎo)致輸出結(jié)果較大的變化——就像雪崩一樣。理想情況下，任何輸入值的變化引發(fā)的輸出值變化都是不相關(guān)的，這樣，攻擊者將不得不實(shí)施窮舉式檢索來(lái)尋找碰撞。5.6TigerHashMD514所謂雪崩效應(yīng)，是所有加Tiger算法特點(diǎn)算法的輸入先被分成512位二進(jìn)制長(zhǎng)度的分組，如果需要的話，就對(duì)輸入值進(jìn)行附加填充位，以補(bǔ)足成512的倍數(shù)位的長(zhǎng)度。算法輸出192位二進(jìn)制長(zhǎng)度的哈希值。算法實(shí)現(xiàn)中使用了4個(gè)S-box，這4個(gè)S-box的每一個(gè)都將8位二進(jìn)制位映射為64位。算法還使用了一個(gè)“密鑰調(diào)度”的算法，不過(guò)由于這里沒(méi)有密鑰的概念，該算法實(shí)際是施加到了輸入分組上。15Tiger算法特點(diǎn)15Tiger算法的過(guò)程首先對(duì)輸入值X進(jìn)行附加填充位，使其長(zhǎng)度滿(mǎn)足512位二進(jìn)制長(zhǎng)的倍數(shù)，表示為：，其中每一個(gè)Xi都是一個(gè)512位二進(jìn)制長(zhǎng)的分組。對(duì)每一個(gè)Xi使用一個(gè)外層的輪運(yùn)算。假設(shè)a，b和c都是64位二進(jìn)制長(zhǎng)的值。對(duì)于第一輪運(yùn)算，(a,b,c)的初始值以16進(jìn)制形式表示如下：16Tiger算法的過(guò)程16一輪運(yùn)算之后，輸出的(a,b,c)就成為后續(xù)下一輪運(yùn)算的初始三元組。最后一輪運(yùn)算之后，最終輸出的(a,b,c)就是192位二進(jìn)制長(zhǎng)的哈希值。首個(gè)外層輪函數(shù)F5的輸入是(a,b,c)，如果我們標(biāo)記F5的輸出為(a,b,c)，那么F7的輸入為(c,a,b)。同樣地，如果我們標(biāo)記F7的輸出為(a,b,

c)，那么F9的輸入為(b,c,a)。上圖的每一個(gè)函數(shù)Fm都包含了8個(gè)下圖所示的內(nèi)層輪運(yùn)算。我們?cè)倭頦表示內(nèi)層輪運(yùn)算的512位二進(jìn)制的輸入值，其可以表示如下17一輪運(yùn)算之后，輸出的(a,b,c)就成為后續(xù)下一輪運(yùn)算的對(duì)于函數(shù)fm,i，當(dāng)i=0,1,2,...,7時(shí)，其各自的輸入值分別如下其中各自對(duì)應(yīng)的函數(shù)fm,i-1的輸出標(biāo)記為(a,b,c)。每一個(gè)fm,i都依賴(lài)于a，b，c，wi和m，其中wi是512位二進(jìn)制輸入值W的第i個(gè)64位子分組。c寫(xiě)作：

，其中每一個(gè)ci都是一個(gè)單獨(dú)的字節(jié)。fm,i由下式給定：每一個(gè)Si都是一個(gè)S-box(即查找表)，將8位二進(jìn)制映射為64位二進(jìn)制。18對(duì)于函數(shù)fm,i，當(dāng)i=0,1,2,...,7時(shí)，其密鑰調(diào)度算法假設(shè)令W為密鑰調(diào)度算法的512位二進(jìn)制輸入值。同上，我們將W寫(xiě)作W=(w0,w1,…,w7)，其中每一個(gè)wi都是一個(gè)64位二進(jìn)制值，我們?cè)倭?/p>

為wi的二進(jìn)制補(bǔ)數(shù)。密鑰調(diào)度算法如下，其中最后的計(jì)算結(jié)果W=(w0,w1,…,w7)給出了該算法的輸出值。19密鑰調(diào)度算法19小結(jié)Tiger哈希算法共包含24輪運(yùn)算，這24輪運(yùn)算可以看成是3個(gè)外層輪運(yùn)算，而這每一個(gè)外層運(yùn)算都包含了8個(gè)內(nèi)層輪運(yùn)算。該算法所有的中間步驟產(chǎn)生的哈希值都是192位二進(jìn)制值。該算法中S-box的設(shè)計(jì)使得僅僅經(jīng)過(guò)24輪運(yùn)算中的3輪計(jì)算，每一個(gè)輸入的二進(jìn)制位就會(huì)影響到a，b和c三者中的每一個(gè)。而且，在消息中任何小的變化，都將影響到算法中間步驟產(chǎn)生的哈希值的多個(gè)二進(jìn)制位。在fm,i計(jì)算過(guò)程中，最后一步的乘法也是該算法設(shè)計(jì)中的一個(gè)關(guān)鍵特性。它的目的是為了確保，對(duì)于一輪運(yùn)算中每個(gè)S-box的輸入，都將在下一輪的運(yùn)算中混入到多個(gè)S-box中。20小結(jié)205.7HMACHMAC來(lái)源怎么才能將密鑰混入到所謂的HMAC中呢？將密鑰置于消息體之前，即計(jì)算h(K,M)假如我們選擇計(jì)算h(K,M)來(lái)得到HMAC。如果消息M=(B1,B2)，其中每個(gè)Bi都是512位二進(jìn)制長(zhǎng)，則如果Trudy選擇了M‘，使得M’=(M,X)，那么，Trudy有可能利用以上燈飾從h(K,M)找到h(K,M')。因?yàn)椋瑢?duì)于特定長(zhǎng)度的K，M和X，有將密鑰附加于消息體之后，即計(jì)算h(M,K)21假如令B為哈希運(yùn)算的分組長(zhǎng)度，以字節(jié)數(shù)表示。對(duì)于所有流行的哈希算法B=64。ipad=0x36重復(fù)B次opad=0x5C重復(fù)B次那么，消息M的HMAC定義為：這個(gè)方案將密鑰徹底地混入到哈希運(yùn)算的結(jié)果當(dāng)中。計(jì)算一個(gè)HMAC值雖然需要執(zhí)行兩遍哈希運(yùn)算，但是第二次哈希運(yùn)算僅作用于少量的二進(jìn)制位并使用了修改的附加填充密鑰。所以，總開(kāi)銷(xiāo)比起計(jì)算h(M)所需要的開(kāi)銷(xiāo)，僅僅多了少許。更好5.7HMACHMAC來(lái)源21假如令B為哈希運(yùn)算的分組長(zhǎng)度5.8哈希函數(shù)的用途標(biāo)準(zhǔn)應(yīng)用身份認(rèn)證消息完整性保護(hù)(使用HMAC)消息指紋錯(cuò)誤檢測(cè)高效數(shù)字簽名等高級(jí)應(yīng)用網(wǎng)上競(jìng)價(jià)垃圾郵件減阻225.8哈希函數(shù)的用途標(biāo)準(zhǔn)應(yīng)用225.8.1網(wǎng)上競(jìng)價(jià)假設(shè)有一個(gè)物品在網(wǎng)上拍賣(mài)，而Alice、Bob以及Charlie都想要出價(jià)競(jìng)拍。每一個(gè)競(jìng)拍者都有一次機(jī)會(huì)提交一個(gè)秘密的報(bào)價(jià)，只有當(dāng)所有的報(bào)價(jià)都接收到之后，競(jìng)拍價(jià)格才會(huì)公開(kāi)。依照慣例，報(bào)價(jià)最高的競(jìng)拍者獲勝。前提：Alice、Bob以及Charlie，三人之間必然是互相不信任的，另外，他們也絕對(duì)都不會(huì)信任和接受競(jìng)投價(jià)格的網(wǎng)上服務(wù)。為了努力消除這些擔(dān)心，網(wǎng)上服務(wù)方提出了如下的方案：每一個(gè)競(jìng)拍者將確定他們各自的競(jìng)拍價(jià)格，比方說(shuō)，Alice出價(jià)為A，Bob出價(jià)為B，Charlie出價(jià)為C，各自確保其報(bào)價(jià)秘密。然后，Alice將提交h(A)，Bob將提交h(B)，Charlie將提交h(C)。一旦所有三個(gè)經(jīng)過(guò)哈希運(yùn)算的報(bào)價(jià)都已接收到，網(wǎng)上服務(wù)方就在線公開(kāi)發(fā)布這些哈希值，以供所有人查閱。優(yōu)點(diǎn)：報(bào)價(jià)的哈希值將競(jìng)拍者與他們的原始報(bào)價(jià)綁在了一起，而且無(wú)需揭示有關(guān)報(bào)價(jià)自身的任何信息。如果率先提交一個(gè)報(bào)價(jià)的哈希值并無(wú)什么不利因素，并且一旦提交了報(bào)價(jià)的哈希值，便再?zèng)]有任何辦法能夠改變報(bào)價(jià)，那么這個(gè)方案防止了如前所述的欺騙，缺陷：它可能會(huì)遭受前向檢索攻擊235.8.1網(wǎng)上競(jìng)價(jià)假設(shè)有一個(gè)物品在網(wǎng)上拍賣(mài)，而Alice、B5.8.2垃圾郵件減阻假如M為電子郵件消息，T為當(dāng)前時(shí)間。電子郵件消息M包含了發(fā)送方和目標(biāo)接收方的電子郵件地址，但是并不包含任何其他的地址。消息M的發(fā)送方必須確定一個(gè)值R，使得下式成立：

也就是說(shuō)，發(fā)送方必須找到一個(gè)值R，使得上面等式中哈希運(yùn)算的輸出結(jié)果中前N個(gè)二進(jìn)制位都是0。一旦完成了這一步，發(fā)送方就發(fā)送三元組(M,R,T)。在接收方Alice接受該郵件之前，她需要驗(yàn)證時(shí)間T是否在不久之前，以及驗(yàn)證h(M,R,T)是否以N個(gè)0開(kāi)始。平均而言，發(fā)送方就需要執(zhí)行大約2N次哈希計(jì)算。而無(wú)論N的長(zhǎng)度是多少，接收方只需執(zhí)行一次哈希計(jì)算便能夠驗(yàn)證h(M,R,T)是否以N個(gè)0開(kāi)始。為使這個(gè)設(shè)計(jì)行之有效，我們需要選擇一個(gè)N，使得相應(yīng)的計(jì)算開(kāi)銷(xiāo)處于常規(guī)的電子郵件用戶(hù)能夠接受的水平，但其成本又高到了垃圾郵件發(fā)送者無(wú)法忍受的程度。245.8.2垃圾郵件減阻假如M為電子郵件消息，T為當(dāng)前時(shí)間。5.9其他與加密相關(guān)的主題Shamir的秘密共享機(jī)制有關(guān)視覺(jué)的加密技術(shù)隨機(jī)性問(wèn)題信息隱藏255.9其他與加密相關(guān)的主題Shamir的秘密共享機(jī)制255.9.1秘密共享問(wèn)題？假設(shè)Alice和Bob想要共享一個(gè)秘密信息S，以實(shí)現(xiàn)如下的效果：Alice或者Bob(當(dāng)然也包括其他的任何人)都不能獨(dú)自確定信息S，除了瞎猜，再無(wú)更好的辦法。Alice和Bob在一起，就能夠輕松地確定該信息S秘密共享機(jī)制因?yàn)槠渲杏袃蓚€(gè)參與者，而且雙方必須協(xié)同合作才能恢復(fù)出秘密信息S。26兩點(diǎn)決定一條直線5.9.1秘密共享問(wèn)題？26兩點(diǎn)決定一條直線假設(shè)秘密信息S是一個(gè)實(shí)數(shù)。通過(guò)點(diǎn)(0,S)在平面上畫(huà)一條直線L，并給Alice指定直線L上的一點(diǎn)A=(X0,Y0)，給Bob指定直線L上的另一點(diǎn)B=(X1,Y1)。這樣，Alice和Bob各自都不掌握關(guān)于S的任何信息，因?yàn)橥ㄟ^(guò)一個(gè)獨(dú)立的點(diǎn)存在無(wú)限多的直線。但是，合在一起，兩個(gè)點(diǎn)A和B唯一確定了直線L，這樣就能夠確定在Y軸上的截距，于是進(jìn)而就獲得了值S。27“moutofn”型的秘密共享機(jī)制：即對(duì)于任何的m≤n，其中n代表參與者的數(shù)量，那么其中任意的m個(gè)參與者合作，就能夠恢復(fù)出共享的秘密。假設(shè)秘密信息S是一個(gè)實(shí)數(shù)。通過(guò)點(diǎn)(0,S)在平面上畫(huà)一條直一條直線是一個(gè)一次多項(xiàng)式，它可以由兩點(diǎn)唯一確定。一條拋物線是一個(gè)二次多項(xiàng)式，它可以由三個(gè)點(diǎn)唯一確定。一般而言，一個(gè)次數(shù)為m–1的多項(xiàng)式可以由m個(gè)點(diǎn)唯一確定。對(duì)于任意的m≤n，正是上述基本事實(shí)使得我們能夠構(gòu)造出一個(gè)“moutofn”型的秘密共享機(jī)制。28一條直線是一個(gè)一次多項(xiàng)式，它可以由兩點(diǎn)唯一確定。285.9.1.1密鑰托管如何解決密鑰托管機(jī)構(gòu)的信任問(wèn)題？通過(guò)擁有多個(gè)托管機(jī)構(gòu)，并允許用戶(hù)將其密鑰在這些托管機(jī)構(gòu)中的n個(gè)之間進(jìn)行分割，使得必須得有n個(gè)托管機(jī)構(gòu)中的m個(gè)協(xié)同合作才能恢復(fù)出密鑰。Shamir的秘密共享機(jī)制可以用于實(shí)現(xiàn)這樣的一個(gè)密鑰托管方案。假設(shè)N=3和m=2，Alice的密鑰是S。使用“2outof3”方案即可。比如，Alice可能會(huì)選擇讓司法部持有點(diǎn)(X0,Y0)，讓商務(wù)部持有點(diǎn)(X1,Y1)，再讓Fred的密鑰托管公司持有點(diǎn)(X2,Y2),。于是，這三個(gè)托管機(jī)構(gòu)中必須至少有兩個(gè)協(xié)同合作才能確定Alice的密鑰S。295.9.1.1密鑰托管如何解決密鑰托管機(jī)構(gòu)的信任問(wèn)題？295.9.1.2視覺(jué)加密技術(shù)視覺(jué)秘密共享機(jī)制該機(jī)制是絕對(duì)安全的。在視覺(jué)秘密共享機(jī)制(也被稱(chēng)作視覺(jué)加密技術(shù))中，解密潛在的圖像并不需要執(zhí)行任何計(jì)算。例子：像素分解30如果某個(gè)特定像素是白色，我們可以通過(guò)拋硬幣的方式來(lái)決定是使用圖中的“a”行還是“b”行。對(duì)于一個(gè)黑色像素，我們通過(guò)拋硬幣來(lái)在“c”行和“d”行之間選擇，然后再使用被選定的行來(lái)確定相應(yīng)的像素部分。5.9.1.2視覺(jué)加密技術(shù)視覺(jué)秘密共享機(jī)制30如果某個(gè)特定如果原始的像素是黑色的，那么其分解的兩份重疊之后總是生成一個(gè)黑色像素。而如果原始的像素是白色的，那么其分解的兩份重疊之后將生成一個(gè)半白半黑的像素，這將被視覺(jué)感知為灰色。這個(gè)結(jié)果會(huì)損失一定的對(duì)比度(黑和灰相對(duì)于黑和白)，但是，原始的圖像仍然可以清晰地辨別。視覺(jué)秘密共享的例子是一個(gè)“2outof2”型的共享方案31如果原始的像素是黑色的，那么其分解的兩份重疊之后總是生成一個(gè)5.9.2隨機(jī)數(shù)在加密技術(shù)領(lǐng)域，生成對(duì)稱(chēng)密鑰、生成RSA密鑰對(duì)(意即隨機(jī)選取大素?cái)?shù))以及生成Diffie-Hellman的秘密指數(shù)，這些都需要隨機(jī)數(shù)。加密技術(shù)中的隨機(jī)數(shù)必須不僅是統(tǒng)計(jì)上隨機(jī)的，而且它們還必須要滿(mǎn)足嚴(yán)格得多的條件——它們必須是不可預(yù)測(cè)的。常用的偽隨機(jī)數(shù)生成器就是可預(yù)測(cè)的，即給定足夠大數(shù)量的輸出值，后續(xù)的值將能夠被很容易地確定。所以，偽隨機(jī)數(shù)生成器不適用于加密類(lèi)應(yīng)用。

假設(shè)有個(gè)服務(wù)器專(zhuān)門(mén)為用戶(hù)生成對(duì)稱(chēng)密鑰，并假設(shè)它為一系列用戶(hù)生成了如下的密鑰：KA

給Alice使用KB

給Bob使用KC

給Charlie使用KD

給Dave使用現(xiàn)在如果Alice、Bob和Charlie都不喜歡Dave，他們就可以將他們的這些信息放在一起，看看是否有助于確定Dave的密鑰。即Alice、Bob和Charlie可以利用對(duì)于他們自己的密鑰KA、KB和KC的理解，來(lái)考慮這些信息是否有助于確定出Dave的密鑰KD。如果能夠根據(jù)對(duì)于密鑰KA、KB和KC的了解來(lái)預(yù)測(cè)KD，那么該系統(tǒng)的安全性是有缺陷的。325.9.2隨機(jī)數(shù)在加密技術(shù)領(lǐng)域，生成對(duì)稱(chēng)密鑰、生成RSA密5.9.2.1德州撲克規(guī)則首先給每個(gè)玩家發(fā)兩張牌，正面朝下扣起來(lái)作為底牌。然后完成一輪投注。接下來(lái)，翻開(kāi)三張公共牌——所有玩家都可以看到公共牌，并可以考慮與他們自己手中的牌結(jié)合使用。進(jìn)行第二輪投注之后，再次翻開(kāi)一張公共牌，隨后再進(jìn)行一輪投注。最后，翻開(kāi)最后的一張公共牌，這之后還可以再加投一次注。在所有保持持續(xù)跟進(jìn)到最后的玩家中，誰(shuí)能夠從自己手里的兩張底牌和翻開(kāi)的5張公共牌中組成最好的一手牌，誰(shuí)就是獲勝者。ASF公司開(kāi)發(fā)的撲克牌游戲軟件在運(yùn)用隨機(jī)數(shù)來(lái)洗一副牌的時(shí)候，隨機(jī)數(shù)的使用方式中有一個(gè)嚴(yán)重的缺陷：這個(gè)程序無(wú)法產(chǎn)生一個(gè)真正隨機(jī)的洗牌結(jié)果，于是在游戲中，玩家就有可能實(shí)時(shí)地確定整副牌的情況。335.9.2.1德州撲克規(guī)則33如何實(shí)時(shí)地就確定洗牌的結(jié)果呢？對(duì)于一幅含有52張牌的撲克來(lái)說(shuō)，共有52!>2225種不同的洗牌結(jié)果。AFS公司的德州撲克程序中使用了一個(gè)“隨機(jī)的”32位二進(jìn)制整數(shù)來(lái)確定洗牌的結(jié)果。因此，在2225種所有可能的洗牌結(jié)果中，這個(gè)程序就不可能產(chǎn)生多于其中232種不同的洗牌結(jié)果。這是一個(gè)不可原諒的設(shè)計(jì)缺陷！為了生成“隨機(jī)的”洗牌結(jié)果，該程序使用了偽隨機(jī)數(shù)生成器或簡(jiǎn)稱(chēng)為PRNG。在每次洗牌時(shí)，該偽隨機(jī)數(shù)生成器都會(huì)基于新的種子值，但種子值基于一個(gè)已知的函數(shù)，即其值為自午夜0點(diǎn)以來(lái)所經(jīng)歷的毫秒數(shù)。因?yàn)樵谝惶熘邪暮撩霐?shù)為實(shí)際上就會(huì)使得最后能夠產(chǎn)生的不同洗牌結(jié)果的數(shù)量小于227。攻擊者Trudy將她的時(shí)鐘與服務(wù)器進(jìn)行同步，她就有可能將需要檢測(cè)的不同洗牌結(jié)果的數(shù)量降低為小于218。事實(shí)上，當(dāng)?shù)谝惠喌墓才平視灾螅琓rudy就能夠唯一確定洗牌結(jié)果了，于是她就能夠知道其他所有玩家最終整手牌的情況。34如何實(shí)時(shí)地就確定洗牌的結(jié)果呢？345.9.2.2隨機(jī)二進(jìn)制位的生成真正的隨機(jī)性不僅非常難以找到，而且非常難以界定。真正的隨機(jī)性的來(lái)源確實(shí)存在。例如，放射性衰變就是隨機(jī)的。但是，基于核放射技術(shù)的計(jì)算機(jī)肯定是不受歡迎的。隨機(jī)性的另一個(gè)來(lái)源是臭名昭著的熔巖燈，可以從其混沌行為中獲得隨機(jī)性。因?yàn)檐浖旧硎?也希望是)有確定性的，所以真正的隨機(jī)數(shù)必須產(chǎn)生于任何代碼之外。355.9.2.2隨機(jī)二進(jìn)制位的生成真正的隨機(jī)性不僅非常難以找5.9.3信息隱藏隱寫(xiě)術(shù)也叫隱藏書(shū)寫(xiě)，就是試圖隱藏特定信息被傳遞這一事實(shí)。隱寫(xiě)術(shù)有很長(zhǎng)的歷史，特別是在戰(zhàn)爭(zhēng)中很久之前就已經(jīng)在使用。現(xiàn)代版本的隱寫(xiě)術(shù)涉及在各種媒介中隱藏信息，這些媒介包括諸如圖像文件、音頻數(shù)據(jù)，甚至是軟件等。數(shù)字水印是為了某種不盡相同的目的而實(shí)施的信息隱藏。數(shù)字水印的分類(lèi)可以有很多種不同的方式。不可見(jiàn)水印——在媒介中是不應(yīng)該能被感知到的水印?？梢?jiàn)水印——設(shè)計(jì)上用于查閱的水印，如在一個(gè)文檔上打上“TOPSECRET”的標(biāo)記。魯棒水印——設(shè)計(jì)上用于保持其可讀性的水印，即使遭受了攻擊和破壞。敏感水印——設(shè)計(jì)為易損的水印，發(fā)生任何篡改都將導(dǎo)致破壞或損害365.9.3信息隱藏隱寫(xiě)術(shù)36不可見(jiàn)數(shù)字水印典型實(shí)例：將特定信息以某種方式插入到照片當(dāng)中，使得當(dāng)照片被破壞時(shí)，仍然有可能從原始照片所剩余的一小塊殘片中重新構(gòu)建出整張的圖像。例子：將要使用的圖像采用24位二進(jìn)制空域色彩分量表示方式——即對(duì)于紅色向量、綠色向量和藍(lán)色向量分別使用一個(gè)字節(jié)來(lái)表示，各自表示為R，G，B。由于低位的RGB值相對(duì)不重要，因?yàn)槠浯砹祟伾胁灰子X(jué)察到的細(xì)微變化。所以我們能夠?qū)⑦@些低二進(jìn)制位用于我們選定的其他用途，包括信息隱藏。37未包含任何隱藏的信息整本《愛(ài)麗絲夢(mèng)游仙境》的書(shū)(以PDF格式)嵌入在了RGB字節(jié)的低位中不可見(jiàn)數(shù)字水印37未包含任何隱藏的信息整本《愛(ài)麗絲夢(mèng)游仙境》假設(shè)一個(gè)HTML文件，該文件包含“海象與木匠”這首詩(shī)，在HTML中，RGB字體顏色以如下形式的標(biāo)簽所規(guī)定<fontcolor="#rrggbb">...</font>其中，rr是以十六進(jìn)制形式表示的R的值，gg是以十六進(jìn)制形式表示的G的值，bb是以十六進(jìn)制形式表示的B的值。既然R，G和B的低位信息不會(huì)影響到對(duì)顏色的感知，那么我們可以將信息隱藏在這些位中。讀取RGB色彩分量字節(jié)的低位就能夠生成“隱藏的”信息，即110010110011000101。38假設(shè)一個(gè)HTML文件，該文件包含“海象與木匠”這首詩(shī)，在HT魯棒性上述兩種方法均完全不具備魯棒性！因?yàn)槿魏我粋€(gè)了解該設(shè)計(jì)方案的攻擊者能夠和目標(biāo)接收者同樣容易地讀取其中隱藏的信息?；蛘吖粽呖梢該Q一種方式，通過(guò)將該文件替換為另一個(gè)文件，除了RGB字節(jié)的低位信息被完全隨機(jī)打亂之外，這個(gè)新的文件與原始的文件再?zèng)]有其他的不同，這樣就直接破壞了這些隱藏信息。但仍然面臨重重障礙和問(wèn)題！39對(duì)于信息隱藏來(lái)說(shuō)，要想具有魯棒性，信息必須放在有一定影響力的二進(jìn)制位上。但是，這就提出了一個(gè)嚴(yán)峻的挑戰(zhàn)，因?yàn)?，?duì)于這些確有影響力的二進(jìn)制位的改變必須要非常地小心謹(jǐn)慎，以便信息隱藏仍然能夠保持“不可見(jiàn)性”。魯棒性39對(duì)于信息隱藏來(lái)說(shuō)，要想具有魯棒性，信息必須放在有一5.10小結(jié)Tiger算法計(jì)算哈希MAC(HMAC)的正確方法秘密共享機(jī)制視覺(jué)加密技術(shù)隨機(jī)數(shù)信息隱藏技術(shù)405.10小結(jié)Tiger算法4041信息安全原理與實(shí)踐InformationSecurity:PrinciplesandPractice,2ndEdition[美]MarkStamp 著張戈 譯1信息安全原理與實(shí)踐InformationSecurity第5章哈希函數(shù)及其他42第5章哈希函數(shù)及其他25.1引言本章內(nèi)容加密哈希函數(shù)加密哈希函數(shù)的標(biāo)準(zhǔn)應(yīng)用哈希函數(shù)的高級(jí)應(yīng)用加密相關(guān)的副作用問(wèn)題435.1引言本章內(nèi)容35.2什么是加密哈希函數(shù)一個(gè)加密哈希函數(shù)h(x)，必須滿(mǎn)足下列所有條件：壓縮——對(duì)于任何長(zhǎng)度的輸入值x，輸出值y=h(x)的長(zhǎng)度都比較小。在實(shí)際使用中，通常輸出值是固定長(zhǎng)度的(比如160位長(zhǎng)度的二進(jìn)制值)，而無(wú)論輸入值的長(zhǎng)度是多少。高效——對(duì)于任何的輸入值x，必須能夠很容易地計(jì)算出h(x)。當(dāng)然，伴隨著輸入值x的長(zhǎng)度增加，計(jì)算h(x)所需要的計(jì)算量也會(huì)隨之增加，但是，這不能增長(zhǎng)得太快。單向——給定任意值y，要想找到一個(gè)值x，使得h(x)=y，將是計(jì)算不可行的。換一種不同的說(shuō)法，即對(duì)于哈希運(yùn)算，沒(méi)有行之有效的逆運(yùn)算?？谷跖鲎残浴o定x和h(x)，要想找到任意y，滿(mǎn)足y≠x，并且h(y)=h(x)，這是不可能的。抗強(qiáng)碰撞性——要想找到任意的x和y，使得x≠y，并且h(x)=h(y)，這是不可能的。也就是說(shuō)，我們不能夠找到任何兩個(gè)輸入，使得它們經(jīng)過(guò)哈希后會(huì)產(chǎn)生相同的輸出值。445.2什么是加密哈希函數(shù)一個(gè)加密哈希函數(shù)h(x)，必須滿(mǎn)足哈希函數(shù)在數(shù)字簽名上的應(yīng)用以前Alice對(duì)一條消息M實(shí)施簽名，是通過(guò)使用她自己的私鑰進(jìn)行“加密”計(jì)算得到的，即要計(jì)算S=[M]Alice。如果Alice發(fā)送消息M和簽名S給Bob，Bob就能夠通過(guò)執(zhí)行驗(yàn)證過(guò)程M={S}Alice來(lái)驗(yàn)證該簽名的有效性。但是，如果消息M很大，[M]Alice就是一個(gè)成本很高的計(jì)算，更不用提發(fā)送消息M和簽名S的帶寬需求了，這兩者都會(huì)很大。相比之下，在計(jì)算一個(gè)MAC時(shí)，加密的速度會(huì)很快，而且在發(fā)送時(shí)，我們也僅僅需要伴隨著消息發(fā)送少量附加的校驗(yàn)位(比如MAC)而已。使用哈希函數(shù)之后假設(shè)Alice有一個(gè)加密哈希函數(shù)h。那么，h(M)可以被看做文檔M的一個(gè)“指紋”，也就是說(shuō)，h(M)比M小得多，但是它能夠標(biāo)識(shí)出M。如果M'不同于M，那么即使僅僅相差一個(gè)單獨(dú)的二進(jìn)制位，哈希函數(shù)執(zhí)行的結(jié)果也幾乎肯定會(huì)不同。而且，哈希函數(shù)的抗碰撞特性意味著，想要將消息M替換為任何不同的消息M'，使得h(M)=h(M')是不可能的1.一旦哈希值發(fā)生相同的情況，該怎么辦呢？好的，這說(shuō)明你已經(jīng)發(fā)現(xiàn)了一個(gè)碰撞，也就意味著你已經(jīng)攻破了這個(gè)哈希函數(shù)，于是你就成為一個(gè)著名的密碼破解專(zhuān)家了。所以，這是個(gè)雙贏的好事。45哈希函數(shù)在數(shù)字簽名上的應(yīng)用5簽名的正確方法假設(shè)沒(méi)有碰撞，那么對(duì)h(M)簽名和對(duì)消息M實(shí)施簽名的效果一樣好。事實(shí)上，對(duì)哈希值實(shí)施簽名比起僅僅對(duì)消息本身實(shí)施簽名，實(shí)際上會(huì)更加安全。現(xiàn)在數(shù)字簽名的安全性不僅依賴(lài)于公鑰系統(tǒng)的安全性，而且也依賴(lài)于哈希函數(shù)本身的安全性——如果二者中有任何一個(gè)比較弱，簽名體制就可能會(huì)被破解。46簽名的正確方法65.3生日問(wèn)題假如你和其他N個(gè)人同在一個(gè)房間里。那么，N必須多大，你才有指望找到至少一個(gè)人和你有相同的生日呢？或者說(shuō)：N必須多大，才會(huì)使得“有某個(gè)人與你生日相同”的概率大于1/2呢？你的生日是在一年中特定的一天。如果一個(gè)人和你的生日不同，那么他或她的生日必定是在其他364天中的一天。假設(shè)所有的生日都是概率相等的，那么“一個(gè)隨機(jī)選擇的人不與你的生日相同”的概率就是364/365。這樣，所有的N個(gè)人都跟你的生日不同的概率就是(364/365)N，于是，至少有一個(gè)人與你的生日相同的概率就是：設(shè)置這個(gè)表達(dá)式等于1/2，并解出N，得到N=253。475.3生日問(wèn)題假如你和其他N個(gè)人同在一個(gè)房間里。那么，N必真正的生日問(wèn)題我們給房間里的N個(gè)人分別編上號(hào)碼1，2，3，…，N。編號(hào)為1的人的生日是一年365天中的一天。如果所有人的生日各不相同，那么編號(hào)為2的人必須與編號(hào)為1的人的生日不相同，也就是說(shuō)，編號(hào)為2的人的生日只能是剩余的364天中的任意一天。同樣，編號(hào)為3的人的生日只能是再剩余的363天中的任意一天，依此類(lèi)推。假設(shè)所有的生日都是概率相等的，考慮上述情況的補(bǔ)集，其最后的概率計(jì)算如下式所示設(shè)置這個(gè)表達(dá)式等于1/2，并解出N，我們得到N=2348生日悖論真正的生日問(wèn)題8生日延伸對(duì)于一個(gè)生成N位二進(jìn)制長(zhǎng)度輸出的安全哈希函數(shù)來(lái)說(shuō)，一個(gè)計(jì)算開(kāi)銷(xiāo)大約以2N/2為因子的強(qiáng)力破解方式，就能夠?qū)ζ浒l(fā)起有效的攻擊。相比較而言，對(duì)于一個(gè)密鑰長(zhǎng)度為N位二進(jìn)制數(shù)的安全對(duì)稱(chēng)密鑰加密方案來(lái)說(shuō)，對(duì)其強(qiáng)力破解的計(jì)算開(kāi)銷(xiāo)的因子是2N-l。所以，安全哈希函數(shù)的輸出必須是對(duì)稱(chēng)加密密鑰二進(jìn)制位數(shù)的大約兩倍長(zhǎng)，才能夠獲得與后者基本相當(dāng)?shù)陌踩健?9延伸95.4生日攻擊假設(shè)哈希函數(shù)h生成一個(gè)n位二進(jìn)制長(zhǎng)的輸出。Trudy原則上能夠發(fā)起一次生日攻擊，具體如下：Trudy選擇一條“惡意”消息E，這是她想讓Alice簽名的消息，但是Alice并不想對(duì)其簽名。Trudy也創(chuàng)建了一條無(wú)害的消息I，她有信心Alice愿意對(duì)這條消息簽名。然后，Trudy通過(guò)對(duì)消息實(shí)施較小的編輯性修改，生成2n/2條該無(wú)害消息I的變體。這些無(wú)害的消息，我們分別標(biāo)識(shí)為Ii，其中i=0,1,...,2n/2–1，所有消息都與I的含義相同，但是既然消息本身不同，那么它們的哈希值也不一樣。同樣，Trudy創(chuàng)建出2n/2個(gè)惡意消息E的變體，分別標(biāo)識(shí)為Ei，其中i=0,1,...,2n/2–1。這些消息也都與原始的惡意消息E表達(dá)同樣的含義，但是它們的哈希值不一樣。Trudy對(duì)所有的惡意消息Ei以及所有的無(wú)害消息Ii實(shí)施哈希運(yùn)算。根據(jù)上述生日問(wèn)題的討論，她就有希望找到一個(gè)碰撞，比方說(shuō)，h(Ej)=h(Ik)?；谶@樣的一個(gè)碰撞，Trudy將Ik發(fā)送給Alice，并請(qǐng)Alice對(duì)其進(jìn)行簽名。既然這條消息看起來(lái)沒(méi)有問(wèn)題，Alice就對(duì)其進(jìn)行簽名，并將Ik和[h(Ik)]Alice返回給Trudy。既然h(Ej)=h(Ik)，那么由此可以得出[h(Ej)]Alice=[h(Ik)]Alice，于是，Trudy實(shí)際上就已經(jīng)獲得了Alice對(duì)惡意消息Ej的簽名。505.4生日攻擊假設(shè)哈希函數(shù)h生成一個(gè)n位二進(jìn)制長(zhǎng)的輸出。T在這個(gè)攻擊中，Trudy獲得了Alice對(duì)于一條Trudy自選消息的簽名，但是并沒(méi)有以任何方式攻擊潛在的公開(kāi)密鑰加密系統(tǒng)。這個(gè)攻擊是一個(gè)針對(duì)哈希函數(shù)h的強(qiáng)力攻擊，而哈希函數(shù)h是用于計(jì)算數(shù)字簽名的。為了防止此類(lèi)攻擊，我們可以選擇一個(gè)哈希函數(shù)，使得該哈希函數(shù)的輸出值的長(zhǎng)度n足夠大，以至于Trudy無(wú)法完成2n/2個(gè)哈希值的計(jì)算。51在這個(gè)攻擊中，Trudy獲得了Alice對(duì)于一條Trudy自5.5非加密哈希非加密哈希運(yùn)算的例子（1）其中，每個(gè)Xi是一個(gè)字節(jié)，定義哈希函數(shù)h(X)為：這毫無(wú)疑問(wèn)提供了壓縮功能，因?yàn)槿魏伍L(zhǎng)度的輸入都被壓縮為8位二進(jìn)制的輸出。但是，這個(gè)哈希很容易被破解，因?yàn)樯諉?wèn)題的結(jié)論告訴我們，只需對(duì)24=16個(gè)隨機(jī)選擇的輸入執(zhí)行哈希運(yùn)算，我們就有望找到一個(gè)碰撞。對(duì)兩個(gè)字節(jié)進(jìn)行互換，就總是能夠產(chǎn)生一個(gè)碰撞，類(lèi)似如下這種情況：（2）我們將哈希函數(shù)h(X)定義為：雖然該函數(shù)在交換輸入字節(jié)順序的情況下能夠輸出不同的結(jié)果，但是仍然逃不過(guò)生日問(wèn)題帶來(lái)的麻煩。525.5非加密哈希非加密哈希運(yùn)算的例子12循環(huán)冗余校驗(yàn)，或簡(jiǎn)稱(chēng)為CRC循環(huán)冗余校驗(yàn)碼的計(jì)算本質(zhì)上是長(zhǎng)除法，將余數(shù)作為CRC計(jì)算的“哈?！敝?。與常規(guī)的長(zhǎng)除法不同，CRC在計(jì)算中使用XOR運(yùn)算替代了減法。在一個(gè)CRC的計(jì)算過(guò)程中，除數(shù)被指定作為算法的一部分，數(shù)據(jù)作為被除數(shù)。例子假設(shè)給定的除數(shù)是10011，而有趣的是數(shù)據(jù)恰好是10101011。那么，我們先對(duì)數(shù)據(jù)附加上4個(gè)0(附加的位數(shù)要比除數(shù)的二進(jìn)制位數(shù)少1)，然后執(zhí)行如下長(zhǎng)除法運(yùn)算：CRC校驗(yàn)和就是長(zhǎng)除法運(yùn)算的余數(shù)——在這個(gè)例子中，就是1010。53循環(huán)冗余校驗(yàn)，或簡(jiǎn)稱(chēng)為CRC135.6TigerHashMD5MD指的是消息摘要(MessageDigest)，它的前身是MD4，而MD4本身又繼承自MD2。所有的MD系列算法都是由加密領(lǐng)域的大師級(jí)人物RonRivest所發(fā)明。MD5算法生成128位的輸出值。SHA-1算法SHA表示安全哈希算法(SecureHashAlgorithm)，是美國(guó)政府的一個(gè)標(biāo)準(zhǔn)。SHA-1算法實(shí)際上非常類(lèi)似于MD5算法。兩個(gè)算法在實(shí)踐中的主要不同在于SHA-1生成160位二進(jìn)制長(zhǎng)的輸出值，比MD5提供了更可觀的安全邊際。54所謂雪崩效應(yīng)，是所有加密哈希函數(shù)都會(huì)追求的一個(gè)理想特性。其目標(biāo)是：在輸入值中任何小的變化，都應(yīng)該級(jí)聯(lián)傳遞并導(dǎo)致輸出結(jié)果較大的變化——就像雪崩一樣。理想情況下，任何輸入值的變化引發(fā)的輸出值變化都是不相關(guān)的，這樣，攻擊者將不得不實(shí)施窮舉式檢索來(lái)尋找碰撞。5.6TigerHashMD514所謂雪崩效應(yīng)，是所有加Tiger算法特點(diǎn)算法的輸入先被分成512位二進(jìn)制長(zhǎng)度的分組，如果需要的話，就對(duì)輸入值進(jìn)行附加填充位，以補(bǔ)足成512的倍數(shù)位的長(zhǎng)度。算法輸出192位二進(jìn)制長(zhǎng)度的哈希值。算法實(shí)現(xiàn)中使用了4個(gè)S-box，這4個(gè)S-box的每一個(gè)都將8位二進(jìn)制位映射為64位。算法還使用了一個(gè)“密鑰調(diào)度”的算法，不過(guò)由于這里沒(méi)有密鑰的概念，該算法實(shí)際是施加到了輸入分組上。55Tiger算法特點(diǎn)15Tiger算法的過(guò)程首先對(duì)輸入值X進(jìn)行附加填充位，使其長(zhǎng)度滿(mǎn)足512位二進(jìn)制長(zhǎng)的倍數(shù)，表示為：，其中每一個(gè)Xi都是一個(gè)512位二進(jìn)制長(zhǎng)的分組。對(duì)每一個(gè)Xi使用一個(gè)外層的輪運(yùn)算。假設(shè)a，b和c都是64位二進(jìn)制長(zhǎng)的值。對(duì)于第一輪運(yùn)算，(a,b,c)的初始值以16進(jìn)制形式表示如下：56Tiger算法的過(guò)程16一輪運(yùn)算之后，輸出的(a,b,c)就成為后續(xù)下一輪運(yùn)算的初始三元組。最后一輪運(yùn)算之后，最終輸出的(a,b,c)就是192位二進(jìn)制長(zhǎng)的哈希值。首個(gè)外層輪函數(shù)F5的輸入是(a,b,c)，如果我們標(biāo)記F5的輸出為(a,b,c)，那么F7的輸入為(c,a,b)。同樣地，如果我們標(biāo)記F7的輸出為(a,b,

c)，那么F9的輸入為(b,c,a)。上圖的每一個(gè)函數(shù)Fm都包含了8個(gè)下圖所示的內(nèi)層輪運(yùn)算。我們?cè)倭頦表示內(nèi)層輪運(yùn)算的512位二進(jìn)制的輸入值，其可以表示如下57一輪運(yùn)算之后，輸出的(a,b,c)就成為后續(xù)下一輪運(yùn)算的對(duì)于函數(shù)fm,i，當(dāng)i=0,1,2,...,7時(shí)，其各自的輸入值分別如下其中各自對(duì)應(yīng)的函數(shù)fm,i-1的輸出標(biāo)記為(a,b,c)。每一個(gè)fm,i都依賴(lài)于a，b，c，wi和m，其中wi是512位二進(jìn)制輸入值W的第i個(gè)64位子分組。c寫(xiě)作：

，其中每一個(gè)ci都是一個(gè)單獨(dú)的字節(jié)。fm,i由下式給定：每一個(gè)Si都是一個(gè)S-box(即查找表)，將8位二進(jìn)制映射為64位二進(jìn)制。58對(duì)于函數(shù)fm,i，當(dāng)i=0,1,2,...,7時(shí)，其密鑰調(diào)度算法假設(shè)令W為密鑰調(diào)度算法的512位二進(jìn)制輸入值。同上，我們將W寫(xiě)作W=(w0,w1,…,w7)，其中每一個(gè)wi都是一個(gè)64位二進(jìn)制值，我們?cè)倭?/p>

為wi的二進(jìn)制補(bǔ)數(shù)。密鑰調(diào)度算法如下，其中最后的計(jì)算結(jié)果W=(w0,w1,…,w7)給出了該算法的輸出值。59密鑰調(diào)度算法19小結(jié)Tiger哈希算法共包含24輪運(yùn)算，這24輪運(yùn)算可以看成是3個(gè)外層輪運(yùn)算，而這每一個(gè)外層運(yùn)算都包含了8個(gè)內(nèi)層輪運(yùn)算。該算法所有的中間步驟產(chǎn)生的哈希值都是192位二進(jìn)制值。該算法中S-box的設(shè)計(jì)使得僅僅經(jīng)過(guò)24輪運(yùn)算中的3輪計(jì)算，每一個(gè)輸入的二進(jìn)制位就會(huì)影響到a，b和c三者中的每一個(gè)。而且，在消息中任何小的變化，都將影響到算法中間步驟產(chǎn)生的哈希值的多個(gè)二進(jìn)制位。在fm,i計(jì)算過(guò)程中，最后一步的乘法也是該算法設(shè)計(jì)中的一個(gè)關(guān)鍵特性。它的目的是為了確保，對(duì)于一輪運(yùn)算中每個(gè)S-box的輸入，都將在下一輪的運(yùn)算中混入到多個(gè)S-box中。60小結(jié)205.7HMACHMAC來(lái)源怎么才能將密鑰混入到所謂的HMAC中呢？將密鑰置于消息體之前，即計(jì)算h(K,M)假如我們選擇計(jì)算h(K,M)來(lái)得到HMAC。如果消息M=(B1,B2)，其中每個(gè)Bi都是512位二進(jìn)制長(zhǎng)，則如果Trudy選擇了M‘，使得M’=(M,X)，那么，Trudy有可能利用以上燈飾從h(K,M)找到h(K,M')。因?yàn)?，?duì)于特定長(zhǎng)度的K，M和X，有將密鑰附加于消息體之后，即計(jì)算h(M,K)61假如令B為哈希運(yùn)算的分組長(zhǎng)度，以字節(jié)數(shù)表示。對(duì)于所有流行的哈希算法B=64。ipad=0x36重復(fù)B次opad=0x5C重復(fù)B次那么，消息M的HMAC定義為：這個(gè)方案將密鑰徹底地混入到哈希運(yùn)算的結(jié)果當(dāng)中。計(jì)算一個(gè)HMAC值雖然需要執(zhí)行兩遍哈希運(yùn)算，但是第二次哈希運(yùn)算僅作用于少量的二進(jìn)制位并使用了修改的附加填充密鑰。所以，總開(kāi)銷(xiāo)比起計(jì)算h(M)所需要的開(kāi)銷(xiāo)，僅僅多了少許。更好5.7HMACHMAC來(lái)源21假如令B為哈希運(yùn)算的分組長(zhǎng)度5.8哈希函數(shù)的用途標(biāo)準(zhǔn)應(yīng)用身份認(rèn)證消息完整性保護(hù)(使用HMAC)消息指紋錯(cuò)誤檢測(cè)高效數(shù)字簽名等高級(jí)應(yīng)用網(wǎng)上競(jìng)價(jià)垃圾郵件減阻625.8哈希函數(shù)的用途標(biāo)準(zhǔn)應(yīng)用225.8.1網(wǎng)上競(jìng)價(jià)假設(shè)有一個(gè)物品在網(wǎng)上拍賣(mài)，而Alice、Bob以及Charlie都想要出價(jià)競(jìng)拍。每一個(gè)競(jìng)拍者都有一次機(jī)會(huì)提交一個(gè)秘密的報(bào)價(jià)，只有當(dāng)所有的報(bào)價(jià)都接收到之后，競(jìng)拍價(jià)格才會(huì)公開(kāi)。依照慣例，報(bào)價(jià)最高的競(jìng)拍者獲勝。前提：Alice、Bob以及Charlie，三人之間必然是互相不信任的，另外，他們也絕對(duì)都不會(huì)信任和接受競(jìng)投價(jià)格的網(wǎng)上服務(wù)。為了努力消除這些擔(dān)心，網(wǎng)上服務(wù)方提出了如下的方案：每一個(gè)競(jìng)拍者將確定他們各自的競(jìng)拍價(jià)格，比方說(shuō)，Alice出價(jià)為A，Bob出價(jià)為B，Charlie出價(jià)為C，各自確保其報(bào)價(jià)秘密。然后，Alice將提交h(A)，Bob將提交h(B)，Charlie將提交h(C)。一旦所有三個(gè)經(jīng)過(guò)哈希運(yùn)算的報(bào)價(jià)都已接收到，網(wǎng)上服務(wù)方就在線公開(kāi)發(fā)布這些哈希值，以供所有人查閱。優(yōu)點(diǎn)：報(bào)價(jià)的哈希值將競(jìng)拍者與他們的原始報(bào)價(jià)綁在了一起，而且無(wú)需揭示有關(guān)報(bào)價(jià)自身的任何信息。如果率先提交一個(gè)報(bào)價(jià)的哈希值并無(wú)什么不利因素，并且一旦提交了報(bào)價(jià)的哈希值，便再?zèng)]有任何辦法能夠改變報(bào)價(jià)，那么這個(gè)方案防止了如前所述的欺騙，缺陷：它可能會(huì)遭受前向檢索攻擊635.8.1網(wǎng)上競(jìng)價(jià)假設(shè)有一個(gè)物品在網(wǎng)上拍賣(mài)，而Alice、B5.8.2垃圾郵件減阻假如M為電子郵件消息，T為當(dāng)前時(shí)間。電子郵件消息M包含了發(fā)送方和目標(biāo)接收方的電子郵件地址，但是并不包含任何其他的地址。消息M的發(fā)送方必須確定一個(gè)值R，使得下式成立：

也就是說(shuō)，發(fā)送方必須找到一個(gè)值R，使得上面等式中哈希運(yùn)算的輸出結(jié)果中前N個(gè)二進(jìn)制位都是0。一旦完成了這一步，發(fā)送方就發(fā)送三元組(M,R,T)。在接收方Alice接受該郵件之前，她需要驗(yàn)證時(shí)間T是否在不久之前，以及驗(yàn)證h(M,R,T)是否以N個(gè)0開(kāi)始。平均而言，發(fā)送方就需要執(zhí)行大約2N次哈希計(jì)算。而無(wú)論N的長(zhǎng)度是多少，接收方只需執(zhí)行一次哈希計(jì)算便能夠驗(yàn)證h(M,R,T)是否以N個(gè)0開(kāi)始。為使這個(gè)設(shè)計(jì)行之有效，我們需要選擇一個(gè)N，使得相應(yīng)的計(jì)算開(kāi)銷(xiāo)處于常規(guī)的電子郵件用戶(hù)能夠接受的水平，但其成本又高到了垃圾郵件發(fā)送者無(wú)法忍受的程度。645.8.2垃圾郵件減阻假如M為電子郵件消息，T為當(dāng)前時(shí)間。5.9其他與加密相關(guān)的主題Shamir的秘密共享機(jī)制有關(guān)視覺(jué)的加密技術(shù)隨機(jī)性問(wèn)題信息隱藏655.9其他與加密相關(guān)的主題Shamir的秘密共享機(jī)制255.9.1秘密共享問(wèn)題？假設(shè)Alice和Bob想要共享一個(gè)秘密信息S，以實(shí)現(xiàn)如下的效果：Alice或者Bob(當(dāng)然也包括其他的任何人)都不能獨(dú)自確定信息S，除了瞎猜，再無(wú)更好的辦法。Alice和Bob在一起，就能夠輕松地確定該信息S秘密共享機(jī)制因?yàn)槠渲杏袃蓚€(gè)參與者，而且雙方必須協(xié)同合作才能恢復(fù)出秘密信息S。66兩點(diǎn)決定一條直線5.9.1秘密共享問(wèn)題？26兩點(diǎn)決定一條直線假設(shè)秘密信息S是一個(gè)實(shí)數(shù)。通過(guò)點(diǎn)(0,S)在平面上畫(huà)一條直線L，并給Alice指定直線L上的一點(diǎn)A=(X0,Y0)，給Bob指定直線L上的另一點(diǎn)B=(X1,Y1)。這樣，Alice和Bob各自都不掌握關(guān)于S的任何信息，因?yàn)橥ㄟ^(guò)一個(gè)獨(dú)立的點(diǎn)存在無(wú)限多的直線。但是，合在一起，兩個(gè)點(diǎn)A和B唯一確定了直線L，這樣就能夠確定在Y軸上的截距，于是進(jìn)而就獲得了值S。67“moutofn”型的秘密共享機(jī)制：即對(duì)于任何的m≤n，其中n代表參與者的數(shù)量，那么其中任意的m個(gè)參與者合作，就能夠恢復(fù)出共享的秘密。假設(shè)秘密信息S是一個(gè)實(shí)數(shù)。通過(guò)點(diǎn)(0,S)在平面上畫(huà)一條直一條直線是一個(gè)一次多項(xiàng)式，它可以由兩點(diǎn)唯一確定。一條拋物線是一個(gè)二次多項(xiàng)式，它可以由三個(gè)點(diǎn)唯一確定。一般而言，一個(gè)次數(shù)為m–1的多項(xiàng)式可以由m個(gè)點(diǎn)唯一確定。對(duì)于任意的m≤n，正是上述基本事實(shí)使得我們能夠構(gòu)造出一個(gè)“moutofn”型的秘密共享機(jī)制。68一條直線是一個(gè)一次多項(xiàng)式，它可以由兩點(diǎn)唯一確定。285.9.1.1密鑰托管如何解決密鑰托管機(jī)構(gòu)的信任問(wèn)題？通過(guò)擁有多個(gè)托管機(jī)構(gòu)，并允許用戶(hù)將其密鑰在這些托管機(jī)構(gòu)中的n個(gè)之間進(jìn)行分割，使得必須得有n個(gè)托管機(jī)構(gòu)中的m個(gè)協(xié)同合作才能恢復(fù)出密鑰。Shamir的秘密共享機(jī)制可以用于實(shí)現(xiàn)這樣的一個(gè)密鑰托管方案。假設(shè)N=3和m=2，Alice的密鑰是S。使用“2outof3”方案即可。比如，Alice可能會(huì)選擇讓司法部持有點(diǎn)(X0,Y0)，讓商務(wù)部持有點(diǎn)(X1,Y1)，再讓Fred的密鑰托管公司持有點(diǎn)(X2,Y2),。于是，這三個(gè)托管機(jī)構(gòu)中必須至少有兩個(gè)協(xié)同合作才能確定Alice的密鑰S。695.9.1.1密鑰托管如何解決密鑰托管機(jī)構(gòu)的信任問(wèn)題？295.9.1.2視覺(jué)加密技術(shù)視覺(jué)秘密共享機(jī)制該機(jī)制是絕對(duì)安全的。在視覺(jué)秘密共享機(jī)制(也被稱(chēng)作視覺(jué)加密技術(shù))中，解密潛在的圖像并不需要執(zhí)行任何計(jì)算。例子：像素分解70如果某個(gè)特定像素是白色，我們可以通過(guò)拋硬幣的方式來(lái)決定是使用圖中的“a”行還是“b”行。對(duì)于一個(gè)黑色像素，我們通過(guò)拋硬幣來(lái)在“c”行和“d”行之間選擇，然后再使用被選定的行來(lái)確定相應(yīng)的像素部分。5.9.1.2視覺(jué)加密技術(shù)視覺(jué)秘密共享機(jī)制30如果某個(gè)特定如果原始的像素是黑色的，那么其分解的兩份重疊之后總是生成一個(gè)黑色像素。而如果原始的像素是白色的，那么其分解的兩份重疊之后將生成一個(gè)半白半黑的像素，這將被視覺(jué)感知為灰色。這個(gè)結(jié)果會(huì)損失一定的對(duì)比度(黑和灰相對(duì)于黑和白)，但是，原始的圖像仍然可以清晰地辨別。視覺(jué)秘密共享的例子是一個(gè)“2outof2”型的共享方案71如果原始的像素是黑色的，那么其分解的兩份重疊之后總是生成一個(gè)5.9.2隨機(jī)數(shù)在加密技術(shù)領(lǐng)域，生成對(duì)稱(chēng)密鑰、生成RSA密鑰對(duì)(意即隨機(jī)選取大素?cái)?shù))以及生成Diffie-Hellman的秘密指數(shù)，這些都需要隨機(jī)數(shù)。加密技術(shù)中的隨機(jī)數(shù)必須不僅是統(tǒng)計(jì)上隨機(jī)的，而且它們還必須要滿(mǎn)足嚴(yán)格得多的條件——它們必須是不可預(yù)測(cè)的。常用的偽隨機(jī)數(shù)生成器就是可預(yù)測(cè)的，即給定足夠大數(shù)量的輸出值，后續(xù)的值將能夠被很容易地確定。所以，偽隨機(jī)數(shù)生成器不適用于加密類(lèi)應(yīng)用。

假設(shè)有個(gè)服務(wù)器專(zhuān)門(mén)為用戶(hù)生成對(duì)稱(chēng)密鑰，并假設(shè)它為一系列用戶(hù)生成了如下的密鑰：KA

給Alice使用KB

給Bob使用KC

給Charlie使用KD

給Dave使用現(xiàn)在如果Alice、Bob和Charlie都不喜歡Dave，他們就可以將他們的這些信息放在一起，看看是否有助于確定Dave的密鑰。即Alice、Bob和Charlie可以利用對(duì)于他們自己的密鑰KA、KB和KC