基于SM2的无证书可截取签名方案
2019-09-23张大伟宋靖文孟吴同刘晓东
高 凡, 张大伟, 宋靖文, 孟吴同, 刘晓东
(1.北京交通大学 计算机与信息技术学院 北京 100044;2.山东大学 网络信息安全研究所 山东 济南 250000)
0 引言
在当今高度信息化的时代,数字签名得到了广泛的应用.然而标准数字签名[1-2]在某些情况下会给签名持有者造成一定约束,不能对已签名的数据进行合理的操作.Steinfeld等[3]于2001年最早提出了可截取签名(content extraction signature,CES)的概念,并给出了具体方案.与标准数字签名方案不同,可截取签名体制允许签名的持有者在不与原始签名者进行交互的情况下,根据自身需要,提取原消息中的部分内容,并为这部分内容计算一个可公开验证的签名,验证时使用的是原始签名者的公钥.可截取签名在某些领域有一定的应用场景.刘军龙等[4]于2006年提出了基于身份的可截取签名方案,但方案中采用双线性对运算,效率有待提升.Yin等[5]于2010年提出了一种不含可信第三方的基于属性的可截取签名方案,与文献[4]相比,减少点乘和哈希运算的次数,提高计算效率.曹素珍等[6]于2012年提出了一种不含双线性对的可截取签名方案,用指数运算代替对运算,从而提高方案效率,之后又于2013年提出了一种基于离散对数问题的可截取签名方案[7],进一步减少了指数运算的次数.刘庆华等[8]于2013年提出了一种高效的无证书内容可截取签名方案[9],用椭圆曲线上的标量点乘运算取代双线性对,进一步提高效率.
截止到目前,可截取签名方案大部分是基于双线性对运算或者大数因子分解问题,只有少部分是基于离散对数问题,并且还没有人将国密算法SM2与可截取签名相结合.为此,本文将可截取签名与国密算法SM2相结合,提出了一种基于椭圆曲线离散对数问题的无证书可截取签名方案,避免传统公钥密码系统的公钥验证和基于身份的密码系统[10]的私钥托管问题.与文献[8]相比,计算效率有所提升,并且在随机预言模型中是可证安全的,在适应性选择消息攻击下存在不可伪造性.
1 可截取签名定义
在可截取签名方案中,将原消息M看作一个集合型数据,由n个子消息组成,M可以表示为:M=(M1,M2,M3,M4,M5),Mi表示M中第i个子消息,截取后得到消息集合为M′.截取子集CI(M′)用来表示截取消息M′中所有子消息编号的集合.M′中仍然有n个子消息,其中被截掉的子消息用标记 ?表示,保留下来的消息与原消息M中对应编号位置的子消息相同.为了使原始签名者对原消息M具有一定控制权,防止截取者恶意截取,引入了内容截取访问结构(content extraction access structure,CEAS),CEAS中规定了截取者必须截取的子消息段的编号,并且满足CEAS⊂CI(M′).例如:M=(M1,M2,M3,M4,M5),CEAS={2,4},若CI(M′)={1,2,4,5},则M′={M1,M2,?,M4,M5},满足CEAS⊂CI(M′),表示截取方式合法;若CI(M′)={1,2,5},则M′={M1,M2,?,?,M5},CEASCI(M′),截取方式不合法.
可截取签名需要满足一定的安全属性,具体为:
1) 不可伪造性.攻击者可以访问一个CES签名预言机,如果消息M′满足:a) 不是一个合法的访问CES签名预言机的消息M的子消息;b) 是一个合法的访问CES签名预言机的消息M的子消息,但是不符合内容截取访问结构.在这种情况下,攻击者想要产生有关M′的一个合法的CES签名几乎是不可能的.
2) 隐私性.对于未被截取的子消息,攻击者若想从截取消息中获取未被截取消息的相关内容是不可行的.
2 基于SM2的无证书可截取签名方案
2.1 SM2数字签名简介
SM2的数字签名算法适用于商用密码应用中的数字签名和验证,在GM/T0003中规定了SM2椭圆曲线公钥密码算法的数字签名算法.具体的算法流程本节不再阐述,只简要介绍一下本文提出的可截取签名方案需要用到的参数表示[11].
(dA,pA):原始签名者Alice(简称A)的公私钥对,dA是私钥,pA是公钥,其中pA=[dA]G;
M:原始消息;
M′:待验证的消息;
e:密码杂凑函数作用于消息M的输出值;
e′:密码杂凑函数作用于消息M′的输出值;
G:椭圆曲线的一个基点,其阶为素数;
H():密码杂凑函数,一般消息摘要长度为256 bit;
modN:模N运算,例如,11 mod 2=1;
N:基点G的阶;
x‖y:x与y的拼接,其中x、y可以是比特串或字节串;
ZA:用户A的可辨别标识、部分椭圆曲线系统参数和用户A公钥的杂凑值;
(r,s):发送的签名;
(r′,s′):接收到的签名;
(x,y):椭圆曲线上的点.
2.2 具体方案
本文提出的基于椭圆曲线的无证书可截取签名方案,主要由7个算法构成.
4) 完整密钥生成 用户A收到(sA,RA)后,验证sAG=RA+hAPpub(modN)是否成立,若成立,计算PA2=sAG,用户A将PA1和PA2合并在一起作为用户公钥PKA=(PA1,PA2),用户将自己的秘密值xA与sA合并作为用户的私钥SKA=(xA,sA).
5) 签名算法 输入原消息M,原始签名者A给出相应的截取规则CEAS,按以下步骤执行签名过程.
A1 对于必选子消息i∈CEAS,计算hCEAS=H2((m[i]‖i)i∈CEAS,CEAS);对于非必选子消息i∈ΓCEAS,计算hi=H2(m[i],i,CEAS);
A3 随机选取k∈[1,N-1],计算椭圆曲线点(x1,y1)=[k]G;
A4 计算r=(e+x1)modN,若r=0或r+k=N,则返回步骤A3;
A5 令dA=(xA+sA) mod (N-2);
A6 签名得到σ=(1+dA)-1(k-rdA) modN,若σ=0,则返回步骤A3;
A7 返回全局签名σFull=(CEAS,σ,r).
6) 截取算法 截取者B收到全局签名σ′Full=(CEAS′,σ′,r′)后,根据SM2标准验签过程对接收到的全局签名进行验证,若验证通过,则进行后续的截取过程,否则验证失败.截取过程具体如下.
B1 根据原消息M和截取规则CEAS′,获得截取子集CI(M′),令X′=CI(M′);
B2 对于i∈ΓX′,截取者B计算hi=H2(m[i],CEAS′);
B3 返回截取签名σExt=(CEAS′,σ′,r′,(hi)i∈ΓCI(M′)).
7) 验证算法 验证者C收到截取消息M′的签名σ′Ext=(CEAS″,σ″,r″,(hi)i∈ΓCI(M′))后,首先验证CEAS″⊂CI(M′)是否成立,若成立,则继续下一步的操作;否则,终止算法.
C1 检验r″∈[1,N-1]是否成立,若成立,则进行下一步操作;否则,验证不通过;
C2 检验σ″∈[1,N-1]是否成立,若成立,则进行下一步操作;否则,验证不通过;
C3 对于i∈CEAS″,计算h′CEAS=H2((m′[i]‖i)i∈CEAS″,CEAS″);对于i∈X′CEAS″,计算h′i=H2(m′[i],CEAS″),结合所收到的截取签名的内容,可以得到对于i∈ΓCEAS″的子消息的哈希值h′i;
C5 计算t″=r″+σ″,若t″≠0,继续进行下一步操作;否则,验证不通过;
C7R=e″+x″1(modN),判断R=r″是否成立,若成立,则验证通过,签名有效;否则,验证不通过.
3 方案分析
3.1 正确性分析
对于一个诚实的截取者,可以通过以下推导过程来证明该方案的正确性.
首先验证部分私钥的正确性.sAG=(rA+hAx)G=RA+hA[x]G=RA+hAPpub,可以看出,该方案满足部分私钥验证方程.
2013年习近平总书记在出访中亚和东南亚国家期间提出了“一带一路”的伟大战略构想。青海雄踞西部地区,是连接“一带一路”的重要省份,也是承东启西、贯通南北的交通干线,拥有丰富的自然资源。因此,研究青海如何搭乘“一带一路”的发展快车将资源优势转变为经济优势,对于青海增强自身发展动力,提升区域核心竞争力具有重要意义。
(x″1,y″1)=[σ″]G+[t″](PA1+PA2)=[σ″]G+[t″](xA+sA)G=[σ″]G+(r″+σ″)(xA+sA)G=
(1+(xA+sA))[σ″]G+r″(xA+sA)G=(k-r″(xA+sA))G+r″(xA+sA)G=[k]G=(x1,y1).
因此可以证明e″=e,x″1=x1,即R=r″.验证方程通过,该方案是正确的.
对于恶意的截取者,可以通过恶意的截取方式来实施攻击,主要有4种情况.
1) 截取者在对原消息进行截取时没有遵守相应的截取规则CEAS.之后验证者在验证截取签名时,CEAS的改动必然会导致必选子消息的哈希值h′CEAS发生变化,与原来的hCEAS不同,同时由于hCEAS参与签名验证过程,因此截取者如果不遵守相应的截取规则,则签名无法通过验证.
2) 截取者按照截取规则对原消息进行截取得到M′,但把M′中的一些子消息m′[i]替换为m″[i],得到一个伪造的截取消息M″.在之后的验签过程中,需要对一些子消息进行哈希运算,即对于i∈CEAS,存在
H2((m[i]‖i)i∈CEAS,CEAS)≠H2((m″[i]‖i)i∈CEAS,CEAS),
或者是对于i∈ΓCEAS,
H2(m[i],CEAS)≠H2(m″[i],CEAS).
3) 截取者按照截取规则对原消息进行截取得到M′,并在截取消息M′后添加j条子消息得到M″,会造成验签过程无法通过,证明过程类似于2)中的分析,不再过多赘述.
4) 恶意的截取者试图伪装成原始签名者,并想要伪造一个原始签名信息.在可截取签名中,验证者在对签名进行验证时,使用的是原始签名者的公钥,对恶意的截取者来说,只知道原始签名者的公钥,并无法获知原始签名者的私钥(需要解决椭圆曲线离散对数问题).因此,恶意的截取者无法伪造出有效的原始签名对.
3.2 安全性证明
本文所提出的方案在随机预言模型下是可证安全的[12],在适应性消息选择攻击下存在不可伪造性,证明过程如下.
证明在多项式时间内,假设敌手AT最多能进行qH1次H1询问,qs次部分私钥询问,挑战者C随机选取挑战目标身份j,j∈[1,qH1].如果敌手AT能成功攻破本方案,那么挑战者C可以利用AT作为子程序解决椭圆曲线离散对数问题.
以下是敌手AT与挑战者C之间的交互过程.
1) 系统初始化:挑战者C首先选择安全参数k,产生主密钥x和系统参数params={Fq,E(Fq),G,Ppub,H1,H2},其中Ppub=xG,然后C保存主密钥x,并将params发送给AT.
2) 询问阶段:假设AT一共进行qH1次H1询问和qs次部分私钥询问,设挑战目标身份为IDj,j∈[1,qH1].
b) 部分私钥询问 C维护一个结构为{IDi,Ri,Pi2,si}部分私钥列表Ls,当收到来自AT的部分私钥询问,若i=j,则C输出⊥,并停止询问过程.否则若i≠j,C查询Ls,如果表中含有{IDi,Ri,Pi2,si},则返回{Ri,si}给AT.否则,C进行H1询问,得到对应元组{IDi,Ri,si,h1i}后,将{Ri,si}返回给AT.
c) 公钥询问 C创建一个结构为{IDi,Pi1,Pi2}的公钥列表LPK.AT提交关于用户IDi的公钥询问.
d) 公钥替换询问 当AT提交关于(IDi,PK′i)的公钥替换询问时,如果公钥列表LPK中含有PK′i,C定义PKi=PK′i;否则,C提交关于IDi的秘密值询问,然后C定义PKi=PK′i.
3) 输出阶段:游戏最后,AT停止询问阶段,输出一个有效的签名对(ID*,M*,s=(σ,r)),若ID*≠IDj,则挑战者C挑战失败并终止算法,否则伪造成功,挑战者C可以利用Forking引理[13],通过选择不同的H2可以再另外生成两个有效的签名对(ID*,M*,s=(σ2,r2)),(ID*,M*,s=(σ3,r3)).然后有(x′1,y′1)=[σ′]G+[t](PA1+PA2)=(x1,y1)=[k]G,因为PA1=xAG,PA2=sAG,t=r′+σ′,即
[σ′1]G+[r′1+σ′1](xA+sA)G=[k]G,
[σ′2]G+[r′2+σ′2](xA+sA)G=[k]G,
[σ′3]G+[r′3+σ′3](xA+sA)G=[k]G,
定理2如果哈希函数满足单向性(one-way),也称为抗原像攻击性,即对于给定的一个哈希输出值,倒推出输入数据是很难的,计算上不可行.那么本文中基于SM2的无证书可截取签名方案满足隐私性.
证明根据截取签名σExt=(CEAS,σ,r,(hi)i∈ΓCI(M′)),可知截取签名σExt包括了所有未截取消息的哈希值,但由于哈希函数具有单向性,故即使得到了所有未被截取消息的哈希值,也无法获知未被截取消息的具体内容.另一方面,截取签名不包含有关截取消息的任何内容,也就是说截取消息与未被截取的消息相独立,对于验证者来说,即使知道了所有的截取消息,也无法从中推出有关未被截取消息的相关内容.因此,本文提出的方案满足隐私性.
3.3 效率分析
本文提出的方案与文献[5-8]中的方案的进行效率比较.为了表示方便,par表示对运算,exp表示指数运算,sca表示基于椭圆曲线密码编码(elliptic curves cryptography, ECC)的标量乘法运算,has表示哈希函数运算.n表示子消息的数目,m表示截取子集中子消息的数目,mCEAS表示包含在内容截取访问结构CEAS中的子消息的数目.方案的效率比较如表1所示.
表1 不同方案间的效率比较Tab.1 Efficiency comparison between different schemes
由于进行一次双线性对运算所需的时间大约为椭圆曲线上标量乘法运算的10倍,椭圆曲线上的加法运算也比较高效,点乘运算可以用硬件实验加速[14]. 因此与文献[5]的方案相比,本方案不采用双线性对运算,极大提高了方案效率.此外,一次指数运算的时间同样大于椭圆曲线上的标量乘法运算,因此本方案不采用指数运算,进一步提升效率.与文献[8]的方案相比,本方案采用统一计算哈希值的思想,减少签名验签过程中哈希运算的次数,在一定程度上改进方案效率.综上所述,本方案与文献[5-8]中的方案相比,在计算效率上有着明显优势.
4 总结
本文结合国密算法SM2,提出一种新的基于椭圆曲线离散对数问题的无证书可截取签名方案,在随机预言模型下证明该方案满足适应性选择消息下存在不可伪造性.与现有的可截取签名方案相比,本方案结合无证书签名体制,避免了传统公钥体制下的证书管理问题以及基于身份的公钥密码体制的私钥托管问题,从整体上提升了效率.此外,本方案在计算效率方面有优势,在数据隐私保护方面也有广泛的应用前景.