無證書簽名方案的分析與改進

趙 洪，喻書涵，韓妍妍，2，李兆斌

（1.北京電子科技學(xué)院 電子與通信工程系，北京 100070；2.北京電子科技學(xué)院 網(wǎng)絡(luò)空間安全系，北京 100070）

0 引言

無證書公鑰密碼體制由Al-Riyami 等［1］在2003 年提出。無證書密碼體制中用戶的私鑰由密鑰生成中心（Key Generation Center，KGC）生成的用戶部分私鑰和用戶選擇的秘密值構(gòu)成；用戶的公鑰由KGC 生成的公鑰和秘密值對應(yīng)的公鑰組成。該密碼體制無需數(shù)字證書，解決了證書管理問題；此外，KGC 只擁有用戶部分私鑰，能夠解決密鑰托管問題。

第一個無證書簽名方案由Al-Riyami 等［1］提出，此后大量無證書簽名方案相繼提出。2004 年，Yum 等［2］提出了無證書簽名的通用構(gòu)造；2005 年，Huang 等［3］指出文獻［1］方案無法抵抗公鑰替換攻擊，并給出了改進方案；隨后，2006 年Yap等［4］提出一個新的無證書簽名方案，但該方案仍無法抵抗敵手的公鑰替換攻擊。第一個標(biāo)準(zhǔn)模型下的無證書簽名方案由Liu 等［5］在2007 年提出，但是無法抵抗惡意KGC 攻擊。2012 年，王圣寶等［6］提出一個基于橢圓曲線離散對數(shù)問題的無雙線性對的方案，該方案在隨機預(yù)言機模型下可證明是安全的；然而王亞飛等［7］指出文獻［6］中方案在第Ⅰ類敵手的公鑰替換攻擊下是完全不安全的，并且基于橢圓曲線的數(shù)字簽名算法提出了一個改進方案并證明了該方案的安全性。2014 年，樊愛宛等［8］通過對傳統(tǒng)無證書算法順序的變換對文獻［7］中方案進行了改進，并聲稱該方案高效、可抵抗自適應(yīng)密文攻擊；然而在2016 年，湯永利等［9］針對文獻［8］方案進行分析，認(rèn)為該方案不能抵抗第Ⅰ類強敵手的攻擊，并且基于橢圓曲線離散對數(shù)改進方案，提出9 個可證明安全的無證書簽名方案。2020 年，王菁等［10］指出文獻［9］的9 個無證書簽名方案中，第1、2、5、8、9 這5 個無證書簽名方案無法抵抗第Ⅰ類敵手的替換公鑰攻擊；然而文獻［10］中并未分析文獻［9］中其余可抵抗第Ⅰ類敵手攻擊的方案是否能夠抵抗第Ⅱ類敵手的攻擊，并且未對文獻［9］中無法抵抗第Ⅰ類敵手攻擊的方案進行改進；同樣，胡冰潔等［11］只對文獻［9］中方案1進行了第Ⅰ類敵手的分析，并沒有分析其余方案的安全性。張振超等［12］通過對現(xiàn)有文獻［13-18］列舉的攻擊過程的分析，總結(jié)了敵手偽造無證書簽名的本質(zhì)原因是簽名方案中公鑰具有線性關(guān)系，并總結(jié)出線性化分析方法。本文使用線性化方程分析的方法，以證明湯永利等［9］提出的9 個無證書簽名方案都不具有安全性，并且提出改進方案，該方案在隨機預(yù)言機模型下是可證明安全的；通過對敵手攻擊方式的分析，提出了一類無證書簽名驗證方案的安全公鑰構(gòu)造格式。

1 預(yù)備知識

1.1 困難問題與安全假設(shè)

設(shè)q是一個大素數(shù)，在有限域Fq上定義一個橢圓曲線E/Fq，在該橢圓曲線上的所有點構(gòu)成一個加法群G，G中有生成元P，P的階數(shù)為q。

定義1橢圓曲線離散對數(shù)問題（Elliptic Curve Discrete Logarithm Problem，ECDLP）。對于一個給定的橢圓曲線群G，P、Q是G上兩點，α∈，使Q=αP，已知P、G，求α。

