几个无证书签密方案的密码分析与改进＊

周才学

（九江学院信息科学与技术学院，江西 九江332005）

1 引言

签密的概念首先由Zheng［1］于1997年提出，它能在一个逻辑步骤内同时实现加密和认证，而所需的计算和通信代价大大低于传统的先签名后加密方案。自从签密被提出后，迅速成为研究热点。

1984年，Shamir［2］提出了基于身份的密码体制。在这种体制中，用户的公钥可由用户的身份信息直接计算出来，从而省去了公钥证书，简化了公钥的管理，自它被提出后，也迅速成为了研究热点。但是，基于身份的密码体制有一个天生的缺陷，就是存在密钥托管问题，即可信中心知道所有用户的私钥。为解决此问题，2003年，Al－Riyami等人［3］提出了无证书密码体制。在无证书密码体制中，用户的私钥由两部分组成，一部分由可信中心产生，另一部分由用户自己生成。这样就解决了密钥托管问题，同时公钥也不需要证书，因此这种密码体制具有巨大的优越性。

2008年，Barbosa等人［4］将无证书概念推广到签密，首次提出了无证书签密的概念。同年Wu等人［5］、Aranha等人［6］基于双线性对也各自提出一个方案。但Selvi等人［7］于2009年指出文献［4～6］都是不安全的，他们给出了具体的攻击方法并提出一个不使用双线性对运算的无证书签密方案。此后，人们又提出了多接收者无证书签密［8～10］、无证书 混 合 签 密［11～13］、标 准 模 型 下 的 无 证 书 签密［14，15］和无证书广播签密［16］等方案。2009年，罗铭等人［17］提出一个适用于3G网络的无证书的短签密方案；2010年，葛爱军等人［18］提出一个不含双线性对运算的无证书签密方案；李鹏程等人［19］提出一个改进的无证书数字签密方案；2011年，王星等人［20］提出一个高效的无证书签密方案。

本文对文献［17～20］进行了安全性分析，分析表明，罗铭等人的方案存在伪造性攻击；葛爱军等人的方案存在保密性攻击；李鹏程等人的方案存在保密性和伪造性攻击；王星等人的方案存在伪造性攻击。对每个方案分别进行了改进，并对改进方案进行了安全性证明。

2 基本概念

2.1 双线性对

设G1是素数q阶加法循环群，G2是同阶乘法循环群。映射e：G1×G1→G2称作双线性对，如果该映射具有以下三个性质：

（1）双线性性：对任意的P、Q ∈G1，a、b∈Zq，都有e （aP，bQ）＝e （P，Q ）ab；

（2）非 退 化 性：存 在 P、Q ∈ G1，满 足e （P，Q）≠1G2；

（3）可计算性：对任意的P、Q∈G1，存在一个有效的算法计算e （P，Q）。

2.2 困难问题

定义1 BDH（Bilinear Diffie－Hellman）问题：已知 （P，aP，bP，cP），a、b、c∈，a、b、c的具体值未知，要求计算e （P，P ）abc。

定义 2 DBDH（Decisional Bilinear Diffie－Hellman）问题：已知 （P，aP，bP，cP，T ），a、b、c∈Zq＊，a、b、c具 体 的 值 未 知，要 求 判 断 等 式e （P，P ）abc＝T是否成立。

定义 3 GBDH（Gap Bilinear Diffie－Hellman）问题：已知 （P，aP，bP，cP），a、b、c∈，a、b、c的具体值未知，要求在DBDH预言机的帮助下计算e （P，P ）abc。

定义 4 CDH （Computational Diffie－Hellman）问题：已知G1中的 （P，aP，bP ），a、b∈Zq，a、b的具体值未知，要求计算abP。

定义5 GDH′问题［4］：已知G1中的 （P，aP，bP），a、b∈Zq，a、b的具体值未知，要求在DBDH预言机的帮助下计算abP。

2.3 无证书签密方案的安全模型

在无证书密码体制中，因为没有证书来对用户的公钥进行认证，这样攻击者就可以把用户的公钥替换为自己任意选定的值，所以无证书密码体制存在两类攻击者［3］：第I类攻击者AI，他不知道系统主密钥，但是他可以替换任意用户的公钥；第II类攻击者AII，他知道系统主密钥，所以他可以计算出每个用户的部分私钥，但是他不可以替换用户的公钥。在实际应用中，AI模拟的是除PKG之外的攻击者，AII模拟的是恶意PKG的非法攻击。

无证书签密方案在第I类攻击者AI和第II类攻击者AII下都需要满足机密性和不可伪造性。下面分别以游戏的方式直观地给出无证书签密方案的安全模型。

