密碼系統必須使用金匙來保護一些秘密文件，因此一個密碼系統要真正安全可靠，除了密碼系統本身在設計上要考慮到種種攻擊之外，如何保護系統的金匙，當然也是一個重要的課題。
　　在公開金匙密碼系統內，所有的公開以及秘密金匙均須安全而妥善的保管(即使是公開金匙也不想讓密碼系統使用者之外的人得知)，一個比較直接的想法便是找一把系統主金匙(master key)來保護管理這許許多多的金匙，但是又該如何來管理這把異常重要的系統主金匙呢？一般而言我們可能會有以下幾個想法：
1.找一個可信任的人來保管。
2.將此主金匙複製幾份，分給好幾個可信賴者來保管。
3.將此主金匙分成幾個小金匙，分給幾個可信賴者來保管，需這幾個人集合在一起，才能拼湊出完整的系統主金匙。

　　以上幾種保管主金匙的方法都有一些缺點存在。第一個方法如果所託非人，那後果便不堪設想了，即使這個人確實是可信賴的，但若此遺失了主金匙，或者在某一些原因之下離開了系統(例如死亡)，那麼整個密碼系統的維護便面臨重大的危機，所以此法可行性不高。第二種方法當然比較不容易遺失，但是因金匙保管者人數增加，發生背叛的危險性也相對增高，因此可行性也不高；第三種方法的可信度明顯提高，因為所找出的幾個可信賴者同時背叛的機率實在太低，但若這幾個保管主金匙的人，只要有一人不願意來拼湊出主金匙的話，那後果便不堪設想了。
　　為了克服以上幾種保管方法的一些缺失，1979年，在現代密碼學極為有名的學者Shamir，以及另一學者Blakey分別提出秘密分享方案(secret sharing scheme)的構想與方法來解決主金匙管理的問題，這個方案的構想如下：
1.將密碼系統主金匙透過某種方法分成n把小金匙(shadow)，分別交給n個人來保管。
2.保管小金匙的這n個人中之任意t個人會合(kn)，可共同推導出密碼系統的主金匙。
3.知道任意k−1把(或更少)的小金匙，無法得知有關主金匙的任何訊息。

　　上述之秘密分享方案由於是用來保護系統主金匙的一個方案，所以又稱為金匙保護方案(key safe-guarding scheme)；又由於只要擁有不少於t把小金匙即可推導出主金匙，換言之，t把小金匙是推導出主金匙的一個門檻，所以也稱為門檻方案(threshold scheme)。
(本段落節錄自《現代密碼學入門與程式設計》p4-3)


這幾本書都有提到秘密分享的內容
1.沈淵源，“密碼學之旅－與MATHEMATICA同行”

2.賴溪松、韓亮、張真誠，“近代密碼學及其應用”

3.楊吳泉，“現代密碼學入門與程式設計”

秘密分享技術與應用
http://www.cis.nctu.edu.tw/~ippr/Doc/Dec88/4.doc

機密共享機制
http://ec2.ba.ntust.edu.tw/mic/d ... 89%E5%85%A8ch10.doc

門檻式簽章之介紹
http://elab.im.ncue.edu.tw/ppt/d ... 7%E9%9B%86/C135.pdf

Secret sharing
http://en.wikipedia.org/wiki/Secret_sharing

[ 本帖最後由 bugmens 於 2013-12-20 11:00 PM 編輯 ]

1.秘密分享方案介紹－Shamir

假設分派者(Dealer)選定要共享的秘密S及一個質數p，滿足0Sp。分派者任意挑選一個k−1次方的多項式f(x)=a0+a1x+a2x2++ak−1xk−1，滿足a0=S，0a1a2…ak−1p。
分派者利用f(x)產生n個子金匙(if(i)),i=12n。每對(if(i))可視為多項式f(x)在坐標平面上的一個點，由於f(x)為k−1次方的多項式，因此k對或k對以上的點坐標可惟一決定f(x)，進而重建出秘密S。

以下的範例出自http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing，只是沒有在Zp底下運算。

要先載入interpol.mac才能使用lagrange指令
(%i1)　load("interpol.mac");
(%o1)　"C:/PROGRA~1/MAXIMA~1.0-2/share/maxima/5.28.0-2/share/numeric/interpol.mac"

