基于RSA的一般訪問結(jié)構(gòu)的秘密共享方案

宋 琦, 徐明杰, 趙季翔, 劉春暉, 侯整風(fēng)

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院,安徽 合肥 230009)

基于RSA的一般訪問結(jié)構(gòu)的秘密共享方案

宋 琦, 徐明杰, 趙季翔, 劉春暉, 侯整風(fēng)

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院,安徽 合肥 230009)

文章基于RSA(Rivest-Shamir-Adleman)密碼體制,提出一種一般訪問結(jié)構(gòu)的秘密共享方案。為避免分發(fā)者的“權(quán)威欺騙”,方案中的參與者各自選擇自己的秘密份額;在秘密恢復(fù)階段,秘密恢復(fù)者利用秘密份額影子來恢復(fù)秘密,而不暴露秘密份額,因此秘密份額可重復(fù)使用;當(dāng)共享秘密改變時,秘密份額不變,秘密分發(fā)者通過改變秘密影子,使得秘密份額能夠共享多個秘密;同時,該方案能夠驗證參與者的欺騙行為。最后,通過理論分析和實例,證明了該方案的安全性和正確性。

秘密共享;一般訪問結(jié)構(gòu);秘密份額;RSA算法;秘密份額影子;秘密影子

秘密共享是信息安全和密碼學(xué)領(lǐng)域中的重要研究方向,也是進行密鑰管理的重要手段。Shamir[1]和Blakley[2]在1979年分別提出了(t,n)門限秘密共享方案。(t,n) 門限秘密共享是指n個參與者共享秘密,t個或t個以上參與者合作能夠恢復(fù)該秘密,少于t個則不能恢復(fù)。隨后,研究者對(t,n)門限共享方案進行了深入研究,文獻[3]提出了基于中國剩余定理的門限秘密共享方案;文獻[4-5]分別提出了不同的可驗證的門限秘密共享方案。

文獻[6]首次提出了一種基于一般訪問結(jié)構(gòu)的秘密共享方案,該方案定義若干授權(quán)子集,使得授權(quán)子集中的參與者合作可以恢復(fù)秘密,而非授權(quán)子集中的參與者不能恢復(fù)秘密。與(t,n)門限秘密共享相比,一般訪問結(jié)構(gòu)更具一般性和普適性。隨后,其他研究者提出了許多基于一般訪問結(jié)構(gòu)上的秘密共享方案[7-15]。文獻[7]對文獻[6]中的構(gòu)造方法進行改進,提出了一個更加簡單、高效的構(gòu)造方法;文獻[8]提出了一種一般訪問結(jié)構(gòu)的秘密共享方案,但該方案中由秘密分發(fā)者產(chǎn)生秘密份額,不能防止分發(fā)者的“權(quán)威欺騙”，此外,在秘密恢復(fù)過程中,缺乏驗證過程,不能防止參與者之間的欺騙。

本文提出了一種基于RSA(Rivest-Shamir-Adleman)的一般訪問結(jié)構(gòu)的秘密共享方案,該方案中每個參與者的秘密份額由參與者自己選取,避免了分發(fā)者的“權(quán)威欺騙”;秘密恢復(fù)者利用秘密份額影子來恢復(fù)秘密,而不暴露秘密份額;當(dāng)共享秘密改變時,秘密份額不變,秘密分發(fā)者通過改變秘密影子使得1份秘密份額可以參與多次秘密共享過程;在秘密恢復(fù)過程中,每個參與者都可以驗證其他合作的參與者是否誠實地提供了秘密份額影子。

1 一般訪問結(jié)構(gòu)上的秘密共享

在門限方案中,各參與者具有完全平等的地位,因而在實際應(yīng)用中缺乏靈活性。例如,某企業(yè)的董事長可以產(chǎn)生有效的簽名,1名董事和總經(jīng)理合作也可以產(chǎn)生有效的簽名,1名董事加3名部長合作也可以產(chǎn)生有效的簽名。顯然,(t,n)門限秘密共享方案無法適應(yīng)這樣的應(yīng)用需求。一般訪問結(jié)構(gòu)秘密共享是門限秘密共享的擴展與延伸,能夠解決上述情況。

定義1 授權(quán)子集。設(shè)參與者集合為P,若A?P且A可以恢復(fù)秘密S0,則A稱為授權(quán)子集。

定義2 訪問結(jié)構(gòu)[16]。 由所有授權(quán)子集組成的集合稱為訪問結(jié)構(gòu)Г。

