基于RSA的一般访问结构的秘密共享方案

宋 琦, 徐明杰, 赵季翔, 刘春晖, 侯整风

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

基于RSA的一般访问结构的秘密共享方案

宋 琦, 徐明杰, 赵季翔, 刘春晖, 侯整风

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

文章基于RSA(Rivest-Shamir-Adleman)密码体制,提出一种一般访问结构的秘密共享方案。为避免分发者的“权威欺骗”,方案中的参与者各自选择自己的秘密份额;在秘密恢复阶段,秘密恢复者利用秘密份额影子来恢复秘密,而不暴露秘密份额,因此秘密份额可重复使用;当共享秘密改变时,秘密份额不变,秘密分发者通过改变秘密影子,使得秘密份额能够共享多个秘密;同时,该方案能够验证参与者的欺骗行为。最后,通过理论分析和实例,证明了该方案的安全性和正确性。

秘密共享;一般访问结构;秘密份额;RSA算法;秘密份额影子;秘密影子

秘密共享是信息安全和密码学领域中的重要研究方向,也是进行密钥管理的重要手段。Shamir[1]和Blakley[2]在1979年分别提出了(t,n)门限秘密共享方案。(t,n) 门限秘密共享是指n个参与者共享秘密,t个或t个以上参与者合作能够恢复该秘密,少于t个则不能恢复。随后,研究者对(t,n)门限共享方案进行了深入研究,文献[3]提出了基于中国剩余定理的门限秘密共享方案;文献[4-5]分别提出了不同的可验证的门限秘密共享方案。

文献[6]首次提出了一种基于一般访问结构的秘密共享方案,该方案定义若干授权子集,使得授权子集中的参与者合作可以恢复秘密,而非授权子集中的参与者不能恢复秘密。与(t,n)门限秘密共享相比,一般访问结构更具一般性和普适性。随后,其他研究者提出了许多基于一般访问结构上的秘密共享方案[7-15]。文献[7]对文献[6]中的构造方法进行改进,提出了一个更加简单、高效的构造方法;文献[8]提出了一种一般访问结构的秘密共享方案,但该方案中由秘密分发者产生秘密份额,不能防止分发者的“权威欺骗”，此外,在秘密恢复过程中,缺乏验证过程,不能防止参与者之间的欺骗。

本文提出了一种基于RSA(Rivest-Shamir-Adleman)的一般访问结构的秘密共享方案,该方案中每个参与者的秘密份额由参与者自己选取,避免了分发者的“权威欺骗”;秘密恢复者利用秘密份额影子来恢复秘密,而不暴露秘密份额;当共享秘密改变时,秘密份额不变,秘密分发者通过改变秘密影子使得1份秘密份额可以参与多次秘密共享过程;在秘密恢复过程中,每个参与者都可以验证其他合作的参与者是否诚实地提供了秘密份额影子。

1 一般访问结构上的秘密共享

在门限方案中,各参与者具有完全平等的地位,因而在实际应用中缺乏灵活性。例如,某企业的董事长可以产生有效的签名,1名董事和总经理合作也可以产生有效的签名,1名董事加3名部长合作也可以产生有效的签名。显然,(t,n)门限秘密共享方案无法适应这样的应用需求。一般访问结构秘密共享是门限秘密共享的扩展与延伸,能够解决上述情况。

定义1 授权子集。设参与者集合为P,若A⊂P且A可以恢复秘密S0,则A称为授权子集。

定义2 访问结构[16]。 由所有授权子集组成的集合称为访问结构Г。

定义3 最小访问结构。 若Г0⊆Г,且Г0={B|如果B满足B⊂A⊂P,那么B∉Г0},则Г0为最小访问结构。Г的所有最小授权子集构成的集合Г0可以唯一确定Г。

一般访问结构的秘密共享是指秘密分发者将共享秘密S0分成若干个份额,分别分发给若干个参与者,秘密分发者定义一个最小访问结构Г0,使得Г0中的授权子集A内的所有成员联合可以恢复S0,而非授权子集中的参与者合作不能得到有关S0的任何信息。

与(t,n)门限秘密共享相比,一般访问结构秘密共享更具有广泛的普适性和灵活性,因此,对一般访问结构上的秘密共享的研究具有重要的理论研究和实际应用价值。

2 本文方案

本文基于RSA密码体制,提出了一种一般访问结构的秘密共享方案。秘密份额由参与者独立选择,避免了分发者的“权威欺骗”(分发者分发假的秘密份额给参与者,使得合法的参与者相互合作无法恢复秘密)。秘密恢复者利用秘密份额影子来恢复秘密,而不是通过秘密份额来恢复秘密,因此,秘密份额没有暴露,可以重复使用。参与者之间通过相互验证秘密份额影子的真实性,能够有效防止参与者的欺骗行为。

该方案分为4个阶段:初始化、秘密份额影子的产生、秘密影子的产生以及秘密恢复。整体流程如图1所示。

图1 方案流程

2.1 初始化

秘密分发者指定授权子集,生成RSA算法相关参数,确定共享秘密。设参与者集合P={P11,P12,…,Pt|rt|};最小访问结构Г0={r1,r2,…,rt};授权子集rj={Pj1,Pj2,…,Pj|rj|},|rj|为rj中成员的数目;秘密分发者为SD,秘密恢复者为SR,共享秘密为S0。

SD选择2个大素数p和q,计算N=p×q,φ(N)=(p-1)(q-1);从[2,N]中随机选取2个整数a和g,计算R0=gamodN,找到1个满足ah≡1 modφ(N)的整数h。对所有参与者公开R0、N、h、g。

