一类新的(r,n)动态密钥分存方案

刘寅寅,魏 露

(安阳工学院，河南 安阳 455000)



一类新的(r,n)动态密钥分存方案

刘寅寅,魏 露

(安阳工学院，河南 安阳 455000)

由于基于拉格朗日插值公式的(r,n)-门限方案易受到攻击,所以通过初始过程,密钥分发过程和密钥重构过程构造了一类新的动态密钥分存方案,同时证明了新构造的动态密钥分存方案是(r,n)-门限方案,并且该方案通过随时更换参加者所拥有的密钥碎片来防欺诈。

拉格朗日插值公式；门限方案；动态密钥分存方案

1 基于拉格朗日插值公式的(r,n)-门限方案

在文献[1]的(r,n)-门限方案中,如果n个参加人员中的任意r个人所拥有的密钥k的密钥碎片被攻击者得到,就能够通过拉格朗日插值公式恢复密钥k。

不妨设攻击者得到参与人员P1,P2,…,Pr的密钥碎片k1,k2,…,kr。通过拉格朗日插值公式得到一个r-1次多项式:

这里,加法、减法、乘法、除法运算都是在GF(q)上进行的。

显然,p(x)满足:p(xj)=kj(j=1,2,…,r)，因此，得到p(0)=k,故攻击者就能够恢复密钥k。因此,文献[1]基于拉格朗日插值公式的(r,n)-门限方案很容易受到攻击者的破坏。

2 构造新的动态密钥分存方案

由产生上述攻击的原因,构造了一类新的(r,n)动态密钥分存方案。新构造的动态密钥分存方案通过分配者D秘密地选取不同的m,算出的k′=kmr-1也就不相同。因此,所有参加人员所拥有的密钥碎片能够随时被更换,也就增强了该方案的安全性。新构造的动态密钥分存方案分为三个过程：初始过程、密钥分发过程和密钥重构过程。

2.1 初始过程

在有限域GF(q)中(q是一个素数幂),P={P1,P2,…,Pn}是n个参加人员的集合,n

2.2 密钥分发过程

(1)分配者D秘密地任意选取不全为零的a1,a2,…,ar-1∈GF(q),且ar-1≠0;

(2)分配者D任意选取互不相同的xi∈GF(q)(xi≠0),并交给参加人员Pi保管,且所有的xi都是公开的(i=1,2,…,n);

(3)分配者D计算zi=a(xi)和k′=kmr-1∈GF(q),其中

a(x)=kmr-1+a1mr-2x+a2mr-3x2+…+ar-2mxr-2+ar-1xr-1=k′+a1mr-2x+a2mr-3x2+…+ar-2mxr-2+ar-1xr-1

(1)

满足a(0)=k′；

(4)分配者D将密钥碎片zi交给参加人员Pi秘密保管(i=1,2,…,n)。

在密钥分发过程中,如果选取的m不同,则得到不同的k′=kmr-1,其中m∈GF(q),m≠0且m≠1。从而利用k′计算出不同的密钥碎片,也就加强了该方案的防攻击性。

2.3 密钥重构过程

新构造的动态密钥分存方案恢复密钥的过程与文献[2]中的基于多项式的(r,n)-门限方案恢复密钥的过程相似,不同之处是:在该方案中,通过任意选取r个参加人员所拥有的密钥碎片恢复出来的是k′=kmr-1;由于分配者D是秘密选取的m∈GF(q)(m≠0且m≠1),所以再通过分配者D就能够恢复密钥k。

3 新构造的动态密钥分存方案是(r,n)-门限方案

命题3.1构造的动态密钥分存方案是(r,n)-门限方案。

证明 根据(r,n)-门限方案的定义,只需证密钥k能够被n个参加人员中任意选取r个参加人唯一确定,但密钥k不能够被任意选取少于r个参加人唯一确定。

首先,证从n个参加人员中任意选取r个参加人员都能够唯一确定密钥k。

在新构造的动态密钥分存方案中,从n个参加人员中任意选取r个参加人,并用他们所拥有的密钥碎片唯一确定密钥的过程如下:对于∀k∈K,分配者D秘密地任意选取m∈GF(q)(m≠0且m≠1),算出k′=kmr-1。在所有的参加人员集合P中,不妨设任意选取r个参加人员Pt1,Pt2,…,Ptr拥有的密钥碎片分别为zt1,zt2,…,ztr代入式子(1)得:

其中,k′,a1mr-2,a2mr-1,…,ar-2m,ar-1是未知的。

其次,同理可证得密钥k不能够被任意选取少于r个参加人员唯一确定。

综上所述,证得新构造的动态密钥分存方案就是(r,n)-门限方案。

4 结论

本文新构造的动态密钥分存方案也是(r,n)-门限方案,但与基于拉格朗日插值公式的(r,n)-门限方案相比,有如下优点:新构造的动态密钥分存方案通过分配者D秘密地选取不同的m,算出的k′=kmr-1也就不相同,其中m∈GF(q),m≠0且m≠1;因此,所有参加人员所拥有k′的密钥碎片能够随时被更换,也就增强了该方案的安全性。

[1] M.Tompa,H.Woll.How to share a secret with cheaters[J].Journal of Cryptology,1988,(1):133-138.

[2] A.Shamir.How to share a secret[J].Communications of the ACM,1979,22(11):612-613.

[3] G.R.Blakley.Safeguarding cryptographic keys[J].AFIPS Conference Proceedings,1979,(48):313-317.

[4] E.D.Karnin,J.W.Green,M.E.Hellman.On secret sharing systems[J].IEEE Transactions on Information Theory,1982,IT-29(1):35-41.

[5] 潘承洞,潘承彪.初等数论(第二版)[M].北京:北京大学出版社,2003.

[6] W.Jackson,K.Martin.Geometric secret sharing schemes and their duals[J].Designs,Codes and Cryptography,1994,4(1):83-95.

[7] E.F.Brickell.Some ideal secret sharing schemes[J].J.Combin.Math and Combin.Comput.,1989,(9):105-113.

[8] J.Rifá-Coma.How to avoid cheaters succeeding in the key sharing scheme[J].Designs,Codes and Cryptography,1993,3(3):221-228. [9] S.Cabello,C.Padró,G.Sáez.Secret sharing scheme with detection of cheaters for a general access structure[J].Designs,Codes and Cryptography,2002,25(2):175-188.

[10] 林东岱.代数学基础与有限域[M].北京:高等教育出版社,2006.

A New (r,n) Dynamic Secret Share Scheme

LIUYin-yin,WEILu

(AnyangInstituteofTechnology,Anyang455000,China)

The (r,n) secret share scheme based on Lagrange interpolation formula is vulnerable, so a new dynamic secret share scheme is constructed by the initial process, key distribution and key reconstruction. This scheme is a (r,n) secret share scheme and can prevent being cheated by changing the participant's key pieces at any time.

Lagrange interpolation formula; secret share scheme; dynamic secret share scheme

2017-03-25

安阳工学院信息与计算科学专业综合改革试点项目(201401)

刘寅寅(1986-),男,硕士,安阳工学院数理学院教师,研究方向：图论、组合、最优化。

TN918

A

1674-3229(2017)02-0013-02