基于SM2與RSA簽密的秘密共享方案*

韓寶杰，李子臣

（北京印刷學院 信息工程學院，北京 102600）

0 引言

對于某些秘密信息諸如國家機密檔案、公司機密文件等重要信息，都需要將秘密拆分由多人掌管，并且需要多人同時在場才能恢復秘密信息，而秘密分享技術已經為此類問題提供了解決方案。秘密分享是現代密碼學的一個重要研究方向，1979年由Shamir與Blakley提出[1]，主旨是將秘密信息分割成若干分享份，將其發送給相應參與者，僅當有足夠的參與者在場時，才能重構出秘密數據。此后，很多學者在秘密分享方案的拓展中做了大量工作。Asmuth與Bloom[2]于1983年提出了一種新的基于中國剩余定理的秘密分享方案，相較于Shamir的分享方案更加高效，運算也更加簡潔。隨后出現了多秘密分享方案[3-6]，可以直接分割多個秘密，增加了秘密共享的容量與效率。

秘密分享技術在不斷創新，拓展研究新的發展方向。2004年，文獻[7]有將秘密分享與博弈論相結合，提出了理性的秘密分享方案，進而提供了一個新的研究熱點[8-9]。Laih[10]等人提出了可以動態改變參與秘密重構人數的秘密共享方案，可以根據秘密的重要性更改恢復門限。

但是，傳統的秘密分享方案存在著不可忽略的安全缺陷。例如，秘密分享份屬于機密信息，為了保證安全，需要選取安全信道進行傳輸，如此增加了信息傳輸的成本。再如，存在惡意用戶使用假的分享份參與秘密重構，致使合法用戶獲得錯誤的重構信息。對于上述問題，已有學者在秘密分享與驗證技術的結合上進行研究，并取得了相關成果[11-14]。Rabin T[15]提出了一個可驗證秘密分享方案，但該方案需要所有參與成員之間都具有秘密通信的能力，提高了通信成本。Harn L[16]提出強力可驗證分享方案，保證了所有的分享份始終不變，防止參與者收集分享份重新定義秘密。

本文方案結合中國剩余定理（Chinese Remainder Theorem，CRT）與橢圓曲線問題構造可驗證的秘密共享方案，其中中國剩余定理提供了拆分秘密的基礎工具，而SM2與RSA簽密體制用來構建簽名與加密，為分發者與用戶創建公私鑰對，提供安全的信息傳輸方案，防止攻擊者竊取分享文件。

該方案允許用戶在安全環境差的情況下進行傳輸，節省了信息傳輸的成本，而且也保證只有合法用戶能夠獲得分享份，且可以驗證分享份的正確性與來源。

1 基礎知識

1.1 (k,n)門限方案的引入

1.1.1 定 義

設P={P1,P2,…,Pn}是一個由n個參與人組成的集合，P的子集構成集合τ。如果τ恰好可以重構出參與者集合組成的秘密c，則τ可稱為接入結構，P的授權子集就是τ中的元素。P的授權子集就是τ中的元素。

接入結構τ是單調性質的，即若B∈τ且B?C?P，則必有C∈τ。

(k,n)門限方案[17]是接入結構τ={A|A?P,|A|≥k}上的秘密共享方案，通用訪問結構的秘密共享或廣義秘密共享也是一般接入結構的秘密共享，具有很大的實用性。

1.1.2 秘密共享方案的數學模型

設秘密發放者為A，n個參與人記為集合P={P1,P2,…,Pn}，PT是授權子集，共享秘密記為c，秘密可分為集合C′={C1,C2,…,Cn}。

秘密分發算法：A通過某種算法計算出C′={C1,C2,…,Cn}，后由安全信道把秘密份額Ci分發給不同的參與人Pi。

秘密重構算法：授權子集PT中的參與人將自己有的秘密份Ci(Pi∈PT)組合，可經某種算法重構原始秘密。

在這種情況下，一個秘密共享方案稱作一個(k,n)門限秘密共享方案。

1.2 中國剩余定理

中國剩余定理[18]是數論中最有用的工具之一。如果已知某個數是關于一些兩兩互素的數的同類，就可以重構這個數。它的這個特性為秘密分享方案提供了基礎理論支持。

設m1,m2,…,mn是兩兩互素的正整數，有則方程組：

對模M有唯一解。

其中ui滿足條件

本文采用Asmuth-Bloom提出的基于CRT的秘密分享方案作為秘密分發步驟的解決辦法，計算上會比基于拉格朗日插值法的shamir分享方案速度更快，且也具備門限功能。

1.3 RSA加密算法

（1）隨機選擇兩個不相等的質數p和q；

