應(yīng)用密碼學(xué)---淺談秘密分割與共享[課件]

1、淺談秘密分割作者：蚍蜉撼青松主頁主頁：http:/ 綱 一、最簡單的秘密分割方案一、最簡單的秘密分割方案 二、秘密分割門限方案二、秘密分割門限方案 Shamir門限方案門限方案 Asmuth-Bloom門限方案門限方案 三、門限數(shù)字簽名方案三、門限數(shù)字簽名方案基于基于ElGamal體制的門限數(shù)字簽名方案體制的門限數(shù)字簽名方案基于基于Schnorr體制的門限數(shù)字簽名方案體制的門限數(shù)字簽名方案一、最簡單的秘密分割方案一、最簡單的秘密分割方案可口可樂公司的煩惱秘密分割的概念秘密分割的概念2人秘密分割的數(shù)學(xué)實(shí)現(xiàn)人秘密分割的數(shù)學(xué)實(shí)現(xiàn)共享人數(shù)為共享人數(shù)為n(n2)時(shí)的推廣時(shí)的推廣安全性分析安全性分析秘密分

2、割 有各種方法把消息分割成許多碎片。每一片本身有各種方法把消息分割成許多碎片。每一片本身并不代表什么，但把這些碎片放到一塊，消息就會(huì)重并不代表什么，但把這些碎片放到一塊，消息就會(huì)重現(xiàn)出來?，F(xiàn)出來。 如前例，消息是一個(gè)飲品配方，每一個(gè)董事有一如前例，消息是一個(gè)飲品配方，每一個(gè)董事有一部分，那么只有他們放在一起才能還原這種配方。如部分，那么只有他們放在一起才能還原這種配方。如果任意一董事撤股或被競爭對手收買而帶走一部分配果任意一董事撤股或被競爭對手收買而帶走一部分配方碎片，這個(gè)碎片本身是毫無用處的。方碎片，這個(gè)碎片本身是毫無用處的。分割的一個(gè)簡單數(shù)學(xué)實(shí)現(xiàn) 以兩個(gè)人之間的消息分割為例，下面是Tren

3、t把一消息分割給Alice和Bob的一個(gè)協(xié)議：（1）Trent產(chǎn)生一隨機(jī)比特串產(chǎn)生一隨機(jī)比特串R，和消息，和消息M一樣長。一樣長。（2）Trent用用R異或異或M得到得到S：M R = S（3）Trent把把R給給Alice，將，將S給給Bob。 為了重構(gòu)此消息，Alice和Bob只需一起做一步：（4）Alice和和Bob將他們的消息異或就可得到此消息：將他們的消息異或就可得到此消息：R S = M推廣：從2人分割到n人分割 這種方案推廣到多人是很容易的。為了在多個(gè)人中分割一秘密消息，將此消息與多個(gè)隨機(jī)比特異或成混合物即可。在下面的例子中，Trent把信息劃分成四部分：1）Trent產(chǎn)生三個(gè)與

4、消息產(chǎn)生三個(gè)與消息M一樣長的隨機(jī)比特串一樣長的隨機(jī)比特串R,S,T；2）Trent用這三個(gè)隨機(jī)串和用這三個(gè)隨機(jī)串和M異或得到異或得到U：M R S T = U3）Trent將將R給給Alice，S給給Bob，T給給Carol，U給給Dave。 Alice、Bob和Carol、Dave在一起可以重構(gòu)此消息：4）Alice、Bob、Carol和和Dave一起計(jì)算：一起計(jì)算：R S T U = M安全性分析1-保密性好 如果做得適當(dāng)，這種技術(shù)是絕對安全的。因?yàn)槊咳绻龅眠m當(dāng)，這種技術(shù)是絕對安全的。因?yàn)槊恳粋€(gè)人所持有的部分消息本身是毫無價(jià)值的。一個(gè)人所持有的部分消息本身是毫無價(jià)值的。 前述協(xié)議的實(shí)質(zhì)，

