夏 高，何成萬

（武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，武漢 430205）

0 概述

秘密共享體制可將一份秘密安全地交給多方保管，其在商業(yè)秘密保管、銀行網(wǎng)絡(luò)管理等注重信息安全的領(lǐng)域發(fā)揮重要作用。秘密共享又稱（k，n）門限秘密共享。將一份秘密信息S在n個(gè)參與方中進(jìn)行分配，每個(gè)參與方所保管的部分稱為S的一個(gè)影子秘密。若掌握其中任意k個(gè)影子秘密，即可計(jì)算還原出S，但若只是掌握任意不足k個(gè)影子秘密，則無法獲取S的任何內(nèi)容，k為恢復(fù)S所需影子的最小秘密個(gè)數(shù)?，F(xiàn)有的秘密共享方案大部分基于SHAMIR 算法發(fā)展而來，這類方法均涉及復(fù)雜多項(xiàng)式計(jì)算，在實(shí)際應(yīng)用中處理信息非常耗時(shí)。針對該問題，本文基于異或運(yùn)算構(gòu)建秘密共享算法，以期提高數(shù)據(jù)處理速度。

1 相關(guān)工作

1979 年，SHAMIR［1］提出了秘密共享的概念，其方案基于多項(xiàng)式插值進(jìn)行，涉及大量多項(xiàng)式計(jì)算，方案較為復(fù)雜且計(jì)算量較大，速度較慢。此后多種基于異或運(yùn)算的秘密共享算法被相繼提出［2-4］，與SHAMIR 算法相比顯著提高了計(jì)算效率。

近年來，抗泄漏秘密共享［11-12］成為一個(gè)熱門的研究方向。隨著側(cè)信道攻擊技術(shù)［13-14］不斷發(fā)展，傳統(tǒng)秘密共享方案的安全性受到嚴(yán)重威脅，特別對于需長期維護(hù)的秘密，敵手可利用側(cè)信道攻擊技術(shù)獲取一定數(shù)量的秘密、秘密份額或者方案相關(guān)信息［15］。對此，AGGARWAL 等［16］提出一種強(qiáng)抗泄露的秘密共享方案，提出一種基于一般訪問模型將非抗泄露的秘密共享方法轉(zhuǎn)化為抗泄露的方法。

身份認(rèn)證協(xié)議［17-18］的目標(biāo)是確認(rèn)用戶當(dāng)前聲稱自己的身份信息是準(zhǔn)確無誤的。作為抵御攻擊的第一道屏障，身份認(rèn)證可以有效防止離線字典攻擊和身份偽造攻擊［19-20］。生活中常見的輸入密碼登錄網(wǎng)站、指紋驗(yàn)證解鎖手機(jī)等場景均是身份認(rèn)證協(xié)議的應(yīng)用。

作為一種基礎(chǔ)的加密協(xié)議，秘密共享協(xié)議可以應(yīng)用于身份認(rèn)證。一種較直接的思路是，對某個(gè)密鑰S進(jìn)行（k，n）秘密共享分散，用戶持有其中m（m

2 本文算法

2.1 異或運(yùn)算的性質(zhì)

異或（XOR）運(yùn)算是一種二進(jìn)制運(yùn)算。假設(shè)對于一個(gè)二進(jìn)制序列L1，將其與另一個(gè)等長的二進(jìn)制序列L2進(jìn)行異或運(yùn)算，記運(yùn)算結(jié)果為L3，L1XORL2=L3。根據(jù)異或運(yùn)算的可逆性，有L3XORL2=L1。將L1視作待加密信息，將L2視作加密鍵，序列L3為加密后的密文。在缺失L2的情況下，解密者只掌握L3的信息，無法根據(jù)L3推測出秘密L1。只有獲取L2和L3后，解密者才可通過L3XORL2=L1來還原秘密L1。

以（3，4）門限秘密共享為例介紹本文算法原理和具體過程。

2.2 （3，4）秘密共享算法

（3，4）秘密共享算法整體包含以下2 個(gè)步驟：

