21 123
發新話題
打印

用Maxima學密碼學-秘密分享

推到噗浪
推到臉書

用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.楊吳泉,“現代密碼學入門與程式設計”

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

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

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

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

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

TOP

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。

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

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

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

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

(%i3) f(x):=''S+166*x+94*x^2;
(%o3) \( f(x) :=1234+166x+94x^2 \)

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

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

(%i6) ratsimp(%);
(%o6) \( 94x^2+166x+1234 \)

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

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

TOP

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


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

設定秘密S
(這個數字可自行修改,但\( S<p \) )

(%i2) S:12345;
(%o2) 12345

設定在\( F_p \)底下運算,其中p為質數
(%i3)
p:65537;
modulus:p;

(%o3) 65537
(%o4) 65537

設定n個人共享秘密,至少要k個人才能重建秘密
(這兩個數字可自行修改,但\( n \ge k \) )

(%i5)
n:8;
k:6;

(%o5) 8
(%o6) 6

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

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

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

假設有k個人聚在一起要重建秘密
(%i10)
random_permutation(%)$
create_list(%[ i ],i,1,k);

(%o11)/R/ [[8,4956],[4,-16004],[1,2233],[7,-6651],[3,16789],[2,-16387]]

利用拉格朗日插值多項式計算通過這k個點座標的k-1次多項式
(%i12) lagrange(%);
(%o12) \( \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} \)

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

若結果出現分數,但在Fp底下運算
則秘密\( S=分子*分母^{-1} \pmod{p} \)

(%i14) ratsimp(%);
(%o14) 12345

TOP

這次我用另一種方法解出秘密S

設方程式\( a_0+a_1x+a_2x^2+\ldots+a_{k-1}x^{k-1}\equiv y \pmod{p} \)
通過\( (x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k) \)共k個點
將這k個點坐標代入方程式得到
\( a_0+a_1 x_1+a_2 x_1^2+\ldots+a_{k-1}x_1^{k-1} \equiv y_1 \pmod{p} \)
\( a_0+a_1 x_2+a_2 x_2^2+\ldots+a_{k-1}x_2^{k-1} \equiv y_2 \pmod{p} \)

\( a_0+a_1 x_k+a_2 x_k^2+\ldots+a_{k-1}x_k^{k-1} \equiv y_k \pmod{p} \)
改寫成矩陣形式
\( \displaystyle \pmatrix{
1 & x_1 & x_1^2 & \ldots & x_1^{k-1} \cr
1 & x_2 & x_2^2 & \ldots & x_2^{k-1} \cr
\vdots & \vdots & \vdots & \ddots & \vdots \cr
1 & x_k & x_k^2 & \ldots & x_k^{k-1}}  
\pmatrix{a_0 \cr a_1 \cr a_2 \cr \vdots \cr a_{k-1}} \equiv
\pmatrix{y_1 \cr y_2 \cr y_3 \cr \vdots \cr y_k} \pmod{p} \)
上面最左邊的矩陣稱為Vandermonde矩陣
http://en.wikipedia.org/wiki/Vandermonde_matrix
其行列式\( \displaystyle det(V)=\prod_{1 \le i<j \le k}(x_j-x_i) \)
因為\( x_i \ne x_j \),\( i \ne j \),所以行列式值不為0,代表整個聯立方程組有唯一解
其中常數項\( a_0 \)就是當初設定的秘密S


