劉 倩，范安東，張麗娜，張 愉

（1.成都理工大學a.管理科學學院；b.旅游與城鄉(xiāng)規(guī)劃學院，四川 成都 610059；2.西安科技大學計算機科學與技術學院，陜西 西安 710054）

一個高效的無證書簽名方案分析與改進

劉 倩1a，范安東1a，張麗娜2，張 愉1b

（1.成都理工大學a.管理科學學院；b.旅游與城鄉(xiāng)規(guī)劃學院，四川 成都 610059；2.西安科技大學計算機科學與技術學院，陜西 西安 710054）

對一種基于雙線性對的高效無證書簽名方案進行安全性分析，表明該方案對于公鑰替換攻擊和惡意的密鑰生成中心攻擊是不安全的。提出了一種可避免這些攻擊的改進方案。在隨機預言機模型、離散對數(shù)問題和計算Diffie-Hellman問題困難性假設下，證明了改進方案可以抵抗自適應選擇消息攻擊的存在性偽造。與其他基于雙線性對的無證書簽名方案相比，改進方案具有較高的計算效率。

無證書簽名；雙線性對；公鑰替換攻擊；惡意密鑰生成中心攻擊；離散對數(shù)問題；計算Diffie-Hellman問題

0 引言

為了消除傳統(tǒng)的基于公鑰基礎設施的公鑰密碼體制［1］（PKC）和基于身份的公鑰密碼體制［2］（IDPKC）存在的缺陷，解決使用證書和私鑰托管的問題，2003年，無證書的公鑰密碼體制（CL-PKC）首次被文獻［3］提出。與ID-PKC類似，CL-PKC也需要一個可信的密鑰生成中心（KGC），但在CL-PKC中，用戶的私鑰是由用戶隨機選擇的秘密值和KGC產(chǎn)生的部分私鑰組成，公鑰則是由用戶自己的秘密值、身份信息和系統(tǒng)參數(shù)進行一定的運算產(chǎn)生的。因此，KGC不知道用戶的秘密值，就無法得知任何用戶的私鑰，從而有效地解決了ID-PKC存在的私鑰托管問題［4］。

近年來，人們設計了各種數(shù)字簽名方案，如盲簽名，群簽名，代理簽名［5］等。隨著無證書公鑰密碼體制被提出，各種結(jié)合無證書公鑰密碼體制的簽名方案引起了學術界的極大關注［3，6－14］。第一個無證書簽名方案被文獻［3］提出后，文獻［6］立即指出此方案存在公鑰替換攻擊問題。2007年，文獻［7］設計了一個改進方案并且對安全的無證書簽名方案模型給出了定義。2008年，文獻［8］提出了一個高效的基于ID的無證書簽名方案，但文獻［9］指出該方案存在公鑰替換攻擊的問題。2009年，文獻［10］提出了在文獻［11］的安全模型下的一類無證書簽名方案。2010年，文獻［12］提出了一個高效無證書簽名方案，但文獻［13］指出該方案不能阻止兩類攻擊，即消極不誠實KGC的公鑰替換攻擊和積極不誠實的KGC攻擊。最近，文獻［14］提出了高效安全的無證書數(shù)字簽名方案，但文獻［15］指出該方案是不安全的，構造了3種偽造攻擊。

文獻［16］設計了一種高效的無證書簽名方案，驗證了它在隨機預言機模型下是安全的。本文對該方案進行分析，指出它既不能抵抗公鑰替換攻擊，也不能抵抗惡意的KGC攻擊。針對這些缺陷，本文提出了一種改進方案，并在隨機預言模型、離散對數(shù)問題（DLP）和計算Diffie-Hellman問題（CDHP）困難性假設下，證明了該方案的安全性，改進方案對于自適應性選擇消息的攻擊是不可偽造的。

1 背景知識

