基于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等人提出的最原始环签名方案的拓展研究。