周才學

（九江學院信息科學與技術學院，江西 九江332005）

1 引言

簽密的概念首先由Zheng［1］于1997年提出，它能在一個邏輯步驟內(nèi)同時實現(xiàn)加密和認證，而所需的計算和通信代價大大低于傳統(tǒng)的先簽名后加密方案。自從簽密被提出后，迅速成為研究熱點。

1984年，Shamir［2］提出了基于身份的密碼體制。在這種體制中，用戶的公鑰可由用戶的身份信息直接計算出來，從而省去了公鑰證書，簡化了公鑰的管理，自它被提出后，也迅速成為了研究熱點。但是，基于身份的密碼體制有一個天生的缺陷，就是存在密鑰托管問題，即可信中心知道所有用戶的私鑰。為解決此問題，2003年，Al－Riyami等人［3］提出了無證書密碼體制。在無證書密碼體制中，用戶的私鑰由兩部分組成，一部分由可信中心產(chǎn)生，另一部分由用戶自己生成。這樣就解決了密鑰托管問題，同時公鑰也不需要證書，因此這種密碼體制具有巨大的優(yōu)越性。

2008年，Barbosa等人［4］將無證書概念推廣到簽密，首次提出了無證書簽密的概念。同年Wu等人［5］、Aranha等人［6］基于雙線性對也各自提出一個方案。但Selvi等人［7］于2009年指出文獻［4～6］都是不安全的，他們給出了具體的攻擊方法并提出一個不使用雙線性對運算的無證書簽密方案。此后，人們又提出了多接收者無證書簽密［8～10］、無證書 混 合 簽 密［11～13］、標 準 模 型 下 的 無 證 書 簽密［14，15］和無證書廣播簽密［16］等方案。2009年，羅銘等人［17］提出一個適用于3G網(wǎng)絡的無證書的短簽密方案；2010年，葛愛軍等人［18］提出一個不含雙線性對運算的無證書簽密方案；李鵬程等人［19］提出一個改進的無證書數(shù)字簽密方案；2011年，王星等人［20］提出一個高效的無證書簽密方案。

本文對文獻［17～20］進行了安全性分析，分析表明，羅銘等人的方案存在偽造性攻擊；葛愛軍等人的方案存在保密性攻擊；李鵬程等人的方案存在保密性和偽造性攻擊；王星等人的方案存在偽造性攻擊。對每個方案分別進行了改進，并對改進方案進行了安全性證明。

2 基本概念

2.1 雙線性對

設G1是素數(shù)q階加法循環(huán)群，G2是同階乘法循環(huán)群。映射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，他不知道系統(tǒng)主密鑰，但是他可以替換任意用戶的公鑰；第II類攻擊者AII，他知道系統(tǒng)主密鑰，所以他可以計算出每個用戶的部分私鑰，但是他不可以替換用戶的公鑰。在實際應用中，AI模擬的是除PKG之外的攻擊者，AII模擬的是惡意PKG的非法攻擊。

無證書簽密方案在第I類攻擊者AI和第II類攻擊者AII下都需要滿足機密性和不可偽造性。下面分別以游戲的方式直觀地給出無證書簽密方案的安全模型。

定義6 類型I攻擊下的保密性：若不存在任何多項式有界的敵手Adv1以不可忽略優(yōu)勢贏得以下游戲，則稱該無證書簽密方案在適應性選擇密文攻擊下具有不可區(qū)分性（IND－CLSC－CCA2）。

（1）初始化：挑戰(zhàn)者C輸入安全參數(shù)k，運行Setup，并發(fā)送系統(tǒng)參數(shù)Params給敵手Adv1，保密主密鑰。

（2）尋找階段：敵手Adv1可以適應性地執(zhí)行多項式有界次的以下詢問：

①Hash詢問：Adv1可以對任何輸入進行Hash詢問。

②部分私鑰生成詢問：Adv1輸入一個身份ID，挑戰(zhàn)者C計算身份ID的部分私鑰SID并返回給Adv1。