5、是前述協(xié)議的實(shí)質(zhì)，是TrentTrent用用一次一密一次一密的方式加密的方式加密消息，并將密文給一人，密鑰給另一人。消息，并將密文給一人，密鑰給另一人。 一次一密加密方式，它們具有完全的保密性。無一次一密加密方式，它們具有完全的保密性。無論有多大計(jì)算能力都不能根據(jù)消息碎片之一就確定出論有多大計(jì)算能力都不能根據(jù)消息碎片之一就確定出秘密消息來。秘密消息來。安全性分析2-缺陷過于依賴秘密分割者過于依賴秘密分割者。 這是一個(gè)裁決協(xié)議，這是一個(gè)裁決協(xié)議，TrentTrent有絕對的權(quán)力，并且能夠做他想做的任何事情。有絕對的權(quán)力，并且能夠做他想做的任何事情。他可以把毫無意義的東西拿出來，并且申明是秘密的他

6、可以把毫無意義的東西拿出來，并且申明是秘密的有效部分。在他們將秘密重構(gòu)出來之前，沒有人能夠有效部分。在他們將秘密重構(gòu)出來之前，沒有人能夠知道它。知道它?？煽啃蕴涂煽啃蕴汀?如果任何一部分丟失了，并且如果任何一部分丟失了，并且TrentTrent又不在，就等于將整個(gè)秘密消息丟掉了。又不在，就等于將整個(gè)秘密消息丟掉了。QUESTION: 怎么才能在保證秘密消息的保密性的同時(shí)提升其可靠性呢？秘密分割秘密分割門限方案門限方案SOLUTION:二、秘密分割門限方案2.1 概述概述2.2 Shamir門限方案門限方案2.3 Asmuth-Bloom門限方案門限方案再來看兩個(gè)有意思的問題美軍核彈發(fā)射控制

7、問題花旗銀行金庫控制問題 把一個(gè)秘密把一個(gè)秘密s分為分為n個(gè)子密鑰個(gè)子密鑰s1,s2,sn,并將每個(gè)子并將每個(gè)子密鑰（也稱為密鑰（也稱為shadow影子影子或或share份額份額）安全分配給）安全分配給n個(gè)參與者持有，使得個(gè)參與者持有，使得由由k k個(gè)或多于個(gè)或多于k k個(gè)參與者所持有的部分信息可重構(gòu)個(gè)參與者所持有的部分信息可重構(gòu)s s；由少于由少于k k個(gè)參與者所持有的部分信息無法重構(gòu)個(gè)參與者所持有的部分信息無法重構(gòu)s s。 這種方案被稱之為這種方案被稱之為(k,n)秘密分割門限方案秘密分割門限方案（k稱為稱為門門限值限值），也簡稱為也簡稱為門限方案門限方案、閾值方案閾值方案。問題的抽象解決

8、方案問題的抽象解決方案完善條件完善條件： 如果少于如果少于k個(gè)參與者所持有的個(gè)參與者所持有的部分信息得不到秘密部分信息得不到秘密s的任何信息的任何信息，則稱該門限方案是，則稱該門限方案是完善完善的的。門限值門限值 K 的設(shè)定的設(shè)定 K的具體取值其實(shí)是由方案的保密性要求和可靠性要求的具體取值其實(shí)是由方案的保密性要求和可靠性要求共同決定的共同決定的。高門限，提供高安全性（指保密性），低可靠性高門限，提供高安全性（指保密性），低可靠性低門限，提供低安全性（指保密性），高可靠性低門限，提供低安全性（指保密性），高可靠性 以美軍核彈發(fā)射控制問題為例，以美軍核彈發(fā)射控制問題為例，K的值越大，那么核的值越大

9、，那么核彈發(fā)射受到瘋子干擾的程度就越小，核彈發(fā)射控制系統(tǒng)彈發(fā)射受到瘋子干擾的程度就越小，核彈發(fā)射控制系統(tǒng)的安全性就越高，但同時(shí)遇到緊急情況時(shí)因?yàn)橛腥巳毕陌踩跃驮礁?，但同時(shí)遇到緊急情況時(shí)因?yàn)橛腥巳毕斐珊藦棢o法及時(shí)發(fā)射的概率就越大；反之亦然。而造成核彈無法及時(shí)發(fā)射的概率就越大；反之亦然。2.3 Shamir門限方案l作者：作者：Adi Shamirl基于基于多項(xiàng)式的拉格朗日插值公式多項(xiàng)式的拉格朗日插值公式ShamirShamir門限方案的原理門限方案的原理 對于有限域?qū)τ谟邢抻?GF(q) 上的一個(gè)上的一個(gè) k-1 次多項(xiàng)式次多項(xiàng)式 f(x) ,若把若把秘密秘密s取做取做 f(0) ，將將

