讓我們考慮一個需要確保銀行金庫安全的場景。如果沒有鑰匙，它是絕對無法進入的，鑰匙是你上班第一天時得到的。您的目標是確保金鑰的安全。

假設您決定隨時攜帶鑰匙，並在需要時授予對保險庫的存取權限。但您很快就會意識到，這種解決方案在實踐中擴展性不佳，因為每次打開儲存時都需要您的實際存在。承諾給你的假期怎麼了？而且，更可怕的問題是：如果你遺失了唯一的鑰匙怎麼辦？

考慮到您要去度假，您決定複製一把鑰匙並將其委託給另一名員工。但是，您明白這也不是理想的。鑰匙數量加倍，鑰匙被偷的可能性也會加倍。

無奈之下，您銷毀了副本並決定將原始金鑰一分為二。現在，您認為必須有兩個值得信賴的人持有鑰匙碎片親自到場來組裝鑰匙並打開保險庫。這意味著小偷必須偷取兩塊碎片，這比偷取一把鑰匙的難度高出一倍。然而，您很快就會意識到，這種方案並不比僅有一把鑰匙好多少，因為如果有人丟失了一半鑰匙，就無法恢復完整的鑰匙。

這個問題可以透過一系列額外的鑰匙和鎖來解決，但這種方法很快就會需要 很多 鑰匙和鎖。您認為理想的方案是分割金鑰，這樣安全性就不會完全依賴一個人。您還得出結論，碎片的數量必須有一個閾值，這樣如果一個碎片丟失（或如果該人去度假），整個密鑰仍然可以發揮作用。

如何分享秘密

這種金鑰管理方案是 Adi Shamir 在 1979 年發表其著作時提出的 《如何分享秘密》。文章簡要地解釋了所謂的 一個閾值方案，用於有效地將秘密值（例如加密金鑰）拆分為 部分。那麼，當且僅當至少 的 零件收集起來，很容易恢復秘密 .

從安全角度來看，該方案的一個重要特性是，攻擊者不應該了解任何東西，除非他至少 部分。甚至存在 部分不應提供任何資訊。我們稱此屬性為 語意安全.

多項式插值

沙米爾的門檻方案 圍繞概念構建 多項式插值。如果您不熟悉這個概念，它實際上非常簡單。事實上，如果您曾經在圖表上畫過點，然後用直線或曲線連接它們，那麼您已經使用過它了！

透過兩點可以繪製無限多個 2 次多項式。為了選擇唯一的一個，需要第三個點。圖解： 維基百科

讓我們考慮一個一次多項式， 。如果您想在圖表上繪製此函數，您需要多少個點？嗯，我們知道它是一個形成直線的線性函數，所以至少需要兩個點。接下來，我們考慮一個二次多項式函數， 。這是一個二次函數，因此至少需要三個點來繪製圖形。三次多項式怎麼樣？至少四分。等等等等。

這個屬性真正酷的地方在於，給定多項式函數的次數，至少 點，我們可以為這個多項式函數推導出額外的點。我們稱這些附加點的外推 多項式插值.

編造秘密

您可能已經意識到 Shamir 的巧妙計劃在這裡發揮了作用。假設我們的秘密 - 。我們可以改變 到圖上的某一點 並得出一個次數為 ，滿足這一點。讓我們回想一下 將是我們所需片段的閾值，因此如果我們將閾值設為三個片段，則我們必須選擇一個二次多項式函數。

我們的多項式的形式為 哪裡 и — 隨機選取的正整數。我們只是建構一個次數為 ，其中是自由係數  -這是我們的秘密 以及隨後的每一個 成員具有隨機選擇的正係數。如果我們回到最初的例子並假設 ，然後我們得到函數 .

在這個階段，我們可以透過連結來產生片段 中唯一的整數 哪裡 （因為這是我們的秘密）。在這個例子中，我們想要分配四個片段，閾值為三，因此我們隨機產生點 我們向四個值得信賴的人（密鑰的保管者）每人發送一分。我們也告訴人們 因為這被視為公共訊息，並且對於恢復是必要的 .

恢復秘密

我們已經討論了多項式插值的概念以及它如何成為 Shamir 閾值方案的基礎。 。當四位受託人中的任何三位想要恢復 ，他們只需要插入 有其獨特的之處。為了做到這一點，他們可以定義自己的觀點 並利用以下公式計算拉格朗日插值多項式。如果你對程式設計的理解比對數學的理解更深刻，那麼 π 本質上就是一個運算符 for，將所有結果相乘，sigma 為 for，將所有內容整合在一起。

