一種基于異或運算的(k,n)門限秘密共享算法

夏 高，何成萬

（武漢工程大學計算機科學與工程學院，武漢 430205）

0 概述

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

1 相關工作

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

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

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

作為一種基礎的加密協議，秘密共享協議可以應用于身份認證。一種較直接的思路是，對某個密鑰S進行（k，n）秘密共享分散，用戶持有其中m（m

2 本文算法

2.1 異或運算的性質

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

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

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

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

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

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

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

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

1）對于秘密S，將其轉化為對應的二進制序列G。

2）對于G，隨機生成1個等長的二進制序列，記為K1。

3）對G和K1進行異或運算，記運算結果為G1，GXORK1=G1。

4）隨機生成1 個與G1等長的二進制序列K2，G1XORK2=G2。

5）隨機生成1 個與G2等長的二進制序列K3，G2XORK3=G3。

6）隨機生成1 個與G3等長的二進制序列K4，G3XORK4=G4。

7）隨機生成1 個與G4等長的二進制序列K5，G4XORK5=G5。

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

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

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

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

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

表1 分配結果Table 1 Distribution result

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

圖1 基于異或運算的恢復過程Fig.1 Restore process based on XOR operation

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

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

在全部異或運算完成后，只保存K1、K2、K3、K4、K5、G5這6 條線索，其余信息均不保存。對于線索的分組，根據前述規則，某一個線索只能存入某2 組中各1 次，且每次影子秘密的組合不與之前任意1 次組合重復。記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組。

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

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

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

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

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

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

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

3 安全性證明

對本文算法進行安全建模，如圖5 所示，安全目標如下：

圖5 安全模型Fig.5 Safety model

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

2）原秘密信息可被長期安全存儲。一定時間后已經泄露的少量信息將失去價值。

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

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

4 實驗與結果分析

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

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

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

通過以下3 個方面對算法進行評估：1）是否能實現任意份額的（k，n）秘密共享；2）高效性；3）算法實現的難易程度。如果一個算法能夠實現任意份額的（k，n）秘密共享，則稱該算法是通用的；如果一個算法的實現原理易于理解，生產中易于實現和維護，則認為該算法是易于實現的。

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

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

5 結束語

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