← 上一章:【狀況題】可以只 Commit 一個檔案的部份的內容嗎? 下一章:【超冷知識】在 .git 目錄裡有什麼東西?Part 1 →


【冷知識】那個長得很像亂碼 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 的消息:

image
圖片來源:https://shattered.io/ 網站

根據這個網站的說明,可以用二個不同的 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

← 上一章:【狀況題】可以只 Commit 一個檔案的部份的內容嗎? 下一章:【超冷知識】在 .git 目錄裡有什麼東西?Part 1 →

Comments