第十九個知識點：Shamir密鑰交換場景

Shamir密鑰交換場景是一個被Adi Shamir提出的算法.算法允許多方分割一個密碼,例如一個密鑰.當足夠多的秘密結合起來,整個密鑰就被計算出來了.

正式的說,如果我們有秘密\(S\)和\(n\)方,我們能把\(S\)劃分成\(n\)方.然後把它們分發給不同的組織.通過這樣發送的密鑰有一個限定值\(k\),如果密鑰\(S\)的\(k\)數量的部分被收集到,那麼就可以計算出\(S\).如果\(k-1\)或者更少的密鑰被收集,那麼\(S\)将無法被計算.這個場景就叫做(\(k,n\))限定場景.

解釋為什麼場景能夠被這樣構造的最好方式就是通過一個例子.假設我們想要把分割秘密\(S = 1425\).分割成5部分(\(n = 5\)).同時需要3方才能允許密鑰(\(S\))被計算出來.首先我們構造一個多項式\(f(x)\).它的階為(\(k-1 = 2\)).系數是随機的.假如說是\(a_1 = 64, a_2 = 112\).和一個常數\(S\).

\[f(x) = S + a_1x + a_2x^2 = 1425 + 64x + 112x^2

\]

從這個多項式中我們可以看到,我們可以構造5個點.這些點分發給不同的組織.

\[P_0=(1,1601),P_1=(2,2001),P_2=(3,2625),P_3=(4,3473),P_4=(5,4545)

如果我們假設我們知道5個點中的3個點.我們能夠計算出這個多項式的系數.通過3個三元一次多項式.

就上面的例子來看,這個方法工作的很好.但是,竊聽者也能夠收集更多關于秘密的資訊.因為上面我們已經工作在一個有理數的算數.然而，如果我們在有限域内工作(是以秘密和多項式是在q大小的域上定義的)，那麼如果任何兩個或更少的參與方走到一起，他們對秘密一無所知。

這是因為這樣的兩方假如說組織一群組織二,然後密鑰的值S來源于這個域.那麼就有一個總有一個在這個多項式域中定義的值:(0,S'), (2,2001 mod q) and (3,2625 mod q).

[1] - http://en.wikipedia.org/wiki/Polynomial

[2] - http://en.wikipedia.org/wiki/Lagrange_polynomial

[3] - http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing