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