單向函數(shù)

散列算法是單向函數(shù)。也就是說(shuō)，它們接收一個(gè)明文字符串，將它轉(zhuǎn)換成一小段無(wú)法用來(lái)重建原始明文的密文。顯然，要使這種函數(shù)起作用，轉(zhuǎn)換中必需丟失一些數(shù)據(jù)。

乍聽(tīng)上去，單向函數(shù)似乎沒(méi)有用，因?yàn)槟鸁o(wú)法從單向計(jì)算的密文中找回明文。為什么要計(jì)算一個(gè)無(wú)法解開(kāi)的密碼呢？當(dāng)然，幾乎是單向的函數(shù)是非常有用的，因?yàn)閺谋举|(zhì)上講，所有的公鑰函數(shù)都是帶“天窗”的單向函數(shù)。公鑰密碼術(shù)的良好候選函數(shù)，是那些在一個(gè)方向上容易計(jì)算，而在另一個(gè)方向上除非您知道某些秘密否則極難計(jì)算的函數(shù)。因此，我們發(fā)現(xiàn)公鑰算法是基于因式分解和其它較難的數(shù)學(xué)竅門的。

散列函數(shù)
正如結(jié)果所表明，真正的單向函數(shù)也是有用的。這些函數(shù)通常叫做 散列函數(shù)，其結(jié)果通常稱為 密碼散列值、 密碼校驗(yàn)和、 密碼指紋或 消息摘要。此類函數(shù)在許多密碼協(xié)議中起著重要作用。

其構(gòu)思就是接收一段明文，然后以一種不可逆的方式將它轉(zhuǎn)換成一段（通常更小）密文。理論上，所有可能的明文將散列成一個(gè)唯一的密文，但實(shí)際上通常發(fā)生的不是那樣。大多數(shù)時(shí)候，幾乎有無(wú)窮多個(gè)不同的字符串可以產(chǎn)生完全相同的散列值。但是，對(duì)于一個(gè)好的密碼散列函數(shù)來(lái)說(shuō)，在實(shí)踐中應(yīng)該很難有兩個(gè)可理解的字符串散列相同的值。好的散列函數(shù)的另一個(gè)特性是輸出不以任何可辨認(rèn)的方式反映輸入。

散列函數(shù)通常產(chǎn)生恒定大小的摘要。許多算法產(chǎn)生很小的摘要，但是，算法的安全性很大程度上取決于結(jié)果摘要的大小。我們推薦選擇那些提供不小于 128 位摘要的算法。SHA-1 提供 160 位散列，是一種可以使用的好散列函數(shù)。

可以使用散列函數(shù)來(lái)確保數(shù)據(jù)完整性，這很象傳統(tǒng)的校驗(yàn)和。如果您公開(kāi)發(fā)布一個(gè)文檔的有規(guī)律密碼散列，則任何人都可以檢驗(yàn)該散列，假設(shè)他們知道散列算法的話。人們?cè)趯?shí)踐中使用的大多數(shù)散列算法是公開(kāi)發(fā)布和為人熟知的。再次提醒您，使用專用密碼算法，包括散列函數(shù)，通常是一個(gè)壞主意。

因特網(wǎng)分發(fā)
考慮一下分發(fā)在因特網(wǎng)上的軟件包的情況。在不遠(yuǎn)的過(guò)去，通過(guò) ftp 得到的軟件包是與校驗(yàn)和關(guān)聯(lián)的。其思想是下載軟件，然后運(yùn)行一個(gè)程序來(lái)計(jì)算您的校驗(yàn)和版本。然后可以將自行計(jì)算的校驗(yàn)和與 ftp 網(wǎng)站上得到的校驗(yàn)和相比較，以確定兩者匹配并確保傳輸連接上（over the wire）的數(shù)據(jù)完整性（各種各樣）。問(wèn)題是這種過(guò)時(shí)的方法根本就不加密。首先，有許多校驗(yàn)和技術(shù)可以惡意修改下載程序，并可能導(dǎo)致修改過(guò)的程序產(chǎn)生完全相同的校驗(yàn)和。其次，帶有其相關(guān)聯(lián)（保護(hù)極差）校驗(yàn)和的軟件包的“特洛伊”版本可以輕易地在 ftp 網(wǎng)站上發(fā)布。密碼散列函數(shù)可以用做老式校驗(yàn)和算法的隨便替代物。它們具有一個(gè)優(yōu)點(diǎn)，就是使篡改投遞代碼變得極其困難。