定义6 类型I攻击下的保密性：若不存在任何多项式有界的敌手Adv1以不可忽略优势赢得以下游戏，则称该无证书签密方案在适应性选择密文攻击下具有不可区分性（IND－CLSC－CCA2）。

（1）初始化：挑战者C输入安全参数k，运行Setup，并发送系统参数Params给敌手Adv1，保密主密钥。

（2）寻找阶段：敌手Adv1可以适应性地执行多项式有界次的以下询问：

①Hash询问：Adv1可以对任何输入进行Hash询问。

②部分私钥生成询问：Adv1输入一个身份ID，挑战者C计算身份ID的部分私钥SID并返回给Adv1。

③私钥生成询问：Adv1选择一个身份ID，挑战者C计算相应的私钥skID并返回给Adv1。如果相应的公钥被替换，则不允许询问该预言机。这是因为挑战者不知道相应的秘密值，所以不能提供完整私钥。

④公钥询问：Adv1输入身份ID，挑战者C计算相应的公钥pkID。

⑤替换公钥询问：在任何时间，Adv1选择一个新的值pk′ID，替换原来的公钥pkID。

⑥签密询问：Adv1选择身份IDa、IDb和明文m，设ska为IDa的私钥、pkb为IDb的公钥，C计算σ ＝ Signcrypt（m，ska，pkb）并 将 结 果 σ 发 送 给Adv1。假如IDa的公钥被替换，为了生成正确的回答，要求Adv1另外提供IDa的秘密值给C。

⑦解签密询问：Adv1选择身份IDa、IDb和密文σ，设skb为IDb的私钥、pka为IDa的公钥，C计算 Unsigncrypt（σ，pka，skb），最后发送结果明文m或“失败”给Adv1。如果IDb的公钥被替换，为了生成正确的回答，要求Adv1另外提供IDb的秘密值给C。

（3）挑战阶段：Adv1生成两个相同长度的明文m0、m1和希望挑战的两个身份ID＊a和ID＊b，ID＊b不能是已经执行过部分密钥生成询问或私钥生成询问的身份，C随机选择j∈ ｛0，1｝，计算σ＊＝Signcrypt（mj，ska，pkb） 并 将 结 果 σ＊发 送 给Adv1。

（4）猜测阶段：Adv1像寻找阶段一样执行多项式有界次的适应性的询问，但不能对ID＊b执行部分密钥生成或私钥生成询问，也不能对密文σ＊、发送者ID＊a和接收者ID＊b执行Unsigncrypt询问，除非ID＊a或ID＊b的公钥被替换。

（5）最后，Adv1输出一个值j′作为对j的猜测，若j′＝j，Adv1赢得游戏。

定义7 类型II攻击下的保密性：若不存在任何多项式有界的敌手Adv2以不可忽略的优势赢得以下游戏，则称该无证书签密方案在适应性选择密文攻击下具有不可区分性（IND－CLSC－CCA2）。

（1）初始化：挑战者C输入安全参数k，运行Setup算法，并发送params和主密钥s给敌手Adv2。

（2）寻找阶段：敌手Adv2可以执行定义1中除“公钥替换询问”和“部分密钥生成询问”以外的所有查询，查询方法同定义1。

（3）挑战阶段：Adv2生成两个相同长度的不同明文m0、m1和希望挑战的两个身份ID＊a和ID＊b，ID＊b不能是已经执行过私钥生成询问的身份，C随机选择j∈ ｛0，1｝，计算σ＊＝Signcrypt（mj，ska，pkb）并将结果σ＊发送给Adv2。

（4）猜测阶段：Adv2像寻找阶段一样适应性地执行多项式有界次的询问，但不能对ID＊b执行私钥生成询问，也不能对密文σ＊、发送者ID＊a和接收者ID＊b执行Unsigncrypt询问。

（5）最后，Adv2输出一个值j′作为对j的猜测，若j′＝j，Adv2赢得游戏。

定义8 类型I攻击下的不可伪造性：若不存在任何多项式有界的敌手Adv1以不可忽略的优势赢得以下游戏，则称该无证书签密方案在适应性选择消息攻击下具有不可伪造性（EUF－CLSCCMA）。

（1）初始化和寻找阶段同定义1。

（2）Adv1输出某发送者IDa（对应接收者为IDb）对某消息m 的签密σ，且 （σ，IDa，IDb）不是签密预言机产生的，也未对IDa进行过部分密钥生成询问或私钥生成询问，若Unsigncrypt（σ，pka，skb）的结果不是“错误”，则Adv1赢得游戏。

定义9 类型II攻击下的不可伪造性：若不存在任何多项式有界的敌手Adv2以一个不可忽略的优势赢得以下游戏，则称一个无证书签密方案在适应性选择消息攻击下具有不可伪造性（EUFCLSC－CMA）。

（1）初始化和寻找阶段同定义2。

