分割秘密 (How to Share a Secret)

15 Sep, 2026

如何把你的密碼用某種方式告訴你的 7 位家人，使得只有在至少 5 個人同意時才能得到密碼？

Shamir 在 1979 年的 How to Share a Secret 討論

如何將一個秘密分割成多個碎片，使得只有達到特定數量的碎片才能重建原始秘密。

問題

如何將一個資料 $D$ 轉變成 $n$ 份碎片 $D_1,...,D_n$ 使得

1. 獲得其中任意 $k$ 份（或更多）碎片就有辦法還原出原始資料 $D$。
2. 只獲得其中 $k-1$ 份（或更少）碎片則無法還原出原始資料（也不能獲得部份資訊）。

這樣的一個方案被稱為 $(k,n)$ threshold scheme。

具體方案

Shamir 給出的方案是利用多項式插值（台灣高中會學到拉格朗日插值多項式）。他用到這個性質：

知道一個 $k-1$ 次多項式在 $k$ 個點的值，就可以唯一決定這個多項式。

1. 選一個 $k-1$ 次多項式 $q(x)=a_0+a_{1}x+...+a_{k-1}{x}^{k-1}$，其中
   • $a_0=D$
   • $a_1,...,a_{k-1}$ 是隨機選取的。
2. 計算 $D_1=q(1),...,D_i=q(i),...,D_n=q(n)$。
   • 其中 $(1,D_1),...,(n,D_n)$ 就是原本問題中的 $n$ 份碎片（每份碎片包含他的編號 $i$ 跟一個數字 $D_i$）。

這個方案滿足原本的要求：

1. 只要得到任意 $k$ 個 $(i,D_i)$ 的值，就可以唯一決定這個多項式，因此可以反推這個多項式在 $x=0$ 的值 $q(0)$，也就是原始資料 $D$。
2. 如果只拿到 $k-1$ 份碎片，則無法得知 $q(0)$ 的任何資訊。

細節

文章中提到

• 要選一個質數 $p$ 進行模運算（$p$ 要比 $D$ 跟 $n$ 大）。
• 多項式的係數 $a_1,...,a_{k-1}$ 都是從 $[0,p)$ 隨機選取。

這些比較像是實作細節，不影響對方案根本的理解。

其他性質

1. 在 $k$ 固定的情況下，可以創造新的碎片 $(i,D_i)$ 而不影響已經產生的碎片。

參考

• Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612–613. https://doi.org/10.1145/359168.359176