Math Pro 數學補給站's Archiver

一隻孤雁要經過一片海峽,起飛時要知道怎飛,
起飛後,要想好下一個落腳點在哪裡,
而最重要的是既然飛了,一定要對自己有信心。

bugmens 發表於 2013-4-6 19:52

用Maxima學密碼學-秘密分享

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

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

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


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

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

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

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

機密共享機制
[url]http://ec2.ba.ntust.edu.tw/mic/download/security/%E5%AF%86%E7%A2%BC%E5%AD%B8%E8%88%87%E8%B3%87%E8%A8%8A%E5%AE%89%E5%85%A8ch10.doc[/url]

門檻式簽章之介紹
[url]http://elab.im.ncue.edu.tw/ppt/dfs1/2012%E6%95%B8%E4%BD%8D%E7%A7%91%E6%8A%80%E8%88%87%E5%89%B5%E6%96%B0%E7%AE%A1%E7%90%86%E7%A0%94%E8%A8%8E%E6%9C%83%E8%AB%96%E6%96%87%E9%9B%86/C135.pdf[/url]

Secret sharing
[url]http://en.wikipedia.org/wiki/Secret_sharing[/url]

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

bugmens 發表於 2013-4-7 12:34

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

假設分派者(Dealer)選定要共享的秘密S及一個質數p,滿足\( 0<S<p \)。分派者任意挑選一個\( k-1 \)次方的多項式\( f(x)=a_0+a_1x+a_2x^2+...+a_{k-1}x^{k-1} \),滿足\( a_0=S \),\( 0<a_1,a_2,…,a_{k-1}<p \)。
分派者利用\( f(x) \)產生n個子金匙\( (i,f(i)) \),\( i=1,2,...,n \)。每對\( (i,f(i)) \)可視為多項式\( f(x) \)在坐標平面上的一個點,由於\( f(x) \)為\( k-1 \)次方的多項式,因此k對或k對以上的點坐標可惟一決定\( f(x) \),進而重建出秘密S。

以下的範例出自[url]http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing[/url],只是沒有在\( Z_p \)底下運算。

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

[color=green]設定秘密為S=1234,n=6個人共享秘密,至少要k=3位才能重組秘密[/color]
[color=red](%i2)[/color] [color=blue]S:1234;[/color]
[color=red](%o2)[/color] 1234

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

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

[color=green]假設第2,4,5位聚在一起要重組秘密S,利用拉格朗日插值多項式計算出f(x)[/color]
[color=red](%i5)[/color] [color=blue]lagrange([%[2],%[4],%[5]]);[/color]
[color=red](%o5)[/color] \( \displaystyle \frac{4414(x-4)(x-2)}{3}-1701(x-5)(x-2)+\frac{971(x-5)(x-4)}{3} \)

[color=red](%i6)[/color] [color=blue]ratsimp(%);[/color]
[color=red](%o6)[/color] \( 94x^2+166x+1234 \)

[color=green]其中常數項就是當初設定的祕密S[/color]
[color=red](%i7)[/color] [color=blue]ev(%,x=0);[/color]
[color=red](%o7)[/color] 1234

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

bugmens 發表於 2013-4-21 20:20

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


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

[color=green]設定秘密S
(這個數字可自行修改,但\( S<p \) )[/color]
[color=red](%i2)[/color] [color=blue]S:12345;[/color]
[color=red](%o2)[/color] 12345

[color=green]設定在\( F_p \)底下運算,其中p為質數[/color]
[color=red](%i3)[/color]
[color=blue]p:65537;
modulus:p;[/color]
[color=green](%o3)[/color] 65537
[color=green](%o4)[/color] 65537

[color=green]設定n個人共享秘密,至少要k個人才能重建秘密
(這兩個數字可自行修改,但\( n \ge k \) )[/color]
[color=red](%i5)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o5)[/color] 8
[color=red](%o6)[/color] 6

[color=green]隨機產生k-1次多項式,其中常數項為秘密S[/color]
[color=red](%i7)[/color] [color=blue]f(x):=''(S+apply("+",create_list(random(p)*x^i,i,1,k-1)));[/color]
[color=red](%o7)[/color] \( f(x) :=5290x^5+18871x^4+4877x^3+31816x^2+60108x+12345 \)

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

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

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

[color=green]利用拉格朗日插值多項式計算通過這k個點座標的k-1次多項式[/color]
[color=red](%i12)[/color] [color=blue]lagrange(%);[/color]
[color=red](%o12)[/color] \( \displaystyle \frac{59(x-7)(x-4)(x-3)(x-2)(x-1)}{10}+\frac{739(x-8)(x-4)(x-3)(x-2)(x-1)}{40} \)
\( \displaystyle -\frac{4001(x-8)(x-7)(x-3)(x-2)(x-1)}{18}-\frac{16789(x-8)(x-7)(x-4)(x-2)(x-1)}{40} \)
\( \displaystyle -\frac{16387(x-8)(x-7)(x-4)(x-3)(x-1)}{60}+\frac{319(2-x)(x-8)(x-7)(x-4)(x-3)}{36} \)

[color=green]其中常數項為當初設定的祕密S[/color]
[color=red](%i13)[/color] [color=blue]ev(%,x=0);[/color]
[color=red](%o13)[/color] \( \displaystyle \frac{6804412}{15} \)

[color=green]若結果出現分數,但在Fp底下運算
則秘密\( S=分子*分母^{-1} \pmod{p} \)[/color]
[color=red](%i14)[/color] [color=blue]ratsimp(%);[/color]
[color=red](%o14)[/color] 12345

