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

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

一個(gè)高效的無證書簽名方案分析與改進(jìn)

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

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

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

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

0 引言

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

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

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

1 背景知識

令G1和G2是具有相同大素?cái)?shù)階q的加法循環(huán)群和乘法循環(huán)群，P是G1的一個(gè)生成元，假設(shè)G1和G2中的離散對數(shù)問題是難解的。若存在一個(gè)映射＾：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）可計(jì)算性：?P，Q∈G1，能夠有一個(gè)有效的算法計(jì)算＾（P，Q）。

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

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

2 已有方案的安全性分析

2.1 公鑰替換攻擊

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

2.2 惡意的KGC攻擊

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

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

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

3 改進(jìn)方案及其分析

3.1 改進(jìn)方案

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

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

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

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

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

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

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

3.2 改進(jìn)方案的分析

3.2.1 正確性分析

對改進(jìn)方案可以進(jìn)行如下的正確性檢驗(yàn)：

由此可見，改進(jìn)的無證書簽名方案是正確的。

3.2.2 安全性分析

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

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

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

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

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

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

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

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

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

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

簽名詢問：當(dāng)A1請求用戶IDi對消息Mi進(jìn)行簽名詢問時(shí)，C隨機(jī)選擇hi∈Z*q，Vi∈G1，并將σ*＝（hi，Vi）返回給A1。

最后，A1輸出一個(gè)偽造簽名（M*，σ*＝（h，V），ID*，P*）。若ID*≠IDJ，C終止詢問；反之，由Forking引理［17］可知：C對A1哈希重放后選擇一個(gè)哈希函數(shù)H′2，可以得到一個(gè)新的偽造簽名（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在隨機(jī)預(yù)言機(jī)模型和DLP、CDHP困難性假設(shè)下，改進(jìn)方案可以抵抗第二類敵手A11的自適應(yīng)選擇消息攻擊的存在性偽造。

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

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

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

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

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

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

簽名詢問：當(dāng)A11請求用戶IDi對消息Mi進(jìn)行簽名詢問時(shí)，C隨機(jī)選擇hi∈Z*q，Vi∈G1，并將σ*＝（hi，Vi）返回給A11。

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

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

3.2.3 效率分析

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

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

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

4 結(jié)束語

本文通過分析文獻(xiàn)［16］方案的安全性，說明了該方案對于公鑰替換和惡意的KGC攻擊是不安全的。為了有效解決該方案存在的問題，提出了一種改進(jìn)方案。在隨機(jī)預(yù)言機(jī)模型和DLP、CDHP困難性假設(shè)下，證明了改進(jìn)方案可以抵抗自適應(yīng)選擇消息攻擊的存在性偽造。與其他基于雙線性對的無證書簽名方案相比，新方案只使用了兩個(gè)雙線性對運(yùn)算，執(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］.軟件學(xué)報(bào)，2011，22（6）：1316－1332.

［5］ 蔡曉秋，王天銀，張建中.基于Schnorr簽名體制的前向安全的代理簽名方案［J］.河南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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］.通信學(xué)報(bào)，2008，29（2）：87－94.

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

［10］ 張磊，張福泰.一類無證書簽名方案的構(gòu)造方法［J］.計(jì)算機(jī)學(xué)報(bào)，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ìn)［J］.計(jì)算機(jī)應(yīng)用，2010，30（3）：685－687.

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

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

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

［16］ 李鳳銀，劉培玉，朱振方.高效的無證書簽名方案［J］.計(jì)算機(jī)工程與應(yīng)用，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

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

劉 倩（1988－），女，陜西戶縣人，碩士生；范安東（1970－），男，四川西充人，教授，博士，碩士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)與信息安全.

2013－10－25