預(yù)先警告您 ― 這種分發(fā)方案還有一個(gè)問(wèn)題。如果作為軟件消費(fèi)者，不知何故下載了錯(cuò)誤的校驗(yàn)和，您會(huì)怎么辦？例如，假設(shè)我們分發(fā)了“xyzzy”軟件包。一天夜里，一些黑客闖入了分發(fā)機(jī)器，并將 xyzzy 軟件換成了一個(gè)稍作修改的版本，其中包含惡意的特洛伊木馬。攻擊者也將我們公開(kāi)分發(fā)的散列替換成帶有特洛伊副本的散列發(fā)行版。此時(shí)，當(dāng)某個(gè)無(wú)辜的用戶下載目標(biāo)軟件包時(shí)，將得到惡意的副本。受害者也下載了密碼校驗(yàn)和，并針對(duì)軟件包測(cè)試它。它進(jìn)行檢測(cè)，而惡意代碼看起來(lái)安全可供使用。顯然，如果我們不能確保散列本身不被修改，僅僅散列不能成為完整的解決方案。簡(jiǎn)而言之，我們需要一種認(rèn)證散列的方法。

認(rèn)證問(wèn)題

在我們考慮認(rèn)證問(wèn)題時(shí)，可能出現(xiàn)兩種情況。我們可能希望每種情況都可以驗(yàn)證散列。如果是這樣，我們可以使用基于 PKI 的數(shù)字簽名，這將在下面討論。或者，我們希望限定誰(shuí)能驗(yàn)證散列。例如，假設(shè)我們向 sci.crypt 新聞組發(fā)送了一封匿名信，其中投遞了一種專用加密算法的全部源代碼，但是希望只有我們最親密的朋友才能驗(yàn)證我們投遞了消息。可以使用消息認(rèn)證代碼（MAC）來(lái)達(dá)到這個(gè)目的。

消息認(rèn)證代碼

MAC 通過(guò)使用一種共享秘鑰起作用，接收方端使用它的一個(gè)副本。該密鑰可以用于認(rèn)證可疑數(shù)據(jù)。發(fā)送方必須擁有秘鑰的另一個(gè)副本。MAC 有幾種工作方式。第一種方式是在計(jì)算摘要之前，將秘鑰并置到數(shù)據(jù)末尾。如果沒(méi)有秘鑰，則無(wú)法確認(rèn)數(shù)據(jù)未經(jīng)改動(dòng)。另一種計(jì)算更復(fù)雜的方式是照常計(jì)算散列，然后再使用對(duì)稱算法（如 DES）加密散列。要認(rèn)證散列，必須首先對(duì)它解密。

MAC 在許多其它環(huán)境中也很有用。如果您希望不使用加密而實(shí)現(xiàn)基本消息認(rèn)證（也許是由于效率原因），MAC 是完成該任務(wù)的合適工具。即使您已經(jīng)使用了加密，MAC 也是一種確保加密位流在傳輸中免遭惡意修改的極佳方法。

如果仔細(xì)設(shè)計(jì)，好的 MAC 可以幫助解決其它公共協(xié)議問(wèn)題。許多協(xié)議在遭受所謂的 回放攻擊（或者 捕獲-回放攻擊）期間，明顯存在一個(gè)普遍問(wèn)題。假設(shè)我們向銀行發(fā)送一個(gè)請(qǐng)求，要求從我們的帳戶劃撥 50 美元到 John Doe 的銀行帳戶。如果 John Doe 攔截了通信，他可以稍后向銀行發(fā)送一個(gè)相同的消息副本！有時(shí)銀行會(huì)認(rèn)為我們發(fā)送了兩個(gè)請(qǐng)求。

回放攻擊

回放攻擊被證實(shí)是許多真實(shí)世界系統(tǒng)中的普遍問(wèn)題。幸好，我們可以使用 MAC 的巧妙用法來(lái)緩和這種情況。在銀行劃撥示例中，假設(shè)我們使用了一種隨秘鑰散列請(qǐng)求的原始 MAC。為了對(duì)付回放，我們可以確保散列永遠(yuǎn)不同。做到這一點(diǎn)的一個(gè)顯而易見(jiàn)的方法是使用時(shí)間戳記。