令G1和G2是具有相同大素數(shù)階q的加法循環(huán)群和乘法循環(huán)群，P是G1的一個生成元，假設G1和G2中的離散對數(shù)問題是難解的。若存在一個映射＾：G1×G1→G2滿足下面的性質(zhì)，則稱之為雙線性映射：

（1）雙線性：對于所有的a，b∈Z*q，P，Q∈G1，都有（aP，bQ）＝（P，Q）ab成立。

（2）非退化性：存在P，Q∈G1，使得（P，Q）≠1。

（3）可計算性：?P，Q∈G1，能夠有一個有效的算法計算＾（P，Q）。

定義1離散對數(shù)問題（DLP）：?P，Q∈G1，求解a∈Z*q使Q＝aP成立。

定義2計算Diffie-Hellman問題（CDHP）：?P，aP，bP∈G1，a，b∈Z*q，計算abP。

2 已有方案的安全性分析

2.1 公鑰替換攻擊

在CL-PKC中，用戶的公鑰并沒有得到直接驗證，從而容易遭受公鑰替換攻擊。通過分析發(fā)現(xiàn)，文獻［16］方案易遭受公鑰替換攻擊。敵手A1可以執(zhí)行以下步驟來偽造用戶對消息M的簽名：敵手A1隨機選取δ∈Z*q，并設P′ID＝δP，然后隨機選擇τ∈Z*q，計算，則σ′＝（h′，V′）是身份為ID，公鑰為P′ID對消息M的有效簽名。容易驗證：

2.2 惡意的KGC攻擊

文獻［16］方案無法抵抗惡意的KGC攻擊，當設置系統(tǒng)參數(shù)的時候，惡意的KGC就針對用戶設置的系統(tǒng)參數(shù)和用戶的公鑰來計算用戶的私鑰，因此能夠偽造用戶對消息的簽名。偽造簽名過程如下：

首先，惡意的KGC隨機選取x′∈Z*q，得到用戶的私鑰S′ID＝x′·DID＝x′s·QID，公鑰P′ID＝x′·P0＝x′s·P；然后，隨機選擇r′∈Z*q，計算，則σ′＝（h′，V′）可以偽造用戶的簽名。對偽造簽名可以進行如下的驗證：

綜上所述，文獻［16］方案對于惡意的KGC攻擊是脆弱的。

3 改進方案及其分析

3.1 改進方案

通過對文獻［16］方案的分析，一方面，可以通過將用戶的公鑰公布到系統(tǒng)參數(shù)中來阻止攻擊者進行公鑰替換攻擊；另一方面，惡意的KGC很容易計算出部分私鑰s·H1（ID），而且原方案中完整的私鑰設計的過于簡單，進而能計算出完整的私鑰x·DID，為此，在KGC生成部分私鑰時，可以將用戶的身份信息和公鑰一起綁定到H1中，對完整的私鑰信息進行處理來抵擋惡意的KGC攻擊。改進方案的具體描述如下：

（1）秘密值設置：身份為ID的用戶隨機選擇一個x∈Z*q作為秘密值。

（2）公鑰生成：秘密值為x的用戶（身份為ID）設置其公鑰為PID＝x·P。

（3）系統(tǒng)參數(shù)生成：輸入一個安全參數(shù)k，KGC選擇滿足第1節(jié)性質(zhì)的，G1，G2，P，計算g＝（P， P），并隨機選取s∈Z*q作為系統(tǒng)主密鑰，記P0＝sP，選擇兩個安全的Hash函數(shù)，設置系統(tǒng)參數(shù)

（4）部分私鑰提?。篕GC檢驗用戶的身份ID，計算部分私鑰，然后將DID返回給該用戶。

（5）完整私鑰生成：具有ID身份的用戶把SID＝DID＋x·H1（ID，PID）∈G1作為私鑰。

（6）簽名算法：簽名者輸入身份ID，公鑰PID，私鑰SID和消息M進行簽名，選擇一個隨機數(shù)r∈Z*q，計算，然后輸出簽名σ＝（h，V）。

3.2 改進方案的分析

3.2.1 正確性分析