bugmens 發表於 2013-6-21 21:12

這次我用另一種方法解出秘密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矩陣
[url]http://en.wikipedia.org/wiki/Vandermonde_matrix[/url]
其行列式\( \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 \)


[color=green]設定秘密S
(這個數字可自行修改,但\( S<p \) )[/color]
[color=red](%i1)[/color] [color=blue]S:12345;[/color]
[color=red](%o1)[/color] 12345

[color=green]設定在\( F_p \)底下運算,其中p為質數[/color]
[color=red](%i2)[/color]
[color=blue]p:65537;
modulus:p;[/color]
[color=green](%o2)[/color] 65537
[color=green](%o3)[/color] 65537

[color=green]設定n個人共享秘密,至少要k個人才能重建秘密
(這兩個數字可自行修改,但\( n \ge k \) )[/color]
[color=red](%i4)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o4)[/color] 8
[color=red](%o5)[/color] 6

[color=green]隨機產生k-1次多項式,其中常數項為秘密S[/color]
[color=red](%i6)[/color] [color=blue]f(x):=''(S+apply("+",create_list(random(p)*x^i,i,1,k-1)));[/color]
[color=red](%o7)[/color] \( f(x) :=5290x^5+18871x^4+4877x^3+31816x^2+60108x+12345 \)

[color=green]產生n個點座標[/color]
[color=red](%i7)[/color] [color=blue]create_list([i,f(i)],i,1,n);[/color]
[color=red](%o7)[/color] [[1,133307],[2,770057],[3,3424713],[4,11321897],[5,30043535],[6,68163657],[7,137883197],[8,255664793]]

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

[color=green]假設有k個人聚在一起要重建秘密[/color]
[color=red](%i9)[/color]
[color=blue]random_permutation(%)$
shadows:create_list(%[ i ],i,1,k);[/color]
[color=red](%o10)/R/[/color] [[8,4956],[4,-16004],[1,2233],[7,-6651],[3,16789],[2,-16387]]

[color=green]建立\( x_i \)的係數矩陣[/color]
[color=red](%i11)[/color] [color=blue]genmatrix (lambda([ i, j],shadows[ i ][1]^j), k, k-1,1,0);[/color]
[color=red](%o11)/R/[/color] \( \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} \)

[color=green]建立\( y_i \)的係數矩陣[/color]
[color=red](%i12)[/color] [color=blue]genmatrix(lambda([ i,j], shadows[ i][2]), k,1);[/color]
[color=red](%o12)/R/[/color] \( \displaystyle \pmatrix{4956 \cr -16004 \cr 2233 \cr -6651 \cr 16789 \cr -16387} \)

[color=green]解出未知數\( a_0,a_1,a_2,a_3,a_4,a_5 \)[/color]
[color=red](%i13)[/color] [color=blue]linsolve_by_lu(%o11,%o12);[/color]
[color=red](%o13)[/color] \( \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] \)

[color=red](%i14)[/color] [color=blue]rat(%[1]);[/color]
[color=red](%o14)[/color]/R/ \( \displaystyle \pmatrix{12345 \cr -5429 \cr 31816 \cr 4877 \cr 18871 \cr 5290} \)

[color=green]其中\( a_0 \)就是祕密\( S=12345 \)[/color]
[color=red](%i15)[/color] [color=blue]S:%[1][1];[/color]
[color=red](%o15)/R/[/color] 12345

[[i] 本帖最後由 bugmens 於 2013-7-13 06:09 AM 編輯 [/i]]

bugmens 發表於 2013-7-1 20:58

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 \)

[img=200x200]http://upload.wikimedia.org/wikipedia/commons/9/9b/Secretsharing-1.png[/img][img=200x200]http://upload.wikimedia.org/wikipedia/commons/b/b3/IntersectingPlanes.png[/img][img=200x200]http://upload.wikimedia.org/wikipedia/commons/c/cd/Secretsharing-3-point.png[/img][/size]
圖來自[url]http://en.wikipedia.org/wiki/Secret_sharing#Blakley.27s_scheme[/url]

例子
設定點坐標\( (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


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

[color=green]設定顯示順序為x,y,z
  預設順序為z,y,x[/color]
[color=red](%i2)[/color] [color=blue]powerdisp:true;[/color]
[color=red](%o2)[/color] [i]true[/i]

[color=green]設定秘密S[/color]
[color=red](%i3)[/color] [color=blue]S:12345;[/color]
[color=red](%o3)[/color] 12345

[color=green]設定在Fp底下運算,其中p為質數[/color]
[color=red](%i4)[/color]
[color=blue]p:65537;
modulus:p;[/color]
[color=red](%o4)[/color] 65537
[color=red](%o5)[/color] 65537

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

[color=green]有n個人要共享秘密[/color]
[color=red](%i9)[/color] [color=blue]n:6;[/color]
[color=red](%o9)[/color] 6

[color=green]產生n個平面方程式ax+by+cz=d,其中a,b,c為任意數字
將(x0,y0,z0)代入平面方程式後得到常數項d[/color]
[color=red](%i10)[/color]
[color=blue]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;[/color]
[color=red](%o12)/R/[/color] \( \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]} \)

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

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

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

bugmens 發表於 2013-7-13 07:50

