Hash Calculation 雜湊計算簡介

24 December, 2019

雜湊計算是廣泛被應用在數位產業中幾乎是各方各面的一種奇妙的計算工序，它的用法用途上天下地、它的算法千奇百怪、它的面貌千變萬化，對於初次接觸雜湊的學生可能一會兒更難以理解，從而產生它為何出現在此、為何如此計算、為何如此使用等疑問。那麼，本篇就要針對初學電子計算機的人、在首次接觸雜湊計算時充滿了疑惑的人來簡單的介紹雜湊運算帶領入門。

定義

雜湊運算的作用是：對任意長度的任意二進位資料進行計算，並得出一個值域範圍固定的結果數值，對於整個計算包含從開始到最後的結果只有一條硬性規定： 在使用同一種演算法的情況下，對於相同的資料輸入，必須算得一樣的結果數值。

基於這個基本定義，還可以延伸推導出兩個規律：

若兩筆資料計算出的結果值不同，則該兩筆資料必不相同。
若兩筆資料計算出的結果值相同，則該兩筆資料可能相同也可能不相同。

相關名詞解釋：

該計算的結果數值稱為 Hash Value，中文稱為「雜湊值」；
計算該結果的工作稱為 Hash Function，中文稱為「雜湊函式」；
計算該結果所使用的演算方法稱為 Hash Algorithm；
對於兩筆不相同的資料計算出的結果值相同的情況稱為 Collision，中文稱為「碰撞」；
而泛指與之有關的稱為 Hash 或 Hash Calculation，中文稱為「雜湊」或「雜湊運算」。

範例

在對雜湊運算充滿疑惑的狀態下，我覺得與其去研究那些算來算去不知在算什麼的知名演算法，不如先試著自己製做一個雜湊函式，從這當中理解學習雜湊運算可能會更有意義。

要寫作一個雜湊函式其實非常簡單，只要把輸入的資料拿進來，然後發揮你的創意隨便亂算，算出一個和亂數差不多的、無意義的奇怪數字即可。唯一的要求只有一個，那就是使用你的計算方法分別計算兩筆一模一樣的輸入資料，最後得出的那個奇怪數字要是一樣的。另外可能因為這種計算看起來和亂算沒什麼不同，所以當時的人在處理 Hash 的中文翻譯的時候，才給了它「雜湊」這個名字吧！

下面以一個我自己隨便寫的雜湊函式做為範例：

uint16_t MyHashFunction(const void *data, size_t size)
{
    const uint8_t *array = data;

    uint16_t value = 1;
    for(size_t i = 0; i < size; ++i)
        value *= array[i];

    return value;
}

這樣我就完成了一個我自己發明的雜湊計算方法，這個簡單的算法在很多特性方面可能不足以好到讓一般的用途去使用，但卻完完全全符合一個雜湊計算所需的要求。我要求了一筆長度為 size 的位元組資料串做為輸入，最終會算出一個 16 位元、值域範圍為 0 至 65535 的整數值，至於計算方式就是很簡單的把每一個位元組值相乘而已(溢出就讓他溢出，超出的部份就直接捨棄)，其中最重要的是：如果在不同的計算中若你輸入了一模一樣的資料，那麼我就一定會算出一模一樣的結果值。

性能指標

由於雜湊運算的定義要求非常簡單，也鼓勵天馬行空發揮創意，因此現實中使用的各種雜湊演算法實在是滿坑滿谷，而這些不同的演算法之間、甚至是與你自己實現的算法之間有什麼不一樣呢？評估一個雜湊演算法的好壞或者適用與否有幾項主要的性能指標，於下分別說明。

正確性

由於雜湊計算的規定只有一個，所以判斷雜湊演算法正確性的依據也只有一個，那就是我們前面一再強調的：對於同樣的輸入資料必須計算出相同的雜湊值。

