# 雜湊函式簡介
___
- 目錄
[ToC]

___
## 介紹
雜湊函式（Hash function）又稱雜湊演算法，是一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函式把訊息或資料壓縮成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值（hash values）的指紋。雜湊值通常用一個短的隨機字母和數字組成的字串來代表。好的雜湊函式在輸入域中很少出現雜湊衝突。在雜湊表和資料處理中，不抑制衝突來區別資料，會使得資料庫記錄更難找到。

如今，雜湊演算法也被用來加密存在資料庫中的密碼字串，由於雜湊演算法所計算出來的雜湊值具有**不可逆**（無法逆向演算回原本的數值）的性質，因此可有效的保護密碼。
#### 以下是一個雜湊函式運作的例子

| 輸入 | apple | Apple |APPLE |
| -------- | -------- | -------- |------ |
| 雜湊值 | d3yB8l52 | eR4h5Nu7 |wEC24v6G|

## 性質
所有雜湊函式都有如下一個基本特性：就類似數學函式的一個X只能對應到一個Y，根據同一函式，如果兩個雜湊值(Y)是不相同的，那麼這兩個雜湊值的原始輸入(X)也是不相同的。

但另一方面，雜湊函式的輸入和輸出不是唯一對應關係的，如果兩個雜湊值相同，兩個輸入值也有可能會不一樣，這種情況稱為「雜湊碰撞（collision）」，這通常是兩個不同長度的輸入值，刻意計算出相同的輸出值。所以，**在密碼學中，雜湊函式必須具有不可逆性**，而加密函式具有一對一的輸入與輸出，這就是雜湊與加密的不同

一個好的雜湊函式具有均勻的真正隨機輸出。同樣重要的是，隨機雜湊函式不太會出現非常高的衝突率。但是，少量的可以估計的衝突在實際狀況下是不可避免的

[:link: 生日悖論或鴿洞原理](https://zh.wikipedia.org/wiki/%E7%94%9F%E6%97%A5%E5%95%8F%E9%A1%8C)

## 函式範例

### SHA-0 (1993年發布)
當時稱做安全雜湊標準（Secure Hash Standard），發布之後很快就被NSA撤回，是SHA-1的前身。

2004年8月12日，Joux, Carribault, Lemuet和Jalby宣佈找到SHA-0演算法的完整碰撞的方法，發現一個完整碰撞只需要251的計算複雜度。他們使用的是一台有256顆Itanium2處理器的超級電腦，約耗80,000 CPU工時。

### SHA-1 (1995年)
SHA-1在許多安全協定中廣為使用，包括TLS、GnuPG、SSH、S/MIME和IPsec，是MD5的後繼者。但SHA-1的安全性在2010年以後已經不被大多數的加密場景所接受。

2005年，密碼分析人員發現了對SHA-1的有效攻擊方法，這表明該演算法可能不夠安全，不能繼續使用。2017年Google公司宣布，他們與CWI Amsterdam合作建立了兩個有著相同SHA-1值但內容不同的PDF檔案，這代表SHA-1演算法已被正式攻破。

### SHA-2 (2001年)
包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。SHA-2目前沒有出現明顯的弱點。雖然至今尚未出現對SHA-2有效的攻擊，但它的演算法跟SHA-1基本上仍然相似。

[:link: sha-256的加密有多安全?](https://www.youtube.com/watch?v=S9JGmA5_unY)

### SHA-3 (2015年)
由於對MD5出現成功的破解，以及對SHA-0和SHA-1出現理論上破解的方法，NIST感覺需要一個與之前演算法不同的，可替換的加密雜湊演算法，也就是現在的SHA-3。

## 應用
### 保護資料
雜湊值可用於唯一地識別機密資訊。前提是雜湊函式是抗碰撞(collision-resistant)的，意味著**很難找到產生相同雜湊值的資料**。雜湊函式分類為密碼雜湊函式和可證明的安全雜湊函式。第二類中的函式最安全，但對於大多數實際目的而言也太慢。透過生成非常大的雜湊值來部分地實現抗碰撞。例如，SHA-256是最廣泛使用的密碼雜湊函式之一，它生成256位元值的雜湊值。

### 確保傳遞真實的資訊
訊息或資料的接受者確認訊息是否被篡改的性質叫資料的真實性，也稱為完整性。發信人通過將原訊息和雜湊值一起傳送，可以保證真實性。

### 錯誤校正
使用一個雜湊函式可以很直觀的檢測出資料在傳輸時發生的錯誤。在資料的傳送方，對將要傳送的資料應用雜湊函式，並將計算的結果同原始資料一同傳送。在資料的接收方，同樣的雜湊函式被再一次應用到接收到的資料上，如果兩次雜湊函式計算出來的結果不一致，那麼就說明資料在傳輸的過程中某些地方有錯誤了。這就叫做冗餘校驗。

### 加密貨幣
我們在加密貨幣有關的文章/談話中，常聽到的"挖礦"，其實就是利用sha-256產生亂數的性質，來比較哪位"礦工"產生的亂數轉成二進位後，前面的0最多

詳情見這支影片11:40-22:20
[:link:你有疑惑過比特幣（與其他加密貨幣）的運作原理嗎？](https://www.youtube.com/watch?v=bBC-nXj3Ng4&t=665)

## 參考資料來源
https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F
https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8#%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0%E7%9A%84%E5%BA%94%E7%94%A8
https://zh.wikipedia.org/wiki/SHA-1
https://zh.wikipedia.org/wiki/SHA-2
https://www.youtube.com/watch?v=cczlpiiu42M