25歲，她生下第一個(gè)孩子。女孩，取名Isabel。在孩子3歲時(shí)，他們舉行婚禮，她又已懷孕。第二個(gè)孩子是男孩，Alex。她對感情失去一個(gè)階段性的寄望，找到一個(gè)合作的男子停歇下來。她需要休息。他們之間肉身聯(lián)系如此緊密，以個(gè)性和特質(zhì)互相施展魔力。這段婚姻，肉體的粘著沉迷是牢固堅(jiān)實(shí)的基礎(chǔ)。除此之外，不過是一對精神模式上沒有共通之處的異國男女。

1）將秘密S轉(zhuǎn)化為6 個(gè)二進(jìn)制序列，S能且只能由全部6 個(gè)二進(jìn)制序列一起通過計(jì)算還原，其中每個(gè)二進(jìn)制序列稱為秘密S 的1 條線索。

2）對這6 條線索，按照一定規(guī)則進(jìn)行分組存儲，每組二進(jìn)制序列形成S的1 個(gè)影子秘密。只有掌握足夠數(shù)量的影子秘密，使這些影子秘密包含著全部6 條線索，原秘密S才能被還原。

在（3，4）秘密共享的情況下，將秘密S轉(zhuǎn)化為線索的過程描述如下：

1）對于秘密S，將其轉(zhuǎn)化為對應(yīng)的二進(jìn)制序列G。

2）對于G，隨機(jī)生成1個(gè)等長的二進(jìn)制序列，記為K1。

3）對G和K1進(jìn)行異或運(yùn)算，記運(yùn)算結(jié)果為G1，GXORK1=G1。

4）隨機(jī)生成1 個(gè)與G1等長的二進(jìn)制序列K2，G1XORK2=G2。

5）隨機(jī)生成1 個(gè)與G2等長的二進(jìn)制序列K3，G2XORK3=G3。

6）隨機(jī)生成1 個(gè)與G3等長的二進(jìn)制序列K4，G3XORK4=G4。

7）隨機(jī)生成1 個(gè)與G4等長的二進(jìn)制序列K5，G4XORK5=G5。

8）保留K1、K2、K3、K4、K5、G5這6 個(gè)二進(jìn)制序列為算法所需的全部線索，刪除過程中所有其他二進(jìn)制序列。線索獲取完畢。

9）線索獲取完畢后，按照一定規(guī)則將6 個(gè)線索分為4 組，分配結(jié)果將使得每組線索的集合成為原秘密S的一個(gè)影子秘密。記這4 個(gè)影子秘密分別為A、B、C、D。在分組時(shí)，需遵循以下2 條規(guī)則：

（1）對于S的任意一個(gè)線索，都要至少存儲在2 個(gè)不同的組中各1 次。

（2）對于A、B、C、D，任取其中2 組，都至少有1 個(gè)線索是只存在于這2 組中各1 次的。

根據(jù)數(shù)學(xué)排列組合的知識，S至少要有6 條線索才能滿足分組規(guī)則。分配結(jié)果并不具有唯一性。一種可行的分配結(jié)果如表1 所示。分配完成后，當(dāng)A、B、C、D，中只缺失任意某1 組時(shí)，剩余3 組已攜帶全部6 個(gè)線索，S可被還原。若4 組中缺失任意2 組，必有1 個(gè)線索缺失，S無法還原，目標(biāo)達(dá)到（3，4）秘密共享算法。

表1 分配結(jié)果Table 1 Distribution result

假設(shè)掌握了A、B、C的信息，從A、B、C的影子秘密恢復(fù)出S的步驟如圖1 所示。

圖1 基于異或運(yùn)算的恢復(fù)過程Fig.1 Restore process based on XOR operation

假設(shè)待加密信息S轉(zhuǎn)化為二進(jìn)制序列后為11010010，算法分散過程如圖2 所示。按照從上往下的順序，隨機(jī)二進(jìn)制生成器生成一個(gè)與G等長的二進(jìn)制K1，并與G進(jìn)行異或運(yùn)算，將運(yùn)算結(jié)果記為G1。在此基礎(chǔ)上，G1再與隨機(jī)生成的二進(jìn)制序列K2進(jìn)行異或運(yùn)算。依次異或，直至異或運(yùn)算進(jìn)行5 次為止。

圖2 秘密S 的分散過程Fig.2 Distribution process of secret S