既然這條規定是硬性的，不符合這項規定的演算法就不是個合格的雜湊算法，那還有什麼好討論的呢？事實上在這個世界上具名的雜湊演算法可能有 99.99% 都符合正確性的要求，所以這項規範適合的討論範圍其實就是在你們因為各種原因需要自己發明雜湊算法的時候。很多時候演算法正確性不足的缺點可能難在開發的過程中發現出來，比方說在研發人員自己的電腦上怎麼算都正確，但客戶使用產品的時候卻就是會發生運算不正確的情況。比方說研發測試的時候都看不出問題，要換臺電腦、換個系統、換個處理器等等才會發現自己的演算法有缺陷，這種問題特別是在軟體開發人員未具有足夠的資訊概論和程式設計基礎的情況下容易發生 (很符合臺灣產業界的現況)。

記得我畢業後的第一份工作，那時我還是個菜鳥中的菜鳥。有一天我們的軟體需要序號驗證功能，防止客戶無限制的把軟體到處複製使用，這時我主管要我做一個其中需要的函式，用來把用戶電腦的一些關鍵訊息進行各種隨意的亂算，最後算出一筆奇怪的資料。那時的我滿臉問號，不知道這幹什麼用的、也不知道要如何開始，後來他說算了，他來做給我看，最後他開心的展示給我他實現的程式碼。我一邊觀看他一邊解說，反正就是各種隨意的到處亂算，其中最讓我印象深刻的是裡面還用到了 sin 和 cos 等函式。我主管說他們以前遇到這種需求都是這樣做的，反正就是想到的都拉進來亂算，算的愈亂愈好！

經過了多年以後重新回想，我才明白這就是一個需要自行製做雜湊計算的需求，也發現當時的這位研發主管根本不知道雜湊這東西，也不知道世界上早就存在許多比他亂來的實現還要更好的演算法。那麼他的實現哪裡不好呢？撇開各種性能方面的問題不談，就光是要達到計算的正確性這個要求就有問題。例如裡面呼叫了三角函式，而這類的函式實現本身就不能保證絕對可以算出二進位資料完全相同的東西，它的運算結果可能會因為數學函式庫的實做不同而有些差異(這些函式庫通常是由編譯器提供)，就算屏除了函式庫實做的差異，浮點運算在不同的 CPU 上面可能也會有不同的行為表現；我想這可能就是這家公司的程式產品為什麼只能使用 Borland C++ Builder 6 編譯(還不能更新版本)、以及為什麼只能支援 Intel x86 CPU 搭配 Windows 平臺的其中一項重大原因吧！另外，對於數位電腦的基礎知識之不足、以及對於程式設計基本功的馬虎，可能也是導致於這些學長們口耳相傳「即使你不覺得有問題，也絕對不要更換編譯器、絕對不要修改編譯設定、連最佳化編譯也不能打開、絕對打死都不要更動流傳下來的開發環境的任何一個環境設定，否則就會發生千奇百怪的問題」等等這些話語的原因吧！

總結來說，在自己實現雜湊算法的時候需要避免使用某些計算：請避免呼叫那些因為實做不同或版本不同而可能會產生結果差異的函式庫，以免你的演算法只能搭配特定的程式庫或編譯器；請避免呼叫系統 API，以免你的演算法只能在特定的系統下使用；請避免使用浮點數運算、以及整數負值計算，以免你的演算法只能在特定的 CPU 上得到正確的結果；請妥善處理 endian 有關的格式轉換、或採用與 endian 無關的運算，以避免你的演算法依賴於特定的 CPU 格式；以及請避免任何其他以上沒有提到，但會破壞演算正確性的東西，比如有些未知的東西也許會讓你今天計算一筆資料得到結果 27，明天再算卻得到 35 之類的！

不可逆性

如果說雜湊計算是從輸入資料算出雜湊值，那麼逆向的雜湊計算就是從雜湊值計算出原始輸入資料了；而可逆性指的就是從雜湊值回推、或估計、或猜測原始資料可能之組合的可行性，那麼不可逆性愈高自然就表示愈難以從雜湊值逆向推估窺探原始資料。