③私鑰生成詢問：Adv1選擇一個身份ID，挑戰(zhàn)者C計算相應的私鑰skID并返回給Adv1。如果相應的公鑰被替換，則不允許詢問該預言機。這是因為挑戰(zhàn)者不知道相應的秘密值，所以不能提供完整私鑰。

④公鑰詢問：Adv1輸入身份ID，挑戰(zhàn)者C計算相應的公鑰pkID。

⑤替換公鑰詢問：在任何時間，Adv1選擇一個新的值pk′ID，替換原來的公鑰pkID。

⑥簽密詢問：Adv1選擇身份IDa、IDb和明文m，設ska為IDa的私鑰、pkb為IDb的公鑰，C計算σ ＝ Signcrypt（m，ska，pkb）并 將 結 果 σ 發(fā) 送 給Adv1。假如IDa的公鑰被替換，為了生成正確的回答，要求Adv1另外提供IDa的秘密值給C。

⑦解簽密詢問：Adv1選擇身份IDa、IDb和密文σ，設skb為IDb的私鑰、pka為IDa的公鑰，C計算 Unsigncrypt（σ，pka，skb），最后發(fā)送結果明文m或“失敗”給Adv1。如果IDb的公鑰被替換，為了生成正確的回答，要求Adv1另外提供IDb的秘密值給C。

（3）挑戰(zhàn)階段：Adv1生成兩個相同長度的明文m0、m1和希望挑戰(zhàn)的兩個身份ID＊a和ID＊b，ID＊b不能是已經(jīng)執(zhí)行過部分密鑰生成詢問或私鑰生成詢問的身份，C隨機選擇j∈ ｛0，1｝，計算σ＊＝Signcrypt（mj，ska，pkb） 并 將 結 果 σ＊發(fā) 送 給Adv1。

（4）猜測階段：Adv1像尋找階段一樣執(zhí)行多項式有界次的適應性的詢問，但不能對ID＊b執(zhí)行部分密鑰生成或私鑰生成詢問，也不能對密文σ＊、發(fā)送者ID＊a和接收者ID＊b執(zhí)行Unsigncrypt詢問，除非ID＊a或ID＊b的公鑰被替換。

（5）最后，Adv1輸出一個值j′作為對j的猜測，若j′＝j，Adv1贏得游戲。

定義7 類型II攻擊下的保密性：若不存在任何多項式有界的敵手Adv2以不可忽略的優(yōu)勢贏得以下游戲，則稱該無證書簽密方案在適應性選擇密文攻擊下具有不可區(qū)分性（IND－CLSC－CCA2）。

（1）初始化：挑戰(zhàn)者C輸入安全參數(shù)k，運行Setup算法，并發(fā)送params和主密鑰s給敵手Adv2。

（2）尋找階段：敵手Adv2可以執(zhí)行定義1中除“公鑰替換詢問”和“部分密鑰生成詢問”以外的所有查詢，查詢方法同定義1。

（3）挑戰(zhàn)階段：Adv2生成兩個相同長度的不同明文m0、m1和希望挑戰(zhàn)的兩個身份ID＊a和ID＊b，ID＊b不能是已經(jīng)執(zhí)行過私鑰生成詢問的身份，C隨機選擇j∈ ｛0，1｝，計算σ＊＝Signcrypt（mj，ska，pkb）并將結果σ＊發(fā)送給Adv2。

（4）猜測階段：Adv2像尋找階段一樣適應性地執(zhí)行多項式有界次的詢問，但不能對ID＊b執(zhí)行私鑰生成詢問，也不能對密文σ＊、發(fā)送者ID＊a和接收者ID＊b執(zhí)行Unsigncrypt詢問。

（5）最后，Adv2輸出一個值j′作為對j的猜測，若j′＝j，Adv2贏得游戲。

定義8 類型I攻擊下的不可偽造性：若不存在任何多項式有界的敵手Adv1以不可忽略的優(yōu)勢贏得以下游戲，則稱該無證書簽密方案在適應性選擇消息攻擊下具有不可偽造性（EUF－CLSCCMA）。

