Cryptanalysis
我們如何解決算術以 13 為模的 Shamir(2,3) 共享方案？
我正在嘗試獲取秘密 S 並且我有 3 個值 (2,2)(6,3)(4,9) 並且知道我們正在工作的模數是 13。
我嘗試使用拉格朗日基多項式並得到 8，但我不確定這是否正確，而且我無法找到以 ax+by= c (mod 13) 的形式導出直線方程的方法。
你應該選擇兩個點。（例如（2,2）和（6,3））。然後你可以計算拉格朗日插值多項式如下：
$ f(x)=2.(\dfrac{x-6}{2-6})+3.(\dfrac{x-2}{6-2})=-(\dfrac{2x-12}{4})+(\dfrac{3x-6}{4}) $
$ \ \ \ \ \ \ \ \ =(\dfrac{x+6}{4})=(\dfrac{x}{4})+(\dfrac{6}{4})\ mod(13)=10x+60\ mod(13)=10x+8 $
因為 $ 4^{-1}=10 \ mod(13) $ .
您期望的方程形式通常不適用於 Shamir 的共享方案。相反，方程通常表示為多項式：
$$ f\left(x\right)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1},! \mod p, $$ 在哪裡 $ k $ 是恢復秘密所需的件數； $ a_i $ 是隨機係數（模 p）和 $ p $ 是 13（在你的情況下）。 根據這個，你的“線方程”（在用拉格朗日插值多項式恢復它之後）應該看起來像：
$$ f\left(x\right)=10x+8\mod 13. $$ 如你看到的 $ a_0 $ 這裡的係數是 $ 8 $ 這樣你的猜測是正確的（因為 $ a_0 $ 是秘密本身）。