5.秘密分享方案介紹－钟红山

這個方案是基於質因數分解，詳細內容請見
钟红山，素数集合秘密共享方案
https://www.google.com.tw/search ... ..2.0.0.4b58LRPZoq8

1.假設n個人要共享秘密S，只要k個人在一起就能重組秘密。
2.設定秘密S。
3.取Cnk−1個不同的質數pi，1iCnk−1。
4.將每個質數分配給k−1個人。
5.將分配的質數相乘，再乘上秘密S，為各使用者所屬的子秘密Vi，1in
6.現在有k個人聚在一起要重組秘密S
　Vi1Vi2Vik
7.計算最大公因數得到秘密S。



例子取自論文，為了文章一致性，本文所使用的符號和論文略有不同。

1.假設有n=5個人要共享秘密S=451，只要有k=3個人就能重組秘密。
2.取C25=10個不同的質數2,3,5,7,13,23,31,47,53,61。
3.將每個質數分配給2個人
　質數 2分配給V1,V2
　質數 3分配給V2,V3
　質數 5分配給V3,V4
　質數 7分配給V4,V5
　質數13分配給V1,V5
　質數23分配給V1,V3
　質數31分配給V2,V4
　質數47分配給V3,V5
　質數53分配給V1,V4
　質數61分配給V2,V5

子秘密Vi			秘密S	p1	p2	p3	p4	p5	p6	p7	p8	p9	p10
V1	14293994		451	2				13	23			53
V2	5117046		451	2	3					31			61
V3	7312956		451		3	5			23		47
V4	25934755		451			5	7			31		53
V5	117664547		451				7	13			47		61

4.將分配的質數相乘，再乘上秘密S，為各使用者所屬的子秘密
　V1=4512132353=14293994
　V2=451233161=5117046
　V3=451352347=7312965
　V4=451573153=25934755
　V5=4517134761=117664547
5.假設有V1V3V4聚在一起要重組秘密
　V1=14293994V3=7312965V4=25934755
6.計算最大公因數得到當初設定的秘密S
　GCD(V1V3V4)=451


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

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

任意取C(5,2)=10個質數
(%i4)　P:[2,3,5,7,13,23,31,47,53,61];
(%o4)　[2357132331475361]

設定質數要給哪一個使用者
P1給V1,V2
P2給V2,V3
P3給V3,V4
...
(%i5)　User:[[1,2],[2,3],[3,4],[4,5],[1,5],[1,3],[2,4],[3,5],[1,4],[2,5]];
(%o5)　[[12][23][34][45][15][13][24][35][14][25]]

將分配到的質數和秘密S乘起來當作子秘密Vi
(%i6)
V:create_list(S,i,1,n)$
for i:1 thru binomial(n,k-1) do
  (index:User[ i ][1],
   V[index]:V[index]*P[ i ],
   index:User[ i ][2],
   V[index]:V[index]*P[ i ]
  )$
V;
(%o8)　[142939945117046731296525934755117664547]

任意三個人就可以解出秘密S
(%i9)　lreduce(lambda([x,y], gcd(x,y)), [V[1],V[3],V[4]]);
(%o9)　451

但只有兩個人就無法解出秘密S
(%i10)　lreduce(lambda([x,y], gcd(x,y)), [V[1],V[3]]);
(%o10)　10373

[ 本帖最後由 bugmens 於 2013-8-31 10:49 AM 編輯 ]

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

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

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

任意取C(n,k-1)個質數
(%i4)
found:false$
m:binomial(n,k-1)$
while found=false do
  (P:create_list(next_prime(random(S)),i,1,m),
   P:unique(P),
   if length(P)=m then
     (found:true
     )
  )$
P;
(%o7)　[9715725134737955713811889321735273557398941115381574360896217654766196701
68838443850185278779889393711000710079103571039110459112391209712323]

設定質數要給哪一位使用者
P1給V1,V2,V3,V4
P2給V1,V2,V3,V5
P3給V1,V2,V3,V6
...
(%i8)
create_list(i,i,1,n)$
setify(%)$
powerset(%,k-1)$
User:full_listify(%);
(%o11)　[[1234][1235][1236][1237][1245][1246][1247]
[1256][1257][1267][1345][1346][1347][1356]
[1357][1367][1456][1457][1467][1567][2345]
[2346][2347][2356][2357][2367][2456][2457]
[2467][2567][3456][3457][3467][3567][4567]]

將分配到的質數和秘密S乘起來當作子秘密Vi
(%i12)
V:create_list(S,i,1,n)$
for i:1 thru m do
  (for user in User[ i ] do
     (V[user]:V[user]*P[ i ]
     )
  )$
V;
(%o14)
[2027405439656203402483392037741077832451907091735220768078908930690305
329395512180772665716441437042961317833047447165674231176372701471582355
873365187527948903078917971136893483135753791078025669159186590065120719495
38557189090206618525408472635427757365514394529139189207988367527928662521235
1085040646795903444837598300544056739255857225025230153016414858410402872064055
4518571371143044485194989367493800863732546105787200385445314138550958905680685
34041447391883330084505313814699077342455987346908316001305119644995002433655445]

其中k個人聚在一起要重組秘密S
(%i15)
random_permutation(%)$
rest(%,n-k);
(%o16)
[34041447391883330084505313814699077342455987346908316001305119644995002433655445
873365187527948903078917971136893483135753791078025669159186590065120719495
1085040646795903444837598300544056739255857225025230153016414858410402872064055
329395512180772665716441437042961317833047447165674231176372701471582355
2027405439656203402483392037741077832451907091735220768078908930690305]

計算最大公因數得到秘密S
(%i17)　lreduce(lambda([x,y], gcd(x,y)), %);
(%o17)　12345

6.秘密分享方案介紹－Kai-Yuen Cheong

這個方案是基於質因數分解，詳細內容請見
Kai-Yuen Cheong，A secret sharing scheme of prime numbers based on hardness of factorization
http://eprint.iacr.org/2012/222.pdf


要特別注意的是這個方案和一般的祕密分享不太一樣
有k個人要共享2k−1個質數的秘密，每一個質數都是n-bit
當全部的人聚在一起才能重組秘密，少一個人就無法重組


1.假設k個人要共享質數秘密pj( 1j2k−1 )，當全部的人聚在一起才能重組秘密。
2.定義B函數：將整數j轉換成二進位後從高位元開始數第i位元的值
　對每個使用者i，計算si=2k−1j=1B(ji)pj
　將子秘密si( 1ik )分配給k個人。
3.全部的人聚在一起要重組秘密時
　對每個j值將B(ji)=1的si收集起來形成集合Sj
　注意：小寫si代表子秘密，大寫Sj代表該集合可以求出某個質數p
4.按照集合Sj的元素多寡遞減排序得到新的集合Sj
5.對每個集合Sj的所有元素求最大公因數就可以得到某個質數pj
6.將集合Sj中有出現pj都除掉
7.回到步驟5再處理下一個集合Sj+1，直到所有質數都被回復為止。


接下來我以論文所舉的例子為例
1.假設k=3個人要共享2k−1=7個質數( p1p2p3p4p5p6p7 )
2.計算每個人會拿到的子秘密si
　s1=p4p5p6p7，s2=p2p3p6p7，s3=p1p3p5p7  

整數 j	二進位	i=1	i=2	i=3	集合Sj
1	001	B(11)=0	B(12)=0	B(13)=1	S1=s3
2	010	B(21)=0	B(22)=1	B(23)=0	S2=s2
3	011	B(31)=0	B(32)=1	B(33)=1	S3=s2s3
4	100	B(41)=1	B(42)=0	B(43)=0	S4=s1
5	101	B(51)=1	B(52)=0	B(53)=1	S5=s1s3
6	110	B(61)=1	B(62)=1	B(63)=0	S6=s1s2
7	111	B(71)=1	B(72)=1	B(73)=1	S7=s1s2s3
		使用者1 拿到質數 s1=p4p5p6p7	使用者2 拿到質數 s2=p2p3p6p7	使用者3 拿到質數 s3=p1p3p5p7

3..當全部的人聚在一起要重組秘密時，對每個j值將B(ji)=1的si收集起來形成集合Sj
　S1=s3，S2=s2，S3=s2s3，S4=s1，S5=s1s3，S6=s1s2，S7=s1s2s3
4.按照集合Sj的元素多寡遞減排序得到新的集合Sj
　S1=s1s2s3，S2=s1s2，S3=s1s3，S4=s2s3，S5=s1，S6=s2，S7=s3

5.對每個集合Sj的所有元素求最大公因數就可以得到某個質數pj
6.將集合Sj中有出現pj都除掉
7.回到步驟5再處理下一個集合Sj+1，直到所有質數都被回復為止。
　GCD(s1s2s3)=GCD(p4p5p6p7　　p2p3p6p7　　p1p3p5p7)=p7
　同除p7，得s1=p4p5p6　，　s2=p2p3p6　，　s3=p1p3p5