（2）計算p和n的乘積n（將n轉換為二進制形式，也就是密鑰的長度，實際應用中一般選擇1 024位、2 048位）；

（3）計算出n的歐拉函數φ(n)；

（4）隨機選擇一個整數e，其中φ(n)＞e＞1，且e與φ(n)互質（實際應用中e一般選為65 537）；

（5）計算e對于φ(n)的模反元素d；

（6）將n和e封裝成公鑰，n和d封裝成私鑰。

假設發送方向接收方發送信息C，C未加密，稱之為明文。發送方從接收方獲得的公鑰為(n,e)，加密公式為：

其中，C必須是整數，C必須比n小。

C、e、n已知，利用公式計算出C′即加密后的信息，稱之為密文。

1.4 SM2數字簽名方案

SM2算法是公鑰密碼，屬于非對稱算法體系，是橢圓曲線加密（Elliptic Curve Encryption，ECC）算法的一種[19]。

數字簽名及流程如下：設待簽名的文件為C，ZA為用戶A的可辯別標識、部分橢圓曲線的系統參數以及用戶A公鑰的雜湊值，h是余因子。要獲得秘密文件C的數字簽名(r,s)，分發者A要實現以下運算：

（3）隨機數發生器要產生隨機數k∈[1,n-1]；

（4）需計算橢圓曲線上的點(x1,y1)=[k]G，將x1的數據類型轉換為整數；

（5）計算r=(e+x1)modn，若r=0或r+k=0，則返回（3）；

（6）計算s=((1+dA)-1·(k-r·dA))modn)，若s=0，則返回（3）；

（7）將r、s的數據類型轉換為字節串，消息C的簽名為(r,s)。

1.5 SM2與RSA簽密方案

在密碼體制中，加密用來保證信息數據的機密性，數字簽名是接收者用來確保消息的認證、完整性和不可否認性。如果分享者想同時獲得這些性質，傳統的方法是先對消息進行加密再進行簽名運算，兩者獨立存在并分別被研究。這種方法在通信成本和計算量上是兩者的代價之和，效率不高。

1997年，Zheng[20]提出了一種新的密碼原語，能夠同時實現以上的安全性質，這就是數字簽密（Digital Signcryption）。與傳統的“先簽名后加密”相比，它的優點包括：（1）簡化了需要同時達到保密和認證要求的密碼協議的設計；（2）簽密算法降低了通信成本和計算量，效率高；（3）簽密可以并行計算一些復雜的操作；（4）簽密方案的水平設計可以更安全。

所以，本方案采用SM2與RSA結合對分享份進行簽密，提高了先簽名后加密的效率。

2 可驗證分享方案

2.1 方案描述

為了將原始秘密拆分并提供門限重構功能，選用基于中國剩余定理的門限分享方案，再使用SM2與RSA簽密技術，保證分享份的安全性與正確性。接收者可以通過收集驗證過的分享份進行秘密重構，獲取重構信息。假設發送方是A，接收方是集合B={B1,B2,…,Bn}，原始秘密文件為C，任意(Bi)k個接收者擁有(Ci)k份分享，通過k個接收者中任意一位Bj解密和驗證后，才能還原出秘密信息C。

本方案流程見圖1和圖2。

原始秘密C經拆分生成n份分享文件，分享者A再依次將文件進行簽密生成簽密文件，然后發送給接收者。實際應用中，為了保護數據可以將數據加密。可以利用秘密重構的方案，即將原始文件C分成n份C1,C2,…,Cn，滿足任意k或多于k份Ci可以恢復出C，任意k-1或少于k-1份Ci信息不能準確計算出C。這種方式不但對分享份進行了加密，而且大大增加了原始文件的安全性。接收者們收集任意k份或多于k份的分享份，使用中國剩余定理可還原出初始文件。簽密文件可以利用自己的私鑰進行解簽密，即可獲得分享份的實際值。任意少于k份分享，將無法還原出正確的重構文件。

圖1 秘密分享流程

圖2 重構秘密流程

方案具體涉及6個階段，分別為系統初始化階段、分享份生成階段、密鑰生成階段、秘密分發階段、分享份的解密與驗證以及分享份重構階段。

2.2 方案步驟

2.2.1 簽密算法初始化

設分發者A選取SM2簽名所需的一條滿足安全要求的橢圓曲線以及RSA加密所需的兩個不同的大素數p和q。

2.2.2 分享份生成階段

分發者A選取m1,m2,…,mn和Q，C為秘密。為增加秘密C的復雜性，要求Q≥C，m1,m2,…,mn嚴格遞增，且滿足：

分享份的生成：

隨機選取整數t，滿足計算Z=C+tQ，對Z與mi做模運算，即：

得到C1,C2,…,Cn，將Ci作為分享份。

