Math Pro 數學補給站

標題: 用Maxima學密碼學－秘密分享 [打印本頁]

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

秘密分享技術與應用
連結已失效h ttp://www.cis.nctu.edu.tw/~ippr/Doc/Dec88/4.doc

機密共享機制
連結已失效h ttp://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

門檻式簽章之介紹
連結已失效h ttp://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

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

作者: 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。

以下的範例出自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

作者: bugmens 時間: 2013-4-21 20:20

延續上一篇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

作者: 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矩陣
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} $
解出唯一解
$ \pmatrix{a_0 \cr a_1 \cr a_2 \cr a_3 \cr a_4 \cr a_5} \equiv
\pmatrix{\displaystyle -\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)　$ [ \pmatrix{\displaystyle
-\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-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 $

圖來自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-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

設定秘密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)　$ [ \pmatrix{\displaystyle
-\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

作者: bugmens 時間: 2013-7-26 20:50

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] $

有三個人就能重組秘密
114.9.27自MAXIMA5.48.1開始，chinese改名為solve_congruences
(%i9)　solve_congruences([s[1],s[2],s[4]],[m[1],m[2],m[4]]);
(%o9)　123

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

作者: bugmens 時間: 2013-8-2 08:40

延續上一篇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
114.9.27自MAXIMA5.48.1開始，chinese改名為solve_congruences
(%i14)
s:makelist(shadows[ i ][1],i,1,k);
m:makelist(shadows[ i ][2],i,1,k);
solve_congruences(s,m);
(%o14)　$ [3,4,20,49,24,14] $
(%o15)　$ [17,41,29,53,37,19] $
(%o16)　12345

作者: bugmens 時間: 2013-8-17 20:32

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] $

有三個人就能重組秘密
114.9.27自MAXIMA5.48.1開始，chinese改名為solve_congruences
(%i13)
solve_congruences([s[1],s[2],s[3]],[m[1],m[2],m[3]])$
S:mod(%,m0);
(%o14)　2

作者: bugmens 時間: 2013-8-20 12:43

延續上一篇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
114.9.27自MAXIMA5.48.1開始，chinese改名為solve_congruences
(%i14)
s:makelist(shadows[ i ][1],i,1,k);
m:makelist(shadows[ i ][2],i,1,k);
S:solve_congruences(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-31 10:46

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

這個方案是基於質因數分解，詳細內容請見
钟红山，素数集合秘密共享方案
連結已失效h ttps://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

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

子秘密$ V_i $ 秘密S $ p_1 $ $ p_2 $ $ p_3 $ $ p_4 $ $ p_5 $ $ p_6 $ $ p_7 $ $ p_8 $ $ p_9 $ $ p_{10} $

$ V_1 $ 14293994 451 2 13 23       53

$ V_2 $ 5117046 451 2 3       31       61

$ V_3 $ 7312956 451 3 5    23    47

$ V_4 $ 25934755 451 5 7       31    53

$ V_5 $ 117664547 451 7 13       47    61

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 $

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

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

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

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

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

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

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

作者: bugmens 時間: 2013-9-8 07:29

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

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

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

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

設定質數要給哪一位使用者
P1給V1,V2,V3,V4
P2給V1,V2,V3,V5
P3給V1,V2,V3,V6
...
(%i8)
create_list(i,i,1,n)$
setify(%)$
powerset(%,k-1)$
User:full_listify(%);
(%o11)　$ [[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]] $

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

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

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

作者: 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
http://eprint.iacr.org/2012/222.pdf

要特別注意的是這個方案和一般的祕密分享不太一樣
有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 $

整數 j	二進位	$ i=1 $	$ i=2 $	$ i=3 $	集合$ S_j $
1	001	$ B(1,1)=0 $	$ B(1,2)=0 $	$ B(1,3)=1 $	$ S_1=\{\; s_3 \}\; $
2	010	$ B(2,1)=0 $	$ B(2,2)=1 $	$ B(2,3)=0 $	$ S_2=\{\; s_2 \}\; $
3	011	$ B(3,1)=0 $	$ B(3,2)=1 $	$ B(3,3)=1 $	$ S_3=\{\; s_2,s_3 \}\; $
4	100	$ B(4,1)=1 $	$ B(4,2)=0 $	$ B(4,3)=0 $	$ S_4=\{\; s_1 \}\; $
5	101	$ B(5,1)=1 $	$ B(5,2)=0 $	$ B(5,3)=1 $	$ S_5=\{\; s_1,s_3 \}\; $
6	110	$ B(6,1)=1 $	$ B(6,2)=1 $	$ B(6,3)=0 $	$ S_6=\{\; s_1,s_2 \}\; $
7	111	$ B(7,1)=1 $	$ B(7,2)=1 $	$ B(7,3)=1 $	$ S_7=\{\; s_1,s_2,s_3 \}\; $
		使用者1 拿到質數 $ s_1=p_4p_5p_6p_7 $	使用者2 拿到質數 $ s_2=p_2p_3p_6p_7 $	使用者3 拿到質數 $ s_3=p_1p_3p_5p_7 $

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 $

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

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

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

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

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

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

作者: bugmens 時間: 2013-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 \left[ \matrix{1 & 0 \cr 0 & 1 \cr 0 & 0 \cr 0 & 0}\right]\;=[\matrix{1 & 0}] $
5.計算$ s_i=U \times A_i $，$ 1 \le i \le 4 $
　每個人拿到所屬的子秘密$ s_i $，$ 1 \le i \le 4 $
　$ s_1=[\matrix{1 & 0 & 1 & 1}]\times \left[ \matrix{0 & 0 \cr 0 & 0 \cr 1 & 0 \cr 0 & 1}\right] =[\matrix{1 & 1}] $　　　　　　　，　　$ s_2=[\matrix{1 & 0 & 1 & 1}]\times \left[ \matrix{1 & 0 \cr 1 & 1 \cr 1 & 0 \cr 0 & 1}\right]=[\matrix{2 & 1}]=[\matrix{0 & 1}] $

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作者: bugmens 時間: 2013-11-17 22:51

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作者: bugmens 時間: 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年逝世，以下為紀念影片。
連結已失效h ttps://www.youtube.com/watch?v=lfQltpzoMC8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作者: bugmens 時間: 2013-12-15 12:43

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

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

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

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

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

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

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

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

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

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

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

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

作者: 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} $

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

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

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

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

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

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

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

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

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

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

作者: bugmens 時間: 2013-12-26 23:14

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作者: 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
http://www.ijarcce.com/upload/20 ... ecret%20sharing.pdf

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

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

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

例子
有$ n=8 $個人要共享秘密$ S=12345 $，只要有$ k=6 $個人就能重組秘密。
1.隨機選取向量$ X=(12,2,34,85,4,1) $和$ $=(91,29,85,98,3,-37) $
　滿足$ S=12 \times 91+2 \times 29+34 \times 85+85 \times 98+4 \times 3+1 \times (-37)=12345 $
2.選取Vandermode矩陣$ \displaystyle Y=\pmatrix{1&2&3&4&5&6&7&8 \cr 1&4&9&16&25&36&49&64 \cr

1&8&27&64&125&216&343&512 \cr 1&16&81&256&625&1296&2401&4096 \cr 1&32&243&1024&3125&7776&16807&32768

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

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

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

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

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

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

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

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

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

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

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

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

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

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

取出各si的第二個值，形成k*k的Vandermode矩陣Y
(%i15)　Y:genmatrix(lambda([i,j],s[j][2]^i),k,k);
(%o15)　$ \displaystyle \pmatrix{3&2&8&6&1&7 \cr 9&4&64&36&1&49 \cr 27&8&512&216&1&343 \cr

81&16&4096&1296&1&2401 \cr 243&32&32768&7776&1&16807 \cr 729&64&262144&46656&1&117649} $

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

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

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

作者: bugmens 時間: 2014-2-22 09:24

錯誤更正碼簡介
https://www.math.sinica.edu.tw/media/pdf/d184/18404.pdf
－－－－－－－－－－－－－－－－－－－－－－－－－－－
數位世界的糾察隊－糾錯編碼的基礎及應用

張耀祖

糾錯編碼能控管數位通信、資料的品質，其理論與組合數學有著密切關係。本文介紹編碼的概念、發展史和應用，並透過實例來了解編碼的操作。

　　能夠交流複雜的資訊是人類建立文明的重要因素之一。隨著人類活動範圍的增大，通信變得越來越重要，如何正確無誤地傳遞訊息自然是極為重要的課題。而在步入數位時代的今天，要保證數位通信、數位影音、資料儲存的品質，靠的就是糾錯編碼！
　　先來看一個簡單的例子：假如在遊覽車上玩一個遊戲，主持人低聲唸幾個數字給坐第一排的同學聽，由他轉告第二排的同學，再由第二排的同學轉告第三排，一直傳到最後一排，再由最後一排的同學報出結果，只要數字一多，就容易出錯。這個例子說明了資訊的傳遞可能會出錯。
　　有些錯誤影響並不大，可有些情況卻不允許出錯，例如在外太空執行任務之無人飛行器的遙控訊號，就不允許有任何錯誤。在錯誤無法避免的情況下，如何正確地傳達指令？這就靠編碼來保證了！
　　現在再來看一個編碼的例子：某一年的北區大學博覽會，有資訊相關公司參展，並在會場贈送精美紀念品。有一位同學為了換紀念品，填寫了好幾份問卷，由於問卷上必須填寫身分證號碼，這位同學寫了自己的號碼，以及只換了最後一個數字的連號，他相信那些號碼都是正確而有效的號碼。
　　了解身分證號碼的編碼規則就知道，不可能有連號的情形。身分證號碼的最後一個數字是「檢查碼」(check digit)，是經由前面的英文字母和數字透過公式所產生的。只要檢驗該公式，就可以知道輸入的身分證號碼是否有效。因此，沒有檢查碼的英文字和數字就足以代表個人，檢查碼則是為了偵測整組號碼是否有效，才加上去的。這種加上檢查碼的作法就是「編碼」(coding)。身分證號碼的編碼只能偵測出是否有錯，這樣的編碼稱為「偵錯編碼」(error-detecting coding)。
　　有了偵錯編碼以後，如果收到一組錯誤的資料，而且錯誤數字的數量在某個範圍之內，就可以從收到的資料檢驗出來，只是無法得知錯在哪裡；如果有必要，可要求重新輸入或重新發送。身分證和國際標準書號(international standard book number, ISBN)都屬於這一類。如果想進一步知道錯在哪裡，就須使用「糾錯編碼」(error-correcting coding)。

糾錯編碼的發展史
第一個糾錯碼－漢明碼
　　糾錯編碼的想法始於1950年代，最早提出糾錯編碼的觀念，並建構出第一個糾錯碼的，是美國貝爾實驗室的漢明(Richard Wesley Hamming，圖一A)。
　　在1947年，電腦還是稀有之物，是只有特大型機關才用得起的貴重儀器。當時的電腦是一部多人使用的大型主機，大家透過終端機的鍵盤輸入工作指令，主機執行完再將結果傳回終端機。既然是大家一起用，就有所謂的優先順序，而漢明的使用層級不高，只能斷斷續續地利用各個週末，從家中連線到主機排隊等候。資料傳輸過程難免有錯誤產生，雖然當時也對傳送的資料做編碼保護，但用的是偵錯編碼，只能知道收到的資料是否有錯，一旦發現有錯就不執行而跳過，直接執行下一筆。
　　有一次漢明發覺，等候了幾個星期的工作沒有被執行，十分生氣。擁有數學背景的他開始思考：既然知道資料在傳送過程出了錯，為什麼不將它修正過來？這一氣使他著手從事編碼的改進，因而發展出第一個具有糾錯能力的編碼方法，現稱為漢明碼(Hamming code)。漢明不但創造出第一個糾錯碼，也建構了糾錯編碼理論的基礎，堪稱為糾錯編碼的開山始祖。由於漢明的重要貢獻，國際電子電機工程師學會(Institute of Electrical and Electronics Engineers, IEEE)在1998年設立了漢明獎(Hamming Medal)，而且第一屆得獎人就是漢明本人！
　　漢明雖然在1947年就構造出漢明碼，卻因為申請專利，直到1950年才出版論文。在這之前，資訊理論的創始人薛農(Claude Elwood Shannon，圖一B)，於1948年發表了＜通信的數學原理＞，提出了一個著名的結果，說明每個受到雜訊干擾的通道(Channel)，一定有一個容量，在不超過這個容量的前提下，會有一種編碼方式能正確無誤地傳送資料；也就是說，在接收訊息後能糾正所有在傳遞過程中產生的錯誤，而復原發送方所送出的訊息。但薛農在論文中只證明了糾錯編碼的存在性，並沒有提到如何建構編碼。
　　另一位編碼學者葛雷(Marcel J.E. Golay)，在讀了薛農的論文後受到很大的啟發，於是開始研究糾錯編碼，並在1949年發表全世界第一篇關於糾錯編碼的論文。該篇論文只有半頁多一點，後來被著名學者伯利坎普(Elwyn Ralph Berlekamp，薛農的學生)稱作是「最有價值的一頁論文」。這篇論文當中提到了葛雷碼(Golay code)－－這種編碼法在理論和實際應用上都非常重要，他與組合設計(combinatorial designs)、有限單群(finite simple groups)有著密切的關係。

圖一：糾錯編碼的兩位重要推手。(A)漢明碼的創始人－－漢明；(B)資訊理論的創始人－－薛農。

編碼法百花齊放
　　薛農的<通信的數學原理>為眾路英雄揭開「獵碼行動」的序幕，漢明碼、葛雷碼只是個開端，之後，各式各樣的糾錯編碼便如雨後春筍般，一一冒出頭來。
　　1954年，穆勒(David E. Muller)提出里德-穆勒碼(Reed-Muller code，簡稱RM碼)，不久之後，里德(Irving Stoy Reed)針對該碼提出一個更好的代數構造法，同時也提出一個很好的解碼法。1971年5月30日發射的水手九號(Mariner 9)上，用的就是RM碼，整個任務共將7329張火星的黑白照片傳回地球。
　　1959年的時候，霍昆格姆(Alexis Hocquenghem)以法文發表了一篇論文，提出一類能糾正多個錯誤的碼；而在隔年，玻士(Raja Chandra Bose)和雷喬德赫瑞(Dwijendra Kumar Ray-Chaudhuri)，也以英文發表了一篇結果相似的論文。這個碼後來被稱為BCH碼，是個實用而且重要的碼，被運用在衛星通信和隨身碟等。坡士為組合設計方面的先驅人物之一，而雷喬德赫瑞是他的學生，他們從組合學的觀點來建構編碼，並不令人意外，畢竟組合觀點比代數結構直覺多了。
　　1960年，里德和索羅門(Gustave Solomon)發表了一篇只有五頁的文章，文中提出一類新的糾錯碼，稱為里德-索羅門碼(簡稱RS碼)。RS碼後來被廣泛應用在各個層面，從臥房中的雷射唱片播放機，一直到已離開太陽系的深空探測機(deep space craft)旅行者號。現在的CD、DVD和藍光DVD，甚至是WAP手機、藍芽技術，也都用到了RS碼。
　　1967年，伯利坎普發表了一個非常有效率的解碼演算法，兩年後梅西(James Lee Massey)提出一個等價的硬體版本，這個演算法讓RS碼成為實用上最重要的碼。到現在伯利坎普-梅西演算法仍然是一個非常重要的解碼演算法。
　　最後，還要介紹的是「平方剩餘碼」(quadratic residue code，簡稱QR碼)。平方剩餘碼是由普朗基(Eugene Prange)在1958年所提出的，其中包括了漢明碼和葛雷碼，伯利坎普稱它為「很難解碼的好碼」，且因為它的重要性，幾乎每一本編碼教科書都會提到這個碼。里德在1991年開始致力於解平方剩餘碼，與他的學生張肇健(T. K. Truong)等陸續解出了幾個碼。
　　1995年，張肇健接受義守大學校長的邀請，辭去美國航太總署與南加州大學的工作，來到台灣擔任義守大學電機資訊學院院長，並帶領義守編碼團隊繼續研究平方剩餘碼的解碼，後來成功地解出包括碼長113位以內的所有未解碼，讓義守大學的編碼團隊在國際間打出了名號。
　　由於篇幅的關係，其他重要的碼，如卷積碼(convolutional code)、渦輪碼(turbo code)、LDPC碼(low-density parity check code)等，並不在這裡做介紹。

糾錯編碼的應用
　　糾錯編碼有非常多應用，只要牽涉到數位的，幾乎都會用到糾錯編碼，例如衛星通信、隨身碟、硬碟、手機、無線電話等，這裡我們只舉兩個例子來說明，這兩個例子都用了RS碼。

雷射唱片
　　第一個例子是雷射唱片(compact disc, CD)，CD是第一個使用糾錯編碼的消費性電子產品。
　　不知道讀者家中有沒有傳統的唱片？那種直徑約20~30公分的唱片，不能亂放，亂放容易變形；播放時要小心翼翼，收拿之際也不可掉以輕心，怕一個不小心就刮傷了唱片。刮傷了唱片會怎麼樣？小則在播放時會出現「波」一聲的雜音，大則這一面就此報廢。只是聽個音樂而已，有必要那麼緊張兮兮嗎？即使一切都沒有問題，播放時也容易因靜電而出現「小音爆」。除了這些問題外，傳統唱片也不耐久播。有些人心愛的唱片24小時內絕不播放兩次；也有愛樂者看到鍾愛的唱片，會一口氣將相同的數張全部買下，為的是多作儲備可免斷糧之虞。這一切，是新一代愛樂者無法想像的。
　　上述的這些苦難，在CD唱片出現之後就不復再現。
　　小小一片直徑12公分的CD到底有多大能耐，能免除前面提到的困擾，不也同樣是在唱盤上播放嗎？為什麼不怕小刮痕(太大的刮痕當然也會有問題)？為什麼可以不限次數地連續播放？而用了幾年的CD和新買的播放起來沒有兩樣。這是怎麼做到的？答案就是數位化再加上糾錯編碼。
　　數位化讓CD能提供完全沒有雜音的完美音響，以及任君指定的播放順序。而使用糾錯編碼，能讓CD可以不怕指紋、不怕刮痕。CD所使用的糾錯編碼是RS碼，理論上，可以糾正一串軌道長度達2.5毫米的訊號。筆者以前清除CD的灰塵，都按照音響雜誌的指示，用清潔工具小心地清理；接觸糾錯編碼之後，就直接拿CD在衣服上清除灰塵。(請注意，並不鼓勵讀者這麼做！)
　　除了沒有上述傳統唱片的缺點之外，CD唱片還有許多優點，其中之一是播放時間長－－CD的連續播放時間最多長達74分鐘，相較之下，傳統黑膠唱片只能連續播放30分鐘，著實遜色不少。至於為什麼是74分鐘？原來，這是為了要能不換片而一口氣聽完貝多芬的《合唱交響曲》呢！

外太空的訊號傳遞
　　美國航太總署在1977年8月20日發射了旅行者二號(Voyager II)，並在同年的9月5日發射了旅行者一號。旅行者號的任務之一，是從較近的距離拍攝天體的照片，並傳送回地球。由於太空船一旦發射出去，便無法補充能源，而能源不僅要維持太空船的正常運作，又要用於拍照並將訊息傳回地球，因此不能用太多的能源來傳送信號。太空船傳訊所用的能量約為5瓦，這樣的能量只能夠點亮一個小燈泡；用這麼小的能量傳遞數十億公里的距離，收到有錯的資料是可以預期的，因此一定要用編碼保護。
　　旅行者號的影像處理方式為，將一張全彩照片轉化為3個800×800的矩陣，每個陣元為8位元的像素(pixel)，也就是說，一張照片需要3×800×800×8=15,360,000個位元(bits)的數位訊號。旅行者號早先在土星傳送的資料都未經壓縮，是以葛雷碼編碼後傳送回地球；地球上收到訊號，經過解碼便可重建原來的照片。1982年旅行者號到達天王星，距離由土星的14億公里倍增為28億，因此便採用由萊斯(Robert Rice)提出的2.5倍壓縮比的無損壓縮演算法，對資料進行壓縮，再做糾錯編碼後傳回地球。由於經過壓縮的資料更是錯不得，所以將糾錯編碼換成糾錯能力更強的RS碼，之後在海王星也是使用RS碼。
　　目前旅行者號已經離開太陽系，因此，離開太陽系的深空探測器增加為四個，分別是先鋒十號、十一號，以及旅行者一號、二號。目前，旅行者二號仍然盡可能地將資料傳回地球，讓科學家獲得具體的數據，以研究過去無法探知的區域。最後，即使燃料完全用完，它們也都帶著一張儲存地球上各種影音資料的鍍金唱片(先鋒號帶的是鍍金鋁板)，要讓那些可能存在的地外文明，也能了解地球文明。

糾錯編碼的實例
　　看了這麼多文字介紹，接下來，我們要從一些簡單的例子，實際了解糾錯編碼。
　　假設要傳送art這個字，先依照表一將英文字母數位化。於是英文單字art就被轉換為數字串「00001」、「10010」、「10100」。接著，將數字串送出。假設傳送的過程中，第2、12個位置出了錯，則送出和收到訊號分別為：
送出：00001 10010 10100
收到：01001 10010 11110

表一：英文字母數位編碼一覽表

字母	編碼	字母	編碼	字母	編碼
a	00001	j	01010	s	10011
b	00010	k	01011	t	10100
c	00011	l	01100	u	10101
d	00100	m	01101	v	10110
e	00101	n	01110	w	10111
f	00110	o	01111	x	11000
g	00111	p	10000	y	11001
h	01000	q	10001	z	11010
i	01001	r	10010

　　由收到的資料解讀，每五個數字一組，解讀後得出「ir?」，無法確定是什麼字，除了第三個字母確定是錯的之外，其他的無從判斷是對是錯，要猜也無從猜起。為了避免這種的情形，在資料傳送前，都會對資料預做編碼處理。請看下面兩個編碼的例子。

奇偶校驗碼
　　奇偶校驗碼(parity-check code)是將原來的數字串分成兩個兩個一組，不足兩個的，補上0使其成為一組。接著，對每一組數字加入一個檢查碼，成為三個一組的數字串。加檢查碼的方式如下：
00→000
01→011
10→101
11→110
則原始資料的編碼流程為：
原始資料：000011001010100
補成偶數：0000110010101000
編碼後：000000110000101101101000
假設，傳送的過程中同樣在第2、12個位置出了錯，因此收到了：
010000110001101101101000
按照原先的編碼方式，解碼的方式為：
000→00
011→01
101→10
110→11
　　由於收到的前三個數字為010，不在規則內，因此解碼結果為「??」，也就是說遇到不在規則內的就解碼為「??」。則解碼後的結果如下：
　　解碼後；?? 00 11 ?? 10 10 10 00
前五個數字為「??001」，當然無法變成英文字母，之後的五個數字「1??10」也一樣，接著的五個數字「10100」，對應到英文字母t，後面留下一個0，表示是補上去的，可以忽略。因此最後得到的結果為「??t」。
　　這種編碼方式可以看出有錯(只要不在事先約定的規則內，就是有錯)，但是無法知道錯在哪裡，也就是說，只具備偵錯功能，不具備糾錯功能。

三倍重複碼
　　三倍重複碼(triple repetition code)是將每組兩個數字編碼為六個數字，而且是採用重複三次的方式做編碼，如下：
00→000000
01→010101
10→101010
11→111111
直接從補上零的原始字串進行編碼，得到：
000000 000000 111111 000000 101010 101010 101010 000000
同樣地，假設傳送的過程中第2、12個位置出了錯，因此收到了：
010000 000001 111111 000000 101010 101010 101010 000000
三倍重複碼解碼的方式如下：
000000→00
010101→01
101010→10
111111→11
前六個數字為「010000」，並不在規則內，表示一定有錯。由於編碼的方式是將ab編為ababab，表示第一、三、五個數字要相同，不同表示有錯；第二、四、六個數字的情形也是一樣。收到的「010000」的第一、三、五個數字都是0，可以視為無錯，而第二、四、六個數字分別1、0、0，表示一定有錯。如果第二個是錯的，則三個數字就都是0，反之，如果第四、六個數字有錯，則三個數字都是1。兩個情形都有可能，那麼要選哪一種好呢？解碼的原則是選擇可能性最大的，稱為「最大可能性解碼」(maximum likelihood decoding)。
　　錯一個和錯兩個，哪一種可能性比較大？一般來說，資料傳送時，出錯的可能性不能太大，在美國航太總署的太空任務中，可接受的最大出錯機率為一千個錯一個，也就是說每個數字出錯的機率為千分之一，兩個數字同時出錯的機率就是千分之一的平方－一百萬之一。上面的兩種情況相比，當然錯一個機率比較大，因此，「010000」應該解為「00」。同樣地，第二組數字「000001」應解為「00」，而剩下的部分沒有錯，都能正確解出，因此最後解碼後的結果為「00001 10010 10100」，由這串數字可以正確解出英文字「art」。這就是一個糾錯編碼的實例。
　　上面的這個例子是一個最簡單的情況。目前整個編碼學已建立在嚴格的數學理論基礎上，要用到組合理論、機率、抽象代數、有限體(finite field)等；而要能理解實際的應用，還要加上演算法(algorithm)和硬體等實作方面的知識。有了這些知識，就能對糾錯理論有更深刻的體會。

結語
　　隨著科技的進步，以往的電話只能聽到聲音，現在的手機還能邊講話邊看到對方，又能傳送音樂、照片和影像；回到家裡打開電視，就能看到上百個來自於有線、無線電視台的高畫質數位節目。如果沒有糾錯編碼，這一切只能是科幻小說中的情節。隨著生活品質的提升，我們對編碼的需求也更加殷切，身為一個現代人，怎能對這個概念一無所知呢？希望這篇文章，能讓你對糾錯理論有個基本的認識。最後，關於組合學以及更多的數學知識，有一本非常好的中文雜誌－－《數學傳播》，現在該雜誌的所有文章都已經放在網路上，歡迎讀者下載閱讀。

參考資料
1. 有澤創司，陳文棠譯，《SONY才子－－大賀典雄傳奇》，台北，迪茂國際出版公司，2001年。
2. 大賀典雄，劉錦秀譯，《指揮家與總裁》，台北，商周出版，2006年。
3. 王勝治，《數位雷射音響》，全華科技出版社，1992年。
4. 萬哲先，《代數和編碼》，北京，科學出版社，1980年。
5. 馮克勤，《代數與通信》，北京，高等教育出版社，2005年。

－－－－－－－－－－－－－－－－－－－－－－－－－－－
http://gclie.users.sonic.net/gclie/ecc.pdf
錯誤訊息的偵測與修正

賴紹正

為什麼條碼機可以正確地讀出你購買的商品價錢？為什麼稍稍刮損的音樂CD仍可播放？數位訊息中暗藏著什麼祕密，且讓我們來一探究竟。

　　筆者在《科學月刊》第468期（2008年12月號）的〈GPS的定位數學〉裡提到，衛星發射信號的功率在50瓦左右，我們也談到衛星的飛行高度大約在2.5萬公里左右。因訊號的強度與距離的平方成反比，故其到達地球表面的訊號強度大約只有瓦／平方公分，是非常弱的。相較之下，一般家用無線網路的功率大約在0.1瓦，其有效距離在100公尺內，其強度尚有瓦／平方公分。因此GPS的接收機應比家用無線網路的接收機敏感多了！

　　即使如此，我們還是很難想像，它能完全無誤地接收訊息，更何況衛星發射器本身及傳遞的過程中均可能產生錯誤訊息。GPS是用來定位的，些許的錯誤訊息很可能造成「差之毫釐，失之千里」！例如某顆衛星在台北的上空，但一字之差，接收機以為它在台南上空，計算後可能告訴你，你即將掉進台灣海峽了！如何解決此類問題正是本文所要探討的。

類比vs.數位
　　要避免像上述掉進台灣海峽的烏龍事件發生，接收機的首要功能應是能偵測到訊息的錯誤。在現今所謂的資訊時代，具備此一功能的設備，事實上已是日常生活中不可或缺的工具，只是大部分的人都沒有注意到而已。例如百貨公司所用的條碼機就有此一功能，相信許多讀者都有這個經驗：第一次掃描若發生錯誤，條碼機就會告訴服務員要重新掃描一次。可是條碼機如何知道它讀的資料有誤呢？

　　很顯然地，錯誤訊息的偵測一定是存在訊息本身內的。在討論訊息本身如何「儲存」偵測錯誤的能力之前，我們得先在這裡談一下訊息結構的種類。訊息的結構與傳播可分為類比（analog）及數位（digital）兩種。早期的訊息幾乎全是類比，類比的訊息是以波動的連續變化來儲存與傳遞；但隨著微電腦及積體電路的不斷改進，數位訊息的使用已越來越廣泛。數位訊息是以數碼的形式來儲存與傳遞訊息，如果原訊息是類比訊息，則須先將它數位化（digitalize）。數位訊息的最大優勢是可輕易且正確地複製及處理，以及本文所要談到的：可以輕易地偵測到訊息本身的錯誤並修正它。

錯誤訊息的偵測
　　如果圖一中的波形受干擾，發生不怎麼大的變形，我們無法判斷到底是因為「原來的信號就是如此」或是「錯誤」所致。但如果是圖二中的信號「50300702」受到少許的干擾，如5 的高度變成5.2，則因為訊息只有整數的，故我們可以毫無困難地知道（偵測到）5.2是錯誤的，應該修正為5 才對。這正是一種錯誤訊息的偵測與修正，相信是大家均早已知曉的數碼傳遞優點；但因其邏輯簡單，沒什麼研究可做（申請不到任何研究經費的），因此一般都不把它歸入「錯誤訊息的偵測與修正」。
　　聰明的讀者也許立即想到：如果干擾較大點，變成5.6呢？不錯，那我們的接收器只好把它當成6了。沒問題，雖然產生了「這麼大」的錯誤，但我們還是有辦法知道接收的訊息錯了，例如我們「規定」每8個數目的總和必須是奇數($ 5+0+3+0+0+7+0+2=17 $)，則第一個數目誤接收為6時，其總和變為偶數。錯了，請服務員再掃瞄一次吧！
　　如果干擾更大，5變成7怎麼辦呢？上面的奇數策略當然就不管用了。但要解決此一難題，事實上很簡單：我們可以「規定」8個數目的總和必須是9的倍數就可以了。當然，在條碼的運用上，這種「規定」很容易做得到。但如果應用到其他由類比數位化成的訊息時，就很難加以這樣「規定」(限制)了。解決此一問題的方法，事實上正是所有偵測訊息錯誤所採用的方法－－在訊息本身外加上其他「冗位」(redundancy)的資料。例如在前面所用的8位數資訊後，我們可以再加一位數，成為9位數的字碼(codeword)。這樣我們就不須要「限制」前面的8位數(它們可以是由任何數字組成的)，仍然可以達到字碼必須是9的倍數之要求(圖三)。請讀者在此特別注意：這冗位的數字不是隨便給的，而是由資訊本身(更正確地說，應是字碼本身)「計算」得來的－－字碼必須是9的倍數！

$ \underbrace{\overbrace{50300702}^{資訊}1}_{字碼} $

圖三：在這串訊息中，前8位數為有用的資訊，最後一位則是「冗位」，總共是9位數的字碼。

　　利用此一「編碼法」，我們可以很容易地偵測出字碼錯誤(不是9的倍數)，但卻不知錯誤在那裡。這用在條碼等訊息傳輸上不是大問題－－只要使用者(例如服務員)再重讀一次即可[註一]。但在很多的實用方面卻會構成大問題；例如在聽音樂CD時，我們不能叫聽者暫停，讓CD播放機重讀一下錯誤的訊息[註二]。因此在許多實用上，我們不只要有偵測錯誤訊息的能力，還須具備即時修正的能力，底下我們就來談談錯誤訊息的修正。

錯誤訊息的修正
　　在前面的例子裡(字碼必須是9的倍數)，我們只要將字碼連續傳遞兩次，則我們不但能偵測到訊息的錯誤，還可以同時完成修正。例如我們收到的訊息是：$ \underbrace{503007021}\underbrace{505007021} $

但我們不但知道訊息有誤，還知道第三位數應是3而不是5(因第三位數不同，且總和應是9的倍數)，這結果看來非常好，但仔細一想，未免太浪費「資源」了：本來只要傳遞8位數的訊息，現在卻須傳遞18位數。這「資源」在訊息傳播上稱為頻寬(bandwidth)。頻寬就像土地一樣，隨著人口的增加及生活水準的不斷提升，正是寸土寸金浪費不得的。
　　相信不少讀者早就想問：如果有兩位數字同時發生錯誤怎麼辦？答案很簡單：沒辦法，此編碼法不能用於修正同時含兩個(或兩個以上)錯誤的訊息。那怎麼辦呢？其解決方法有二：其一是尋根究底改進訊息的產生與傳遞，以及接收的機構，來降低錯誤的發生率到編碼法可以輕鬆完成任務的地步；其二則是設計「更好」的編碼方法，本文後面將會談論到。
　　在這裡順便一提，所有錯誤訊息的偵測及修正法均是採用原訊息中增加「冗位」的資料來完成的。這看來在資訊的儲存上似乎是個浪費，但如果仔細分析，就會知道這結論並不完全正確。例如在錄音帶的系統中，因有偵測及修正錯誤的能力，我們可以減低對訊號雜訊比(signal to noise ratio)的要求，而使用較狹窄的錄音帶。
　　到此為止，筆者所談的錯誤偵測與修正法，均可用直覺來推斷，缺少理論的基礎，但筆者相信已將其原理用白話清楚地表達出來。實用的編碼方法很多，也都有數學基礎，但那數學卻不是一般高中或大學所涉及的[註三]，因此我們在此不擬討論其推理，而僅說明結果。底下就是個無法用「直覺」想出來的例子－－音樂CD編碼的基本原理，如果不是數學家早有研究，相信索尼(Sony)及飛利浦(Philips)不會那麼快就發展出今日的CD標準。

漢明碼
　　為了能夠清楚地說明漢明碼(Hamming codes)，我們將以一個由7個二進位數組成的字碼來做為例子： $ \underbrace{1010}_{資訊}\underbrace{001}_{檢測} $
　　前面4位數是(有用的)資訊，而後面的3位數則是我們前面所談到之「冗位」資料，在錯誤訊息的偵測與修正上，一般稱為「同位位元」(parity bit)。用3位數來檢測與修正4位元的資訊，好像也比前面的10:8之頻寬浪費好不了多少。不錯，但這是為了說明方便，所以才採用3位元來檢視。如果我們採用4位元來檢測，則有用的資料長度可達11位元；用5位元來檢測與修正，有用的資料長度可高達26位元！
　　如前所述，同位位元並不是隨便加進去的，必須依一定規則計算出來。如果我們用$ b_1 $、$ b_2 $、$ b_3 $及$ b_4 $來代表前面的資訊，則後面3位檢測位元$ p_1 $、$ p_2 $及$ p_3 $依數學分析將分別為：$ \matrix{p_1=b_1+b_2+b_3 \cr p_2=b_1+b_3+b_4 \cr p_3=b_2+b_3+b_4} $
　　上面的「+」為二進位運算中的「互斥或(exclusive OR)」：$ \matrix{1+1=0 \cr 1+0=1 \cr 0+1=1 \cr 0+0=0} $
　　所以如果資訊為1010，我們得：$ \matrix{p_1=1+0+1=0 \cr p_2=1+1+0=0 \cr p_3=0+1+0=1} $。將這3位檢測位元加到原資訊後面，我們便得字碼：1010001。如果我們收到的字碼為$ (b_1b_2b_3b_4p_1p_2p_3) $，我們如何偵測及修正錯誤呢？我們由所接收的字碼計算出3個「接收檢測位元」：$ \matrix{Q_1=b_1+b_2+b_3+p_1 \cr Q_2=b_1+b_3+b_4+p_2 \cr Q_3=b_2+b_3+b_4+p_3} $

如果接收到之字碼沒錯，則$ Q_1=Q_2=Q_3=0 $；如果僅有一位位元有錯(此一漢明碼不能同時偵測兩個或以上之錯誤)，則其中至少有一Q不為0，我們可由$ Q_1,Q_2,Q_3 $之值推斷錯誤所在處如下[註四]：
$ (1,1,0)→b_1 $
$ (1,0,1)→b_2 $
$ (1,1,1)→b_3 $
$ (0,1,1)→b_4 $
$ (1,0,0)→p_1 $
$ (0,1,0)→p_2 $
$ (0,0,1)→p_3 $
　　然後將錯誤處之值0→1或1→0即可。例如原字碼1010001，但我們收到為1110001，則我們得：$ \matrix{Q_1=1+1+1+0=1 \cr Q_2=1+1+0+0=0 \cr Q_3=1+1+0+1=1} $
　　即$ (Q_1,Q_2,Q_3)=(1,0,1) $，所以我們可以得知$ b_2 $是錯誤的！這些計算看來雖然不怎麼複雜，不過似乎很繁瑣；但其運算方式是計算機設計的基本邏輯，因此可以利用微電腦線路，完全自動化地偵測及修正接收到的資訊。

里德-所羅門碼
　　在音樂CD中所用的錯誤偵測原理雖然與上面的例子相似，但當然要比它複雜多了。我們上面例子裡的每個二進位位元，在音樂CD裡則是由8位位元組合的「符號」(symbol)；檢測位元也是由符號組成的。它的字碼由24個資料符號及8個檢測符號組成(共32個符號)，可以同時偵測及修正4個資料符號。此一「編碼法」是里德(Irving Reed)及索羅門(Gustave Solomon)於1960年，在美國麻省理工學院林肯實驗室發展出來的，稱為里德-索羅門碼(Reed-Solomon codes，簡稱RS碼)。
　　為了能修正「大面積」錯誤(burst error)，此編碼法更將原來一連串符號(包括檢測符號)交錯記錄於音樂CD內，這樣原來RS碼無法修正的大面積錯誤(大於4個資料符號)在復原時就被「打散」成許多RS碼可以處理的小面積(等於或小於4個資料符號)錯誤。在音樂CD的編碼上，此一做法稱為「交叉插入里德-索羅門碼(cross interleave Reed-Solomon code，簡稱CIRC)」。這說明了為什麼在音樂CD上刮一道(請勿輕易嘗試)，有時還是不會失真的原因。當然，要產生原來音樂前，得先將交錯復原後再解碼。

結語
　　隨著微電腦及積體電路的不斷改進，數位訊息的使用已越來越廣泛：從微電腦本身到MP3、音樂CD、DVD影碟機、電影、錄影機、照相機、無線電廣播、電視、電台……等等。數位訊息最大的優勢是處理(如修改)容易、可輕易且完美地複製、以及「很容易地」偵測到其傳遞錯誤的訊息並修正之。本文不用數學，簡單地介紹了數位訊息傳遞錯誤的偵測與修正的基本原理：在原訊息中增加「多餘」的「同位位元」來達成(例如音樂CD裡就多加了三分之一同位位元)。雖然我們未能深入地討論其數學，但希望讀者還是能因本文而了解到，看似簡單的日常用品後面，事實上是暗藏了常被視為無用之「純」數學的研究成果。

註一：電腦的記憶體就是使用此一原理(9位元，其中有一位元是屬於「冗位」的)；但因電源及其設計越來越穩定，不少個人電腦都已開始採用不須「冗位」位元的記憶結構(買記憶體時應注意)。
註二：隨身聽音樂CD播放機因隨時在動的關係，其錯誤訊息出現的頻率遠超過家用音樂CD播放機，因此必須常常利用重讀來解決錯誤的問題，所以較貴的CD隨身聽機都有所謂的「抗震」功能。它們是先將資料儲存於緩衝區，然後依序播放。緩衝區越大，抗震的能力當然也越大。緩衝區使得它們有時間(不須暫停)去重讀錯誤的資料。
註三：所用的數學為抽象代數學(abstract algebra)中的場(field)論。我們所熟知的一個例子是：所有的實數及其運作(加減及乘除)規則構成了一個抽象代數中的「(無限)場」(因具有無限的實數)。
註四：如果讀者對排列組合有興趣，可以輕易算出不全為0的情形共有7種，這正是7位元資訊單一錯誤的可能情形！利用此一分析，讀者也可了解為什麼我們在文中說：「如果採用4位元來檢測，則有用的資料長度可達11位元」了。

－－－－－－－－－－－－－－－－－－－－－－－－－－－
110.1.29補充
Hamming codes and error correction
https://www.youtube.com/watch?v=X8jsijhllIA
Hamming codes part 2, the elegance of it all
https://www.youtube.com/watch?v=b3NxrZOu_CE

作者: bugmens 時間: 2025-8-12 11:14

11.秘密分享方案介紹－R. J. McEliece and D. V. Sarwate

這個方案是基於Reed-Solomon糾錯編碼，詳細內容請見
R. J. McEliece and D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Comm. ACM, Vol. 24 (1981), 583-584.
https://dl.acm.org/doi/pdf/10.1145/358746.358762

由Adi Shamir提出的著名「秘密分享機制」(Secret Sharing Scheme)，實際上可以被視為「里德-所羅門碼 (Reed-Solomon Codes)」編碼理論中的一個特例。若將秘密分享問題置於編碼理論的框架下進行探討，將帶來許多顯著的優勢。

最大的優勢在於能夠利用里德-所羅門碼強大的「錯誤與抹除解碼算法」(errors-and-erasures decoding algorithm)。這意味著，即使部分「秘密份額 (pieces of the secret)」因為惡意篡改(錯誤)或儲存媒介損壞(抹除)而變得不可信，只要收集到足夠數量的(包含錯誤的)份額，依然可以透過解碼算法找出哪些份額是錯誤的，並成功還原出原始的秘密。

1.Shmir秘密分享
設秘密為$S$，$n$個人共享秘密，至少要$k$位才能重組秘密 $f(x)$為$k-1$次多項式，其中常數項為秘密$S$，其餘各項係數為隨機整數計算$f(x)$上$n$個點座標，將各個座標分派給$n$個人 Shamir's secret sharing的$\displaystyle f(x)=\sum_{i=0}^{k-1}a_ix^i$等同於 Reed-Solomon錯誤校正碼的$\displaystyle p_m(a)=\sum_{i=0}^{k-1}m_i a^i$	範例出自Shamir's secret sharing 設秘密為$S=1234$，$n=6$個人共享秘密，至少要$k=3$位才能重組秘密 $f(x)$為$k-1=2$次多項式，其中常數項為秘密$S$，1次項和2次項係數為隨機整數 $f(x)=1234+166x+94x^2\pmod{1613}$ 計算$f(x)$上6個點座標 $f(1)=1234+166\cdot 1+94\cdot 1^2=1494\equiv 1494\pmod{1613}$ $f(2)=1234+166\cdot 2+94\cdot 2^2=1942\equiv 329\pmod{1613}$ $f(3)=1234+166\cdot 3+94\cdot 3^2=2578\equiv 965\pmod{1613}$ $f(4)=1234+166\cdot 4+94\cdot 4^2=3402\equiv 176\pmod{1613}$ $f(5)=1234+166\cdot 5+94\cdot 5^2=4414\equiv 1188\pmod{1613}$ $f(6)=1234+166\cdot 6+94\cdot 6^2=5614\equiv 775\pmod{1249}$ 將$(1,1494),(2,329),(3,965),(4,176),(5,1188),(6,775)$分派給6個人
2.當$k$個人聚在一起要重建秘密(無錯誤情況)
有$k$個人聚在一起要重組秘密$S$，利用拉格朗日插值多項式計算出$f(x)$ 秘密為$S=f(0)$	假設第2,4,5位聚在一起要重組秘密$S$，利用拉格朗日插值多項式根據$(2,329),(4,176),(5,1188)$計算出$f(x)$ $\displaystyle f(x)=329\frac{(x-4)(x-5)}{(2-4)(2-5)}+176\frac{(x-2)(x-5)}{(4-2)(4-5)}+1188\frac{(x-2)(x-4)}{(5-2)(5-4)}$ 　　$\displaystyle =329\frac{(x-4)(x-5)}{6}-88(x-2)(x-5)+396(x-2)(x-4)$ 　　$\equiv 329\cdot 269(x-4)(x-5)-88(x-2)(x-5)+396(x-2)(x-4)\pmod{1613}$ 　　$\equiv 1234+166x+94x^2 \pmod{1613}$ 秘密為$f(0)=1234$
3.有錯誤情況用Berlekamp-Welch演算法修正解碼
設$e$為發生錯誤數量，錯誤位置多項式$\displaystyle E(x)=\sum_{i=0}^{e}e_i x^i$，最高次方係數$e_e=1$ (1)當$(a_i,b_i)$為正確的點座標時　$E(a_i)\ne 0$($x=a_i$代入錯誤位置多項式不為0(不符合)) 　$b_i=f(a_i)$(點座標$(a_i,b_i)$)符合$f(x)$多項式) (2)當$(a_i,b_i)$為錯誤的點座標時　$E(a_i)=0$($x=a_i$代入錯誤位置多項式為0(符合)) 　$b_i\ne f(a_i)$(點座標$(a_i,b_i)$不符合$f(x)$多項式) $b_i=f(a_i)$，兩邊同乘$E(a_i)$得到$b_iE(a_i)=f(a_i)E(a_i)$ 設$Q(a_i)=f(a_i)E(a_i)$得到$b_iE(a_i)=Q(a_i)$，$b_iE(a_i)-Q(a_i)=0$ (1)當$(a_i,b_i)$為正確的點座標時($E(a_i)\ne 0,b_i=f(a_i)$) 　$b_iE(a_i)-Q(a_i)=b_iE(a_i)-f(a_i)E(a_i)=E(a_i)(b_i-f(a_i))=0$等式成立 (2)當$(a_i,b_i)$為錯誤的點座標時($E(a_i)=0,b_i\ne f(a_i)$) 　$b_iE(a_i)-Q(a_i)=b_iE(a_i)-f(a_i)E(a_i)=0(b_i-f(a_i))=0$等式成立代表點座標$(a_i,b_i)$無論正確還是錯誤都符合$b_iE(a_i)-Q(a_i)=0$ 將$b_iE(a_i)-Q(a_i)=0$，以$\displaystyle E(a_i)=\sum_{i=0}^{e}e_i a_i^i$，$\displaystyle Q(a_i)=\sum_{i=0}^q q_ia_i^i$展開 $b_i(e_0+e_1a_i+e_2a_i^2+\ldots+e_ea_i^e)-(q_0+q_1a_i+q_2a_i^2+\ldots+q_qa_i^q)=0$ 其中$q=n-e-1$，又$E(x)$最高次方係數$e_e=1$，方程式改成 $b_i(e_0+e_1a_i+e_2a_i^2+\ldots+e_{e_1}a_i^{e-1})-(q_0+q_1a_i+q_2a_i^2+\ldots+q_qa_i^q)=-b_ia_i^e$ 將各個點座標$(a_i,b_i)$代入上式，解聯立方程組求$e_0,e_1,\ldots,e_{e-1},q_0,q_2,\ldots,q_q$ $E(x)$有$e$個未知數，$Q(x)=f(x)E(x)$有$k+e$個未知數，需要$n=e+(k+e)$個方程式該演算法從假設最大可能錯誤數$\displaystyle e =\Bigg\lfloor\;\frac{n-k}{2}\Bigg\rfloor\;$開始。如果方程式無法求解，則將$e$減1並重複此過程，直到聯立方程組可以求出惟一解或$e$降至0，表示沒有找到錯誤。找到$E(x)$和$Q(x)$，解$E(x)=0$得到錯誤位置，計算$\displaystyle f(x)=\frac{Q(x)}{E(x)}$，秘密$S=f(0)$	有5個人聚在一起但不知道哪個人的子秘密是錯誤的 $(1,1494),(2,329),(3,123),(4,176),(5,1188)$，($(3,123)$應為$(3,965)$) $\displaystyle e=\Bigg\lfloor\;\frac{5-3}{2}\Bigg\rfloor\;=1$，最多可以修正1個錯誤錯誤位置多項式$E(x)=e_0+x$，只有1個錯誤為1次多項式，$e_0$為錯誤點的$x$坐標設$Q(x)=E(x)f(x)$次數為$e+(k-1)=1+2=3$次 $Q(x)=q_0+q_1x+q_2x^2+q_3x^3$ 將$(a_i,b_i)=(1,1494),(2,329),(3,123),(4,176),(5,1188)$代入$b_i \cdot E(a_i)-Q(a_i)=0$ $b_i(e_0+a_i)-(q_0+q_1a_1+q_2a_1^2+q_3a_1^3)\equiv 0\pmod{p}$ $b_ie_0-(q_0+q_1a_1+q_2a_1^2+q_3a_1^3)\equiv -b_ia_i\pmod{p}$ $\cases{1494e_0-(q_0+q_1\cdot 1+q_2 \cdot 1^2+q_3\cdot 1^3)\equiv -1494\cdot 1\cr 329e_0-(q_0+q_1\cdot 2+q_2 \cdot 2^2+q_3\cdot 2^3)\equiv -329\cdot 2\cr 123e_0-(q_0+q_1\cdot 3+q_2 \cdot 3^2+q_3\cdot 3^3)\equiv -123\cdot 3\cr 176e_0-(q_0+q_1\cdot 4+q_2 \cdot 4^2+q_3\cdot 4^3)\equiv -176\cdot 4\cr 1188e_0-(q_0+q_1\cdot 5+q_2 \cdot 5^2+q_3\cdot 5^3)\equiv -1188\cdot 5}\pmod{1613}$ 解聯立方程組，得到$e_0=-3,q_0=-476,q_1=736,q_2=-116,q_3=94$ $E(x)=-3+x$，解$E(x)=0$，錯誤在$x=3$ $Q(x)=f(x)E(x)=f(x)(x-3)=-476+736x-116x^2+94x^3\pmod{1613}$ 使用綜合除法計算$f(x)$ $\frac{\matrix{94&-116&736&-476&\|3\cr 　&282&498&3702&\|　}}{\matrix{94&166&1234&\|3226&　}}$ 餘式$3226\equiv 0\pmod{1613}$是整除的 $f(x)=1234+166x+94x^2\pmod{1613}$ $f(3)=1234+166\cdot 3+94\cdot 3^2=2578\equiv 965\pmod{1613}$ 正確的子秘密為$(3,965)$ 秘密$S=f(0)=1234$

要先載入interpol.mac才能使用lagrange指令
load("interpol.mac");
C:/maxima-5.47.0/share/maxima/5.47.0/share/numeric/interpol.mac

設定秘密S
S:1234;
$1234$

設定在GF(p)底下運算，其中p為質數
p:1613;
modulus:p;
$1613$
$1613$

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

設定6個人要分享此秘密，計算f(x)上6個點座標分派給這6個人
shadows:create_list([x,f(x)],x,1,6);
$[[1,1494],[2,329],[3,965],[4,176],[5,1188],[6,775]]$

假設第2,4,5位聚在一起要重組秘密S，利用拉格朗日插值多項式計算出f(x)
fx:lagrange([shadows[2],shadows[4],shadows[5]]);
fx:ratsimp(fx);
$\displaystyle 396(x-4)(x-2)-88(x-5)(x-2)+\frac{329(x-5)(x-4)}{6}$
$94x^2+166x-379$

其中常數項就是當初設定的祕密S
S:mod(ev(fx,x=0),p);
$1234$

使用者3的子秘密發生錯誤，應為[3,965]
shadows[3]:[3,123];
$[3,123]$

有5個人聚在一起但不知道哪1個人的子秘密是錯誤的
Users:[1,2,3,4,5];
$[1,2,3,4,5]$

錯誤位置多項式
E(x):=e0+x;
$E(x) :=e0+x$

Q(x)=f(x)E(x)多項式
Q(x):=q0+q1*x+q2*x^2+q3*x^3;
$Q(x) :=q0+q1x+q2x^2+q3x^3$

將5人的子秘密代入bi*E(ai)-Q(ai)=0
equations:[]$
for i in Users do
(ai:shadows[ i ][1],/*x座標*/
bi:shadows[ i ][2],/*y座標*/
equations:append(equations,[bi*E(ai)-Q(ai)=0])
)$
equations;
$[-q3-q2-q1-q0+1494(e0+1)=0,-8q3-4q2-2q1-q0+329(e0+2)=0,-27q3-9q2-3q1-q0+123(e0+3)=0,$
$-64q3-16q2-4q1-q0+176(e0+4)=0,-125q3-25q2-5q1-q0+1188(e0+5)=0]$

聯立方程組以直式顯示
transpose(matrix(equations));
$\left[\matrix{-q3-q2-q1-q0+1494(e0+1)=0\cr
-8q3-4q2-2q1-q0+329(e0+2)=0\cr
-27q3-9q2-3q1-q0+123(e0+3)=0\cr
-64q3-16q2-4q1-q0+176(e0+4)=0\cr
-125q3-25q2-5q1-q0+1188(e0+5)=0}\right]$

解聯立方程組
solution:solve(equations,[e0,q0,q1,q2,q3]);
$[[e0=-3,q0=-476,q1=736,q2=-116,q3=94]]$

將解代回E(x)和Q(x)
Ex:ev(E(x),solution[1]);
Qx:ev(Q(x),solution[1]);
$x-3$
$94x^3-116x^2+736x-476$

Q(x)除以E(x)得f(x)
fx: Qx/Ex;
fx:ratsimp(fx);
$\displaystyle \frac{94x^3-116x^2+736x-476}{x-3}$
$94x^2+166x-379$

解E(x)=0，得到錯誤位置
x:solve(Ex,x);
x:rhs(x[1]);
$[x=3]$
$3$

算出第3位正確的子秘密
shadows[x]:[x,ev(fx,x=x)];
$[3,965]$

秘密S=f(0)
S:mod(ev(fx,x=0),p);
$1234$

作者: bugmens 時間: 2025-8-13 16:35

延續上一篇McEliece和Sarwate方案，提供另一個例子

要先載入interpol.mac才能使用lagrange指令
load("interpol.mac");
C:/maxima-5.47.0/share/maxima/5.47.0/share/numeric/interpol.mac

設定秘密S
(這個數字可自行修改，但S<p)
S:12345;
$12345$

設定在Fp底下運算，其中p為質數
p:65537;
modulus:p;
$65537$
$65537$

設定n個人共享秘密，至少要k個人才能重建秘密
(這兩個數字可自行修改，但n≥k)
n:8;
k:3;
$8$
$3$

最多可以修正Error個錯誤
Error:floor((n-k)/2);
$2$

隨機產生k-1次多項式，其中常數項為秘密S
f(x):=''(S+apply("+",create_list(random(p)*x^i,i,1,k-1)));
$f(x) :=31816x^2+60108x+12345$

產生n個點座標，將點座標mod p後分派給這n個人
shadows:create_list([i,mod(f(i),p)],i,1,n);
$[[1,38732],[2,63214],[3,20254],[4,40926],[5,59693],[6,11018],[7,25975],[8,39027]]$

將順序打亂
shadows:random_permutation(shadows);
$[[7,25975],[3,20254],[1,38732],[5,59693],[6,11018],[8,39027],[2,63214],[4,40926]]$

假設有k個人聚在一起要重建秘密
shadowk:sort(rest(shadows,-(n-k)));
$[[1,38732],[3,20254],[7,25975]]$

利用拉格朗日插值多項式計算通過這k個點座標的k-1次多項式
fx:lagrange(shadowk);
fx:ratsimp(fx);
$\displaystyle \frac{25975(x-3)(x-1)}{24}-\frac{10127(x-7)(x-1)}{4}+\frac{9683(x-7)(x-3)}{3}$
$31816x^2-5429x+12345$

其中常數項為當初設定的祕密S
S:mod(ev(fx,x=0),p);
$12345$

需要(k+2*Error)個人聚在一起才能修正錯誤並重建秘密
shadows:rest(shadows,n-k-2*Error);
$[[3,20254],[1,38732],[5,59693],[6,11018],[8,39027],[2,63214],[4,40926]]$

其中Error個人的子秘密是錯誤的
for i:1 thru Error do
  (print("假設第",shadows[ i ][1],"位使用者的子秘密是錯誤的，改成",shadows[ i ][2]:1111*i)
  )$
shadows:sort(shadows);
假設第3位使用者的子秘密是錯誤的，改成1111
假設第1位使用者的子秘密是錯誤的，改成2222
$[[1,2222],[2,63214],[3,1111],[4,40926],[5,59693],[6,11018],[8,39027]]$

錯誤位置多項式E(x)
E(x):=''(apply("+",create_list(if i=Error then x^i else e[ i ]*x^i,i,0,Error)));
$E(x) :=x^2+e_1x+e_0$

Q(x)=f(x)E(x)多項式
Q(x):=''(apply("+",create_list(q[ i ]*x^i,i,0,k+Error-1)));
$Q(x) :=q_4x^4+q_3x^3+q_2x^2+q_1x+q_0$

將(k+2*Error)個子秘密代入bi*E(ai)-Q(ai)=0
equations:[]$
for shadow in shadows do
  (ai:shadow[1],/*x座標*/
bi:shadow[2],/*y座標*/
equations:append(equations,[bi*E(ai)-Q(ai)=0])
  )$
equations;
$-q_4-q_3-q_2-q_1+2222(e_1+e_0+1)-q_0=0,-16q_4-8q_3-4q_2-2q_1+63214(2e_1+e_0+4)-q_0=0,$
$-81q_4-27q_3-9q_2-3q_1+1111(3e_1+e_0+9)-q_0=0,-256q_4-64q_3-16q_2-4q_1+40926(4e_1+e_0+16)-q_0=0,$
$-625q_4-125q_3-25q_2-5q_1+59693(5e_1+e_0+25)-q_0=0,-1296q_4-216q_3-36q_2-6q_1+11018(6e_1+e_0+36)-q_0=0,$
$-4096q_4-512q_3-64q_2-8q_1+39027(8e_1+e_0+64)-q_0=0$

聯立方程組以直式顯示
transpose(matrix(equations));
$\left[\matrix{-q_4-q_3-q_2-q_1+2222(e_1+e_0+1)-q_0=0\cr
-16q_4-8q_3-4q_2-2q_1+63214(2e_1+e_0+4)-q_0=0\cr
-81q_4-27q_3-9q_2-3q_1+1111(3e_1+e_0+9)-q_0=0\cr
-256q_4-64q_3-16q_2-4q_1+40926(4e_1+e_0+16)-q_0=0\cr
-625q_4-125q_3-25q_2-5q_1+59693(5e_1+e_0+25)-q_0=0\cr
-1296q_4-216q_3-36q_2-6q_1+11018(6e_1+e_0+36)-q_0=0\cr
-4096q_4-512q_3-64q_2-8q_1+39027(8e_1+e_0+64)-q_0=0}\right]$

共有(k+2*Error)個未知數
variable:append(create_list(e[ i ],i,0,Error-1),
                        create_list(q[ i ],i,0,k+Error-1));
$[e_0,e_1,q_0,q_1,q_2,q_3,q_4]$

解聯立方程組
solution:solve(equations,variable);
$[[e_0=3,e_1=-4,q_0=-28502,q_1=-130,q_2=-1565,q_3=-1619,q_4=31816]]$

將解代回E(x)和Q(x)
Ex:subst(solution[1],E(x));
Qx:subst(solution[1],Q(x));
$x^2-4x+3$
$31816x^4-1619x^3-1565x^2-130x-28502$

Q(X)除以E(X)得f(x)
fx: Qx/Ex;
fx:ratsimp(fx);
$\displaystyle \frac{31816x^4-1619x^3-1565x^2-130x-28502}{x^2-4x+3}$
$31816x^2-5429x+12345$

解E(x)=0，得到錯誤位置
factor(Ex);
Errorx:solve(Ex,x);
$(x-3)(x-1)$
$[x=1,x=3]$

算出正確的子秘密
for i:1 thru Error do
  (x:rhs(Errorx[ i ]),
print("第",x,"位使用者的子秘密是錯誤的，修正為f(",x,")=",mod(f(x),p))
  )$
第1位使用者的子秘密是錯誤的，修正為$f(1)=38732$
第3位使用者的子秘密是錯誤的，修正為$f(3)=20254$

秘密S=f(0)
S:mod(ev(fx,x=0),p);
$12345$

作者: bugmens 時間: 2025-9-13 17:04

當要分享的秘密相當長時，每一份子秘密也會跟著變長使用上會造成不便，以Reed-Solomon編碼的另一種實現方式，犧牲些許安全性代價，來達到一定程度的資料壓縮。

原始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。	假設$b=(b_1,b_2,\ldots,b_k)$是要分享的秘密，存在唯一一個Reed-solomon碼字(cdoeword)$D$，前$k$個就是密碼本身，即$D_1=b_1,D_2=b_2,\ldots,D_k=b_k$。事實上，$D$可以由Shamir方法的拉格朗日插值多項式或標準Reed-Solomon編碼演算法找到。只有剩下$r-1-k$個$D_{k+1},\ldots,D_{r-1}$可以分給參與者共享秘密，如前面所述，至少$k$個(未被竄改)才能還原秘密。
範例
設秘密$S=1234567890$非常長再找比$S$還大的質數$p=1234567907$ $f(x)=1234567890+15618435x+38443541x^2\pmod{p}$ 常數項$a_0=S$，係數$a_1,a_2$為小於$p$的任意整數 $(1,f(1))=(1,54061959)$ $(2,f(2))=(2,185011017)$ $(3,f(3))=(3,392847157)$ $(4,f(4))=(4,677570379)$ $(5,f(5))=(5,1039180683)$ $(6,f(6))=(6,243110162)$ 每位使用者所拿到的子秘密幾乎和原始秘密長度相同當三位使用者聚在一起，將各個子秘密$(3,f(3)),(4,f(4)),(6,f(6))$利用拉格朗日插值多項式 $\displaystyle f(x)=392847157\frac{(x-4)(x-6)}{(3-4)(3-6)}$ 　$\displaystyle +677570379\frac{(x-3)(x-6)}{(4-3)(4-6)}$ 　$\displaystyle +243110162\frac{(x-3)(x-4)}{(6-3)(6-4)}\pmod{p}$ $f(x)=1234567890+15618435x+38443541x^2\pmod{p}$ 秘密$S=f(0)=1234567890$	將秘密$1234567890$拆成$S=(0,1234),(1,567),(2,890)$ $p=1613$ 利用拉格朗日插值多項式，產生通過$(0,1234),(1,567),(2,890)$三點的二次多項式$f(x)$ $\displaystyle f(x)=1234\cdot \frac{(x-1)(x-2)}{(0-1)(0-2)}+567\cdot \frac{(x-0)(x-2)}{(1-0)(1-2)}+890\cdot \frac{(x-0)(x-1)}{(2-0)(2-1)}\pmod{1613}$ $f(x)=1234+451x+495x^2\pmod{1613}$ 常數項$a_0=S$，係數$a_1,a_2$是根據拉格朗日插值多項式所產生的特定整數 $(3,f(3))=(3,590)$ $(4,f(4))=(4,1280)$ $(5,f(5))=(5,1347)$ $(6,f(6))=(6,791)$ $(7,f(7))=(7,1225)$ $(8,f(8))=(8,1036)$ 每位使用者所拿到的子秘密縮短許多當三位使用者聚在一起，將各個子秘密$(3,f(3)),(4,f(4)),(6,f(6))$利用拉格朗日插值多項式 $\displaystyle f(x)=590\frac{(x-4)(x-6)}{(3-4)(3-6)}+1280\frac{(x-3)(x-6)}{(4-3)(4-6)}+791\frac{(x-3)(x-4)}{(6-3)(6-4)}\pmod{1613}$ $f(x)=1234+451x+495x^2\pmod{1613}$ $f(0)=1234$，$f(1)=567$，$f(2)=890$ 合併秘密$S=1234567890$
安全性
若已知2個子秘密$(3,392847157),(4,677570379)$ 代入$f(x)=a_0+a_1x+a_2x^2\pmod{p}$得 $\cases{392847157=a_0+3a_1+9a_2\cr 677570379=a_0+4a_1+16a_2}$ 兩式相減得$284723222\equiv a_1+7a_2\pmod{1234567907}$ $a_1,a_2$為隨機整數，知道$a_1$和$a_2$的關係式對於求$a_0=S$沒有幫助。	若已知2個子秘密$(3,590),(4,1280)$ 代入$f(x)=a_0+a_1x+a_2x^2\pmod{p}$得 $\cases{590=a_0+3a_1+9a_2\cr 1280=a_0+4a_1+16a_2}$ 兩式相減得$690\equiv a_1+7a_2\pmod{1613}$ $a_1,a_2$本身就是祕密的一部分，知道$a_1$和$a_2$的關係式對於秘密空間的複雜度被大大降低。

要先載入interpol.mac才能使用lagrange指令
(%i1)　load("interpol.mac");
(%o1)　C:/maxima-5.43.0/share/maxima/5.48.1/share/numeric/interpol.mac

設定非常長的秘密S
(%i2)　S:1234567890;
(%o2)　$1234567890$

設定在GF(p)底下運算，其中p為質數
(%i4)
p:1613;
modulus:p;
(%o3)　$1613$
(%o4)　$1613$

將長秘密分割，每個部份都小於p
(%i9)
SList:[]$
while S>p do
  (for i:2 thru floor(log(p)/log(10))+1 do
   (if mod(S,10^i)>p then
      (remainder:mod(S,10^(i-1)),
      S:floor(S/10^(i-1)),
      SList:append([remainder],SList)
      )
   )
  )$
print("將秘密S分割成",SList:append([S],SList))$
print("共有",SListLen:length(SList),"組")$
print("加上x座標",SList:makelist([i-1,SList[ i ]],i,1,SListLen))$
將秘密$S$分割成$[1234,567,890]$
共有3組
加上$x$座標$[[0,1234],[1,567],[2,890]]$

設定n個人共享秘密，至少要k個人才能重建秘密
(%i11)
n:6;
k:3;
(%o10)　$6$
(%o11)　$3$

利用拉格朗日插值多項式計算通過這SList個點座標的多項式
(%i12)　define(f(x),lagrange(SList));
(%o12)　$f(x) :=445(x-1)x-567(x-2)x-617(1-x)(x-2)$

設定6個人要分享此秘密，計算f(x)上6個點座標分派給這6個人
(%i13)　shadows:create_list([i,mod(f(i),p)],i,SListLen,n+SListLen-1);
(%o13)　$[[3,590],[4,1280],[5,1347],[6,791],[7,1225],[8,1036]]$

假設任意k個人聚在一起要重組秘密S
(%i15)
shadows:random_permutation(shadows)$
shadowk:sort(rest(shadows,-(n-k)));
(%o15)　$[[3,590],[4,1280],[6,791]]$

利用拉格朗日插值多項式計算出f(x)
(%i17)
fx:lagrange(shadowk);
fx:ratsimp(fx);
(%o16)　$\displaystyle \frac{1225(x-6)(x-5)}{2}-791(x-7)(x-5)-\frac{1347(6-x)(x-7)}{2}$
(%o17)　$495x^2+451x-379$

計算f(0),f(1),...,f(SListLen)
(%i18)　SList:create_list(mod(ev(fx,x=x),p),x,0,SListLen-1);
(%o18)　$[1234,567,890]$

合併成秘密S
(%i19)　S:parse_string(apply(sconcat,map(string,SList)));
(%o19)　$1234567890$

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0

整數 j	二進位	\( i=1 \)	\( i=2 \)	\( i=3 \)	集合\( S_j \)
1	001	\( B(1,1)=0 \)	\( B(1,2)=0 \)	\( B(1,3)=1 \)	\( S_1=\{\; s_3 \}\; \)
2	010	\( B(2,1)=0 \)	\( B(2,2)=1 \)	\( B(2,3)=0 \)	\( S_2=\{\; s_2 \}\; \)
3	011	\( B(3,1)=0 \)	\( B(3,2)=1 \)	\( B(3,3)=1 \)	\( S_3=\{\; s_2,s_3 \}\; \)
4	100	\( B(4,1)=1 \)	\( B(4,2)=0 \)	\( B(4,3)=0 \)	\( S_4=\{\; s_1 \}\; \)
5	101	\( B(5,1)=1 \)	\( B(5,2)=0 \)	\( B(5,3)=1 \)	\( S_5=\{\; s_1,s_3 \}\; \)
6	110	\( B(6,1)=1 \)	\( B(6,2)=1 \)	\( B(6,3)=0 \)	\( S_6=\{\; s_1,s_2 \}\; \)
7	111	\( B(7,1)=1 \)	\( B(7,2)=1 \)	\( B(7,3)=1 \)	\( S_7=\{\; s_1,s_2,s_3 \}\; \)
		使用者1 拿到質數 \( s_1=p_4p_5p_6p_7 \)	使用者2 拿到質數 \( s_2=p_2p_3p_6p_7 \)	使用者3 拿到質數 \( s_3=p_1p_3p_5p_7 \)

1.Shmir秘密分享
設秘密為\(S\)，\(n\)個人共享秘密，至少要\(k\)位才能重組秘密 \(f(x)\)為\(k-1\)次多項式，其中常數項為秘密\(S\)，其餘各項係數為隨機整數計算\(f(x)\)上\(n\)個點座標，將各個座標分派給\(n\)個人 Shamir's secret sharing的\(\displaystyle f(x)=\sum_{i=0}^{k-1}a_ix^i\)等同於 Reed-Solomon錯誤校正碼的\(\displaystyle p_m(a)=\sum_{i=0}^{k-1}m_i a^i\)	範例出自Shamir's secret sharing 設秘密為\(S=1234\)，\(n=6\)個人共享秘密，至少要\(k=3\)位才能重組秘密 \(f(x)\)為\(k-1=2\)次多項式，其中常數項為秘密\(S\)，1次項和2次項係數為隨機整數 \(f(x)=1234+166x+94x^2\pmod{1613}\) 計算\(f(x)\)上6個點座標 \(f(1)=1234+166\cdot 1+94\cdot 1^2=1494\equiv 1494\pmod{1613}\) \(f(2)=1234+166\cdot 2+94\cdot 2^2=1942\equiv 329\pmod{1613}\) \(f(3)=1234+166\cdot 3+94\cdot 3^2=2578\equiv 965\pmod{1613}\) \(f(4)=1234+166\cdot 4+94\cdot 4^2=3402\equiv 176\pmod{1613}\) \(f(5)=1234+166\cdot 5+94\cdot 5^2=4414\equiv 1188\pmod{1613}\) \(f(6)=1234+166\cdot 6+94\cdot 6^2=5614\equiv 775\pmod{1249}\) 將\((1,1494),(2,329),(3,965),(4,176),(5,1188),(6,775)\)分派給6個人
2.當\(k\)個人聚在一起要重建秘密(無錯誤情況)
有\(k\)個人聚在一起要重組秘密\(S\)，利用拉格朗日插值多項式計算出\(f(x)\) 秘密為\(S=f(0)\)	假設第2,4,5位聚在一起要重組秘密\(S\)，利用拉格朗日插值多項式根據\((2,329),(4,176),(5,1188)\)計算出\(f(x)\) \(\displaystyle f(x)=329\frac{(x-4)(x-5)}{(2-4)(2-5)}+176\frac{(x-2)(x-5)}{(4-2)(4-5)}+1188\frac{(x-2)(x-4)}{(5-2)(5-4)}\) 　　\(\displaystyle =329\frac{(x-4)(x-5)}{6}-88(x-2)(x-5)+396(x-2)(x-4)\) 　　\(\equiv 329\cdot 269(x-4)(x-5)-88(x-2)(x-5)+396(x-2)(x-4)\pmod{1613}\) 　　\(\equiv 1234+166x+94x^2 \pmod{1613}\) 秘密為\(f(0)=1234\)
3.有錯誤情況用Berlekamp-Welch演算法修正解碼
設\(e\)為發生錯誤數量，錯誤位置多項式\(\displaystyle E(x)=\sum_{i=0}^{e}e_i x^i\)，最高次方係數\(e_e=1\) (1)當\((a_i,b_i)\)為正確的點座標時　\(E(a_i)\ne 0\)(\(x=a_i\)代入錯誤位置多項式不為0(不符合)) 　\(b_i=f(a_i)\)(點座標\((a_i,b_i)\))符合\(f(x)\)多項式) (2)當\((a_i,b_i)\)為錯誤的點座標時　\(E(a_i)=0\)(\(x=a_i\)代入錯誤位置多項式為0(符合)) 　\(b_i\ne f(a_i)\)(點座標\((a_i,b_i)\)不符合\(f(x)\)多項式) \(b_i=f(a_i)\)，兩邊同乘\(E(a_i)\)得到\(b_iE(a_i)=f(a_i)E(a_i)\) 設\(Q(a_i)=f(a_i)E(a_i)\)得到\(b_iE(a_i)=Q(a_i)\)，\(b_iE(a_i)-Q(a_i)=0\) (1)當\((a_i,b_i)\)為正確的點座標時(\(E(a_i)\ne 0,b_i=f(a_i)\)) 　\(b_iE(a_i)-Q(a_i)=b_iE(a_i)-f(a_i)E(a_i)=E(a_i)(b_i-f(a_i))=0\)等式成立 (2)當\((a_i,b_i)\)為錯誤的點座標時(\(E(a_i)=0,b_i\ne f(a_i)\)) 　\(b_iE(a_i)-Q(a_i)=b_iE(a_i)-f(a_i)E(a_i)=0(b_i-f(a_i))=0\)等式成立代表點座標\((a_i,b_i)\)無論正確還是錯誤都符合\(b_iE(a_i)-Q(a_i)=0\) 將\(b_iE(a_i)-Q(a_i)=0\)，以\(\displaystyle E(a_i)=\sum_{i=0}^{e}e_i a_i^i\)，\(\displaystyle Q(a_i)=\sum_{i=0}^q q_ia_i^i\)展開 \(b_i(e_0+e_1a_i+e_2a_i^2+\ldots+e_ea_i^e)-(q_0+q_1a_i+q_2a_i^2+\ldots+q_qa_i^q)=0\) 其中\(q=n-e-1\)，又\(E(x)\)最高次方係數\(e_e=1\)，方程式改成 \(b_i(e_0+e_1a_i+e_2a_i^2+\ldots+e_{e_1}a_i^{e-1})-(q_0+q_1a_i+q_2a_i^2+\ldots+q_qa_i^q)=-b_ia_i^e\) 將各個點座標\((a_i,b_i)\)代入上式，解聯立方程組求\(e_0,e_1,\ldots,e_{e-1},q_0,q_2,\ldots,q_q\) \(E(x)\)有\(e\)個未知數，\(Q(x)=f(x)E(x)\)有\(k+e\)個未知數，需要\(n=e+(k+e)\)個方程式該演算法從假設最大可能錯誤數\(\displaystyle e =\Bigg\lfloor\;\frac{n-k}{2}\Bigg\rfloor\;\)開始。如果方程式無法求解，則將\(e\)減1並重複此過程，直到聯立方程組可以求出惟一解或\(e\)降至0，表示沒有找到錯誤。找到\(E(x)\)和\(Q(x)\)，解\(E(x)=0\)得到錯誤位置，計算\(\displaystyle f(x)=\frac{Q(x)}{E(x)}\)，秘密\(S=f(0)\)	有5個人聚在一起但不知道哪個人的子秘密是錯誤的 \((1,1494),(2,329),(3,123),(4,176),(5,1188)\)，(\((3,123)\)應為\((3,965)\)) \(\displaystyle e=\Bigg\lfloor\;\frac{5-3}{2}\Bigg\rfloor\;=1\)，最多可以修正1個錯誤錯誤位置多項式\(E(x)=e_0+x\)，只有1個錯誤為1次多項式，\(e_0\)為錯誤點的\(x\)坐標設\(Q(x)=E(x)f(x)\)次數為\(e+(k-1)=1+2=3\)次 \(Q(x)=q_0+q_1x+q_2x^2+q_3x^3\) 將\((a_i,b_i)=(1,1494),(2,329),(3,123),(4,176),(5,1188)\)代入\(b_i \cdot E(a_i)-Q(a_i)=0\) \(b_i(e_0+a_i)-(q_0+q_1a_1+q_2a_1^2+q_3a_1^3)\equiv 0\pmod{p}\) \(b_ie_0-(q_0+q_1a_1+q_2a_1^2+q_3a_1^3)\equiv -b_ia_i\pmod{p}\) \(\cases{1494e_0-(q_0+q_1\cdot 1+q_2 \cdot 1^2+q_3\cdot 1^3)\equiv -1494\cdot 1\cr 329e_0-(q_0+q_1\cdot 2+q_2 \cdot 2^2+q_3\cdot 2^3)\equiv -329\cdot 2\cr 123e_0-(q_0+q_1\cdot 3+q_2 \cdot 3^2+q_3\cdot 3^3)\equiv -123\cdot 3\cr 176e_0-(q_0+q_1\cdot 4+q_2 \cdot 4^2+q_3\cdot 4^3)\equiv -176\cdot 4\cr 1188e_0-(q_0+q_1\cdot 5+q_2 \cdot 5^2+q_3\cdot 5^3)\equiv -1188\cdot 5}\pmod{1613}\) 解聯立方程組，得到\(e_0=-3,q_0=-476,q_1=736,q_2=-116,q_3=94\) \(E(x)=-3+x\)，解\(E(x)=0\)，錯誤在\(x=3\) \(Q(x)=f(x)E(x)=f(x)(x-3)=-476+736x-116x^2+94x^3\pmod{1613}\) 使用綜合除法計算\(f(x)\) \(\frac{\matrix{94&-116&736&-476&\|3\cr 　&282&498&3702&\|　}}{\matrix{94&166&1234&\|3226&　}}\) 餘式\(3226\equiv 0\pmod{1613}\)是整除的 \(f(x)=1234+166x+94x^2\pmod{1613}\) \(f(3)=1234+166\cdot 3+94\cdot 3^2=2578\equiv 965\pmod{1613}\) 正確的子秘密為\((3,965)\) 秘密\(S=f(0)=1234\)