設定秘密為S=1234，n=6個人共享秘密，至少要k=3位才能重組秘密
(%i2)　S:1234;
(%o2)　1234

需要3個人才能重組秘密，所以f(x)要為二次多項式
其中常數項為秘密S，一次項和二次項係數為隨機的整數
''S代表將1234代入S，若沒有''則為f(x):=S+166x+94x^2
(%i3)　f(x):=''S+166*x+94*x^2;
(%o3)　f(x):=1234+166x+94x2

設定6個人要分享此秘密，計算f(x)上6個點座標分派給這6個人
(%i4)　create_list([k,f(k)],k,1,6);
(%o4)　[[1,1494],[2,1942],[3,2578],[4,3402],[5,4414],[6,5614]]

假設第2,4,5位聚在一起要重組秘密S，利用拉格朗日插值多項式計算出f(x)
(%i5)　lagrange([%[2],%[4],%[5]]);
(%o5)　34414(x−4)(x−2)−1701(x−5)(x−2)+3971(x−5)(x−4)

(%i6)　ratsimp(%);
(%o6)　94x2+166x+1234

其中常數項就是當初設定的祕密S
(%i7)　ev(%,x=0);
(%o7)　1234

參考資料
Shamir's Secret Sharing
http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
Adi Shamir,  How to Share a Secret, Communications of the ACM, Volume 22(11), pp. 612 - 613, Association for Computing Machinery, 1979.
https://www.google.com.tw/search ... chrome&ie=UTF-8

延續上一篇Shamir方案，因為範例取自wiki，f(x)係數都是固定的，所以整體比較沒有變化。所以在這篇提供另一個範例，你可以自行設定Spnk等參數，每次執行時f(x)係數也都是隨機產生，而且設定在Fp底下運算，就算得到的結果是分數，但計算分母的反元素後再乘上分子就會是當初的秘密S。


要先載入interpol.mac才能使用lagrange指令
(%i1)　load("interpol.mac");
(%o1)　C:/PROGRA~1/MAXIMA~1.0-2/share/maxima/5.28.0-2/share/numeric/interpol.mac

設定秘密S
(這個數字可自行修改，但Sp )
(%i2)　S:12345;
(%o2)　12345

設定在Fp底下運算，其中p為質數
(%i3)
p:65537;
modulus:p;
(%o3)　65537
(%o4)　65537

設定n個人共享秘密，至少要k個人才能重建秘密
(這兩個數字可自行修改，但nk )
(%i5)
n:8;
k:6;
(%o5)　8
(%o6)　6

隨機產生k-1次多項式，其中常數項為秘密S
(%i7)　f(x):=''(S+apply("+",create_list(random(p)*x^i,i,1,k-1)));
(%o7)　f(x):=5290x5+18871x4+4877x3+31816x2+60108x+12345

產生n個點座標
(%i8)　create_list([i,f(i)],i,1,n);
(%o8)　[[1,133307],[2,770057],[3,3424713],[4,11321897],[5,30043535],[6,68163657],[7,137883197],[8,255664793]]

將點座標mod p後分派給這n個人
(%i9)　rat(%);
(%o9)/R/　[[1,2233],[2,-16387],[3,16789],[4,-16004],[5,27589],[6,5177],[7,-6651],[8,4956]]

假設有k個人聚在一起要重建秘密
(%i10)
random_permutation(%)$
create_list(%[ i ],i,1,k);
(%o11)/R/　[[8,4956],[4,-16004],[1,2233],[7,-6651],[3,16789],[2,-16387]]

利用拉格朗日插值多項式計算通過這k個點座標的k-1次多項式
(%i12)　lagrange(%);
(%o12)　1059(x−7)(x−4)(x−3)(x−2)(x−1)+40739(x−8)(x−4)(x−3)(x−2)(x−1)
−184001(x−8)(x−7)(x−3)(x−2)(x−1)−4016789(x−8)(x−7)(x−4)(x−2)(x−1)
−6016387(x−8)(x−7)(x−4)(x−3)(x−1)+36319(2−x)(x−8)(x−7)(x−4)(x−3)

其中常數項為當初設定的祕密S
(%i13)　ev(%,x=0);
(%o13)　156804412

若結果出現分數，但在Fp底下運算
則秘密S=分子分母−1(modp)
(%i14)　ratsimp(%);
(%o14)　12345

這次我用另一種方法解出秘密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 編輯 ]