如果服務(wù)器發(fā)現(xiàn)一個(gè)請(qǐng)求的時(shí)間戳記過(guò)期（比如，超過(guò) 60 秒），它將拒絕請(qǐng)求。這或許足夠了，也可能還不夠，因?yàn)樗€是導(dǎo)致了一個(gè) 60 秒的窗口，其中回放攻擊可能 發(fā)生。您可能會(huì)考慮禁止在同一時(shí)間單元發(fā)生兩次請(qǐng)求，并緩存關(guān)于過(guò)去 60 秒以內(nèi)到達(dá)的有效請(qǐng)求的信息。如果您能夠處理這種特殊情況：在同一時(shí)間單元里兩次執(zhí)行了同一交易，則這種解決方案也許可行。但是存在更簡(jiǎn)單的解決方案。當(dāng)您計(jì)算 MAC 時(shí)，不僅散列數(shù)據(jù)和秘鑰，而且散列一個(gè)唯一、有序的序列號(hào)。遠(yuǎn)程主機(jī)只需要了解它所處理的最后一個(gè)序列號(hào)，并確保不處理比下一個(gè)預(yù)期序列號(hào)更舊的請(qǐng)求。這是普遍使用的方法。

在許多情況下，認(rèn)證其實(shí)不是問(wèn)題。例如，考慮使用密碼散列來(lái)認(rèn)證從控制臺(tái)登錄到機(jī)器的用戶。在許多系統(tǒng)中，當(dāng)用戶第一次輸入密碼時(shí)，實(shí)際上并沒(méi)有存儲(chǔ)密碼本身。相反，存儲(chǔ)了密碼的密碼散列。因?yàn)榇蠖鄶?shù)用戶覺(jué)得如果系統(tǒng)管理員不能隨意檢索他們的密碼會(huì)更好。假設(shè)操作系統(tǒng)是可信的（這是個(gè)可笑的大前提），我們可以假設(shè)我們的加密散列密碼的數(shù)據(jù)庫(kù)是正確的。當(dāng)用戶試圖登錄，并輸入密碼時(shí)，登錄程序散列它，并將新散列的密碼與存儲(chǔ)的散列比較。如果兩者相等，我們假設(shè)用戶輸入了正確密碼，則登錄繼續(xù)。

Telnet 協(xié)議

可惜，架構(gòu)設(shè)計(jì)師和開(kāi)發(fā)人員有時(shí)假設(shè)認(rèn)證機(jī)制的安全性實(shí)際上不是問(wèn)題，但實(shí)際上它是。例如，考慮一下 telnet 協(xié)議。大多數(shù) telnet 服務(wù)器接收用戶名密碼作為輸入。然后散列密碼，或執(zhí)行一些類似的轉(zhuǎn)換，然后將結(jié)果與本地?cái)?shù)據(jù)庫(kù)中的比較。問(wèn)題在于使用 telnet 協(xié)議時(shí)，密碼在網(wǎng)絡(luò)上以明文傳輸。任何能夠使用包嗅探器在網(wǎng)絡(luò)線路上偵聽(tīng)的人都可以發(fā)現(xiàn)密碼。telnet 認(rèn)證提供了很差的保護(hù)，潛在攻擊者可以輕易地清除保護(hù)。許多著名的協(xié)議（包括 FTP、POP3 和 IMAP 的多數(shù)版本）都具有類似的破綻百出的認(rèn)證機(jī)制。

其它攻擊

任何好的密碼散列算法應(yīng)該是這樣的，即使給定一個(gè)已知的消息和與它關(guān)聯(lián)的消息散列，也很難找到替代明文的重復(fù)散列。對(duì)沖突的故意搜索意味著蠻力攻擊，這通常很難。當(dāng)攻擊者希望用第二份明文文檔產(chǎn)生除了雜亂無(wú)意義的字符串之外的東西時(shí)，就尤其困難。