10、 f( (xi i)()(i=1,=1,n) ) 作為作為 n 個(gè)個(gè)shadow, ,那么利用其中任意那么利用其中任意 k 個(gè)個(gè)shadow可以重構(gòu)可以重構(gòu) f(x) ，從而可，從而可以得到秘密以得到秘密s。ShamirShamir門限方案門限方案1.系統(tǒng)初始化系統(tǒng)初始化 有限域有限域GF(q),q為大素?cái)?shù)，為大素?cái)?shù)，qn+1。秘密。秘密s是是GF(q)0上上均勻選取的隨機(jī)數(shù)，表示為均勻選取的隨機(jī)數(shù)，表示為sRGF(q)0. k-1個(gè)系數(shù)個(gè)系數(shù)a1,a2,ak-1選取選取ai RGF(q)0.在在GF(q)上構(gòu)造一個(gè)上構(gòu)造一個(gè)k-1次多項(xiàng)式：次多項(xiàng)式： f(x)= s +a1x+ak-1xk-

11、1秘密分發(fā)秘密分發(fā) N個(gè)參與者個(gè)參與者P1,Pn，Pi的的Shadow為（為（i, f (i)）。）。3. 秘密重構(gòu)秘密重構(gòu) 任意任意k個(gè)參與者得到秘密，可使用個(gè)參與者得到秘密，可使用(il,f(il)|l=1,k構(gòu)造構(gòu)造方程組，從而算出方程組，從而算出f(x)。)()()()()()(11101111110kkkkkkkifiaiaaifiaiaa多項(xiàng)式的第二種重構(gòu)多項(xiàng)式的第二種重構(gòu)由由LagrangeLagrange插值公式插值公式)(mod)()()(11qiiixifxfkjkjllljlj)(mod)() 1(111qiiiifskjkjllljljkShamirShamir門限方案

12、的安全性分析門限方案的安全性分析 如果如果k-1-1個(gè)參與者想獲得個(gè)參與者想獲得s,可構(gòu)造可構(gòu)造k-1-1個(gè)方程，有個(gè)方程，有k個(gè)未知量。個(gè)未知量。 對任一對任一s0 0, ,設(shè)設(shè)f(0)= (0)= s0.0.這樣可以得到這樣可以得到第第k個(gè)方程，得到個(gè)方程，得到f( (x) )。 對每個(gè)對每個(gè)s s0 0都有唯一的多項(xiàng)式滿足，所都有唯一的多項(xiàng)式滿足，所有由有由k-1-1個(gè)個(gè)shadowshadow得不到任何得不到任何s的信息。的信息。因此此方案是完善的。因此此方案是完善的。ShamirShamir門限方案的主要特點(diǎn)門限方案的主要特點(diǎn)主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)：（1）是完善的門限方案；）是完善的門限

13、方案；（2）每個(gè)份額的大小與秘密值的大小相近；）每個(gè)份額的大小與秘密值的大小相近；（3）易于擴(kuò)充新用戶，即計(jì)算要分配的新份額不影響原）易于擴(kuò)充新用戶，即計(jì)算要分配的新份額不影響原來的各個(gè)份額。來的各個(gè)份額。（4）安全性不依賴于未經(jīng)證明的假設(shè)。）安全性不依賴于未經(jīng)證明的假設(shè)。主要缺點(diǎn)主要缺點(diǎn)：（5）門限值固定）門限值固定(即不區(qū)分參與者即不區(qū)分參與者)；（6）秘密分發(fā)者知道參與者的份額；）秘密分發(fā)者知道參與者的份額；（7）不能防止秘密分發(fā)者和參與者的欺詐。）不能防止秘密分發(fā)者和參與者的欺詐。ShamirShamir門限方案的示例門限方案的示例【例例】設(shè)設(shè) k=3，n=5，q=19，s=11。隨機(jī)