上一篇可以稱為\( (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


[color=green]設定秘密S[/color]
[color=red](%i1)[/color]  [color=blue]S:12345;[/color]
[color=red](%o1)[/color] 12345

[color=green]設定在Fp底下運算,其中p為質數[/color]
[color=red](%i2)[/color]
[color=blue]p:65537;
modulus:p;[/color]
[color=red](%o2)[/color] 65537
[color=red](%o3)[/color] 65537

[color=green]有n個人要共享秘密,至少k個人才能重組秘密[/color]
[color=red](%i4)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o4)[/color] 8
[color=red](%o5)[/color] 6

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

[color=green]產生n個超平面方程式a1x1+a2x2+...+a6x6=b[/color]
[color=red](%i7)[/color] [color=blue]matrixA:genmatrix(lambda([i,j],random(p)),n,k);[/color]
[color=red](%o7)[/color] \( \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} \)

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

[color=green]將這n個超平面方程式分派給n個人[/color]
[color=red](%i9)[/color]
[color=blue]transpose(append(transpose(matrixA),transpose(matrixB)))$
create_list(%[ i ],i,1,n);[/color]
[color=red](%o10)/R/[/color]   \( \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]]} \)

[color=green]其中k個人聚在一起要重組秘密S[/color]
[color=red](%i11)[/color]
[color=blue]random_permutation(%)$
shadows:apply('matrix,rest(%,n-k));[/color]
[color=red](%o12)/R/[/color] \( \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} \)

[color=green]求出k個超平面方程式的交點坐標[/color]
[color=red](%i13)[/color]
[color=blue]A:submatrix(shadows,k+1)$
B:col(shadows,k+1)$
linsolve_by_lu(A,B);[/color]
[color=red](%o15)[/color] \( \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] \)

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

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

bugmens 發表於 2013-7-26 20:50

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

這個方案是基於中國剩餘定理,詳細內容請見wiki。
[url]http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86[/url]
[url]http://en.wikipedia.org/wiki/Secret_sharing_using_the_Chinese_remainder_theorem#Mignotte.27s_threshold_secret_sharing_scheme[/url]

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 \)


[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:4;
k:3;[/color]
[color=red](%o1)[/color] 4
[color=red](%o2)[/color] 3

[color=green]任選n項的遞增數列[/color]
[color=red](%i3)[/color] [color=blue]m:[7,8,9,11];[/color]
[color=red](%o3)[/color] \( [7,8,9,11] \)

[color=green]設定秘密S[/color]
[color=red](%i4)[/color] [color=blue]S:123;[/color]
[color=red](%o4)[/color] 123

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

[color=green]檢查S是否落在這二個數字之間[/color]
[color=red](%i7)[/color] [color=blue]is(product1<S and S<product2);[/color]
[color=red](%o7)[/color] [i]true[/i]

[color=green]計算子秘密s[/color]
[color=red](%i8)[/color] [color=blue]s:mod(S,m);[/color]
[color=red](%o8)[/color] \( [4,3,6,2] \)

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

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

bugmens 發表於 2013-8-2 08:40

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


[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o1)[/color] 8
[color=red](%o2)[/color] 6

[color=green]找出符合m(n-k+2)*m(n-k+3)*...*m(n) < m(1)*m(2)*...*m(k)的遞增數列m
為了方便數列m都採用質數,其中任兩個數字一定互質[/color]
[color=red](%i3)[/color]
[color=blue]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;[/color]
[color=red](%o5)[/color] \( [11,17,19,29,31,37,41,53] \)

[color=green]m(n-k+2)*m(n-k+3)*...*m(n)的乘積為product1
   m(1)*m(2)*...*m(k)的乘積為product2[/color]
[color=red](%i6)[/color]
[color=blue]product1;
product2;[/color]
[color=red](%o6)[/color] 72280499
[color=red](%o7)[/color] 118183439

[color=green]設定秘密S[/color]
[color=red](%i8)[/color] [color=blue]S:12345;[/color]
[color=red](%o8)[/color] 12345

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

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

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

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

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

bugmens 發表於 2013-8-17 20:32

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

這個方案是基於中國剩餘定理,詳細內容請見wiki。
[url]http://en.wikipedia.org/wiki/Secret_sharing_using_the_Chinese_remainder_theorem#Asmuth-Bloom.27s_threshold_secret_sharing_scheme[/url]

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
[url]http://en.wikipedia.org/wiki/Secret_sharing_using_the_Chinese_remainder_theorem#Example[/url]
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} \)



[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:4;
k:3;[/color]
[color=red](%o1)[/color] 4
[color=red](%o2)[/color] 3

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

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

[color=green]檢查m(0)*m(n-k+2)*m(n-k+3)*...*m(n)是否小於
  m(1)*m(2)*...*m(k)[/color]
[color=red](%i7)[/color] [color=blue]is(product1 < product2);[/color]
[color=red](%o7)[/color] [i]true[/i]

[color=green]設定秘密S[/color]
[color=red](%i8)[/color] [color=blue]S:2;[/color]
[color=red](%o8)[/color] 2

[color=green]檢查S是否小於m0[/color]
[color=red](%i9)[/color] [color=blue]is(S < m0);[/color]
[color=red](%o9)[/color] [i]true[/i]

[color=green]任意整數α[/color]
[color=red](%i10)[/color] [color=blue]alpha:51;[/color]
[color=red](%o10)[/color] 51

[color=green]檢查S+α*m0是否小於m(1)*m(2)*...*m(k)[/color]
[color=red](%i11)[/color] [color=blue]is(S+alpha*m0 < product2);[/color]
[color=red](%o11)[/color] [i]true[/i]

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

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

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

bugmens 發表於 2013-8-20 12:43

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


[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o1)[/color] 8
[color=red](%o2)[/color] 6

[color=green]設定秘密S[/color]
[color=red](%i3)[/color] [color=blue]S:12345;[/color]
[color=red](%o3)[/color] 12345

[color=green]找出符合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獨立出來)[/color]
[color=red](%i4)[/color]
[color=blue]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;[/color]
[color=red](%o6)[/color] 14843
[color=red](%o7)[/color] \( [20857,21163,22871,23399,24439,24469,25409,26209] \)

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

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

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

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

