應用密碼學---淺談秘密分割與共享[課件]

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

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

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

4、消息產(chǎn)生三個與消息M一樣長的隨機比特串一樣長的隨機比特串R,S,T；2）Trent用這三個隨機串和用這三個隨機串和M異或得到異或得到U：M R S T = U3）Trent將將R給給Alice，S給給Bob，T給給Carol，U給給Dave。 Alice、Bob和Carol、Dave在一起可以重構此消息：4）Alice、Bob、Carol和和Dave一起計算：一起計算：R S T U = M安全性分析1-保密性好 如果做得適當，這種技術是絕對安全的。因為每如果做得適當，這種技術是絕對安全的。因為每一個人所持有的部分消息本身是毫無價值的。一個人所持有的部分消息本身是毫無價值的。 前述協(xié)議的實質(zhì)，

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

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

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

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

9、，那么核彈發(fā)射受到瘋子干擾的程度就越小，核彈發(fā)射控制系統(tǒng)彈發(fā)射受到瘋子干擾的程度就越小，核彈發(fā)射控制系統(tǒng)的安全性就越高，但同時遇到緊急情況時因為有人缺席的安全性就越高，但同時遇到緊急情況時因為有人缺席而造成核彈無法及時發(fā)射的概率就越大；反之亦然。而造成核彈無法及時發(fā)射的概率就越大；反之亦然。2.3 Shamir門限方案l作者：作者：Adi Shamirl基于基于多項式的拉格朗日插值公式多項式的拉格朗日插值公式ShamirShamir門限方案的原理門限方案的原理 對于有限域?qū)τ谟邢抻?GF(q) 上的一個上的一個 k-1 次多項式次多項式 f(x) ,若把若把秘密秘密s取做取做 f(0) ，將將

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

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

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

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