14、選隨機(jī)選a1=2，a2=7 使使 f(x)=7x2+2x11 mod 19 計(jì)算計(jì)算f (1)=1，f(2)=5，f(3)=4，f(4)=17，f(5)=6將將i，f(i)(i=1，2，3，4，5)分發(fā)給五個(gè)用戶。分發(fā)給五個(gè)用戶。1127)35)(25()3)(2(6)53)(23()5)(2(4)52)(32()5)(3(5)(2xxxxxxxxxf若已知若已知f(2)，f(3)，f(5)，重構(gòu)，重構(gòu)f(x)如下：如下：2.2 Asmuth-Bloom門限方案l作者：作者：Asmuth-Blooml基于基于中國剩余定理中國剩余定理舉例引入舉例引入任何一個(gè)方程無法確定x任何兩個(gè)方程可唯一確定x

15、x 9 (mod 13)顯然不滿足顯然不滿足,其他一樣其他一樣x 2 (mod 9)x 8 (mod 11)x 74 (mod 99)x 2 (mod 9)x 8 (mod 11)x 9 (mod 13)x 74 (mod 1287)x 2 (mod 9)x 8 (mod 11)x 9 (mod 13)13 x m mn nmmn-1n-1mmn-n-t t+2+2n S S是秘密是秘密, ,滿足滿足 m1m2m t s mnmn-1mn-t+2（等價(jià)：（等價(jià)：s s 大于任意大于任意 t-1 t-1 個(gè)個(gè)mmi i的乘積的乘積 s s 小于任意小于任意 t t 個(gè)個(gè)mmi i的乘積的乘積 ）

16、此時(shí)，此時(shí)，可構(gòu)造可構(gòu)造( (t t,n),n)門限方案。門限方案。簡化的簡化的Asmuth-Bloom門限方案門限方案u子密鑰的分發(fā)子密鑰的分發(fā)n計(jì)算計(jì)算 si = s(mod mi) (i=1, N)， （mi,si）為一子密鑰為一子密鑰. . u密鑰的恢復(fù)密鑰的恢復(fù)n當(dāng)當(dāng)k k個(gè)參與者提供子密鑰時(shí)，可建立方程組個(gè)參與者提供子密鑰時(shí)，可建立方程組n由中國剩余定理可以求得由中國剩余定理可以求得 s s s s mod N mod N ，NN為為k k個(gè)個(gè)mi的乘積的乘積顯然，當(dāng)顯然，當(dāng) s= t,則由系統(tǒng)初始化條件則由系統(tǒng)初始化條件因?yàn)橐驗(yàn)閟小于任意小于任意 t 個(gè)個(gè)mi的乘積，所以的乘積，

17、所以sN. .故，故，s s mod N 的解唯一確定。的解唯一確定。n若若 k N故，故，s s mod N 的解無法確定。的解無法確定。簡化的簡化的Asmuth-Bloom門限方案門限方案(9,2),(11,8),(13,9)(9,2),(11,8),(13,9)構(gòu)成構(gòu)成（2,32,3）門限方案）門限方案s 2 (mod 9)s 8 (mod 11)s 9 (mod 13)方案舉例方案舉例例：例：k=2,n=3, mk=2,n=3, m1 1=9,m=9,m2 2=11,m=11,m3 3=13=13，m m1 1m m2 2=99=99ss13=m13=m3,3, 此范圍選取此范圍選取s

18、=74s=74。 子秘密分發(fā)：子秘密分發(fā)： 若已知若已知(9,2),(11,8)，可建立方程組，可建立方程組 解得解得s (1152958) mod 99 74,故故s=74s 2 (mod 9)s 8 (mod 11)安全性分析安全性分析 此方法存在的欺騙問題包括在重建階段的參此方法存在的欺騙問題包括在重建階段的參與者欺騙與分割階段的分派者欺騙。與者欺騙與分割階段的分派者欺騙。 參與者欺騙是指參與者可能丟出假的子秘密，參與者欺騙是指參與者可能丟出假的子秘密，使得只有他自己能解出共享的秘密，而其它使得只有他自己能解出共享的秘密，而其它人無法解出該秘密。人無法解出該秘密。 分派者欺騙是指分派者可

19、能把假的子秘密給分派者欺騙是指分派者可能把假的子秘密給參與者，使得該參與者無法在日后重建共享參與者，使得該參與者無法在日后重建共享的秘密。的秘密。 解決方案包括子秘密應(yīng)具備可驗(yàn)證性解決方案包括子秘密應(yīng)具備可驗(yàn)證性(verifiable)(verifiable)與通過數(shù)字簽名解決。與通過數(shù)字簽名解決。三、門限數(shù)字簽名方案3.1 概述概述3.2 基于基于Schnorr體制的體制的(t,n)門限簽名方案門限簽名方案3.3 基于基于ElGamal體制的體制的(t,n)門限簽名方案門限簽名方案（t,nt,n）門限簽名是指，群體的簽名密鑰被所有）門限簽名是指，群體的簽名密鑰被所有n n個(gè)成員共享，使得任意

20、不少于個(gè)成員共享，使得任意不少于t t個(gè)成員的子集個(gè)成員的子集可以代表群體產(chǎn)生簽名，而任意少于可以代表群體產(chǎn)生簽名，而任意少于t t個(gè)成員的個(gè)成員的子集不能代表群體產(chǎn)生簽名；同時(shí)任何人都可子集不能代表群體產(chǎn)生簽名；同時(shí)任何人都可以利用群的唯一公鑰，驗(yàn)證簽名的正確性。以利用群的唯一公鑰，驗(yàn)證簽名的正確性。總經(jīng)理總經(jīng)理n位副總經(jīng)理位副總經(jīng)理已簽名文件已簽名文件未簽名文件未簽名文件t位經(jīng)理簽名位經(jīng)理簽名3.3 基于Schnorr體制的(t,n)門限數(shù)字簽名方案Schnorr數(shù)字簽名方案基本思路：基本的簽名方案參照Schnorr數(shù)字簽名方案；簽名用的私鑰 x 不再單獨(dú)分發(fā)給個(gè)人，而是作為一個(gè)共享秘密，

21、分割后發(fā)放給 n 個(gè)成員；分發(fā)時(shí)采用Shamir等 (t,n) 秘密分割門限方案，由于私鑰 x 的重構(gòu)需要滿足門限條件，故此有效簽名的產(chǎn)生也滿足門限條件。方案實(shí)現(xiàn)-1.系統(tǒng)初始化大素?cái)?shù)p和q滿足 q|(p-1)，q2160是整數(shù)，p2512是整數(shù)，確保在Zp中求解離散對數(shù)的困難性; gZp，且滿足gq=1(mod p)，g1; h為單向哈希函數(shù)。 有限域GF(w),w為大素?cái)?shù)，wn+1(n為系統(tǒng)參與者數(shù))。系統(tǒng)私鑰系統(tǒng)私鑰：分發(fā)者在GF(q)0上均勻選取隨機(jī)數(shù) s 作為私鑰,且滿足1sq，保密。系統(tǒng)公鑰系統(tǒng)公鑰：分發(fā)者計(jì)算y=gs(mod p)作為公鑰，公開。p、q、g、w作為系統(tǒng)參數(shù)，供所有