ECDLP 假設(shè)：對于任何概率多項式時間算法A，都只能以可忽略的優(yōu)勢解決ECDLP。

1.2 無證書簽名方案定義回顧

根據(jù)文獻［1］定義，無證書簽名方案包括三個合法參與者：密鑰生成中心KGC、簽名者和驗證者，和以下7 種多項式時間的算法。

建立系統(tǒng)算法（Setup）：KGC 輸入安全參數(shù)，生成公開的系統(tǒng)參數(shù)params和主密鑰s，并秘密保存主密鑰s。

部分私鑰生成算法（Extract-Partial-Private-Key）：由KGC完成該算法，KGC 輸入系統(tǒng)參數(shù)params、主密鑰s和用戶身份標(biāo)識ID，輸出值dID作為用戶部分私鑰。

用戶秘密值生成算法（Set-Secret-Value）：由用戶完成該算法，用戶輸入系統(tǒng)參數(shù)params和個人身份標(biāo)識ID，輸出值xID作為用戶秘密值。

完整私鑰生成算法（Set-Private-Key）：由用戶完成該算法，用戶輸入系統(tǒng)參數(shù)params、用戶標(biāo)識ID、秘密值xID和部分私鑰dID，輸出值sID作為用戶完整私鑰。

公鑰生成算法（Set-Public-Key）：由用戶完成該算法，用戶輸入系統(tǒng)參數(shù)params、用戶標(biāo)識ID和秘密值xID，輸出值PID作為用戶公鑰。

簽名算法（Sign）：簽名者IDA輸入消息M、系統(tǒng)參數(shù)params、簽名者標(biāo)識ID和私鑰sID，輸出值σ作為對消息M的簽名。

驗證算法（Verify）：驗證者IDB輸入系統(tǒng)參數(shù)params、簽名者標(biāo)識ID、簽名者公鑰PID以及對消息M的簽名σ，若簽名驗證通過，則輸出true；若驗證不通過，則輸出false。

1.3 無書簽名的安全模型

根據(jù)文獻［19-21］的定義，無證書簽名的安全模型將敵手按能力劃分為兩類：第Ⅰ類敵手和第Ⅱ類敵手。其中：第Ⅰ類敵手沒有KGC 主密鑰，但可以發(fā)動替換用戶公鑰攻擊；第Ⅱ類敵手不能替換用戶公鑰，但是擁有KGC 主密鑰。

文獻［20］中詳細(xì)定義了敵手與挑戰(zhàn)者之間的游戲過程。

2 湯永利方案的安全性分析

2.1 湯永利方案回顧

湯永利通過對文獻［8］中方案的分析，在2016 年給出了具體的攻擊方案證明文獻［8］中的方案不能抵抗第Ⅰ類強敵手的攻擊，并且提出了基于ECDLP 假設(shè)的改進方案，具體如下。

1）建立系統(tǒng)算法（Setup）：

①KGC 輸入安全參數(shù)k，選擇大素數(shù)q，P為橢圓曲線加法群G中一個q階生成元。

②KGC 任意選擇主密鑰s∈，生成KGC 公鑰Ppub=sP。

④KGC 公開系統(tǒng)參數(shù)params={p，q，G，P，Ppub，H1，H2}，并保存主密鑰s。

2）部分私鑰生成算法（Extract-Partial-Private-Key）：

①KGC 接收到用戶提交的身份標(biāo)識IDA后，選擇隨機數(shù)rA∈，計算RA=rAP。

②計算dA=rA+sH1(IDA，RA)。

③dA作為用戶的部分私鑰，RA作為用戶的部分公鑰，KGC 將(RA，dA)以安全的方式返回給用戶。

④用戶驗證dAP=RA+PpubH1(IDA，RA)等式是否成立，成立則接受，否則拒絕。

3）用戶秘密值生成算法（Set-Secret-Value）：

用戶隨機選擇秘密值xA，其中xA∈。

4）完整私鑰生成算法（Set-Private-Key）：

生成sA=(dA，xA)作為用戶的完整私鑰。

5）公鑰生成算法（Set-Public-Key）：