例子
設方程式\( a_0+a_1x+a_2x^2+\ldots+a_5x^5 \equiv y \pmod{65537} \)
通過\( (8,4956),(4,-16004),(1,2233),(7,-6651),(3,16789),(2,-16387) \)共6個點
建立聯立方程組的矩陣形式
\( \displaystyle \pmatrix{
1 & 8^1 & 8^2 & 8^3 & 8^4 & 8^5 \cr
1 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 \cr
1 & 1^1 & 1^2 & 1^3 & 1^4 & 1^5 \cr
1 & 7^1 & 7^2 & 7^3 & 7^4 & 7^5 \cr
1 & 3^1 & 3^2 & 3^3 & 3^4 & 3^5 \cr
1 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5}
\pmatrix{a_0 \cr a_1 \cr a_2 \cr a_3 \cr a_4 \cr a_5} \equiv
\pmatrix{4956 \cr -16004 \cr 2233 \cr -6651 \cr 16789 \cr -16387} \pmod{65537} \)
解出唯一解
\( \displaystyle \pmatrix{a_0 \cr a_1 \cr a_2 \cr a_3 \cr a_4 \cr a_5} \equiv
\pmatrix{-\frac{181843183}{315} \cr -\frac{3946562}{63} \cr \frac{9579461}{126} \cr -\frac{938557}{36} \cr \frac{107371}{30} \cr -\frac{2057}{12}} \equiv
\pmatrix{-181843183 \times 315^{-1} \cr -3946562 \times 63^{-1} \cr 9579461 \times 126^{-1} \cr -938557 \times 36^{-1} \cr 107371 \times 30^{-1} \cr -2057 \times 12^{-1}} \equiv
\pmatrix{12345 \cr -5429 \cr 31816 \cr 4877 \cr 18871 \cr 5290} \pmod{65537} \)
當初的多項式函數\( f(x)=12345-5429x+31816x^2+4877x^3+18871x^4+5290x^5 \)
其中常數項就是秘密\( S=12345 \)


設定秘密S
(這個數字可自行修改,但\( S<p \) )

(%i1) S:12345;
(%o1) 12345

設定在\( F_p \)底下運算,其中p為質數
(%i2)
p:65537;
modulus:p;

(%o2) 65537
(%o3) 65537

設定n個人共享秘密,至少要k個人才能重建秘密
(這兩個數字可自行修改,但\( n \ge k \) )

(%i4)
n:8;
k:6;

(%o4) 8
(%o5) 6

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

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

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

假設有k個人聚在一起要重建秘密
(%i9)
random_permutation(%)$
shadows:create_list(%[ i ],i,1,k);

(%o10)/R/ [[8,4956],[4,-16004],[1,2233],[7,-6651],[3,16789],[2,-16387]]

建立\( x_i \)的係數矩陣
(%i11) genmatrix (lambda([ i, j],shadows[ i ][1]^j), k, k-1,1,0);
(%o11)/R/ \( \displaystyle \pmatrix{
1 & 8 & 64 & 512 & 4096 & 32768 \cr
1 & 4 & 16 & 64 & 256 & 1024 \cr
1 & 1 & 1 & 1 & 1 & 1 \cr
1 & 7 & 49 & 343 & 2401 & 16807 \cr
1 & 3 & 9 & 27 & 81 & 243 \cr
1 & 2 & 4 & 8 & 16 & 32} \)

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

解出未知數\( a_0,a_1,a_2,a_3,a_4,a_5 \)
(%i13) linsolve_by_lu(%o11,%o12);
(%o13) \( \displaystyle [ \pmatrix{
-\frac{181843183}{315} \cr -\frac{3946562}{63} \cr \frac{9579461}{126} \cr -\frac{938557}{36} \cr \frac{107371}{30} \cr -\frac{2057}{12}},false] \)

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

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

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

TOP

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

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


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

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


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

設定顯示順序為x,y,z
  預設順序為z,y,x

(%i2) powerdisp:true;
(%o2) true

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

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

(%o4) 65537
(%o5) 65537

假設全部的平面的交點在(x0,y0,z0)
其中x0為秘密S,y0,z0為任意數字

(%i6)
x0:S;
y0:random(p);
z0:random(p);

(%o6) 12345
(%o7) 60108
(%o8) 31816

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

產生n個平面方程式ax+by+cz=d,其中a,b,c為任意數字
將(x0,y0,z0)代入平面方程式後得到常數項d

(%i10)
planes:[]$
for k:1 thru n do
  (a:random(p),
   b:random(p),
   c:random(p),
   d:rat(a*x0+b*y0+c*z0),
   push(a*x+b*y+c*z=d,planes)
  )$
planes;

(%o12)/R/ \( \matrix{[ 6093 x+63576 y+58177 z=8825, \cr
57696 x+31204 y+13769 z=-32708, \cr
6671 x+24953 y+40161 z=21652 , \cr
43481 x+47688 y+20331 z=-1181, \cr
49113 x+5683 y+30540 z=-24341, \cr
4877 x+18871 y+5290 z=-30642]} \)

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

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

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

