認識 PHP 的 Hashing Functions

阿恆

Hashing function (散列函式) 在網頁應用中被廣泛採用，從數碼簽署、錯誤檢測、登入驗證、到壓縮儲存空間，由於它的原理比較複雜，很多人把它跟加密函式混淆，對於如何運用 hash function，如何選擇合適的 hash function，和它的優點缺點都不清楚，本文嘗試解答這些問題。

Hashing 是甚麼？

簡單地說，Hashing 是一種數據影射 (mapping) 的算法 (algorithm)，通常用來把一大串不定長度的數據影射到一個固定長度的、較短的數據，這個固定長度的數據稱為 hashing value (散列值)。

例如我們把一個由英文字母組成的任意長度的字串，把每一個字符的 ASCII 數值加起來，最後除以 256 得到的餘數作為 hash value，這裏輸入的字串長度沒有限制，輸出的數值則必定在 0 至 255 之間，所以是一個合法的 hashing function。

以上的 hash function 只有 256 個可能的 hash value，很明顯有很多字串都會得到相同的 hash value，這種情況我們稱為 hash collision (散列衝突)，或者簡稱 collision，事實上從一個不定長度的數據影射到一個固定長度的數據，Collision 是無可避免的，我們並不要求完全沒有 collision，只需把 collision 的機會盡量降低便可以了，若果真的要完全沒有 collision 的話，Hash value 理論上必須與輸入的數據長度相同，這樣便違背了 hash function 的設計目的。

現實應用的 hashing function 通常比較複雜，比較有名的包括 MD4、MD5、SHA1、SHA256 等，它們的 hash value 的數量從 2 的幾十次方到幾百次方。其實我們任何人都可以自行設計一個 hashing function，不過基於 hashing function 的實際用途，我們對 hashing function 有一些基本要求，在進一步解釋前，讓我們看看 hashing 有甚麼常見的用途。

Hashing 的用途

  1. 數碼簽署很多提供程式下載的網站，都會在網頁上列出下載檔案的 hash value，比較常見的是 MD5 碼，下載的人可以自行計算下載回來的檔案的 hash value 是否與網站提供的相符，從而驗證這個程式是否曾經被修改，這個過程就是數碼簽署。數碼簽署的概念可以應用在很多通訊領域，例如你要發送一個很重要的電子郵件給別人，為了讓收件者放心內容在傳送過程中沒有被其他人擅改，你可以另外告訴收件人電子郵件的 MD5 碼，讓他自行驗證。在這種用途中，理想的 hashing function 應該具備兩種特性，首先是任何對原本文件的改動都會令產生的 hash value 改變；第二是沒有方法可以得知如何該動原本的文件使計算出來的 hash value 相同。當然，我們還要確保 hash value 不會在傳送途中被人攔截並且修改，但這屬於通訊安全的問題，超越了 hash function 的討論。

  2. 錯誤檢測資料在網絡上傳送的時候，會受到很多干擾而使內容改變，其中包括網絡問題、電腦硬件問題、電腦程式問題等，為了檢驗資料的正確性，我們可以一併把資料的 hash value 發送給收件者，讓收件者比對自行計算的 hash value 和收到的 hash value 來確認資料的正確性。在這種用途種中，理想的 hash function 跟上面的要求差不多，就是任何對原本資料的改動都會令產生的 hash value 改變。

  3. 登入驗證在伺服器上儲存用戶的系統密碼是有風險的，第一這樣做等於把密碼的安全交托給伺服器管理員，他們一定可靠嗎？別忘記密碼萬一洩漏背黑鑊的是你而不是他們啊；第二很多用戶把相同的密碼應用在很多不同的系統（這樣做當然很不好，但你無法限制用戶不可以這樣做），當一個系統被黑客入侵洩漏了用戶的密碼，他們在其他系統的帳號也同時中門大開，後果可以很嚴重。為了保障用戶，設計良好的系統都不會直接儲存用戶的密碼，只會儲存密碼的 hash value。用戶登入時輸入的密碼，會被轉換成 hash value，然後與伺服器上儲存的 hash value 比較來進行身分驗證。這種用途的 hash function，必須是不可能返過來從 hash value 計算原本的密碼。此外，由於 collision 的緣故，只要找到一個密碼，它的 hash value 與用戶的密碼的 hash value 相同，便可以冒認這名用戶登入系統，無須知道真正的密碼，所以 hash value 的數量必須非常龐大，使 collision 的可能性很低很低，使尋找這個「偽冒」密碼的人要付出很大的代價。

  4. 壓縮儲存空間Hash function 其中一個最經典的用途是製作 hashing table (散列表)，它可說是一個關聯陣列 (associative array)，陣列的指標是一些不定長度的數據或者是比較複雜的數據結構，很多高階編程語言包括 PHP、Perl、gawk 等都支援關連陣列，背後的原理就是利用 hash function 把這些數據轉換成數字，然後讀取陣列中的元素。在大部分的情況下，作為陣列指標的數據可以非常龐大，但是陣列的長度 (元素的數量) 相對來說卻很少，所以衝突的情況會比較突出，從用戶 (編程人員) 的角度衝突是不應該發生的，不同的數據便應該對應到不同的陣列位置，所以這些語言都有某些方法來處理衝突。用 hash table 來實作關聯陣列的好處是搜索資料的速度高，無論有多少資料，搜索的速度都是固定的，這一點對於要處理大量數據的應用很重要。

PHP 有甚麼 hashing 工具？

在 PHP5 之前我們只有 CRC32、MD5 和 SHA1 三個內置的 hash function，它們輸出的 hash value 長度如下：

其中 SHA-1 可說是最多人使用的 hash function，原因是它的 hash value 比其他的大，Collision 的機會便小得多。其次 SHA 家族的 hashing functions 是由美國國家安全部 (NSA – National Security Agency) 設計，並被列為美國聯邦資訊處理標準的一部分，所以給人較高的信心，很多複雜的安全方案例如 SSL 都使用 SHA-1。

PHP 還有兩個需要額外安裝的函式庫支援更多 hash function，就是 mhash 和 hash，Hash 從 PHP 5.1.2 開始列為標準的模組，無須自行編譯或安裝，所以越來越多人使用。一些比 SHA-1 更先進的 hash function 都可以在這兩個函式庫中找到，例如屬於 SHA-2 家族的 SHA-256 和 SHA-512 等，不過由於 SHA-1 的歷史比較悠久，很多系統仍然繼續使用它，尤其是用 SHA-1 來進行登入驗證的系統，由於 hash function 的不可還原性，很難一下子改用其他 hash function。

使用 SHA-1 的方法很簡單 (PHP 的函式大都很簡單，不是嗎？)：

1

echo sha1('I am a happy boy.');

Hash 的用法也很簡單：

1

echo hash('sha256', 'I am a happy boy.);

Hash 支援很多 hash function，可以用 hash_algo 查看你的 PHP 版本支援甚麼：

1

print_r(hash_algos());