另一種對(duì)密碼散列的攻擊比平均蠻力攻擊容易實(shí)施得多。考慮下列情況：Alice 向 Bob 顯示了一份文檔和驗(yàn)證文檔的密碼散列，文檔內(nèi)容是 Alice 同意為每個(gè)小飾品付給 Bob 5 美元。Bob 不想在他的服務(wù)器中存儲(chǔ)該文檔，所以他只存儲(chǔ)了密碼散列。Alice 希望只為每個(gè)小飾品付 1 美元，所以她想創(chuàng)建第二份文檔，所產(chǎn)生的散列值和 5 美元的那份相同，然后告上法庭，控訴 Bob 多收了她的錢。當(dāng)她出庭時(shí)，Bob 將出示散列值，相信 Alice 的文檔不能散列出那個(gè)值，因?yàn)檫@不是她顯示給他的原始文檔。如果其攻擊是成功的，Alice 將能夠證明她所偽造的文檔確實(shí)散列出 Bob 存儲(chǔ)的值，法庭將判她勝訴。

但她是如何做到這一點(diǎn)的呢？Alice 使用了所謂的 生日攻擊。在這種攻擊中，她創(chuàng)建了兩份文檔，一份寫著每個(gè)小飾品 5 美元，另一份則寫著每個(gè)小飾品 1 美元。然后，在每份文檔中，她標(biāo)識(shí)出 n處可以進(jìn)行表面更改的地方（例如，那些可以用制表符取代空格的地方）。好的 n值通常是最終散列輸出的位長(zhǎng)度的一半加 1（所以如果我們指定散列輸出的位長(zhǎng)度為 m，則 n= m/2+1）。對(duì)于 64 位散列算法，她將在每份文檔中選擇 33 個(gè)地方。然后她反復(fù)嘗試每份文檔不同的排列，創(chuàng)建和存儲(chǔ)散列值。一般來(lái)說(shuō)，預(yù)計(jì)她將在散列了大約 2 m/2條消息之后找到散列出相同值的兩份文檔。這比蠻力攻擊要有效得多，如果使用蠻力攻擊，預(yù)計(jì)她必須散列的消息數(shù)為 2 m-1。如果 Alice 執(zhí)行一次成功的蠻力攻擊需要一百萬(wàn)年，那么她也許一周以內(nèi)就可以完成一次成功的生日攻擊。因此，Bob 應(yīng)該要求 Alice 使用一種算法，它所產(chǎn)生的摘要大小使得她不能在任何合理的時(shí)間之內(nèi)完成生日攻擊。

如果希望針對(duì)生日攻擊獲得和針對(duì)蠻力攻擊一樣的安全性，給定一個(gè)密鑰長(zhǎng)度為 p的對(duì)稱密碼，您應(yīng)該選擇提供大小為 p*2的摘要的散列算法。因此，對(duì)于具有很高安全性需求級(jí)別的應(yīng)用程序，要求散列算法產(chǎn)生 256 位甚或 512 位的消息摘要是個(gè)好主意。

什么是適用的好散列算法呢？

我們特別喜歡 SHA-1。Bruce Schneier 也推薦這個(gè)算法。但是如果散列長(zhǎng)度必需超過(guò) 160 位，SHA-1 還不夠。對(duì)于大位數(shù)散列，嘗試使用適合于執(zhí)行散列法的對(duì)稱加密術(shù)。GOST 散列算法是個(gè)好示例，它從 GOST 加密術(shù)派生而來(lái)，帶有 256 位的散列長(zhǎng)度。更長(zhǎng)的散列長(zhǎng)度很可能要求進(jìn)行一些編碼來(lái)適應(yīng)對(duì)稱加密術(shù)。Schneier 在 Applied Cryptography中概述了構(gòu)建此類算法的構(gòu)造。SHA-1 或 GOST 散列算法都沒(méi)有任何知識(shí)產(chǎn)權(quán)限制。

數(shù)字簽名

數(shù)字簽名背后的思想是模仿傳統(tǒng)手寫簽名。該思想是能夠以某種方式“簽署”一份數(shù)字文檔，該簽名具有和物理簽名一樣的法律效力。數(shù)字簽名至少必須和手寫簽名一樣好地滿足以下主要目的：

簽名應(yīng)該成為可靠性證明。它在一份文檔上的存在應(yīng)該使人信服，某人的簽名出現(xiàn)在某文檔上是他有意簽署的。
簽名應(yīng)該不可偽造。因此，在文檔上簽了名的人應(yīng)該不能聲明這簽名不是他們的。
在簽署文檔以后，應(yīng)該不可能不可檢測(cè)對(duì)文檔的更改，否則簽名可能是無(wú)效的。
簽名應(yīng)該不能移動(dòng)到另一份文檔。
即使對(duì)于手寫簽名，這些目標(biāo)也只是概念上的，并不能真正地反映現(xiàn)實(shí)。例如，偽造簽名是可能的，盡管很少有人技藝高超，真的能偽造。然而，簽名罕有濫用的傾向，這很好地保持了它在法庭的地位。總之，墨水簽名已經(jīng)是足夠好的解決方案。