（2）Adv2输出某发送者IDa（对应接收者为IDb）对某消息m 的签密σ，且 （σ，IDa，IDb）不是签密预言机产生的，也未对IDa进行过私钥生成询问，若 Unsigncrypt（σ，pka，skb）的 结 果 不 是 “错误”，则Adv2赢得游戏。

3 对罗铭等人方案的分析与改进

3.1 罗铭等人的方案

Setup：KGC（Key Generation Center）随机选择一个生成元P∈G1，双线性映射e：G1×G1→G2，选取主密钥s∈并计算主公钥PPub＝sP，再选择三个密码杂凑函数 H1：｛0，1｝n→G1，H2：｛0，1｝n× ｛0，1｝n××G2→ ｛0，1｝n，H3：｛0，1｝n×｛0，1｝n×G21→ ｛0，1｝n，公 开 参 数 为 params ＝（G1，G2，q，e，P，PPub，H1，H2，H3）。

Extract－Partial－Private－Key：输入Params、主密钥s和用户身份IDU，KGC计算DU＝sQU，其中QU＝ H1（IDU）。

Generate－User－Keys：输入Params，用户U 选择一个随机数xU∈作为秘密值，计算公钥PKU＝xUP。

Set－Private－Keys：输入Params、秘密值xU和部分私钥DU，输出用户完整私钥SU＝（DU，xU）。

Signcrypt：发送者为A，接收者为B，签密如下：

（1）A随机选择一个数k∈Z＊q，计算R＝kP。

（2）计算密文：首先计算u＝e（DA，QB），再计算密文y＝H2（IDA，IDB，R，kPKB，xAPKB，u）⊕m。

（3）计 算 签 名：首 先 计 算 h ＝ H3（IDA，y，PKA，R），再计算签名S＝DA＋（xA＋h）QA。

（4）发送签密消息σ＝ （y，R，S）给B。

Unsigncrypt：

（1）计算h＝ H3（IDA，y，PKA，R）。

（2）验证等式e（S，P）＝e（QA，PPub＋PKA＋hP）是否成立，成立，则通过验证，否则输出⊥。

（3）计算u ＝e（DB，QA），xBR ＝ xBkP ＝kPKB。

（4）计算m ＝ H2（IDA，IDB，R，xBR，xBPKA，u）⊕y。

3.2 对罗铭等人方案的攻击

伪造性攻击：

方法一：攻击者S任选x′A∈Z＊q，替换用户A的公钥为PK′A＝x′AP，要求签密预言机签密消息m，发送者为A，接收者为B，但是A的公钥已被替换为PK′A，于是签密预言机返回σ＊＝ （y＊，R＊，S＊），即 S＊＝ DA＋ （x′A＋h＊）QA，而h＊＝H3（IDA，y＊，PK′A，R＊）是可以公开计算的。于是攻击者S可以直接求出DA＝S＊－（x′A＋h＊）QA，知道部分私钥DA，攻击者S可以任意伪造A的签密。

方法二：设σ＊＝ （y＊，R＊，S＊）是发送者为A、接收者为B的对消息m＊的签密文。攻击者S作任一身份IDC的私钥询问得（DC，xC），提交σ＊作为发送者为A、接收者为C的某随机消息m′的签 密 文，其 中 m′ ＝ H2（IDA，IDC，R＊，xCR＊，xCPKA，u′）⊕y＊，u′＝e（DC，QA），显然σ＊能通过验证等式，伪造成功。

3.3 对罗铭等人方案的改进

把 h ＝ H3（IDA，y，PKA，R） 改 为 h ＝H3（IDB，y，PKB，R），把S＝DA＋（xA＋h）QA改为S＝DA＋（xA＋h＋k）QA，其它同原方案，解签密的验证等式相应地变成e（S，P）＝e（QA，PPub＋PKA＋hP＋R）。

4 对葛爱军等人方案的分析与改进

4.1 葛爱军等人的方案

（1）系统建立：输入安全参数k，产生两个素数p、q＞2k且q｜（p－1）。随机选择Z＊p的一个阶为q的生成元g，由g生成的子群记为G。PKG任意选主密钥x∈Z＊q并计算y＝gx（mod p）。选择三个Hash函数：H1：｛0，1｝＊×Z＊p→Zq，H2：｛0，1｝l×Zp＊→Zq，H3：Zp＊×Zp＊→ ｛0，1｝l，其中，l为消息的长度。系统公开参数params＝ （p，q，g，G，y，H1，H2，H3），主密钥msk＝x。

