幾個(gè)無證書簽密方案的密碼分析與改進(jìn)＊

周才學(xué)

（九江學(xué)院信息科學(xué)與技術(shù)學(xué)院，江西 九江332005）

1 引言

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

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

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

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

2 基本概念

2.1 雙線性對(duì)

設(shè)G1是素?cái)?shù)q階加法循環(huán)群，G2是同階乘法循環(huán)群。映射e：G1×G1→G2稱作雙線性對(duì)，如果該映射具有以下三個(gè)性質(zhì)：

（1）雙線性性：對(duì)任意的P、Q ∈G1，a、b∈Zq，都有e （aP，bQ）＝e （P，Q ）ab；

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

（3）可計(jì)算性：對(duì)任意的P、Q∈G1，存在一個(gè)有效的算法計(jì)算e （P，Q）。

2.2 困難問題

定義1 BDH（Bilinear Diffie－Hellman）問題：已知 （P，aP，bP，cP），a、b、c∈，a、b、c的具體值未知，要求計(jì)算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預(yù)言機(jī)的幫助下計(jì)算e （P，P ）abc。

定義 4 CDH （Computational Diffie－Hellman）問題：已知G1中的 （P，aP，bP ），a、b∈Zq，a、b的具體值未知，要求計(jì)算abP。

定義5 GDH′問題［4］：已知G1中的 （P，aP，bP），a、b∈Zq，a、b的具體值未知，要求在DBDH預(yù)言機(jī)的幫助下計(jì)算abP。

2.3 無證書簽密方案的安全模型

在無證書密碼體制中，因?yàn)闆]有證書來對(duì)用戶的公鑰進(jìn)行認(rèn)證，這樣攻擊者就可以把用戶的公鑰替換為自己任意選定的值，所以無證書密碼體制存在兩類攻擊者［3］：第I類攻擊者AI，他不知道系統(tǒng)主密鑰，但是他可以替換任意用戶的公鑰；第II類攻擊者AII，他知道系統(tǒng)主密鑰，所以他可以計(jì)算出每個(gè)用戶的部分私鑰，但是他不可以替換用戶的公鑰。在實(shí)際應(yīng)用中，AI模擬的是除PKG之外的攻擊者，AII模擬的是惡意PKG的非法攻擊。

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

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

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

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

①Hash詢問：Adv1可以對(duì)任何輸入進(jìn)行Hash詢問。

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

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

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

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

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

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

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

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

（5）最后，Adv1輸出一個(gè)值j′作為對(duì)j的猜測(cè)，若j′＝j(luò)，Adv1贏得游戲。

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

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

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

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

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

（5）最后，Adv2輸出一個(gè)值j′作為對(duì)j的猜測(cè)，若j′＝j(luò)，Adv2贏得游戲。

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

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

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

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

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

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

3 對(duì)羅銘等人方案的分析與改進(jìn)

3.1 羅銘等人的方案