總體而言，在雜湊計算的定義裡並沒有對可逆或不可逆的特性做出任何要求，在某些用途上可能也不會在意可逆性高或不高，但若所在應用的場景中不樂意讓人從雜湊的結果來窺探原始資料的話，所使用的演算法之不可逆特性就會變得相當重要。

以我的範例來說，它的不可逆性就不夠好，如果算出來的值為零，那麼絕大的機率可能是因為資料中有零的存在，在輸入資料格式已知的情況下，有時就可以猜測某些資料排列組合；若輸入的資料只有一個位元組的情況那更慘，因為這時我的計算結果根本就等於原始輸入資料。

均勻性

一個理想的雜湊算法對於各種輸入資料所算出來的雜湊值，應該平均的分佈在其所定義的值域範圍內，一個結果值的分佈均勻性不佳的雜湊算法，會在某些應用用途上產生不樂見的問題，例如在 Hash Map Container 的應用上會導致性能衰退。

以我的範例來說，它的均勻性就不夠好，雜湊值為零的機率比其他數值都來得高，只要資料中出現了一個零，不論是因為資料本身的零值、還是在計算過程中因為數值截斷的緣故而產生的零值，那麼結果就一定是零了。最終，這個雜湊函式的範例可能只有在輸入資料為長度適中的 ASCII 字串時，才能有較為理想的均勻性表現。

隨機性

雜湊的隨機性指的是對於輸入資料所計算出的雜湊值是否具有規律性而容易被預測的指標，隨機性能愈高的演算法，其所計算的結果愈沒有明顯的規律、愈難被預測。隨機性和均勻性看起來是類似的，然實則有所差異，一個隨機性高的算法未必擁有均勻的算值分佈，反之亦同。

值域範圍

演算法所得之雜湊值值域範圍也是一個很重要的指標，它會間接的影響其他方面的性能表現。雜湊值值域在 0 至 255 之間的演算法，我可以用一個 8 位元整數就能儲存；雜湊值值域再廣一點的，我也許也能用 16 位元、32 位元的數來儲存並應用；但若值域範圍再大上去，當沒有計算機內建整數型態可以容納的時候，對於雜湊值的儲存、運算、和比對等工作所消耗的計算資源可能就會一下子上漲。站在這個考量點上，較小值域範圍、或至少在計算機內建整數型態範圍內的演算法是比較討喜的。

碰撞率

在雜湊運算中的「碰撞」即是用來稱呼當兩筆不同的輸入資料卻計算出一樣的雜湊值的情況，而碰撞率當然指的就是某個演算法是否容易發生碰撞情況的指標。通常來說碰撞率會與均勻性或隨機性等等其他特性連動，總體來說，演算法的碰撞率不是一個單一的性能指標，比較像是整體綜和表現的結果。

基本在所有的應用條件下，人們所喜歡的理想雜湊函式碰撞率是愈低愈好，最好絕對不會發生碰撞；然而實際上碰撞率愈低的演算法往往在某些其他的性能屬性上成績愈不好看，因此在經過權衡取捨後，還是能接受使用一些碰撞率相對高得多的演算法。

以雜湊值值域做為範例，一個值域範圍小的雜湊值可以讓相關的儲存、比對等工作變得容易快速，但是另一方面來看，不管演算法再怎麼厲害，當其雜湊值值域範圍愈低，碰撞率將必然的向上增加。若我要求一個雜湊值範圍在 0 至 255 的演算法，又如何要求它可以在算遍天下資料之後仍不發生碰撞？

運算複雜度

雜湊算法的複雜程度也是一項重要的指標，算法繁複的雜湊函式必然要消耗更多的計算時間才能完成，因此在部份的應用上，也常常選擇那些其他性能看起來沒那麼好但計算快速的雜湊演算法。

應用用途