　GCD(s1s2)=GCD(p4p5p6　　p2p3p6)=p6
　同除p6，得s1=p4p5　，　s2=p2p3　，　s3=p1p3p5

　GCD(s1s3)=GCD(p4p5　　p1p3p5)=p5
　同除p5，得s1=p4　，　s2=p2p3　，　s3=p1p3

　GCD(s2s3)=GCD(p2p3　　p1p3)=p3
　同除p3，得s1=p4　，　s2=p2　，　s3=p1

　GCD(s1)=GCD(p4)=p4
　同除p4，得 s_1=1 　，　 s_2=p_2 　，　 s_3=p_1

　 GCD(s_2)=GCD(p_2)=p_2
　同除 p_2 ，得 s_1=1 　，　 s_2=1 　，　 s_3=p_1

　 GCD(s_3)=GCD(p_1)=p_1
　同除 p_1 ，得 s_1=1 　，　 s_2=1 　，　 s_3=1
8.得到所有質數 p_1,p_2,p_3,p_4,p_5,p_6,p_7



有k個人共享2^k-1個質數的秘密,要全部的人聚在一起才能重建秘密
(%i1)　k:3;
(%o1)　3

B函數--將整數j轉換成二進位後從高位元開始數第i位元的值為?(0或1)
例如6=(110),第1個位元為1,第2個位元為1,第三個位元為0
(%i2)　B(j,i):=mod(floor(j/2^(k-i)),2);
(%o2)　 \displaystyle B(j,i) :=mod(floor(\frac{j}{2^{k-i}}),2)

將B函數回傳值為1所對應的質數pj收集起來形成子秘密si
(%i3)
s(i):=product(if B(j,i)=1 then p[j] else 1,j,1,2^k-1);
s:create_list(s(i),i,1,k);
(%o3)　 \displaystyle s(i) :=\prod_{j=1}^{2^k-1} if B(j,1)=1 then p_j else 1
(%o4)　 [p_4p_5p_6p_7　,　p_2p_3p_6p_7　,　p_1p_3p_5p_7]

當全部的人聚在一起要重組秘密時，
對每個j值將B(j,i)=1的si收集起來形成集合S_j
(%i5)
S:[]$
for j:1 thru 2^k-1 do
  (temp:create_list(if B(j,i)=1 then 's[ i ] else false,i,1,2^k-1),
   temp:delete(false,temp),
   S:append([temp],S)
  )$
S;
(%o7)　 [ [s_1,s_2,s_3],[s_1,s_2],[s_1,s_3],[s_1],[s_2,s_3],[s_2],[s_3] ]

按照Sj各集合元素個數遞減排序
(%i8)　S:sort(S,lambda([a, b],ordergreatp(length(a),length(b))));
(%o8)　 [ [s_1,s_2,s_3],[s_1,s_3],[s_2,s_3],[s_1],[s_2],[s_3] ]

求出每一組Sj的最大公因數GCD得到質數p
將子秘密s中有出現p的都約掉(程式碼則用subst用1取代掉)
再處理下一組Sj
(%i9)
for j:1 thru 2^k-1 do
  (Sj:map(lambda([x],s[part(x,1)]),S[j]),
   GCD:lreduce(lambda([x,y], gcd(x,y)),Sj),
   print("從",S[j],"=",Sj,"求最大公因數得到質數",GCD),
   s:subst(1,GCD,s)
)$
從 [s_1,s_2,s_3]=[p_4p_5p_6p_7　,　p_2p_3p_6p_7　,　p_1p_3p_5p_7] 求最大公因數得到質數 p_7
從 [s_1,s_2]=[p_4p_5p_6　,　p_2p_3p_6] 求最大公因數得到質數 p_6
從 [s_1,s_3]=[p_4p_5　,　p_1p_3p_5] 求最大公因數得到質數 p_5
從 [s_2,s_3]=[p_2p_3　,　p1p_3] 求最大公因數得到質數 p_3
從 [s_1]=[p_4] 求最大公因數得到質數 p_4
從 [s_2]=[p_2] 求最大公因數得到質數 p_2
從 [s_3]=[p_1] 求最大公因數得到質數 p_1

[ 本帖最後由 bugmens 於 2013-9-22 02:01 PM 編輯 ]

7.秘密分享方案介紹－Karnin-Greene-Hellman

這個方案是基於矩陣乘法，詳細內容請見
E. D. Karnin, J. W. Greene, and M. E. Hellman. On secret sharing systems. IEEE Transactions on Information Theory, 29:35-41,1983.

楊吳泉，現代密碼學入門與程式設計　有這個方案的介紹及簡單的範例。

設定在 F_2 底下運算
1.任意選擇 n+1 個 kt \times t 之矩陣 A_0,A_1,\ldots,A_n ，每個矩陣之任一元素為0或1，並公開 A_i 矩陣。
2.選擇一個 1 \times kt 之矩陣 U=(u_1,u_2,\ldots,u_{mt}) ，每一個 u_i 亦為0或1。
3.設定秘密 S=U \times A_0
4.計算 s_i=U \times A_i ， 1 \le i \le n
　每個人拿到所屬的子秘密 s_i ， 1 \le i \le n
5.現在有k個人聚在一起要重組秘密S
　 s_{i1},s_{i2},\ldots,s_{ik} 將子秘密串接在一起形成 1 \times kt 矩陣 s=[s_{i1},s_{i2},\ldots,s_{ik}]
6.根據子秘密找出對應的公開矩陣
　 A_{i1},A_{i2},\ldots,A_{ik} 並將矩陣串接在一起形成 kt \times kt 矩陣 A=[A_{i1},A_{i2},\ldots,A_{ik}]
7.計算 U=s \times A^{-1} 得到矩陣 U
　計算 S=U \times A_0 得到秘密S。



以下的範例取自原論文，設定在 F2 底下運算
1.有4個人共享秘密，要2個人才能重建秘密
2.隨機選取5個 A_i 矩陣，並將 A_i 公開
　 \displaystyle A_0=\left[ \matrix{1 & 0 \cr 0 & 1 \cr 0 & 0 \cr 0 & 0}\right] 、 \displaystyle A_1=\left[ \matrix{0 & 0 \cr 0 & 0 \cr 1 & 0 \cr 0 & 1}\right] 、 \displaystyle A_2=\left[ \matrix{1 & 0 \cr 1 & 1 \cr 1 & 0 \cr 0 & 1}\right] 、 \displaystyle A_3=\left[ \matrix{0 & 1 \cr 1 & 0 \cr 1 & 0 \cr 0 & 1}\right] 、 \displaystyle A_4=\left[ \matrix{1 & 0 \cr 0 & 1 \cr 1 & 1 \cr 0 & 1}\right] 。
3.選擇 U=[\matrix{1 & 0 & 1 & 1}] 矩陣
4.設定秘密 S=U \times A_0
　 S=[\matrix{1 & 0 & 1 & 1}]\times \Bigg[\; \matrix{1 & 0 \cr 0 & 1 \cr 0 & 0 \cr 0 & 0}\Bigg]\;=[\matrix{1 & 0}]
5.計算 s_i=U \times A_i ， 1 \le i \le 4
　每個人拿到所屬的子秘密 s_i ， 1 \le i \le 4
　 s_1=[\matrix{1 & 0 & 1 & 1}]\times \left[ \matrix{0 & 0 \cr 0 & 0 \cr 1 & 0 \cr 0 & 1}\right] =[\matrix{1 & 1}] 　　　　　　　，　　 s_2=[\matrix{1 & 0 & 1 & 1}]\times \left[ \matrix{1 & 0 \cr 1 & 1 \cr 1 & 0 \cr 0 & 1}\right]=[\matrix{2 & 1}]=[\matrix{0 & 1}]

　 s_3=[\matrix{1 & 0 & 1 & 1}]\times \left[ \matrix{0 & 1 \cr 1 & 0 \cr 1 & 0 \cr 0 & 1}\right]=[\matrix{1 & 2}]=[\matrix{1 & 0}] 　　，　　 s_4=[\matrix{1 & 0 & 1 & 1}]\times \left[ \matrix{1 & 0 \cr 0 & 1 \cr 1 & 1 \cr 0 & 1}\right]=[\matrix{2 & 2}]=[\matrix{0 & 0}]
6.現在有2個人聚在一起要重組秘密S
　 s_1=[\matrix{1 & 1}] ， s_3=[\matrix{1 & 0}] 串接在一起形成矩陣 s=[\matrix{1 & 1 & 1 & 0}]
7.針對子秘密選取對應的 A_i 矩陣
　 \displaystyle A_1=\left[ \matrix{0 & 0 \cr 0 & 0 \cr 1 & 0 \cr 0 & 1}\right] 、 \displaystyle A_3=\left[ \matrix{0 & 1 \cr 1 & 0 \cr 1 & 0 \cr 0 & 1}\right] 串接在一起形成矩陣 \displaystyle A=\left[ \matrix{0 & 0 & 0 & 1\cr 0 & 0 & 1 & 0 \cr 1 & 0 & 1 & 0 \cr 0 & 1 & 0 & 1}\right]
8.計算 U=s \times A^{-1} 得到矩陣 U
　 \displaystyle U=[\matrix{1 & 1 & 1 & 0}]\times {\left[ \matrix{0 & 0 & 0 & 1\cr 0 & 0 & 1 & 0 \cr 1 & 0 & 1 & 0 \cr 0 & 1 & 0 & 1}\right]}^{-1}=[\matrix{1 & 1 & 1 & 0}]\times \left[\; \matrix{0 & 1 & 1 & 0\cr 1 & 0 & 0 & 1 \cr 0 & 1 & 0 & 0 \cr 1 & 0 & 0 & 0}\right]=[\matrix{1 & 0 & 1 & 1}]
　計算 S=U \times A_0 得到秘密S。
　 \displaystyle S=[\matrix{1 & 0 & 1 & 1}] \times \left[ \matrix{1 & 0 \cr 0 & 1 \cr 0 & 0 \cr 0 & 0}\right]=[\matrix{1 & 0}]



設定在F2底下運算
(%i1)　modulus:2;
(%o1)　2

隨機選取5個Ai矩陣，並將Ai公開
(%i2)　A0:matrix([1,0],[0,1],[0,0],[0,0]);
(%o2)　 \displaystyle \left[ \matrix{1 & 0 \cr 0 & 1 \cr 0 & 0 \cr 0 & 0}\right]

(%i3)　A1:matrix([0,0],[0,0],[1,0],[0,1]);
(%o3)　 \displaystyle \left[ \matrix{0 & 0 \cr 0 & 0 \cr 1 & 0 \cr 0 & 1}\right]

(%i4)　A2:matrix([1,0],[1,1],[1,0],[0,1]);
(%o4)　 \displaystyle \left[ \matrix{1 & 0 \cr 1 & 1 \cr 1 & 0 \cr 0 & 1}\right]

(%i5)　A3:matrix([0,1],[1,0],[1,0],[0,1]);
(%o5)　 \displaystyle \left[ \matrix{0 & 1 \cr 1 & 0 \cr 1 & 0 \cr 0 & 1}\right]

(%i6)　A4:matrix([1,0],[0,1],[1,1],[0,1]);
(%o6)　 \displaystyle \left[ \matrix{1 & 0 \cr 0 & 1 \cr 1 & 1 \cr 0 & 1}\right]

選擇一個U矩陣
(%i7)　U:matrix([1,0,1,1]);
(%o7)　 [\matrix{1 & 0 & 1 & 1}]

設定秘密S=U.A0
maxima的矩陣乘法用.
(%i8)　S:rat(U.A0);
(%o8)/R/　 [\matrix{1 & 0}]

計算子秘密si
(%i9)
s1:rat(U.A1);
s2:rat(U.A2);
s3:rat(U.A3);
s4:rat(U.A4);
(%o9)/R/　 [\matrix{1 & 1}]
(%o10)/R/　 [\matrix{0 & 1}]
(%o11)/R/　 [\matrix{1 & 0}]
(%o12)/R/　 [\matrix{0 & 0}]

有2位使用者聚在一起要重組秘密S
將子秘密串接在一起形成矩陣s
(%i13)　s:addcol(s1,s3);
(%o13)/R/　 [\matrix{1 & 1 & 1 & 0}]

針對子秘密選取對應的Ai矩陣
串接在一起形成矩陣A
(%i14)　A:addcol(A1,A3);
(%o14)　 \displaystyle \left[ \matrix{0 & 0 & 0 & 1 \cr 0 & 0 & 1 & 0 \cr 1 & 0 & 1 & 0 \cr 0 & 1 & 0 & 1}\right]

計算U=S.A^(-1)得到矩陣U
(%i15)　U:s.invert(A);
(%o15)/R/　 [\matrix{1 & 0 & 1 & 1}]

計算S=U.A0得到秘密S
(%i16)　S:U.A0;
(%o16)/R/　 [\matrix{1 & 0}]

[ 本帖最後由 bugmens 於 2014-6-9 10:31 PM 編輯 ]

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

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

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

約定在Fp底下運算
(%i4)
p:7;
modulus:p;
(%o4)　7
(%o5)　7

將秘密S轉換成p進位
12345=5*7^4+6*7^2+6*7+4
(%i6)　S_Base_p:create_list(mod(floor(S/p^i),p),i,0,floor(log(S)/log(p)));
(%o6)　 [4,6,6,0,5]

S轉換後的長度設為t
(%i7)　t:length(S_Base_p);
(%o7)　5

產生kt*t維的Ai矩陣
(%i8)　A[ i ]:=genmatrix(lambda([a,b],random(p)),k*t,t);
(%o8)　 A_i:=genmatrix(lambda([a,b],random(p)),kt,t)

先產生A0矩陣
(%i9)　A[0];
(%o9)　 \displaystyle \left[ \matrix{1&0&1&1&2\cr 6&2&5&0&4\cr 6&3&4&0&6\cr 0&6&3&1&5\cr 1&3&2&2&6\cr 0&2&6&2&6\cr 4&0&1&2&1\cr 6&0&6&2&3\cr 0&2&2&4&6\cr 1&3&0&4&2\cr 1&4&0&5&2\cr 3&1&4&0&0\cr 4&4&1&5&0\cr 3&2&6&5&6\cr 3&2&1&5&5} \right]

根據S和A0來產生對應的U矩陣
步驟1:假設U矩陣有kt個未知數
(%i10)　U:create_list(x[ i ],i,1,k*t);
(%o10)　 [x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10},x_{11},x_{12},x_{13},x_{14},x_{15}]

