門限多重影子秘密共享方案及應(yīng)用

楊 捷

(南京工業(yè)職業(yè)技術(shù)學(xué)院 圖書館，江蘇 南京 210023)

引言

現(xiàn)代密碼與信息安全其體制的安全性密切依賴于密鑰的使用。因此，對秘密數(shù)據(jù)的保管成為密碼學(xué)與信息安全領(lǐng)域一個極其重要的研究內(nèi)容。1979 年 Shamir［1］和 Blakley［2］分別基于 Lagrange 內(nèi)插多項式與射影幾何的理論各自獨立地提出了(t，n)門限秘密共享方案。其含義是把秘密數(shù)據(jù)分拆成n個子數(shù)據(jù)分交n個人保管，使得當(dāng)有t個人或t個以上的人提供子數(shù)據(jù)就能匯集起來進(jìn)行運算恢復(fù)出原先的秘密數(shù)據(jù)，而少于t個人就不行。這一秘密共享的思想為秘密數(shù)據(jù)安全存放給出了一個科學(xué)的框架。由于秘密數(shù)據(jù)安全存放十分重要，三十多年來許多學(xué)者對此進(jìn)行了大量研究，給出了許多有創(chuàng)意的方案。Stadler［3］提出了在線秘密共享機(jī)制，引入公告牌發(fā)布一些有關(guān)信息;還有一些方案針對多秘密共享防欺詐［4，5］等方面進(jìn)行了研究。但是這些方案都有一個致命弱點，就是讓分發(fā)者掌握了秘密。如果分發(fā)者把掌握到的秘密出賣給攻擊者，那么體制就形同虛設(shè)了。因為有此隱患，有些方案假設(shè)分發(fā)者是可信的，并在分發(fā)者是可信的前提下討論問題。然而這一前提過于理想化。本方案不讓分發(fā)者知道秘密，而只傳給他影子秘密，讓門限方案構(gòu)成對影子秘密的保護(hù)，影子秘密與秘密持有者的私鑰協(xié)同作用構(gòu)成對秘密的保護(hù)。相應(yīng)于這種思路，本文在秘密集與共享集之間給出了一種結(jié)構(gòu)上的聯(lián)系，即多個秘密均由共享集中的若干成員提供，對此進(jìn)行了討論，給出了相應(yīng)于這種聯(lián)系的共享方案。方案中雖然有一個分配中心(分發(fā)者)，但不必為可信的;方案中也用了公告牌，共享者不獨可以閱讀、下載，對公告內(nèi)容如有疑問還可提出質(zhì)疑。

1 方案的構(gòu)成

1.1 初始化階段

設(shè){K1，K2，…，Km}為秘密集，{U1，U2，…，Um，Um+1，…，Un}為秘密共享集，D為子秘密分發(fā)者。D取大素數(shù)p，q滿足q|p－1;g∈，g的階為q;h:{0，1}*→為抗碰撞，單向的Hash函數(shù)。Ui以αi為私鑰，βi為公鑰，βi=gαimodP，i=1，2，…，n 秘密Ki∈為秘密共享集中的成員Ui所持有。Ui計算ki=(Ki+h(αi))modq，稱 ki為 Ki的影子秘密，i=1，2，…，m。U1，U2，…，Um將 k1，k2，…，km傳 給 D，Um+1，Um+2，…，Un不持有秘密，僅僅參與秘密共享。本方案需要一個公告牌，D可以公布、更新公告牌上的內(nèi)容，共享者可以閱讀下載，也可對公告內(nèi)容提出異議［6］。在初始化階段 D 在公告牌上公布 p，q，g，h以及 h1，h2，…，hm，這里 hi是 ki的散列值，i=1，2，…，m。對公告牌上的hi，Ui計算h(ki)，核對h(ki)=hi是否成立。如果成立，認(rèn)為傳給D的ki，D已安全收到，如果h(ki)≠hi則Ui對D在公告牌上公布的數(shù)值hi進(jìn)行質(zhì)疑提出異議，直到D在公告牌上給出ki的正確的散列值為止。對數(shù)值ki除Ki的持有者Ui之外其他的人無權(quán)過問。i=1，2，…，m

1.2 子秘密的生成與分發(fā)

(1)D 在公布 k1，k2，…，km的散列值之后，如果U1，U2，…，Um未提出異議，D 便認(rèn)為 k1，k2，…，km在傳送過程中未受到竄改。此時D便以k1，k2，…，km以及t個隨機(jī)數(shù)a1，a2，…，at∈(t＜ n)為系數(shù)作Zq上的m+t－1次多項式