[color=green]秘密S還要對m0取餘數才是答案[/color]
[color=red](%i17)[/color] [color=blue]mod(S,m0);[/color]
[color=red](%o17)[/color] 12345

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

bugmens 發表於 2013-8-31 10:46

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

這個方案是基於質因數分解,詳細內容請見
钟红山,素数集合秘密共享方案
[url]https://www.google.com.tw/search?q=zhonghongshan381615-self-200812-7&oq=zhonghongshan381615-self-200812-7&gs_l=serp.3...344064.344443.0.344862.2.2.0.0.0.0.59.114.2.2.0....0...1c.1.26.serp..2.0.0.4b58LRPZoq8[/url]

1.假設n個人要共享秘密S,只要k個人在一起就能重組秘密。
2.設定秘密S。
3.取\( C_{k-1}^n \)個不同的質數\( p_i \),\( 1 \le i \le C_{k-1}^n \)。
4.將每個質數分配給\( k-1 \)個人。
5.將分配的質數相乘,再乘上秘密S,為各使用者所屬的子秘密\( V_i \),\( 1 \le i \le n \)
6.現在有k個人聚在一起要重組秘密S
 \( V_{i1},V_{i2},\ldots,V_{ik} \)
7.計算最大公因數得到秘密S。



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

1.假設有n=5個人要共享秘密S=451,只要有k=3個人就能重組秘密。
2.取\( C_2^5=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[align=center][table=80%][tr][td=3,1]子秘密\( V_i \)[/td][td]秘密S[/td][td]\( p_1 \)[/td][td]\( p_2 \)[/td][td]\( p_3 \)[/td][td]\( p_4 \)[/td][td]\( p_5 \)[/td][td]\( p_6 \)[/td][td]\( p_7 \)[/td][td]\( p_8 \)[/td][td]\( p_9 \)[/td][td]\( p_{10} \)[/td][/tr]
[tr][td]\( V_1 \)[/td][td=2,1]14293994[/td][td]451[/td][td]2[/td][td] [/td][td] [/td][td] [/td][td]13[/td][td]23[/td][td]  [/td][td]  [/td][td]53[/td][td][/td][/tr]
[tr][td]\( V_2 \)[/td][td=2,1]5117046[/td][td]451[/td][td]2[/td][td]3[/td][td] [/td][td] [/td][td]  [/td][td]  [/td][td]31[/td][td]  [/td][td]  [/td][td]61[/td][/tr]
[tr][td]\( V_3 \)[/td][td=2,1]7312956[/td][td]451[/td][td][/td][td]3[/td][td]5[/td][td] [/td][td]  [/td][td]23[/td][td]  [/td][td]47[/td][td]  [/td][td][/td][/tr]
[tr][td]\( V_4 \)[/td][td=2,1]25934755[/td][td]451[/td][td][/td][td] [/td][td]5[/td][td]7[/td][td]  [/td][td]  [/td][td]31[/td][td]  [/td][td]53[/td][td][/td][/tr]
[tr][td]\( V_5 \)[/td][td=2,1]117664547[/td][td]451[/td][td][/td][td] [/td][td] [/td][td]7[/td][td]13[/td][td]  [/td][td]  [/td][td]47[/td][td]  [/td][td]61[/td][/tr]
[/table][/align]
4.將分配的質數相乘,再乘上秘密S,為各使用者所屬的子秘密
 \( V_1=451 \times 2 \times 13 \times 23 \times 53=14293994 \)
 \( V_2=451 \times 2 \times 3 \times 31 \times 61=5117046 \)
 \( V_3=451 \times 3 \times 5 \times 23 \times 47=7312965 \)
 \( V_4=451 \times 5 \times 7 \times 31 \times 53=25934755 \)
 \( V_5=451 \times 7 \times 13 \times 47 \times 61=117664547 \)
5.假設有\( V_1,V_3,V_4 \)聚在一起要重組秘密
 \( V_1=14293994,V_3=7312965,V_4=25934755 \)
6.計算最大公因數得到當初設定的秘密S
 \( GCD(V_1,V_3,V_4)=451 \)


[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:5;
k:3;[/color]
[color=red](%o1)[/color] 5
[color=red](%o2)[/color] 3

[color=green]設定秘密S[/color]
[color=red](%i3)[/color] [color=blue]S:451;[/color]
[color=red](%o3)[/color] 451

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

[color=green]設定質數要給哪一個使用者
P1給V1,V2
P2給V2,V3
P3給V3,V4
...[/color]
[color=red](%i5)[/color] [color=blue]User:[[1,2],[2,3],[3,4],[4,5],[1,5],[1,3],[2,4],[3,5],[1,4],[2,5]];[/color]
[color=red](%o5)[/color] \( [[1,2],[2,3],[3,4],[4,5],[1,5],[1,3],[2,4],[3
,5],[1,4],[2,5]] \)

[color=green]將分配到的質數和秘密S乘起來當作子秘密Vi[/color]
[color=red](%i6)[/color]
[color=blue]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;[/color]
[color=red](%o8)[/color] \( [14293994,5117046,7312965,25934755,117664547] \)

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

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

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

bugmens 發表於 2013-9-8 07:29

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

[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:7;
k:5;[/color]
[color=red](%o1)[/color] 7
[color=red](%o2)[/color] 5

[color=green]設定秘密S[/color]
[color=red](%i3)[/color] [color=blue]S:12345;[/color]
[color=red](%o3)[/color] 12345

[color=green]任意取C(n,k-1)個質數[/color]
[color=red](%i4)[/color]
[color=blue]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;[/color]
[color=red](%o7)[/color] \( [97,157,251,347,379,557,1381,1889,3217,3527,3557,3989,4111,5381,5743,6089,6217,6547,6619,6701, \)
\( 6883,8443,8501,8527,8779,8893,9371,10007,10079,10357,10391,10459,11239,12097,12323] \)

[color=green]設定質數要給哪一位使用者
P1給V1,V2,V3,V4
P2給V1,V2,V3,V5
P3給V1,V2,V3,V6
...[/color]
[color=red](%i8)[/color]
[color=blue]create_list(i,i,1,n)$
setify(%)$
powerset(%,k-1)$
User:full_listify(%);[/color]
[color=red](%o11)[/color] \( [[1,2,3,4],[1,2,3,5],[1,2,3,6],[1,2,3,7],[1,2,4,5],[1,2,4,6],[1,2,4,7],\)
\( [1,2,5,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,3,4,6],[1,3,4,7],[1,3,5,6], \)
\( [1,3,5,7],[1,3,6,7],[1,4,5,6],[1,4,5,7],[1,4,6,7],[1,5,6,7],[2,3,4,5], \)
\( [2,3,4,6],[2,3,4,7],[2,3,5,6],[2,3,5,7],[2,3,6,7],[2,4,5,6],[2,4,5,7], \)
\( [2,4,6,7],[2,5,6,7],[3,4,5,6],[3,4,5,7],[3,4,6,7],[3,5,6,7],[4,5,6,7]] \)

[color=green]將分配到的質數和秘密S乘起來當作子秘密Vi[/color]
[color=red](%i12)[/color]
[color=blue]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;[/color]
[color=red](%o14)[/color]
\( [2027405439656203402483392037741077832451907091735220768078908930690305, \)
\( 329395512180772665716441437042961317833047447165674231176372701471582355, \)
\( 873365187527948903078917971136893483135753791078025669159186590065120719495, \)
\( 38557189090206618525408472635427757365514394529139189207988367527928662521235, \)
\( 1085040646795903444837598300544056739255857225025230153016414858410402872064055, \)
\( 4518571371143044485194989367493800863732546105787200385445314138550958905680685, \)
\( 34041447391883330084505313814699077342455987346908316001305119644995002433655445] \)

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

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

bugmens 發表於 2013-9-22 13:45

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

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


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


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


接下來我以論文所舉的例子為例
1.假設\( k=3 \)個人要共享\( 2^k-1=7 \)個質數( \( {p_1,p_2,p_3,p_4,p_5,p_6,p_7} \) )
2.計算每個人會拿到的子秘密\( s_i \)
 \( s_1=p_4p_5p_6p_7 \),\( s_2=p_2p_3p_6p_7 \),\( s_3=p_1p_3p_5p_7  \)
[table=80%][tr][td]整數 j[/td][td]二進位[/td][td]\( i=1 \)[/td][td]\( i=2 \)[/td][td]\( i=3 \)[/td][td=2,1]集合\( S_j \)[/td][/tr]
[tr][td]1[/td][td]001[/td][td]\( B(1,1)=0 \)[/td][td]\( B(1,2)=0 \)[/td][td]\( B(1,3)=1 \)[/td][td=2,1]\( S_1=\{\; s_3 \}\; \)[/td][/tr]
[tr][td]2[/td][td]010[/td][td]\( B(2,1)=0 \)[/td][td]\( B(2,2)=1 \)[/td][td]\( B(2,3)=0 \)[/td][td=2,1]\( S_2=\{\; s_2 \}\; \)[/td][/tr]
[tr][td]3[/td][td]011[/td][td]\( B(3,1)=0 \)[/td][td]\( B(3,2)=1 \)[/td][td]\( B(3,3)=1 \)[/td][td=2,1]\( S_3=\{\; s_2,s_3 \}\; \)[/td][/tr]
[tr][td]4[/td][td]100[/td][td]\( B(4,1)=1 \)[/td][td]\( B(4,2)=0 \)[/td][td]\( B(4,3)=0 \)[/td][td=2,1]\( S_4=\{\; s_1 \}\; \)[/td][/tr]
[tr][td]5[/td][td]101[/td][td]\( B(5,1)=1 \)[/td][td]\( B(5,2)=0 \)[/td][td]\( B(5,3)=1 \)[/td][td=2,1]\( S_5=\{\; s_1,s_3 \}\; \)[/td][/tr]
[tr][td]6[/td][td]110[/td][td]\( B(6,1)=1 \)[/td][td]\( B(6,2)=1 \)[/td][td]\( B(6,3)=0 \)[/td][td=2,1]\( S_6=\{\; s_1,s_2 \}\; \)[/td][/tr]
[tr][td]7[/td][td]111[/td][td]\( B(7,1)=1 \)[/td][td]\( B(7,2)=1 \)[/td][td]\( B(7,3)=1 \)[/td][td=2,1]\( S_7=\{\; s_1,s_2,s_3 \}\; \)[/td][/tr]
[tr][td] [/td][td] [/td][td]使用者1
拿到質數
\( s_1=p_4p_5p_6p_7 \)[/td][td]使用者2
拿到質數
\( s_2=p_2p_3p_6p_7 \)[/td][td]使用者3
拿到質數
\( s_3=p_1p_3p_5p_7 \)[/td][/tr][/table]
3..當全部的人聚在一起要重組秘密時,對每個j值將\( B(j,i)=1 \)的\( s_i \)收集起來形成集合\( S_j \)
 \( S_1=\{\; s_3 \}\; \),\( S_2=\{\; s_2 \}\; \),\( S_3=\{\; s_2,s_3 \}\; \),\( S_4=\{\; s_1 \}\; \),\( S_5=\{\; s_1,s_3 \}\; \),\( S_6=\{\; s_1,s_2 \}\; \),\( S_7=\{\; s_1,s_2,s_3 \}\; \)
4.按照集合\( S_j \)的元素多寡遞減排序得到新的集合\( S_{\sigma j} \)
 \( S_{\sigma 1}=\{\; s_1,s_2,s_3 \}\; \),\( S_{\sigma 2}=\{\; s_1,s_2 \}\; \),\( S_{\sigma 3}=\{\; s_1,s_3 \}\; \),\( S_{\sigma 4}=\{\; s_2,s_3 \}\; \),\( S_{\sigma 5}=\{\; s_1 \}\; \),\( S_{\sigma 6}=\{\; s_2 \}\; \),\( S_{\sigma 7}=\{\; s_3 \}\; \)

5.對每個集合\( S_{\sigma j} \)的所有元素求最大公因數就可以得到某個質數\( p_{\sigma j} \)
6.將集合\( S_{\sigma j} \)中有出現\( p_{\sigma j} \)都除掉
7.回到步驟5再處理下一個集合\( S_{\sigma j+1} \),直到所有質數都被回復為止。
 \( GCD(s_1,s_2,s_3)=GCD(p_4p_5p_6p_7 , p_2p_3p_6p_7 , p_1p_3p_5p_7)=p_7 \)
 同除\( p_7 \),得\( s_1=p_4p_5p_6 \) , \( s_2=p_2p_3p_6 \) , \( s_3=p_1p_3p_5 \)

 \( GCD(s_1,s_2)=GCD(p_4p_5p_6 , p_2p_3p_6)=p_6 \)
 同除\( p_6 \),得\( s_1=p_4p_5 \) , \( s_2=p_2p_3 \) , \( s_3=p_1p_3p_5 \)

 \( GCD(s_1,s_3)=GCD(p_4p_5 , p_1p_3p_5)=p_5 \)
 同除\( p_5 \),得\( s_1=p_4 \) , \( s_2=p_2p_3 \) , \( s_3=p_1p_3 \)

 \( GCD(s_2,s_3)=GCD(p_2p_3 , p_1p_3)=p_3 \)
 同除\( p_3 \),得\( s_1=p_4 \) , \( s_2=p_2 \) , \( s_3=p_1 \)

 \( GCD(s_1)=GCD(p_4)=p_4 \)
 同除\( p_4 \),得\( 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 \)



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

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

[color=green]將B函數回傳值為1所對應的質數pj收集起來形成子秘密si[/color]
[color=red](%i3)[/color]
[color=blue]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);[/color]
[color=red](%o3)[/color] \( \displaystyle s(i) :=\prod_{j=1}^{2^k-1}\) if \( B(j,1)=1 \) then \( p_j \) else 1
[color=red](%o4)[/color] \( [p_4p_5p_6p_7 , p_2p_3p_6p_7 , p_1p_3p_5p_7] \)

[color=green]當全部的人聚在一起要重組秘密時,
對每個j值將B(j,i)=1的si收集起來形成集合S_j[/color]
[color=red](%i5)[/color]
[color=blue]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;[/color]
[color=red](%o7)[/color] \( [ [s_1,s_2,s_3],[s_1,s_2],[s_1,s_3],[s_1],[s_2,s_3],[s_2],[s_3] ] \)

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

[color=green]求出每一組Sj的最大公因數GCD得到質數p
將子秘密s中有出現p的都約掉(程式碼則用subst用1取代掉)
再處理下一組Sj[/color]
[color=red](%i9)[/color]
[color=blue]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)
)$[/color]
從\( [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 \)

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

bugmens 發表於 2013-11-2 22:27

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}] \)