①通過用戶秘密值xA計算XA=xAP。

②設(shè)置PA=(RA，XA)作為用戶的完整公鑰。

6）簽名算法（Sign）：簽名者為用戶A，要簽名的文件為M，驗證者為用戶B，該算法如下。

①用戶A 隨機選取t∈，計算T=tP。

②計算哈希值：h2=H2(M，IDA，RA，XA，T)

③根據(jù)表1 中列出的9 個無證書簽名方案計算部分簽名u，用戶A 對消息M完成簽名σ=(u，T)，發(fā)送(IDA，σ，M，PA)給用戶B。

7）驗證算法（Verify）：用戶B 為簽名驗證者，算法如下。

①B 接收到(IDA，σ，M，PA)之后，計算h1=H1(IDA，RA)，h2=H2(M，IDA，RA，XA，T)。

②B 按照表1 與簽名方案計算u對應(yīng)的公式T′，驗證T′=T是否成立，若成立則σ為用戶A 對消息M的簽名，返回true；否則此簽名無效，返回false。

表1 簽名驗證方案Tab.1 Signature and verification schemes

2.2 線性化方程分析回顧

在文獻［12］中，給出線性化方程的定義：假設(shè)用戶產(chǎn)生的部分公鑰為P1，P2，…，Pn，KGC 產(chǎn)生的公鑰為Q1，Q2，…，Qn，有若干抗碰撞的哈希函數(shù)h1，h2，…，h2n，當(dāng)驗證等式中出現(xiàn)式（1）的等式時稱為公鑰具有線性關(guān)系。

3 針對湯永利方案的攻擊

3.1 第Ⅰ類敵手針對湯永利簽名方案的攻擊回顧

根據(jù)文獻［11］對湯永利方案1 進行的公鑰替換攻擊，第Ⅰ類敵手可以通過控制用戶公鑰XA消除KGC 公鑰Ppub，同時不需要提交更改的用戶秘密值xA即可完成偽造簽名；在第2、5、8、9 這4 個無證書簽名方案中，同樣存在等式XA+RA+h1Ppub=0 可以被第Ⅰ類敵手通過相同的方法攻破，因此湯永利等［9］提出的9 個無證書簽名方案中，第1、2、5、8、9 這5個無證書簽名方案無法抵抗第Ⅰ類敵手攻擊。

3.2 第Ⅱ類敵手對湯永利方案3的攻擊

文獻［10-11］僅僅對湯永利方案進行了第Ⅰ類敵手安全性分析，指出文獻［9］中提出的第1、2、5、8、9 這5 個無證書簽名方案是不安全的；本文通過線性化方程的方法，對9 個方案進行分析，可以對包括文獻［9］中的第3、4、6、7 這4 個第Ⅰ類敵手攻擊安全的無證書簽名方案在內(nèi)的所有9 個方案進行第Ⅱ類敵手攻擊。

第Ⅱ類敵手擁有KGC 的主密鑰s，但是不能替換用戶公鑰，因此第Ⅱ類敵手通過消除用戶秘密值xA作用的方式偽造簽名，在文獻［9］的無證書簽名方案3 中，驗證算法中存在形如式（1）的等式h2XA+RA+h1Ppub=0，第Ⅱ類敵手可以使用線性化分析的方法，通過自己控制的KGC 公鑰Ppub消除RA和XA，完成對簽名的偽造，詳細(xì)過程如下所述。

1）偽造攻擊：第Ⅱ類敵手執(zhí)行以下操作。

①隨機選取一個t′∈，計算T′=t′P。

②選擇一條新的消息M′≠M，計算：

結(jié)論1 湯永利等［9］的無證書簽名方案3 無法抵抗第Ⅱ類敵手進行的惡意KGC 攻擊，敵手可以偽造用戶對消息的簽名，因此該方案是不安全的。

3.3 針對其他簽名方案的攻擊

