莊鋒茂,胡慧丹,林昌露
(1.福建體育職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)部,福建 福州 350003;2.福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福建 福州 350117)
1979年,Shamir[1]利用拉格朗日插值多項(xiàng)式提出了(t,n)-門限的秘密共享方案.在該方案中,一個(gè)誠實(shí)的第三方將秘密拆分成n份共享,并將每一份共享秘密地分發(fā)給n位不同的參與者;其中,任意t個(gè)或大于t個(gè)參與者的合作能重構(gòu)出秘密(正確性),而任意小于t個(gè)參與者的合作得不到關(guān)于秘密的任何消息(隱私性).同年,Blakley[2]借助幾何的方法提出了不同的秘密共享方案.1983年,Mignotte[3]和Asmuth-Bloom[4]借助中國剩余定理提出了新的門限秘密共享方案.
為了豐富秘密共享方案,許多的學(xué)者利用不同的數(shù)學(xué)工具,如:二進(jìn)制序列,格,二元對(duì)稱多項(xiàng)式,雙線性映射,等等,分別地提出了各種秘密共享方案[5-9],以滿足不同的應(yīng)用需求.2017年,Deepika和Sreekumar[10]基于格雷碼和異或運(yùn)算提出了一類新的秘密共享方案.其中利用格雷碼技術(shù)實(shí)現(xiàn)秘密分發(fā),而用異或運(yùn)算實(shí)現(xiàn)安全的秘密重構(gòu).作者稱該方案無信息丟失且可應(yīng)用于視覺密碼學(xué)中.顯然,參與者僅僅需要進(jìn)行異或運(yùn)算就能還原出秘密,與傳統(tǒng)的其他方案比較,該方按可大量地減少了參與者的計(jì)算量.通過詳細(xì)的安全性分析發(fā)現(xiàn),該方案存在安全漏洞并給出了具體的攻擊方式,進(jìn)而給出了一個(gè)改進(jìn)的安全方案.在改進(jìn)方案中,我們?cè)诠蚕砩呻A段添加了隨機(jī)值用以破壞共享之間的關(guān)聯(lián)性;通過一些公開值實(shí)現(xiàn)了方案的正確性.
格雷碼是一類循環(huán)二進(jìn)制單位距離碼,它是任意兩個(gè)相鄰的碼字只有一位二進(jìn)制數(shù)不同的編碼,它與奇偶校驗(yàn)碼同屬可靠性編碼.
異或也叫半加運(yùn)算,其運(yùn)算法則相當(dāng)于不帶進(jìn)位的二進(jìn)制加法,二進(jìn)制下1表示真,0表示假,則異或的運(yùn)算法則為:0⊕0=0,1⊕0=0⊕1=1,1⊕1=1.
二進(jìn)制碼轉(zhuǎn)換成格雷碼,其法則是保留二進(jìn)制碼的最高位作為格雷碼的最高位,而次高位格雷碼為二進(jìn)制碼的高位與次高位相異或,而格雷碼其余各位與次高位的求法類似.例如:
某二進(jìn)制數(shù)為:Bn-1Bn-2…B2B1B0
其對(duì)應(yīng)的格雷碼為:Gn-1Gn-2…G2G1G0
具體地,最高位保留Gn-1=Bn-1,其他各位數(shù)Gi=Bi+1⊕Bi,其中 i=0,1,…,n-2.
Deepika和Sreekumar[10]借助格雷碼與異或運(yùn)算提出一類新的秘密共享方案,該方案不同于基于多項(xiàng)式的秘密共享方案和基于中國剩余定理的秘密共享方案.該方案利用簡單的異或運(yùn)算實(shí)現(xiàn)了秘密的重構(gòu),這可大量地減低了每位參與用戶的計(jì)算量.本節(jié)主要簡要回顧Deepika-Sreekumar的秘密共享方案.具體地,Deepika和Sreekumar給出了該類型秘密共享方案的兩種構(gòu)造:一種是(7,7)-門限秘密共享方案,即只有7個(gè)參與者都拿出他們的共享才能重構(gòu)出秘密;另一種是(3,7)-門限秘密共享方案,即僅有三個(gè)特定的參與者就可還原秘密.這兩種情形的秘密共享方案的共享的生成算法是一樣的,但是它們的秘密恢復(fù)算法不一樣.具體步驟如下所示.
第一步:輸入主秘密S,將S轉(zhuǎn)化為二進(jìn)制數(shù).
第二步:將秘密S轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G.
第二步:計(jì)算共享S1,S1=G;將秘密S1轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G1.
第三步:計(jì)算共享S2,S2=G1;將秘密S2轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G2.
第四步:計(jì)算共享S3,S3=G2;將秘密S3轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G3.
第五步:計(jì)算共享S4,S4=G3;將秘密S4轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G4.
第六步:計(jì)算共享S5,S5=G4;將秘密S5轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G5.
第七步:計(jì)算共享S6,S6=G5;將秘密S6轉(zhuǎn)化成它所對(duì)應(yīng)的格雷碼G6.
第八步:計(jì)算共享S7,S7=G6
第九步:將二進(jìn)制 S1,S2,S3,S4,S5,S6,S7轉(zhuǎn)化為十進(jìn),輸出十進(jìn)制的 7 個(gè)共享 S1,S2,S3,S4,S5,S6,S7,并秘密地分發(fā)給7位不同的參與者.
1)第一階段
第一步:輸入 S1,S2,S3,S4,S5,S6,S7.
第二步:判定共享的下標(biāo)i是否整除2;如果i-2=0,則Si是授權(quán)集里的共享;否則Si不是授權(quán)集里的共享.
第三步:輸出共享 S2,S4,S6.
2)第二階段
第一步:輸入 S2,S4,S6,并將 S2,S4,S6轉(zhuǎn)化為二進(jìn)制數(shù).
第二步:計(jì)算S2⊕S4⊕S6.
第三步:將M轉(zhuǎn)化為十進(jìn)制數(shù).
第四步:輸出秘密S=M.
第一步:輸入 S1,S2,S3,S4,S5,S6,S7,并將 S1,S2,S3,S4,S5,S6,S7轉(zhuǎn)化為二進(jìn)制數(shù).
第二步:計(jì)算 S1⊕S2⊕S3⊕S4⊕S5⊕S6⊕S7=M.
第三步:將M轉(zhuǎn)化為十進(jìn)制數(shù).
第四步:輸出秘密S=M.
本節(jié)將通過具體實(shí)例來闡述Deepika和Sreekumar提出的兩種情形的門限秘密共享方案存在嚴(yán)重的安全漏洞.將指出它們無法滿足門限秘密共享方案的最基本的隱私性與正確性要求.不失一般性,假設(shè)秘密S=860,通過執(zhí)行“共享的生成算法”得到秘密S的二進(jìn)制形式S=1101011100,以及7個(gè)共享:S1=1011110010,S2=1110011011,S3=1001010110,S4=1101111101,S5=1011010011,S6=1110111010,S7=1001110111.
將分析 Deepika 和 Sreekumar設(shè)計(jì)的 (3,7)-門限秘密共享方案與(7,7)-門限秘密共享方案均無法確保其隱私性:1)每個(gè)參與者利用所持有的一個(gè)共享都可以恢復(fù)秘密;2)參與者能獲得其他參與者的共享.
3.1.1 參與者P1利用S1得到秘密S
參與者P1可通過執(zhí)行以下的兩個(gè)步驟成功地獲得秘密.
第一步:P1可以得到S的格雷碼G=S1=1011110010.
第二步:設(shè) S=B9B8B7B6B5B4B3B2B1B0,G=G9G8G7G6G5G4G3G2G1G0,其中 B9=G9=1,B8=B9⊕G8=1⊕0=1,B7=B8⊕G7=1⊕1=0,B6=B7⊕G6=0⊕1=1,B5=B6⊕G5=1⊕1=0,B4=B5⊕G4=0⊕1=1,B3=B4⊕G3=1⊕0=1,B2=B3⊕G2=1⊕0=1,B1=B2⊕G1=1⊕1=0,B0=B1⊕G0=0⊕0=0, 易知,參
與者P1通過以上計(jì)算可獲得秘密S.
3.1.2 參與者Pi獲得其他參與者Pj的共享
參與者Pii=(2,3,…,7)不僅能得到秘密S,還能得到其他參與者Pj(j<i)的共享.具體地,參與者 Pii=(2,3,…,7)通過以下的步驟成功地獲得其他參與者Pj(j<i)的共享,且可恢復(fù)出秘密.
第一步:Pi可以獲得Pi-1的共享Si-1的格雷碼Gi-1=Si.
第三步:Pi重復(fù)的執(zhí)行i-1次步驟1,2即可得到Si-2,Si-3,…,S1,S,并可正確地恢復(fù)出秘密S.
本節(jié)僅對(duì)Deepika和Sreekumar提出的 (3,7)-門限秘密共享方案不滿足正確性要求給出詳細(xì)的分析.即該方案不滿足任意3個(gè)或大于3個(gè)參與者能正確地恢復(fù)秘密;小于3個(gè)參與者無法還原秘密.由于(7,7)-門限秘密共享方案中7個(gè)參與者全部參與能還原出秘密,因此 Deepika和 Sreekumar提出的(7,7)-門限秘密共享方案滿足正確性.通過以下例子說明(3,7)-門限秘密共享存在的缺陷,具體步驟如下所示:
設(shè)參與者P1,P2,P3去重構(gòu)秘密,參與者P1,P2,P3利用所得到的三個(gè)共享S1=1011110010,S2=1110011011,和S3=1001010110進(jìn)行異或運(yùn)算去還原秘密.首先對(duì)S1和S2進(jìn)行異或運(yùn)算得結(jié)果m1=S1⊕S2=1011110010⊕1110011011=0101101001,然后再將m1和S3進(jìn)行異或運(yùn)算得到結(jié)果m2=m1⊕S3=0101101001⊕1001010110=11001111111.我們發(fā)現(xiàn)通過共享,S1,S2和S3所得到的結(jié)果m2≠S.具體的重構(gòu)秘密的運(yùn)算過程如下所示.
設(shè)參與者P1,P2,P4,P6去重構(gòu)秘密,參與者P1,P2,P4,P6利用所得到的四個(gè)共享 S1=1011110010,S2=1110011011,S4=1101111101 和 S6=1110111010 執(zhí)行重構(gòu)算法去還原秘密.首先需要對(duì)S1=1011110010和S2=1110011011執(zhí)行異或運(yùn)算得到結(jié)果m3=S1⊕S2=0101101001,然后再對(duì) m3=101101001和S4=1101111101執(zhí)行異或運(yùn)算得到結(jié)果 m4=m3⊕S4=1000010100,最后計(jì)算 m4⊕S6得到結(jié)果 m6=0110101110.我們發(fā)現(xiàn)通過共享 S1,S2,S4和 S6所得到的結(jié)果m5≠S.具體的運(yùn)算過程如下所示.
通過以上的兩個(gè)例子說明Deepika和Sreekumar所提出的(3,7)-門限秘密共享方案無法滿足任意的三個(gè)或大于三個(gè)參與者都能還原出真正的秘密這個(gè)性質(zhì).
本節(jié)將改進(jìn)Deepika和Sreekumar的秘密共享方案,僅對(duì)提出(3,7)-門限秘密共享方案的給出具體的改進(jìn).在改進(jìn)的方案中,在重構(gòu)階段也僅只需要做異或運(yùn)算,且滿足正確性和隱私性.該改進(jìn)方案的共享生成算法和秘密恢復(fù)算法分別描述如下.
第一步:可信第三方執(zhí)行第2.1節(jié)中“生成算法”過程中將秘密 S 生成 7 個(gè)偽共享 S1,S2,S3,S4,S5,S6,S7.
第二步:第三方任意的選擇7個(gè)隨機(jī)值K1,K2,K3,K4,K5,K6,K7, 將 K1, K2,K3,K4,K5,K6,K7, 轉(zhuǎn)化為二進(jìn)制數(shù),再計(jì)算共享 Y1=S1⊕K1,Y2=S2⊕K2,Y3=S3⊕K3,Y4=S4⊕K4,Y5=S5⊕K5,Y6=S6⊕K6,Y7=S7⊕K7.
第三步:第三方計(jì)算公開值A(chǔ)i1i2i3.具體地,Ai1i2i3=Yi1⊕Yi2⊕Yi3⊕S,其中這里 S 為秘密且{i1,i2,i3}是{1,2,…,7}的任意3元子集,公開哈希值H(S),其中H為安全的哈希函數(shù).
第四步: 第三方通過安全的信道將 Y1,Y2,Y3,Y4,Y5,Y6,Y7傳輸給參與者 U1,U2,U3,U4,U5,U6,U7.
假設(shè)任意三位參與者Ui1,Ui2,Ui3重構(gòu)秘密S,利用公開值A(chǔ)i1i2i3和三個(gè)共享Yi1,Yi2,Yi3即可計(jì)算秘密.
本節(jié)將通過兩個(gè)定理來論證改進(jìn)的秘密共享方案滿足正確性和隱私性要求.
定理 1(正確性):在改進(jìn)方案中,任意3個(gè)或大于3個(gè)的參與者利用手中的共享執(zhí)行秘密重構(gòu)算法可以重構(gòu)出正確的秘密.
定理2(隱私性):在改進(jìn)的方案中,小于3個(gè)參與者利用手中的共享執(zhí)行秘密重構(gòu)算法無法恢復(fù)秘密.
證明:不失一般性,假定參與者U1,U2擬重構(gòu)秘密S.由于參與者U1,U2只有共享Y1,Y2但沒有公開值A(chǔ)1,2,因此參與者無法利用公開值A(chǔ)1,2執(zhí)行秘密重構(gòu)算法,這使得秘密重構(gòu)算法無法正確的計(jì)算Y1⊕Y2⊕A1,2并恢復(fù)正確的秘密.此外,參與者U1或U2各自均無法通過公開值或自己的共享份額計(jì)算得到其他參與者的共享.其原因是,他們各自的共享中包含了一個(gè)隨機(jī)值,即Y1=S1⊕K1和Y2=S2⊕K2中分別含有隨機(jī)值K1和K2,且這隨機(jī)值只有分發(fā)者知道,而任何一個(gè)參與者不僅不知道與自己共享相關(guān)的隨機(jī)值,而且無法預(yù)測得到與其他參與者相關(guān)的那個(gè)隨機(jī)值的任何信息.
本文對(duì)Deepika和Sreekumar所提出的兩種秘密共享方案給出了具體的安全性分析.分析結(jié)果表明:他們所提出的方案中每個(gè)參與者僅僅通過自己的共享可以還原秘密,同時(shí)還能得到其他參與者的共享,即無法達(dá)到隱私性.同時(shí)通過兩個(gè)具體的例子說明他們?cè)O(shè)計(jì)的(3,7)-門限的秘密共享方案無法保證正確性.最后,本文對(duì)(3,7)-門限的秘密共享方案給出了的一種改進(jìn)的方案,并確保了改進(jìn)的方案能達(dá)到秘密共享的隱私性及正確性.