理想上完美的雜湊演算法各項性能指標都要表現傑出，演算不可逆、算值均勻又隨機、既不可能發生碰撞又只需要內建整數型態即可儲存其值、同時還要實做簡單而運算效率高。無奈這種完美的演算法似乎不可能實現，許多性能指標之間往往互相抵觸，一方面好則另一方面就不可能好。對於不同的用途，重視的性能指標也不一樣，程式開發人員需要依據面對的情況，權衡不同性能指標間的優劣表現，選擇最適合自己的雜湊演算法。因此接下來要介紹在各種常見的雜湊用途中對於演算法選擇的不同觀點，順道介紹雜湊算法常見被用在什麼用途上。

資料校驗

當資料需要在不同的機器之間傳送接收的時候，比如說經過網路傳輸、經過串列埠傳輸等等，偶而會因為一些硬體雜訊還什麼的原因，造成收到的資料有異，這時就要通知對方重送。然而一個很大的問題在於你得要先知到資料發生了異常，然後才知道該進行後續的動作，所以在資料傳輸的用途上幾乎是一定都需要一個資料校驗的機制。

一個簡單的想法是我直接把同樣的資料連續傳個兩三次，如果資料收下來都是一樣的，那就是正確的，反之就表示資料有異。然而這麼做有兩個缺點，首先傳輸的資料量會立刻膨脹兩三倍，白白浪費資料流量空間。第二是萬一遇到問題的發生與通透資料的特性有關的時候，例如某些硬體設計瑕疵導致當傳送了 1、3、5、接著傳送 4 時就會發生資料錯誤，那麼同樣的資料重複送幾次不就都是吻合但卻全部錯誤的嗎？

因此一般我們使用雜湊運算做為資料校驗的手段，對要傳送出去的資料進行雜湊計算得到雜湊值，然後把這個值併到資料裡面一起發送，資料接收方收到資料以後重新計算資料的雜湊值，然後與傳送方夾帶過來的雜湊值比較看看是否一致，若雜湊值相同則可以相信這筆資料絕高的機率是正確的。

在資料校驗的用途上，我們面對的假想情況是整筆資料中的少數幾個位元可能會隨機的發生錯誤的情況，一筆資料的雜湊值也不會需要去和別的資料的雜湊值做比對。因此在演算法的選擇上比較不在意碰撞率和隨機性的表現、對於不可逆性也沒有要求，但通常會很在意運算效率，不希望一筆資料的收送在校驗值上面花費太多的時間和其他計算資源，同樣的也傾向於使用那些值域範圍較小的演算法，以利減少冗餘資料長度並加速計算與比對速度。在資料校驗用途的雜湊演算法一般常見的有 CRC-32、或是更簡單的 checksum 或 LRC 等，甚至在古老的時代理，只有一個位元長度的 parity bit 也是被接受的。

資料索引

在資料結構演算法裡面有一種容器叫作 Hash Map 或 Hash Table，這是一種可用來儲存「鍵值對」資料的容器。我這裡不想要展開解釋太多關於資料結構和容器的東西，那又是另一個大主題了，所以這裡只簡單的帶過一些提示，有興趣的人自己再透過這些關鍵字去查詢更多的細節。當我們需要建立一個資料容器，並且希望可以使用一個關鍵值來找尋容器內符合的資料的時候，除了使用經典而複雜的各種二元樹結構來做以外，也可以使用 Hash Map 容器。使用 Hash Map 的好處是它的實現相對簡單快速，在實際應用上的效能表現通常不俗，在許多需要鍵值容器的簡單執行環境裡有一定的立足位置。

在這種應用場合上，不用說，這演算法的複雜度和計算效能絕對是首要條件，而對於不可逆性和值域範圍等就沒有太多的執著，畢竟值域再大的雜湊值也會因為被取餘的關係而降下來。另一方面，做為容器使用的雜湊算法更看重其均勻性，至於隨機性則不重要。一個算值不均勻分佈的演算法將會容易讓雜湊值集中碰撞在某些區間，導致資料查找效率衰退，最嚴重的情況下會讓 Hash Map 退化為 Linked List。