[color=green]設定在F2底下運算[/color]
[color=red](%i1)[/color] [color=blue]modulus:2;[/color]
[color=red](%o1)[/color] 2

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

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

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

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

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

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

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

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

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

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

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

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

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

bugmens 發表於 2013-11-17 22:51

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

[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:4;
k:3;[/color]
[color=red](%o1)[/color] 4
[color=red](%o2)[/color] 3

[color=green]設定秘密S[/color]
[color=red](%i3)[/color] [color=blue]S:12345;[/color]
[color=red](%o3)[/color] 12345

[color=green]約定在Fp底下運算[/color]
[color=red](%i4)[/color]
[color=blue]p:7;
modulus:p;[/color]
[color=red](%o4)[/color] 7
[color=red](%o5)[/color] 7

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

[color=green]S轉換後的長度設為t[/color]
[color=red](%i7)[/color] [color=blue]t:length(S_Base_p);[/color]
[color=red](%o7)[/color] 5

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

[color=green]先產生A0矩陣[/color]
[color=red](%i9)[/color] [color=blue]A[0];[/color]
[color=red](%o9)[/color] \( \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] \)

[color=green]根據S和A0來產生對應的U矩陣
步驟1:假設U矩陣有kt個未知數[/color]
[color=red](%i10)[/color] [color=blue]U:create_list(x[ i ],i,1,k*t);[/color]
[color=red](%o10)[/color] \( [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}] \)