(2)D 計算 f(1)，f(2)，…，f(n)，將(1，f(1))，(2，f(2))，…，(n，f(n))分別傳給 U1，U2，…Un保管;計算 f(n+1)，f(n+2)，…，f(n+m)，將(n+1，f(n+1))，(n+2，f(n+2))，…，(n+m，f(n+m))公布于公告牌。

(3)D 計算多項式 f(x)的系數(shù) k1，k2，…，km，a1，a2，…，at的變換值 k'1=gk1modp，k'2=gk2mod p，…，k'm=gkmmod p，a1'=ga1modp，a'2=ga2modp，…，a't=gatmodp，然后用變換值構(gòu)造驗證公式gf(x)=k'1并將它公布于公告牌。

(4)Ui收到(j，f(j))后，將x=j代入驗證公式，如果等式成立則接收(j，f(j))作為子秘密保管，不成立則向D質(zhì)疑要求對錯誤數(shù)據(jù)進(jìn)行更正。

(5)對于公告牌上的數(shù)對(j，f(j))j=n+1，n+2，…，n+m共享集中的成員，以及其他任何人都可將j的值代入驗證公式進(jìn)行驗證。若都成立，則說明D沒有欺詐，若有數(shù)對代入使等式不成立，此時驗證者應(yīng)立即向D提出異議。

1.3 秘密恢復(fù)階段

如果Ui(1≤i≤m)想恢復(fù)Ki，他可以委托一位恢復(fù)者先去恢復(fù)影子秘密ki。恢復(fù)者可以是共享集中的任何人，也可以是Ui自己。恢復(fù)過程如下:

(1)恢復(fù)者從掌握子秘密的n個共享者手中提取t個人的子秘密，即t個秘密數(shù)對，例如提取的是(1，f(1))，(2，f(2))，…，(t，f(t))再從公告牌上下載m個數(shù)對(n+1，f(n+1))，(n+2，f(n+2))，…，(n+m，f(n+m))。

(2)恢復(fù)者將所得數(shù)對用公告牌上的驗證公式逐個驗證。

(3)當(dāng)t+m個數(shù)對全部驗證無誤后記它們?yōu)?xi，yi)i=1，2，…，m+t并作 Zq上的插值多項式

(4)如果得出的插值多項式是m+t－1次的(如低于m+t－1次，恢復(fù)者需另取一個子秘密替換原先使用過的任一子秘密重構(gòu)插值多項式，直到是m+t－1次為止)恢復(fù)者便對該多項式中xi－1次方的系數(shù)求散列值。

(5)如果這一散列值為公告牌上的hi時，恢復(fù)者將該項系數(shù)傳送給Ui。

(6)Ui收到該系數(shù)后，求其散列值，得到hi后由Hash函數(shù)的抗碰撞性，他可以相信該系數(shù)就是影子秘密ki。然后Ui便可利用ki與自己的私鑰去恢復(fù)秘密 Ki=(ki－ h(αi))modq。

值得指出的是恢復(fù)者在獲得m+t個數(shù)對后可跳過步驟(2)直接去構(gòu)造插值多項式，并對xi－1次方的系數(shù)求散列值。只有在散列值不是hi時，為了查找哪個數(shù)對被篡改才需要用步驟(2)通過驗證公式逐個驗證。

2 安全性分析

本方案的安全性依賴于離散對數(shù)的難解性與Hash函數(shù)的抗碰撞性與單向性;而不依賴系統(tǒng)成員的誠信品質(zhì)。

1.在系統(tǒng)內(nèi)部共享者的不誠信行為可以表現(xiàn)在他將竄改過的子秘密(x，y)傳給恢復(fù)者?；謴?fù)者將(x，y)在驗證公式上進(jìn)行驗證，只有當(dāng)?shù)仁絞y=成立時才會接收。這就是說共享者的不誠信行為要想得逞必須在已知x或者說在已知時從上面的等式中解出離散對數(shù)y，無疑這是困難的。

2.而恢復(fù)者的不誠信行為可以表現(xiàn)在當(dāng)他恢復(fù)了f(x)之后他把xi－1的系數(shù)ki換成異于ki的∈Zq傳給Ui，要使欺詐行為不被發(fā)現(xiàn)他必須找到滿足h)=h(ki)的∈Zq，由哈希函數(shù)的抗碰撞性可知這也是困難的。

3.又分發(fā)者的不誠信行為可能表現(xiàn)在他在構(gòu)造多項式f(x)時用xi－1代替kixi－1(ki≠)，目的是使Ui(1≤i≤m)的影子秘密ki不能恢復(fù)。但是要使欺詐行為成功同樣需要滿足h()=h(ki)=hi，由上面的討論可知找到這樣的是困難的。