22、用戶使用，在系統(tǒng)內(nèi)公開。方案實(shí)現(xiàn)-2.成員子密鑰分發(fā)在GF(w)上構(gòu)造一個(gè)k-1次多項(xiàng)式：f(x)= s + a1x + + ak-1xk-1,其中 k-1 個(gè)系數(shù)a1,a2,ak-1選取ai RGF(w)0設(shè)n個(gè)參與者為P1,P2,Pn,身份標(biāo)識(shí)為i1,i2,in。分發(fā)者利用ik(1=k=n)和f(x)計(jì)算f(ik)，并將結(jié)果f(ik)秘密分發(fā)給ik，作為其子密鑰。方案實(shí)現(xiàn)-3.簽名過程對于一個(gè)待簽名消息m，可信中心選擇t個(gè)參與者：Pj1,Pj2,Pjt。由t個(gè)參與者提供的私鑰f(ijk)，根據(jù)拉格朗日插值公式可以計(jì)算出系統(tǒng)私鑰s；可信中心按照與系統(tǒng)私鑰s相同的條件生成一個(gè)隨機(jī)數(shù)K，計(jì)算出

23、r=gK mod p令 e=h(r,m)，求出 u=(K-s*e) mod p(e,u)即為系統(tǒng)對m的簽名。 方案實(shí)現(xiàn)-4.驗(yàn)證過程接收者收到消息m和簽名(e,u)。 先計(jì)算r=guye(mod p)，然后計(jì)算e=h(r，m)，檢驗(yàn)e=e是否成立。 如果成立，則簽名有效; 否則，簽名無效。若(e，u)為合法簽名，則有g(shù)uye=gk-xegxe=gk=r(mod p) 所以當(dāng)簽名有效時(shí)，上式成立，從而說明驗(yàn)證過程是正確的。3.2 基于ElGamal體制的(t,n)門限數(shù)字簽名方案ElGamal數(shù)字簽名方案可信第三方可信第三方簽名合成者簽名合成者成員成員謝謝觀看！附 錄可口可樂公司的煩惱 假設(shè)假設(shè)