定義3 最小訪問結(jié)構(gòu)。 若Г0?Г,且Г0={B|如果B滿足B?A?P,那么B?Г0},則Г0為最小訪問結(jié)構(gòu)。Г的所有最小授權(quán)子集構(gòu)成的集合Г0可以唯一確定Г。

一般訪問結(jié)構(gòu)的秘密共享是指秘密分發(fā)者將共享秘密S0分成若干個份額,分別分發(fā)給若干個參與者,秘密分發(fā)者定義一個最小訪問結(jié)構(gòu)Г0,使得Г0中的授權(quán)子集A內(nèi)的所有成員聯(lián)合可以恢復(fù)S0,而非授權(quán)子集中的參與者合作不能得到有關(guān)S0的任何信息。

與(t,n)門限秘密共享相比,一般訪問結(jié)構(gòu)秘密共享更具有廣泛的普適性和靈活性,因此,對一般訪問結(jié)構(gòu)上的秘密共享的研究具有重要的理論研究和實際應(yīng)用價值。

2 本文方案

本文基于RSA密碼體制,提出了一種一般訪問結(jié)構(gòu)的秘密共享方案。秘密份額由參與者獨立選擇,避免了分發(fā)者的“權(quán)威欺騙”(分發(fā)者分發(fā)假的秘密份額給參與者,使得合法的參與者相互合作無法恢復(fù)秘密)。秘密恢復(fù)者利用秘密份額影子來恢復(fù)秘密,而不是通過秘密份額來恢復(fù)秘密,因此,秘密份額沒有暴露,可以重復(fù)使用。參與者之間通過相互驗證秘密份額影子的真實性,能夠有效防止參與者的欺騙行為。

該方案分為4個階段:初始化、秘密份額影子的產(chǎn)生、秘密影子的產(chǎn)生以及秘密恢復(fù)。整體流程如圖1所示。

圖1 方案流程

2.1 初始化

秘密分發(fā)者指定授權(quán)子集,生成RSA算法相關(guān)參數(shù),確定共享秘密。設(shè)參與者集合P={P11,P12,…,Pt|rt|};最小訪問結(jié)構(gòu)Г0={r1,r2,…,rt};授權(quán)子集rj={Pj1,Pj2,…,Pj|rj|},|rj|為rj中成員的數(shù)目;秘密分發(fā)者為SD,秘密恢復(fù)者為SR,共享秘密為S0。

SD選擇2個大素數(shù)p和q,計算N=p×q,φ(N)=(p-1)(q-1);從[2,N]中隨機選取2個整數(shù)a和g,計算R0=gamodN,找到1個滿足ah≡1 modφ(N)的整數(shù)h。對所有參與者公開R0、N、h、g。

2.2 秘密份額影子的產(chǎn)生

每個參與者Pji各自選擇一個整數(shù)fji(j=1,2,…,t)作為各自的秘密份額,并各自計算秘密份額影子,即

(1)

Pji將fji保密,并將Tji發(fā)給SD。

2.3 秘密影子的產(chǎn)生

分發(fā)者SD收到秘密份額影子后,為每個授權(quán)子集計算出其相應(yīng)的秘密影子S,并對該授權(quán)子集內(nèi)成員公開，計算步驟如下：

(1) 對于每個授權(quán)子集rj,SD選擇一個非負整數(shù) ΔTj,由(2)式計算Tj,并使得Tj與φ(N)互素;然后解同余方程(3)式,求解出Dj。

(2)

(3)

(2) 由(4)式計算S,將S對授權(quán)子集rj內(nèi)成員公開。

(4)

(3) 由(5)式計算Qj,將Qj和Tji發(fā)給秘密恢復(fù)者SR。

(5)

2.4 秘密恢復(fù)

設(shè)秘密恢復(fù)者SR可由授權(quán)子集rj中的任一成員擔(dān)任。SR先驗證參與者的秘密份額影子的真實性。當(dāng)檢測到無效的秘密份額影子時,則通知參與者重新發(fā)送秘密份額影子;當(dāng)且僅當(dāng)授權(quán)子集內(nèi)所有參與者的秘密份額影子均有效時,則進行秘密恢復(fù)。秘密恢復(fù)過程如下：

(1)rj中每個成員Pji利用自己的秘密份額fji,由(6)式計算fji′,將fji′發(fā)給SR。

(6)

(2) SR驗證fji′。若(7)式成立,則秘密份額影子有效。

(7)