TOP

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

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


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

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

其中\( x_1=12345 \)就是秘密S


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

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

(%o2) 65537
(%o3) 65537

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

(%o4) 8
(%o5) 6

假設全部平面的交點(x1,x2,x3,x4,x5,x6)
其中x1=S,X2,X3,X4,X5,X6為任意數字

(%i6) matrixX:genmatrix(lambda([i,j],if i=1 then S else random(p)),k,1);
(%o6) \( \displaystyle \pmatrix{12345 \cr 60108 \cr 31816 \cr 4877 \cr 18871 \cr 5290} \)

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

矩陣A和交點坐標相乘得到超平面方程式的常數項(矩陣B)
A.X=B

(%i8) matrixB:rat(matrixA.matrixX);
(%o8)/R/ \( \displaystyle \pmatrix{-8762 \cr 16308 \cr 17725 \cr 19053 \cr -18298 \cr 8396 \cr 20957 \cr -20354} \)

將這n個超平面方程式分派給n個人
(%i9)
transpose(append(transpose(matrixA),transpose(matrixB)))$
create_list(%[ i ],i,1,n);

(%o10)/R/   \( \matrix{[[49113,5683,30540,43481,47688,20331,-8762],\cr
[
6671,24953,40161,57696,31204,13769,16308], \cr
[6093,63576,
58177,11336,56130,52284,17725], \cr
[1550,61347,51763,6103,
56842,24958,19053], \cr
[54066,34186,31828,8249,23728,47682,-
18298], \cr
[58433,20124,62414,22027,34969,63343,-8396], \cr
[
16502,23915,26371,45158,30220,16212,20957], \cr
[58810,59547,
21555,32712,20787,12223,-20354]]} \)