對改進方案可以進行如下的正確性檢驗：

由此可見，改進的無證書簽名方案是正確的。

3.2.2 安全性分析

在CL-PKC中存在兩類敵手［3］。第一類敵手A1：A1可以替換任意用戶的公鑰，但是無法獲得系統(tǒng)的主密鑰以及用戶的部分私鑰；第二類敵手A11：A11相當于惡意的KGC攻擊，無法替換任意用戶的公鑰，但是可以獲得系統(tǒng)的主密鑰以及用戶的部分私鑰。下面的定理1和定理2說明了改進方案可以抵抗兩類敵手的自適應選擇消息攻擊的存在性偽造。

定理1在隨機預言機模型和DLP、CDHP困難性假設下，改進方案可以抵抗第一類敵手A1的自適應選擇消息攻擊的存在性偽造。

證明假設A1是第一類敵手，C是一個CDHP的挑戰(zhàn)者，輸入為（P，aP，bP）時，挑戰(zhàn)者C能夠利用A1計算abP。

設置參數(shù)：挑戰(zhàn)者C設置P0＝a·P，生成系統(tǒng)參數(shù)并發(fā)送給A1，A1可以適應性的執(zhí)行以下詢問。

H1詢問：挑戰(zhàn)者C維護列表L1，其格式為（ID，PID，α，QID），開始該列表為空。若A1最多執(zhí)行NH1次H1詢問，C在［1，NH1］中隨機選取一個值J。當C收到A1對H1（IDi，Pi）的詢問時，若i≠J，C隨機選擇αi∈Z*q，計算Qi＝αiP，Pi＝αiP0，將（IDi，Pi，αi，Qi）加入到L1中，并將Qi返回給A1；否則，C設置PJ＝βP0，αJ＝⊥，QJ＝bP，將（IDJ，PJ，αJ，QJ）加入到L1中，并將QJ返回給A1。

H2詢問：C維護列表L2，列表格式為（M，ID，R，P，h），起初該列表初始化為空。當A1詢問H2（Mi‖IDi‖Ri‖Pi）時，C隨機選擇hi∈Z*q，將（Mi，IDi，Ri，Pi，hi）加入到列表L2中，并將hi返回給A1。

部分私鑰詢問：若IDi＝IDJ，C終止詢問；否則檢查L1找到（IDi，αi，Qi），計算Di＝αiP0，并將Di返回給A1。若未詢問過H1（IDi，Pi），則首先執(zhí)行H1（IDi，Pi）詢問。

公鑰詢問：C維護列表K1，其格式為（ID，x，PID），開始該列表為空。A1對IDi進行公鑰詢問時，C首先檢查K1，若K1中有一項（IDi，xi，Pi），則C返回Pi給A1；否則，C隨機選擇xi∈Z*q，計算Pi＝xi·P，返回Pi給A1，將（IDi，xi，Pi）加入到K1中。

公鑰替換詢問：當C接到A1將用戶IDi的公鑰（IDi，Pi）替換為（IDi，P′i）時，C檢查K1找到（IDi，xi，Pi），并設置xi＝⊥，Pi＝P′i。

秘密值詢問：當C接到A1對用戶IDi的秘密值詢問時，C檢查K1找到（IDi，xi，Pi）。若xi＝⊥，說明用戶IDi的公鑰已經(jīng)被替換，返回⊥；否則C將xi返回給A1。

簽名詢問：當A1請求用戶IDi對消息Mi進行簽名詢問時，C隨機選擇hi∈Z*q，Vi∈G1，并將σ*＝（hi，Vi）返回給A1。

最后，A1輸出一個偽造簽名（M*，σ*＝（h，V），ID*，P*）。若ID*≠IDJ，C終止詢問；反之，由Forking引理［17］可知：C對A1哈希重放后選擇一個哈希函數(shù)H′2，可以得到一個新的偽造簽名（M*，σ*′＝（h′，V′），ID*，P*）。并且它們滿足V＝r·P＋h·SID和V′＝r·P＋h′·SID，所以sQID＝abP＝（1＋β）－1×（h－h(huán)′）－1（V－V′），這與CDHP的困難性相矛盾。

