【冷知識】那個長得很像亂碼 SHA-1 是怎麼算出來的？

SHA-1 是「Secure Hash Algorithm 1」的縮寫，它是一種雜湊演算法，計算之後的結果通常會以 40 個十六進位的數字方式呈現。這個演算法的特點之一，就是只要輸入一樣的值，就會有一樣的輸出值，反之，如果是不同的輸入值，就會有不同的輸出值。Git 裡所有物件的「編號」的計算主要都是靠這個演算法產生的。

SHA-1 值會有「重複」的狀況發生嗎？

首先，前面提到 SHA-1 演算法的特性之一，就是相同的輸入值就會得到相同的結果，所以當遇到 SHA-1 值「重複」的時候不表示就是「重複」，通常是表示有相同的輸入值而已。

而當輸入兩個不同的值，卻得到相同的結果，也就是說，兩個內容不同的檔案，卻得到一樣的 SHA-1 值，這種情況稱之為碰撞（collision）。

老實說，這不是不可能發生，而是發生的機率大概是連續中 N 次的樂透彩吧。這發生機會有多低？我數學不好沒辦法給一個精準的數字，只能說發生碰撞的機會，就算每秒 Commit 幾十萬上下，在短短有限的人生大概也沒機會遇到碰撞。

等等... 聽說 Google 不是破解 SHA-1 什麼的嗎？

是的，Google 的確在今年（2017 年）年初就公佈了破解 SHA-1 的消息：

根據這個網站的說明，可以用二個不同的 PDF 檔（注意，是 PDF 檔而不是文字檔喔）的內容丟給 SHA-1 演算法會得到一樣的結果。

參考網址：https://shattered.io/

不過這其實有一點作弊，因為這裡改的是 PDF 檔而不是文字檔，也就是說的確可以硬改出兩個這樣的 PDF 沒錯，但這兩個 PDF 能不能正常被閱讀還不知道，所以如果是要改出兩個內容不同但 SHA-1 值要一樣的文字檔的難度將會更高。而且，這件事如果不是擁有地表最強運算資源的 Google，大概也做不到這件事。

除此之外，對 Git 來說，它也不是單純只用檔案的內容在計算，它還額外加了一些料，讓碰撞機會更低。

計算公式

在 Git 裡，不同種類的物件的 SHA-1 值計算會稍微有些不同，舉例來說，Blob 物件的 SHA-1 計算公式是：

1. "blob" 字樣
2. 一個空白字元
3. 輸入內容的長度
4. Null 結束符號
5. 輸入內容

如果是 Tree 物件，第 1 項則改成 "tree"；如果是 Commit 物件，第 1 項則改成 "commit"，以此類推。

同時，從上列公式可以看得出來，第 1 項到第 5 項都沒有跟時間或亂數有關的內容，只跟要計算的內容有關（不過 Commit 物件以及 Tag 物件除外，因為這兩個物件的「內容」本身就有包括時間）。所以，以 Blob 物件來說，不管是在什麼時間或不同的電腦上，一樣的輸入值，就會有一樣的內容。以下我用一段簡單的 Ruby 程式範例，用來計算 Git 裡 Blob 物件的 SHA-1 值：

# 引入 SHA-1 計算函式庫
require "digest/sha1"

# 要計算的內容
content = "Hello, 5xRuby"

# 計算公式
input = "blob #{content.length}\0#{content}"

puts Digest::SHA1.hexdigest(input)
# 得到 "4135fc4add3332e25ab3cd5acabe1bd9ea0450fb"

如果你用 Git 內建的 hash-object 指令幫你算，也可以得到一樣的結果喔：

$ printf "Hello, 5xRuby" | git hash-object --stdin
4135fc4add3332e25ab3cd5acabe1bd9ea0450fb