(3) SR利用各個參與者的秘密份額影子Tji來恢復(fù)秘密S0,秘密恢復(fù)式為:

(8)

3 分析與討論

3.1 正確性分析

(8)式的正確性證明如下:

[Qj(STj1modN)…(STj|rj|modN)]modN=

SΔTj+Tj1+…+Tj|rj|modN=

STjmodN=S0。

3.2 安全分析

(1) 有效避免分發(fā)者的“權(quán)威欺騙”。在秘密份額影子產(chǎn)生階段,參與者Pji各自選擇秘密份額fji,并按照(1)式計算出秘密份額影子Tji,然后將Tji發(fā)給分發(fā)者SD。根據(jù)(1)式可以認為是參與者Pji執(zhí)行了RSA解密算法,其中N為模數(shù),fji相當(dāng)于私鑰,g相當(dāng)于密文,Tji相當(dāng)于明文。分發(fā)者想要從參與者Pji的秘密份額影子Tji推導(dǎo)出秘密份額fji,其難度等價于求出RSA系統(tǒng)的私鑰,因此,分發(fā)者無法通過Tji獲得fji,因而本方案避免了分發(fā)者的“權(quán)威欺騙”。

(2) 秘密恢復(fù)者可以驗證參與者提供的秘密份額影子。參與者Pji將fji′和Tji提供給秘密恢復(fù)者,Pji通過(7)式驗證Tji的有效性;若(7)式成立,則秘密份額影子Tji是有效的;否則,Tji是無效的。

由(1)式、(6)式可得:

(3) 秘密份額可以重復(fù)使用。在秘密份額影子產(chǎn)生階段,參與者Pji各自選擇秘密份額fji,并通過(1)式計算出秘密份額影子Tji,然后把秘密份額影子Tji發(fā)給分發(fā)者SD，分發(fā)者無法通過Tji獲得fji;在秘密恢復(fù)階段,秘密恢復(fù)者SR獲得Tji而不是fji,因此秘密份額fji沒有暴露;因而在整個秘密共享過程中秘密份額可以重復(fù)使用。

3.3 多秘密共享

本方案支持多秘密共享。當(dāng)參與者選定了各自的秘密份額后,可共享多個秘密。

設(shè)S1,S2,…,Sn為多個共享秘密,rj={P1,P2,…,Pt}為授權(quán)子集;f1,f2,…,ft為rj中參與者選擇的秘密份額;T1,T2,…,Tt為對應(yīng)的秘密份額影子。

對任一秘密Sk(1≤k≤n),由(8)式得到:

當(dāng)共享秘密S0變?yōu)镾k時,由(4)式知, 秘密影子S發(fā)生改變;同時秘密份額影子T1,T2,…,Tt以及D1不變。由(1)式可以得到,秘密份額f1,f2,…,ft不變,即在共享秘密改變時,秘密份額始終沒有改變,因此本文方案中1份秘密份額可以共享多個秘密。

4 實 例

4.1 初始化

假設(shè)p=5,q=11,N=55,φ(N)=40,g=3,n=5,a=9,h=9,S0=2,P={P11,P12,P13,P21,P22},Г0={r1,r2},其中r1={P11,P12,P13}。

4.2 秘密份額影子的產(chǎn)生

授權(quán)子集r1的成員P11、P12、P13中，P11選取f11=1,P12選取f12=2,P13選取f13=6，由(1)式依次計算可得:

T11=gf11modN=31mod 55=3,

T12=gf12modN=32mod 55=9,

T13=gf13modN=36mod 55=14。

4.3 秘密影子的產(chǎn)生

取ΔT1=1,由(2)式計算T1,即

由(3)式計算出D1=3。由(4)式計算S,由(5)式計算Q1,即

Q1=SΔT1modN=81mod 55=8。

將Q1發(fā)給秘密恢復(fù)者SR。

4.4 秘密恢復(fù)

(1) 成員P11、P12、P13由(6)式分別計算f11′、f12′、f13′,并將f11′、f12′、f13′發(fā)給秘密恢復(fù)者SR,具體計算如下:

(2) SR可以依次算出:

T11modN=3,

T12modN=9,

T13modN=14。

通過計算可以驗證(7)式成立,即成員P11、P12、P13的秘密份額影子是有效的。

(3) SR可以由(8)式恢復(fù)出秘密S0,即

(ST13modN)]modN=2。

5 結(jié) 論