定理2在隨機預言機模型和DLP、CDHP困難性假設下，改進方案可以抵抗第二類敵手A11的自適應選擇消息攻擊的存在性偽造。

證明假設A11是第二類敵手，C是一個CDHP的挑戰(zhàn)者，輸入為（P，aP，bP）時，挑戰(zhàn)者C能夠利用A11計算abP。

設置參數(shù)：挑戰(zhàn)者C隨機選取一個s∈Z*q作為系統(tǒng)主密鑰，計算P0＝sP，生成系統(tǒng)參數(shù)，將系統(tǒng)參數(shù)params和s發(fā)送給A11，A11可以適應性的執(zhí)行以下詢問。

H1詢問：挑戰(zhàn)者C維護列表L1，列表的格式為（ID，PID，α，QID），開始該列表為空。若A11最多執(zhí)行NH1次H1詢問，C在［1，NH1］中隨機選取一個值J。當C收到A11對H1（IDi，Pi）的詢問時，若i≠J，C隨機選擇αi∈Z*q，計算Qi＝αiP，將（IDi，Pi，αi，Qi）加入到L1中，并將Qi返回給A11；否則，C設置αJ＝⊥，QJ＝bP，將（IDJ，PJ，αJ，QJ）加入到L1中，并將QJ返回給A11。

H2詢問：C維護列表L2，列表格式為（M，ID，R，P，h），起初該列表初始化為空。當A11詢問時，C隨機選擇hi∈Z*q，將（Mi，IDi，Ri，Pi，hi）加入到列表L2中，并將hi返回給A11。

公鑰詢問：C維護列表K1，其格式為（ID，x，PID），開始該列表為空。A11對IDi進行公鑰詢問時，C首先檢查K1，若K1中有一項（IDi，xi，Pi），則C返回Pi給A11；否則，C隨機選擇xi∈Z*q，計算Pi＝xi·P，返回Pi給A11，將（IDi，xi，Pi）加入到K1中。

秘密值詢問：當C接到A11對用戶IDi的秘密值詢問時，C檢查K1找到（IDi，xi，Pi）。若xi＝⊥，說明用戶IDi的公鑰已經(jīng)被替換，返回⊥；否則C將xi返回給A11。

簽名詢問：當A11請求用戶IDi對消息Mi進行簽名詢問時，C隨機選擇hi∈Z*q，Vi∈G1，并將σ*＝（hi，Vi）返回給A11。

最后，A11輸出一個偽造簽名（M*，σ*＝（h，V），ID*，P*）。若ID*≠IDJ，C終止詢問；反之，由Forking引理［17］可知：C對A11哈希重放后選擇一個哈希函數(shù)H′2，可以得到一個新的偽造簽名。并且它們滿足V＝r·P＋h′·SID和V′＝r·P＋h′·SID，所以xQID＝abP＝（h－h(huán)′）－1（V－V′）－sQID，這與CDHP的困難性相矛盾。

因此，在隨機預言機模型和DLP、CDHP困難性假設下，改進方案可以抵抗敵手A1和A11的自適應選擇消息攻擊的存在性偽造。

3.2.3 效率分析

本文從運算量和安全性兩個方面，將改進的新方案與其他無證書簽名方案比較，比較結(jié)果如表1所示。令P、mul、exp、H分別表示雙線性對運算、標量乘運算、冪運算和哈希運算。

表1 新方案與其他無證書簽名方案的比較

從表1可以得出：新方案消除了公鑰替換攻擊和惡意的KGC攻擊，運算量沒有比文獻［16］方案增加，與其他方案相比運算量減少了。

4 結(jié)束語