原始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。	假設\(b=(b_1,b_2,\ldots,b_k)\)是要分享的秘密，存在唯一一個Reed-solomon碼字(cdoeword)\(D\)，前\(k\)個就是密碼本身，即\(D_1=b_1,D_2=b_2,\ldots,D_k=b_k\)。事實上，\(D\)可以由Shamir方法的拉格朗日插值多項式或標準Reed-Solomon編碼演算法找到。只有剩下\(r-1-k\)個\(D_{k+1},\ldots,D_{r-1}\)可以分給參與者共享秘密，如前面所述，至少\(k\)個(未被竄改)才能還原秘密。
範例
設秘密\(S=1234567890\)非常長再找比\(S\)還大的質數\(p=1234567907\) \(f(x)=1234567890+15618435x+38443541x^2\pmod{p}\) 常數項\(a_0=S\)，係數\(a_1,a_2\)為小於\(p\)的任意整數 \((1,f(1))=(1,54061959)\) \((2,f(2))=(2,185011017)\) \((3,f(3))=(3,392847157)\) \((4,f(4))=(4,677570379)\) \((5,f(5))=(5,1039180683)\) \((6,f(6))=(6,243110162)\) 每位使用者所拿到的子秘密幾乎和原始秘密長度相同當三位使用者聚在一起，將各個子秘密\((3,f(3)),(4,f(4)),(6,f(6))\)利用拉格朗日插值多項式 \(\displaystyle f(x)=392847157\frac{(x-4)(x-6)}{(3-4)(3-6)}\) 　\(\displaystyle +677570379\frac{(x-3)(x-6)}{(4-3)(4-6)}\) 　\(\displaystyle +243110162\frac{(x-3)(x-4)}{(6-3)(6-4)}\pmod{p}\) \(f(x)=1234567890+15618435x+38443541x^2\pmod{p}\) 秘密\(S=f(0)=1234567890\)	將秘密\(1234567890\)拆成\(S=(0,1234),(1,567),(2,890)\) \(p=1613\) 利用拉格朗日插值多項式，產生通過\((0,1234),(1,567),(2,890)\)三點的二次多項式\(f(x)\) \(\displaystyle f(x)=1234\cdot \frac{(x-1)(x-2)}{(0-1)(0-2)}+567\cdot \frac{(x-0)(x-2)}{(1-0)(1-2)}+890\cdot \frac{(x-0)(x-1)}{(2-0)(2-1)}\pmod{1613}\) \(f(x)=1234+451x+495x^2\pmod{1613}\) 常數項\(a_0=S\)，係數\(a_1,a_2\)是根據拉格朗日插值多項式所產生的特定整數 \((3,f(3))=(3,590)\) \((4,f(4))=(4,1280)\) \((5,f(5))=(5,1347)\) \((6,f(6))=(6,791)\) \((7,f(7))=(7,1225)\) \((8,f(8))=(8,1036)\) 每位使用者所拿到的子秘密縮短許多當三位使用者聚在一起，將各個子秘密\((3,f(3)),(4,f(4)),(6,f(6))\)利用拉格朗日插值多項式 \(\displaystyle f(x)=590\frac{(x-4)(x-6)}{(3-4)(3-6)}+1280\frac{(x-3)(x-6)}{(4-3)(4-6)}+791\frac{(x-3)(x-4)}{(6-3)(6-4)}\pmod{1613}\) \(f(x)=1234+451x+495x^2\pmod{1613}\) \(f(0)=1234\)，\(f(1)=567\)，\(f(2)=890\) 合併秘密\(S=1234567890\)
安全性
若已知2個子秘密\((3,392847157),(4,677570379)\) 代入\(f(x)=a_0+a_1x+a_2x^2\pmod{p}\)得 \(\cases{392847157=a_0+3a_1+9a_2\cr 677570379=a_0+4a_1+16a_2}\) 兩式相減得\(284723222\equiv a_1+7a_2\pmod{1234567907}\) \(a_1,a_2\)為隨機整數，知道\(a_1\)和\(a_2\)的關係式對於求\(a_0=S\)沒有幫助。	若已知2個子秘密\((3,590),(4,1280)\) 代入\(f(x)=a_0+a_1x+a_2x^2\pmod{p}\)得 \(\cases{590=a_0+3a_1+9a_2\cr 1280=a_0+4a_1+16a_2}\) 兩式相減得\(690\equiv a_1+7a_2\pmod{1613}\) \(a_1,a_2\)本身就是祕密的一部分，知道\(a_1\)和\(a_2\)的關係式對於秘密空間的複雜度被大大降低。

子秘密\( V_i \)		秘密S	\( p_1 \)	\( p_2 \)	\( p_3 \)	\( p_4 \)	\( p_5 \)	\( p_6 \)	\( p_7 \)	\( p_8 \)	\( p_9 \)	\( p_{10} \)
\( V_1 \)	14293994	451	2				13	23			53
\( V_2 \)	5117046	451	2	3					31			61
\( V_3 \)	7312956	451		3	5			23		47
\( V_4 \)	25934755	451			5	7			31		53
\( V_5 \)	117664547	451				7	13			47		61