電子簽名至少可以做得和物理簽名一樣好。這個(gè)事實(shí)經(jīng)常使人們吃驚，因?yàn)樗麄儗⑦@種簽名當(dāng)成是類似于人們經(jīng)常放置在電子郵件消息末尾的那種簽名文件（一串 ASCII）。如果數(shù)字簽名就是象這樣的，那么它們根本就沒(méi)什么用。很容易從一個(gè)文件復(fù)制簽名，并將它直接添加到另一個(gè)文件上以形成一個(gè)贗品。也可能輕易地修改一個(gè)經(jīng)過(guò)簽署的文檔，并且誰(shuí)也不能發(fā)現(xiàn)。謝天謝地，數(shù)字簽名完全不是這樣。

大多數(shù)數(shù)字簽名系統(tǒng)將公鑰密碼術(shù)和密碼散列算法結(jié)合使用。正如我們所解釋的，公鑰密碼系統(tǒng)經(jīng)常使用接收方公鑰來(lái)加密消息，然后接收方使用相應(yīng)的專用密鑰解密。專用密鑰也能用來(lái)對(duì)只能用相應(yīng)公鑰解密的消息進(jìn)行解密。如果某人將他的專用密鑰完全保持私有，（您最近沒(méi)有被黑，不是嗎？）能夠使用相應(yīng)公鑰解密消息，則構(gòu)成可疑的人對(duì)原始消息進(jìn)行加密的證明。

數(shù)字簽名不僅在簽署文檔的時(shí)候有用 — 它們幾乎可用于任何認(rèn)證需求。例如，它們經(jīng)常與加密聯(lián)合使用，以便保持?jǐn)?shù)據(jù)私有性和數(shù)據(jù)認(rèn)證。

用于文檔的數(shù)字簽名經(jīng)常由對(duì)文檔的加密散列構(gòu)成，然后用專用密鑰加密散列。結(jié)果密文稱為簽名。任何人都可以通過(guò)自行散列文檔，然后解密簽名（使用公鑰或共享秘鑰），并比較兩個(gè)散列來(lái)確認(rèn)簽名。如果兩個(gè)散列相等，則認(rèn)為簽名有效（假設(shè)進(jìn)行確認(rèn)的人相信他使用的公鑰確實(shí)屬于您）。

簽名不必隨文檔一起存儲(chǔ)。同樣，簽名適用于文檔的任何相同的數(shù)字副本。簽名也可以復(fù)制，但是無(wú)法使它適用于其它文檔，因?yàn)樽詈蟮玫降纳⒘信c解密散列不匹配。

數(shù)字簽名的問(wèn)題

數(shù)字簽名的一個(gè)問(wèn)題是認(rèn)可。人們總是可以聲明他們的密鑰被盜。但是，數(shù)字簽名還是作為物理簽名的合法替代廣泛地得到接受，因?yàn)樗鼈冎辽俸臀锢砗灻粯咏咏厦嫣岬降哪繕?biāo)。目前至少有 30 個(gè)州有數(shù)字簽名法律，并且更多州很可能立法（如果美國(guó)國(guó)會(huì)沒(méi)有搶先通過(guò)一項(xiàng)國(guó)家法律的話）。

大多數(shù)公鑰算法，包括 RSA 和 ElGamal，可以容易地?cái)U(kuò)展以支持?jǐn)?shù)字簽名。實(shí)際上，一個(gè)支持這些算法之一的好軟件包應(yīng)該也支持?jǐn)?shù)字簽名。我們推薦您將自己喜歡的公鑰密碼術(shù)算法用于數(shù)字簽名。嘗試使用內(nèi)置原語(yǔ)而不是拋開(kāi)加密算法和散列函數(shù)去構(gòu)建自己的構(gòu)造。

下一步是什么？

在未來(lái)最重要的主題是密鑰管理：如何安全地生成、存儲(chǔ)、更改、銷毀或傳遞加密密鑰？密碼術(shù)是一個(gè)巨大的領(lǐng)域，但又只是軟件安全性的一個(gè)方面。甚至我們也不能謊稱自己完全了解它。