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

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

（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）

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

無證書簽名；雙線性對(duì)；公鑰替換攻擊；惡意密鑰生成中心攻擊；離散對(duì)數(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］。

近年來，人們?cè)O(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)方案并且對(duì)安全的無證書簽名方案模型給出了定義。2008年，文獻(xiàn)［8］提出了一個(gè)高效的基于ID的無證書簽名方案，但文獻(xiàn)［9］指出該方案存在公鑰替換攻擊的問題。2009年，文獻(xiàn)［10］提出了在文獻(xiàn)［11］的安全模型下的一類無證書簽名方案。2010年，文獻(xiàn)［12］提出了一個(gè)高效無證書簽名方案，但文獻(xiàn)［13］指出該方案不能阻止兩類攻擊，即消極不誠(chéng)實(shí)KGC的公鑰替換攻擊和積極不誠(chéng)實(shí)的KGC攻擊。最近，文獻(xiàn)［14］提出了高效安全的無證書數(shù)字簽名方案，但文獻(xiàn)［15］指出該方案是不安全的，構(gòu)造了3種偽造攻擊。

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

1 背景知識(shí)

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

（1）雙線性：對(duì)于所有的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離散對(duì)數(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í)行以下步驟來偽造用戶對(duì)消息M的簽名：敵手A1隨機(jī)選取δ∈Z*q，并設(shè)P′ID＝δP，然后隨機(jī)選擇τ∈Z*q，計(jì)算，則σ′＝（h′，V′）是身份為ID，公鑰為P′ID對(duì)消息M的有效簽名。容易驗(yàn)證：

2.2 惡意的KGC攻擊

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

首先，惡意的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′）可以偽造用戶的簽名。對(duì)偽造簽名可以進(jìn)行如下的驗(yàn)證：

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

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

3.1 改進(jìn)方案

通過對(duì)文獻(xiàn)［16］方案的分析，一方面，可以通過將用戶的公鑰公布到系統(tǒng)參數(shù)中來阻止攻擊者進(jìn)行公鑰替換攻擊；另一方面，惡意的KGC很容易計(jì)算出部分私鑰s·H1（ID），而且原方案中完整的私鑰設(shè)計(jì)的過于簡(jiǎn)單，進(jìn)而能計(jì)算出完整的私鑰x·DID，為此，在KGC生成部分私鑰時(shí)，可以將用戶的身份信息和公鑰一起綁定到H1中，對(duì)完整的私鑰信息進(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 正確性分析

對(duì)改進(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對(duì)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終止詢問；否則檢查L(zhǎng)1找到（IDi，αi，Qi），計(jì)算Di＝αiP0，并將Di返回給A1。若未詢問過H1（IDi，Pi），則首先執(zhí)行H1（IDi，Pi）詢問。

公鑰詢問：C維護(hù)列表K1，其格式為（ID，x，PID），開始該列表為空。A1對(duì)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對(duì)用戶IDi的秘密值詢問時(shí)，C檢查K1找到（IDi，xi，Pi）。若xi＝⊥，說明用戶IDi的公鑰已經(jīng)被替換，返回⊥；否則C將xi返回給A1。

簽名詢問：當(dāng)A1請(qǐng)求用戶IDi對(duì)消息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對(duì)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對(duì)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對(duì)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對(duì)用戶IDi的秘密值詢問時(shí)，C檢查K1找到（IDi，xi，Pi）。若xi＝⊥，說明用戶IDi的公鑰已經(jīng)被替換，返回⊥；否則C將xi返回給A11。

簽名詢問：當(dāng)A11請(qǐng)求用戶IDi對(duì)消息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對(duì)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分別表示雙線性對(duì)運(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］方案的安全性，說明了該方案對(duì)于公鑰替換和惡意的KGC攻擊是不安全的。為了有效解決該方案存在的問題，提出了一種改進(jìn)方案。在隨機(jī)預(yù)言機(jī)模型和DLP、CDHP困難性假設(shè)下，證明了改進(jìn)方案可以抵抗自適應(yīng)選擇消息攻擊的存在性偽造。與其他基于雙線性對(duì)的無證書簽名方案相比，新方案只使用了兩個(gè)雙線性對(duì)運(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）；國(guó)土資源部地學(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