基于SM2密碼算法的環簽名方案的研究與設計*

韓寶杰，李子臣

（北京印刷學院，北京 102600）

0 引 言

隱私保護是區塊鏈技術發展過程中用戶最關心的問題之一，也是去中心化分布式云存儲項目（Decentralized Distributed Cloud Storage Project，PPIO）研究的重點。區塊鏈涉及隱私保護的算法很多。大多數隱私算法都是基于密碼學。密碼學是區塊鏈底層技術的核心，應用廣泛。首先，區塊鏈是一種按照時間順序將數據區塊相連構成的一種鏈式數據結構，需密碼學技術確保不可篡改和不可偽造的分布式賬本，構成一種去中心化的分布式結構網絡，以完成點對點的信息分享和互換。區塊鏈還有一個最重要的特點是匿名性，在交易層完成對所有用戶的隱私保護。實現區塊鏈匿名性的重要技術就是環簽名，能夠實現對數據的認證，是區塊鏈必不可少的核心技術之一，能夠有效保護區塊鏈中的用戶隱私數據[1]。隨著區塊鏈技術的日趨成熟，環簽名算法類型也很多。環簽名概念在2001年被Rivest等[2]提出，因為某個參數使得簽名結果成“環形”而得名，實現了不泄露簽名者的身份而能夠代表一群成員而簽名。隨后，許多學者在此基礎上不斷探索專研，構造了許多類型的環簽名方案。Bresson等[3]提出了門限環簽名，即環中簽名者達到所設置的閾值時，就能驗證方案的正確性，使用了公平拆分的方法，證明是安全可行的。此方案針對人數少時比較高效，對于人數多時效率不高。Toshiyuki等[4]對環中簽名者較多的情境提出了更加高效的門限環簽名方案。2015年，Asaar等人[5]在RSA的基礎上構造了一個基于身份的代理環簽名方案；Chung等[6]由雙線性對性質，寫出了基于身份認證的環簽名方案，但效率較低；Shim[7]對基于身份的環簽名方案改進，提升了效率；張偉哲等[8]根據ECC設計了隱匿身份的環簽名方案。以上方案都是根據密碼學的難解問題設計的。直到2017年，Melchor等[9]基于編碼理論設計了效率更高的門限環簽名方案，Zhang等[10]基于MQ問題的抗量子攻擊設計了更先進的門限環簽名方案。研究者們提出了這些不同形式和不同特性的環簽名算法，但沒有基于國密SM2密碼算法的環簽名。本方案設計了基于SM2數字簽名算法的環簽名方案，保證了簽名的完整性、真實性、不可偽造性和無條件匿名性。

本文根據文獻[2]中原始基于RSA的環簽名方案，設計基于SM2算法新的改進方案并在隨機預言模型中可證安全。該方案具有以下幾個優點：（1）與基于陷門單向函數相比，在同等長度的密鑰下具有較好的安全性；（2）加強了對簽名者的保護，實現了簽名者的完全匿名性；（3）與基于單向陷門函數的方案相比，此方案的不可偽造性更強。

1 基礎知識

1.1 SM2公鑰密碼算法

SM2算法是一種橢圓曲線公鑰密碼算法。橢圓曲線是基于素域的。要想確保設計方案的安全性，需挑選可以抵御各種攻擊的橢圓曲線，因此涉及選取安全橢圓曲線的問題。用于建立密碼體制的橢圓曲線的主要參數有q、a、b、G、n和h。其中：q為有限域F(q)中元素的數目；a、b為方程系數，在F(q)中取值；G為基點（生成元）；n為G點的階；N除以n的結果h為橢圓曲線上點的個數，被稱為余因子。如需所設計的密碼體系具有較好的安全性能，則選擇的參數要達到以下條件[11]：

（1）q的取值越大越安全，但會減慢計算速度，160位尚可滿足安全需求；

（2）對于選定的有限域F(q)，選取大素數n（n＞2160）時要盡可能大，以預防Pohlig-Hellman算法的攻擊；

（3）只有x3+ax+b無重復因子時，才能基于橢圓曲線E(Fq)定義群，所以要求4a3+27b2≠0(mod p)；

（4）要確保p的階n足夠大，以防止小步大步攻擊，一般h≤4；

（5）要防止MOV規約法，就不能選取超奇異或者異常橢圓曲線等特殊的曲線。

1.2 有限域上的橢圓曲線

橢圓曲線密碼學（Elliptic Curve Cryptography，ECC）是一種建立公開密鑰加密的算法，也就是非對稱加密[12]。類似的還有RSA、ElGamal算法等。ECC被公認在給定密鑰長度下最安全的加密算法。比特幣中的公私鑰生成和簽名算法ECDSA都是基于ECC的。設存在大素數q，限域Fq上的橢圓曲線是所有點構成的合集。仿射坐標中，橢圓曲線中的點P（不是無窮遠點）坐標為P=-Q，此中的(xp,yp)是符合特定方程的域元素，稱為點P的x坐標和y坐標。Fq為基域，q為模數，在此基域上存在橢圓曲線E(Fq)的方程為：