通過對簽名方案中驗證等式的分析發(fā)現(xiàn)，在第1、2、5、8、9 這 5 個無證書簽名方案中存在等式XA+RA+h1Ppub=0；方案4 中存在等式XA+h2RA+h1h2Ppub=0；方案6 中存在等式h2XA+RA+h1Ppub=0；方案7 中存在等式XA+h2RA+h1h2Ppub=0，因此與攻擊方案3 的方法相同，第Ⅱ類敵手可以通過自己控制的KGC 公鑰Ppub發(fā)起惡意的KGC 攻擊，消除RA和XA，完成對簽名的偽造。

結(jié)論2 湯永利等［9］中的所有無證書簽名方案都無法抵抗第Ⅱ類敵手發(fā)起的惡意KGC 攻擊，該文獻中所有方案面對于第Ⅱ類敵手攻擊都不安全。

4 改進的無證書簽名方案

本章將對文獻［9］方案的不安全原因進行分析并改進，改進的方案對第Ⅰ類敵手和第Ⅱ類敵手是安全的，并且給出了安全性證明。

4.1 湯永利等方案不安全原因分析

對于第Ⅰ類敵手，為了成功偽造簽名，在無法計算出KGC 主密鑰的情況下需要避開KGC 主密鑰s。文獻［9］方案中存在用戶公鑰和KGC 公鑰的線性關(guān)系，敵手可以通過線性的關(guān)系控制用戶公鑰消去KGC 公鑰，這樣在偽造的過程中可以不使用KGC 的主密鑰進行簽名，而只使用用戶私鑰，消去了KGC 作為第三方的參與，變成了敵手與驗證者一對一的信息傳遞，只要是敵手選取的私鑰生成的簽名就一定可以通過敵手的公鑰對簽名驗證。

對于第Ⅱ類敵手，為了成功偽造簽名，在無法計算出用戶秘密值的情況下只能以避開用戶秘密值的方法偽造簽名。由于敵手掌握了KGC 的主密鑰，可以發(fā)動惡意KGC 攻擊，因此敵手可以在生成系統(tǒng)參數(shù)算法（Setup）中適應(yīng)性地設(shè)置陷門信息，即在設(shè)置KGC 公鑰時通過巧妙的設(shè)計使包含用戶秘密值的公鑰在計算中被KGC 公鑰消除。通過這種方法，在驗證簽名的過程中無需驗證用戶公鑰和私鑰之間的關(guān)系，用戶的秘密值就失去了作用，敵手達到了避開用戶秘密值的目的。在文獻［9］中，KGC 公鑰與用戶公鑰存在著線性的關(guān)系，敵手可以輕易通過KGC 公鑰和用戶公鑰間的線性關(guān)系，控制KGC 公鑰消去用戶公鑰，完成簽名偽造。

本文基于方案3 進行改進，通過破壞KGC 公鑰和用戶公鑰之間的線性關(guān)系解決文獻［9］中存在的問題，并且提出了一種安全的公鑰構(gòu)造格式，這類構(gòu)造格式不具有線性性質(zhì)，因此無法通過線性化分析方法偽造，證明了改進的方案在隨機預(yù)言機模型下是安全的。

4.2 改進的無證書簽名方案

1）建立系統(tǒng)算法（Setup）：

①KGC 輸入安全參數(shù)k，選擇素數(shù)q，P為橢圓曲線加法群G中一個q階生成元。

②KGC 隨機選擇主密鑰s∈，生成KGC 公鑰Ppub=sP。

③選擇兩個安全 的Hash 函數(shù)H1：{0，1}*→，H2：{0，1}*→。

④KGC 公開系統(tǒng)參數(shù)params={p，q，G，P，Ppub，H1，H2}，并保存主密鑰s。

2）部分私鑰生成算法（Extract-Partial-Private-Key）：

①KGC 接收到用戶提交的身份標(biāo)識IDA后，選擇隨機數(shù)rA∈，計算RA=rAP。

②計算h1=H1(IDA，RA，P，Ppub)；

③計算dA=rA+sh1。

④dA作為用戶的部分私鑰，RA作為用戶的部分公鑰，KGC 通過安全的方式將(RA，dA)返回給用戶。

⑤用戶驗證dAP=RA+Ppubh1，若等式不成立，則申請重新生成部分私鑰。