在全部異或運(yùn)算完成后，只保存K1、K2、K3、K4、K5、G5這6 條線索，其余信息均不保存。對于線索的分組，根據(jù)前述規(guī)則，某一個(gè)線索只能存入某2 組中各1 次，且每次影子秘密的組合不與之前任意1 次組合重復(fù)。記4 組線索集合為A、B、C、D。具體分組過程描述為：1）對于K1，分別存入A、B組；2）對于K2，分別存入A、C組；3）對于K3，分別存入A、D組；4）對于K4，分別存入B、C組；5）對于K5，分別存入B、D組；6）對于G5，分別存入C、D組。

假設(shè)已完全掌握了A、B、C的全部信息，還原S的步驟如圖3 所示。首先從C中取出G5，從B中取出K5，兩者異或生成G4。在此基礎(chǔ)上，依次從A、B、C中取出線索K4、K3、K2、K1，并依次與上一次異或運(yùn)算的結(jié)果進(jìn)行異或運(yùn)算。當(dāng)全部異或運(yùn)算完成時(shí)，秘密信息S即被成功還原。

圖3 秘密S 的還原過程Fig.3 Restore process of secret S

2.3 （k，n）秘密共享算法

基于2.2 節(jié)的舉例說明，本節(jié)提出一種基于異或運(yùn)算的（k，n）秘密共享算法。記算法生成的影子秘密分別為A1，A2，…，An，全體影子秘密的集合為U。算法步驟描述如下：

將S轉(zhuǎn)化為線索的方法并不唯一，本文采用圖4所示方法進(jìn)行分散。將S轉(zhuǎn)換為二進(jìn)制序列G，隨機(jī)生成一個(gè)等長的二進(jìn)制序列K1、G和K1進(jìn)行異或運(yùn)算，將結(jié)果記為G2。重復(fù)此步驟，每次生成的K與之前一次異或運(yùn)算的結(jié)果進(jìn)行異或運(yùn)算。重復(fù)異或m－1 次，保留最后一次異或的結(jié)果Gm?1和全部的K。S能且只能由這m條線索還原，缺少任意一條線索都會(huì)導(dǎo)致S無法還原。

圖4 基于異或運(yùn)算的分散過程Fig.4 Distribution process based on XOR operation

恢復(fù)S的過程是分散S的逆過程。在獲取到任意k個(gè)影子秘密全部信息的前提下，按照分散的逆序，依次異或運(yùn)算還原G：Gm?1XORkm?1XORkm?2XOR…XORk1=G。當(dāng)獲取的影子秘密個(gè)數(shù)不及k時(shí)，至少一個(gè)線索缺失，S無法還原。

3 安全性證明

對本文算法進(jìn)行安全建模，如圖5 所示，安全目標(biāo)如下：

圖5 安全模型Fig.5 Safety model

1）被攻破的服務(wù)器數(shù)量少于k時(shí)，原秘密信息仍維持保密。攻擊者必須攻破至少k臺服務(wù)器才能獲取到原秘密信息。

2）原秘密信息可被長期安全存儲。一定時(shí)間后已經(jīng)泄露的少量信息將失去價(jià)值。

以（2，3）秘密共享為例，假設(shè)攻擊者試圖獲取秘密信息S，必須滲透2 臺存儲影子秘密服務(wù)器，設(shè)法獲取到每臺服務(wù)器上的全部影子秘密的信息，理論上S才有泄露的可能性。由于單個(gè)影子秘密和原秘密信息S沒有任何邏輯上的聯(lián)系，即使1 臺服務(wù)器中的影子秘密的信息全部被竊取，理論上原秘密S仍然維持保密狀態(tài)，攻擊者無法根據(jù)現(xiàn)有信息推測出任何原機(jī)密信息S的內(nèi)容。

算法的安全性依賴于可信第三方以及安全的信道。可信第三方可定期重新運(yùn)行算法對現(xiàn)存影子秘密進(jìn)行更新，由于算法基于隨機(jī)二進(jìn)制的生成而構(gòu)建，每次更新后影子秘密與更新前影子秘密不存在聯(lián)系，因此加大了攻擊者獲取S的難度，解決了多次部分影子秘密信息的泄露導(dǎo)致S泄露的問題，從而使秘密信息長時(shí)間存儲的安全性得到保證。

4 實(shí)驗(yàn)與結(jié)果分析