其中k個人聚在一起要重組秘密S
(%i11)
random_permutation(%)$
shadows:apply('matrix,rest(%,n-k));

(%o12)/R/ \( \displaystyle \pmatrix{
6093 & 63576 & 58177 & 11336 & 56130 & 52284 & 17725 \cr
54066 & 34186 & 31828 & 8249 & 23728 & 47682 & -18298 \cr
58810 & 59547 & 21555 & 32712 & 20787 & 12223 & -20354 \cr
49113 & 5683 & 30540 & 43481 & 47688 & 20331 & -8762 \cr
58433 & 20124 & 62414 & 22027 & 34969 & 63343 & -8396 \cr
6671 & 24953 & 40161 & 57696 & 31204 & 13769 & 16308} \)

求出k個超平面方程式的交點坐標
(%i13)
A:submatrix(shadows,k+1)$
B:col(shadows,k+1)$
linsolve_by_lu(A,B);

(%o15) \( \displaystyle [ \pmatrix{
-\frac{239491479314553105644042475017644464141348447204156669689205637453765303376528277604}
{216396336661829004078184209560598894913754528761549337466792501379219596480279330621} \cr   \cr
\frac{1210805713819882573289422222280783600688940179592831917819578082169049120990916334350266}
{19113321079899398891561301316928566622410951815332061591718561061341473390034415245174541} \cr   \cr
-\frac{37644552818254310466065473507177075951008884574753786958432937812591617153278450}
{106546694565154605651493948577350514482400063398104055867450763849935793441791891} \cr   \cr
\frac{63479880358930370859878647750293235168149198063790494688930192308562}
{66968254011130256410216439253313699375179209442652365784366974851833} \cr   \cr
-\frac{11513040138995712259570392386228043283995950153230}
{22465424471730794622726083901131483083365892339583} \cr   \cr
\frac{549677002877614509907708808}{851081629302730915840058149}},false] \)

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

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

TOP

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

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

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


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


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

(%o1) 4
(%o2) 3

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

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

計算m(n-k+2)*m(n-k+3)*...*m(n)
  m(1)*m(2)*...*m(k)

(%i5)
product1:product(m[ i ],i,n-k+2,n);
product2:product(m[ i ],i,1,k);

(%o5) 99
(%o6) 504

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

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

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

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

TOP

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


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

(%o1) 8
(%o2) 6

找出符合m(n-k+2)*m(n-k+3)*...*m(n) < m(1)*m(2)*...*m(k)的遞增數列m
為了方便數列m都採用質數,其中任兩個數字一定互質

(%i3)
found:false$
while found=false do
  (m:create_list(next_prime(random(50)),i,1,n),
   m:unique(m),
   if length(m)=n then
     (m:sort(m),
      product1:product(m[ i ],i,n-k+2,n),
      product2:product(m[ i ],i,1,k),
      if product1<product2 then
        found:true
     )
  )$
m;

(%o5) \( [11,17,19,29,31,37,41,53] \)

m(n-k+2)*m(n-k+3)*...*m(n)的乘積為product1
   m(1)*m(2)*...*m(k)的乘積為product2

(%i6)
product1;
product2;

(%o6) 72280499
(%o7) 118183439

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

按照Mignotte方案,秘密S要落在這二個數字之間
但我故意找比較小的S最後也能得到答案,原因我還不清楚

(%i9) is(product1<S and S<product2);
(%o9) false

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

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

其中k個人聚在一起要重組秘密S
(%i12)
random_permutation(%)$
shadows:rest(%,n-k);

(%o13) \( [ [3,17],[4,41],[20,29],[49,53],[24,37],[14,19] ] \)

利用中國剩餘定理求出秘密S
(%i14)
s:makelist(shadows[ i ][1],i,1,k);
m:makelist(shadows[ i ][2],i,1,k);
chinese(s,m);

(%o14) \( [3,4,20,49,24,14] \)
(%o15) \( [17,41,29,53,37,19] \)
(%o16) 12345

TOP

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

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

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


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



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

(%o1) 4
(%o2) 3

任選n項的遞增數列
(maxima的list是從1開始數,所以將m0獨立出來)

(%i3)
m0:3;
m:[11,13,17,19];

(%o3) 3
(%o4) \( [11,13,17,19] \)

計算m(0)*m(n-k+2)*m(n-k+3)*...*m(n)
  m(1)*m(2)*...*m(k)

(%i5)
product1:m0*product(m[ i ],i,n-k+2,n);
product2:product(m[ i ],i,1,k);

(%o5) 969
(%o6) 2431

檢查m(0)*m(n-k+2)*m(n-k+3)*...*m(n)是否小於
  m(1)*m(2)*...*m(k)

(%i7) is(product1 < product2);
(%o7) true

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

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

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

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

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

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

(%o14) 2

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

TOP

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


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

(%o1) 8
(%o2) 6

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

找出符合S<m0和
m(0)*m(n-k+2)*m(n-k+3)*...*m(n) < m(1)*m(2)*...*m(k)的遞增數列m
為了方便,數列m都採用質數,其中任兩個數字一定互質
(maxima的list是從1開始數,所以將m0獨立出來)

(%i4)
found:false$
while found=false do
  (m0:next_prime(S+random(S)),
   m:create_list(next_prime(m0+random(S)),i,1,n),
   m:unique(m),
   if length(m)=n then
     (m:sort(m),
      product1:m0*product(m[ i ],i,n-k+2,n),
      product2:product(m[ i ],i,1,k),
      if product1<product2 then
        found:true
     )
  )$
m0;
m;

(%o6) 14843
(%o7) \( [20857,21163,22871,23399,24439,24469,25409,26209] \)

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

(%o10) 2664

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

其中k個人聚在一起要重組秘密S
(%i12)
random_permutation(%)$
shadows:rest(%,n-k);

(%o13) \( [[4716,26209],[11795,24439],[17693,25409],[9787,23399],[9225,20857],[450,21163]] \)

利用中國剩餘定理求出秘密S
(%i14)
s:makelist(shadows[ i ][1],i,1,k);
m:makelist(shadows[ i ][2],i,1,k);
S:chinese(s,m);

(%o14) \( [4716,11795,17693,9787,9225,450] \)
(%o15) \( [26209,24439,25409,23399,20857,21163] \)
(%o16) 39554097

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

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

TOP

 21 123
發新話題