Setup：KGC（Key Generation Center）隨機(jī)選擇一個(gè)生成元P∈G1，雙線性映射e：G1×G1→G2，選取主密鑰s∈并計(jì)算主公鑰PPub＝sP，再選擇三個(gè)密碼雜湊函數(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計(jì)算DU＝sQU，其中QU＝ H1（IDU）。

Generate－User－Keys：輸入Params，用戶U 選擇一個(gè)隨機(jī)數(shù)xU∈作為秘密值，計(jì)算公鑰PKU＝xUP。

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

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

（1）A隨機(jī)選擇一個(gè)數(shù)k∈Z＊q，計(jì)算R＝kP。

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

（3）計(jì) 算 簽 名：首 先 計(jì) 算 h ＝ H3（IDA，y，PKA，R），再計(jì)算簽名S＝DA＋（xA＋h）QA。

（4）發(fā)送簽密消息σ＝ （y，R，S）給B。

Unsigncrypt：

（1）計(jì)算h＝ H3（IDA，y，PKA，R）。

（2）驗(yàn)證等式e（S，P）＝e（QA，PPub＋PKA＋hP）是否成立，成立，則通過驗(yàn)證，否則輸出⊥。

（3）計(jì)算u ＝e（DB，QA），xBR ＝ xBkP ＝kPKB。

（4）計(jì)算m ＝ H2（IDA，IDB，R，xBR，xBPKA，u）⊕y。

3.2 對(duì)羅銘等人方案的攻擊

偽造性攻擊：

方法一：攻擊者S任選x′A∈Z＊q，替換用戶A的公鑰為PK′A＝x′AP，要求簽密預(yù)言機(jī)簽密消息m，發(fā)送者為A，接收者為B，但是A的公鑰已被替換為PK′A，于是簽密預(yù)言機(jī)返回σ＊＝ （y＊，R＊，S＊），即 S＊＝ DA＋ （x′A＋h＊）QA，而h＊＝H3（IDA，y＊，PK′A，R＊）是可以公開計(jì)算的。于是攻擊者S可以直接求出DA＝S＊－（x′A＋h＊）QA，知道部分私鑰DA，攻擊者S可以任意偽造A的簽密。

方法二：設(shè)σ＊＝ （y＊，R＊，S＊）是發(fā)送者為A、接收者為B的對(duì)消息m＊的簽密文。攻擊者S作任一身份IDC的私鑰詢問得（DC，xC），提交σ＊作為發(fā)送者為A、接收者為C的某隨機(jī)消息m′的簽 密 文，其 中 m′ ＝ H2（IDA，IDC，R＊，xCR＊，xCPKA，u′）⊕y＊，u′＝e（DC，QA），顯然σ＊能通過驗(yàn)證等式，偽造成功。

3.3 對(duì)羅銘等人方案的改進(jìn)

把 h ＝ H3（IDA，y，PKA，R） 改 為 h ＝H3（IDB，y，PKB，R），把S＝DA＋（xA＋h）QA改為S＝DA＋（xA＋h＋k）QA，其它同原方案，解簽密的驗(yàn)證等式相應(yīng)地變成e（S，P）＝e（QA，PPub＋PKA＋hP＋R）。

4 對(duì)葛愛軍等人方案的分析與改進(jìn)

4.1 葛愛軍等人的方案

（1）系統(tǒng)建立：輸入安全參數(shù)k，產(chǎn)生兩個(gè)素?cái)?shù)p、q＞2k且q｜（p－1）。隨機(jī)選擇Z＊p的一個(gè)階為q的生成元g，由g生成的子群記為G。PKG任意選主密鑰x∈Z＊q并計(jì)算y＝gx（mod p）。選擇三個(gè)Hash函數(shù)：H1：｛0，1｝＊×Z＊p→Zq，H2：｛0，1｝l×Zp＊→Zq，H3：Zp＊×Zp＊→ ｛0，1｝l，其中，l為消息的長(zhǎng)度。系統(tǒng)公開參數(shù)params＝ （p，q，g，G，y，H1，H2，H3），主密鑰msk＝x。

（2）密鑰提?。航o定一用戶身份為ID，PKG隨機(jī)選擇s∈Zq＊，計(jì)算該用戶的部分公鑰PID＝w＝gs（mod p），部 分 私 鑰 DID＝t ＝s＋xH1（ID，w）（mod q），用戶接收到 （PID，DID）后，首先驗(yàn)證gDID＝PIDyH1（ID，PID）是否成立。若成立，用戶再計(jì)算μID＝gZID（mod p），其中，zID∈Zq＊是用戶自己隨機(jī)選擇的秘密值；否則，用戶輸出“拒絕”。最后輸出用戶的公鑰PKID＝（PID，μID）、用戶的私鑰SKID＝ （DID，zID）。

（3）簽密算法：輸入消息m，假設(shè)接收者Bob的公鑰PKB＝ （PB，μB），簽密者Alice利用自己私鑰SKA＝ （tA，zA）進(jìn)行如下簽密：

①隨機(jī)選擇r1、r2∈RZ＊q，計(jì)算c1＝gr1（mod p），c2＝gr2（mod p）。

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

③計(jì)算c＝m ⊕ H3（（μB）r1，（wByH1（IDB，wB））r1）。最后 Alice發(fā)送密文σ＝ （u，v1，v2，c）給接收者Bob。

（4）解簽密算法：接收到簽密文σ＝ （u，v1，v2，c）之后，Bob利用自己的私鑰進(jìn)行如下解簽密：

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

