黃科華
(泉州幼兒師范高等??茖W(xué)校初等教育系,福建泉州362000)
秘密分享方案的主要目的是用來(lái)解決在特定用戶(準(zhǔn)入結(jié)構(gòu))中分享一個(gè)秘密.一個(gè)秘密分享方案(SSS)主要包含以下幾個(gè)方面:秘鑰分發(fā)者D,參與用戶集合P,準(zhǔn)入結(jié)構(gòu)Γ,秘鑰空間S,分配算法和恢復(fù)算法.
Shamir[1]和 Blakley[2]與1979年分別獨(dú)立提出了(t,n)門限秘密分享方案,通過(guò)該方案,n用戶中只要有t個(gè)及以上的人合作就能合成秘鑰,而少于t個(gè)用戶就得不到秘鑰的任何信息.當(dāng)然,兩個(gè)方案都存在許多不足的地方,如1)秘密份額是一次性的,不能重復(fù)利用;2)秘鑰分發(fā)者的權(quán)利過(guò)大,有可能導(dǎo)致秘鑰分發(fā)者的欺騙,比如發(fā)送無(wú)效的份額;3)每次只能共享一個(gè)秘鑰,秘鑰的信息不夠大等.在兩個(gè)方案的基礎(chǔ)上,Asmuth和Bloom[3]在1983年提出的基于中國(guó)剩余定理的門限方案;Brlckell[4]等人在1991年提出了理想化的秘密共享方案;黃科華[5]結(jié)合單向函數(shù)和二元多項(xiàng)式的方案解決了秘鑰的一次性使用的問題,本文正是在此基礎(chǔ)上,利用中國(guó)剩余定理,提供了一個(gè)多秘密的分享方案,而且在這個(gè)方案中,引入可驗(yàn)證的秘鑰機(jī)制,來(lái)避免秘鑰欺騙.
陷門單項(xiàng)函數(shù)h(x)滿足以下兩個(gè)條件,(i)給定x,能夠容易地計(jì)算y=h(x);
(ii)給定y,計(jì)算x=h-1(y)是困難的,但是如果知道陷門,可以容易地計(jì)算出y.
陷門單向函數(shù)可以選擇離散對(duì)數(shù)函數(shù)或者RSA函數(shù)等.
設(shè)整數(shù) m1,m2,…mn兩兩互質(zhì),對(duì)于任意整數(shù) s1,s2,…sn,方程組:
設(shè)有n個(gè)用戶為P1,P2,…Pn.每個(gè)Pj自己選取一個(gè)向量作為自己的私鑰(且yij≠ymn,i≠m 或者 j≠ n),并計(jì)算 h(yij),i=0,1,2,…t,j=1,2,…n.其中h(x)為無(wú)碰撞陷門單向函數(shù),由秘鑰分發(fā)者D選取并公布,陷門信息由D掌握.
設(shè)s1,si,…sn是需要分享的多個(gè)秘鑰,秘鑰分發(fā)者D選擇n個(gè)互質(zhì)的整數(shù) m1,m2,…mn,通過(guò)中國(guó)剩余定理得到modM的唯一解S.
D構(gòu)造一個(gè)二元多項(xiàng)式f(x,y),表達(dá)式如下:
并使得a00=S(常數(shù)項(xiàng)為秘鑰S)
D 計(jì)算 f(xi,yij),i=0,1,2,…,t,j=1,2,3,…,n.并公布.
不妨設(shè) f(xi,yij)=Aij,i=0,1,2,…,t,j=1,2,3,…,n
三個(gè)月前,他們瞞著所有的人,寫了一份分手協(xié)議,分配了財(cái)產(chǎn)。但他們彼此各退一步,商定等孩子三年后上了大學(xué),再公布于眾。按照協(xié)議規(guī)定,他們互不打探干涉對(duì)方的私生活,仍在一個(gè)屋檐下或者另租居所,不過(guò),每月孩子回來(lái)的那天必須琴瑟和鳴夫唱婦隨。
t+1個(gè)用戶合作可以通過(guò)以下方式恢復(fù)二元多項(xiàng)式,取得S.
從公告牌中的 xi,(i=0,1,2,…,t)可以得出下列方程組:
即
t+1 個(gè)用戶可以拿出 yij0,yij1,…,yijt,
其中 0 ≤ j0,j1,…,jt(均為正整數(shù))≤ n,i=0,1,2,…,t
代入(2)式可得:
(3)可以寫成方程組:
也即是以下的矩陣:
由(2)式可得下列方程組:
其中 j=0,1,2,…,t.
寫成矩陣即為:
由于xi≠xj,i≠j,所以系數(shù)矩陣為范德蒙矩陣,能夠解出唯一解:
因?yàn)槟軌蚝铣烧麄€(gè)二元多項(xiàng)式,取得S.
取得S后,每個(gè)用戶可以再?gòu)墓嫉膍1,m2,…mn中解出所有的秘鑰 s1,si,…sn.
從方案中可以看出,該方案為(t+1,n)門限方案,t+1個(gè)人合作可以順利恢復(fù)秘鑰,而少于t+1,就無(wú)法從方程組4(或者矩陣 5)中恢復(fù)出(Bi0,Bi1,…,Bit),i=0,1,2,…,t,因而,也無(wú)法從方程組6(或者矩陣7)中恢復(fù)出系數(shù)(a0j,a1j,…,atj),j=0,1,2,…,t,故不能得到密鑰 S.
利用中國(guó)剩余定理,把多個(gè)秘密封裝成S進(jìn)行分發(fā),合成用戶可以通過(guò)公布的m1,m2,…mn取得多個(gè)秘鑰.
由于使用了陷門單向函數(shù),所有的交流都可以在公用信道上達(dá)成,整個(gè)秘密共享的過(guò)程不需要任何的安全信道.而且,公布在外面的只是h(yij),用戶的份額沒有泄露,所以份額可以多次使用.
由于秘密份額是用戶自己選擇并發(fā)布的,所以任何用戶都可以通過(guò)公布的h(x)驗(yàn)證分發(fā)者提供的份額是不是正確的.這限制了分發(fā)者的權(quán)利.
當(dāng)完成一次秘密分享以后,秘鑰分發(fā)者D只需要更新陷門單線函數(shù)h(x)即可.
本文是文[5]的進(jìn)一步改進(jìn),除了繼承文[5]的優(yōu)點(diǎn)之外,該系統(tǒng)不需要安全信道,并且防止了秘鑰分發(fā)者D的欺騙,是可驗(yàn)證的秘密分享方案.
[1]Shamir A.How to share a secret[J].Communications of the ACM,1979,(11):612-613.
[2]Blakley G R.Safeguarding cryptographic keys[A].Managing Requirements Knowledge,International Workshop on[C].IEEE Computer Society,1899.
[3]Asmuth C,Bloom J.A modular approach to key safeguarding[J].IEEE Transactions on Information Theory,1983,(2):208-210.
[4]Brickell E F,Davenport D M.On the classification of ideal secret sharing schemes[J].Journal of Cryptology,1991,(2):123-134.
[5]黃科華,熱娜·艾合買提,張瑛瑛.基于單向函數(shù)與二元多項(xiàng)式的秘密分享方案[J]魯東大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,(3):223-227.
長(zhǎng)沙大學(xué)學(xué)報(bào)2015年2期