（2）密钥提取：给定一用户身份为ID，PKG随机选择s∈Zq＊，计算该用户的部分公钥PID＝w＝gs（mod p），部 分 私 钥 DID＝t ＝s＋xH1（ID，w）（mod q），用户接收到 （PID，DID）后，首先验证gDID＝PIDyH1（ID，PID）是否成立。若成立，用户再计算μID＝gZID（mod p），其中，zID∈Zq＊是用户自己随机选择的秘密值；否则，用户输出“拒绝”。最后输出用户的公钥PKID＝（PID，μID）、用户的私钥SKID＝ （DID，zID）。

（3）签密算法：输入消息m，假设接收者Bob的公钥PKB＝ （PB，μB），签密者Alice利用自己私钥SKA＝ （tA，zA）进行如下签密：

①随机选择r1、r2∈RZ＊q，计算c1＝gr1（mod p），c2＝gr2（mod p）。

②令u＝ H2（m，（wByH1（IDB，wB））r1，（μB）r1，c2，PKA，PKB），计算v1＝r1－uzA（mod q），v2＝r2－utA（mod q）。

③计算c＝m ⊕ H3（（μB）r1，（wByH1（IDB，wB））r1）。最后 Alice发送密文σ＝ （u，v1，v2，c）给接收者Bob。

（4）解签密算法：接收到签密文σ＝ （u，v1，v2，c）之后，Bob利用自己的私钥进行如下解签密：

① 解 密 消 息 m ＝ c ⊕ H3（（gv1μuA）zB，（gv1μuA）tB）。

② 验 证 u ＝ H2（m，（gv1μuA）tB，（gv1μuA）zB，gv2（wAyH1（IDA，wA））u，PKA，PKB）是 否 成 立，如 果等式成立，Bob接受该消息，否则输出“拒绝”。

4.2 对葛爱军等人方案的攻击

保密性攻击：

设σ＊＝（u＊，v＊1，v＊2，c＊）是发送者为A、接收者为B的对消息mb的挑战密文。考虑内部攻击者A，A计算r1＝v＊1＋u＊zA（mod q），从而可以直接计算mb＝c＊⊕H3（（μB）r1，（wByH1（IDB，wB））r1），从而知道挑战密文是m0还是m1。

4.3 对葛爱军等人方案的改进

增加U1＝μuA（mod p），U2＝ （wAyH1（IDA，wA））u（mod p），最后 Alice发送密文σ ＝ （U1，U2，v1，v2，c）给接收者Bob，其它同原方案。相应地解签密变成m ＝c⊕H3（（gv1U1）zB，（gv1U1）tB），验证等式变成判断U1＝μu′A（mod p）是否成立，其中u′＝ H2（m，（gv1U1）tB，（gv1U1）zB，gv2U2，PKA，PKB）。

5 对李鹏程等人方案的分析与改进

5.1 李鹏程等人的方案

（1）系统参数建立：取一个阶为素数q的加法循环群G1和阶为素数q的乘法循环群G2，G1的生成元为P，定义一个双线性映射e：G1×G1→G2。KGC任意选主密钥s∈Z＊q并计算主公钥P0＝sP ∈G1，KGC预计算g＝e（P，P）∈G2。KGC选择三个Hash函数：H1：｛0，1｝＊→Z＊q，H2：G2→｛0，1｝n，H3：｛0，1｝n×G22×G21→Z＊q。系统公开参 数 （G1，G2，q，e，P，P0，g，H1，H2，H3，n），n 为消息的比特长度。

（2）提取部分私钥：对用户Ui，KGC计算Qi＝H1（IDi）∈Z＊q（IDi∈｛0，1｝＊），部分私钥Di＝（s＋Qi）－1P ∈G1。KGC将 部 分 私钥Di通过安全信道传送给用户Ui。

（3）生成用户公钥：用户Ui随机选择一个秘密值xi∈Z＊q，得到公钥Pi＝〈Xi，Yi〉＝〈gxi，xi（P0＋QiP）〉∈ （G2，G1）。

（4）生成用户私钥：用户Ui得到私钥Si＝〈xi，Di〉∈（Z＊q，G1）。

用户在执行上述两个算法中的秘密值xi必须保持一致。

（5）签密：假设签密方为A，解签密方为B；签密消息的长度将通过某种压缩方法压缩到长度n。

①A任意选择一个随机值k∈Z＊q并计算T＝k（P0＋QBP）∈G1。

②A 计算密文C ＝m ⊕H2（XkB）∈ ｛0，1｝n。

③计算 U ＝ H3（C‖XA‖XB‖YA‖T）∈Z＊q。

④A 计算V ＝ （xA＋U）－1DA∈G1。

A通过公开信道将签密〈C，T，V〉发送给解签密方B。

（6）解签密：B在接收到A 签密＜C，T，V＞后按以下算法验证并解密消息：

①B计算U ＝ H3（C‖XA‖XB‖YA‖T）∈Z＊q。