Crypto++是基于C++語言實(shí)現(xiàn)的加密算法庫，庫中實(shí)現(xiàn)了SHAMIR 秘密共享算法［1］。由 于Crypto++加密庫和SHAMIR 的秘密共享算法均被廣泛使用，因此將本文算法與Crypto++所實(shí)現(xiàn)的SHAMIR 算法進(jìn)行對比，完成速度方面的性能評估。

在相同的實(shí)驗(yàn)環(huán)境下，通過對一個(gè)大小為10 MB的文件進(jìn)行（3，4）秘密共享算法的處理，分別記錄2種方法加密和還原過程的耗時(shí)。多次實(shí)驗(yàn)后，取平均耗時(shí)進(jìn)行對比。實(shí)驗(yàn)環(huán)境設(shè)定為：操作系統(tǒng)為Windows 10 Professional Edition，處理器為Intel I7-4700HQ 2.40 GHz。本文算法和SHAMIR 算法的處理耗時(shí)和還原耗時(shí)數(shù)據(jù)如表2 所示。實(shí)驗(yàn)數(shù)據(jù)表明，無論加密或者恢復(fù)，本文算法處理效率都明顯優(yōu)于SHAMIR 秘密共享算法。相較于SHAMIR 算法最后生成的影子秘密體積10 MB，本文算法所儲存的影子秘密體積更大，為30 MB，因此，本文算法對于運(yùn)行內(nèi)存和存儲內(nèi)存的要求較SHAMIR 算法更高。

表2 2 種算法的耗時(shí)對比Table 2 Comparison of time consuming of two algorithms ms

通過以下3 個(gè)方面對算法進(jìn)行評估：1）是否能實(shí)現(xiàn)任意份額的（k，n）秘密共享；2）高效性；3）算法實(shí)現(xiàn)的難易程度。如果一個(gè)算法能夠?qū)崿F(xiàn)任意份額的（k，n）秘密共享，則稱該算法是通用的；如果一個(gè)算法的實(shí)現(xiàn)原理易于理解，生產(chǎn)中易于實(shí)現(xiàn)和維護(hù)，則認(rèn)為該算法是易于實(shí)現(xiàn)的。

將本文算法與SHAMIR 算法和MATSUO 算法［4］進(jìn)行對比，如表3 所示。由于都實(shí)現(xiàn)了任意份額的秘密共享，因此這3 種算法都是通用的。由于SHAMIR 算法涉及大量多項(xiàng)式計(jì)算，因此整體較為復(fù)雜，處理速度較慢，且難以實(shí)現(xiàn)。MATSUO 算法亦是基于異或運(yùn)算構(gòu)建，數(shù)據(jù)處理速度較快，但是當(dāng)k和n的值改變時(shí)，其算法的實(shí)現(xiàn)原理也有較大改變，因此，MATSUO 算法整體上是難以實(shí)現(xiàn)的，并且該算法在部分影子秘密的信息泄露時(shí)，雖然不會(huì)導(dǎo)致原秘密信息整體泄露，但可能會(huì)導(dǎo)致部分秘密信息泄露。而本文算法不存在此類安全隱患，其不僅可實(shí)現(xiàn)任意（k，n）秘密共享算法，而是更易于實(shí)現(xiàn)和高效的。

表3 3 種算法的評估結(jié)果Table 3 Evaluation results of three algorithms

5 結(jié)束語

本文提出一種基于異或運(yùn)算的秘密共享算法。通過連續(xù)的異或運(yùn)算生成算法所需的所有線索，并通過排列組合將這些線索進(jìn)行合理分組。該算法不僅能夠?qū)崿F(xiàn)任意份額的秘密共享，而且還具有極快的運(yùn)算速度。與SHAMIR 算法相比，其對同一秘密信息分別多次加密解密的平均耗時(shí)大幅減少。但本文算法存在影子秘密體積過大的問題，單個(gè)影子秘密與原秘密的體積比值大于1。而在實(shí)際應(yīng)用中，對運(yùn)行算法的機(jī)器運(yùn)行內(nèi)存和對存儲影子秘密的機(jī)器的存儲空間要求較高。下一步將尋找更理想的將秘密分散為線索的方法，通過減小每個(gè)線索體積的方式縮小影子秘密的體積。