24、Coca-ColaCoca-Cola公司最近新研發(fā)出了一種特別的飲品，公司最近新研發(fā)出了一種特別的飲品，飲品的配方將由公司董事會(huì)負(fù)責(zé)保管。飲品的配方將由公司董事會(huì)負(fù)責(zé)保管。 把配方交給某位董事而忽略其他董事？當(dāng)然不行，把配方交給某位董事而忽略其他董事？當(dāng)然不行，董事會(huì)的成員都是平等的，每個(gè)人都應(yīng)該享有保管權(quán)利。董事會(huì)的成員都是平等的，每個(gè)人都應(yīng)該享有保管權(quán)利。 那么把配方給每位董事都發(fā)一份嗎？不，絕對不行，那么把配方給每位董事都發(fā)一份嗎？不，絕對不行，萬一有一位董事被競爭對手收買了怎么辦？配方將被泄萬一有一位董事被競爭對手收買了怎么辦？配方將被泄露，特別的飲品將不再特別露，特別的飲品將不再特別

25、 董事會(huì)為此爭論不休，煩惱之極！董事會(huì)為此爭論不休，煩惱之極！如果你是公司的安全顧問，你該怎么為如果你是公司的安全顧問，你該怎么為你的你的bossboss們解憂？們解憂？返回返回美軍核彈發(fā)射控制問題 你正在為核導(dǎo)彈設(shè)計(jì)發(fā)射裝置，導(dǎo)彈的發(fā)射權(quán)力你正在為核導(dǎo)彈設(shè)計(jì)發(fā)射裝置，導(dǎo)彈的發(fā)射權(quán)力將交給五位官員。但五個(gè)官員中潛藏有至多兩個(gè)瘋子，將交給五位官員。但五個(gè)官員中潛藏有至多兩個(gè)瘋子，而瘋子們沒理由得想要轟炸多倫多。而瘋子們沒理由得想要轟炸多倫多。 為了不會(huì)因?yàn)榀傋觽兊氖Э囟l(fā)生一起多倫多炮為了不會(huì)因?yàn)榀傋觽兊氖Э囟l(fā)生一起多倫多炮轟事件，你確信當(dāng)僅有瘋子在場的情況下是不應(yīng)擁有轟事件，你確信當(dāng)僅有瘋子