②验证等式g＝e（V，YA＋U（P0＋QAP））是否成立，如果不成立则立即终止验证过程。

③B 解密消息m ＝C⊕H2（e（xBT，DB））。

5.2 对李鹏程等人方案的攻击

（1）保密性攻击：

设σ＊＝（C＊，T＊，V＊）是发送者为A、接收者为B的对消息mb的挑战密文。攻击者S任取一身份IDc，作IDc的私钥询问得到SC＝（xC，DC），S 设 C′ ＝ C＊，T′ ＝ T＊，计 算 U′ ＝H3（C＊‖XC‖XB‖YC‖T＊），V′ ＝ （xC＋U′）－1DC，要求挑战者解密σ′＝ （C＊，T＊，V′），显然σ′是发送者为C、接收者为B的对消息mb的密文，解密结果为mb，从而知道挑战密文是m0还是m1。

（2）伪造性攻击：

攻击者S任选x′A∈Z＊q，替换用户A的公钥为P′A＝ 〈X′A，Y′A〉＝ 〈gx′A，x′A（P0＋QAP）〉，要求签密预言机签密消息m，发送者为A，接收者为B，但是A的公钥已被替换为P′A。于是签密预言机返回 σ＊＝ （C＊，T＊，V＊），即 V＊＝ （x′A＋U＊）－1DA，而 U＊＝ H3（C＊‖X′A‖XB‖ Y′A‖T＊）是可以公开计算的，于是攻击者S可以直接求出DA＝V＊（x′A＋U＊）。因为知道部分私钥DA，于是攻击者S可以任意伪造A的签密。

5.3 对李鹏程等人方案的改进

把C＝m⊕H2（XkB）∈｛0，1｝n改为C＝m⊕H2（XkB，XA）∈ ｛0，1｝n，增加T1＝k（P0＋QAP）∈G1，把V ＝ （xA＋U）－1DA∈G1改为V＝ （xA＋U＋k）－1DA∈G1，其它同原方案，最后A 通过公开信道将签密｛C，T，T1，V｝发送给解签密方B。相应地验证等式变成g ＝e（V，YA＋T1＋U（P0＋QAP）），解 密 变 成 m ＝ C ⊕ H2（e（xBT，DB），XA）。

6 对王星等人方案的分析与改进

6.1 王星等人方案

（1）系统建立：给定安全参数k，由KGC选取合适的双线性映射e：G1×G1→G2，并选取四个安全哈希函数 H1：｛0，1｝＊→G1，H2：｛0，1｝＊→ ｛0，1｝n，H3：｛0，1｝＊→Z＊q，H4：｛0，1｝＊→Z＊q。KGC随机选取主密钥s∈Z＊q并计算主公钥PPub＝sP。选取安全的对称加密算法（E，D），公开系 统 参 数 params ＝ （G1，G2，q，e，P，PPub，H1，H2，H3，H4，E，D）。

（2）部分私钥提取：给定用户身份ID，任何人都能够计算QID＝H1（ID），并由KGC计算用户部分私钥SID＝sH1（ID），通过安全信道将部分私钥传给用户。

（3）选取秘密值：用户随机地选取x∈Z＊q作为自己的秘密值。

（4）设置用户公钥：用户计算并发布自身的公钥PK＝xP，该公钥不需要使用公钥证书进行认证。

（5）设置完整私钥：用户的完整私钥设置为（SID，x）。

（6）签密：假设发送方A的身份信息为IDA，公钥为 （QA，PKA），私钥为 （SA，xA），接收方 B的身份信息为IDB，公钥为 （QB，PKB），私钥为（SB，xB）。A执行以下步骤对消息m进行签密：

①随机选取r∈Z＊q，计算R＝rP，T＝e（PPub，QB）r，W ＝rPKB。

②计算 K ＝ H2（R，T，W ，IDA，IDB）。

③计算c＝EK（m）。

④计算u＝H3（R，c，IDA，PKA），v＝H4（R，c，IDA，PKA）。

⑤计算V ＝ （uxA＋r）QA＋vSA。

A输出消息m 的密文为σ＝ （R，c，V）。

（7）解签密：B 在收到密文σ＝ （R，c，V）后，执行以下操作对密文进行解签密：

①计算u＝H3（R，c，IDA，PKA），v＝H4（R，c，IDA，PKA）。

②验证等式e（V，P）＝e（R＋uPA＋vPPub，QA）是否成立，如果等式成立，接受密文为合法密文，算法继续执行。否则，密文为非法密文，解签密算法终止。

③计算T＝e（R，SB），W ＝xBR ，并计算对称加密所使用的密钥 K＝H2（R，T，W，IDA，IDB）。

④恢复出消息m＝DK（c）。

6.2 对王星等人方案的攻击

伪造性攻击：