在 我們可以如下解決這個問題並恢復原始多項式函數：

因為我們知道 ， 恢復 它的執行很簡單：

使用不安全的整數運算

儘管我們已經成功地運用了 Shamir 的基本思想 ，我們面臨一個至今仍被忽視的問題。我們的多項式函數使用不安全的整數運算。請注意，攻擊者在我們的函數圖上獲得的每一個額外點，其他點的可能性就會減少。當您使用整數運算繪製多項式函數中點數不斷增加的圖形時，您可以親眼看到這一點。這與我們所述的安全目標背道而馳，因為攻擊者至少應該在 碎片。

為了證明整數算術方案的脆弱性，請考慮這樣一種情況：攻擊者有兩個點 並了解以下公開信息 。根據這些信息，他可以推斷 ，等於二，並將已知值代入公式 и .

攻擊者可以發現 ，已經計算過 :

由於我們已經定義 作為隨機選擇的正整數，可能的 。利用這些訊息，攻擊者可以推斷 ，因為任何大於 5 的都可以 消極的。事實證明這是正確的，因為我們已經確定

然後攻擊者可以計算可能的值 替換 в :

由於選擇範圍有限 很明顯，選擇和檢查值是多麼容易 。這裡只有五個選項。

解決不安全整數運算的問題

為了消除這種漏洞，Shamir 建議使用模組化演算法，取代 上 哪裡 и — 所有質數的集合。

讓我們快速回顧一下模運算的工作原理。帶有指針的時鐘是一個熟悉的概念。她使用的手錶 。時針一過十二點，就回到一點。這個系統的一個有趣特性是，僅透過查看時鐘，我們無法推斷出時針轉了多少圈。然而，如果我們知道時針已經經過了四次 12，我們完全可以用一個簡單的公式來確定已經過去的小時數 哪裡  - 這是我們的除數（這裡 ),  — 這是係數（除數除以原數的多少倍，這裡 ），和  — 這是餘數，通常透過呼叫模運算子返回（此處 ）。知道所有這些值使我們能夠解出以下方程 ，但如果我們遺漏了一個係數，我們將永遠無法恢復原始值。

我們可以透過將方案應用於前面的範例並使用來演示如何提高方案的安全性 。我們的新多項式函數 和新點 。現在，密鑰保管者可以再次使用多項式插值來重建我們的函數，只是這次加法和乘法運算必須伴隨模數減少。 （例如 ).

使用這個新的例子，假設攻擊者了解了其中兩個新點， 以及公開資訊 。這次，攻擊者根據他掌握的所有信息，得出以下函數，其中  — 所有正整數的集合，以及 表示模組的係數 .

現在我們的攻擊者再次找到了它 ，計算 :

然後他又試著退出 替換 в :

這次他遇到了嚴重的問題。公式中沒有值 , и 。由於這些變數的組合有無數種，因此他無法獲得任何額外的資訊。

安全注意事項

Shamir 的秘密共享方案表明 從資訊理論角度看安全。這意味著數學甚至能夠抵禦擁有無限運算能力的攻擊者。然而，該方案仍存在一些已知問題。

例如，Shamir 的方案並沒有創造 檢查碎片即人們可以自由地呈現虛假的碎片，並幹擾正確秘密的恢復。擁有足夠資訊的敵對碎片持有者甚至可以透過改變 由您自行決定。這個問題可以透過以下方法解決 可驗證秘密共享方案，例如費爾德曼方案。

另一個問題是，任何片段的長度都等於對應的秘密長度，因此秘密的長度很容易確定。這個問題很容易解決 內餡 具有任意數字的秘密，長度不超過固定值。

最後，值得注意的是，我們的安全擔憂可能超出了該計劃本身。對於真正的加密應用程序，通常存在旁道攻擊的威脅，攻擊者試圖從應用程式的執行時間、快取、崩潰等中提取有用的信息。如果擔心這一點，則應在開發過程中仔細考慮使用保護措施，例如恆定時間函數和查找，防止記憶體刷新到磁碟，以及一些超出本文範圍的其他事項。

演示

上 此頁 這裡有一個 Shamir 秘密共享方案的互動式示範。該演示是在圖書館的基礎上進行的 ssss-js，它本身就是一個流行程式的 JavaScript 端口 SSSS。請注意，計算較大的值 , и 這可能需要一些時間。

來源： www.habr.com