步驟2:矩陣方程式S=U.A0
(maxima用.代表矩陣乘法)
(%i11)　matrix(U).A[0]-matrix(S_Base_p);
(%o11)　 \displaystyle \matrix{[3x_{15}+3x_{14}+4x_{13}+3x_{12}+x_{11}+x_{10}+6x_8+4x_7+x_5+6x_3+6x_2+x_1-4 \cr 2x_{15}+2x_{14}+4x_{13}+x_{12}+4x_{11}+3x_{10}+2x_9+2x_6+3x_5+6x_4+3x_3+2x_2-6 \cr x_{15}+6x_{14}+x_{13}+4x_{12}+2x_9+6x_8+x_7+6x_6+2x_5+3x_4+4x_3+5x_2+x_1-6 \cr 5x_{15}+5x_{14}+5x_{13}+5x_{11}+4x_{10}+4x_9+2x_8+2x_7+2x_6+2x_5+x_4+x_1 \cr 5x_{15}+6x_{14}+2x_{11}+2x_{10}+6x_9+3x_8+x_7+6x_6+6x_5+5x_4+6x_3+4x_2+2x_1-5]}

步驟3:得到無限多組的解答
%r1,%r2,...為參數
(%i12)　solution:solve(%[1],U);
(%o12)　 \displaystyle \matrix{[[x_1=3\%r9+2\%r8-\%r7+2\%r6+3\%r5+\%r4-3\%r3-\%r2-\%r10+3\%r1,\cr x_2=-3\%r9-2\%r7-3\%r6-2\%r5+3\%r4-3\%r3-\%r2+2\%r10+3\%r1+1 \cr x_3=2\%r9+\%r8-3\%r7-\%r6+\%r5-3\%r4-\%r3-3\%r2-\%r10-\%r1,\cr x_4=-3\%r9+3\%r8-2\%r7+\%r6+2\%r5+\%r3+\%r2+2\%r10-3\cr x_5=-\%r9+3\%r7+2\%r5+3\%r4+2\%r3+\%r2+2\%r10+3\%r1-2,\cr x_6=\%r10,x_7=\%r9,x_8=\%r8,x_9=\%r7,x_{10}=\%r6,x_{11}=\%r5,x_{12}=\%r4,x_{13}=\%r3,x_{14}=\%r2,x_{15}=\%r1]]}

步驟4:將參數都設為1
(設為其他數字都可以)
(%i13)　variable:create_list(r=1,r,%rnum_list);
(%o13)　 \displaystyle [\%r1=1,\%r2=1,\%r3=1,\%r4=1,\%r5=1,\%r6=1,\%r7=1,\%r8=1,\%r9=1,\%r10=1]

步驟5:將參數代入得到一組解
(%i14)　solution:rat(ev(solution,variable));
(%o14)/R/　 [[x_1=1,x_2=2,x_3=-2,x_4=2,x_5=-1,x_6=1,x_7=1,x_8=1,x_9=1,x_{10}=1,x_{11}=1,x_{12}=1,x_{13}=1,x_{14}=1,x_{15}=1]]

步驟6:將解答轉換成U矩陣
(%i15)　U:map(lambda([x],rhs(x)),%[1]);
(%o15)/R/　 [1,2,-2,2,-1,1,1,1,1,1,1,1,1,1,1]