设σ＊＝ （R＊，c＊，V＊）是发送者为A、接收者为B对消息m＊的签密文。攻击者S作任一身份IDC的私钥询问得 （SC，xC），提交σ＊作为发送者为A、接收者为C的某随机消息m′的签密文，其中 m′ ＝ DK′（c＊），K′ ＝ H2（R＊，e（R＊，SC），xCR＊，IDA，IDC），显然σ＊能通过验证等式，伪造成功。

6.3 对王星等人方案的改进

把u＝ H3（R，c，IDA，PKA）改为u＝ H3（R，c，IDB，PKB），v＝ H4（R，c，IDA，PKA）改为v ＝H4（R，c，IDB，PKB），其它同原方案。

7 改进方案的安全性分析

限于篇幅，本文仅对定理1给出安全性证明，证明的方法类似文献［4］。

证明 设区分者B接收一个随机的GBDH问题的实例 （P，aP，bP，cP），a、b、c∈Zq＊，a、b、c的具体值未知，要求B在DBDH预言机的帮助下计算e （P，P ）abc。首先，B设PPub＝aP，将系统参数传 给 A。B 维 护 七 张 表 L1，L2，L3，L4，LK，LSC，LDSC，分别用于记录A 对预言机 Hi（i＝1，2，3，4）、公钥询问预言机、签密预言机和解签密预言机的询问。表的初始值为空，下面详细叙述这些表的建立过程。

H1询问：B 首先从 ｛1，2，…，q1｝中选取一个随机数λ，假设A不会作重复询问。对于A的第i次询问，若i＝λ，返回QIDλ＝bP ，把 （λ，IDλ，⊥）放入表L1；否则随机选取ri∈Z＊q，并设QIDi＝riP ，把 （i，IDi，ri）放入表L1。

部分私钥询问：假设A在此之前已经询问过H1。如果IDi＝IDλ，B失败并终止模拟；否则，在表L1中查找对应的条目，返回SIDi＝riaP。

公钥询问：如果 （IDi，PKi，xi）在表LK中，返回此PKi；否则，随机选取xi∈Z＊q作为秘密值，计算公钥PKi＝xiP，返回该公钥并更新表LK。

替换公钥询问：输入 （IDi，PK′i），B 用 （IDi，PKi，⊥）更新表LK。

私钥询问：假设A在此之前已经询问过H1。如果IDi＝IDλ，B失败并终止模拟；否则，B在表LK中查找IDi对应的条目，如果没找到就作公钥询问，返回 （xi，riaP）。

H3询 问：如 果 （R，c，IDB，PKB，ti）在 表 L3中，返回此ti；否则，随机选取ti∈Z＊q，返回ti并

限于篇幅，本文仅对王星等人的改进方案进行安全性分析，其它改进方案可以类似处理。以下简称对王星等人的改进方案为改进方案。

定理1 （类型I攻击者的保密性）：在随机预言机模型中，若存在一个类型I攻击者AI能够以不可忽略的概率在多项式时间内成功攻击本文的改进方案的保密性，他最多能进行qi次Hi（i＝1，2，3，4）询问，qX次部分私钥询问，qSK次私钥询问，qPK次公钥询问，qR－PK次替换公钥询问，qSC次签密询问和qDSC次解签密询问，则存在一个区分者B利用A可以以不可忽略的概率在多项式时间内成功解决GBDH问题。更新表L3。

H4询 问：如 果 （R，c，IDB，PKB，si）在 表 L4中，返回此si；否则，随机选取si∈Zq＊，返回si并更新表L4。

H2询 问：如 果 （R，T，W ，IDA，IDB，hi）在 表L2中，返回此hi；否则，如下处理：

（1）用元组 （aP，bP，cP，T）检验 DBDH 预言机的输出是否为1，如果是，则B成功计算出e （P，P ）abc＝T，返回T并终止模拟。

（2）B 遍历L2中形如 （R，＊，W ，IDA，IDB，hi）的元组，对不同的hi，用元组 （aP，bP，R，T）检验DBDH预言机的输出是否为1，注意这时IDB＝IDλ，如果这样的元组存在，返回该hi，并用T替换元组中的＊。

（3）B 遍历L2中形如 （R，T，＊，IDA，IDB，hi）的元组，测试其中的R，判断e（R，PKB）＝e（P，W）是否成立，如果这样的元组存在，返回该hi，并用W 替换元组中的＊。

（4）如果B到达这一步，B随机取一个hi∈｛0，1｝n，把 （R，T，W ，IDA，IDB，hi）加入表L2。

签密 询 问：对每 一 个 新 的 询 问 （m，IDA，IDB），如果IDA≠IDλ，这时B由于可以得到IDA的私钥，于是B只需按正常方式生成签密文，并返回给A；如果IDA＝IDλ，B如下处理：

