單向函數
散列算法是單向函數。也就是說，它們接收一個明文字符串，將它轉換成一小段無法用來重建原始明文的密文。顯然，要使這種函數起作用，轉換中必需丟失一些數據。
乍聽上去，單向函數似乎沒有用，因為您無法從單向計算的密文中找回明文。為什么要計算一個無法解開的密碼呢？當然，幾乎是單向的函數是非常有用的，因為從本質上講，所有的公鑰函數都是帶“天窗”的單向函數。公鑰密碼術的良好候選函數，是那些在一個方向上容易計算，而在另一個方向上除非您知道某些秘密否則極難計算的函數。因此，我們發現公鑰算法是基于因式分解和其它較難的數學竅門的。
散列函數正如結果所表明，真正的單向函數也是有用的。這些函數通常叫做 散列函數，其結果通常稱為 密碼散列值、 密碼校驗和、 密碼指紋或 消息摘要。此類函數在許多密碼協議中起著重要作用。
其構思就是接收一段明文，然后以一種不可逆的方式將它轉換成一段（通常更小）密文。理論上，所有可能的明文將散列成一個唯一的密文，但實際上通常發生的不是那樣。大多數時候，幾乎有無窮多個不同的字符串可以產生完全相同的散列值。但是，對于一個好的密碼散列函數來說，在實踐中應該很難有兩個可理解的字符串散列相同的值。好的散列函數的另一個特性是輸出不以任何可辨認的方式反映輸入。
散列函數通常產生恒定大小的摘要。許多算法產生很小的摘要，但是，算法的安全性很大程度上取決于結果摘要的大小。我們推薦選擇那些提供不小于 128 位摘要的算法。SHA-1 提供 160 位散列，是一種可以使用的好散列函數。
可以使用散列函數來確保數據完整性，這很象傳統的校驗和。如果您公開發布一個文檔的有規律密碼散列，則任何人都可以檢驗該散列，假設他們知道散列算法的話。人們在實踐中使用的大多數散列算法是公開發布和為人熟知的。再次提醒您，使用專用密碼算法，包括散列函數，通常是一個壞主意。
因特網分發考慮一下分發在因特網上的軟件包的情況。在不遠的過去，通過 ftp 得到的軟件包是與校驗和關聯的。其思想是下載軟件，然后運行一個程序來計算您的校驗和版本。然后可以將自行計算的校驗和與 ftp 網站上得到的校驗和相比較，以確定兩者匹配并確保傳輸連接上（over the wire）的數據完整性（各種各樣）。問題是這種過時的方法根本就不加密。首先，有許多校驗和技術可以惡意修改下載程序，并可能導致修改過的程序產生完全相同的校驗和。其次，帶有其相關聯（保護極差）校驗和的軟件包的“特洛伊”版本可以輕易地在 ftp 網站上發布。密碼散列函數可以用做老式校驗和算法的隨便替代物。它們具有一個優點，就是使篡改投遞代碼變得極其困難。
預先警告您 ― 這種分發方案還有一個問題。如果作為軟件消費者，不知何故下載了錯誤的校驗和，您會怎么辦？例如，假設我們分發了“xyzzy”軟件包。一天夜里，一些黑客闖入了分發機器，并將 xyzzy 軟件換成了一個稍作修改的版本，其中包含惡意的特洛伊木馬。攻擊者也將我們公開分發的散列替換成帶有特洛伊副本的散列發行版。此時，當某個無辜的用戶下載目標軟件包時，將得到惡意的副本。受害者也下載了密碼校驗和，并針對軟件包測試它。它進行檢測，而惡意代碼看起來安全可供使用。顯然，如果我們不能確保散列本身不被修改，僅僅散列不能成為完整的解決方案。簡而言之，我們需要一種認證散列的方法。
認證問題在我們考慮認證問題時，可能出現兩種情況。我們可能希望每種情況都可以驗證散列。如果是這樣，我們可以使用基于 PKI 的數字簽名，這將在下面討論。或者，我們希望限定誰能驗證散列。例如，假設我們向 sci.crypt 新聞組發送了一封匿名信，其中投遞了一種專用加密算法的全部源代碼，但是希望只有我們最親密的朋友才能驗證我們投遞了消息。可以使用消息認證代碼（MAC）來達到這個目的。
消息認證代碼MAC 通過使用一種共享秘鑰起作用，接收方端使用它的一個副本。該密鑰可以用于認證可疑數據。發送方必須擁有秘鑰的另一個副本。MAC 有幾種工作方式。第一種方式是在計算摘要之前，將秘鑰并置到數據末尾。如果沒有秘鑰，則無法確認數據未經改動。另一種計算更復雜的方式是照常計算散列，然后再使用對稱算法（如 DES）加密散列。要認證散列，必須首先對它解密。
MAC 在許多其它環境中也很有用。如果您希望不使用加密而實現基本消息認證（也許是由于效率原因），MAC 是完成該任務的合適工具。即使您已經使用了加密，MAC 也是一種確保加密位流在傳輸中免遭惡意修改的極佳方法。如果仔細設計，好的 MAC 可以幫助解決其它公共協議問題。許多協議在遭受所謂的 回放攻擊（或者 捕獲-回放攻擊）期間，明顯存在一個普遍問題。假設我們向銀行發送一個請求，要求從我們的帳戶劃撥 50 美元到 John Doe 的銀行帳戶。如果 John Doe 攔截了通信，他可以稍后向銀行發送一個相同的消息副本！有時銀行會認為我們發送了兩個請求。
回放攻擊回放攻擊被證實是許多真實世界系統中的普遍問題。幸好，我們可以使用 MAC 的巧妙用法來緩和這種情況。在銀行劃撥示例中，假設我們使用了一種隨秘鑰散列請求的原始 MAC。為了對付回放，我們可以確保散列永遠不同。做到這一點的一個顯而易見的方法是使用時間戳記。
如果服務器發現一個請求的時間戳記過期（比如，超過 60 秒），它將拒絕請求。這或許足夠了，也可能還不夠，因為它還是導致了一個 60 秒的窗口，其中回放攻擊可能 發生。您可能會考慮禁止在同一時間單元發生兩次請求，并緩存關于過去 60 秒以內到達的有效請求的信息。如果您能夠處理這種特殊情況：在同一時間單元里兩次執行了同一交易，則這種解決方案也許可行。但是存在更簡單的解決方案。當您計算 MAC 時，不僅散列數據和秘鑰，而且散列一個唯一、有序的序列號。遠程主機只需要了解它所處理的最后一個序列號，并確保不處理比下一個預期序列號更舊的請求。這是普遍使用的方法。在許多情況下，認證其實不是問題。例如，考慮使用密碼散列來認證從控制臺登錄到機器的用戶。在許多系統中，當用戶第一次輸入密碼時，實際上并沒有存儲密碼本身。相反，存儲了密碼的密碼散列。因為大多數用戶覺得如果系統管理員不能隨意檢索他們的密碼會更好。假設操作系統是可信的（這是個可笑的大前提），我們可以假設我們的加密散列密碼的數據庫是正確的。當用戶試圖登錄，并輸入密碼時，登錄程序散列它，并將新散列的密碼與存儲的散列比較。如果兩者相等，我們假設用戶輸入了正確密碼，則登錄繼續。
Telnet 協議可惜，架構設計師和開發人員有時假設認證機制的安全性實際上不是問題，但實際上它是。例如，考慮一下 telnet 協議。大多數 telnet 服務器接收用戶名密碼作為輸入。然后散列密碼，或執行一些類似的轉換，然后將結果與本地數據庫中的比較。問題在于使用 telnet 協議時，密碼在網絡上以明文傳輸。任何能夠使用包嗅探器在網絡線路上偵聽的人都可以發現密碼。telnet 認證提供了很差的保護，潛在攻擊者可以輕易地清除保護。許多著名的協議（包括 FTP、POP3 和 IMAP 的多數版本）都具有類似的破綻百出的認證機制。
其它攻擊
任何好的密碼散列算法應該是這樣的，即使給定一個已知的消息和與它關聯的消息散列，也很難找到替代明文的重復散列。對沖突的故意搜索意味著蠻力攻擊，這通常很難。當攻擊者希望用第二份明文文檔產生除了雜亂無意義的字符串之外的東西時，就尤其困難。
另一種對密碼散列的攻擊比平均蠻力攻擊容易實施得多。考慮下列情況：Alice 向 Bob 顯示了一份文檔和驗證文檔的密碼散列，文檔內容是 Alice 同意為每個小飾品付給 Bob 5 美元。Bob 不想在他的服務器中存儲該文檔，所以他只存儲了密碼散列。Alice 希望只為每個小飾品付 1 美元，所以她想創建第二份文檔，所產生的散列值和 5 美元的那份相同，然后告上法庭，控訴 Bob 多收了她的錢。當她出庭時，Bob 將出示散列值，相信 Alice 的文檔不能散列出那個值，因為這不是她顯示給他的原始文檔。如果其攻擊是成功的，Alice 將能夠證明她所偽造的文檔確實散列出 Bob 存儲的值，法庭將判她勝訴。
但她是如何做到這一點的呢？Alice 使用了所謂的 生日攻擊。在這種攻擊中，她創建了兩份文檔，一份寫著每個小飾品 5 美元，另一份則寫著每個小飾品 1 美元。然后，在每份文檔中，她標識出 n處可以進行表面更改的地方（例如，那些可以用制表符取代空格的地方）。好的 n值通常是最終散列輸出的位長度的一半加 1（所以如果我們指定散列輸出的位長度為 m，則 n= m/2+1）。對于 64 位散列算法，她將在每份文檔中選擇 33 個地方。然后她反復嘗試每份文檔不同的排列，創建和存儲散列值。一般來說，預計她將在散列了大約 2 m/2條消息之后找到散列出相同值的兩份文檔。這比蠻力攻擊要有效得多，如果使用蠻力攻擊，預計她必須散列的消息數為 2 m-1。如果 Alice 執行一次成功的蠻力攻擊需要一百萬年，那么她也許一周以內就可以完成一次成功的生日攻擊。因此，Bob 應該要求 Alice 使用一種算法，它所產生的摘要大小使得她不能在任何合理的時間之內完成生日攻擊。
如果希望針對生日攻擊獲得和針對蠻力攻擊一樣的安全性，給定一個密鑰長度為 p的對稱密碼，您應該選擇提供大小為 p*2的摘要的散列算法。因此，對于具有很高安全性需求級別的應用程序，要求散列算法產生 256 位甚或 512 位的消息摘要是個好主意。
什么是適用的好散列算法呢？
我們特別喜歡 SHA-1。Bruce Schneier 也推薦這個算法。但是如果散列長度必需超過 160 位，SHA-1 還不夠。對于大位數散列，嘗試使用適合于執行散列法的對稱加密術。GOST 散列算法是個好示例，它從 GOST 加密術派生而來，帶有 256 位的散列長度。更長的散列長度很可能要求進行一些編碼來適應對稱加密術。Schneier 在 Applied Cryptography中概述了構建此類算法的構造。SHA-1 或 GOST 散列算法都沒有任何知識產權限制。
數字簽名背后的思想是模仿傳統手寫簽名。該思想是能夠以某種方式“簽署”一份數字文檔，該簽名具有和物理簽名一樣的法律效力。數字簽名至少必須和手寫簽名一樣好地滿足以下主要目的：
即使對于手寫簽名，這些目標也只是概念上的，并不能真正地反映現實。例如，偽造簽名是可能的，盡管很少有人技藝高超，真的能偽造。然而，簽名罕有濫用的傾向，這很好地保持了它在法庭的地位。總之，墨水簽名已經是足夠好的解決方案。
電子簽名至少可以做得和物理簽名一樣好。這個事實經常使人們吃驚，因為他們將這種簽名當成是類似于人們經常放置在電子郵件消息末尾的那種簽名文件（一串 ASCII）。如果數字簽名就是象這樣的，那么它們根本就沒什么用。很容易從一個文件復制簽名，并將它直接添加到另一個文件上以形成一個贗品。也可能輕易地修改一個經過簽署的文檔，并且誰也不能發現。謝天謝地，數字簽名完全不是這樣。
大多數數字簽名系統將公鑰密碼術和密碼散列算法結合使用。正如我們所解釋的，公鑰密碼系統經常使用接收方公鑰來加密消息，然后接收方使用相應的專用密鑰解密。專用密鑰也能用來對只能用相應公鑰解密的消息進行解密。如果某人將他的專用密鑰完全保持私有，（您最近沒有被黑，不是嗎？）能夠使用相應公鑰解密消息，則構成可疑的人對原始消息進行加密的證明。
數字簽名不僅在簽署文檔的時候有用 — 它們幾乎可用于任何認證需求。例如，它們經常與加密聯合使用，以便保持數據私有性和數據認證。
用于文檔的數字簽名經常由對文檔的加密散列構成，然后用專用密鑰加密散列。結果密文稱為簽名。任何人都可以通過自行散列文檔，然后解密簽名（使用公鑰或共享秘鑰），并比較兩個散列來確認簽名。如果兩個散列相等，則認為簽名有效（假設進行確認的人相信他使用的公鑰確實屬于您）。
簽名不必隨文檔一起存儲。同樣，簽名適用于文檔的任何相同的數字副本。簽名也可以復制，但是無法使它適用于其它文檔，因為最后得到的散列與解密散列不匹配。
數字簽名的問題數字簽名的一個問題是認可。人們總是可以聲明他們的密鑰被盜。但是，數字簽名還是作為物理簽名的合法替代廣泛地得到接受，因為它們至少和物理簽名一樣接近上面提到的目標。目前至少有 30 個州有數字簽名法律，并且更多州很可能立法（如果美國國會沒有搶先通過一項國家法律的話）。
大多數公鑰算法，包括 RSA 和 ElGamal，可以容易地擴展以支持數字簽名。實際上，一個支持這些算法之一的好軟件包應該也支持數字簽名。我們推薦您將自己喜歡的公鑰密碼術算法用于數字簽名。嘗試使用內置原語而不是拋開加密算法和散列函數去構建自己的構造。
下一步是什么？在未來最重要的主題是密鑰管理：如何安全地生成、存儲、更改、銷毀或傳遞加密密鑰？密碼術是一個巨大的領域，但又只是軟件安全性的一個方面。甚至我們也不能謊稱自己完全了解它。