至於 Hash Map 實際使用的演算法就令人眼花撩亂了，似乎並沒有共識說哪幾個演算法使用率最高，常常是看設計者的想法、以及實際實驗適配以後最終才選擇使用某些演算法，基本上符合上面敘述之特性的演算法都可以放在備選方案裡面。

資料簽章認證

資料簽章認証其實和前面說的資料校驗在概念上是一樣的，都是為了讓資料的正確性受到保障，但更強調接收方所收到(比如從某處下載)的檔案資料是正確且未被竄改過的。其之不同之處在於，相比於資料校驗面對的是資料自然的隨機出錯，資料認証的用途中需要面對並對抗的更多是對於人為刻意而精心竄改的防範。

與資料校驗相同，若人們計算所收到資料的雜湊值與發送方所提供的雜湊值相同的話，基本可以判定該筆資料是正確可受信任的，因為在中間若有資料竄改的情況發生，一般來說這會導致最後計算出的雜湊值不吻合。然而對於一個不夠複雜可靠的雜湊算法而言(例如 LRC)，竄改者可以透過精心設計的內容修改、或者在資料的前後與中間等處插入一些特別設計的垃圾資料，最終讓修改後的內文所計算出的雜湊值與修改前的內文雜湊值相同，導致被竄改的文件受到接收方信任。

因此對於資料認証用途的雜湊演算法選擇上，最看重的是算法要擁有幾乎不可能發生碰撞的極低碰撞率、以及極為隨機的雜湊值分佈，最好是只要改了資料的一小點部份就會造成最終雜湊值十萬八千里的不同，而能夠達成這種要求的演算法基本都是不可逆的。一個符合上述特性的雜湊演算法，可以讓竄改者想要微調控制資料使得雜湊值發生碰撞的情況基本不可能發生，至於演算法的其他的性能指標如運算效率等等一般完全不會有人在意。目前常被使用於資料認証用途的演算法有 MD5、SHA-2 等，此外在各種雜湊演算法列表中若您有看到關於「適合加密使用」等的註記或分類的話，那麼這種演算法就是可以用來做資料認証用途的雜湊算法。如果您曾有在網路上下載檔案時，看到下載處旁邊有一串文字寫著類似「MD5=……」這樣的東西，它就是所謂的驗證碼，下回您可以試著將下載到的檔案用軟體工具計算一下它的驗證碼，再比較看看與網頁上的記載是否相同？

再延伸下去，雖然這一長串的驗證碼可以保證資料的正確性，可是驗證碼本身的可信度呢？我怎麼能確定記載的這個驗證碼是原始作者留的、還是被駭客改過的？如果說驗證碼保障了資料的話，那麼誰來保障驗證碼呢？對於這樣的需求發展出來的解決方案，一般是使用了公鑰加密技術，用原作者或發佈者的私鑰將驗證碼加密起來，這樣任何人都可以用發佈者的公鑰解密出驗證碼，並且只有使用了正確的公鑰才能夠解密出正確的驗證碼，讓竄改者無從下手。對於這種經過加密的驗證碼，我們一般稱之為「簽章」，如同現實世界手寫簽名的數位版本，任何人都可以透過公鑰系統搭配雜湊算法，驗證某筆檔案或資料是否確為某個人所簽名發佈並且未經竄改。

資料隱藏

當我們想要隱藏一些不想讓別人知道的資料時，直覺想到的方法大概就是加密了吧！然而有時候我們可以使用雜湊計算來隱藏資料，除了比一般的加密算法更簡單快速以外，還不用費心在管理和保護加密密鑰的工作上。當然，使用雜湊計算來隱藏資料有一個明顯的缺點，就是無法回復資料，因此只適合用來隱藏那些不需要解密的資料。那麼實際上有這種不需要解密的資料隱藏需求嗎？答案是有的，比如密碼的加密。

