淺談 Shamir 私鑰分割演算法：切一切再拼回來
現代密碼學從 20 世紀中葉發展至今，已經有很多非常經典的加密演算法如 AES、RSA 等等，這些演算法經過各方驗證，沒有密碼或 private key 是絕對不可能把明文解出來的。所以重點就變成該如何保存好密碼，讓密碼不會輕易被偷走、而且也絕對不會弄丟（弄丟這世界上就沒人解得開了XD）
但要保存好密碼可不容易，因為不管是把密碼放在什麼服務上，那個服務都有可能被攻破、被 DDOS 打掛、中勒索病毒等等，導致你的密碼外洩或是在需要時拿不回來
雖說上了網就一定有風險，但自己保存也不見得是好主意。譬如說把密碼存在隨身碟、抄在紙條藏在衣櫃等等（聽說有比特幣大戶就是這樣保存錢包私鑰XD），哪天不小心硬碟壞掉（我就壞過兩次）、發生火災、家裡淹水，鉅額財產可能就直接拜拜了～
Shamir’s Secret Sharing
而 Shamir’s Secret Sharing（簡稱 SSS）私鑰分割演算法正是要解決上述的問題，他可以幫你把 secret 用數學原理分割成 n 個不同的 share，並且你只需要其中 k 個 share 就可以拼回原本的 secret（n 跟 k 可以自己設定）
那這有什麼用呢？假如我們 Starbugs 手上有一份超超機密文件，洩漏出去會出事的那種。那就可以把文件用 AES 加密起來後，將密碼（secret key）用 n=4、k=3 分割成四份不同的 share 由我、神Q、Luka、小城各持有一份，並且每人把 share 放在不同的服務上
因為 k=3 的關係，駭客如果想還原出密碼就必須取得其中三份 share，也就是說他必須攻破其中三個服務才行。而且也因為 k=3，所以即便哪天我把自己那份 share 弄丟了，還是可以靠其他三人的 share 還原出文件，聽起來很不錯吧～
那這麼強大的演算法，鐵定需要很高深的數學對吧？
沒有哦，其實這個演算法只會用到國中數學，所以今天就是要跟大家介紹 Shamir’s Secret Sharing 演算法的原理，也讓大家對於數學如何應用在密碼學上有點概念～
分割 secret
Step 1 — 準備隨機函數
Shamir’s Secret Sharing 演算法的內容是這樣的，假設我想要分割的 secret 是 101，而且我希望分割成四份 share（n=4）、有其中三份 share 即可還原出 secret（k=3），那我就先隨機生成一個 k-1 次方的函數，並且把常數項設為 secret
以這例子來說 k=3，那就隨機生一個二次函數 f(x) = 2x²-9x+101（他的常數項 101 就是我們想要分割的 secret），畫成圖是一個漂亮的二次曲線，而且通過 (0, 101) 這個點
Step 2 — 在函數上找 n 個點作為 share
有了函數之後，接下來就隨機在函數上找 n 個點，這邊為了方便計算我找的是 (-8,301)、(-4,169)、(6,119)、(12,281) 四點（n=4），真的寫成程式的話就隨機找幾個數字，然後帶入函數 f(x) 隨機找出一些點就可以了
有這四點後，接著就是把原本的 secret 101 銷毀掉，並給每人一個點作為各自的 share，譬如說我拿 (-8,301)、小城拿 (-4,169)、神 Q 拿 (6,119) 等等，就這樣一人一個 share，每個人要負責把自己的 share 保存好
分割 secret 的步驟到這邊就完成了，簡單來說就是把 secret 藏在函數的常數項，然後只給每人一個點。如此一來就沒有人知道真正的 secret 是 101，每個人又只有手中的一個點，所以也不可能知道函數 f(x) 的全貌
還原 secret
Step 1 — 假設 k-1 次函數
還原 secret 的方式也很簡單，就是透過多個點把原本的函數還原出來，知道函數後取其常數項就是 secret 了
因為我們知道知道 k=3，代表一開始的 f(x) 是一個二次函數，所以我們就假設原本的二次函數長這樣，其中 a、b、secret 都是未知數
Step 2 — 解開連立方程式
假如今天我的那份 share 不見了（我真的很常弄丟東西XD），只剩下另外三份 share 分別是 (-4,169)、(6,119)、(12,281)
因為我們知道 f(x) 通過這三個點，因此就可以把三個點帶入 f(x) 中得到連立方程組，把原本函數長什麼樣子算出來
從這個例子也可以看出，雖然我弄丟了一個 share，但因為 k=3，所以即便只有三個 share 還是可以反推出原函數 f(x) = 2x²-9x+101，也就知道 secret 是 101
到這邊我想大家都看懂 Shamir’s Secret Sharing 演算法了，簡單來說 SSS 就是把 secret 藏在函數的常數項。所以要還原 secret 也是先用多個點反推出原本的函數，再取其常數項就是 secret
如果還是覺得哪邊不太懂可以多看幾次上面那段，用到的數學都不難所以應該很快就能看懂
常見問題
如果 share 太少有可能猜出 secret 嗎
以同一個例子來說，如果你只有其中兩個 share，也就是還少一個 share，那你列出來的連立方程式就只會有兩個
大家這麼聰明，應該都知道兩個方程式不可能解出三個未知數，所以最後只能得到 secret = 149 — 24a 這樣的關係式。又因為 a 可以是任意數，換句話說可能的 (a, secret) 組合仍然有無限多個，所以還是找不出真正的 secret（除非你的 a 數字太小，一下子就被猜到了）
secret 只能是數字嗎？
這應該是很多人關心的問題，畢竟大部分的 secret 都不會只有數字。雖然上面是以單純數字為例，但 secret 可以有各種形式，只要他們最後被編碼成數字就可以了
譬如說我設下的 secret 是 你好，根本不可能拿來做數學運算。但我可以先把 你好 在記憶體中的樣子用 16 進位輸出得到 e4bda0e5a5bd 字串，接著再把這字串轉換成十進位得到 251503099356605，然後就可以用上述的演算法把這個巨大數字放在常數項去做分割
還原也是一樣，解開連立方程式得到 secret 是 251503099356605 後，就先把它轉成 16 進位，接著再重新編碼成 UTF8 格式就能得到 你好 了～
因此只要你有某個編碼方法可以把字串轉成數字、數字轉回字串，那就可以運用 SSS 演算法來保護任何形式的 secret，並沒有限定 secret 一定要是數字
secret 可以多長
既然 secret 可以被編碼成數字，那說真的 secret 多長都可以，就算編碼出來的數字有一萬位數，遠遠超過 int64 的極限，那也只需要把大數運算開下去就什麼都算得出來～
雖然大數運算是用二進位模擬十進位做計算，速度鐵定會比較慢，但因為產生隨機數、在函數上找點、解聯立方程式這幾個動作都非常簡單，也不需要太複雜的計算，所以就算慢個十倍以現在的 CPU 跑起來還是非常快
順帶一提現在很多語言都有內建大數運算了，像 Go 的 math/big 跟 JS 的 BigInt 用起來都很簡單哦～
實際玩玩看
關於 Shamir’s Secret Sharing 的原理就講到這，有很多用來管理 secret 的工具如 HashiCorp Vault 都會用 SSS 來分割重要的 key，而且 Github 上有滿多 SSS 演算法的實作，我看了一下 ssss 這個 CLI 大概是用起來最簡單的，而且他支援直接輸入 ASCII 字串，這邊來實際操作一下
首先我想要把 starbugs weekly is awesome 這串 secret 分割成五份 share、只要有其中三份就能解回來。那我就下指令 ssss-split -n 5 -t 3 接著再輸入 secret，從下圖中可以看出來他已經把我的 secret（隱藏起來了）分割成五份 share（每個 share 實際上都是一個點），而且每個 share 都長到記不起來
如果有一天需要還原時也很簡單，只要下指令 ssss-combine -t 3 然後隨便丟三份 share 進去就拼回來了，而內部原理就是他會用三個點拼出原函數，再取其常數項的 secret，很有趣吧～
結論
大部分的密碼學工具背後的數學原理其實都有點難度，而且常常需要用到線性代數跟數論相關的定理，Shamir’s Secret Sharing 算是少數只需要簡單數學而且又非常實用的
他就只是把 secret 藏在一個隨機函數中的常數項，然後每個 share 都是方程式上的一個點。如此一來就沒有人可以知道函數原本的樣子，除非湊齊足夠多的點才能把原函數還原出來，再得到方程式的常數項（也就是 secret）
雖然把 secret 分割之後還是有機率外洩（可能某駭客組織為了偷取 Starbugs 的機密而盜我帳號、威脅神 Q、賄賂 Luka），但至少可以大幅提高攻擊者的成本，畢竟在資安領域本來就沒有絕對的安全，你只能不斷提高攻擊者的成本，當這個成本已經遠大過攻擊能帶來的利益時，那就可以說是足夠安全了