2.2 秘密份额影子的产生

每个参与者Pji各自选择一个整数fji(j=1,2,…,t)作为各自的秘密份额,并各自计算秘密份额影子,即

(1)

Pji将fji保密,并将Tji发给SD。

2.3 秘密影子的产生

分发者SD收到秘密份额影子后,为每个授权子集计算出其相应的秘密影子S,并对该授权子集内成员公开，计算步骤如下：

(1) 对于每个授权子集rj,SD选择一个非负整数 ΔTj,由(2)式计算Tj,并使得Tj与φ(N)互素;然后解同余方程(3)式,求解出Dj。

(2)

(3)

(2) 由(4)式计算S,将S对授权子集rj内成员公开。

(4)

(3) 由(5)式计算Qj,将Qj和Tji发给秘密恢复者SR。

(5)

2.4 秘密恢复

设秘密恢复者SR可由授权子集rj中的任一成员担任。SR先验证参与者的秘密份额影子的真实性。当检测到无效的秘密份额影子时,则通知参与者重新发送秘密份额影子;当且仅当授权子集内所有参与者的秘密份额影子均有效时,则进行秘密恢复。秘密恢复过程如下：

(1)rj中每个成员Pji利用自己的秘密份额fji,由(6)式计算fji′,将fji′发给SR。

(6)

(2) SR验证fji′。若(7)式成立,则秘密份额影子有效。

(7)

(3) SR利用各个参与者的秘密份额影子Tji来恢复秘密S0,秘密恢复式为:

(8)

3 分析与讨论

3.1 正确性分析

(8)式的正确性证明如下:

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

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

STjmodN=S0。

3.2 安全分析

(1) 有效避免分发者的“权威欺骗”。在秘密份额影子产生阶段,参与者Pji各自选择秘密份额fji,并按照(1)式计算出秘密份额影子Tji,然后将Tji发给分发者SD。根据(1)式可以认为是参与者Pji执行了RSA解密算法,其中N为模数,fji相当于私钥,g相当于密文,Tji相当于明文。分发者想要从参与者Pji的秘密份额影子Tji推导出秘密份额fji,其难度等价于求出RSA系统的私钥,因此,分发者无法通过Tji获得fji,因而本方案避免了分发者的“权威欺骗”。

(2) 秘密恢复者可以验证参与者提供的秘密份额影子。参与者Pji将fji′和Tji提供给秘密恢复者,Pji通过(7)式验证Tji的有效性;若(7)式成立,则秘密份额影子Tji是有效的;否则,Tji是无效的。

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

(3) 秘密份额可以重复使用。在秘密份额影子产生阶段,参与者Pji各自选择秘密份额fji,并通过(1)式计算出秘密份额影子Tji,然后把秘密份额影子Tji发给分发者SD，分发者无法通过Tji获得fji;在秘密恢复阶段,秘密恢复者SR获得Tji而不是fji,因此秘密份额fji没有暴露;因而在整个秘密共享过程中秘密份额可以重复使用。

3.3 多秘密共享

本方案支持多秘密共享。当参与者选定了各自的秘密份额后,可共享多个秘密。

设S1,S2,…,Sn为多个共享秘密,rj={P1,P2,…,Pt}为授权子集;f1,f2,…,ft为rj中参与者选择的秘密份额;T1,T2,…,Tt为对应的秘密份额影子。

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

当共享秘密S0变为Sk时,由(4)式知, 秘密影子S发生改变;同时秘密份额影子T1,T2,…,Tt以及D1不变。由(1)式可以得到,秘密份额f1,f2,…,ft不变,即在共享秘密改变时,秘密份额始终没有改变,因此本文方案中1份秘密份额可以共享多个秘密。

4 实 例

4.1 初始化

假设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 秘密份额影子的产生

授权子集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 秘密影子的产生

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

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

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

将Q1发给秘密恢复者SR。

4.4 秘密恢复

(1) 成员P11、P12、P13由(6)式分别计算f11′、f12′、f13′,并将f11′、f12′、f13′发给秘密恢复者SR,具体计算如下:

(2) SR可以依次算出:

T11modN=3,

T12modN=9,

T13modN=14。

通过计算可以验证(7)式成立,即成员P11、P12、P13的秘密份额影子是有效的。

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

(ST13modN)]modN=2。

5 结 论

本文提出了一种基于RSA算法的一般访问结构的秘密共享方案,通过理论分析和实例证明了该方案的安全性和正确性。每个参与者选择自己的秘密份额,从而有效地避免了分发者的“权威欺骗”;在秘密恢复过程中,秘密恢复者利用秘密份额影子来恢复秘密,而不暴露秘密份额,因此秘密份额可以重复使用。本文方案支持多秘密共享,1份秘密份额可以共享多个秘密。此外,秘密恢复者能够验证秘密份额影子的有效性。

[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] 庞辽军,姜正涛,王育民.基于一般访问结构的多重秘密共享方案[J].计算机研究与发展,2006,43(1):33-38.

[12] 张来顺,周洪伟,原锦辉.基于RSA的一般访问结构多重秘密共享方案[J].计算机工程与设计,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] 王永,朱艳琴,罗喜召.基于一般访问结构的可验证多秘密共享方案[J].计算机应用与软件,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.

(责任编辑 张淑艳)

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

安徽省自然科学基金资助项目(11040606M138)

宋 琦(1990-),女,安徽定远人,合肥工业大学硕士生; 侯整风(1958-),男,安徽和县人,合肥工业大学教授,硕士生导师.

10.3969/j.issn.1003-5060.2017.05.010

TP309.7

A

1003-5060(2017)05-0624-04