② 驗(yàn) 證 u ＝ H2（m，（gv1μuA）tB，（gv1μuA）zB，gv2（wAyH1（IDA，wA））u，PKA，PKB）是 否 成 立，如 果等式成立，Bob接受該消息，否則輸出“拒絕”。

4.2 對(duì)葛愛軍等人方案的攻擊

保密性攻擊：

設(shè)σ＊＝（u＊，v＊1，v＊2，c＊）是發(fā)送者為A、接收者為B的對(duì)消息mb的挑戰(zhàn)密文。考慮內(nèi)部攻擊者A，A計(jì)算r1＝v＊1＋u＊zA（mod q），從而可以直接計(jì)算mb＝c＊⊕H3（（μB）r1，（wByH1（IDB，wB））r1），從而知道挑戰(zhàn)密文是m0還是m1。

4.3 對(duì)葛愛軍等人方案的改進(jìn)

增加U1＝μuA（mod p），U2＝ （wAyH1（IDA，wA））u（mod p），最后 Alice發(fā)送密文σ ＝ （U1，U2，v1，v2，c）給接收者Bob，其它同原方案。相應(yīng)地解簽密變成m ＝c⊕H3（（gv1U1）zB，（gv1U1）tB），驗(yàn)證等式變成判斷U1＝μu′A（mod p）是否成立，其中u′＝ H2（m，（gv1U1）tB，（gv1U1）zB，gv2U2，PKA，PKB）。

5 對(duì)李鵬程等人方案的分析與改進(jìn)

5.1 李鵬程等人的方案

（1）系統(tǒng)參數(shù)建立：取一個(gè)階為素?cái)?shù)q的加法循環(huán)群G1和階為素?cái)?shù)q的乘法循環(huán)群G2，G1的生成元為P，定義一個(gè)雙線性映射e：G1×G1→G2。KGC任意選主密鑰s∈Z＊q并計(jì)算主公鑰P0＝sP ∈G1，KGC預(yù)計(jì)算g＝e（P，P）∈G2。KGC選擇三個(gè)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 為消息的比特長(zhǎng)度。

（2）提取部分私鑰：對(duì)用戶Ui，KGC計(jì)算Qi＝H1（IDi）∈Z＊q（IDi∈｛0，1｝＊），部分私鑰Di＝（s＋Qi）－1P ∈G1。KGC將 部 分 私鑰Di通過安全信道傳送給用戶Ui。

（3）生成用戶公鑰：用戶Ui隨機(jī)選擇一個(gè)秘密值xi∈Z＊q，得到公鑰Pi＝〈Xi，Yi〉＝〈gxi，xi（P0＋QiP）〉∈ （G2，G1）。

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

用戶在執(zhí)行上述兩個(gè)算法中的秘密值xi必須保持一致。

（5）簽密：假設(shè)簽密方為A，解簽密方為B；簽密消息的長(zhǎng)度將通過某種壓縮方法壓縮到長(zhǎng)度n。

①A任意選擇一個(gè)隨機(jī)值k∈Z＊q并計(jì)算T＝k（P0＋QBP）∈G1。

②A 計(jì)算密文C ＝m ⊕H2（XkB）∈ ｛0，1｝n。

③計(jì)算 U ＝ H3（C‖XA‖XB‖YA‖T）∈Z＊q。

④A 計(jì)算V ＝ （xA＋U）－1DA∈G1。

A通過公開信道將簽密〈C，T，V〉發(fā)送給解簽密方B。

（6）解簽密：B在接收到A 簽密＜C，T，V＞后按以下算法驗(yàn)證并解密消息：

①B計(jì)算U ＝ H3（C‖XA‖XB‖YA‖T）∈Z＊q。

②驗(yàn)證等式g＝e（V，YA＋U（P0＋QAP））是否成立，如果不成立則立即終止驗(yàn)證過程。

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

5.2 對(duì)李鵬程等人方案的攻擊

（1）保密性攻擊：