[color=green]步驟2:矩陣方程式S=U.A0
(maxima用.代表矩陣乘法)[/color]
[color=red](%i11)[/color] [color=blue]matrix(U).A[0]-matrix(S_Base_p);[/color]
[color=red](%o11)[/color] \( \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]} \)

[color=green]步驟3:得到無限多組的解答
%r1,%r2,...為參數[/color]
[color=red](%i12)[/color] [color=blue]solution:solve(%[1],U);[/color]
[color=red](%o12)[/color] \( \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]]} \)

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

[color=green]步驟5:將參數代入得到一組解[/color]
[color=red](%i14)[/color] [color=blue]solution:rat(ev(solution,variable));[/color]
[color=red](%o14)/R/[/color] \( [[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]] \)

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

[color=green]產生A1~An矩陣,將A0,A1~An公開[/color]
[color=red](%i16)[/color] [color=blue]create_list(A[ i ],i,1,n);[/color]
[color=red](%o16)[/color] \( \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] \)

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

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

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

[color=green]將對應的Ai矩陣組成matrixA方陣[/color]
[color=red](%i22)[/color] [color=blue]matrixA:addcol(A[1],A[3],A[4]);[/color]
[color=red](%o22)[/color] \( \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] \)

[color=green]求matrixA的反矩陣[/color]
[color=red](%i23)[/color] [color=blue]inv_A:rat(invert(matrixA));[/color]
[color=red](%o23)/R/[/color] \( \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] \)

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

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

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

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