3）用戶秘密值生成算法（Set-Secret-Value）：用戶隨機選擇秘密值xA，其中xA∈。

4）完整私鑰生成算法（Set-Private-Key）：生成sA=(dA，xA)作為用戶的完整私鑰。

5）公鑰生成算法（Set-Public-Key）：

①通過用戶秘密值xA計算XA=xAP；

②設(shè)置PA=(RA，XA)作為用戶的完整公鑰。

6）簽名算法（Sign）：簽名者為用戶A，要簽名的文件為M，簽名者為用戶B，算法如下。

①對于消息M，用戶A 任選隨機值t∈，計算T=tP。

②計算哈希值h2=H2(M，IDA，RA，XA，T)。

③計算u=t-1(h2xA+dA)，生成簽名σ=(u，T)，并將消息M，身份標(biāo)識IDA，用戶公鑰PA=(RA，XA)以及簽名σ=(u，T)發(fā)送給驗證者B。

7）驗證算法（Verify）。當(dāng)B 接收到消息M和簽名后，計算：

判斷等式T′=T是否成立，若成立則簽名σ有效，輸出true，否則輸出false，其中T′為驗證時的信息。

改進方案的正確性由以下方程保證：

4.3 驗證方案中一種安全的公鑰構(gòu)造格式

湯永利等［9］方案無法抵抗敵手攻擊的原因在于用戶公鑰和KGC 公鑰在簽名驗證時存在線性關(guān)系。通過簽名驗證等式的偽造過程可以發(fā)現(xiàn)，當(dāng)與公鑰相乘的哈希函數(shù)中包含該部分公鑰時，無法偽造該公鑰。為使驗證等式中的所有公鑰都無法被敵手替換，本文提出形如式（9）的構(gòu)造格式，保證敵手無法進行公鑰替換攻擊。

其中：Xi為用戶的公鑰；Pi為KGC 公鑰。與用戶公鑰相乘的哈希函數(shù)hi中至少需要包含用戶的公鑰Xi，與KGC 公鑰相乘的哈希函數(shù)hi+n中至少需要包含KGC 公鑰Pi。

通過這種構(gòu)造格式，將KGC 公鑰同對應(yīng)哈希值關(guān)聯(lián)，任何對于KGC 公鑰的修改都會引起哈希值的改變，而哈希值的改變又會影響公鑰值，使第Ⅱ類敵手無法輕易地控制KGC公鑰的變化，從而無法消除用戶公鑰。同時，通過將用戶公鑰與包含用戶公鑰的哈希函數(shù)關(guān)聯(lián)，破壞原有的線性關(guān)系，第Ⅰ類敵手無法輕易地控制用戶公鑰的變化，從而無法達到消除KGC 公鑰的目的。該構(gòu)造格式既保證了簽名驗證等式的簡便性，又避免了公鑰之間的線性關(guān)系，對無證書簽名方案中簽名驗證等式的安全構(gòu)造具有參考價值。

4.4 安全性證明

定理1在隨機預(yù)言機模型下，若AⅠ是一個第Ⅰ類敵手，可以在多項式時間內(nèi)以不可忽視的優(yōu)勢ε攻破本方案中簽名的不可偽造性，那么存在C1作為一個ECDLP 挑戰(zhàn)者，可以在多項式時間內(nèi)以不可忽視的優(yōu)勢ε′≥解決ECDLP。其中：q1為敵手AⅠ對隨機預(yù)言機H1進行的用戶生成查詢次數(shù)；q2為敵手AⅠ進行的部分私鑰查詢次數(shù)。

證明 假設(shè)C1是針對ECDLP 的攻擊者，擁有參數(shù)(P，aP)，C1的目標(biāo)是計算出a。C1讓其子程序AⅠ成為一個在自適應(yīng)選擇的消息攻擊下攻破所提出簽名方案的敵手，C1充當(dāng)挑戰(zhàn)者的角色，并且維持列表L、、，其中L列表用于跟蹤敵手AⅠ對用戶的公鑰生成查詢；用于追蹤敵手AⅠ對預(yù)言機H1的詢問；用于追蹤敵手AⅠ對預(yù)言機H2的詢問。

