改进的基于身份的签密方案

汤鹏志，郭红丽，张婷婷

(华东交通大学 系统工程与密码学研究所，南昌 330013)

签密能够同时实现签名和加密，大大提高了消息的安全性和计算效率。1984 年，Shamir［1］使用用户的身份(电子邮箱或者邮政地址等)作为公钥，提出基于身份的密码体制。2002 年，Malone－Lee［2］提出了基于身份的签密方案，但Libert 和Quisquater［3］指出该方案不满足语义安全性。2005 年，Chen 和Malone－Lee［4］提出了效率比较高的基于身份的签密方案，但该方案既不满足公开验证性，也不满足数据的完备性。李发根等［5］提出了一个新的效率比较高的基于身份的签密。近几年，基于身份的签密方案在理论上和应用上都取得了很大的进步。［6－8］可对文献［9］进行选择性明文攻击，由此提出一个安全高效的改进的基于身份的签密方案。

1 预备知识

1.1 双线性对 设G1是生成元为P 的q 阶的加法循环群，G2是生成元为P 的q 阶的乘法循环群，映射e:G1×G1→G2是一个双线性对，满足下列性质:(1)双线性性:对 U，V ∈G1，a，b ∈，有e(aU，bV)= e(U，V)ab。

(2)非退化性:-U，V ∈G1，使得e(U，V)≠1。

(3)实效性:对 U，V ∈G1，e(U，V)是有效且可计算的。

1.2 (CBDHP) 已知P，aP，bP，cP ∈G1，计算e(P，P)abc∈G2。

1.3 (DBDHP) 已知P 为G1的生成元，给定a，b，c ∈，P，aP，bP，cP ∈G1，h ∈G2，判定h =e(P，P)abc是否成立。

1.4 (DLP) 对 P，Q ∈G，已知P，Q，求a，使得Q = aP。

2 签密方案的安全性定义

签密方案的机密性和不可伪造性可定义为:

定义1 机密性。［10，11］若在适应性选择密文攻击下的消息，基于身份的签密方案具有不可区分性(IND－IBSC－CCA2)。则没有PPT 时间内的攻击者，具备不可忽视的优势赢得以下定义的游戏的优势(IND－IBSC－GAME)的能力。游戏的步骤为:

(1)系统建立。挑战者C 输入参数k，执行方案中的系统建立的算法。将得到的系统参数发送给攻击者A。

(2)询问1。攻击者A 执行如下询问:

1)密钥询问。攻击者A 选择IDU发送给挑战者C，C 计算SU= extract(IDU)。将计算得到的密钥发送给攻击者A。

2)签密询问。攻击者A 将选择的IDA、IDB和明文消息m 发送给挑战者C。挑战者C 执行签密算法计算σ = signcrypt(m，SA，IDB)。将得到的σ 发送给攻击者A。

3)解签密询问。攻击者A 将选择的IDA、IDB和密文消息σ 发送给挑战者C。挑战者C 执行解签密算法计算SB= extract(IDB)和m = unsigncrypt(σ，IDA，SB)，并将得到的m 或者“⊥”发送给攻击者A。

4)挑战。攻击者A 产生明文m0、m1和打算挑战的IDi和IDj。IDj没有执行过的密钥询问。C 随机选择u ∈{0，1}，计算σ = signcrypt(mu，Si，IDj)，并将σ 发送给攻击者A。

5)询问2。攻击者A 执行多项式有界次类似于(2)的询问。但攻击者A 不能对目标用户IDj和目标密文σ 执行询问。

6)猜测。攻击者A 输出u'。若u' = u，则攻击者A 赢得此游戏。

定义2 不可伪造性。［10，11］在适应性选择消息和身份攻击下，基于身份的签密方案是存在性不可伪造的(EUF－IBSC－CMIA)。则没有PPT 时间的攻击者，具备不可忽视的优势赢得以下定义的游戏(EUF－IBSC－GAME)的能力。游戏的步骤为:

a)系统建立。挑战者C 输入参数k，执行方案中的系统建立的算法，并将得到的系统参数发送给攻击者A。

b)询问。攻击者A 执行类似于定义1 的询问。