（1）B产生三个随机数x1、x2、x3∈Z＊q，设置R＝x3P－（x1PKλ＋x2PPub），在表L1中查找IDB得rB，计算T＝e（R，rBPPub）。

（2）B 遍历L2中形如 （R，T，W ，IDλ，IDB，hi）的元组，若有某个W 使得e（R，PKB）＝e（P，W），则用此W 值计算K ＝H2（R，T，W，IDλ，IDB），计算c＝EK（m）；否则，随机取一个hi∈ ｛0，1｝n，计算c＝Ehi（m），并把 （R，T，＊，IDλ，IDB，hi）加入表L2。

（3）B 定义x1＝ H3（R，c，IDB，PKB），x2＝H4（R，c，IDB，PKB），并 把 元 组 （R，c，IDB，PKB，x1）加入表L3，把元组 （R，c，IDB，PKB，x2）加入表L4，如果表L3和L4已经存在该元组，则B失败并终止模拟；否则，B计算V ＝x3bP，返回σ＝（R，c，V）。

解签密询问：对每一个新的询问 （R，c，V，IDA，IDB），B首先执行验证算法，如果验证不通过，B返回⊥并停止；否则，表示验证通过，要求B返回m，假如IDB≠IDλ，则B由于可以得到IDB的私钥，所以很容易就返回m给A；否则，IDB＝IDλ，B如下处理：

（1）B计算W ＝xBR，如果IDB的公钥被替换，则xB由攻击者提供，否则通过查找LK表获得。

（2）由于B得不到IDB的私钥，于是B遍历L2，寻找元组 （R，T，W，IDA，IDλ，hi），测试其中的R和T，看是否能使对元组 （aP，bP，R，T）的DBDH询问预言机输出1成立，假如这样的元组存在，则正确的T值被找到，B就用该元组对应的hi值解密，返回m。

（3）假如B执行到此，则B随机取一个hi∈｛0，1｝n，用 此hi解 密 并 把 元 组 （R，＊，W，IDA，IDλ，hi）放入L2。

最终，A输出两个消息 （m0，m1）和两个身份ID＊A和ID＊B。假如ID＊B≠IDλ，B失败并终止模拟；否则，B构造挑战签密文如下。B设置R＊＝cP，选择一个随机比特b和一个随机的h＊∈｛0，1｝n，计算c＊＝mb⊕h＊。计算V＊＝ （uxA＋r）QA＋vSA＝ （tixA＋c）rAP＋siSA＝tirAPKA＋rAR＊＋siSA，其中，ti由表L3获得，si由表L4获得，rA由表L1获得，PKA由表LK获得，SA由对ID＊A的部分私钥询问获得。返回σ＊＝（R＊，c＊，V＊）给A。

第二阶段，对A的询问回答同前。最终，A输出他的猜测值b′。A 不知道σ＊＝ （R＊，c＊，V＊）不是一个正确的密文，除非A用挑战元组 （R＊，T＊，W＊，IDA＊，IDλ）询问H2，如果 这种情 况发生，则由H2询问的第一步，B可以成功计算e （P，P ）abc，从而以不可忽略的优势解决了GBDH问题。

定理2 （类型II攻击者的保密性）：在随机预言机模型中，若存在一个类型II攻击者AII能够以不可忽略的概率在多项式时间内成功攻击本文的改进方案的保密性，他最多能进行qi次Hi（i＝1，2，3，4）询问，qSK次私钥询问，qPK次公钥询问，qSC次签密询问和qDSC次解签密询问，则存在一个区分者B利用A可以以不可忽略的概率在多项式时间内成功解决CDH问题。

定理3 （类型I攻击者的不可伪造性）：在随机预言机模型中，若存在一个类型I攻击者AI能够以不可忽略的概率在多项式时间内成功攻击本文的改进方案的不可伪造性，他最多能进行的预言机的询问次数同定理一，则存在一个区分者B利用A可以以不可忽略的概率在多项式时间内成功解决GDH′问题。

定理4 （类型II攻击者的不可伪造性）：在随机预言机模型中，若存在一个类型II攻击者AII能够以不可忽略的概率在多项式时间内成功攻击本文的改进方案的不可伪造性，他最多能进行的预言机的询问次数同定理2，则存在一个区分者B利用A可以以不可忽略的概率在多项式时间内成功解决CDH问题。

8 结束语

对四个无证书签密方案进行了密码分析，指出其中两个方案存在保密性攻击，三个方案存在伪造性攻击，给出了具体的攻击方法，并分别给出了改进方案，最后对改进方案进行了安全性证明。无证书签密在很多领域具有广阔的应用前景，我们期待着更多安全的无证书签密方案的出现。