1）初始化階段：挑戰(zhàn)者C1設(shè)置KGC 公鑰為Ppub=aP（隱含條件為系統(tǒng)主密鑰s=a），產(chǎn)生系統(tǒng)參數(shù)params={p，q，G，P，Ppub，H1，H2}，挑戰(zhàn)者將系統(tǒng)參數(shù)發(fā)送給敵手AⅠ。

2）查詢階段：用戶生成查詢。挑戰(zhàn)者C1隨機選取一個索引I，0 ≤I≤q1，q1為敵手AⅠ對隨機預(yù)言機H1進行的用戶生成最大查詢次數(shù)，挑戰(zhàn)者C1創(chuàng)建列表L，列表初始化為空，列表的存儲格式為一個五元組(IDi，xi，Xi，Ri，di)，每當(dāng)敵手根據(jù)身份標(biāo)識IDi進行查詢時，挑戰(zhàn)者C1查詢列表L，并按照如下步驟與敵手進行交互：

3）偽造階段：敵手AⅠ經(jīng)過以上查詢之后，生成一個關(guān)于身份ID*、消息M*的簽名σ=(u，T)，若ID*≠IDI，則挑戰(zhàn)者C1終止程序；若ID*=IDI，并且敵手AⅠ沒有對身份為IDI的消息M*進行過簽名查詢，敵手AⅠ就生成了一個對于身份ID*，消息M*的有效偽造簽名。由于一個偽造簽名無法解決挑戰(zhàn)者C1的ECDLP，因此挑戰(zhàn)者使用分叉引理［22］，選擇兩個不同的Hash 函數(shù)H1，可以獲得兩個不同的有效簽名，故存在另一個有效的偽造簽名σ′=(u′，T)，并且以下兩個等式成立：

求得a=則挑戰(zhàn)者成功地利用敵手AⅠ作為子程序，解決了ECDLP。

定義以下三個事件。

Δ1：敵手AⅠ不查詢身份為ID*=IDI的部分私鑰。

Δ2：敵手AⅠ成功輸出身份為ID*=IDI的偽造簽名。

Δ3：敵手AⅠ成功偽造兩個不同的有效簽名。

AⅠ在查詢階段共進行q2次部分私鑰查詢，每次查詢到身份為IDI的概率為

AⅠ在偽造階段輸出身份為ID*=IDI的偽造簽名概率為

已知AⅠ成功輸出一個有效偽造簽名的概率為ε，根據(jù)分叉引理［22］可知，敵手AⅠ成功偽造兩個不同的有效簽名的概率為

事件Δ3發(fā)生的概率即為ε′，若ε是不可忽視的，則挑戰(zhàn)者C1可以以的概率解決ECDLP，這一概率也是不可忽視的。

定理2根據(jù)文獻［20］的定義，在隨機預(yù)言機模型下，若AⅡ是一個第Ⅱ類敵手，能在多項式時間內(nèi)以不可忽視的優(yōu)勢ε攻破本方案中簽名的不可偽造性，那么存在C2作為一個ECDLP 挑戰(zhàn)者，可以在多項式時間內(nèi)以不可忽視的優(yōu)勢ε′≥解決ECDLP，其中：q1為敵手AⅡ?qū)﹄S機預(yù)言機H1進行的用戶生成查詢次數(shù)；q3為敵手AⅡ進行的用戶秘密值查詢次數(shù)。

定理2 的證明同定理1 類似，區(qū)別在于敵手AⅡ擁有KGC主密鑰，但是不能替換用戶公鑰，挑戰(zhàn)者選定用戶IDI的秘密值xI=a。查詢過程在此不再贅述。

敵手AⅡ經(jīng)過多輪查詢之后，生成一個關(guān)于身份ID*、消息M*的簽名σ=(u，T)，若ID*≠IDI，則挑戰(zhàn)者C2終止；若ID*=IDI，并且敵手AⅡ沒有對身份為IDI的消息M*進行過簽名查詢，那么敵手AⅡ就生成了一個對于身份ID*、消息M*的有效偽造簽名，根據(jù)分叉引理［22］可知，選擇兩個不同的Hash函數(shù)H2，可以獲得兩個不同的有效簽名，故存在另一個有效的偽造簽名σ′=(u′，T)，并且以下兩個等式成立：