設(shè)σ＊＝（C＊，T＊，V＊）是發(fā)送者為A、接收者為B的對(duì)消息mb的挑戰(zhàn)密文。攻擊者S任取一身份IDc，作IDc的私鑰詢問得到SC＝（xC，DC），S 設(shè) C′ ＝ C＊，T′ ＝ T＊，計(jì) 算 U′ ＝H3（C＊‖XC‖XB‖YC‖T＊），V′ ＝ （xC＋U′）－1DC，要求挑戰(zhàn)者解密σ′＝ （C＊，T＊，V′），顯然σ′是發(fā)送者為C、接收者為B的對(duì)消息mb的密文，解密結(jié)果為mb，從而知道挑戰(zhàn)密文是m0還是m1。

（2）偽造性攻擊：

攻擊者S任選x′A∈Z＊q，替換用戶A的公鑰為P′A＝ 〈X′A，Y′A〉＝ 〈gx′A，x′A（P0＋QAP）〉，要求簽密預(yù)言機(jī)簽密消息m，發(fā)送者為A，接收者為B，但是A的公鑰已被替換為P′A。于是簽密預(yù)言機(jī)返回 σ＊＝ （C＊，T＊，V＊），即 V＊＝ （x′A＋U＊）－1DA，而 U＊＝ H3（C＊‖X′A‖XB‖ Y′A‖T＊）是可以公開計(jì)算的，于是攻擊者S可以直接求出DA＝V＊（x′A＋U＊）。因?yàn)橹啦糠炙借€DA，于是攻擊者S可以任意偽造A的簽密。

5.3 對(duì)李鵬程等人方案的改進(jìn)

把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。相應(yīng)地驗(yàn)證等式變成g ＝e（V，YA＋T1＋U（P0＋QAP）），解 密 變 成 m ＝ C ⊕ H2（e（xBT，DB），XA）。

6 對(duì)王星等人方案的分析與改進(jìn)

6.1 王星等人方案

（1）系統(tǒng)建立：給定安全參數(shù)k，由KGC選取合適的雙線性映射e：G1×G1→G2，并選取四個(gè)安全哈希函數(shù) H1：｛0，1｝＊→G1，H2：｛0，1｝＊→ ｛0，1｝n，H3：｛0，1｝＊→Z＊q，H4：｛0，1｝＊→Z＊q。KGC隨機(jī)選取主密鑰s∈Z＊q并計(jì)算主公鑰PPub＝sP。選取安全的對(duì)稱加密算法（E，D），公開系 統(tǒng) 參 數(shù) params ＝ （G1，G2，q，e，P，PPub，H1，H2，H3，H4，E，D）。

（2）部分私鑰提?。航o定用戶身份ID，任何人都能夠計(jì)算QID＝H1（ID），并由KGC計(jì)算用戶部分私鑰SID＝sH1（ID），通過安全信道將部分私鑰傳給用戶。

（3）選取秘密值：用戶隨機(jī)地選取x∈Z＊q作為自己的秘密值。

（4）設(shè)置用戶公鑰：用戶計(jì)算并發(fā)布自身的公鑰PK＝xP，該公鑰不需要使用公鑰證書進(jìn)行認(rèn)證。

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

（6）簽密：假設(shè)發(fā)送方A的身份信息為IDA，公鑰為 （QA，PKA），私鑰為 （SA，xA），接收方 B的身份信息為IDB，公鑰為 （QB，PKB），私鑰為（SB，xB）。A執(zhí)行以下步驟對(duì)消息m進(jìn)行簽密：

①隨機(jī)選取r∈Z＊q，計(jì)算R＝rP，T＝e（PPub，QB）r，W ＝rPKB。

②計(jì)算 K ＝ H2（R，T，W ，IDA，IDB）。

③計(jì)算c＝EK（m）。

④計(jì)算u＝H3（R，c，IDA，PKA），v＝H4（R，c，IDA，PKA）。

⑤計(jì)算V ＝ （uxA＋r）QA＋vSA。

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

（7）解簽密：B 在收到密文σ＝ （R，c，V）后，執(zhí)行以下操作對(duì)密文進(jìn)行解簽密：

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

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

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

④恢復(fù)出消息m＝DK（c）。

6.2 對(duì)王星等人方案的攻擊

偽造性攻擊：