本文提出了一種基于RSA算法的一般訪問結(jié)構(gòu)的秘密共享方案,通過理論分析和實例證明了該方案的安全性和正確性。每個參與者選擇自己的秘密份額,從而有效地避免了分發(fā)者的“權(quán)威欺騙”;在秘密恢復(fù)過程中,秘密恢復(fù)者利用秘密份額影子來恢復(fù)秘密,而不暴露秘密份額,因此秘密份額可以重復(fù)使用。本文方案支持多秘密共享,1份秘密份額可以共享多個秘密。此外,秘密恢復(fù)者能夠驗證秘密份額影子的有效性。

[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]//Proc AFIPS National Computer Conference.New York:AFIPS Press,1979:313-317.

[3] ASMUTH C,BLOOM J.A modular approach to key safeguarding[J].IEEE Transaction on Information Theory,1983,29(2):208-210.

[4] FELDMAN P.A practical scheme for non-interactive verifiable secret sharing[C]//Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science.Los Angeles:IEEE Computer Society,1987:427-438.

[5] PEDERSE T P.Non-interactive and information-theoretic secure verifiable secret sharing[C]//Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology.London:Springer-Verlag,1992:129-139.

[6] ITO M,SAITO A,NISHIZKI T.Secret sharing scheme realizing general access structure[J].Electronics and Communications in Japan,1989,72(9):56-64.

[7] BENALOH J,LEICHTER J.Generalized secret sharing and monotone functions[C]//Advances in Cryptology:CRYPTO’88.New York:Springer-Verlag,1988:27-35.

[8] WEI Yun,ZHONG Pucha,XIONG Guohua.A multi-stage secret sharing scheme with general access structures[C]//International Conference on Wireless Communications,Networking and Mobile Computing.Dalian,China:IEEE,2008:1-4.

[9] YE Saizhi,YAO Guoxiang,GUAN Quanlong.A multiple secrets sharing scheme with general access structure[C]//International Symposium on Intelligent Ubiquitous Computing and Education.Chengdu,China:IEEE,2009:461-464.

[10] WANG S J.Direct construction of a secret in generalized group-oriented cryptography[J].Computer Standards and Interfaces,2004,26(5):455-460.

[11] 龐遼軍,姜正濤,王育民.基于一般訪問結(jié)構(gòu)的多重秘密共享方案[J].計算機研究與發(fā)展,2006,43(1):33-38.

[12] 張來順,周洪偉,原錦輝.基于RSA的一般訪問結(jié)構(gòu)多重秘密共享方案[J].計算機工程與設(shè)計,2009,30(10):2379-2380.

[13] SUN Hua,WANG Aimin.A multi-secret sharing scheme with general access structures based on elliptic curve[C]//International Conference on Advanced Computer Theory and Engineering(ICACTE).Chengdu,China:IEEE,2010:629-632.

[14] 王永,朱艷琴,羅喜召.基于一般訪問結(jié)構(gòu)的可驗證多秘密共享方案[J].計算機應(yīng)用與軟件,2011,28(4):37-39.

[15] WU X,SUN W.Visual secret sharing for general access structures by random grids[J].IET Information Security,2012,6(4):299-309.

[16] HWANG R J,CHANG C C.An on-line secret sharing scheme for multi-secrets[J].Computer Communications,1998,21(13):1170-1176.

(責(zé)任編輯 張淑艷)

Secret sharing scheme with general access structures based on RSA

SONG Qi, XU Mingjie, ZHAO Jixiang, LIU Chunhui, HOU Zhengfeng

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Based on the Rivest-Shamir-Adleman(RSA) cryptosystem, a new secret sharing scheme with general access structures is proposed. In this scheme, each participant selects a secret share by himself to avoid the “authority deception”. In the recovery phase, the recuperator uses the secret share shadows to recover the secret and does not expose the secret shares, so the secret shares are reusable. The secret shares do not need to be changed when the shared secret is renewed. The secret share can be used in many secrets because the dealer changes the secret shadow. This scheme can also identify the participants’ mutual cheating. Finally, the results of the theoretical analysis and the example show that the scheme is secure and correct.

secret sharing; general access structure; secret share; Rivest-Shamir-Adleman(RSA) algorithm; secret share shadow; secret shadow

2015-03-30；

2016-03-30

安徽省自然科學(xué)基金資助項目(11040606M138)

宋 琦(1990-),女,安徽定遠人,合肥工業(yè)大學(xué)碩士生; 侯整風(fēng)(1958-),男,安徽和縣人,合肥工業(yè)大學(xué)教授,碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2017.05.010

TP309.7

A

1003-5060(2017)05-0624-04