无双线性对的无证书签密方案分析与改进

张雪峰,姜民富

(信阳农林学院 信息工程学院，河南 信阳 464000)

0 引言

信息的保密和认证是密码学研究的两个重要方面，数字签名算法和公钥加密算法是公钥密码学领域分别实现保密和认证的两类重要算法.数字签密[1]将数字签名和公钥加密结合在一起，可以同时完成对消息的加密和签名，相较于先签名后加密，签密算法无论在计算性能方面还是在数据传输量方面都有较明显的优势.

传统的基于证书公钥密码体制需要解决复杂的公钥证书的存储和管理问题，而基于身份公钥密码体制[2]虽然不需要公钥证书，但却出现了新的安全隐患，即密钥托管问题.无证书公钥密码体制[3]很好地解决了这两个问题：由用户自己生成公钥，不需要公钥证书；由用户和私钥生成中心(KGC)共同生成私钥，解决了密钥托管问题.2008年，BARBOSA等[4]提出了第一个无证书签密方案，并定义了无证书签密的安全模型.同年，ARANHA等[5]和WU等[6]基于双线性对也分别提出无证书签密方案.但SHARMILA等[7]和SELVI等[8]指出文献[4,5,6]方案都不安全.文献[8]还提出了一个不使用双线性对的无证书签密方案，由于不使用双线性对运算，使得方案的运算效率有较大提高，所以备受研究者的关注.朱辉等[9]和刘文浩等[10]也分别提出了不使用双线性对的无证书签密方案，都声称方案的安全性基于离散对数难解问题.但这些方案都被证明存在安全隐患[11-14]，都不能保障不可伪造性和机密性.

最近，高键鑫等[15]提出一种无双线性对的无证书签密方案.本文对文献[15]方案的安全性进行分析，指出方案不能抵抗公钥替换攻击，不满足不可伪造性.本文给出了一种改进方案，并证明了改进方案在随机预言模型下对自适应选择消息和身份攻击是存在性不可伪造的，其安全性依赖于群G中的DLP的难解性.

1 预备知识

1.1 离散对数问题

设G是阶为素数q的乘法群，g是G的一个生成元.下面考虑G中的离散对数问题和假设.

1)离散对数问题(DLP)：对任意的yG，计算使得y=gx.

2)DLP假设：对任意的概率多项式时间算法A解决DLP的优势：

是可以忽略的.

1.2 无证书签密系统的攻击模型

无证书密码系统中，公钥由用户自己生成，没有公钥证书认证，所以非法攻击者可以伪造替换合法用户的公钥.另一方面，私钥生成中心拥有系统主密钥，可以生成所有用户的部分私钥.所以，在无证书密码系统中，攻击者被分成两类：第1类攻击者AI没有系统主密钥，但可以替换用户的公钥；第2类攻击者AII知道系统主密钥，但是不可以替换用户的公钥.

在随机预言模型下，无证书签密方案的安全模型(机密性和不可伪造型)可以参看文献[15]，在此不作赘述.

2 对文献[15]方案的攻击

2.1 方案回顾

(4)用户公钥生成.用户计算uu=gzu，生成用户公钥对PKu=(wu,uu).

h=H2(m,R,IDa,ua,r2),

c=E((wbubyh1)r1,(r2,m))；

将消息m的签密文σ=(h,s,c)发送给用户B.

(6)解密验证.用户B收到签密文σ′=(h′,s′,c′)后，计算

则通过验证并接受消息m′.

2.2 公钥替换攻击

通过分析发现，高键鑫等[15]提出的无证书签密方案不满足不可伪造性，第1类攻击者AI可以施行公钥替换攻击具体步骤如下：

(2)伪造攻击.对于消息m*，攻击者进行以下操作：

3)计算h1=H1(IDb,wb)c*=E((wbubyh1)r1,(r2,m*))，

则σ*=(h*,s*,c*)是攻击者AI冒充用户A伪造的发给用户B的签密文.

上述伪造产生的签密文σ*=(h*,s*,c*)可以解密并通过验证证明如下：

所以

(wbubyh1)r1=(gsbgzbyxh1)r1=g(sb+xH1(IDb,wb)+zb)r1=

g(tb+zb)r1=g(tb+zb)s*(δ+h*)=

表明加密密钥与解密密钥相等，用户B可以正确解密获得消息m*.

(2)攻击者伪造的签密文满足可验证性.由于

(gδgh*)s*=g(δ+h*)s*=gr1=R,

所以

说明由伪造签密文σ*=(h*,s*,c*)解密获得的消息m*可以通过验证.

3 对文献[15]方案的改进

3.1 改进方案描述

改进方案的用户部分密钥生成、生成用户私钥和生成用户公钥环节与原方案相同，其他环节描述如下：

(2)签密.用户A执行以下操作生成发送给用户B的消息m的签密文.

3)计算

h=H2(m,R,IDa,ua,r2),

4)用户A发送签密文σ=(h,s,c)给用户B.

(3)解密验证.用户B收到签密文σ=(h,s,c)后，进行以下操作：

3.2 改进方案的正确性

g(sb+xH1(IDb,wb)+h2zb)r1=g(tb+h2zb)r1=

表明加密密钥与解密密钥相等，用户B可以正确解密获得消息m.

(2)验证签密文的正确性.由于

所以