bugmens 發表於 2013-12-7 09:04

這個方案是基於向量空間的外積,詳細內容請見
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年逝世,以下為紀念影片。
[url]https://www.youtube.com/watch?v=lfQltpzoMC8[/url]


定義:\( 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 \)。


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

[color=green]隨機選取2個列向量V1,V2[/color]
[color=red](%i2)[/color]
[color=blue]V1:[1,2,3];
V2:[4,5,6];[/color]
[color=red](%o2)[/color] \( [1,2,3] \)
[color=red](%o3)[/color] \( [4,5,6] \)

[color=green]V1,V2外積得到向量U[/color]
[color=red](%i4)[/color] [color=blue]U:express(V1~V2);[/color]
[color=red](%o4)[/color] \( [-3,6,-3] \)

[color=green]得到秘密S,並將U的第一個分量公開[/color]
[color=red](%i5)[/color]
[color=blue]h:U[1];
S:abs(U[2])*abs(U[3]);[/color]
[color=red](%o5)[/color] \( -3 \)
[color=red](%o6)[/color] 18

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

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

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

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

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

bugmens 發表於 2013-12-15 12:43

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

[color=green]設定n個人共享秘密,至少要k個人才能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:8;
t:6;[/color]
[color=red](%o1)[/color] 8
[color=red](%o2)[/color] 6

[color=green]隨機產生t列(t+1)行的矩陣V[/color]
[color=red](%i3)[/color] [color=blue]V:genmatrix(lambda([i, j],random(10)),t,t+1);[/color]
[color=red](%o3)[/color] \( \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} \)

[color=green]計算V1,V2,...,Vt的外積U[/color]
[color=red](%i4)[/color]
[color=blue]addrow(V,create_list((-1)^i*ident(t+1)[ i ],i,1,t+1));
U:determinant(%);[/color]
[color=red](%o4)[/color] \( \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]} \)
[color=red](%o5)[/color] \( [-23496,1488,28440,17232,42288,24960,-13536] \)

[color=green]公開U的第一個分量u1,其餘分量不公開[/color]
[color=red](%i6)[/color] [color=blue]u1:U[1];[/color]
[color=red](%o6)[/color] -23496

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

[color=green]隨機選取n列t行的矩陣A[/color]
[color=red](%i8)[/color] [color=blue]A:genmatrix(lambda([i,j],random(10)),n,t);[/color]
[color=red](%o8)[/color] \( \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} \)


[color=green]將A矩陣和V矩陣相乘得到子秘密s
將每一列s[ i ]分派給這n個人[/color]
[color=red](%i9)[/color] [color=blue]s:A.V;[/color]
[color=red](%o9)[/color] \( \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} \)

[color=green]假設有t個人聚在一起要重建秘密
將每個人所擁有的子秘密s[ i ]重組成矩陣V[/color]
[color=red](%i10)[/color] [color=blue]V:apply('matrix,rest(random_permutation(args(s)),n-t));[/color]
[color=red](%o10)[/color] \( \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} \)

[color=green]計算V1,V2,...,Vt的外積U[/color]
[color=red](%i11)[/color]
[color=blue]addrow(V,create_list((-1)^i*ident(t+1)[ i ],i,1,t+1));
U:determinant(%);[/color]
[color=red](%o11)[/color] \( \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]} \)
[color=red](%o12)[/color] \( [238719360,-15118080,-288950400,-175077120,-429646080,-253593600,137525760] \)

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

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

bugmens 發表於 2013-12-21 11:21

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} \)


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

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

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

[color=green]約定在Fp底下運算[/color]
[color=red](%i4)[/color]
[color=blue]p:19;
modulus:p;[/color]
[color=red](%o4)[/color] 19
[color=red](%o5)[/color] 19

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

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

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

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

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

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

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

