一類新的(r,n)動態(tài)密鑰分存方案

劉寅寅,魏 露

(安陽工學院，河南 安陽 455000)

?

一類新的(r,n)動態(tài)密鑰分存方案

劉寅寅,魏 露

(安陽工學院，河南 安陽 455000)

由于基于拉格朗日插值公式的(r,n)-門限方案易受到攻擊,所以通過初始過程,密鑰分發(fā)過程和密鑰重構(gòu)過程構(gòu)造了一類新的動態(tài)密鑰分存方案,同時證明了新構(gòu)造的動態(tài)密鑰分存方案是(r,n)-門限方案,并且該方案通過隨時更換參加者所擁有的密鑰碎片來防欺詐。

拉格朗日插值公式；門限方案；動態(tài)密鑰分存方案

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 構(gòu)造新的動態(tài)密鑰分存方案

由產(chǎn)生上述攻擊的原因,構(gòu)造了一類新的(r,n)動態(tài)密鑰分存方案。新構(gòu)造的動態(tài)密鑰分存方案通過分配者D秘密地選取不同的m,算出的k′=kmr-1也就不相同。因此,所有參加人員所擁有的密鑰碎片能夠隨時被更換,也就增強了該方案的安全性。新構(gòu)造的動態(tài)密鑰分存方案分為三個過程：初始過程、密鑰分發(fā)過程和密鑰重構(gòu)過程。

2.1 初始過程

在有限域GF(q)中(q是一個素數(shù)冪),P={P1,P2,…,Pn}是n個參加人員的集合,n

2.2 密鑰分發(fā)過程

(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)。

在密鑰分發(fā)過程中,如果選取的m不同,則得到不同的k′=kmr-1,其中m∈GF(q),m≠0且m≠1。從而利用k′計算出不同的密鑰碎片,也就加強了該方案的防攻擊性。

2.3 密鑰重構(gòu)過程

新構(gòu)造的動態(tài)密鑰分存方案恢復密鑰的過程與文獻[2]中的基于多項式的(r,n)-門限方案恢復密鑰的過程相似,不同之處是:在該方案中,通過任意選取r個參加人員所擁有的密鑰碎片恢復出來的是k′=kmr-1;由于分配者D是秘密選取的m∈GF(q)(m≠0且m≠1),所以再通過分配者D就能夠恢復密鑰k。

3 新構(gòu)造的動態(tài)密鑰分存方案是(r,n)-門限方案

命題3.1構(gòu)造的動態(tài)密鑰分存方案是(r,n)-門限方案。

證明 根據(jù)(r,n)-門限方案的定義,只需證密鑰k能夠被n個參加人員中任意選取r個參加人唯一確定,但密鑰k不能夠被任意選取少于r個參加人唯一確定。

首先,證從n個參加人員中任意選取r個參加人員都能夠唯一確定密鑰k。

在新構(gòu)造的動態(tài)密鑰分存方案中,從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個參加人員唯一確定。

綜上所述,證得新構(gòu)造的動態(tài)密鑰分存方案就是(r,n)-門限方案。

4 結(jié)論

本文新構(gòu)造的動態(tài)密鑰分存方案也是(r,n)-門限方案,但與基于拉格朗日插值公式的(r,n)-門限方案相比,有如下優(yōu)點:新構(gòu)造的動態(tài)密鑰分存方案通過分配者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] 潘承洞,潘承彪.初等數(shù)論(第二版)[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] 林東岱.代數(shù)學基礎與有限域[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

安陽工學院信息與計算科學專業(yè)綜合改革試點項目(201401)

劉寅寅(1986-),男,碩士,安陽工學院數(shù)理學院教師,研究方向：圖論、組合、最優(yōu)化。

TN918

A

1674-3229(2017)02-0013-02