26、在場的情況下是不應(yīng)擁有啟動(dòng)導(dǎo)彈發(fā)射權(quán)力的。啟動(dòng)導(dǎo)彈發(fā)射權(quán)力的。 當(dāng)然，出于對合眾國安全的考慮，你當(dāng)然，出于對合眾國安全的考慮，你同樣必須保證在有個(gè)別官員休假的情況下，同樣必須保證在有個(gè)別官員休假的情況下，我們照樣能夠啟動(dòng)導(dǎo)彈發(fā)射。我們照樣能夠啟動(dòng)導(dǎo)彈發(fā)射。 求發(fā)射裝置的控制方案設(shè)計(jì)。求發(fā)射裝置的控制方案設(shè)計(jì)?？煽诳蓸放浞奖９軉栴} Coca-Cola公司的董事會(huì)有12位董事，他們想保護(hù)可樂的配方。他們不希望每個(gè)董事都擁有獨(dú)立取得配方的權(quán)利，因?yàn)檫@樣的話配方的秘密很容易泄露。而當(dāng)所有董事都在場的時(shí)候，則可以順利取得配方。 一旦處于緊急的情況下，董事會(huì)需要及時(shí)取得配方。但總有各種意外導(dǎo)致有的董事來不

27、了，從而導(dǎo)致配方無法取出。為此董事會(huì)希望有一種機(jī)制，使得只要同時(shí)有5位董事在場就能取得配方，而不用等所有人到齊。 作為公司的安全維護(hù)人員，你要怎樣設(shè)計(jì)才能達(dá)到董事們的要求？花旗銀行金庫開啟問題 花旗銀行某支行有一位正行長和五位副行長，要對花旗銀行某支行有一位正行長和五位副行長，要對其某下屬金庫實(shí)施開啟控制。其某下屬金庫實(shí)施開啟控制。 如果銀行每位正副行長都有可以打開金庫的鑰匙，如果銀行每位正副行長都有可以打開金庫的鑰匙，雖然很方便但卻極不安全；雖然很方便但卻極不安全； 反之，如果要求所有行長到齊并同時(shí)使用各自的鑰反之，如果要求所有行長到齊并同時(shí)使用各自的鑰匙才能打開金庫，雖然安全卻極不可靠。因

28、為我們不能匙才能打開金庫，雖然安全卻極不可靠。因?yàn)槲覀儾荒芘懦澄恍虚L由于航空或交通意外而躺在醫(yī)院某個(gè)角落排除某位行長由于航空或交通意外而躺在醫(yī)院某個(gè)角落的可能的可能 如果你是該支行的安全維護(hù)人員，如果你是該支行的安全維護(hù)人員，你該怎樣設(shè)計(jì)金庫開啟控制方案？你該怎樣設(shè)計(jì)金庫開啟控制方案？返回返回 設(shè)設(shè)(x1,y1),(xk,yk)是平面上是平面上k個(gè)點(diǎn)構(gòu)個(gè)點(diǎn)構(gòu)成的點(diǎn)集，其中成的點(diǎn)集，其中xi(i=1,k,)各不相同，那么各不相同，那么在平面上存在唯一的在平面上存在唯一的k-1次多項(xiàng)式次多項(xiàng)式f(x)通過這通過這k個(gè)點(diǎn)。個(gè)點(diǎn)。 且有如下關(guān)系式：且有如下關(guān)系式：)(mod)()()(11qiiix

29、ifxfkjkjllljlj拉格朗日插值公式拉格朗日插值公式返回返回設(shè)設(shè)m1, m2, mk是是 k 個(gè)兩兩互素的正整數(shù)，個(gè)兩兩互素的正整數(shù)，并記并記 M = m1 m2 mk，Mi= M/mi， 則同余方程組：則同余方程組：在模在模 M 同余的意義下同余的意義下有唯一解有唯一解： x M1 M1 b1 M2 M2 b2 Mk Mk bk mod M （2）其中其中 Mi Mi 1 mod mi中國剩余定理，中國剩余定理，CRTChina Residue Theorem )(mod.)(mod)(mod2211kkmbxmbxmbx（1）返回返回ElGamal數(shù)字簽名算法描述：數(shù)字簽名算法描述

30、： (1) 系統(tǒng)初始化：系統(tǒng)初始化：選取大素?cái)?shù)選取大素?cái)?shù) p， Zp*是一個(gè)本原元。是一個(gè)本原元。 p， 作為系統(tǒng)參數(shù)公開。作為系統(tǒng)參數(shù)公開。 每個(gè)用戶每個(gè)用戶U隨機(jī)選取整數(shù)隨機(jī)選取整數(shù) dU，2 dU p2。 計(jì)算：計(jì)算： eU = dU mod p 將將 eU 作為用戶作為用戶U的公開密鑰，的公開密鑰， dU作為用于簽名的秘作為用于簽名的秘密密鑰，并嚴(yán)格保密。密密鑰，并嚴(yán)格保密。(2) 簽名變換：簽名變換： 給定消息給定消息M，簽名方，簽名方A將進(jìn)行下述簽名計(jì)算：將進(jìn)行下述簽名計(jì)算： 選擇隨機(jī)數(shù)選擇隨機(jī)數(shù) rZp* ，且，且r與（與（p1)互素互素 用單向散列函數(shù)用單向散列函數(shù)H對消息對消