設(shè)σ＊＝ （R＊，c＊，V＊）是發(fā)送者為A、接收者為B對(duì)消息m＊的簽密文。攻擊者S作任一身份IDC的私鑰詢問得 （SC，xC），提交σ＊作為發(fā)送者為A、接收者為C的某隨機(jī)消息m′的簽密文，其中 m′ ＝ DK′（c＊），K′ ＝ H2（R＊，e（R＊，SC），xCR＊，IDA，IDC），顯然σ＊能通過驗(yàn)證等式，偽造成功。

6.3 對(duì)王星等人方案的改進(jìn)

把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 改進(jìn)方案的安全性分析

限于篇幅，本文僅對(duì)定理1給出安全性證明，證明的方法類似文獻(xiàn)［4］。

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

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

部分私鑰詢問：假設(shè)A在此之前已經(jīng)詢問過H1。如果IDi＝IDλ，B失敗并終止模擬；否則，在表L1中查找對(duì)應(yīng)的條目，返回SIDi＝riaP。

公鑰詢問：如果 （IDi，PKi，xi）在表LK中，返回此PKi；否則，隨機(jī)選取xi∈Z＊q作為秘密值，計(jì)算公鑰PKi＝xiP，返回該公鑰并更新表LK。

替換公鑰詢問：輸入 （IDi，PK′i），B 用 （IDi，PKi，⊥）更新表LK。

私鑰詢問：假設(shè)A在此之前已經(jīng)詢問過H1。如果IDi＝IDλ，B失敗并終止模擬；否則，B在表LK中查找IDi對(duì)應(yīng)的條目，如果沒找到就作公鑰詢問，返回 （xi，riaP）。

H3詢 問：如 果 （R，c，IDB，PKB，ti）在 表 L3中，返回此ti；否則，隨機(jī)選取ti∈Z＊q，返回ti并

限于篇幅，本文僅對(duì)王星等人的改進(jìn)方案進(jìn)行安全性分析，其它改進(jìn)方案可以類似處理。以下簡(jiǎn)稱對(duì)王星等人的改進(jìn)方案為改進(jìn)方案。

定理1 （類型I攻擊者的保密性）：在隨機(jī)預(yù)言機(jī)模型中，若存在一個(gè)類型I攻擊者AI能夠以不可忽略的概率在多項(xiàng)式時(shí)間內(nèi)成功攻擊本文的改進(jìn)方案的保密性，他最多能進(jìn)行qi次Hi（i＝1，2，3，4）詢問，qX次部分私鑰詢問，qSK次私鑰詢問，qPK次公鑰詢問，qR－PK次替換公鑰詢問，qSC次簽密詢問和qDSC次解簽密詢問，則存在一個(gè)區(qū)分者B利用A可以以不可忽略的概率在多項(xiàng)式時(shí)間內(nèi)成功解決GBDH問題。更新表L3。

H4詢 問：如 果 （R，c，IDB，PKB，si）在 表 L4中，返回此si；否則，隨機(jī)選取si∈Zq＊，返回si并更新表L4。

H2詢 問：如 果 （R，T，W ，IDA，IDB，hi）在 表L2中，返回此hi；否則，如下處理：

（1）用元組 （aP，bP，cP，T）檢驗(yàn) DBDH 預(yù)言機(jī)的輸出是否為1，如果是，則B成功計(jì)算出e （P，P ）abc＝T，返回T并終止模擬。

（2）B 遍歷L2中形如 （R，＊，W ，IDA，IDB，hi）的元組，對(duì)不同的hi，用元組 （aP，bP，R，T）檢驗(yàn)DBDH預(yù)言機(jī)的輸出是否為1，注意這時(shí)IDB＝IDλ，如果這樣的元組存在，返回該hi，并用T替換元組中的＊。

（3）B 遍歷L2中形如 （R，T，＊，IDA，IDB，hi）的元組，測(cè)試其中的R，判斷e（R，PKB）＝e（P，W）是否成立，如果這樣的元組存在，返回該hi，并用W 替換元組中的＊。

（4）如果B到達(dá)這一步，B隨機(jī)取一個(gè)hi∈｛0，1｝n，把 （R，T，W ，IDA，IDB，hi）加入表L2。

簽密 詢 問：對(duì)每 一 個(gè) 新 的 詢 問 （m，IDA，IDB），如果IDA≠IDλ，這時(shí)B由于可以得到IDA的私鑰，于是B只需按正常方式生成簽密文，并返回給A；如果IDA＝IDλ，B如下處理：