c)伪造。最后，攻击者A 生成新的三元组(σ'，IDA，IDB)，且(σ'，IDA，IDB)不是在寻找阶段的密钥提取预言机和签密预言机输出的。若unsigncrypt(σ'，SB，IDA)≠⊥，则攻击者A 赢得以上的游戏。

3 原方案分析

原方案请参照文献［9］，原方案不具有语义安全性，可以实施不可区分性明文攻击。

假设攻击者A 选择明文m0，m1，C 随机选择mi，i ∈{0，1}。经过签密算法产生一个密文消息σ*= (C*，T*，Z*，V*)，然后A 计算h*= H3(m0|| B|| Z*|| IDr|| IDs)，最后验证e(V，Ppub+dIDsP)与Z*Yh*是否相等。若相等，则σ*是m0对应的签密密文;若不相等，则σ*是m1对应的签密密文。因此此方案不具有语义安全性。

4 原文献［9］方案的改进

为了抵抗选择明文攻击，本文改进了文献［10］的方案，提出改进的基于身份的签密方案。系统建立大部分参考原方案，其中修改的部分为:将原方案的系统主密钥改为s，不需要哈希函数H3。下面为密钥生成、签密与解签密:

(1)密钥生成:QID= H1(ID)，公钥为dID=sQID，私钥为并通过秘密信道将SID传给使用者。

(2)签密:假设IDA为发送者，IDB为接收者，M 为所要签密的明文，IDA执行以下步骤:

步骤1:随机选择t ∈Z*q ，计算T = t(Ppub+dIDBP)，Z = Yt，C= H2(Z)⊕M。

步骤2:计算V= tSIDA，输出密文σ= (C，V，T)。

(3)解签密

接收者IDB收到密文σ = (C，V，T)，IDB执行以下步骤:

步骤1:计算B = e(T，SIDB)，M = H2(B)⊕C。

步骤2:检查e(V，Ppub+ dIDAP)= Z 是否成立，如果不成立，输出⊥;如果成立，则接受σ 为有效密文。

算法的正确性通过以下两个式子检验:

(1)验证签密数据的有效性:

(2)验证消息的正确性

5 改进的签密方案的安全性分析和证明

假设哈希函数H1、H2为随机预言机。攻击者A在PPT 时间内对挑战者Q 执行有限次H1询问、H2询问、公钥询问、私钥询问、签密询问和解签密询问，列表L1、L2、LPK、LSK、LS、LU，用于记录对应的每次询问的情况，q1、q2、qK、qS、qU表示对应的询问次数。

5.1 机密性

在随机预言机模型和DLP 困难问题下，如果敌手A 能在时间t 内以一个不可忽略的优势ε 赢得上述IND－IBSC 游戏，那么存在算法Q 在PPT 时间内解决DBDHP。

证明:设算法Q 能够解决DBDHP，即输入(P，aP，bP，cP)和ξ，随机选取a，b，c ∈Z*q ，判断ξ =e(P，P)abc是否成立。

(1)系统参数设置:挑战者Q 生成系统参数params = {G1，G2，e，P，Ppub，Y，H1，H2}，将系统参数发送给敌手A;设系统公钥为Ppub= ap，a (未知)为系统主密钥;目标用户为IDk。

(2)询问

1)哈希询问

H1询问:挑战者Q 收到攻击者A 关于(IDi，QIDi)的H1询问时，当i ≠k 时，Q 首先查询列表L1，如果(IDi，QIDi)在列表L1中，则Q 将QIDi返回给A，否则，Q 随机选择QIDi∈Z*q ，计算并将其作为回答返回给A，并将(IDi，QIDi)添加列表L1;当i = k时，设置Qk= H1(IDk)= dP。

H2询问:当挑战者Q 收到攻击者A 关于(ti，Zi，h2i)的H2询问时，Q 首先查询列表L2，如果(ti，Zi，h2i)在列表L2中，则Q 将h2i返回给A;否则，Q随机选择h2i∈Z*q ，并将其作为回答返回给A，并将(ti，Zi，h2i)添加列表L1。

2)公钥询问

当挑战者Q 收到攻击者A 关于(IDi，QIDi，dIDi)的公钥询问时，Q 首先查询列表LPK，如果(IDi，QIDi，dIDi)在列表LPK中，则Q 将dIDi返回给A;否则，C 随机选择QIDi∈Z*q ，计算dIDi= aQIDi，并将dIDi作为回答返回给A，并将(IDi，QIDi，dIDi)添加列表LPK。

3)私钥询问

当挑战者Q 收到攻击者A 关于(IDi，SIDi)的私钥询问时，Q 首先查询列表LSK，如果(IDi，SIDi)在列表LSK中，则Q 将SIDi返回给A;否则:

(a)当i = k 时，终止算法;

(b)当i ≠k 时，Q 先执行H1询问得到QIDi，计算将获得的SIDi作为答复发送给A1，并将(IDi，SIDi)记录到列表LSK中。

4)签密询问

当挑战者Q 收到攻击者A 关于(IDi，IDj)和Mi的签密询问时，Q 首先检查列表LS，如果(IDi，IDj，Zi，Mi，Ci，Vi，Ti)已经在列表中，则将相应的签密数据发送给A;否则:

(a)当i ≠k 时，Q 先执行H1询问和H2询问，得到QIDi、h2i，再查询列表LPK、LSK，随机选择t∈，计算Ti= t(Ppub+ dIDiP)，Zi= Yt，Ci=H2(Zi)⊕M，得到密文σi= (Ci，Vi，Ti)，将密文发送给攻击者A，并将(IDi，IDj，Zi，Mi，Ci，Vi，Ti)添加到列表LS。

