考慮一個您需要保護銀行金庫的場景。 如果沒有鑰匙，它被認為是絕對堅不可摧的，而鑰匙是在工作第一天給你的。 您的目標是安全地儲存密鑰。
假設您決定始終隨身攜帶密鑰，並根據需要提供對儲存的存取。 但您很快就會意識到，這樣的解決方案在實踐中無法很好地擴展，因為每次打開儲存時都需要您親自到場。 你答應的假期怎麼樣？ 此外，更可怕的問題是：如果你丟了唯一的鑰匙怎麼辦？
考慮到您的假期，您決定複製一份鑰匙並將其委託給另一名員工。 但是，您知道這也不理想。 將鑰匙數量增加一倍，鑰匙被偷的可能性也會增加一倍。
無奈之下，您銷毀了副本並決定將原始鑰匙分成兩半。 現在，您可能會認為兩個擁有密鑰碎片的值得信賴的人必須親自在場才能收集密鑰並打開金庫。 這意味著小偷需要偷兩把鑰匙，比偷一把鑰匙更困難一倍。 然而，您很快意識到這個方案並不比只有一把鑰匙好多少，因為如果有人丟失了半把鑰匙，則無法恢復完整的鑰匙。
這個問題可以透過一系列額外的鑰匙和鎖來解決，但這種方法很快就需要 很多 鑰匙和鎖。 您認為理想的設計是共享金鑰，這樣安全性就不會完全依賴一個人。 您還得出結論，碎片的數量必須有某個閾值，以便如果一個碎片丟失（或一個人去度假），整個鑰匙仍然可以使用。
如何分享秘密
這種類型的金鑰管理方案是 Adi Shamir 在 1979 年發表其著作時提出的 。 文章簡單解釋了所謂 
用於有效地將秘密值（例如金鑰）劃分為的閾值方案 部分。 那麼，當且僅當至少 的 零件組裝完畢，即可輕鬆還原秘密 .
從安全的角度來看，該方案的一個重要特性是攻擊者絕對不應該知道任何事情，除非他至少有 部分。 就連存在感 零件不應提供任何資訊。 我們稱這個屬性為 語意安全.
多項式插值
沙米爾閾值方案 圍繞這個概念構建 多項式插值。 如果您不熟悉這個概念，它實際上非常簡單。 事實上，如果您曾經在圖表上繪製過點，然後用直線或曲線將它們連接起來，那麼您就已經使用過它了！
透過兩個點，您可以繪製無限多個 2 次多項式。要從中選擇唯一的一個，您需要第三個點。 圖解：
考慮一個一階多項式， 。 如果你想在圖表上繪製這個函數，你需要幾個點？ 好吧，我們知道這是一個形成直線的線性函數，因此它至少需要兩個點。 接下來，考慮一個二階多項式函數， 。 這是一個二次函數，因此至少需要三個點來繪製圖形。 三階多項式怎麼樣？ 至少有四分。 等等等等。
這個屬性真正酷的地方在於，給定多項式函數的次數並且至少 點，我們可以為這個多項式函數導出額外的點。 我們將這些附加點的外推稱為 多項式插值.
編造一個秘密
您可能已經意識到，這就是沙米爾的巧妙計劃發揮作用的地方。 說出我們的秘密 - 。 我們可以轉 到圖上的一點 並提出一個有次數的多項式函數 ，滿足這一點。 讓我們回憶一下 將是我們所需片段的閾值，因此如果我們將閾值設為三個片段，我們必須選擇二階多項式函數。
我們的多項式將有以下形式 哪裡 и — 隨機選取的正整數。 我們只是建構一個有次數的多項式 ，其中自由係數 - 這是我們的秘密 ，以及對於每個後續的 項中存在隨機選擇的正係數。 如果我們回到原來的例子並假設 ，然後我們得到函數 .
此時我們可以透過連結來產生片段 中唯一的整數 哪裡 （因為這是我們的秘密）。 在此範例中，我們希望以閾值 XNUMX 分佈四個片段，因此我們隨機產生點 並向四個值得信賴的人（密鑰的保管人）每人發送一分。 我們也讓人們知道 ，因為這被認為是公共資訊並且是恢復所必需的 .
恢復秘密
我們已經討論了多項式插值的概念以及它如何成為 Shamir 閾值方案的基礎 。 當四名受託人中的任何三名想要恢復時 ，他們只需要插值 有自己的獨特之處。 為此，他們可以確定自己的觀點 並使用以下公式計算拉格朗日插值多項式。 如果程式設計對你來說比數學更清晰，那麼 pi 本質上就是一個運算符 for，將所有結果相乘，西格瑪是 for，將所有內容相加。
在 我們可以這樣解決它並返回原始多項式函數：
因為我們知道 ， 恢復 簡單地完成：
使用不安全的整數算術
雖然我們已經成功應用了Shamir的基本思想 ，我們留下了一個迄今為止我們一直忽略的問題。 我們的多項式函數使用不安全的整數運算。 請注意，攻擊者在我們的函數圖上每獲得一個額外的點，其他點的可能性就會減少。 當您使用整數算術為多項式函數繪製越來越多的點時，您可以親眼看到這一點。 這與我們聲明的安全目標適得其反，因為攻擊者應該一無所知，直到他們至少擁有 碎片。
為了證明整數運算電路有多弱，請考慮攻擊者獲得兩點的場景 並了解公共訊息 。 從這些資訊他可以推斷出 ，等於二，並將已知值代入公式中 и .
然後攻擊者可以發現 ， 數數 :
既然我們已經定義了 作為隨機選擇的正整數，可能的數量有限 。 使用此信息，攻擊者可以推斷出 ，因為任何大於 5 的值都可以 消極的。 事實證明這是真的，因為我們已經確定
然後攻擊者可以計算可能的值 替換 в :
選項有限 很明顯選擇和檢查值是多麼容易 。 這裡只有五個選項。
解決整數運算不安全的問題
為了消除這個漏洞，Shamir 建議使用模運算，替換 上 哪裡 и ——所有質數的集合。
讓我們快速記住模運算是如何運作的。 帶有指針的時鐘是一個熟悉的概念。 她使用的手錶是 。 時針一過十二，就回到一。 該系統的一個有趣的功能是，僅通過查看時鐘，我們無法推斷出時針轉了多少圈。 然而，如果我們知道時針已經經過了 12 四次，我們就可以使用一個簡單的公式來完全確定已經過去的小時數 哪裡 是我們的除數（這裡 ), 是係數（除數與原始數字相乘多少次而沒有餘數，這裡 ），和 是餘數，通常會傳回模運算子呼叫（這裡 ）。 知道所有這些值可以讓我們解方程 ，但如果我們錯過了係數，我們將永遠無法恢復原始值。
我們可以透過將該方案應用於我們先前的範例並使用來演示這如何提高我們方案的安全性 。 我們的新多項式函數 ，以及新的點 。 現在密鑰保管者可以再次使用多項式插值來重構我們的函數，只是這次加法和乘法運算必須伴隨模數約簡 （例如 ).
使用這個新範例，我們假設攻擊者了解了其中兩個新點， ，以及公開資訊 。 這次，攻擊者根據他擁有的所有信息，輸出以下函數，其中 是所有正整數的集合，並且 表示模係數 .
現在我們的攻擊者再次發現 ，計算 :
然後他再次嘗試 替換 в :
這次他遇到了嚴重的問題。 公式缺失值 , и 。 由於這些變數的組合有無數種，他無法獲得任何額外的資訊。
安全注意事項
沙米爾的秘密共享計劃表明 資訊理論角度的安全。 這意味著即使對於具有無限運算能力的攻擊者，數學也具有抵抗力。 然而，該電路仍存在幾個已知問題。
例如，Shamir 的方案並沒有創建 待檢查的片段，即人們可以隨意呈現虛假片段並幹擾正確秘密的恢復。 擁有足夠資訊的敵對碎片保管者甚至可以透過改變產生另一個碎片 由您自行決定。 這個問題可以使用以下方法來解決 可驗證的秘密共享方案，例如費爾德曼的方案。
另一個問題是任何片段的長度都等於相應的秘密長度，因此秘密的長度很容易確定。 這個問題可以用簡單的方法解決 填充 具有任意數字的秘密，最多固定長度。
最後，值得注意的是，我們的安全擔憂可能超出了設計本身。 對於現實世界的加密應用程序，通常存在側通道攻擊的威脅，攻擊者試圖從應用程式執行時間、快取、崩潰等中提取有用的信息。 如果這是一個問題，那麼在開發過程中應該仔細考慮使用保護措施，例如函數和恆定時間查找、防止記憶體被保存到磁碟，以及一些超出本文範圍的其他注意事項。
演示
上 有沙米爾秘密共享方案的互動演示。 基於庫的演示 ，它本身就是流行程式的 JavaScript 端口 。 請注意計算大值 , и 可能需要一段時間。
來源： www.habr.com