14、選隨機選a1=2，a2=7 使使 f(x)=7x2+2x11 mod 19 計算計算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ā)給五個用戶。分發(fā)給五個用戶。1127)35)(25()3)(2(6)53)(23()5)(2(4)52)(32()5)(3(5)(2xxxxxxxxxf若已知若已知f(2)，f(3)，f(5)，重構，重構f(x)如下：如下：2.2 Asmuth-Bloom門限方案l作者：作者：Asmuth-Blooml基于基于中國剩余定理中國剩余定理舉例引入舉例引入任何一個方程無法確定x任何兩個方程可唯一確定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（等價：（等價：s s 大于任意大于任意 t-1 t-1 個個mmi i的乘積的乘積 s s 小于任意小于任意 t t 個個mmi i的乘積的乘積 ）

16、此時，此時，可構造可構造( (t t,n),n)門限方案。門限方案。簡化的簡化的Asmuth-Bloom門限方案門限方案u子密鑰的分發(fā)子密鑰的分發(fā)n計算計算 si = s(mod mi) (i=1, N)， （mi,si）為一子密鑰為一子密鑰. . u密鑰的恢復密鑰的恢復n當當k k個參與者提供子密鑰時，可建立方程組個參與者提供子密鑰時，可建立方程組n由中國剩余定理可以求得由中國剩余定理可以求得 s s s s mod N mod N ，NN為為k k個個mi的乘積的乘積顯然，當顯然，當 s= t,則由系統(tǒng)初始化條件則由系統(tǒng)初始化條件因為因為s小于任意小于任意 t 個個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)構成構成（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、能把假的子秘密給分派者欺騙是指分派者可能把假的子秘密給參與者，使得該參與者無法在日后重建共享參與者，使得該參與者無法在日后重建共享的秘密。的秘密。 解決方案包括子秘密應具備可驗證性解決方案包括子秘密應具備可驗證性(verifiable)(verifiable)與通過數(shù)字簽名解決。與通過數(shù)字簽名解決。三、門限數(shù)字簽名方案3.1 概述概述3.2 基于基于Schnorr體制的體制的(t,n)門限簽名方案門限簽名方案3.3 基于基于ElGamal體制的體制的(t,n)門限簽名方案門限簽名方案（t,nt,n）門限簽名是指，群體的簽名密鑰被所有）門限簽名是指，群體的簽名密鑰被所有n n個成員共享，使得任意

20、不少于個成員共享，使得任意不少于t t個成員的子集個成員的子集可以代表群體產(chǎn)生簽名，而任意少于可以代表群體產(chǎn)生簽名，而任意少于t t個成員的個成員的子集不能代表群體產(chǎn)生簽名；同時任何人都可子集不能代表群體產(chǎ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 不再單獨分發(fā)給個人，而是作為一個共享秘密，

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

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

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

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

25、 董事會為此爭論不休，煩惱之極！董事會為此爭論不休，煩惱之極！如果你是公司的安全顧問，你該怎么為如果你是公司的安全顧問，你該怎么為你的你的bossboss們解憂？們解憂？返回返回美軍核彈發(fā)射控制問題 你正在為核導彈設計發(fā)射裝置，導彈的發(fā)射權力你正在為核導彈設計發(fā)射裝置，導彈的發(fā)射權力將交給五位官員。但五個官員中潛藏有至多兩個瘋子，將交給五位官員。但五個官員中潛藏有至多兩個瘋子，而瘋子們沒理由得想要轟炸多倫多。而瘋子們沒理由得想要轟炸多倫多。 為了不會因為瘋子們的失控而發(fā)生一起多倫多炮為了不會因為瘋子們的失控而發(fā)生一起多倫多炮轟事件，你確信當僅有瘋子在場的情況下是不應擁有轟事件，你確信當僅有瘋子

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

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

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

29、ifxfkjkjllljlj拉格朗日插值公式拉格朗日插值公式返回返回設設m1, m2, mk是是 k 個兩兩互素的正整數(shù)，個兩兩互素的正整數(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)初始化：選取大素數(shù)選取大素數(shù) p， Zp*是一個本原元。是一個本原元。 p， 作為系統(tǒng)參數(shù)公開。作為系統(tǒng)參數(shù)公開。 每個用戶每個用戶U隨機選取整數(shù)隨機選取整數(shù) dU，2 dU p2。 計算：計算： eU = dU mod p 將將 eU 作為用戶作為用戶U的公開密鑰，的公開密鑰， dU作為用于簽名的秘作為用于簽名的秘密密鑰，并嚴格保密。密密鑰，并嚴格保密。(2) 簽名變換：簽名變換： 給定消息給定消息M，簽名方，簽名方A將進行下述簽名計算：將進行下述簽名計算： 選擇隨機數(shù)選擇隨機數(shù) rZp* ，且，且r與（與（p1)互素互素 用單向散列函數(shù)用單向散列函數(shù)H對消息對消

31、息M進行壓縮。簽名方進行壓縮。簽名方A計算計算H(M)，并計算：，并計算： R r mod pS(H(M) dAR) r1 (mod p1) 用戶用戶A將將Sig(M, r) = (R, S) 作為自己對消息作為自己對消息M的數(shù)字簽的數(shù)字簽名，與消息名，與消息M一起傳送給接收方。一起傳送給接收方。(3) 驗證簽名：驗證簽名：接收方在收到消息接收方在收到消息M與數(shù)字簽名與數(shù)字簽名(R，S)后：后： 計算計算H(M)； 計算計算eAR RS (mod p) 和和 H(M) (mod p) 若若兩式相等，即兩式相等，即 eAR RS (mod p) H(M) (mod p) 則確認則確認(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)由模運算規(guī)則，上式為：由模運算規(guī)則，上式為： r S+ dAR = H(M) (mod p1)即：即： dAR + r S = H(M) (mod p1)再由模運算的指數(shù)性質(zhì)有：再由模運算的指數(shù)性質(zhì)有： dA Rr S H(M) (mod p) 所以有：所以有： eAR RS (mod p) H(M) (mod p)

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