楊 捷

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

引言

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

1 方案的構(gòu)成

1.1 初始化階段

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

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

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

(2)D 計(jì)算 f(1)，f(2)，…，f(n)，將(1，f(1))，(2，f(2))，…，(n，f(n))分別傳給 U1，U2，…Un保管;計(jì)算 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 計(jì)算多項(xiàng)式 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)造驗(yàn)證公式gf(x)=k'1并將它公布于公告牌。

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

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

1.3 秘密恢復(fù)階段

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

(1)恢復(fù)者從掌握子秘密的n個(gè)共享者手中提取t個(gè)人的子秘密，即t個(gè)秘密數(shù)對(duì)，例如提取的是(1，f(1))，(2，f(2))，…，(t，f(t))再?gòu)墓媾粕舷螺dm個(gè)數(shù)對(duì)(n+1，f(n+1))，(n+2，f(n+2))，…，(n+m，f(n+m))。

(2)恢復(fù)者將所得數(shù)對(duì)用公告牌上的驗(yàn)證公式逐個(gè)驗(yàn)證。

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

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

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

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

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

2 安全性分析

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

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

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

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

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

3 應(yīng)用的例子

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

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

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

4 結(jié)束語(yǔ)

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

由于門(mén)限方案中僅出現(xiàn)秘密的影子，所以一切數(shù)據(jù)都可在公共信道上傳輸，又?jǐn)[脫了方案對(duì)分發(fā)者誠(chéng)信的依賴(lài)，同時(shí)也不怕外部人員的攻擊，所以此方案既是安全的又是經(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］ 黃東平，劉鋒，王道順，戴一奇.一種安全的門(mén)限多秘密共享方案［J］.電子學(xué)報(bào)，2006，34(11):1937-1940.

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