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

環簽名算法種類很多，大多數算法設計基于雙線性對或大素數難分解，在安全性和運算速度方面有待提高。與基于橢圓曲線離散對數相比，雙線性對的優勢并不明顯，因為它無法運用一樣長度的密鑰提供同樣的安全性能。為了能夠提升方案的安全性以及能夠保證簽名者身份的完全匿名性，基于SM2商用密碼算法設計了一個新的環簽名方案。利用單向函數設計簽名算法，并對方案的安全性進行了嚴格證明，保證了新方案的正確性、安全性與隱匿性。

0 引　言

隱私保護是區塊鏈技術發展過程中用戶最關心的問題之一，也是去中心化分布式云存儲項目（Decentralized Distributed Cloud Storage Project，PPIO）研究的重點。區塊鏈涉及隱私保護的算法很多。大多數隱私算法都是基于密碼學。密碼學是區塊鏈底層技術的核心，應用廣泛。

首先，區塊鏈是一種按照時間順序將數據區塊相連構成的一種鏈式數據結構，需密碼學技術確保不可篡改和不可偽造的分布式賬本，構成一種去中心化的分布式結構網絡，以完成點對點的信息分享和互換。區塊鏈還有一個最重要的特點是匿名性，在交易層完成對所有用戶的隱私保護。實現區塊鏈匿名性的重要技術就是環簽名，能夠實現對數據的認證，是區塊鏈必不可少的核心技術之一，能夠有效保護區塊鏈中的用戶隱私數據。

隨著區塊鏈技術的日趨成熟，環簽名算法類型也很多。環簽名概念在2001年被Rivest等提出，因為某個參數使得簽名結果成“環形”而得名，實現了不泄露簽名者的身份而能夠代表一群成員而簽名。

隨后，許多學者在此基礎上不斷探索專研，構造了許多類型的環簽名方案。Bresson等提出了門限環簽名，即環中簽名者達到所設置的閾值時，就能驗證方案的正確性，使用了公平拆分的方法，證明是安全可行的。此方案針對人數少時比較高效，對于人數多時效率不高。Toshiyuki等對環中簽名者較多的情境提出了更加高效的門限環簽名方案。2015年，Asaar等人在RSA的基礎上構造了一個基于身份的代理環簽名方案；Chung等由雙線性對性質，寫出了基于身份認證的環簽名方案，但效率較低；Shim對基于身份的環簽名方案改進，提升了效率；張偉哲等根據ECC設計了隱匿身份的環簽名方案。

以上方案都是根據密碼學的難解問題設計的。直到2017年，Melchor等基于編碼理論設計了效率更高的門限環簽名方案，Zhang等基于MQ問題的抗量子攻擊設計了更先進的門限環簽名方案。研究者們提出了這些不同形式和不同特性的環簽名算法，但沒有基于國密SM2密碼算法的環簽名。本方案設計了基于SM2數字簽名算法的環簽名方案，保證了簽名的完整性、真實性、不可偽造性和無條件匿名性。

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

1 基礎知識

1.1　SM2公鑰密碼算法

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

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

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

（3）只有無重復因子時，才能基于橢圓曲線定義群，所以要求；

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

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

1.2　有限域上的橢圓曲線

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

式中，且。假設點滿足方程，則點為點P  的對稱點，稱為負點，即是。橢圓曲線上的點構成的集合中只有一種運算——加法（常數與點的乘法可以看做多個加法）。2個點可以進行加法運算得到第3個點，這里的加法不是簡單的平面坐標系橫縱坐標的相加，這樣相加的結果得到的坐標很有可能不在曲線上。假設橢圓曲線上點，且，直線過點與橢圓曲線交于點，E 關于x 軸對稱的點為且。橢圓曲線上的點與無窮遠點0 共同組成素數階為q 的加法循環群：

對應的，定義在上的倍點運算為：

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

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

定義1　假定一個函數是，則對于任何的會有，對于任何，能夠使，則此函數稱為可忽略函數。

