Shamir’s Secret Sharing Algorithm 私鑰分割演算法
1. 前言
Hello! 大家好我是Murky! 又和大家見面了！
這篇文章主要是想要介紹Shamir’s Secret Sharing Algorithm(其實以下內文只是Wiki的翻譯加上自己的解讀)，由於本篇用到很多Latex, Medium不好編輯，於是只在Medium放一部分文章，文章最後的<前往HackMD繼續閱讀> 可以去HackMD看完整且有公式的文章喔！
Shamir’s secret sharing (SSS) 於 1979年由Adi Shamir提出，這個演算法可以使用分散的形式保護金鑰，演算法將金鑰分成n把，並設定m為threshold(閥值)，當有m把以上的拆分金鑰時，可以還原成未拆分錢的金鑰。
主要用途有：
- 從 passphrase(密碼短語)中還原成master secret, 主要用在加密錢包
- 用來分享用來解碼 Password Manager 的 rook key的金鑰
- 恢復用於encrypted email access(加密電子郵件訪問)的用戶金鑰
2. 參考資料
- Wiki: Shamir’s secret sharing
- Shamir’s Secret Sharing: Explanation and Visualization
- 原始論文：How to Share a Secret
- Wiki: finite field
3. 什麼是Shamir’s Secret Sharing
以下介紹與圖片來自於Shamir’s Secret Sharing: Explanation and Visualization, David Nugent
如前言所述，Shamir’s Secret Sharing 主要的功能是把一把金鑰拆成n把小金鑰，並且需要k把金鑰才能還原。
他的底層邏輯其實就是多項式的原理，當我們在平面上有k個 (x, y)的點，我們就可以畫出最高次方向為 k-1 的多項式。舉例來說果我們有三個點 (0,0), (1,1), (2,4) 就可以畫出 f(x)=x²
在Shamir’s Secret Sharing 中，原始的金鑰會被放在用來生成小金鑰的多項式的常數項。接著生成 n 個 隨機的點，並帶入 f(x) 並產生 (x_0, f(x_0)) , (x_1, f(x_1)) … (x_{n-1}, f(x_{n-1})) 個點 (這邊建議前往HackMD閱讀), 這些點就會變成一串小金鑰, 在這邊每把小金鑰是 (x, y)的pair
而上面這個多項式是怎麼生成呢？首先 $a_0$ 放的是我們要加密的 secret ，接著我們需要先挑選一個質數 prime (為什麼需要質數會於後面的部份介紹)， a_1 ~ a_{k_1} 從 1 ~ prime-1 中隨機選取
以下做一個舉例，假設我們設定使用 1613 當作質數 prime , 而 secret 是 1234, 做一個需要 3 把金鑰才能解開的多項式。 首先我們先從 1~1613 中隨機抽選兩個數字，這裡抽 166 與 1234, 並把 secret 放在常數向，得到：
接著我們可以在這個數線上面取得無限多個點產生無限把小金鑰，但最少要產生3把小金鑰才可以還原原本的多項式。這裡我們就取三個點 x=2 、 $x=4$ 、 x=5 得到以下的三個小金鑰 取點, 非影片上表示)
不好意思以下的公式太多，請點選下面的連結前往HackMD閱讀完整文章！