2.秘密分享方案介紹－Blakley

分派者(Dealer)選定要共享的秘密S及一個質數p，滿足 0<S<p 。
令 x_0=S 再任意選兩個數字 y_0,z_0 形成空間中的一個點坐標 (x_0,y_0,z_0) 。
任意選三個數字 a,b,c 當作平面方程式的 x,y,z 係數，再將 (x_0,y_0,z_0) 代入平面方程式得到常數項 d 。
反複以上的步驟得到平面方程組 a_i x+b_i y+c_i z=d_i ， 1 \le i \le n ，而且全部的平面都會通過點 (x_0,y_0,z_0) 。
至少要三個平面才能求出交點 (x_0,y_0,z_0) ，其中秘密為 x_0=S


圖來自http://en.wikipedia.org/wiki/Secret_sharing#Blakley.27s_scheme

例子
設定點坐標 (12345,60108,31816) ，質數 p=65537
隨機產生六個平面方程式，全部的平面都會通過 (12345,60108,31816)
\matrix{6093 x+63576 y+58177 z=8825 \cr 57696 x+31204 y+13769 z=−32708 \cr 6671 x+24953 y+40161 z=21652 \cr 43481 x+47688 y+20331 z=−1181 \cr 49113 x+5683 y+30540 z=−24341 \cr 4877 x+18871 y+5290 z=−30642}
任選其中三個平面方程式
\matrix{57696 x+31204 y+13769 z=-32708 \cr 43481 x+47688 y+20331 z=-1181 \cr 49113 x+5683 y+30540 z=-24341}
解聯立方程式得到 x=12345,y=-5429,z=31816
其中 x=12345 就是當初設定的祕密S


要先載入basic.mac才能使用push指令
(%i1)　load("basic.mac");
(%o1)　C:/PROGRA~1/MAXIMA~1.0-2/share/maxima/5.28.0-2/share/macro/basic.mac

設定顯示順序為x,y,z
　　預設順序為z,y,x
(%i2)　powerdisp:true;
(%o2)　true

設定秘密S
(%i3)　S:12345;
(%o3)　12345

設定在Fp底下運算，其中p為質數
(%i4)
p:65537;
modulus:p;
(%o4)　65537
(%o5)　65537

假設全部的平面的交點在(x0,y0,z0)
其中x0為秘密S，y0,z0為任意數字
(%i6)
x0:S;
y0:random(p);
z0:random(p);
(%o6)　12345
(%o7)　60108
(%o8)　31816

有n個人要共享秘密
(%i9)　n:6;
(%o9)　6

產生n個平面方程式ax+by+cz=d,其中a,b,c為任意數字
將(x0,y0,z0)代入平面方程式後得到常數項d
(%i10)
planes:[]$
for k:1 thru n do
  (a:random(p),
   b:random(p),
   c:random(p),
   d:rat(a*x0+b*y0+c*z0),
   push(a*x+b*y+c*z=d,planes)
  )$
planes;
(%o12)/R/　 \matrix{[ 6093 x+63576 y+58177 z=8825, \cr 57696 x+31204 y+13769 z=-32708, \cr 6671 x+24953 y+40161 z=21652 , \cr 43481 x+47688 y+20331 z=-1181, \cr 49113 x+5683 y+30540 z=-24341, \cr 4877 x+18871 y+5290 z=-30642]}

任意三個人的平面方程式就可以解出秘密S
(%i13)　solve([planes[2],planes[4],planes[5]],[x,y,z]);
(%o13)　 [ [x=12345,y=-5429,z=31816] ]

但只有兩個平面方程式就無法解出秘密
(%i14)　solve([planes[2],planes[3]],[x,y,z]);
(%o14)　 [ [x=18576-28066 \%r1,y=-22494+25096 \%r1,z=\%r1] ]

[ 本帖最後由 bugmens 於 2013-7-6 07:31 AM 編輯 ]

上一篇可以稱為 (3,6) 的秘密分享方案，代表有6個參與者，每位都有一個空間中的平面方程式，至少3位才能求出平面的交點來重組秘密。