產生A1~An矩陣，將A0,A1~An公開
(%i16)　create_list(A[ i ],i,1,n);
(%o16)　 \displaystyle \left[ \matrix{0&3&5&5&6\cr 0&0&4&0&1\cr 1&0&3&1&5\cr 2&4&1&0&1\cr 0&3&5&1&0\cr 4&3&2&3&3\cr 3&0&3&1&0\cr 5&4&2&5&1\cr 3&1&1&2&3\cr 3&2&4&4&2\cr 5&3&0&2&6\cr 6&2&0&3&2\cr 1&1&0&1&5\cr 2&2&5&2&3\cr 1&4&0&2&3} \right], \left[ \matrix{4&6&3&1&3\cr 0&0&4&3&3\cr 1&5&2&0&4\cr 5&5&0&6&3\cr 0&0&1&5&5\cr 3&6&6&5&2\cr 5&3&0&4&2\cr 2&6&2&4&0\cr 6&6&3&6&5\cr 2&3&5&5&3\cr 4&4&2&5&6\cr 1&6&1&4&1\cr 2&0&6&2&1\cr 2&2&5&0&1\cr 6&1&0&6&6} \right], \left[ \matrix{2&4&0&5&1\cr 4&5&2&1&3\cr 5&4&4&6&0\cr 1&3&5&6&6\cr 4&3&3&0&5\cr 6&3&4&0&0\cr 3&3&2&0&0\cr 5&3&3&3&3\cr 6&3&0&6&1\cr 5&4&4&6&5\cr 2&2&1&3&4\cr 6&1&2&1&0\cr 4&4&0&4&0\cr 3&6&2&4&2\cr 4&3&0&1&1} \right], \left[ \matrix{6&0&3&6&1\cr 3&5&4&3&4\cr 2&5&2&0&5\cr 5&2&3&1&4\cr 0&2&5&4&5\cr 0&6&5&4&3\cr 2&6&2&5&2\cr 2&1&0&1&6\cr 6&5&4&1&6\cr 1&2&0&4&4\cr 0&6&1&1&5\cr 1&0&4&2&3\cr 3&5&0&5&1\cr 6&5&1&4&3\cr 3&6&6&1&2}\right]