定義2　（橢圓曲線離散對數問題）假設G 是橢圓曲線的生成元，，對于Y、G，求滿足方程的唯一整數x ，在限定時間內多項式算法A解決橢圓曲線離散對數問題（Elliptic Curve Discrete Logarithm Problem，ECDLP）問題的概率為：

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

定義3　（橢圓曲線離散對數假設）對于所有限定時間內多項式算法A和某些忽略函數，會有，因此概率為是可以忽略的。

1.4　SM3密碼雜湊算法

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

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

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

2.1　初始化階段

基于SM2簽名算法的環簽名方案的生成，首先每個環成員選定一條滿足安全要求的橢圓曲線（256位），l  是選定的安全參數，q  為大素數且是模的運算，是由整數組成的整數集合，是橢圓曲線加法群的倍點運算即元素G的k倍，N是橢圓曲線基點G的階次。為SM3密碼雜湊函數的哈希算法，輸入為任意長度的比特串，輸出為固定長度的密碼雜湊函數。通過隨機數發生器產生隨機數、環成員的公鑰集合為。其中，第s個用戶為匿名的簽名者，參與簽名的n個環成員的公鑰組成一個公鑰集合。環成員選擇隨機數，簽名者的成員可辨別標識身份組成的集合，然后計算：

（1）簽名者的私鑰；

（2）簽名者的公鑰；

（3）計算是否為0，若為0，則重新選擇；

（4）輸出簽名者的公私鑰對。

2.2　生成消息m的環簽名

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

式中，為整數組成的整數集合，q為大素數，H為SM3密碼雜湊函數，G為循環群的一個生成元，循環群是階為素數q的加法循環群。

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

對于每個，根據SM2算法生成部分環簽名。對于消息m，首先簽名者s置，計算，并將的數據類型轉換成整數。

步驟3：計算橢圓曲線上的點,并將的數據類型也轉換為整數。

步驟4：計算，若或則重新選擇，這就是的生成過程。

步驟5：依次計算、，其中記為用戶的公鑰。

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

步驟7：生成消息m的環簽名。

2.3　對簽名進行合法性驗證

驗證者收到消息m及其環簽名后，采用以下步驟進行環簽名驗證：

步驟1：置，計算，并將的數據類型轉換成整數；

步驟2：檢驗是否成立，若不成立則驗證不通過；

步驟3：對從1增至N，檢驗，若不成立則驗證不通過；

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

步驟5：檢驗是否成立，若成立則驗證通過；否則，驗證不通過。

3 安全性分析

3.1　正確性

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

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

3.2　匿名性

除非簽名者自己暴露身份信息，否則從任意第三方檢驗都無法確定真正的簽名者。在生成簽名算法中，對于簽名者，不包括簽名者自己，生成環簽名。簽名的（6）中，簽名者使用自己的私鑰，利用陷門函數生成簽名。后來生成的環簽名中包括，此時，因此從生成的環簽名無法判斷具體是誰產生的簽名。對于攻擊者而言，在無法確定是不是正確之前，即便所有的簽名者暴露自己所有的信息，也不能確定消息簽的正確簽名者身份，因此方案符合無條件匿名性。

3.3　不可偽造性

3.3.1　簽名詢問

隨機預言模型下，假設敵人可以與最多位的非簽名者合作，通過次的散列詢問，可以偽造出簽名的幾率為。對于的陷門函數，已知某個輸出點，可構造出偽造的算法以概率計算出輸入，使得。

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

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

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

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

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

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

挑戰階段：假設敵手可以由不可忽略概率偽造消息的環簽名，其中，且在簽名詢問階段并沒有出現。如果，挑戰者輸出，否則就輸出“錯誤”。

當且僅當和時，由于對手進行了次的散列詢問，因此挑戰者能成功輸出的概率為，即所設計的環簽名方案滿足強不可偽造性。

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

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

3.3.3　私鑰的不可偽造

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

4 結　語

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