一般性的 (k,n) 秘密分享方案需要 n 個 k 維的超平面(hyperplanes)方程式( a_1x_1+a_2x_2+a_3 x_3+\ldots+a_kx_k=b )。
當k個人聚在一起要重組秘密時，將超平面方程式收集起來
\displaystyle \matrix{ a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1k}x_k=b_1 \pmod{p} \cr a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2k}x_k=b_2 \pmod{p} \cr \ldots \cr a_{k1}x_1+a_{k2}x_2+a_{k3}x_3+\ldots+a_{kk}x_k=b_k \pmod{p}}
改寫成矩陣形式
\displaystyle \pmatrix{ a_{11} & a_{12} & a_{13} & \ldots & a_{1k} \cr a_{21} & a_{22} & a_{23} & \ldots & a_{2k} \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr a_{k1} & a_{k2} & a_{k3} & \ldots & a_{kk} } \pmatrix{x_1 \cr x_2 \cr x_3 \cr \vdots \cr x_k} \equiv \pmatrix{b_1 \cr b_2 \cr b_3 \cr \vdots \cr b_k} \pmod{p}
因為這些超平面方程式互不平行，所以聯立方程組有惟一解，其中 x_1 就是秘密S


例子
有8個人各擁有一個超平面方程式，約定在 F_{65537} 底下運算
\displaystyle \matrix{ 49113x_1+5683x_2+30540x_3+43481x_4+47688x_5+20331x_6=-8762 \cr 6671x_1+24953x_2+40161x_3+57696x_4+31204x_5+13769x_6=16308 \cr 6093x_1+63576x_2+58177x_3+11336x_4+56130x_5+52284x_6=17725 \cr 1550x_1+61347x_2+51763x_3+6103x_4+56842x_5+24958x_6=19053 \cr 54066x_1+34186x_2+31828x_3+8249x_4+23728x_5+47682x_6=-18298 \cr 58433x_1+20124x_2+62414x_3+22027x_4+34969x_5+63343x_6=-8396 \cr 16502x_1+23915x_2+26371x_3+45158x_4+30220x_5+16212x_6=20957 \cr 58810x_1+59547x_2+21555x_3+32712x_4+20787x_5+12223x_6=-20354}

只要有6個人聚在一起就能重組秘密
\displaystyle \pmatrix{ 6093 & 63576 & 58177 & 11336 & 56130 & 52284  \cr 54066 & 34186 & 31828 & 8249 & 23728 & 47682 \cr 58810 & 59547 & 21555 & 32712 & 20787 & 12223 \cr 49113 & 5683 & 30540 & 43481 & 47688 & 20331 \cr 58433 & 20124 & 62414 & 22027 & 34969 & 63343 \cr 6671 & 24953 & 40161 & 57696 & 31204 & 13769 } \pmatrix{x_1 \cr x_2 \cr x_3 \cr x_4 \cr x_5 \cr x_6} \equiv \pmatrix{17725 \cr -18298 \cr -20354 \cr -8762 \cr -8396 \cr 16308} \pmod{65537}
解聯立方程式得到交點
\displaystyle \pmatrix{x_1 \cr x_2 \cr x_3 \cr x_4 \cr x_5 \cr x_6} \equiv \pmatrix{12345 \cr -5429 \cr 31816 \cr 4877 \cr 18871 \cr 5290} \pmod{65537}

其中 x_1=12345 就是秘密S


設定秘密S
(%i1)  S:12345;
(%o1)　12345

設定在Fp底下運算，其中p為質數
(%i2)
p:65537;
modulus:p;
(%o2)　65537
(%o3)　65537

有n個人要共享秘密，至少k個人才能重組秘密
(%i4)
n:8;
k:6;
(%o4)　8
(%o5)　6

假設全部平面的交點(x1,x2,x3,x4,x5,x6)
其中x1=S，X2,X3,X4,X5,X6為任意數字
(%i6)　matrixX:genmatrix(lambda([i,j],if i=1 then S else random(p)),k,1);
(%o6)　 \displaystyle \pmatrix{12345 \cr 60108 \cr 31816 \cr 4877 \cr 18871 \cr 5290}

產生n個超平面方程式a1x1+a2x2+...+a6x6=b
(%i7)　matrixA:genmatrix(lambda([i,j],random(p)),n,k);
(%o7)　 \displaystyle \pmatrix{ 49113 & 5683 & 30540 & 43481 & 47688 & 20331 \cr 6671 & 24953 & 40161 & 57696 & 31204 & 13769 \cr 6093 & 63576 & 58177 & 11336 & 56130 & 52284 \cr 1550 & 61347 & 51763 & 6103 & 56842 & 24958 \cr 54066 & 34186 & 31828 & 8249 & 23728 & 47682 \cr 58433 & 20124 & 62414 & 22027 & 34969 & 63343 \cr 16502 & 23915 & 26371 & 45158 & 30220 & 16212 \cr 58810 & 59547 & 21555 & 32712 & 20787 & 12223}