31、息M進(jìn)行壓縮。簽名方進(jìn)行壓縮。簽名方A計(jì)算計(jì)算H(M)，并計(jì)算：，并計(jì)算： R r mod pS(H(M) dAR) r1 (mod p1) 用戶用戶A將將Sig(M, r) = (R, S) 作為自己對消息作為自己對消息M的數(shù)字簽的數(shù)字簽名，與消息名，與消息M一起傳送給接收方。一起傳送給接收方。(3) 驗(yàn)證簽名：驗(yàn)證簽名：接收方在收到消息接收方在收到消息M與數(shù)字簽名與數(shù)字簽名(R，S)后：后： 計(jì)算計(jì)算H(M)； 計(jì)算計(jì)算eAR RS (mod p) 和和 H(M) (mod p) 若若兩式相等，即兩式相等，即 eAR RS (mod p) H(M) (mod p) 則確認(rèn)則確認(rèn)(R, S)

32、為有效簽名。為有效簽名。 eA = dA mod p，R r mod pS(H(M) dAR) r1 (mod p1)由于由于 eAR RS ( dA ) R ( r )S dA R r S dA Rr S (mod p) 又由又由 S(H(M) dAR) r1 (mod p1)由模運(yùn)算規(guī)則，上式為：由模運(yùn)算規(guī)則，上式為： r S+ dAR = H(M) (mod p1)即：即： dAR + r S = H(M) (mod p1)再由模運(yùn)算的指數(shù)性質(zhì)有：再由模運(yùn)算的指數(shù)性質(zhì)有： dA Rr S H(M) (mod p) 所以有：所以有： eAR RS (mod p) H(M) (mod p)

33、完整地，驗(yàn)證算法可表述如下：完整地，驗(yàn)證算法可表述如下：Ver(M, (R, S)(eAR RS (mod p) = H(M) (mod p) )? True : false 在在ElGamal簽名方案中，簽名過程需要保密的密鑰簽名方案中，簽名過程需要保密的密鑰dA和一個(gè)秘和一個(gè)秘密的隨機(jī)數(shù)密的隨機(jī)數(shù) r ，而對簽名進(jìn)行驗(yàn)證則只需要公開的參數(shù)，而對簽名進(jìn)行驗(yàn)證則只需要公開的參數(shù)(eA, p, )。ElGamal 數(shù)字簽名算法舉例數(shù)字簽名算法舉例 設(shè)設(shè) p = 11， 2是是Z11* 的一個(gè)本原元。用戶的一個(gè)本原元。用戶A選擇隨機(jī)整選擇隨機(jī)整數(shù)數(shù) dA = 8，計(jì)算：，計(jì)算： eA = dA mod p=28 mod 11= 3 系統(tǒng)參數(shù)系統(tǒng)參數(shù) p ， 和和用戶用戶A的的公鑰公鑰eA公開，簽名私鑰公開，簽名私鑰dA保密。保密。 假設(shè)假設(shè)用戶用戶A要對消息要對消息M進(jìn)行簽名進(jìn)行簽名 ，且，且H(M) 5 。(1) 用戶用戶A選擇隨機(jī)數(shù)選擇隨機(jī)數(shù) r = 9; 因?yàn)橐驗(yàn)?(9, 10) = 1，所以，所以9模模10的逆一定存在，根據(jù)擴(kuò)展的的逆一定存在，根據(jù)擴(kuò)展的Euclid算法，算法， 有：有： r1 (mod p1) 91 (mod 10)9 用戶用戶A計(jì)算：計(jì)算：R r mod