（1）初始化和尋找階段同定義1。

（2）Adv1輸出某發(fā)送者IDa（對應接收者為IDb）對某消息m 的簽密σ，且 （σ，IDa，IDb）不是簽密預言機產(chǎn)生的，也未對IDa進行過部分密鑰生成詢問或私鑰生成詢問，若Unsigncrypt（σ，pka，skb）的結果不是“錯誤”，則Adv1贏得游戲。

定義9 類型II攻擊下的不可偽造性：若不存在任何多項式有界的敵手Adv2以一個不可忽略的優(yōu)勢贏得以下游戲，則稱一個無證書簽密方案在適應性選擇消息攻擊下具有不可偽造性（EUFCLSC－CMA）。

（1）初始化和尋找階段同定義2。

（2）Adv2輸出某發(fā)送者IDa（對應接收者為IDb）對某消息m 的簽密σ，且 （σ，IDa，IDb）不是簽密預言機產(chǎn)生的，也未對IDa進行過私鑰生成詢問，若 Unsigncrypt（σ，pka，skb）的 結 果 不 是 “錯誤”，則Adv2贏得游戲。

3 對羅銘等人方案的分析與改進

3.1 羅銘等人的方案

Setup：KGC（Key Generation Center）隨機選擇一個生成元P∈G1，雙線性映射e：G1×G1→G2，選取主密鑰s∈并計算主公鑰PPub＝sP，再選擇三個密碼雜湊函數(shù) 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，公 開 參 數(shù) 為 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 選擇一個隨機數(shù)xU∈作為秘密值，計算公鑰PKU＝xUP。

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

Signcrypt：發(fā)送者為A，接收者為B，簽密如下：

（1）A隨機選擇一個數(shù)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）發(fā)送簽密消息σ＝ （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，發(fā)送者為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＊）是發(fā)送者為A、接收者為B的對消息m＊的簽密文。攻擊者S作任一身份IDC的私鑰詢問得（DC，xC），提交σ＊作為發(fā)送者為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）系統(tǒng)建立：輸入安全參數(shù)k，產(chǎn)生兩個素數(shù)p、q＞2k且q｜（p－1）。隨機選擇Z＊p的一個階為q的生成元g，由g生成的子群記為G。PKG任意選主密鑰x∈Z＊q并計算y＝gx（mod p）。選擇三個Hash函數(shù)：H1：｛0，1｝＊×Z＊p→Zq，H2：｛0，1｝l×Zp＊→Zq，H3：Zp＊×Zp＊→ ｛0，1｝l，其中，l為消息的長度。系統(tǒng)公開參數(shù)params＝ （p，q，g，G，y，H1，H2，H3），主密鑰msk＝x。

（2）密鑰提?。航o定一用戶身份為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發(fā)送密文σ＝ （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＊）是發(fā)送者為A、接收者為B的對消息mb的挑戰(zhàn)密文。考慮內(nèi)部攻擊者A，A計算r1＝v＊1＋u＊zA（mod q），從而可以直接計算mb＝c＊⊕H3（（μB）r1，（wByH1（IDB，wB））r1），從而知道挑戰(zhàn)密文是m0還是m1。

4.3 對葛愛軍等人方案的改進

增加U1＝μuA（mod p），U2＝ （wAyH1（IDA，wA））u（mod p），最后 Alice發(fā)送密文σ ＝ （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）系統(tǒng)參數(shù)建立：取一個階為素數(shù)q的加法循環(huán)群G1和階為素數(shù)q的乘法循環(huán)群G2，G1的生成元為P，定義一個雙線性映射e：G1×G1→G2。KGC任意選主密鑰s∈Z＊q并計算主公鑰P0＝sP ∈G1，KGC預計算g＝e（P，P）∈G2。KGC選擇三個Hash函數(shù)：H1：｛0，1｝＊→Z＊q，H2：G2→｛0，1｝n，H3：｛0，1｝n×G22×G21→Z＊q。系統(tǒng)公開參 數(shù) （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）。