任選k個Ai矩陣組成一個方陣，檢查是否有反矩陣
若沒有反矩陣就要回到上一步再重新產生Ai矩陣
因為運算結果會佔很大版面,所以用$隱藏起來
(%i17)
powerset(setify(%),k)$
create_list(apply('addcol,listify(m)),m,listify(%))$
create_list(rat(invert(m)),m,%)$

將U矩陣和Ai矩陣相乘得到子秘密si
si=U.Ai
(%i20)　s:create_list(U.A[ i ],i,1,n);
(%o20)/R/　 [[\matrix{0&2&0&-1&0}],[\matrix{3&1&1&-1&1}],[\matrix{0&-1&0&0&2}],[\matrix{0&2&3&3&2}]]

其中k個人聚在一起要重組秘密S
將子秘密組成matrixs矩陣
(%i21)　matrixs:addcol(s[1],s[3],s[4]);
(%o21)/R/　 \displaystyle [\matrix{0&2&0&-1&0&0&-1&0&0&2&0&2&3&3&2}]

將對應的Ai矩陣組成matrixA方陣
(%i22)　matrixA:addcol(A[1],A[3],A[4]);
(%o22)　 \displaystyle \left[ \matrix{ 0&3&5&5&6&2&4&0&5&1&6&0&3&6&1\cr 0&0&4&0&1&4&5&2&1&3&3&5&4&3&4\cr 1&0&3&1&5&5&4&4&6&0&2&5&2&0&5\cr 2&4&1&0&1&1&3&5&6&6&5&2&3&1&4\cr 0&3&5&1&0&4&3&3&0&5&0&2&5&4&5\cr 4&3&2&3&3&6&3&4&0&0&0&6&5&4&3\cr 3&0&3&1&0&3&3&2&0&0&2&6&2&5&2\cr 5&4&2&5&1&5&3&3&3&3&2&1&0&1&6\cr 3&1&1&2&3&6&3&0&6&1&6&5&4&1&6\cr 3&2&4&4&2&5&4&4&6&5&1&2&0&4&4\cr 5&3&0&2&6&2&2&1&3&4&0&6&1&1&5\cr 6&2&0&3&2&6&1&2&1&0&1&0&4&2&3\cr 1&1&0&1&5&4&4&0&4&0&3&5&0&5&1\cr 2&2&5&2&3&3&6&2&4&2&6&5&1&4&3\cr 1&4&0&2&3&4&3&0&1&1&3&6&6&1&2} \right]

求matrixA的反矩陣
(%i23)　inv_A:rat(invert(matrixA));
(%o23)/R/　 \displaystyle \left[ \matrix{ -2&-1&1&-3&-3&-2&-3&2&1&0&0&2&2&-1&-2\cr 1&0&3&0&-1&-2&-3&3&0&2&-3&1&-2&-2&1\cr 0&-3&-1&1&-3&2&1&-1&-3&2&-1&3&0&-3&3\cr -1&-3&-2&1&0&2&1&-1&1&0&-2&3&-3&-1&2\cr 2&2&1&-2&3&0&3&3&1&2&3&0&-2&1&-3\cr 3&3&3&2&3&3&-3&-1&-2&2&3&0&1&-1&2\cr -3&0&2&1&0&-2&0&3&3&2&-1&1&1&-1&2\cr 2&2&2&-1&1&2&-2&-3&1&0&0&-2&0&0&1\cr -3&-3&2&2&-3&-1&-1&-1&-2&-3&3&0&-3&-3&1\cr -1&2&2&1&-1&1&-2&-1&2&-3&-3&-3&2&-2&-1\cr 3&-2&-3&0&-1&-2&1&3&2&1&-2&-2&-1&2&3\cr -1&-2&2&-1&-3&-2&3&-1&2&3&-3&-1&-2&-3&-3\cr 2&0&0&1&3&2&3&2&0&-1&2&3&-1&2&-1\cr 3&-1&0&-3&0&1&-2&3&-3&2&0&3&-3&-3&1\cr -1&1&-1&-2&0&-1&-2&0&3&-2&-2&0&-3&1&2} \right]

得到U矩陣
U=[s1,s3,s4].[A1,A3,A4] ^{-1}
(%i24)　U:matrixs.inv_A;
(%o24)/R/　 [\matrix{1&2&-2&2&-1&1&1&1&1&1&1&1&1&1&1}]

得到秘密S的p進位表示
(%i25)　S_Base_p:mod(U.A[0],p);
(%o25)　 [\matrix{4&6&6&0&5}]

得到秘密S
12345=(((5*7+0)*7+6)*7+6)*7+4
(%i26)　S:lreduce(lambda([a,b],a*p+b),reverse(S_Base_p[1]));
(%o26)　12345

[ 本帖最後由 bugmens 於 2014-6-9 10:35 PM 編輯 ]

這個方案是基於向量空間的外積，詳細內容請見
Chi-Sung Laih, Jau-Yien Lee, Lein Harn: A new threshold scheme and its application in designing the conference key distribution cryptosystem. Inf. Process. Lett. 32(3): 95-99 (1989)

Chi Sung LAIH(賴溪松)，Jau Yien LEE(李肇嚴)，Lein HARN(韓亮)
賴溪松教授已於2010年逝世，以下為紀念影片。
https://www.youtube.com/watch?v=lfQltpzoMC8


定義： s-1 個線性獨立的s維度列向量 Z_1,Z_2,\ldots,Z_{s-1} 的外積為
\displaystyle Z_1 \times Z_2 \times \ldots \times Z_{s-1}=\pmatrix{ \left|\ \matrix{z_2^1,& z_3^1, & \ldots & z_s^1 \cr z_2^2,& z_3^2, & \ldots & z_s^2 \cr \vdots & \vdots & & \vdots \cr z_2^{s-1}, & z_3^{s-1}, & \ldots & z_s^{s-1}} \right| , \left|\ \matrix{z_3^1,& z_4^1, & \ldots & z_s^1 & z_1^1 \cr z_3^2,& z_4^2, & \ldots & z_s^2 & z_1^2 \cr \vdots & \vdots & & \vdots & \vdots \cr z_3^{s-1}, & z_4^{s-1}, & \ldots & z_s^{s-1} & z_1^{s-1}} \right| , \ldots, \left|\ \matrix{z_1^1,& z_2^1, & \ldots & z_{s-1}^1 \cr z_1^2,& z_2^2, & \ldots & z_{s-1}^2 \cr \vdots & \vdots & & \vdots \cr z_1^{s-1}, & z_2^{s-1}, & \ldots & z_{s-1}^{s-1}} \right| }
Z_i=(z_1^i,z_2^i,\ldots,z_s^i)


例子：3個線性獨立的4維列向量 Z_1=(0,3,1,9)、Z_2=(5,6,4,0)、Z_3=(3,5,6,0) 的外積？
將4個列向量寫成行列式 \displaystyle \left|\ \matrix{0 & 3 & 1 & 9 \cr 5 & 6 & 4 & 0 \cr 3 & 5 & 6 & 0} \right|\

刪除第1行，從第2,3,4行開始寫，得到 \displaystyle \left|\ \matrix{3 & 1 & 9 \cr 6 & 4 & 0 \cr 5 & 6 & 0} \right|\

刪除第2行，從第3,4,1行開始寫，得到 \displaystyle \left|\ \matrix{1 & 9 & 0 \cr 4 & 0 & 5 \cr 6 & 0 & 3} \right|\

刪除第3行，從第4,1,2行開始寫，得到 \displaystyle \left|\ \matrix{9 & 0 & 3 \cr 0 & 5 & 6 \cr 0 & 3 & 5} \right|\

刪除第4行，從第1,2,3行開始寫，得到 \displaystyle \left|\ \matrix{0 & 3 & 1 \cr 5 & 6 & 4 \cr 3 & 5 & 6} \right|\

\displaystyle Z_1 \times Z_2 \times Z_3=\pmatrix{ \left|\ \matrix{3 & 1 & 9 \cr 6 & 4 & 0 \cr 5 & 6 & 0} \right|\ , \left|\ \matrix{1 & 9 & 0 \cr 4 & 0 & 5 \cr 6 & 0 & 3} \right|\ , \left|\ \matrix{9 & 0 & 3 \cr 0 & 5 & 6 \cr 0 & 3 & 5} \right|\ , \left|\ \matrix{0 & 3 & 1 \cr 5 & 6 & 4 \cr 3 & 5 & 6} \right|\ }=(144,162,63,-47)


假設有n個人要共享秘密S，只要有t個人在一起就能重組秘密。
1.分派者(Dealer)隨機選取t個線性獨立的 t+1 維列向量 V_1,V_2,\ldots,V_t 。
2.計算這t個列向量的外積，得到U向量
　 U=(u_1,u_2,\ldots,u_{t+1})=V_1 \times V_2 \times \ldots \times V_t
　其中秘密為 \displaystyle S=\prod_{i=2}^{t+1}\big| u_i \big| 。
　將 u_1 公開。
3.隨機選取一個 n \times t 矩陣A，乘上 V_i 矩陣，得到子秘密 s_i
　 \displaystyle \pmatrix{s_1 \cr s_2 \cr \vdots \cr s_n}=\pmatrix{ a_{11} & a_{12} & \ldots & a_{1t} \cr a_{21} & a_{22} & \ldots & a_{2t} \cr \vdots & \vdots &　& \vdots \cr a_{n1} & a_{n2} & \ldots & a_{nt}} \pmatrix{V_1 \cr V_2 \cr \vdots \cr V_t}
4.現在有t個人聚在一起要重組秘密S
　計算外積 s_1 \times s_2 \times \ldots \times s_t=(k_1,k_2,\ldots,k_{k+1})
5.得到秘密 \displaystyle S=\prod_{i=2}^{t+1}\big| \frac{k_i}{h} \big| ，其中 \displaystyle h=\frac{k_1}{u_1}

以下的範例取自原論文
有5個人要共享秘密，只要有2個人聚在一起就能重組秘密
1.隨機選取2個列向量 V_1={1,2,3},V_2={4,5,6}
2.計算外積 U=V_1 \times V_2=(u_1,u_2,u_3)=(-3,6,-3)
　秘密 S=6 \cdot 3=18
　將 u_1=-3 公開。
3.隨機選取一個 5 \times 2 矩陣A，乘上 V_i 矩陣，得到子秘密 s_i
　 \displaystyle \pmatrix{9 & 12 & 15 \cr 3 & 3 & 3 \cr 24 & 33 & 42 \cr 14 & 19 & 24 \cr -10 & -11 & -12}= \pmatrix{1 & 2 \cr -1 & 1 \cr 4 & 5 \cr 2 & 3 \cr 2 & -3} \pmatrix{1 & 2 & 3 \cr 4 & 5 & 6}
　得到子秘密 s_1=(9,12,15)、s_2=(3,3,3)、s_3=(24,33,42)、s_4=(14,19,24)、s_5=(-10,-11,-12)
4.現在有2個人聚在一起要重組秘密S
　 \displaystyle s_3 \times s_5=\pmatrix{ \left| \matrix{33 & 42 \cr -11 & -12} \right| , \left| \matrix{42 & 24 \cr -12 & -10} \right| , \left| \matrix{24 & 33 \cr -10 & -11} \right| } =(66,-132,66)
5.得到秘密 \displaystyle S=\big| \frac{132}{-22} \big| \cdot \big| \frac{66}{-22} \big|=18 ，其中 \displaystyle h=\frac{66}{-3}=-22 。


要先載入vect.mac才能使用向量外積指令express(V1~V2)
出自http://www.math.utexas.edu/pipermail/maxima/2006/000023.html
(%i1)　load("vect.mac");
(%o1)　C:/PROGRA~1/MAXIMA~1.0-2/share/maxima/5.28.0-2/share/vector/vect.mac

隨機選取2個列向量V1,V2
(%i2)
V1:[1,2,3];
V2:[4,5,6];
(%o2)　 [1,2,3]
(%o3)　 [4,5,6]

V1,V2外積得到向量U
(%i4)　U:express(V1~V2);
(%o4)　 [-3,6,-3]

得到秘密S，並將U的第一個分量公開
(%i5)
h:U[1];
S:abs(U[2])*abs(U[3]);
(%o5)　 -3
(%o6)　18

隨機選取5*2維的矩陣A
(%i7)
A:matrix([ 1, 2],
         [-1, 1],
         [ 4, 5],
         [ 2, 3],
         [ 2,-3]);
(%o7)　 \displaystyle \pmatrix{1 & 2 \cr -1 & 1 \cr 4 & 5 \cr 2 & 3 \cr 2 & -3}

矩陣A乘矩陣V得到子秘密s，將列向量分給5位使用者
(%i8)　s:A.matrix(V1,V2);
(%o8)　 \displaystyle \pmatrix{9 & 12 & 15 \cr 3 & 3 & 3 \cr 24 & 33 & 42 \cr 14 & 19 & 24 \cr -10 & -11 & -12}

假設第3位和第5位使用者聚在一起要重組秘密
(%i9)　express(s[3]~s[5]);
(%o9)　 [66,-132,66]

計算和當初外積相差的倍數
(%i10)　h:%[1]/U[1];
(%o10)　 -22

得到秘密S
(%i11)　S:abs(%o9[2]/h)*abs(%o9[3]/h);
(%o11)　18

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

設定n個人共享秘密，至少要k個人才能重建秘密
(%i1)
n:8;
t:6;
(%o1)　8
(%o2)　6

隨機產生t列(t+1)行的矩陣V
(%i3)　V:genmatrix(lambda([i, j],random(10)),t,t+1);
(%o3)　 \displaystyle \pmatrix{2&2&4&5&4&1&9 \cr 5&8&3&5&5&0&6 \cr 9&0&9&4&7&6&9 \cr 9&3&9&6&6&6&3 \cr 0&1&2&9&9&8&6 \cr 5&3&3&7&8&4&6}

計算V1,V2,...,Vt的外積U
(%i4)
addrow(V,create_list((-1)^i*ident(t+1)[ i ],i,1,t+1));
U:determinant(%);
(%o4)　 \displaystyle \pmatrix{2&2&4&5&4&1&9 \cr 5&8&3&5&5&0&6 \cr 9&0&9&4&7&6&9 \cr 9&3&9&6&6&6&3 \cr 0&1&2&9&9&8&6 \cr 5&3&3&7&8&4&6 \cr [-1,0,0,0,0,0,0] & [0,1,0,0,0,0,0] & [0,0,-1,0,0,0,0] & [0,0,0,1,0,0,0] & [0,0,0,0,-1,0,0] & [0,0,0,0,0,1,0] & [0,0,0,0,0,0,-1]}
(%o5)　 [-23496,1488,28440,17232,42288,24960,-13536]

公開U的第一個分量u1，其餘分量不公開
(%i6)　u1:U[1];
(%o6)　-23496

將剩下的分量相乘當成祕密S
(%i7)　S:product(abs(U[ i ]),i,2,t+1);
(%o7)　10418861903245330297651200

隨機選取n列t行的矩陣A
(%i8)　A:genmatrix(lambda([i,j],random(10)),n,t);
(%o8)　 \displaystyle \pmatrix{5&0&7&6&5&4 \cr 7&2&8&3&0&6 \cr 2&6&6&7&4&6 \cr 9&1&6&8&2&0 \cr 2&2&1&3&5&2 \cr 9&9&1&6&9&0 \cr 8&8&8&3&9&0 \cr 6&3&2&3&0&9}


將A矩陣和V矩陣相乘得到子秘密s
將每一列s[ i ]分派給這n個人
(%i9)　s:A.V;
(%o9)　 \displaystyle \pmatrix{147&45&159&162&182&139&180 \cr 153&57&151&137&160&97&192 \cr 181&95&169&184&206&136&189 \cr 149&52&169&140&149&109&177 \cr 60&40&66&101&104&74&90 \cr 126&117&144&211&205&123&216 \cr 155&98&173&211&227&146&255 \cr 117&72&105&134&143&72&153}

假設有t個人聚在一起要重建秘密
將每個人所擁有的子秘密s[ i ]重組成矩陣V
(%i10)　V:apply('matrix,rest(random_permutation(args(s)),n-t));
(%o10)　 \displaystyle \pmatrix{155&98&173&211&227&146&255 \cr 147&45&159&162&182&139&180 \cr 117&72&105&134&143&72&153 \cr 181&95&169&184&206&136&189 \cr 153&57&151&137&160&97&192 \cr 60&40&66&101&104&74&90}

計算V1,V2,...,Vt的外積U
(%i11)
addrow(V,create_list((-1)^i*ident(t+1)[ i ],i,1,t+1));
U:determinant(%);
(%o11)　 \displaystyle \pmatrix{155&98&173&211&227&146&255 \cr 147&45&159&162&182&139&180 \cr 117&72&105&134&143&72&153 \cr 181&95&169&184&206&136&189 \cr 153&57&151&137&160&97&192 \cr 60&40&66&101&104&74&90 \cr [-1,0,0,0,0,0,0] & [0,1,0,0,0,0,0] & [0,0,-1,0,0,0,0] & [0,0,0,1,0,0,0] & [0,0,0,0,-1,0,0] & [0,0,0,0,0,1,0] & [0,0,0,0,0,0,-1]}
(%o12)　 [238719360,-15118080,-288950400,-175077120,-429646080,-253593600,137525760]

將外積U的第一個分量除以之前公開的u1，得到相差的倍數h
(%i13)　h:U[1]/u1;
(%o13)　-10160

將剩下的分量相乘得到祕密S
(%i14)　S:product(abs(U[ i ]/h),i,2,t+1);
(%o14)　10418861903245330297651200

9.秘密分享方案介紹－Li Bai

這個方案是基於矩陣投影，詳細內容請見
Li Bai, A Strong Ramp Secret Sharing Scheme Using Matrix Projection, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.652-656, June 26-29, 2006

假設有n個人要共享 m \times m 的秘密矩陣S，只要有k個人在一起就能重組秘密。
1.隨機選取 m \times k 的矩陣A，其中 m>2(k-1)-1 。
2.隨機選取n個 k \times 1 向量 x_i ，其中任意k個向量是線性獨立。
3.計算 s_i=Ax_i \pmod{p} ， 1 \le i \le n 。
　每個人拿到所屬的子秘密 s_i ， 1 \le i \le n
4.計算A的矩陣投影 proj(A)=A(A'A)^{-1}A 。
　 A' 代表矩陣轉置， A^{-1} 代表反矩陣
5.計算矩陣 R=(S-proj(A)) \pmod{p} 。
　公開矩陣R
6.現在有k個人聚在一起要重組秘密矩陣S
　 s_{i1},s_{i2},\ldots,s_{ik}
7.將這k個子秘密組成矩陣B
　 B=[ \matrix{s_{i1} & s_{i2} & \ldots & s_{ik}} ]
8.計算B的矩陣投影 proj(B)=B(B'B)^{-1}B 。
9.計算 S=(proj(B)+R) \pmod{p}
　得到秘密矩陣S。


例子取自論文，為了文章一致性，本文所使用的符號和論文略有不同。

有3個人要共享 3 \times 3 的秘密矩陣 \displaystyle S=\pmatrix{2 & 3 & 1 \cr 5 & 4 & 6 \cr 8 & 9 & 7} ，只要有2個人在一起就能重組秘密。
約定在 F_{19} 底下運算
1.隨機選取 3 \times 2 的矩陣 \displaystyle A=\pmatrix{10 & 1 \cr 7 & 2 \cr 8 & 4}
　其中 m=3,k=2 滿足 m>2(k-1)-1 。
2.隨機選取3個 2 \times 1 向量， \displaystyle x_1=\pmatrix{1 \cr 17},x_2=\pmatrix{1 \cr 7},x_3=\pmatrix{1 \cr 9}
　其中任2個向量都是線性獨立。
3.計算 s_i=Ax_i \pmod{19} ， 1 \le i \le 3
　 \displaystyle s_1=\pmatrix{10 & 1 \cr 7 & 2 \cr 8 & 4} \pmatrix{1 \cr 17}=\pmatrix{8 \cr 3 \cr 0} \pmod{19} ，

　 \displaystyle s_2=\pmatrix{10 & 1 \cr 7 & 2 \cr 8 & 4} \pmatrix{1 \cr 7}=\pmatrix{17 \cr 2 \cr 17} \pmod{19} ，

　 \displaystyle s_2=\pmatrix{10 & 1 \cr 7 & 2 \cr 8 & 4} \pmatrix{1 \cr 9}=\pmatrix{0 \cr 6 \cr 6} \pmod{19} ，
4.計算A的投影矩陣 \displaystyle proj(A)=(A(A'A)^{-1}A) \pmod{19}=\pmatrix{13 & 6 & 13 \cr 6 & 4 & 16 \cr 13 & 16 & 4}
5.計算矩陣 R=(S-proj(A)) \pmod{19}=\pmatrix{8 & 16 & 7 \cr 18 & 0 & 9 \cr 14 & 12 & 3} ，公開矩陣R。
6.現在有2個人聚在一起要重組秘密矩陣S
　 \displaystyle s_1=\pmatrix{8 \cr 3 \cr 0},s_2=\pmatrix{17 \cr 2 \cr 17}
7.將這2個子秘密組成矩陣 \displaystyle B=\pmatrix{8 & 17 \cr 3 & 2 \cr 0 & 17}
8.計算B的矩陣投影 \displaystyle proj(B)=(B(B'B)^{-1}B') \pmod{19}=\pmatrix{13 & 6 & 13 \cr 6 & 4 & 16 \cr 13 & 16 & 4}
9.計算 S=(proj(B)+R) \pmod{19}=\pmatrix{2 & 3 & 1 \cr 5 & 4 & 6 \cr 8 & 9 & 7}


假設有3個人要共享3*3的秘密矩陣S，有2個人聚在一起就能重組秘密
(%i1)　S:matrix([2,3,1],[5,4,6],[8,9,7]);
(%o1)　 \displaystyle \pmatrix{2 & 3 & 1 \cr 5 & 4 & 6 \cr 8 & 9 & 7}

隨機選取3*2的矩陣A
(%i2)　A:matrix([10,1],[7,2],[8,4]);
(%o2)　 \displaystyle \pmatrix{10 & 1 \cr 7 & 2 \cr 8 & 4}

隨機選取3個2*1向量x
(%i3)　x:[matrix([1],[17]),matrix([1],[7]),matrix([1],[9])];
(%o3)　 \displaystyle [ \pmatrix{1 \cr 17},\pmatrix{1 \cr 7},\pmatrix{1 \cr 9} ]

約定在Fp底下運算
(%i4)
p:19;
modulus:p;
(%o4)　19
(%o5)　19

A矩陣和x相乘得到子秘密s，分給3位使用者
(%i6)　s:create_list(mod(A.x[ i ],p),i,1,3);
(%o6)　 \displaystyle [ \pmatrix{8 \cr 3 \cr 0},\pmatrix{17 \cr 2 \cr 17},\pmatrix{0 \cr 6 \cr 6} ]

計算A的投影矩陣proj(A)=A(A'A)^(-1)A
(%i7)　projA:mod(rat(A.invert(transpose(A).A).transpose(A)),p);
(%o7)　 \displaystyle \pmatrix{13 & 6 & 13 \cr 6 & 4 & 16 \cr 13 & 16 & 4}

計算R=S-projA (mod p)，並公開矩陣R
(%i8)　R:mod(S-projA,p);
(%o8)　 \displaystyle \pmatrix{8 & 16 & 7 \cr 18 & 0 & 9 \cr 14 & 12 & 3}

假設第1位和第2位使用者聚在一起要重組秘密，將這2位的子秘密合併成矩陣B
(%i9)　B:apply(addcol,[s[1],s[2]]);
(%o9)　 \displaystyle \pmatrix{8 & 17 \cr 3 & 2 \cr 0 & 17}

計算B的投影矩陣proj(B)=B(B'B)^(-1)B
(%i10)　projB:mod(rat(B.invert(transpose(B).B).transpose(B)),p);
(%o10)　 \displaystyle \pmatrix{13 & 6 & 13 \cr 6 & 4 & 16 \cr 13 & 16 & 4}

計算S=projB+R (mod p)，得到秘密矩陣S
(%i11)　S:mod(projB+R,p);
(%o11)　 \displaystyle \pmatrix{2 & 3 & 1 \cr 5 & 4 & 6 \cr 8 & 9 & 7}

[ 本帖最後由 bugmens 於 2013-12-21 11:58 AM 編輯 ]

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

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

選擇符合m>2(k-1)-1的m值
(%i3)　m:2*(k-1);
(%o3)　10

選擇質數p
(%i4)
p:next_prime(m^2);
modulus:p;
(%o4)　101
(%o5)　101

m*m的秘密矩陣S,這個範例設定的是1~m^2的數字
(%i6)　S:genmatrix(lambda([i,j],(i-1)*m+j),m,m);
(%o6)　 \displaystyle \pmatrix{1&2&3&4&5&6&7&8&9&10 \cr 11&12&13&14&15&16&17&18&19&20 \cr 21&22&23&24&25&26&27&28&29&30 \cr 31&32&33&34&35&36&37&38&39&40 \cr 41&42&43&44&45&46&47&48&49&50 \cr 51&52&53&54&55&56&57&58&59&60 \cr 61&62&63&64&65&66&67&68&69&70 \cr 71&72&73&74&75&76&77&78&79&80 \cr 81&82&83&84&85&86&87&88&89&90 \cr 91&92&93&94&95&96&97&98&99&100}

隨機選取m*k的矩陣A
(%i7)　A:genmatrix(lambda([i,j],random(p)),m,k);
(%o7)　 \displaystyle \pmatrix{53&20&50&22&63&43 \cr 43&39&83&76&86&22 \cr 63&91&15&10&89&56 \cr 64&32&3&22&40&10 \cr 69&18&14&58&91&64 \cr 77&95&72&29&97&24 \cr 90&32&20&61&46&48 \cr 77&100&59&15&16&9 \cr 83&75&93&93&77&65 \cr 93&49&94&10&18&23}

隨機選取n個k*1向量x(每一個直行就是一個向量xi)
(%i9)　x:genmatrix(lambda([i,j],random(p)),k,n);
(%o9)　 \displaystyle \pmatrix{33&89&53&82&61&13&0&66 \cr 28&79&52&76&19&54&17&94 \cr 60&62&89&63&25&41&44&80 \cr 22&24&61&40&70&10&8&17 \cr 56&5&56&4&8&37&81&49 \cr 73&83&10&23&34&24&0&77}

A矩陣和x相乘得到子秘密s
(%i10)　s:rat(A.x);
(%o10)/R/　 \displaystyle \pmatrix{37&-28&-36&27&-14&29&42&-10 \cr 31&-26&-46&-46&-26&34&-29&43 \cr -28&-30&6&22&-29&-25&2&30 \cr -24&-31&16&49&20&-23&-49&-29 \cr 20&36&-37&45&48&48&-30&-37 \cr -29&-23&44&-30&6&4&45&0 \cr -36&-17&43&-47&41&11&-18&-39 \cr -43&4&-30&19&-39&-19&-45&27 \cr 9&22&42&-49&-31&40&26&27 \cr -41&15&16&-8&-25&38&43&-22}

將子秘密s分給n個人
(%i11)　s:create_list(col(s,i),i,1,n);
(%o11)/R/　 \displaystyle [ \pmatrix{37 \cr 31 \cr -28 \cr -24 \cr 20 \cr -29 \cr -36 \cr -43 \cr 9 \cr -41}, \pmatrix{-28 \cr -26 \cr -30 \cr -31 \cr 36 \cr -23 \cr -17 \cr 4 \cr 22 \cr 15}, \pmatrix{-36 \cr -46 \cr 6 \cr 16 \cr -37 \cr 44 \cr 43 \cr -30 \cr 42 \cr 16}, \pmatrix{27 \cr -46 \cr 22 \cr 49 \cr 45 \cr -30 \cr -47 \cr 19 \cr -49 \cr -8}, \pmatrix{-14 \cr -26 \cr -29 \cr 20 \cr 48 \cr 6 \cr 41 \cr -39 \cr -31 \cr -25}, \pmatrix{29 \cr 34 \cr -25 \cr -23 \cr 48 \cr 4 \cr 11 \cr -19 \cr 40 \cr 38}, \pmatrix{42 \cr -29 \cr 2 \cr -49 \cr -30 \cr 45 \cr -18 \cr -45 \cr 26 \cr 43}, \pmatrix{-10 \cr 43 \cr 30 \cr -29 \cr -37 \cr 0 \cr -39 \cr 27 \cr 27 \cr -22} ]

投影矩陣的副程式
(%i12)　proj(M):=rat(M.invert(transpose(M).M).transpose(M));
(%o12)　proj(M):=rat(M . invert(transpose(M) . M) . transpose(M))

計算矩陣A的投影矩陣
(%i13)　projA:proj(A);
(%o13)/R/　 \displaystyle \pmatrix{14&29&-11&44&44&29&8&32&-11&-2 \cr 29&25&-44&-12&-46&-11&43&-49&47&2 \cr -11&-44&-8&-11&-44&-9&29&-21&15&-36 \cr 44&-12&-11&36&15&-46&-21&-30&-15&45 \cr 44&-46&-44&15&-45&27&-19&-39&-38&-40 \cr 29&-11&-9&-46&27&-39&48&3&6&9 \cr 8&43&29&-21&-19&48&18&42&-46&16 \cr 32&-49&-21&-30&-39&3&42&-3&-38&33 \cr -11&47&15&-15&-38&6&-46&-38&22&0 \cr -2&2&-36&45&-40&9&16&33&0&-14}

計算R=S-projA (mod p)，並公開矩陣R
(%i14)　R:mod(S-projA,p);
(%o14)　 \displaystyle \pmatrix{88&74&14&61&62&78&100&77&20&12 \cr 83&88&57&26&61&27&75&67&73&18 \cr 32&66&31&35&69&35&99&49&14&66 \cr 88&44&44&99&20&82&58&68&54&96 \cr 98&88&87&29&90&19&66&87&87&90 \cr 22&63&62&100&28&95&9&55&53&51 \cr 53&19&34&85&84&18&49&26&14&54 \cr 39&20&94&3&13&73&35&81&16&47 \cr 92&35&68&99&22&80&32&25&67&90 \cr 93&90&28&49&34&87&81&65&99&13}

假設有k個人聚在一起要重建秘密
(%i15)　rest(random_permutation(s),n-k);
(%o15)/R/　 \displaystyle [ \pmatrix{42 \cr -29 \cr 2 \cr -49 \cr -30 \cr 45 \cr -18 \cr -45 \cr 26 \cr 43}, \pmatrix{-36 \cr -46 \cr 6 \cr 16 \cr -37 \cr 44 \cr 43 \cr -30 \cr 42 \cr 16}, \pmatrix{37 \cr 31 \cr -28 \cr -24 \cr 20 \cr -29 \cr -36 \cr -43 \cr 9 \cr -41}, \pmatrix{-14 \cr -26 \cr -29 \cr 20 \cr 48 \cr 6 \cr 41 \cr -39 \cr -31 \cr -25}, \pmatrix{27 \cr -46 \cr 22 \cr 49 \cr 45 \cr -30 \cr -47 \cr 19 \cr -49 \cr -8}, \pmatrix{-10 \cr 43 \cr 30 \cr -29 \cr -37 \cr 0 \cr -39 \cr 27 \cr 27 \cr -22} ]

將每個人所擁有的子秘密s[ i ]重組成矩陣B
(%i16)　B:apply(addcol,%);
(%o16)/R/　 \displaystyle \pmatrix{42&-36&37&-14&27&-10 \cr -29&-46&31&-26&-46&43 \cr 2&6&-28&-29&22&30 \cr -49&16&-24&20&49&-29 \cr -30&-37&20&48&45&-37 \cr 45&44&-29&6&-30&0 \cr -18&43&-36&41&-47&-39 \cr -45&-30&-43&-39&19&27 \cr 26&42&9&-31&-49&27 \cr 43&16&-41&-25&-8&-22}

計算矩陣B的投影矩陣
(%i17)　projB:proj(B);
(%o17)/R/　 \displaystyle \pmatrix{14&29&-11&44&44&29&8&32&-11&-2 \cr 29&25&-44&-12&-46&-11&43&-49&47&2 \cr -11&-44&-8&-11&-44&-9&29&-21&15&-36 \cr 44&-12&-11&36&15&-46&-21&-30&-15&45 \cr 44&-46&-44&15&-45&27&-19&-39&-38&-40 \cr 29&-11&-9&-46&27&-39&48&3&6&9 \cr 8&43&29&-21&-19&48&18&42&-46&16 \cr 32&-49&-21&-30&-39&3&42&-3&-38&33 \cr -11&47&15&-15&-38&6&-46&-38&22&0 \cr -2&2&-36&45&-40&9&16&33&0&-14}

計算S=projB+R (mod p)，得到秘密矩陣S
(%i19)　mod(projB+R,p);
(%o19)　 \displaystyle \pmatrix{1&2&3&4&5&6&7&8&9&10 \cr 11&12&13&14&15&16&17&18&19&20 \cr 21&22&23&24&25&26&27&28&29&30 \cr 31&32&33&34&35&36&37&38&39&40 \cr 41&42&43&44&45&46&47&48&49&50 \cr 51&52&53&54&55&56&57&58&59&60 \cr 61&62&63&64&65&66&67&68&69&70 \cr 71&72&73&74&75&76&77&78&79&80 \cr 81&82&83&84&85&86&87&88&89&90 \cr 91&92&93&94&95&96&97&98&99&100}

10.秘密分享方案介紹－Sonali Patil, Prashant Deshmukh

這個方案是基於線性獨立向量的內積，詳細內容請見
A Novel (t,n) Threshold Secret Sharing Using Dot Product of Linearly Independent Vectors
http://www.ijarcce.com/upload/20 ... ecret%20sharing.pdf

假設有n個人要共享秘密S，只要有k個人在一起就能重組秘密。
1.隨機選取向量X和向量$，滿足 S=$.X 。
2.選取Vandermode矩陣 Y_{ij} ， 1 \le i \le n ， 1 \le j \le k 。
3.計算 \displaystyle \matrix{ s_1=$_1.Y_{11}+$_2.Y_{12}+\ldots+$_k.Y_{1k} \cr s_2=$_1.Y_{21}+$_2.Y_{22}+\ldots+$_k.Y_{2k} \cr \ldots \cr s_n=$_1.Y_{n1}+$_2.Y_{n2}+\ldots+$_k.Y_{nk} \cr} ，得到子秘密 s_i ， 1 \le i \le n

4.銷毀秘密S和向量$。
5.將子秘密 s_i 分配給n個人。
6.公開Vandermode矩陣Y和向量X。


有k個人聚在一起要重組秘密S
1.將子秘密 s_i 代入聯立方程組
　 \displaystyle s_i=$_1.Y_{i1}+$_2.Y_{i2}+\ldots+$_k.Y_{ik} ， 1 \le i \le k
　解聯立方程式得到當初設定的向量$。
2.計算$.X得到秘密S。


例子
有 n=8 個人要共享秘密 S=12345 ，只要有 k=6 個人就能重組秘密。
1.隨機選取向量 X=(12,2,34,85,4,1) 和 $=(91,29,85,98,3,-37)
　滿足 S=12 \times 91+2 \times 29+34 \times 85+85 \times 98+4 \times 3+1 \times (-37)=12345
2.選取Vandermode矩陣 \displaystyle Y=\pmatrix{1&2&3&4&5&6&7&8 \cr 1&4&9&16&25&36&49&64 \cr 1&8&27&64&125&216&343&512 \cr 1&16&81&256&625&1296&2401&4096 \cr 1&32&243&1024&3125&7776&16807&32768 \cr 1&64&729&4096&15625&46656&117649&262144}
3.計算 s=$.Y ，得到子秘密 s_i=(269,274,-15477,-117124,-495695,-1555986,-4036081,-9153512)
　 \displaystyle \pmatrix{91 & 29 & 85 & 98 & 3 & -37} \pmatrix{1&2&3&4&5&6&7&8 \cr 1&4&9&16&25&36&49&64 \cr 1&8&27&64&125&216&343&512 \cr 1&16&81&256&625&1296&2401&4096 \cr 1&32&243&1024&3125&7776&16807&32768 \cr 1&64&729&4096&15625&46656&117649&262144}= \pmatrix{269 & 274 & -15477 & -117124 & -495695 & -1555986 & -4036081 & -9153512}
4.銷毀秘密S和向量$。
5.將子秘密 s_i 分配給n個人。
6.公開Vandermode矩陣Y和向量X。



有 k=6 個人聚在一起要重組秘密S
第3位使用者的子秘密 s_3=−15477
第2位使用者的子秘密 s_2=274
第8位使用者的子秘密 s_8=−9153512
第6位使用者的子秘密 s_6=−1555986
第1位使用者的子秘密 s_1=269
第7位使用者的子秘密 s_7=−4036081

1.將子秘密 s_i 代入聯立方程組
　 \displaystyle \pmatrix{$_1 & $_2 & $_3 & $_4 & $_5 & $_6} \pmatrix{3&2&8&6&1&7 \cr 9&4&64&36&1&49 \cr 27&8&512&216&1&343 \cr 81&16&4096&1296&1&2401 \cr 243&32&32768&7776&1&16807 \cr 729&64&262144&46656&1&117649}=\pmatrix{-15477 & 274 & -9153512 & -1555986 & 269 & -4036081}
　解聯立方程式得到當初設定的向量 $=(91,29,85,98,3,-37)
2.計算$.X得到秘密 S=12 \times 91+2 \times 29+34 \times 85+85 \times 98+4 \times 3+1 \times (-37)=12345  


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

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

隨機選取k-1個X值
(%i4)　X:create_list(random(100),i,1,k-1);
(%o4)　 [12,2,34,85,4]

隨機選取k-1個$值
(%i5)　Dollar:create_list(random(100),i,1,k-1);
(%o5)　 [91,29,85,98,3]

為了湊出S=X.$，先計算X和$前k-1個值的內積
將秘密S減掉前面內積的結果
剩下來的值附加在Dollar後面
X則附加1，並將向量X公開
(%i6)
Dollar:append(Dollar,[S-Dollar.X]);
X:append(X,[1]);
(%o6)　 [91,29,85,98,3,-37]
(%o7)　 [12,2,34,85,4,1]

檢查秘密S是否等於$.X
(%i8)　is(S=Dollar.X);
(%o8)　true

產生k*n的Vandermode矩陣Y
(%i9)　Y:genmatrix(lambda([i,j],j^i),k,n);
(%o9)　 \displaystyle \pmatrix{1&2&3&4&5&6&7&8 \cr 1&4&9&16&25&36&49&64 \cr 1&8&27&64&125&216&343&512 \cr 1&16&81&256&625&1296&2401&4096 \cr 1&32&243&1024&3125&7776&16807&32768 \cr 1&64&729&4096&15625&46656&117649&262144}

計算s=$.Y得到子秘密si
(%i10)　s: Dollar.Y;
(%o10)　 [\matrix{269&274&-15477&-117124&-495695&-1555986&-4036081&-9153512}]

但子秘密si還要加上序號，之後才能還原出秘密S
(%i11)　s:create_list([s[1,i],i],i,1,n);
(%o11)　 [[269,1],[274,2],[-15477,3],[-117124,4],[- 495695,5],[-1555986,6],[-4036081,7],[-9153512,8]]

其中k個人聚在一起要重組秘密S
(%i12)
random_permutation(%)$
s:rest(%,n-k);
(%o13)　 [[-15477,3],[274,2],[-9153512,8],[-1555986,6 ],[269,1],[-4036081,7]]

取出各si的第一個值，形成1*k的矩陣sk
(%i14)　sk:genmatrix(lambda([i,j],s[j][1]),1,k);
(%o14)　 [\matrix{-15477&274&-9153512&-1555986&269&-4036081}]

取出各si的第二個值，形成k*k的Vandermode矩陣Y
(%i15)　Y:genmatrix(lambda([i,j],s[j][2]^i),k,k);
(%o15)　 \displaystyle \pmatrix{3&2&8&6&1&7 \cr 9&4&64&36&1&49 \cr 27&8&512&216&1&343 \cr 81&16&4096&1296&1&2401 \cr 243&32&32768&7776&1&16807 \cr 729&64&262144&46656&1&117649}

計算矩陣Y的反方陣
(%i16)　inv_Y:invert(Y);
(%o16)　 \displaystyle \pmatrix{ \frac{28}{15} & -\frac{65}{18} & \frac{34}{15} & -\frac{211}{360} & \frac{1}{15} & -\frac{1}{360} \cr -\frac{21}{5} & \frac{297}{40} & -\frac{983}{240} & \frac{233}{240} & -\frac{5}{48} & \frac{1}{240} \cr -\frac{3}{40} & \frac{9}{56} & -\frac{401}{3360} & \frac{131}{3360} & -\frac{19}{3360} & \frac{1}{3360} \cr -\frac{7}{15} & \frac{353}{360} & -\frac{169}{240} & \frac{157}{720} & -\frac{7}{240} & \frac{1}{720} \cr \frac{24}{5} & -\frac{213}{35} & \frac{298}{105} & -\frac{257}{420} & \frac{13}{210} & -\frac{1}{420} \cr \frac{12}{35} & -\frac{51}{70} & \frac{8}{15} & -\frac{143}{840} & \frac{1}{42} & -\frac{1}{840} }

將sk矩陣和Y的反方陣相乘得到當初的$矩陣
(%i17)　Dollar:sk.inv_Y;
(%o17)　 [91,29,85,98,3,-37]

將$矩陣再和公開的X相乘得到秘密S
(%i18)　S: Dollar.X;
(%o18)　12345

[ 本帖最後由 bugmens 於 2014-1-30 10:24 AM 編輯 ]