矩陣A和交點坐標相乘得到超平面方程式的常數項(矩陣B)
A.X=B
(%i8)　matrixB:rat(matrixA.matrixX);
(%o8)/R/　 \displaystyle \pmatrix{-8762 \cr 16308 \cr 17725 \cr 19053 \cr -18298 \cr 8396 \cr 20957 \cr -20354}

將這n個超平面方程式分派給n個人
(%i9)
transpose(append(transpose(matrixA),transpose(matrixB)))$
create_list(%[ i ],i,1,n);
(%o10)/R/    \matrix{[[49113,5683,30540,43481,47688,20331,-8762],\cr [ 6671,24953,40161,57696,31204,13769,16308], \cr [6093,63576, 58177,11336,56130,52284,17725], \cr [1550,61347,51763,6103, 56842,24958,19053], \cr [54066,34186,31828,8249,23728,47682,- 18298], \cr [58433,20124,62414,22027,34969,63343,-8396], \cr [ 16502,23915,26371,45158,30220,16212,20957], \cr [58810,59547, 21555,32712,20787,12223,-20354]]}

其中k個人聚在一起要重組秘密S
(%i11)
random_permutation(%)$
shadows:apply('matrix,rest(%,n-k));
(%o12)/R/　 \displaystyle \pmatrix{ 6093 & 63576 & 58177 & 11336 & 56130 & 52284 & 17725 \cr 54066 & 34186 & 31828 & 8249 & 23728 & 47682 & -18298 \cr 58810 & 59547 & 21555 & 32712 & 20787 & 12223 & -20354 \cr 49113 & 5683 & 30540 & 43481 & 47688 & 20331 & -8762 \cr 58433 & 20124 & 62414 & 22027 & 34969 & 63343 & -8396 \cr 6671 & 24953 & 40161 & 57696 & 31204 & 13769 & 16308}

求出k個超平面方程式的交點坐標
(%i13)
A:submatrix(shadows,k+1)$
B:col(shadows,k+1)$
linsolve_by_lu(A,B);
(%o15)　 \displaystyle [ \pmatrix{ -\frac{239491479314553105644042475017644464141348447204156669689205637453765303376528277604} {216396336661829004078184209560598894913754528761549337466792501379219596480279330621} \cr 　 \cr \frac{1210805713819882573289422222280783600688940179592831917819578082169049120990916334350266} {19113321079899398891561301316928566622410951815332061591718561061341473390034415245174541} \cr 　 \cr -\frac{37644552818254310466065473507177075951008884574753786958432937812591617153278450} {106546694565154605651493948577350514482400063398104055867450763849935793441791891} \cr 　 \cr \frac{63479880358930370859878647750293235168149198063790494688930192308562} {66968254011130256410216439253313699375179209442652365784366974851833} \cr 　 \cr -\frac{11513040138995712259570392386228043283995950153230} {22465424471730794622726083901131483083365892339583} \cr 　 \cr \frac{549677002877614509907708808}{851081629302730915840058149}},false]

雖然算出來是分數，但在Fp底下運算，化簡後得到交點坐標
(%i16)　rat(%);
(%o16)/R/　 \displaystyle [ \pmatrix{12345 \cr -5429 \cr 31816 \cr 4877 \cr 18871 \cr 5290},false]

其中x1就是秘密S=12345
(%i17)　%[1][1][1];
(%o17)/R/　12345

3.秘密分享方案介紹－Mignotte

這個方案是基於中國剩餘定理，詳細內容請見wiki。
http://zh.wikipedia.org/wiki/%E4 ... 9%E5%AE%9A%E7%90%86
http://en.wikipedia.org/wiki/Sec ... cret_sharing_scheme

1.假設有n個人要共享秘密S，只要有k個人在一起就能重組秘密。
2.任取n個嚴格遞增的正整數，其中任兩數互質(不一定要質數)。
　 m_1<m_2< \ldots <m_n 　，　 \forall 1 \le i<j \le n ， (m_i,m_j)=1
3.計算 m_{n-k+2} \times m_{n-k+3} \times \ldots \times m_n 和 m_1 \times m_2 \times \ldots \times m_k
　檢查秘密S是否落在這兩個數字之間，若不符合則回到步驟2再重新選取 m_i 數列
　 \displaystyle \prod_{i=n-k+2}^n m_i<S<\prod_{i=1}^n m_i
4.計算 s_i \equiv S \pmod{m_i} ， 1 \le i \le n
　每個人拿到所屬的子秘密 (s_i,m_i) ， 1 \le i \le n
5.現在有k個人聚在一起要重組秘密S
　 (s_{i1},m_{i1}),(s_{i2},m_{i2}),\ldots,(s_{ik},m_{ik})
6.同餘方程組
　 \displaystyle \Bigg\{\; \matrix{x \equiv s_{i1} \pmod{m_{i1}} \cr x \equiv s_{i2} \pmod{m_{i2}} \cr \ldots \cr x \equiv s_{ik} \pmod{m_{ik}}}
7.因為 m_{i1},m_{i2},\ldots,m_{ik} 兩兩互質，由中國剩餘定理可知，同餘方程組有唯一解，解出的x就是秘密S


例子
1.假設有 n=4 個人共享秘密 S=123 ，只要有 k=3 個人就能重組秘密
2.選取4個數字， m_1=7,m_2=8,m_3=9,m_4=11 ，其中任兩數互質
3.計算 m_3 \times m_4=9 \times 11=99 和 m_1 \times m_2 \times m_3=7 \times 8 \times 9=504
　且S介於在99和504之間
4.計算子秘密
　 s_1 \equiv 4 \equiv 123 \pmod{7}
　 s_2 \equiv 3 \equiv 123 \pmod{8}
　 s_3 \equiv 6 \equiv 123 \pmod{9}
　 s_4 \equiv 2 \equiv 123 \pmod{11}
　四個人分別拿到 (4,7),(3,8),(6,9),(2,11) 子秘密
5.假設有三個人要重組秘密
　 \displaystyle \Bigg\{\; \matrix{x \equiv 4 \pmod{7} \cr x \equiv 3 \pmod{8} \cr x \equiv 2 \pmod{11}}
6.解同餘方程組得到 x=123 ，當初設定的秘密 S=123


有n個人共享秘密,有k個人聚在一起就能重建秘密
(%i1)
n:4;
k:3;
(%o1)　4
(%o2)　3

任選n項的遞增數列
(%i3)　m:[7,8,9,11];
(%o3)　 [7,8,9,11]

設定秘密S
(%i4)　S:123;
(%o4)　123

計算m(n-k+2)*m(n-k+3)*...*m(n)
　　m(1)*m(2)*...*m(k)
(%i5)
product1:product(m[ i ],i,n-k+2,n);
product2:product(m[ i ],i,1,k);
(%o5)　99
(%o6)　504

檢查S是否落在這二個數字之間
(%i7)　is(product1<S and S<product2);
(%o7)　true

計算子秘密s
(%i8)　s:mod(S,m);
(%o8)　 [4,3,6,2]

有三個人就能重組秘密
(%i9)　chinese([s[1],s[2],s[4]],[m[1],m[2],m[4]]);
(%o9)　123

但二個人就無法解出秘密
(%i10)　chinese([s[2],s[4]],[m[2],m[4]]);
(%o10)　35

延續上一篇Mignotte方案，提供另一個例子


有n個人共享秘密,有k個人聚在一起就能重建秘密
(%i1)
n:8;
k:6;
(%o1)　8
(%o2)　6

找出符合m(n-k+2)*m(n-k+3)*...*m(n) < m(1)*m(2)*...*m(k)的遞增數列m
為了方便數列m都採用質數，其中任兩個數字一定互質
(%i3)
found:false$
while found=false do
  (m:create_list(next_prime(random(50)),i,1,n),
   m:unique(m),
   if length(m)=n then
     (m:sort(m),
      product1:product(m[ i ],i,n-k+2,n),
      product2:product(m[ i ],i,1,k),
      if product1<product2 then
        found:true
     )
  )$
m;
(%o5)　 [11,17,19,29,31,37,41,53]

m(n-k+2)*m(n-k+3)*...*m(n)的乘積為product1
　　　m(1)*m(2)*...*m(k)的乘積為product2
(%i6)
product1;
product2;
(%o6)　72280499
(%o7)　118183439

設定秘密S
(%i8)　S:12345;
(%o8)　12345

按照Mignotte方案，秘密S要落在這二個數字之間
但我故意找比較小的S最後也能得到答案，原因我還不清楚
(%i9)　is(product1<S and S<product2);
(%o9)　false

計算秘密S對m的餘數
(%i10)　s:mod(S,m);
(%o10)　 [3,3,14,20,7,24,4,49]

將這n個數對分派給n個人
(%i11)　create_list([s[ i ],m[ i ]],i,1,n);
(%o11)　 [ [3,11],[3,17],[14,19],[20,29],[7,31],[24,37],[4,41],[49,53] ]

其中k個人聚在一起要重組秘密S
(%i12)
random_permutation(%)$
shadows:rest(%,n-k);
(%o13)　 [ [3,17],[4,41],[20,29],[49,53],[24,37],[14,19] ]

利用中國剩餘定理求出秘密S
(%i14)
s:makelist(shadows[ i ][1],i,1,k);
m:makelist(shadows[ i ][2],i,1,k);
chinese(s,m);
(%o14)　 [3,4,20,49,24,14]
(%o15)　 [17,41,29,53,37,19]
(%o16)　12345

4.秘密分享方案介紹－Asmuth-Bloom

這個方案是基於中國剩餘定理，詳細內容請見wiki。
http://en.wikipedia.org/wiki/Sec ... cret_sharing_scheme

1.假設有n個人要共享秘密S，只要有k個人在一起就能重組秘密。
2.任取 n+1 個嚴格遞增的正整數，其中任兩數互質
　 m_0<m_1<m_2<\ldots<m_n 　，　 \forall 0 \le i < j \le n ， (m_i,m_j)=1
3.計算 m_0 \times m_{n-k+2} \times m_{n-k+3} \times \ldots \times m_n 和 m_1 \times m_2 \times \ldots m_k
　 \displaystyle m_0 \times \prod_{i=n-k+2}^n m_i<S<\prod_{i=1}^n m_i
4.取秘密S，檢查 S<m_0 。
5.任取整數 \alpha ，檢查 S+\alpha \times m_0<m_1 \times m_2 \times \ldots \times m_k \
6.計算 s_i \equiv S+\alpha \times m_0 \pmod{m_i} ， 1 \le i \le n
　每個人拿到所屬的子秘密 (s_i,m_i) ， 1\le i \le n
7.現在有k個人聚在一起要重組秘密S
　 (s_{i1},m_{i1}),(s_{i2},m_{i2}),\ldots,(s_{ik},m_{ik})
8.同餘方程組
　 \displaystyle \Bigg\{\; \matrix{x \equiv s_{i1} \pmod{m_{i1}} \cr x \equiv s_{i2} \pmod{m_{i2}} \cr \ldots \cr x \equiv s_{ik} \pmod{m_{ik}}}
9.因為 m_{i1},m_{i2},\ldots,m_{ik} 兩兩互質，由中國剩餘定理可知，同餘方程組有唯一解，解出的x再取 m_0 的餘數就是秘密S。


例子取自wiki
http://en.wikipedia.org/wiki/Sec ... der_theorem#Example
1.假設有 n=4 個人共享秘密 S=2 ，只要有 k=3 個人就能重組秘密。
2.選取5個數字， m_0=3,m_1=11,m_2=13,m_3=17,m_4=19 。
3.計算 m_0 \times m_3 \times m_4=3 \times 17 \times 19=969 和 m_1 \times m_2 \times m_3=11 \times 13 \times 17=2431
4.任取整數 \alpha=51 ，計算 S+\alpha \times m_0=2+51 \times 3=155 。
5.計算子秘密
　 s_1 \equiv 1 \equiv 155 \pmod{11}
　 s_2 \equiv 12 \equiv 155 \pmod{13}
　 s_3 \equiv 2 \equiv 155 \pmod{17}
　 s_4 \equiv 3 \equiv 155 \pmod{19}
　四個人分別拿到 (1,11),(12,13),(2,17),(3,19) 子秘密
6.假設有三個人要重組秘密
　 \displaystyle \Bigg\{\; \matrix{x \equiv 1 \pmod{11} \cr x \equiv 12 \pmod{13} \cr x \equiv 2 \pmod{17}}
7.解同餘方程組得到 x=155 ，當初設定的秘密 S \equiv 155 \equiv 2 \pmod{m_0}



有n個人共享秘密,有k個人聚在一起就能重建秘密
(%i1)
n:4;
k:3;
(%o1)　4
(%o2)　3

任選n項的遞增數列
(maxima的list是從1開始數，所以將m0獨立出來)
(%i3)
m0:3;
m:[11,13,17,19];
(%o3)　3
(%o4)　 [11,13,17,19]

計算m(0)*m(n-k+2)*m(n-k+3)*...*m(n)
　　m(1)*m(2)*...*m(k)
(%i5)
product1:m0*product(m[ i ],i,n-k+2,n);
product2:product(m[ i ],i,1,k);
(%o5)　969
(%o6)　2431

檢查m(0)*m(n-k+2)*m(n-k+3)*...*m(n)是否小於
　　m(1)*m(2)*...*m(k)
(%i7)　is(product1 < product2);
(%o7)　true

設定秘密S
(%i8)　S:2;
(%o8)　2

檢查S是否小於m0
(%i9)　is(S < m0);
(%o9)　true

任意整數α
(%i10)　alpha:51;
(%o10)　51

檢查S+α*m0是否小於m(1)*m(2)*...*m(k)
(%i11)　is(S+alpha*m0 < product2);
(%o11)　true

計算子秘密s
(%i12)　s:create_list(mod(S+alpha*m0,m[ i ]),i,1,n);
(%o12)　 [1,12,2,3]

有三個人就能重組秘密
(%i13)
chinese([s[1],s[2],s[3]],[m[1],m[2],m[3]])$
S:mod(%,m0);
(%o14)　2

[ 本帖最後由 bugmens 於 2013-8-17 08:54 PM 編輯 ]

延續上一篇Asmuth-Bloom，提供另一個例子


有n個人共享秘密,有k個人聚在一起就能重建秘密
(%i1)
n:8;
k:6;
(%o1)　8
(%o2)　6

設定秘密S
(%i3)　S:12345;
(%o3)　12345

找出符合S<m0和
m(0)*m(n-k+2)*m(n-k+3)*...*m(n) < m(1)*m(2)*...*m(k)的遞增數列m
為了方便，數列m都採用質數，其中任兩個數字一定互質
(maxima的list是從1開始數，所以將m0獨立出來)
(%i4)
found:false$
while found=false do
  (m0:next_prime(S+random(S)),
   m:create_list(next_prime(m0+random(S)),i,1,n),
   m:unique(m),
   if length(m)=n then
     (m:sort(m),
      product1:m0*product(m[ i ],i,n-k+2,n),
      product2:product(m[ i ],i,1,k),
      if product1<product2 then
        found:true
     )
  )$
m0;
m;
(%o6)　14843
(%o7)　 [20857,21163,22871,23399,24439,24469,25409,26209]

隨意取整數α並檢查S+α*m0是否小於m(1)*m(2)*...*m(k)
(%i8)
found:false$
while found=false do
  (alpha:random(S),
   if S+alpha*m0 < product2 then
     found:true
  )$
alpha;
(%o10)　2664

計算子秘密s並分派給n個人
(%i11)　create_list([mod(S+alpha*m0,m[ i ]),m[ i ]],i,1,n);
(%o11)　 [[9225,20857],[450,21163],[10138,22871],[9787,23399],[11795,24439],[12193,24469],[17693,25409],[4716,26209]]

其中k個人聚在一起要重組秘密S
(%i12)
random_permutation(%)$
shadows:rest(%,n-k);
(%o13)　 [[4716,26209],[11795,24439],[17693,25409],[9787,23399],[9225,20857],[450,21163]]

利用中國剩餘定理求出秘密S
(%i14)
s:makelist(shadows[ i ][1],i,1,k);
m:makelist(shadows[ i ][2],i,1,k);
S:chinese(s,m);
(%o14)　 [4716,11795,17693,9787,9225,450]
(%o15)　 [26209,24439,25409,23399,20857,21163]
(%o16)　39554097

秘密S還要對m0取餘數才是答案
(%i17)　mod(S,m0);
(%o17)　12345

[ 本帖最後由 bugmens 於 2013-8-20 12:46 PM 編輯 ]