用戶在執(zhí)行上述兩個算法中的秘密值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〉發(fā)送給解簽密方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＊）是發(fā)送者為A、接收者為B的對消息mb的挑戰(zhàn)密文。攻擊者S任取一身份IDc，作IDc的私鑰詢問得到SC＝（xC，DC），S 設 C′ ＝ C＊，T′ ＝ T＊，計 算 U′ ＝H3（C＊‖XC‖XB‖YC‖T＊），V′ ＝ （xC＋U′）－1DC，要求挑戰(zhàn)者解密σ′＝ （C＊，T＊，V′），顯然σ′是發(fā)送者為C、接收者為B的對消息mb的密文，解密結果為mb，從而知道挑戰(zhàn)密文是m0還是m1。

（2）偽造性攻擊：

攻擊者S任選x′A∈Z＊q，替換用戶A的公鑰為P′A＝ 〈X′A，Y′A〉＝ 〈gx′A，x′A（P0＋QAP）〉，要求簽密預言機簽密消息m，發(fā)送者為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｝發(fā)送給解簽密方B。相應地驗證等式變成g ＝e（V，YA＋T1＋U（P0＋QAP）），解 密 變 成 m ＝ C ⊕ H2（e（xBT，DB），XA）。

6 對王星等人方案的分析與改進

6.1 王星等人方案

（1）系統(tǒng)建立：給定安全參數(shù)k，由KGC選取合適的雙線性映射e：G1×G1→G2，并選取四個安全哈希函數(shù) 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），公開系 統(tǒng) 參 數(shù) 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）設置用戶公鑰：用戶計算并發(fā)布自身的公鑰PK＝xP，該公鑰不需要使用公鑰證書進行認證。

（5）設置完整私鑰：用戶的完整私鑰設置為（SID，x）。

（6）簽密：假設發(fā)送方A的身份信息為IDA，公鑰為 （QA，PKA），私鑰為 （SA，xA），接收方 B的身份信息為IDB，公鑰為 （QB，PKB），私鑰為（SB，xB）。A執(zhí)行以下步驟對消息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）后，執(zhí)行以下操作對密文進行解簽密：

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

②驗證等式e（V，P）＝e（R＋uPA＋vPPub，QA）是否成立，如果等式成立，接受密文為合法密文，算法繼續(xù)執(zhí)行。否則，密文為非法密文，解簽密算法終止。

③計算T＝e（R，SB），W ＝xBR ，并計算對稱加密所使用的密鑰 K＝H2（R，T，W，IDA，IDB）。

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

6.2 對王星等人方案的攻擊

偽造性攻擊：

設σ＊＝ （R＊，c＊，V＊）是發(fā)送者為A、接收者為B對消息m＊的簽密文。攻擊者S作任一身份IDC的私鑰詢問得 （SC，xC），提交σ＊作為發(fā)送者為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］。

證明 設區(qū)分者B接收一個隨機的GBDH問題的實例 （P，aP，bP，cP），a、b、c∈Zq＊，a、b、c的具體值未知，要求B在DBDH預言機的幫助下計算e （P，P ）abc。首先，B設PPub＝aP，將系統(tǒng)參數(shù)傳 給 A。B 維 護 七 張 表 L1，L2，L3，L4，LK，LSC，LDSC，分別用于記錄A 對預言機 Hi（i＝1，2，3，4）、公鑰詢問預言機、簽密預言機和解簽密預言機的詢問。表的初始值為空，下面詳細敘述這些表的建立過程。

H1詢問：B 首先從 ｛1，2，…，q1｝中選取一個隨機數(shù)λ，假設A不會作重復詢問。對于A的第i次詢問，若i＝λ，返回QIDλ＝bP ，把 （λ，IDλ，⊥）放入表L1；否則隨機選取ri∈Z＊q，并設QIDi＝riP ，把 （i，IDi，ri）放入表L1。