本文通過分析文獻［16］方案的安全性，說明了該方案對于公鑰替換和惡意的KGC攻擊是不安全的。為了有效解決該方案存在的問題，提出了一種改進方案。在隨機預言機模型和DLP、CDHP困難性假設下，證明了改進方案可以抵抗自適應選擇消息攻擊的存在性偽造。與其他基于雙線性對的無證書簽名方案相比，新方案只使用了兩個雙線性對運算，執(zhí)行效率比較高。

［1］ Adams C，Lloyd S.Understanding Public-Key Infrastructure-Concepts，Standards，and Deployment Considerations［M］. Indiana，USA：Sams，1999.

［2］ Shamir A.Identity-Based Cryptosystem and Signature Scheme［C］／／Advances in Cryptology-Crypto’84，LNCS 196.Berlin：Springer-Verlag，1984：47－53.

［3］ Al-Riyami S S，Paterson K G.Certificateless Public Key Cryptography［C］／／Advances in Cryptology-ASIACRYPT’03. Berlin：Springer-Verlag，2003：452－473.

［4］ 張福泰，孫銀霞，張磊，等.無證書公鑰密碼體制研究［J］.軟件學報，2011，22（6）：1316－1332.

［5］ 蔡曉秋，王天銀，張建中.基于Schnorr簽名體制的前向安全的代理簽名方案［J］.河南科技大學學報：自然科學版，2005，25（6）：33－36.

［6］ Huang X Y，Susilo W，Mu Y，et al.On the Security of Certificateless Signature Schemes from Asia Crypt’03［C］／／Proceedings of CANS’05.Berlin：Springer-Verlag，2005：13－25.

［7］ Huang X Y，Mu Y，Susilo W，et al.Certificateless Signature Revisited［C］／／Information Security and Privacy，ACISP 2007，LNCS 4586.Berlin：Springer-Verlag，2007：308－322.

［8］ 劉景偉，孫蓉，馬文平.高效的基于ID的無證書簽名方案［J］.通信學報，2008，29（2）：87－94.

［9］ 樊愛宛，任童童，魯書喜.一種無證書簽名方案的安全性分析及改進［J］.平頂山學院學報，2012，27（2）：59－64.

［10］ 張磊，張福泰.一類無證書簽名方案的構造方法［J］.計算機學報，2009，32（5）：940－945.

［11］ Hu B C，Wong D S，Zhang Z，et al.Key Replacement Attack Against a Generic Construction of Certificateless Signature［C］／／Proceedings of ACISP’06.Berlin：Springer-Verlag，2006：235－246.

［12］ 梁紅梅，黃振杰.高效無證書簽名方案的安全性分析與改進［J］.計算機應用，2010，30（3）：685－687.

［13］ 黃明軍，杜偉章.一種無證書簽名方案的安全性分析及其改進［J］.計算機應用，2011，31（6）：1536－1538.

［14］ 王麗莎，張建中.一種高效安全的無證書數(shù)字簽名方案［J］.計算機工程與應用，2012，48（15）：70－73.

［15］ 杜紅珍.一個無證書數(shù)字簽名方案的密碼學分析［J］.科學技術與工程，2012，12（33）：9042－9044.

［16］ 李鳳銀，劉培玉，朱振方.高效的無證書簽名方案［J］.計算機工程與應用，2011，47（10）：23－26.

［17］ Pointcheval D，Stern J.Security Proofs for Signature Schemes［C］／／Proceedings of the EUROCRYPT’96.Spain：Saragossa，1996：387－398.

TP309

A

1672－6871（2014）04－0049－05

四川省應用基礎計劃基金項目（2012JY0033）；國土資源部地學空間信息技術重點實驗室開放基金項目（KLGSIT2013－08）；四川省杰出青年學科帶頭人培養(yǎng)計劃基金項目（06ZQ026－014）；四川省教育廳自然科學重點基金項目（2006A116）

劉 倩（1988－），女，陜西戶縣人，碩士生；范安東（1970－），男，四川西充人，教授，博士，碩士生導師，主要研究方向為密碼學與信息安全.

2013－10－25