2.2.3 密鑰生成及簽密方案

（1）SM2數字簽名方案及密鑰生成。設lk是安全參數，橢圓曲線的E(Fq)的方程的兩個元素a,b∈Fq；E(Fq)上的基點G=(xG,yG)(G≠0)，其中xG和yG是Fq中的兩個元素；G點的階是n1。發送者的公鑰pks=PA=[dA]G=(xG,yG)，私鑰sks=dA。此外，公開參數params1=(a,b,n1,G,pks,h,ZA)。

（2）SA加密及密鑰生成算法[21]。安全參數lk，定義大素數p、q，且n2=p·q，φ(n)=(p-1)(q-1)。隨機選取e，其中1＜e＜φ(n)，且gcd(e,φ(n))=1，計算de=1mod(φ(n))，公 鑰pks=(e,n)，私 鑰sks=d。H1(·)、H2(·)是由密碼雜湊函數Hv(·)的密碼函數；l(·)表示參數的長度，單位是位；公開參數params2=(n2,e)。

2.2.4 簽密算法

發送者A獲得接收者Bi的公鑰證書后，對分享份Ci進行以下計算（這里是n份分享中的任意一個Ci分享的簽密過程）。

（1）生成隨機數ki1∈[1,n1]，ki2∈[1,n2]；

（3）計算ai2=ci⊕H1(ki1,ZA)和w=H2(ki1,ci)；

（4）計算橢圓曲線上的點(x1,y1)=ki2G；

（5）計算ri=(x1+w)modn1和si=(1+dA)-1(ki2-rdA)modn1，若ri=0，ri+ki1=0或者si=0，則返回（1），輸出密文Ci′=(ai1,ai2,ri,si)。

2.3 分享份的解密與重構

2.3.1 解簽密算法

接收者C獲得發送者A的公鑰以及簽密的文件Ci′=(ai1,ai2,ri,si)后需進行計算。

（1）根據接收者的私鑰d計算：

（2）計算得出分享份Ci=H1(ki1,ZA)⊕ai2；

（3）計算w=H2(ki1,Ci)，并解出：

（4）計算(x1,y1)=[si]G+[v]PA

（5）驗證Ri=(x1+w)modn1是否等于ri，若相等則可得到分享份Ci，若不相等則解簽密失敗。

2.3.2 秘密重構階段

Bi位用戶可以利用自己的分享份額，合作完成秘密重構。在進行重構計算前，要求各用戶Bi使用分發者的公鑰PA進行驗證，驗證通過才可參與重構計算，否則拒絕參與重構。由解簽密算法計算出來的分享份Ci，Bj可通過收集到的任意k份分享，進行以下的重構操作。

可根據中國剩余定理由k份分享(Ci)k進行計算：

得到重組秘密C。

3 方案性能分析

3.1 方案的正確性

驗證橢圓曲線上的點(x1,y1)是否與公私鑰對應，需計算：

3.2 方案的機密性

在隨機預言模型下，如果存在一個IND-HCCCA2敵方F能夠在有限的時間t內以不可忽略的優勢ε贏得游戲，則說明有區分者S，可以在t′＜t+(qs+2qu)te的時間內，可以有的優勢攻破大整數分解問題，其中te是冪指數時間。證明：假如挑戰者為S，攻擊者是F′。

（1）初始階段。挑戰者生成分發者A的公私鑰對(pks,sks)，生成參與者的公私鑰對(pkr,skr)，s將pks和(pks,sks)發送給攻擊者，并將skr保密。

（2）階段1。F執行以下多項式有界次適應性詢問和最先進hash查詢，應答交付S。

H1詢問：如果是第i次查詢，隨機選取h1i∈{0,1}C，把(h1i,k1i,ZAi)保存在H1列表中，返回h1i。

H2詢問：隨機選取h2i∈{0,1}k+C，把(h2i,k1i,Ci)保存在H2列表中，返回h2i。

簽密查詢：遍歷H1和H2列表查詢(h2i,k1i,Ci)和(h1i,k1i,ZAi)，使得和ri=(x1i+h2i)modn1等式滿足，且滿足(x1,y1)=[si]G+[t]PA和Ri=(x1+h2i)modn1=ri則C為簽密的結果輸出，否則輸出錯誤。

挑戰階段：何時結束階段1的詢問進入挑戰階段取決于F。先由F給挑戰者S發送個一樣長的明文C0和C1，隨后S任意選擇一個數據γ∈(0,1)，計算mγ在分發者的私鑰sks和接收者的公鑰pks，進而計算簽密密文c*=Signcrypt(sks,pkr,mg)，并將c*傳給F。

階段2：F可運行階段1中的所有步驟，但不能執行接收者的私鑰查詢和解簽密查詢。

