給定部分鍵查找鍵
我正在研究密碼學考試的試卷，但遇到了一個我不確定的問題。
六個使用者已獲得以下部分密鑰
$ P(x) = (k + \sum_{i=1}^2 c_ix^i)\bmod{503} $
User X Y 1 10 25 2 20 405 3 30 272 4 40 129 5 50 479 6 60 316重構密鑰 K 以驗證它是 138。
我嘗試使用牛頓除差來跳過使用公式，但這不起作用。我也嘗試在數據上使用中國剩餘定理，但這也不起作用。我已經嘗試填寫方程式，但我認為我做的並不正確，因此對於如何解決這個問題的任何幫助將不勝感激
除了稍微不尋常的命名法之外，這是沙米爾的秘密共享計劃 $ n=6 $ 和 $ k=3 $ （即，秘密被共享為六部分，其中任意三部分可以組合以檢索秘密）。
在這種情況下，碎片如下：
$$ \begin{align}(x_0, y_0) &= (10, 25) \ (x_1, y_1) &= (20, 405) \ (x_2, y_2) &= (30, 272) \ (x_3, y_3) &= (40, 129) \ (x_4, y_4) &= (50, 479) \ (x_5, y_5) &= (60, 316)\end{align} $$ 檢索秘密只需要其中三個。如維基百科文章中所述，這是通過計算一組拉格朗日基多項式來完成的：
$$ \begin{align}\ell_0 &= \frac{x - x_1}{x_0 - x_1} \cdot \frac{x - x_2}{x_0 - x_2} = \frac{x - 20}{10 - 20} \cdot \frac{x - 30}{10 - 30} = \frac{x^2}{200} - \frac{x}{4} + 3 \ \ell_1 &= \frac{x - x_0}{x_1 - x_0} \cdot \frac{x - x_2}{x_1 - x_2} = \frac{x - 10}{20 - 10} \cdot \frac{x - 30}{20 - 30} = \frac{-x^2}{100} + \frac{2x}{5} - 3 \ \ell_2 &= \frac{x - x_0}{x_2 - x_0} \cdot \frac{x - x_1}{x_2 - x_1} = \frac{x - 10}{30 - 10} \cdot \frac{x - 20}{30 - 20} = \frac{x^2}{200} - \frac{3x}{20} + 1 \end{align} $$ 這些多項式所需要的只是常數項，乘以相應的 $ y $ 為您提供秘密價值的條款：
$$ \begin{align}s &= (3 \cdot 25 - 3 \cdot 405 + 1 \cdot 272) \pmod{503} \ &= 138 \end{align} $$