如何分攤秘密？
本節要介紹的是以色列密碼學家Adi Shamir在1979年提出的一個非常優雅高效的基於有限域上拉格朗日插值法的秘密分攤方法。Shamir最為傑出和廣為人知的貢獻是同Ron Rivest和Leonard Adleman一起建立了著名的RSA加密系統，他們因此獲得了2002年的圖靈獎。
十一、Shamir分攤法
Shamir分攤法的思想是相當簡單的：首先將需要分攤的秘密藏入一個k-1次多項式，需要知道秘密，就需要恢復出多項式；在n個（n>k）點上對多項式取值，這些值被分攤給n人；而只要其中任意的k個值，我們就可以通過拉格朗日插值法來恢復出原多項式，從而揭示出原始秘密。
讓我們來看一下具體方法。
和先前一樣，首先得固定秘密的範圍即一個整數N，而秘密s是0到N-1之間的某數。但現在我們對N有另外兩個要求。一是要求N必須大於參與分攤秘密的總人數。如果是在100個人之間分攤一個6位賬號密碼，那麼原來N=1000000已經大於100，沒有必要變動N；但如果是在100個人裡面分攤一個是非題的答案，也就是1比特的信息，那麼原來N可取2，現在則必須取大於100的數。二是要求N必須為素數，因為這次我們不但將在以N為模的同餘類之間做加減法，還要做乘除法，也即我們要在域GF(N)上運算。如果要分攤一個6位賬號密碼，原來N=1000000，現在就要取N為大於1000000的素數，比如可以取滿足這個要求的最小素數1000003。
現在用一個好的隨機數產生器產生k-1個0到N-1之間的整數，令它們為a1，a2，……，ak-1。考慮下面係數在GF(N)中的k-1次多項式：
P(x) = [ak-1]xk-1+……+[a2]x2+[a1]x+
其中表示以N為模的同餘類。接著計算出P([1])，P([2])，……，P([n])，把它們分別給n人，這就是分攤給他們的那部分秘密；同時也分別告訴每人他們是第幾人。（相當於給每個人一個二元組([t],P([t]))，但只有P([t])這部分被看作是秘密，每人對應的那個[t]不被看作是秘密，甚至可以是公開的。）我們看出為什麼前面要求N必須大於參與分攤秘密的總人數的目的，因為這樣才能使[1]，[2]，……，[n]都是在GF(N)中的不同的同餘類。更一般地，我們其實並不需要這n個取值點一定是[1]，[2]，……，[n]，只需這是GF(N)內n個不同於[0]的值就可以了。
如果有k個以上的人同意合作，我們只需任意選擇其中的k人，把分攤給他們的秘密收集起來，這相當於知道了多項式P在k個點上的值，於是可以用拉格朗日插值法來恢復出P，然後計算P([0])就得到了原秘密。
如果只有k-1個人同意合作，他們能得到什麼樣的關於原始秘密的結論？對於每一個可能的原始秘密，也即每一個可能的P([0])，我們都可以用它和這k-1個人所持有的P在另外k-1個點的值一起來使用拉格朗日插值法，得到一個多項式P 。因為對P的係數的隨機選取的原因，任何一個這樣插值出來的多項式P 是真正的P的可能性都是一樣的，而且P ([0])=。於是每個是真正的秘密的可能性也是一樣的。所以這k-1人無法更多地了解原始秘密。
我們可以看到，這個分攤秘密的方法是非常高效的，它只需要每個分攤秘密的人記住自己的編號（一般來說不會很大），和一個GF(N)中的元素，所需要的儲存空間和原秘密一樣。也許有人會指出在一開始我們需要增加N讓它成為一個素數，會增加所需的儲存空間。但根據伯特蘭-切比雪夫定理，對任何自然數m，我們總能在p和2p之間找到一個素數。即便在上面N為素數的要求下，需要將原來的N增加到2N-1，也只不過多增加1比特的空間而已，所以因為這個原因增加的儲存空間可以忽略不計。
最後讓我們具體看一個例子。本來應該舉一個100個人分攤秘密需至少80個人同意才能揭曉秘密的例子，但這得產生一個79次的多項式，並計算P在100個點上的值，用電腦倒是不麻煩，可寫出來沒法讀。所以我們退而求其次，舉一個10人分攤秘密需至少8人同意才能揭曉秘密的例子，被分攤的原始秘密則仍是一個6位賬號密碼。
按照前面所說，我們取N=1000003。令被分攤的秘密是123456。
用隨機數產生器產生7個0到1000002之間的隨機數，這裡舉例就用401993, 875845, 799228, 672942, 171533, 797326, 384241，得到多項式
P(x) = [401993]x7+[875845]x6+[799228]x5+[672942]x4+[171533]x3+[797326]x2+[384241]x+[123456]
在GF(N)內計算得到：
P([1]) = [226552]
P([2]) = [304611]
P([3]) = [448569]
P([4]) = [759237]
P([5]) = [232780]
P([6]) = [368644]
P([7]) = [538534]
P([8]) = [155130]
P([9]) = [679162]
P([10]) = [503465]
這就是分別分攤給第一到第十個人的秘密。
如果其中的8個人，比如是第三到第十人決定要揭開秘密，他們擁有上面所列的P([3])到P([10])的值，但沒有P([1])和P([2])。
按照上節拉格朗日插值法，我們要先計算以下8個多項式：
r1(x) = (x-[4])(x-[5])(x-[6])(x-[7])(x-[8])(x-[9])(x-[10])/(([3]-[4])([3]-[5])([3]-[6])([3]-[7])([3]-[8])([3]-[9])([3]-[10]))
r2(x) = (x-[3])(x-[5])(x-[6])(x-[7])(x-[8])(x-[9])(x-[10])/(([4]-[3])([4]-[5])([4]-[6])([4]-[7])([4]-[8])([4]-[9])([4]-[10]))
r3(x) = (x-[3])(x-[4])(x-[6])(x-[7])(x-[8])(x-[9])(x-[10])/(([5]-[3])([5]-[4])([5]-[6])([5]-[7])([5]-[8])([5]-[9])([5]-[10]))
r4(x) = (x-[3])(x-[4])(x-[5])(x-[7])(x-[8])(x-[9])(x-[10])/(([6]-[3])([6]-[4])([6]-[5])([6]-[7])([6]-[8])([6]-[9])([6]-[10]))
r5(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[8])(x-[9])(x-[10])/(([7]-[3])([7]-[4])([7]-[5])([7]-[6])([7]-[8])([7]-[9])([7]-[10]))
r6(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[7])(x-[9])(x-[10])/(([8]-[3])([8]-[4])([8]-[5])([8]-[6])([8]-[7])([8]-[9])([8]-[10]))
r7(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[7])(x-[8])(x-[10])/(([9]-[3])([9]-[4])([9]-[5])([9]-[6])([9]-[7])([9]-[8])([9]-[10]))
r8(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[7])(x-[8])(x-[9])/(([10]-[3])([10]-[4])([10]-[5])([10]-[6])([10]-[7])([10]-[8])([10]-[9]))
（注意到諸ri(x)的下標是獨立的，和十個人本身的編號無關。在重構原多項式P時，r1(x)到r8(x)將分別和第三到第十人拿的P([3])到P([10])的值相乘後再相加。）
為了計算簡單起見，考慮到我們想知道的秘密其實是最終的多項式P在[0]點的值P([0])，我們也只需計算上面這些多項式在[0]點的值：
r1([0])
= (-[4])(-[5])(-[6])(-[7])(-[8])(-[9])(-[10])/(([3]-[4])([3]-[5])([3]-[6])([3]-[7])([3]-[8])([3]-[9])([3]-[10]))
= [-604800]/[-5040]
r2([0])
= (-[3])(-[5])(-[6])(-[7])(-[8])(-[9])(-[10])/(([4]-[3])([4]-[5])([4]-[6])([4]-[7])([4]-[8])([4]-[9])([4]-[10]))
= [-453600]/[720]
r3([0])
= (-[3])(-[4])(-[6])(-[7])(-[8])(-[9])(-[10])/(([5]-[3])([5]-[4])([5]-[6])([5]-[7])([5]-[8])([5]-[9])([5]-[10]))
= [-362880]/[-240]
r4([0])
= (-[3])(-[4])(-[5])(-[7])(-[8])(-[9])(-[10])/(([6]-[3])([6]-[4])([6]-[5])([6]-[7])([6]-[8])([6]-[9])([6]-[10]))
= [-302400]/[144]
r5([0])
= (-[3])(-[4])(-[5])(-[6])(-[8])(-[9])(-[10])/(([7]-[3])([7]-[4])([7]-[5])([7]-[6])([7]-[8])([7]-[9])([7]-[10]))
= [-259200]/[-144]
r6([0])
= (-[3])(-[4])(-[5])(-[6])(-[7])(-[9])(-[10])/(([8]-[3])([8]-[4])([8]-[5])([8]-[6])([8]-[7])([8]-[9])([8]-[10]))
= [-226800]/[240]
r7([0])
= (-[3])(-[4])(-[5])(-[6])(-[7])(-[8])(-[10])/(([9]-[3])([9]-[4])([9]-[5])([9]-[6])([9]-[7])([9]-[8])([9]-[10]))
= [-201600]/[-720]
r8([0])
= (-[3])(-[4])(-[5])(-[6])(-[7])(-[8])(-[9])/(([10]-[3])([10]-[4])([10]-[5])([10]-[6])([10]-[7])([10]-[8])([10]-[9]))
= [-181440]/[5040]
讀者可以自行驗證，在GF(1000003)中我們有：[1]/[144]=[701391]，[1]/[240]=[220834]，[1]/[720]=[740280]，[1]/[5040]=[534327]，於是
= [-604800]/[-5040] = [-604800][-534327] = [323160969600]
= [120]
= [-453600]/[720] = [-453600][740280] = [-335791008000]
= [999373]
= [-362880]/[-240] = [-362880][-220834] = [80136241920]
= [1512]
= [-302400]/[144] = [-302400][701391] = [-212100638400]
= [997903]
= [-259200]/[-144] = [-259200][-701391] = [181800547200]
= [1800]
= [-226800]/[240] = [-226800][220834] = [-50085151200]
= [999058]
= [-201600]/[-720] = [-201600][-740280] = [149240448000]
= [280]
= [-181440]/[5040] = [-181440][534327] = [-96948290880]
= [999967]
於是最後的秘密就可以通過第三到第十人知道的P([3])，P([4])，……，P([10])和上述的諸ri([0])的值求出：
P([0])
= P([3])r1([0])+P([4])r2([0])+P([5])r3([0])+P([6])r4([0])+P([7])r5([0])+P([8])r6([0])+P([9])r7([0])+P([10])r8([0])
= [448569][120]+[759237][999373]+[232780][1512]+[368644][997903]+[538534][1800]+[155130][999058]+[679162][280]+[503465][999967]
= [1786629483328]
= [123456]
正是原始秘密。（待續）
※從《鹿鼎記》說起，看如何分攤秘密
※如何約會更浪漫？秘密「妝」這裡……
※塔羅牌分析：情人「不敢對你說」的秘密是什麼？
※招聘的秘密：HR如何看簡歷？
※火箭只有三分？錯！秘密武器卻遭忽視！
※如何破解長壽的秘密？先推掉無聊的飯局吧
※乾陵里究竟藏了什么秘密令郭沫若如此神往？
※乾陵里究竟藏了什么秘密令郭沫若如此神往？
※秘密
※揭秘！項羽為何火燒阿房宮 隱藏什麼不為人知秘密？
※揭秘：「沉香」背後哪些不為人知的秘密？
※黑夜裡還有什麼秘密？
※和女人不分手的秘密！
※你的眼睛泄露秘密了嗎？
※火影里不為人知的秘密？半分吐槽，半分真實
※皇帝女人偷情會如何 揭秘清福臨老婆 那些不為人知的偷情秘密
※結婚為什麼要藏鞋？揭秘你不知道的婚禮秘密！
※真瞎？索隆左眼的秘密
※B超單上隱藏的秘密，教你一分鐘讀懂它！