猜測階段：F產生一個比特γ′，若γ′=γ，則F取得了勝利。

S需在H1的列表h1i,k1i,ZAi中找到它滿足的這些計算：

且滿足：

假如這些式子都滿足，則證明F可以得到一個關于橢圓曲線的離散對數問題的實際解。

F的優勢為：

其中Pr[γ′=γ]表示γ′=γ的概率。

在H1詢問中有唯一一個(h1i,k1i,ZAi)與之相對，所以拒絕正確密文的概率為因此假如ε是不能略去，則ε′也是不能略去的。但是，這和大整數的難解問題是矛盾的。因此，在大整數問題的難解性下，以不可忽略的優勢攻擊此簽密方案的IND-SC-CCA2敵手是不存在的。由此證明此簽密方案是IND-SC-CCA2安全的。

3.3 方案的防偽造性

證明：假如有偽造者F′有不能略去的概率ε去攻擊SM2與RSA簽密方案的EUF-SC-CMA安全，會有挑戰者F通過F′來攻擊SM2的EUF-CMA安全性，偽造者F′與挑戰者S有以下這些互動。

初始階段。挑戰者輸出分發者的公私鑰對(pks,sks)和接收者的公私鑰對(pkr,skr)，S將pks和(pks,sks)傳給F′，并把skr保密。

攻擊階段。F′能夠運行簽密查詢，合理的應答則由S完成。查詢中，F′生成一個接收者的公鑰pkri及消息mi，S查詢消息mi得到(ri,si)。隨機選取k1i∈[1,n1-1]，計算：

返回ci=(c1i,c2i,r1,si)給S。

偽造階段。F′提供接收的一個合法密文ci=(c1i,c2i,r1,si)返回給S，S進行如下操作得到一個合法的簽名：

其中(ri,si)就是對ci簽名的合法偽造，且滿足：

可見，F′造出密文的優勢ε不能略去，S偽造合法的簽名也不能略去。但是，因為橢圓曲線的離散對數問題的難解條件，SM2簽名是EUF-CMA安全的，所以偽造者F′是不存在的。此方案是EUFSC-CMA安全的。

在秘密的恢復階段，攻擊者想要使用偽造的分享份參與信息重構，以破壞重構信息的正確性，需要先通過重構信息前的驗證，否則拒絕參與秘密重構。

3.4 方案的性能分析

從計算代價來看。對比先加密而后簽名的方案，如采用SM2簽名算法對消息摘要進行簽名，用SM2公鑰密碼體制對加密明文的對稱密鑰進行加密，這里共用到了6個橢圓曲線上的離散點的運算：1個用來產生簽名(x1,y1)=[k]G；3個用來加密a1=[k]G=(x1,y1)，s=[h]PB，[k]PB=(x2,y2)；2個用來解密s=[h]C1，[dB]C2=(x2,y2)。使用RSA加密簽名，加密需要1次指數運算，解密需要1次指數運算，簽名需要1次指數運算，驗證需要1次指數運算。

設計的SM2與RSA簽密方案，簽密只需要使用1次橢圓曲線上的離散點運算和1次指數運算，解簽密使用1次橢圓曲線上的離散點運算和1次指數運算，減少了通信量，提高了通信效率。

此外，該方案的安全性能安全分析已經證明，即具有較好的安全性。

4 結語

由于網絡的飛速發展，網絡安全問題倍受關注，越來越多的人選擇將機密信息進行加密，隨之而來的是密鑰管理問題。一般將密鑰簡單存儲在計算機中，若密鑰文檔失竊，則會直接威脅機密文檔安全。對于機密等級更高的文檔，查看與修改的權限也要加以限制，以保證其安全。

所提方案基于中國剩余定理，結合SM2與RSA簽密算法，構造了一種分享份可驗證的秘密分享方案，為密鑰的安全存儲與使用權限問題提供了解決方案，保證了分享份的安全來源，節省信道資源的同時保障了分享信息的安全，確保用戶能夠且只能獲得屬于自己的分享份。該方案能夠有效減少攻擊者竊取密鑰所造成的損失，也能夠防止攻擊者通過偽造的分享份破壞導致信息重構。該平臺可以被廣泛應用于實際環境，如政府重要人員的檔案信息密鑰管理、公司財務檔案密鑰管理等，需要在加密的基礎上進一步提升安全性能需求。因此，本平臺有著廣闊的應用場景。

本平臺具有5種功能，分別為密鑰生成、秘密分享、簽名加密、解密驗證與信息重構，可以對加密密鑰數據在合理的時間內進行以上操作，并且解決了密鑰權限與存儲的問題，對構建更加安全的數據系統提供了新思路。