说明由签密文σ=(h,s,c)解密获得的消息m可以通过验证.

4 改进方案的安全性分析

4.1 机密性

机密性即选择密文攻击下的不可区分性，其严格证明过程与文献[15]相似，在此不作详述，仅仅分析如下：

由于第I类攻击者AI和第II类攻击者AII都没有用户A和用户B的完全私钥，所以无法获得加解密密钥，不能完成对签密文的解密，所以所提方案对选择密文攻击是不可区分的，即方案满足机密性.

4.2 不可伪造性

定理1 在随机预言模型下，改进方案对第I类攻击者AI的自适应选择消息和身份攻击是存在性不可伪造的，其安全性依赖于群G中的DLP的难解性.

证明假设存在攻击者AI能够以不可忽略的概率伪造签密，则DLP的挑战者执行如下步骤：

(1)系统初始化.

挑战者首先生成系统公开参数params=(p,q,g,y,H1,H2,H3,E,D)，并发送给攻击者AI.其中，y=ga是系统公钥，即用a模拟系统主密钥，但不知道a的值，其目标是求解出a.

(2)询问.

AI可适应性地向进行多项式有限次的询问，维护表L1,L2,L3,LPK,LSC记录并响应AI的H1询问，H2询问，H3询问，公钥询问和签密询问.选择随机整数n，记IDn=ID*.

5)部分私钥询问：对AI关于用户IDi的部分私钥询问，若IDi=ID*，则挑战失败，算法终止；若IDi≠ID*，则从表L1中找出项(IDi,si,wi,ti,qi)，将ti作为IDi的部分私钥返回给AI.

6)秘密值询问：AI可以向询问用户IDi的秘密值.查找表LPK，若不含项(IDi,wi,ui,zi)，说明没有进行过关于IDi的公钥询问，首先执行公钥询问；将zi返回给AI作为用户IDi的秘密值.

r1=s(gaza+ta+h),

c=E(v,(r2,m)).

如果(m,gr1,IDa,ua,r2,h)已经含于列表L2中，则重新选择h,r1,r2，并将(m,gr1,IDa,ua,r2,h)加到列表L2；将(h,s,c)作为身份IDa对消息m的签密返回给AI.

(3)伪造.

如果算法没有停止，则AI在没有询问过(ID*,m)的签密和ID*的部分私钥的前提下，伪造了用户ID*对消息m的签密(ID*,IDb,h,s,c).由Forking引理[16]可知，重放H2询问，可以得到(ID*,IDb,m)的两个有效签密：

(ID*,IDb,h,s,c), (ID*,IDb,h′,s′,c)，

其中h≠h′，且

s(gID*zID*+tID*+h)=s′(gID*zID*+tID*+h′)，

其中tID*=sID*+a·qID*，可以解出

gID*zID*-sID*)，

即挑战者获得了DLP的解.

所以，在DLP困难的假设下，攻击者AI不能成功伪造签密，即所提改进方案可以抵抗第I类攻击者AI的自适应选择消息和身份下的存在性伪造攻击.证毕.

定理1也说明了改进方案可以抵抗第I类攻击者的公钥替换攻击.

定理2 在随机预言模型下，改进方案对第II类攻击者AII的自适应选择消息和身份攻击是存在性不可伪造的，其安全性依赖于群G中的DLP的难解性.

证明假设存在攻击者AII能够以不可忽略的概率伪造签密，则DLP的挑战者执行如下步骤：

(1)系统初始化.

(2)询问.

AII可适应性地向进行多项式有限次的询问.随机选择整数n，记IDn=ID*.H2询问、H3询问以及签密询问与定理1的证明相同.

3)部分私钥询问：AII可以向询问用户IDi的部分私钥.从列表L1中找出项(IDi,si,wi,ti,qi)，将ti作为IDi的部分私钥返回给AII.

4)秘密值询问：对AII关于IDi的秘密值询问，如果IDi=ID*，宣告失败，算法终止；否则，即IDi≠ID*，查找表LPK，若不含项(IDi,wi,ui,zi)，说明没有进行过关于IDi的公钥询问，首先执行公钥询问将zi返回给AII作为用户IDi的秘密值.

(3)伪造.

如果算法没有停止，则AII在没有询问过(ID*,m)的签密和ID*的秘密值的前提下，成功伪造用户ID*对消息m的签密(ID*,IDb,h,s,c).由Forking引理[16]可知，重放H2询问，可以得到(ID*,IDb,m)的两个有效签密

(ID*,IDb,h,s,c), (ID*,IDb,h′,s′,c)，

其中h≠h′，且

s(gID*zID*+tID*+h)=s′(gID*zID*+tID*+h′)，

可以解出

即挑战者获得了DLP的解.

所以，在DLP困难的假设下，攻击者AII不能伪造签密，即所提改进方案可以抵抗第II类攻击者AII的自适应选择消息和身份下的存在性伪造攻击.证毕.

5 结语

对高键鑫等人[15]提出的无双线性对的无证书签密方案进行了密码攻击，发现方案不能抵抗公钥替换攻击.为了消除这种安全缺陷，提出了一种改进方案.安全性证明显示改进方案对两类攻击者的自适应选择消息和身份攻击是存在性不可伪造的，有效地抵抗了公钥替换攻击.同时，改进方案仍然没有使用计算耗时的对运算，具有较高的运算效率.