式中：a,b∈Fq，且Δ=(4a3+27b2)(mod q)≠0。假設點(xp,yp)滿足E(Fq)方程，則點Q(xQ,-yQ)為點P的對稱點，稱為負點，即是P=-Q。橢圓曲線上的點構成的集合中只有一種運算——加法（常數與點的乘法可以看做多個加法）。2個點可以進行加法運算得到第3個點，這里的加法不是簡單的平面坐標系橫縱坐標的相加，這樣相加的結果得到的坐標很有可能不在曲線上。假設橢圓曲線E(Fq)上點P(x1,y1)，Q(x2,y2)且P≠Q，直線l過點P、Q與橢圓曲線交于點E′=(x3,-y3)，E′關于x軸對稱的點為E=(x3,y3)且E=P+Q。橢圓曲線E(Fq)上的點與無窮遠點O共同組成素數階為q的加法循環群：

對應的，定義在ε(k)≤1/kc上的倍點運算為：

1.3 基于SM2的困難性問題假設

不同類型的困難性問題假設定義是從離散對數問題[12]中獲得的，可在素數階為q的群G中定義。

定義1 假定一個函數是ε(k)，則對于任何的c＞0會有k0，對于任何k≥k0，能夠使ε(k)≤1/kc，則此函數ε(k)稱為可忽略函數。

定義2 （橢圓曲線離散對數問題）假設G是橢圓曲線E(Fq)的生成元，Y∈E(Fq)，對于Y和G，求滿足方程[x]G=Y 0≤x≤ord(G)-1的唯一整數x，在限定時間內多項式算法A解決橢圓曲線離散對數問題（Elliptic Curve Discrete Logarithm Problem，ECDLP）問題的概率為

ECDLP被公認要比整數分解問題和離散對數問題難解得多，因此在同等安全性下，ECC僅需要較短的密鑰長度。

1.4 SM3密碼雜湊算法

對消息m的哈希算法使用SM3密碼雜湊算法[13]，對于長度klen的消息，SM3算法經過填充和迭代壓縮，生成長度為256位的雜湊值。SM3密碼雜湊算法基于MD結構，雜湊函數H可以將一個任意有限長度的消息m壓縮到某一固定長度為n的雜湊h，即H(m)=h。SM3雜湊算法是對長度為n（l＜264）的消息m進行填充和迭代壓縮生成雜湊值，雜湊值的長度為256 bit。

2 基于SM2算法的環簽名方案

假設Alice希望用環簽名為消息m簽名，m的長度為klen，環中有n個成員A1、A2…An，其中簽名者Alice是As。對于s的某個值1≤s≤n，其中所有環成員使用SM2作為他們各自的簽名方案。基于SM2算法的環簽名方案主要由系統建立、密鑰生成、簽名與驗證3個部分組成。

2.1 初始化階段

基于SM2簽名算法的環簽名方案的生成，首先每個環成員Ai選定一條滿足安全要求的橢圓曲線（256位），l是選定的安全參數，q為大素數且q＞2256，mod q是模q的運算，Zq*是由整數1,2,…,q-1組成的整數集合，[k]G是橢圓曲線加法群的倍點運算即元素G的k倍，N是橢圓曲線基點G的階次。H(·)為SM3密碼雜湊函數的哈希算法，輸入為任意長度的比特串{0,1}*，輸出為固定長度的密碼雜湊函數。通過隨機數發生器產生隨機數k∈[1,n-1]、環成員Ai的公鑰集合為{P1,P2,…,Pr,其中r≠s}。其中，第s個用戶為匿名的簽名者，參與簽名的n個環成員的公鑰組成一個公鑰集合P={P1,P2,…,Pn}。環成員選擇隨機數k∈Zq*，簽名者的成員可辨別標識身份組成的集合Z={z1,z2,…,zn}，然后計算：

（1）簽名者的私鑰di∈[1,n-2]；

（2）簽名者As的公鑰Pi=[di]·G；

（3）計算Pimod q是否為0，若為0，則重新選擇ki=Zq*；

（4）輸出簽名者的公私鑰對(Pi,di)。

2.2 生成消息m的環簽名

步驟1：隨機產生ks=Zq*，根據環內用戶公鑰集合P待簽名消息m，計算：

式中：Zq*為整數1,2,…,q-1組成的整數集合；q為大素數；H為SM3密碼雜湊函數；G為循環群的一個生成元；循環群是階為素數q的加法循環群。