(b)当i = k 时，Q 随机选取Vk，Tk∈Z*q ，计算Zk= e(Vk，Ppub+dIDkP)，将(Vk，Tk)作为目标用户的签名，计算Zk= e(Vk，Ppub+dIDkP)= e(P，P)t，通过查询列表L2，得到h2i，计算Ck= h2i⊕Mi，将签密数据(Ck，Vk，Tk)发送给A。

5)解签密询问

当挑战者Q 收到攻击者A 关于(IDi，IDj)的签密数据σi= (Ci，Vi，Ti)时，查询列表LU，如果(Ci，Vi，Ti)已经存在于列表LU中，则返回Mi给Q，否则:

(a)当j = k 时，算法终止，拒绝输出消息M;

(b)当j ≠k 时，Q 根据签密者的身份从列表L2得到h2i，从列表LPK中查询得到dIDi，从LS中得到Zi，计算e(Vi，Ppub+ dIDiP)= Zi是否成立，如果不成立，则拒绝接受签密数据σi= (Ci，Vi，Ti);否则，根据从列表LS中得到Ti，计算Bj=e(Ti，SIDj)，再根据Bj查询列表L2得到的h2j，然后计算M = h2j⊕Cj，最后将得到的明文消息M 发送给攻击者A。

(3)挑战

A 随机选择两个希望挑战的身份(IDi，IDj)和两个明文M0、M1，当j ≠k，Q 终止挑战;当j = k时，Ppub= uP，Q 查询列表L1、L2，得到(IDi，QIDi)、(ti，Zi，h2i)，计算SA= bP，随机选择c ∈Z*

(4)询问2。敌手A 继续执行类似于(2)的询问。但是不能对IDB和σ*执行密钥询问和解签密询问。

(5)猜测。两次询问结束后，如果敌手可以得到p' = p，则挑战者Q 输出ξ = e(Ti，SIDj)= e(a(u +ud)P，bP)= e(P，P)a(u+ud)b，即解决了DBDHP。

5.2 不可伪造性

定理2 在随机预言机模型下，基于DLP，对于敌手A，本方案在IND－IBSC 攻击下是存在性不可伪造的。

证明:算法B 能解决DLP 问题，即输入y =xP，输出x。

系统设置。算法Q 生成系统参数params ={G1，G2，e，P，Ppub，Y，H1，H2}，其中Ppub= aP (a为系统主密钥)。

询问。A 向Q 执行多项式有界次询问，询问过程和定理1 相同。

由上述过程可知，A 通过向Q 进行多项式有限次询问后，解决了DLP，但是这与DLP 的困难性矛盾，所以在随机预言机模型和DLP 困难性的假设下，该方案是存在性不可伪造的。

6 总结

在基于身份的签密中，降低计算成本，提高计算效率是人们关心的话题。本方案比原方案少了一个哈希运算，且在随机预言机模型下，满足机密性和不可伪造性。

［1］ Shamir A.Identity－based cryptosystems and signature schemes［C］//Advances in Cryptology－Crypto’84，LNCS 196.Berlin:Springer－Verlag，1984:47－53.

［2］ Malone－Lee J.Identity based signcryption ［EB/OL］.Cryptology ePrint Archive，Report 2002/098，2002.http://eprint.iacr.org/2002/098.2011－6－2.

［3］ Libert B，Quisquater J.A new identity based signcryption scheme from pairings［C］.The IEEE Information Theory Workshop (ITW’2003)，Pairs，2003:155－158.

［4］ L.Chen and J.Malone－Lee.Improved identity－based signcryption.Public Key Cryptography－PKC 2005［C］，Berlin:Spring－Verlag，2005:362－379.

［5］李发根，胡予濮，李刚. 一个高效的基于身份的签密方案［J］. 计算机学报，2006，29(9):1641－1647.

［6］张明武，杨波，周敏，等. 基于身份的公开验证签密方案［J］. 计算机应用，2012，32(1):99－103.

［7］肖鸿飞，刘长江. 一种基于身份的改进高效签密方案［J］. 计算机工程，2011，37(24):126－128.

［8］周才学，周顽，胡日新，等. 基于身份的签密方案分析与改进［J］. 计算机工程，2012，38(2):132－134.

［9］邓伦治，王祥斌，瞿云云. 高效的基于身份的签密方案［J］. 计算机工程与科学，2014，36(3):441－445.

［10］LIBERT B，QUISQUATER J.A new identity based signcryption schemes from pairings［C］//Proc of IEEE Information Theory Workshop，2003:155－158.

［11］何俊杰，焦淑云，祁传达. 一个基于身份的签密方案的分析与改进［J］. 计算机应用研究，2013，30(3):913－920.