4.分發(fā)者、恢復(fù)者及系統(tǒng)外的攻擊者假設(shè)他們獲得了影子秘密ki(1≤i≤m)，由于他們不知道秘密持有者的私鑰αi所以無法利用公式Ki=(ki－h(huán)(αi))modq獲得秘密 Ki，而要從 Ui的公鑰 βi找出私鑰 αi需解 βi=gαimodp，這又是困難的。

3 應(yīng)用的例子

為了說明本方案的應(yīng)用現(xiàn)舉一個具體的例子。

一次重要的考試，出了m份試卷，這些試卷不能丟失、不能泄露、也不能被篡改，問題是如何存放它們。

假設(shè)m份試卷其上的考題都是來自某些公開的題庫，且是從題庫中第1000題至9999題這一范圍內(nèi)選出的，這就是說考題在題庫中的編號都是4位數(shù)，在此情況下試卷的存放可轉(zhuǎn)化為相關(guān)數(shù)據(jù)的存放，方法是將試卷中考題在題庫中的編號依次連接起來形成一個整數(shù)，m份試卷形成m個整數(shù)，記它們?yōu)镵1，K2，…，Km。試卷不能泄露，這些相關(guān)的整數(shù)也就不能泄露，它們是必須保密的秘密數(shù)據(jù)，我們稱K1，K2，…，Km為秘密集?，F(xiàn)在用本文所介紹的方案將它們存放，依照方案的步驟首先由秘密持有者(出題者)對各秘密數(shù)據(jù)分別加密形成影子秘密k1，k2，…，km，再對影子秘密使用(k，n)門限方案，其主要步驟是由分發(fā)者將影子秘密分成n個子秘密，分交n個共享者保管，完成這一步后便將試卷、秘密數(shù)據(jù)、影子秘密全部銷毀，剩下的只是n個共享者手中保存的子秘密，別的什么都沒有了。當(dāng)要重新獲得第i(1≤i≤m)份試卷時恢復(fù)者從n個掌握子秘密的共享者中提取k(﹤n)個人的子秘密，按方案中的方法操作可重新獲得影子秘密ki并將它提交給秘密持有者(出題者)，出題者對影子秘密ki驗證無誤后對它解密，重新獲得秘密數(shù)據(jù)Ki，將此數(shù)據(jù)每4位為一個分段并將這些分段視為考題在相應(yīng)題庫中的編號，從編號就可以得到考題，這樣就恢復(fù)了第i份試卷。根據(jù)對方案的安全性分析，可知秘密數(shù)據(jù)的存放是安全的，能有效的防止秘密數(shù)據(jù)的丟失、篡改和泄露，因秘密數(shù)據(jù)可產(chǎn)生試卷也就等于說試卷不會丟失、不會被篡改、不會泄露。因此應(yīng)用本方案方法就解決了試卷的存放問題。

4 結(jié)束語

本文給出的方案有別于傳統(tǒng)的門限方案，其特點是(秘密所有者的)私鑰與門限共同承擔(dān)了對秘密的保護(hù)，也同時承擔(dān)了對秘密的恢復(fù)，但是私鑰、門限兩者在方案中的功能還是各有側(cè)重的，保護(hù)主要靠私鑰，恢復(fù)主要靠門限。在使用公告牌的方法上本方案也有別于傳統(tǒng)的做法，提出了對公告牌上的內(nèi)容共享者如有異議可對分發(fā)者提出質(zhì)疑，這一做法使得系統(tǒng)成員之間可以互相制約，分清責(zé)任。

由于門限方案中僅出現(xiàn)秘密的影子，所以一切數(shù)據(jù)都可在公共信道上傳輸，又?jǐn)[脫了方案對分發(fā)者誠信的依賴，同時也不怕外部人員的攻擊，所以此方案既是安全的又是經(jīng)濟(jì)的。

［1］ SHAMIR A.How to share a secret［J］.Communications of the ACM，1979，22(11):612-613.

［2］ BLAKLEY G R.Safeguarding cryptographic keys［C］//Proceedings of National Computer Conference.Montvale，NJ:AFIPS Press，1979，48:313-317.

［3］ STADLER M.Publicly verifiable secret sharing［C］//Proc.of Advances in Cryptology-Eurocrypt'96.Berlin:Springer-Verlag 1996，190-199.

［4］ Yang CC，Chang T Y，Hwang M S，A(t，n)multi-secret sharing scheme［J］.Applied Mathematics and Computation，2004，151(2):483-490.

［5］ 黃東平，劉鋒，王道順，戴一奇.一種安全的門限多秘密共享方案［J］.電子學(xué)報，2006，34(11):1937-1940.

［6］ 楊捷，李繼國.基于密鑰協(xié)商的門限多秘密共享方案［J］.計算機(jī)工程，2010，36(20):153-154.