在很多時候我們會需要對使用者進行密碼驗證，比如說網站的密碼登入、電腦的密碼登入等等，如果我們把使用者設定的密碼資料直接明碼儲存在網站資料庫、或者電腦系統的檔案系統內的話，那麼就會存在很大的風險，一旦資料庫被入侵竊取的話，所有使用者的密碼就一覽無遺。一個普遍被使用的保護方法是我們不直接儲存密碼，我們將密碼做為輸入資料計算出該密碼的雜湊值之後，只儲存這個雜湊值。這樣雖然無法還原出原本的密碼，但卻完全不影響密碼機制的使用，因為我們只要對使用者輸入的密碼進行一樣的雜湊計算得到雜湊值，然後比對和資料庫中儲存的雜湊值有沒有一樣，就知道密碼是否正確了。相對的，就算有人從資料庫中取得了這些雜湊資料，也無法知道密碼是什麼？只能使用暴力破解法一個一個去嘗試！

對於資料隱藏用途的雜湊演算法挑選，一般完全比照資料簽章認証的標準，一樣使用加密類型的雜湊算法。

產生密鑰

雜湊計算除了通常用來把一筆很長的資料計算為很短的雜湊值之外，也可以用來將很短的資料變成長度比較長的雜湊值。

舉例來說，學過加密算法的人大概都知道加密金鑰長度通常都在數百位元的大小，可是我們常用的文件加密、壓縮檔加密等等都只需要設定相對短得多的密碼，甚至密碼只有一個字母也行，那麼這麼短的密碼怎麼能夠用來當作加密金鑰使用呢？這時候雜湊計算就派上用場了。比如說我們使用 MD5 將用戶輸入的密碼計算為 128 位元的雜湊值，正好符合 AES 加密的最短金鑰長度，這樣使用者不管設定了多短、或多長的密碼，我都可以計算得到一個足夠我使用、且看似亂數的金鑰；並且最重要的是，只要輸入了同樣的密碼，我一定可以算出同樣的金鑰。

對於金鑰產生用途的雜湊演算法挑選，可完全比照資料隱藏的標準，一樣使用加密類型的雜湊算法。

與其他一些看起來類似的計算不一樣的地方

在完成了雜湊計算的介紹和比較之後，最後我還想順便針對初學者補充一些資料，解釋有些看起來與雜湊計算相似(或雜湊計算與之相似)的計算工作之間的差異。

亂數

亂數產生就是產生一個隨機的亂數，而雜湊計算也是算出一個看起來隨機的亂數，那麼此二者之間的差別在哪裡呢？

相比於雜湊計算，亂數的計算強調的是絕對的隨機性和均勻性。除此之外，亂數與雜湊之間最大的差別還在於，雜湊計算雖然最終也是算出無法預測的隨機數值，但是只要輸入的資料相同，則最終的這個隨機數值也會是一樣的。相反的，亂數計算以能夠算得最亂最無法預估的數值為目標，即便目前的偽隨機亂數演算法當中只要輸入相同的狀態資訊則亦能算得一樣的亂數值，但這比較像是迫於現實無奈之下的結果，而非偽隨機亂數的本意。

另外，雜湊演算法要求在各種軟硬體計算環境下都能算得一樣的結果，而亂數生演算法則對不同環境下造成的計算差異不太看中，甚至有些亂數生成工作還會刻意把一些無法預測的硬體雜訊湊進來計算，只為能夠算出更亂更無法預測的結果。

加密

前面提到，雜湊可以用來隱藏資訊變成好像隨機亂數的資料，而加密計算也是能夠把資訊隱藏變成好像隨機亂數的資料。

然而它們之間的不同比較容易分辨，雜湊與真正的加密行為之間最大的不同在於，加密算法可以把資料從隱藏狀態下還原，而雜湊不行！因此雜湊計算只能用來將資料隱藏之後做為比對等用途使用。但也因為雜湊計算不要求能夠還原資料的原因，雜湊計算通常會比真正的加密計算來得簡單快速得多，也避免了使用加密機制所需要的密鑰管理保護工作。

定義

範例