科普 | Emoji 表情帶你秒懂雜湊函式
區塊鏈的發展史本質上是技術人員和雜湊函式之間長達十年的纏綿情史。
事實上,如果你瞭解雜湊函式,那麼理解 區塊鏈的挖礦模式和不可篡改性 還不是小菜一碟!(文末還有更多內容)
Git是一種版本控制程式碼庫系統,幾乎覆蓋到了所有開發者。連這種革命性的開源工具都離不開雜湊函式。
電子簽名軟體 Docusign 同樣基於雜湊函式。
你每次在網站輸入密碼之時 , 背後都有雜湊函式在作用。
雜湊函式雖然用起來非常簡單,但是效能非常強大,普遍應用於各種軟體,以實現 版本控制、安全性和真實性 。
什麼是雜湊函式?
雜湊函式在近年來的技術進步中發揮著非常重要的作用。那麼,雜湊函式是什麼?它的工作原理是什麼樣的?我覺得大家至少應該對它有個基本瞭解。
雜湊函式或許不對你的胃口,所以我也只是想解釋下它為什麼如此強大,不會涉及太多細節……所以別棄文好嘛:wink:!
網上很多關於雜湊函式的解釋都過於直白,要麼晦澀難懂,要麼枯燥無聊……要麼二者兼具。因此,在本文中,我將通過 emoji 解釋雜湊函式,讓一向暗淡的密碼學世界變得鮮活起來。(雖然可能會起反效果,但……我們繼續吧!)
雜湊函式簡介
不妨把雜湊函式想象成一個 emoji 表情工廠,接受一行行 emoji ,不過僅限於獼猴桃、菠蘿、茄子、辣椒、胡蘿蔔和玉米這 6 種。
工廠處理完輸入之後,得到的輸出也只會由上述 emoji 組成。
校對注:這裡的意思就是,輸入雜湊函式的是資料,輸出的也是資料。輸入和輸出的基本組成部分都是一樣的,就是字元。
這個 emoji 表情工廠的特別之處在於:
1. 這個工廠輸出的 emoji 數量少於輸入的 emoji 數量
這家工廠每次接受一行 8 個 emoji (僅選取自上述 6 種 emoji ,其中每種 emoji 都可重複出現)。這行 emoji 經過處理之後,會返回一行 3 個 emoji 的輸出,同樣選取自上述 6 種 emoji 。
重點是,它輸出的 emoji 比接收到的少(8 個變成 3 個)。
2. 相同的輸入進入工廠一定會產生相同的輸出
如果你兩次都將相同順序的 8 個 emoji 表情送入工廠,它每次都會返回相同順序的 3 個 emoji 表情。
即,這個工廠具有 確定性 。
你可以從上面的 gif 動圖中看出,對於相同的輸入,工廠每次都會返回相同的輸出。
校對注:這個大家可以自己驗證一下: ofollow,noindex" target="_blank">https://1024tools.com/hash
這是一個線上計算雜湊值的網站。你會發現,不管你今天還是明天,放“ethfans”這段字元進去,得出的 SHA256 值一定是:
1a64ed5b74670156e60e10d8b4f94b02347169cda06b6f1493f80db0c24f2d6c
(注意輸入是全小寫哦!)
3. Emoji 表情工廠是一條單向通道
如果你輸入一行 8 個 emoji ,工廠會立刻返回一個輸出。就這麼簡單!
然而,如果我將工廠輸出的 3 個 emoji 告訴你,但是不告訴你對應的輸入是什麼,你是無法通過分析工廠和輸出來倒推出輸入的。實際上,要想找出輸入,試錯已經是最快的辦法了。
換句話說,要想找出某個輸出對應的輸入,最快的方式就是隨機輸入不同的 emoji 表情組,直到找到正確的那組。
更重要的是,你甚至可以在工廠裡走一走,觀察它的實際運作情況,卻依然不能根據輸出求解或逆向倒推輸入!它是一個完全的 單向工廠 。
我知道這個比喻或許還不夠接地氣,所以我還準備了一個更日常的比喻。
這個工廠的運作方式不就像是烤蛋糕嗎!(破音)
如果我給你製作一個蛋糕所需的配料和一個詳細的配方,你只要依照配方操作這些配料,立馬就能做出一個蛋糕。
如果我讓你用同樣的配料和配方再做一次,你很快就會做出一個相同的蛋糕。 烘焙同樣具有確定性(理論上是這樣的!)。
但是……如果我給你的是蛋糕和配方(配方不包含配料用量,只包括混制和烘培步驟),那就很難計算出這個蛋糕的確切配料用量。
這個時候,通過改變蛋糕配料比進行試錯或許是最好的方法。(在這一點上,專業廚師可能另有高見!)
接下來再說回 emoji 表情工廠的屬性。
4. 哪怕只改變輸入中的一個 emoji 表情,也會得到完全不同的輸出
就蛋糕烘焙一例而言,你可能通過一次又一次的試錯,越來越近正確的配料用量。但是對於 emoji 表情工廠來說,哪怕只對輸入作出細微的改變(僅改變一個 emoji 表情), 得到的輸出都是八竿子打不著的 !
以上面的 gif 動圖為例,如果將輸入中第一個茄子換成胡蘿蔔,得到的輸出會是完全不同的 3 個 emoji 表情。
這就意味著在給定輸出的情況下,你無法通過不斷試錯“逐步接近”正確的輸入。你只能隨機嘗試不同的 emoji 表情組,直到無意中發現了正確的輸入為止。
區塊鏈挖礦本質上就是通過計算機不斷進行試錯來找到一類輸入,經過 emoji 表情工廠的處理能夠返回帶有某個特性的輸出,例如,以兩個茄子開頭的輸出。
校對注:先給大家幾個例子感受一下:
SHA256(ethfans) = '1a64ed5b74670156e60e10d8b4f94b02347169cda06b6f1493f80db0c24f2d6c'
SHA256(ethFans) = 'a59b6016fb422d7f41d58e16c76e570ff98830c85dc805b1d857fbf6c8173b8f'
SHA256(12345678) = 'ef797c8118f02dfb649607dd5d3f8c7623048c9c063d532cc95c5ed7a898a64f'
SHA256(24691356) = '89c3a10b69ffebfeb45eb70c183823a02cf1277250bdfc03179eb58e779c5fc3'
上面這個輸入是恰好是上一個輸入的兩倍,但是輸出值沒有任何關聯。其實第三點跟第四點是相通的。那麼我問你:如果我要你找到一個輸入,使得 SHA256 輸出值以 4 個 A 開頭,你有什麼好辦法來找?
看第五點。
5. 要找到一個輸出對應的兩個輸入,最快的方法就是試錯
你現在一定有個疑惑……
“等等,如果輸出比輸入短,每個輸出肯定會對應多個輸入吧?”
……你是對的。如果你將 8 個 emoji 放入工廠,只得到 3 個 emoji ,那麼一個輸出必定對應多個輸入。
然而,emoji 表情工廠的設計太妙了,即使你知道某個輸出對應的輸入之一,可惜找出其餘輸入的最快方法依舊是試錯。
換句話說,要找到一個輸出對應的兩個輸入,最快的方法就是試錯,直到發生“ 碰撞 ”為止。
現在是時候總結一下這個 emoji 工廠所有的神奇特性了!
小結
-
工廠接收 8 個 emoji 表情並且返回 3 個 emoji 表情。( 壓縮性 )
-
相同的輸入總是返回相同的輸出。( 確定性 )
-
輸入的毫釐之差都會導致輸出的千里之謬。( 漫射性 )
-
給定一個輸出,試錯是計算對應輸入的最快方法。( 單向性 )
-
試錯是找到同一個輸出對應的兩個不同輸入的最快方法。( 抗碰撞 性 )
有趣歸有趣,這些特性為何如此重要呢?
現在,讓我們一起來看看這個工廠的實際應用。
想象一下,你的密碼由 8 個 emoji 表情組成。每次你把密碼輸入一個網站,網站儲存的不是你的密碼,而是你的密碼的 “雜湊值”(你的密碼經過 emoji 表情工廠處理之後,會輸出 3 個 emoji 表情)。
這樣一來,如果出現數據洩露或者有人竊取到該網站的個人資料,那麼竊取者得到的只是一堆雜湊值,而非實際的密碼!
由於工廠是 單向 的,如果竊取者要根據雜湊值逆向計算出實際的密碼,唯一方法就是試錯。
在當前情境下,由於你只能從 6 種 emoji 表情中選出 8 個作為密碼,竊取者可能不用花很長時間便可破解。
但在實際生活中,可選作密碼的字串集合要大得多,這就意味著可能的輸入範圍也要大的多。與此同時,實際生活中雜湊工廠/函式的輸出長度也遠遠大於 3 個字元。
因此在現實中,竊取者要花費很多很多年的時間才能根據 雜湊值 算出對應的密碼!
在此期間,雖然存在資料洩露的問題,卻不影響你重新登入網站,反正你知道自己的密碼,直接輸入就好。
這時,你輸入的密碼會立即經由雜湊工廠轉化成一個雜湊值。網站可以立刻檢查這個雜湊值是否與你的賬戶名所對應的雜湊值匹配,因為雜湊工廠總是返回相同的輸出( 確定性 ),並允許你登陸。
但是密碼長度不一定都是 8 個 emoji 表情那麼長,如果我想對一行更長的 emoji 表情進行雜湊計算呢?
你可以的!驚不驚喜!意不意外!通過這項由 Ralph Merkle 和 Ivan Damgård 兩位密碼學專家提出的簡單技術,任意長度的 emoji 表情都可被轉化成僅由 3 個 emoji 表情組成的雜湊值。
我們要怎麼做呢?
如果增加 emoji 表情組的長度,我們就會建立一組工廠來處理它。具體步驟如下。
-
先對一行較長的 emoji 表情組進行分段,前 8 個 emoji 作為第一段,之後以 5 個 emoji 為一段。(如果最後一段不足 5 個 emoji ,可以使用額外的 emoji 進行填充,不過這個額外步驟技術含量太高,這裡就不做解釋了。我們就假設這行 emoji 表情組是可以完美分段的!)
-
將第一段 emoji 輸入第一個工廠。
-
得到一個由 3 個 emoji 表情組成的輸出,將這個輸出與第二段表情一起輸入第二個工廠。
-
不斷重複這個過程,直到這行 emoji 表情組全部經過工廠處理。
-
將最後一個工廠得到的輸出返回。
所以現在我們可以把更長的 emoji 表情組轉化成 3 個 emoji 的雜湊值了!
等等……
既然現在輸入的長度問題解決了,那麼找到輸出相同(一次碰撞)的兩行輸入會容易得多嗎?
你的直覺可能會這麼認為。不過出乎意料的是,這就像在一家工廠找到 “一次碰撞” 一樣困難。以下是推理過程。
推理開始
假設除了試錯之外,還有某種方法可以找到一個輸出對應的兩個較長的 emoji 表情組輸入( 一次碰撞 )。
那麼,在某個實行 Merkle-Damgård 架構的工廠中,你輸入兩行不同的 emoji 表情組,這個工廠將返回相同的輸出。
但是,這意味著你已經使用試錯之外的方法找到了一次碰撞,這就與上文提出的抗碰撞性相矛盾了!
所以……
通過增設工廠和數學推理,我們創造了一種方法,可以將任意長度的 emoji 表情組轉化成由 3 個 emoji 組成的雜湊值。
更重要的是,如果有人得到了一個由 3 個 emoji 組成的輸出,也沒有比試錯更快的方法計算出任意長度的對應輸入。鑑於現實世界的雜湊計算存在太多組合方式,試錯可能會花費許多年!
有了這個簡單的技巧,假設一個 emoji 表情工廠是抗碰撞的,你就可以將自己的 emoji 表情密碼設定成任意長度,其安全性依然不受影響。
那麼區塊鏈呢?
想象你有一個文件(滿是 emoji 表情),裡面可能是關於一筆金融交易的描述。你要向人們證明這個文件在某個確切的時刻處於某個確切的狀態(截止到最後一個 emoji 表情)。
然後,你可以將整個文件放入使用 Merkle-Damgard 架構的雜湊工廠中,將輸出結果通過電子郵件傳送給 100 個人。
因為工廠是單向的,所以郵件接收者無法弄清楚文件的原始內容。如果未來有人汙衊你的文件是假的,或者你已經篡改了它,你就可以證實在某個確切的時刻(當你把這個文件傳送給去中心化網路的其它人之時),這個文件處於某個確切的狀態(截止到最後一個 emoji /字母)。
既然雜湊工廠是抗碰撞的,其他人自然會相信你不是騙子!
總之
雜湊函式的單向性和抗碰撞性是非常強大的,它們正在改變整個技術世界。
但是 emoji 表情工廠/雜湊函式內部到底是如何運作呢?
這就要涉及到很多技術細節了,實際上,如果你確信上述特性成立,那麼工廠的內部運作就無關緊要了。雜湊函式的特性比它們的內部運作更有趣(除非你是數學家或密碼學家!)。
真正的雜湊函式接受的是 十六進位制字串 (並不是 6 進位制 emoji 表情字串)。十六進位制字串僅由 “0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f” 十六個字元組成。雜湊函式接受任意長度的輸入,並且返回 64 個十六進位制字元(或者為了增強安全性,返回 128 個十六進位制字元)。
一種普遍使用的雜湊函式是 SHA-256。如果你對本部落格有任何想法,請發郵件給我,不過你要先從下方的雜湊值算出我的郵箱地址!(提示:在這種情況下,可能有比試錯更巧妙的方法噢!)(校對注:從密碼學上來說,因為我們知道了輸入必然具備的一些條件,比如裡面要有個“@”。從社會工程學上來說,我們可以直接翻推特和領英 : ) )
我的郵箱地址的雜湊值是:8d935def1f9e0353b0f19f3c765bdeec151862a199084ae4f4b417ca42608914
原文連結: https://medium.com/swlh/this-simple-yet-powerful-invention-is-changing-the-world-d04688c25f13
作者:Patrick Woodhead
翻譯&校對:stormpang & 閔敏