［1］ Zheng Yu－liang.Digital signcryption or how to achieve cost（signature ＆encryption）＜＜cost（signature）＋cost（encryption）［C］∥Proc of Crypto，1997：165－179.

［2］ Shamir A.Identity－based cryptosystems and signature schemes［C］∥Proc of Crypto，1984：47－53.

［3］ Al－Riyami S S，Paterson K G.Certificateless public key cryptography［C］∥Proc of Asiacrypt，2003：452－473.

［4］ Barbosa M，Farshim P.Certificateless signcryption［C］∥Proc of the 3th ACM Symposium on Information，Computer and Communications Security，2008：369－372.

［5］ Wu Chen－huang，Chen Zhi－xiong.A new efficient certificateless signcryption scheme［C］∥Proc of the 2008International Symposium on Information Science and Engineering，2008：661－664.

［6］ Aranha D，Castro R，Lopez J，et al.Efficient certificateless signcryption［EB／OL］.［2009－03－21］.http：／／sbseg2008.inf.ufrgs.br／anais／data／pdf／st03＿01＿resumo.pdf.

［7］ Selvi S S D，Vivek S S，Rangan C P.Cryptanalysis of certificateless signcryption schemes and an efficient construction without pairing［C］∥Proc of the 5th China International Conference on Information Security and Cryptology，2009：75－92.

［8］ Selvi S S D，Vivek S S，Shukla D，et al.Efficient and provably secure certificateless multi－receiver signcryption［C］∥Proc of the 2nd Provable Security International Conference，2008：52－67.

［9］ Miao Song－qin，Zhang Fu－tai，Zhang Lei.Cryptanalysis of a certificateless multi－receiver signcryption scheme［C］∥Proc of 2010International Conference on Multimedia Information Networking and Security，2010：593－597.

［10］ Shim K A，Lee Y R.Security pitfalls of the certificateless signature and multi－receiver signcryption schemes［J］.Fundamenta Informaticae，2011，112（4）：365－376.

［11］ Li Fa－gen，Masaaki S，Tsuyoshi T.Certificateless hybrid signcryption［C］∥Proc of Information Security Practice and Experience，2009：112－123.

［12］ Selvi S S D，Vivek S S，Rangan C P.Certificateless KEM and Hybrid signcryption schemes revisited［C］∥Proc of the 6th Information Security Practice and Experience Conference，2010：294－307.

［13］ Jin Chun－hua，Li Xue－jun，Wei Peng－juan，et al.New certificateless hybrid signcryption［J］.Application Research of Computers，2011，28（9）：3527－3531.（in Chinese）

［14］ Liu Zhen－hua，Hu Yu－pu，Zhang Xiang－song，et al.Certificateless signcryption scheme in the standard model［J］.Information Sciences，2010，180（3）：452－464.

［15］ Weng Jian，Yao Guo－xiang，Deng Rober H，et al.Cryptanalysis of a certificateless signcryption scheme in the standard model［J］.Information Sciences，2011，181（3）：661－667.

［16］ Luo Ming，Zou Chun－hua，Xu Jian－feng.Certificateless broadcast signcryption with forward secrecy［C］∥Proc of the 7th International Conference on Computational Intelligence and Security，2011：910－914.

［17］ Luo Ming，He Guang－yu，Wen Ying－you，et al.Certificateless short signcryption scheme for 3Gnetwork［J］.Computer Engineering and Applications，2009，45（30）：6－9.（in Chinese）

［18］ Ge Ai－jun，Chen Shao－zhen.Certificateless signcryption scheme without bilinear pairings calculation［J］.Computer Engineering，2010，36（20）：147－149.（in Chinese）

［19］ Li Peng－cheng，He Ming－xing，Li Xiao.Improved certificateless digital signcryption scheme［J］.Computer Engineering and Applications，2010，46（27）：93－95.（in Chinese）

［20］ Wang Xing，Qian Hai－feng.Efficient certificateless signcryption scheme［J］.Computer Engineering and Applications，2011，47（20）：62－64.（in Chinese）

附中文参考文献：

［13］ 金春花，李学俊，魏鹏娟，等.新的无证书混合签密［J］.计算机应用研究，2011，28（9）：3527－3531.

［17］ 罗铭，何光宇，闻英友，等.适用于3G网络的无证书的短签密方案［J］.计算机工程与应用，2009，45（30）：6－9.

［18］ 葛爱军，陈少真.不含双线性对运算的无证书签密方案［J］.计算机工程，2010，36（20）：147－149.

［19］ 李鹏程，何明星，李虓.改进的无证书数字签密方案［J］.计算机工程与应用，2010，46（27）：93－95.

［20］ 王星，钱海峰.高效的无证书签密方案［J］.计算机工程与应用，2011，47（20）：62－64.