步驟2：根據環內用戶的公鑰集合P和待簽名消息m計算ci。

步驟3：計算橢圓曲線上的點(xi,yi)=[ki]G,并將xi的數據類型也轉換為整數。

步驟4：計算ri=(e+xi)mod N，若ri=0或ri+ki=N則重新選擇ki，這就是ri的生成過程。

步 驟 5： 依 次 計 算zi=[ri+ci]Pi+[ri]G、Ci+1=H(P,m,Zi)，其中記C1=Cn+1，Pi為用戶i的公鑰。

步驟6：根據簽名者私鑰ds，計算：

步驟7：生成消息m的環簽名σ=(c1,r1,…,rn)。

2.3 對簽名進行合法性驗證

驗證者收到消息 m′及其環簽名 (c1′,r1′,…,rn′)后，采用以下步驟進行環簽名驗證：

步驟2：檢驗c1′∈zq*是否成立，若不成立則驗證不通過；

步驟3：對i從1增至n，檢驗r′∈zq*，若不成立則驗證不通過；

步驟4：對i從1增至n，依次計算：

步驟5：檢驗C1′=C′n+1是否成立，若成立則驗證通過；否則，驗證不通過。

3 安全性分析

3.1 正確性

生成簽名和驗證簽名階段用到了輪函數算法，有：

因為接收者收到的簽名中含有c1，代入即可驗證輪函數的正確性。

3.2 匿名性

除非簽名者自己暴露身份信息，否則從任意第三方檢驗都無法確定真正的簽名者。在生成簽名算法中，對于簽名者i=s+1,…,n,1,…,s-1，不包括簽名者自己，生成環簽名ri∈zq*。簽名的式（6）中，簽名者使用自己的私鑰ds，利用陷門函數生成簽名rs。后來生成的環簽名中包括(r1,…,rn)，此時i=1,2,…,s,s+1,s+2,…,n，因此從生成的環簽名σ無法判斷具體是誰產生的簽名。對于攻擊者而言，在無法確定C1′=C′n+1是不是正確之前，即便所有的簽名者暴露自己所有的信息，也不能確定消息簽名的正確簽名者身份，因此方案符合無條件匿名性。

3.3 不可偽造性

3.3.1 簽名詢問

證明：此方案需在自適應選擇消息的攻擊下證明環簽名流程的不可偽造性（E xistential Unforgeability against Chosen-Message Attacks，EUCMA）。游戲所需的成員為敵手和挑戰者。假設敵手在詢問后可以偽造環簽名，由此挑戰者能夠設計相應算法根據已知陷門單向函數的輸出(xi,yi)得出相應的輸入，對應的步驟如下。

挑戰者可以為所有的簽名者生成公私鑰對，并把產生的所有用戶的公鑰P1,P2,…,Pn發給敵手。

對手進行如下自適應的詢問階段。

散列詢問：挑戰者接收到由對手生成的橢圓曲線坐標點，然后隨機選擇l位的隨機數v，并設定v的散列值為H(v)，返回給對手。

私鑰詢問：挑戰者接收到敵手產生的用戶公鑰，并把相對應的私鑰返回給敵手，但是敵手最多只可以詢問(n-1)個用戶的私鑰。

簽名詢問：挑戰者繼續收集敵手產生的用戶公鑰，將隨機產生的散列值代入環簽名的方案里產生簽名σ，并返還給敵手。

3.3.2 橢圓曲線離散對數問題的困難性

本文是根據SM2的簽名算法上進行改進的環簽名方案，攻擊者可由簽名者的公鑰和系統參數計算出簽名者私鑰的困難性相當于解決橢圓曲線離散對數問題的困難性，此概率能夠忽略不記。假設攻擊者A可以以不可忽略的概率成功偽造一個有效簽名，則有算法B可以以不能忽略的概率解出ECDLP。但是，ECDLP是公認的困難性問題，因此該方案在隨機預測模型的適應性選擇信息與身份攻擊中滿足不可偽造性。

3.3.3 私鑰的不可偽造

由于攻擊者無法知道簽名者的私鑰，若想成功偽造簽名者簽名的概率是忽略不計的。

4 結 語

本文基于SM2橢圓曲線簽名算法的基礎上構造了一個環簽名方案。與傳統的基于雙線性對的環簽名相比較，它同時滿足簽名的強不可偽造性和簽名者的匿名性，提高了簽名效率。本方案在安全性方面和完全保護簽名者身份的匿名性方面優勢明顯。雖然根據原始環簽名拓展出新環簽名算法很多，如基于門限、基于身份認證等，但是基于SM系列國密的環簽名算法幾乎沒有。所以，本文的創新點突出，是對Rivest、Shamir和Tauman等人提出的最原始環簽名方案的拓展研究。