部分私鑰詢問：假設A在此之前已經(jīng)詢問過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在此之前已經(jīng)詢問過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能夠以不可忽略的概率在多項式時間內(nèi)成功攻擊本文的改進方案的保密性，他最多能進行qi次Hi（i＝1，2，3，4）詢問，qX次部分私鑰詢問，qSK次私鑰詢問，qPK次公鑰詢問，qR－PK次替換公鑰詢問，qSC次簽密詢問和qDSC次解簽密詢問，則存在一個區(qū)分者B利用A可以以不可忽略的概率在多項式時間內(nèi)成功解決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產(chǎn)生三個隨機數(shù)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已經(jīng)存在該元組，則B失敗并終止模擬；否則，B計算V ＝x3bP，返回σ＝（R，c，V）。

解簽密詢問：對每一個新的詢問 （R，c，V，IDA，IDB），B首先執(zhí)行驗證算法，如果驗證不通過，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執(zhí)行到此，則B隨機取一個hi∈｛0，1｝n，用 此hi解 密 并 把 元 組 （R，＊，W，IDA，IDλ，hi）放入L2。

最終，A輸出兩個消息 （m0，m1）和兩個身份ID＊A和ID＊B。假如ID＊B≠IDλ，B失敗并終止模擬；否則，B構造挑戰(zhàn)簽密文如下。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用挑戰(zhàn)元組 （R＊，T＊，W＊，IDA＊，IDλ）詢問H2，如果 這種情 況發(fā)生，則由H2詢問的第一步，B可以成功計算e （P，P ）abc，從而以不可忽略的優(yōu)勢解決了GBDH問題。

定理2 （類型II攻擊者的保密性）：在隨機預言機模型中，若存在一個類型II攻擊者AII能夠以不可忽略的概率在多項式時間內(nèi)成功攻擊本文的改進方案的保密性，他最多能進行qi次Hi（i＝1，2，3，4）詢問，qSK次私鑰詢問，qPK次公鑰詢問，qSC次簽密詢問和qDSC次解簽密詢問，則存在一個區(qū)分者B利用A可以以不可忽略的概率在多項式時間內(nèi)成功解決CDH問題。

定理3 （類型I攻擊者的不可偽造性）：在隨機預言機模型中，若存在一個類型I攻擊者AI能夠以不可忽略的概率在多項式時間內(nèi)成功攻擊本文的改進方案的不可偽造性，他最多能進行的預言機的詢問次數(shù)同定理一，則存在一個區(qū)分者B利用A可以以不可忽略的概率在多項式時間內(nèi)成功解決GDH′問題。

定理4 （類型II攻擊者的不可偽造性）：在隨機預言機模型中，若存在一個類型II攻擊者AII能夠以不可忽略的概率在多項式時間內(nèi)成功攻擊本文的改進方案的不可偽造性，他最多能進行的預言機的詢問次數(shù)同定理2，則存在一個區(qū)分者B利用A可以以不可忽略的概率在多項式時間內(nèi)成功解決CDH問題。

8 結束語

對四個無證書簽密方案進行了密碼分析，指出其中兩個方案存在保密性攻擊，三個方案存在偽造性攻擊，給出了具體的攻擊方法，并分別給出了改進方案，最后對改進方案進行了安全性證明。無證書簽密在很多領域具有廣闊的應用前景，我們期待著更多安全的無證書簽密方案的出現(xiàn)。

［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，F(xiàn)arshim P.Certificateless signcryption［C］∥Proc of the 3th ACM Symposium on Information，Computer and Communications Security，2008：369－372.

［5］ Wu Chen－h(huán)uang，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－h(huán)ua，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－h(huán)ua，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－h(huán)ua，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網(wǎng)絡的無證書的短簽密方案［J］.計算機工程與應用，2009，45（30）：6－9.

［18］ 葛愛軍，陳少真.不含雙線性對運算的無證書簽密方案［J］.計算機工程，2010，36（20）：147－149.

［19］ 李鵬程，何明星，李虓.改進的無證書數(shù)字簽密方案［J］.計算機工程與應用，2010，46（27）：93－95.

［20］ 王星，錢海峰.高效的無證書簽密方案［J］.計算機工程與應用，2011，47（20）：62－64.