這次我用另一種方法解出秘密S
設方程式\( a_0+a_1x+a_2x^2+\ldots+a_{k-1}x^{k-1}\equiv y \pmod{p} \)
通過\( (x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k) \)共k個點
將這k個點坐標代入方程式得到
\( a_0+a_1 x_1+a_2 x_1^2+\ldots+a_{k-1}x_1^{k-1} \equiv y_1 \pmod{p} \)
\( a_0+a_1 x_2+a_2 x_2^2+\ldots+a_{k-1}x_2^{k-1} \equiv y_2 \pmod{p} \)
…
\( a_0+a_1 x_k+a_2 x_k^2+\ldots+a_{k-1}x_k^{k-1} \equiv y_k \pmod{p} \)
改寫成矩陣形式
\( \displaystyle \pmatrix{
1 & x_1 & x_1^2 & \ldots & x_1^{k-1} \cr
1 & x_2 & x_2^2 & \ldots & x_2^{k-1} \cr
\vdots & \vdots & \vdots & \ddots & \vdots \cr
1 & x_k & x_k^2 & \ldots & x_k^{k-1}}
\pmatrix{a_0 \cr a_1 \cr a_2 \cr \vdots \cr a_{k-1}} \equiv
\pmatrix{y_1 \cr y_2 \cr y_3 \cr \vdots \cr y_k} \pmod{p} \)
上面最左邊的矩陣稱為Vandermonde矩陣
http://en.wikipedia.org/wiki/Vandermonde_matrix
其行列式\( \displaystyle det(V)=\prod_{1 \le i<j \le k}(x_j-x_i) \)
因為\( x_i \ne x_j \)，\( i \ne j \)，所以行列式值不為0，代表整個聯立方程組有唯一解
其中常數項\( a_0 \)就是當初設定的秘密S
例子
設方程式\( a_0+a_1x+a_2x^2+\ldots+a_5x^5 \equiv y \pmod{65537} \)
通過\( (8,4956),(4,-16004),(1,2233),(7,-6651),(3,16789),(2,-16387) \)共6個點
建立聯立方程組的矩陣形式
\( \displaystyle \pmatrix{
1 & 8^1 & 8^2 & 8^3 & 8^4 & 8^5 \cr
1 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 \cr
1 & 1^1 & 1^2 & 1^3 & 1^4 & 1^5 \cr
1 & 7^1 & 7^2 & 7^3 & 7^4 & 7^5 \cr
1 & 3^1 & 3^2 & 3^3 & 3^4 & 3^5 \cr
1 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5}
\pmatrix{a_0 \cr a_1 \cr a_2 \cr a_3 \cr a_4 \cr a_5} \equiv
\pmatrix{4956 \cr -16004 \cr 2233 \cr -6651 \cr 16789 \cr -16387} \pmod{65537} \)
解出唯一解
\( \displaystyle \pmatrix{a_0 \cr a_1 \cr a_2 \cr a_3 \cr a_4 \cr a_5} \equiv
\pmatrix{-\frac{181843183}{315} \cr -\frac{3946562}{63} \cr \frac{9579461}{126} \cr -\frac{938557}{36} \cr \frac{107371}{30} \cr -\frac{2057}{12}} \equiv
\pmatrix{-181843183 \times 315^{-1} \cr -3946562 \times 63^{-1} \cr 9579461 \times 126^{-1} \cr -938557 \times 36^{-1} \cr 107371 \times 30^{-1} \cr -2057 \times 12^{-1}} \equiv
\pmatrix{12345 \cr -5429 \cr 31816 \cr 4877 \cr 18871 \cr 5290} \pmod{65537} \)
當初的多項式函數\( f(x)=12345-5429x+31816x^2+4877x^3+18871x^4+5290x^5 \)
其中常數項就是秘密\( S=12345 \)
設定秘密S
(這個數字可自行修改，但\( S<p \) )
(%i1) S:12345;
(%o1) 12345
設定在\( F_p \)底下運算，其中p為質數
(%i2)
p:65537;
modulus:p;
(%o2) 65537
(%o3) 65537
設定n個人共享秘密，至少要k個人才能重建秘密
(這兩個數字可自行修改，但\( n \ge k \) )
(%i4)
n:8;
k:6;
(%o4) 8
(%o5) 6
隨機產生k-1次多項式，其中常數項為秘密S
(%i6) f(x):=''(S+apply("+",create_list(random(p)*x^i,i,1,k-1)));
(%o7) \( f(x) :=5290x^5+18871x^4+4877x^3+31816x^2+60108x+12345 \)
產生n個點座標
(%i7) create_list([i,f(i)],i,1,n);
(%o7) [[1,133307],[2,770057],[3,3424713],[4,11321897],[5,30043535],[6,68163657],[7,137883197],[8,255664793]]
將點座標mod p後分派給這n個人
(%i8) rat(%);
(%o8)/R/ [[1,2233],[2,-16387],[3,16789],[4,-16004],[5,27589],[6,5177],[7,-6651],[8,4956]]
假設有k個人聚在一起要重建秘密
(%i9)
random_permutation(%)$
shadows:create_list(%[ i ],i,1,k);
(%o10)/R/ [[8,4956],[4,-16004],[1,2233],[7,-6651],[3,16789],[2,-16387]]
建立\( x_i \)的係數矩陣
(%i11) genmatrix (lambda([ i, j],shadows[ i ][1]^j), k, k-1,1,0);
(%o11)/R/ \( \displaystyle \pmatrix{
1 & 8 & 64 & 512 & 4096 & 32768 \cr
1 & 4 & 16 & 64 & 256 & 1024 \cr
1 & 1 & 1 & 1 & 1 & 1 \cr
1 & 7 & 49 & 343 & 2401 & 16807 \cr
1 & 3 & 9 & 27 & 81 & 243 \cr
1 & 2 & 4 & 8 & 16 & 32} \)
建立\( y_i \)的係數矩陣
(%i12) genmatrix(lambda([ i,j], shadows[ i][2]), k,1);
(%o12)/R/ \( \displaystyle \pmatrix{4956 \cr -16004 \cr 2233 \cr -6651 \cr 16789 \cr -16387} \)
解出未知數\( a_0,a_1,a_2,a_3,a_4,a_5 \)
(%i13) linsolve_by_lu(%o11,%o12);
(%o13) \( \displaystyle [ \pmatrix{
-\frac{181843183}{315} \cr -\frac{3946562}{63} \cr \frac{9579461}{126} \cr -\frac{938557}{36} \cr \frac{107371}{30} \cr -\frac{2057}{12}},false] \)
(%i14) rat(%[1]);
(%o14)/R/ \( \displaystyle \pmatrix{12345 \cr -5429 \cr 31816 \cr 4877 \cr 18871 \cr 5290} \)
其中\( a_0 \)就是祕密\( S=12345 \)
(%i15) S:%[1][1];
(%o15)/R/ 12345
[
本帖最後由 bugmens 於 2013-7-13 06:09 AM 編輯 ]