（1）B產(chǎn)生三個(gè)隨機(jī)數(shù)x1、x2、x3∈Z＊q，設(shè)置R＝x3P－（x1PKλ＋x2PPub），在表L1中查找IDB得rB，計(jì)算T＝e（R，rBPPub）。

（2）B 遍歷L2中形如 （R，T，W ，IDλ，IDB，hi）的元組，若有某個(gè)W 使得e（R，PKB）＝e（P，W），則用此W 值計(jì)算K ＝H2（R，T，W，IDλ，IDB），計(jì)算c＝EK（m）；否則，隨機(jī)取一個(gè)hi∈ ｛0，1｝n，計(jì)算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計(jì)算V ＝x3bP，返回σ＝（R，c，V）。

解簽密詢問：對(duì)每一個(gè)新的詢問 （R，c，V，IDA，IDB），B首先執(zhí)行驗(yàn)證算法，如果驗(yàn)證不通過，B返回⊥并停止；否則，表示驗(yàn)證通過，要求B返回m，假如IDB≠IDλ，則B由于可以得到IDB的私鑰，所以很容易就返回m給A；否則，IDB＝IDλ，B如下處理：

（1）B計(jì)算W ＝xBR，如果IDB的公鑰被替換，則xB由攻擊者提供，否則通過查找LK表獲得。

（2）由于B得不到IDB的私鑰，于是B遍歷L2，尋找元組 （R，T，W，IDA，IDλ，hi），測(cè)試其中的R和T，看是否能使對(duì)元組 （aP，bP，R，T）的DBDH詢問預(yù)言機(jī)輸出1成立，假如這樣的元組存在，則正確的T值被找到，B就用該元組對(duì)應(yīng)的hi值解密，返回m。

（3）假如B執(zhí)行到此，則B隨機(jī)取一個(gè)hi∈｛0，1｝n，用 此hi解 密 并 把 元 組 （R，＊，W，IDA，IDλ，hi）放入L2。

最終，A輸出兩個(gè)消息 （m0，m1）和兩個(gè)身份ID＊A和ID＊B。假如ID＊B≠IDλ，B失敗并終止模擬；否則，B構(gòu)造挑戰(zhàn)簽密文如下。B設(shè)置R＊＝cP，選擇一個(gè)隨機(jī)比特b和一個(gè)隨機(jī)的h＊∈｛0，1｝n，計(jì)算c＊＝mb⊕h＊。計(jì)算V＊＝ （uxA＋r）QA＋vSA＝ （tixA＋c）rAP＋siSA＝tirAPKA＋rAR＊＋siSA，其中，ti由表L3獲得，si由表L4獲得，rA由表L1獲得，PKA由表LK獲得，SA由對(duì)ID＊A的部分私鑰詢問獲得。返回σ＊＝（R＊，c＊，V＊）給A。

第二階段，對(duì)A的詢問回答同前。最終，A輸出他的猜測(cè)值b′。A 不知道σ＊＝ （R＊，c＊，V＊）不是一個(gè)正確的密文，除非A用挑戰(zhàn)元組 （R＊，T＊，W＊，IDA＊，IDλ）詢問H2，如果 這種情 況發(fā)生，則由H2詢問的第一步，B可以成功計(jì)算e （P，P ）abc，從而以不可忽略的優(yōu)勢(shì)解決了GBDH問題。

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

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

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

8 結(jié)束語

對(duì)四個(gè)無證書簽密方案進(jìn)行了密碼分析，指出其中兩個(gè)方案存在保密性攻擊，三個(gè)方案存在偽造性攻擊，給出了具體的攻擊方法，并分別給出了改進(jìn)方案，最后對(duì)改進(jìn)方案進(jìn)行了安全性證明。無證書簽密在很多領(lǐng)域具有廣闊的應(yīng)用前景，我們期待著更多安全的無證書簽密方案的出現(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）

附中文參考文獻(xiàn)：

［13］ 金春花，李學(xué)俊，魏鵬娟，等.新的無證書混合簽密［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3527－3531.

［17］ 羅銘，何光宇，聞?dòng)⒂?，?適用于3G網(wǎng)絡(luò)的無證書的短簽密方案［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（30）：6－9.

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

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

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