bugmens 發表於 2013-12-26 23:14

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

[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o1)[/color] 8
[color=red](%o2)[/color] 6

[color=green]選擇符合m>2(k-1)-1的m值[/color]
[color=red](%i3)[/color] [color=blue]m:2*(k-1);[/color]
[color=red](%o3)[/color] 10

[color=green]選擇質數p[/color]
[color=red](%i4)[/color]
[color=blue]p:next_prime(m^2);
modulus:p;[/color]
[color=red](%o4)[/color] 101
[color=red](%o5)[/color] 101

[color=green]m*m的秘密矩陣S,這個範例設定的是1~m^2的數字[/color]
[color=red](%i6)[/color] [color=blue]S:genmatrix(lambda([i,j],(i-1)*m+j),m,m);[/color]
[color=red](%o6)[/color] \( \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} \)

[color=green]隨機選取m*k的矩陣A[/color]
[color=red](%i7)[/color] [color=blue]A:genmatrix(lambda([i,j],random(p)),m,k);[/color]
[color=red](%o7)[/color] \( \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} \)

[color=green]隨機選取n個k*1向量x(每一個直行就是一個向量xi)[/color]
[color=red](%i9)[/color] [color=blue]x:genmatrix(lambda([i,j],random(p)),k,n);[/color]
[color=red](%o9)[/color] \( \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} \)

[color=green]A矩陣和x相乘得到子秘密s[/color]
[color=red](%i10)[/color] [color=blue]s:rat(A.x);[/color]
[color=red](%o10)/R/[/color] \( \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} \)

[color=green]將子秘密s分給n個人[/color]
[color=red](%i11)[/color] [color=blue]s:create_list(col(s,i),i,1,n);[/color]
[color=red](%o11)/R/[/color] \( \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} ] \)

[color=green]投影矩陣的副程式[/color]
[color=red](%i12)[/color] [color=blue]proj(M):=rat(M.invert(transpose(M).M).transpose(M));[/color]
[color=red](%o12)[/color] proj(M):=rat(M . invert(transpose(M) . M) . transpose(M))

[color=green]計算矩陣A的投影矩陣[/color]
[color=red](%i13)[/color] [color=blue]projA:proj(A);[/color]
[color=red](%o13)/R/[/color] \( \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} \)

[color=green]計算R=S-projA (mod p),並公開矩陣R[/color]
[color=red](%i14)[/color] [color=blue]R:mod(S-projA,p);[/color]
[color=red](%o14)[/color] \( \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} \)

[color=green]假設有k個人聚在一起要重建秘密[/color]
[color=red](%i15)[/color] [color=blue]rest(random_permutation(s),n-k);[/color]
[color=red](%o15)/R/[/color] \( \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} ] \)

[color=green]將每個人所擁有的子秘密s[ i ]重組成矩陣B[/color]
[color=red](%i16)[/color] [color=blue]B:apply(addcol,%);[/color]
[color=red](%o16)/R/[/color] \( \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} \)

[color=green]計算矩陣B的投影矩陣[/color]
[color=red](%i17)[/color] [color=blue]projB:proj(B);[/color]
[color=red](%o17)/R/[/color] \( \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} \)

[color=green]計算S=projB+R (mod p),得到秘密矩陣S[/color]
[color=red](%i19)[/color] [color=blue]mod(projB+R,p);[/color]
[color=red](%o19)[/color] \( \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} \)

bugmens 發表於 2014-1-30 10:20

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

這個方案是基於線性獨立向量的內積,詳細內容請見
A Novel (t,n) Threshold Secret Sharing Using Dot Product of Linearly Independent Vectors
[url]http://www.ijarcce.com/upload/2013/july/5-SONALI%20PATIL-a%20novel%20t,n%20threshold%20secret%20sharing.pdf[/url]

假設有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  \)


[color=green]有n個人共享秘密,有k個人聚在一起就能重建秘密[/color]
[color=red](%i1)[/color]
[color=blue]n:8;
k:6;[/color]
[color=red](%o1)[/color] 8
[color=red](%o2)[/color] 6

[color=green]設定秘密S[/color]
[color=red](%i3)[/color] [color=blue]S:12345;[/color]
[color=red](%o3)[/color] 12345

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

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

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

[color=green]檢查秘密S是否等於$.X[/color]
[color=red](%i8)[/color] [color=blue]is(S=Dollar.X);[/color]
[color=red](%o8)[/color] true

[color=green]產生k*n的Vandermode矩陣Y[/color]
[color=red](%i9)[/color] [color=blue]Y:genmatrix(lambda([i,j],j^i),k,n);[/color]
[color=red](%o9)[/color] \( \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} \)

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

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

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

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

[color=green]取出各si的第二個值,形成k*k的Vandermode矩陣Y[/color]
[color=red](%i15)[/color] [color=blue]Y:genmatrix(lambda([i,j],s[j][2]^i),k,k);[/color]
[color=red](%o15)[/color] \( \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} \)

[color=green]計算矩陣Y的反方陣[/color]
[color=red](%i16)[/color] [color=blue]inv_Y:invert(Y);[/color]
[color=red](%o16)[/color] \( \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} } \)

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

[color=green]將$矩陣再和公開的X相乘得到秘密S[/color]
[color=red](%i18)[/color] [color=blue]S: Dollar.X;[/color]
[color=red](%o18)[/color] 12345

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

頁: [1] 2

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.