其中：xI=a，可以求得則挑戰(zhàn)者C2成功地利用敵手AⅡ作為子程序，解決了ECDLP。

文獻［9］在驗證方案上存在用戶和KGC 公鑰的線性關(guān)系，使敵手可以進行公鑰替換攻擊和惡意KGC 攻擊，而改進后的方案通過增加哈希函數(shù)中的輸入和驗證等式的改進方法，加強了用戶各部分公鑰之間、用戶公鑰與KGC 公鑰之間的關(guān)聯(lián)程度，各部分公鑰之前的系數(shù)不再是與該部分公鑰無關(guān)的哈希值，而是含有該公鑰的哈希函數(shù)，通過這種方法破壞了原有的線性性質(zhì)，使敵手很難通過線性方程消除其余公鑰。上述安全性證明將攻破簽名方案的不可偽造性問題規(guī)約到了ECDLP 上，而ECDLP 是已經(jīng)證明了的困難性問題，因此改進后的方案可以抵抗第Ⅰ類敵手和第Ⅱ類敵手攻擊，該簽名方案具有不可偽造性，在隨機預(yù)言機模型下是安全的。

5 安全性與效率分析

將本文方案與文獻［7-9］方案進行效率比較，其中相較于點乘運算、求逆運算的開銷，散列運算、點加運算、大數(shù)加法運算和模運算時間都可忽略不計。本文用F 表示點乘運算，M 表示求逆運算。

由表2 可知，本文方案簽名階段只需要1F+1M，驗證階段只需要2F+1M。本文驗證階段只需要2F 的原因是：根據(jù)文獻［23］中定義，諸如aP1+bP類的運算可以進行快速計算。經(jīng)分析，文獻［7-9］中的方案存在安全缺陷，其中文獻［7］中的方案不能抵抗第Ⅰ類敵手發(fā)起的公鑰替換攻擊；文獻［8］中的方案是完全不安全的，既不能抵抗第Ⅰ類敵手也不能抵抗第Ⅱ類敵手攻擊；文獻［9］中的9 個方案當(dāng)中，第1、2、5、8、9 這5 個無證書簽名方案不能抵抗第Ⅰ類敵手發(fā)起的公鑰替換攻擊，9 個方案對于第Ⅱ類敵手攻擊是完全不安全的。在計算效率方面，本文提出的方案相較于文獻［7-8］減少了驗證階段的點乘運算，提高了計算效率。

對于基于橢圓曲線的無證書簽名方案，本文選擇了曲線secp160r1，使用MIRACL 庫在8 GB 內(nèi)存，1.80 GHz 的CPU 環(huán)境中進行仿真。結(jié)果如下：

在仿真環(huán)境下得到單個點乘運算的平均時間開銷約為0.552 706 ms，求逆運算的平均時間開銷約為0.024 728 ms，圖1 對比了存在的各個無證書簽名方案的簽名、驗證以及總體方案的計算開銷。各個方案的實際運行時間與表2 中分析所得的計算時間相符。與文獻［7-8］方案相比，改進方案的驗證時間明顯減少；與文獻［9］方案相比，在保證了安全的情況下，方案的運行時間持平。

表2 各方案安全性與效率分析Tab.2 Safety and efficiency analysis of each scheme

圖1 現(xiàn)有方案計算開銷對比Fig.1 Cost comparison of existing schemes

6 結(jié)語

本文對文獻［9］中的所有無證書簽名方案進行了分析，指出所有的方案都不能抵抗第Ⅱ類敵手的攻擊，為此提出了改進方案，改進方案可以抵抗第Ⅰ類敵手和第Ⅱ類敵手攻擊，具有更高的安全性。同時本文提出了一種在簽名方案中安全的公鑰構(gòu)造格式，將該格式使用在簽名驗證等式的構(gòu)造中，可以有效抵抗敵手的替換公鑰攻擊，相關(guān)結(jié)論對構(gòu)造安全的無證書簽名方案有參考意義。