涂曉斌，艾美珍，2，左黎明，2，易傳佳，2，周 曉，鄧國健

（華東交通大學(xué)1. 理學(xué)院； 2. 系統(tǒng)工程與密碼學(xué)研究所； 3. 信息工程學(xué)院，江西 南昌330013）

1976 年，傳統(tǒng)公鑰密碼體制被Diffie 和Hellman[1]首次提出，該密碼體制中公鑰需依賴可信證書機構(gòu)（certificate authority， CA） 與用戶身份關(guān)聯(lián)， 但CA 的管理增加了系統(tǒng)維護成本。 基于身份的密碼體制在1984 年被Shamir[2]提出，解決了公鑰與用戶的關(guān)聯(lián)問題，卻帶來了密鑰托管問題[3]。Al-Riyami 和Paterson[4]在2003 年提出了無證書密碼體制，不僅克服了公鑰密碼體制中的CA 證書管理問題，還解決了基于身份的密碼體制的密鑰托管問題。 由此，無證書密碼體制被廣泛應(yīng)用于數(shù)字簽名[5]中，成為了當(dāng)前國內(nèi)外專家的研究熱點[6-8]。 2015 年，湯永利等人[9]提出了一類無證書簽名方案，且通過形式化的安全證明表明該方案具有較高安全性。2017 年，周彥偉等人[10]提出了一個高效安全的無證書簽名方案，實驗表明該方案具有較高的計算效率。 2018 年，吳濤等人[11]指出Huang 等人[12]所提出的無證書方案不能抵抗第二類敵手的攻擊，并給出了改進方案。 本文針對于無證書簽名方案中公鑰與持有者之間沒有認證關(guān)系，提出了一種基于密鑰捆綁的無證書簽名方案，通過對用戶自選參數(shù)和公鑰進行密鑰捆綁，可有效防止公鑰替換攻擊，阻斷針對無證書簽名的第一類攻擊者，另一方面該方案中的部分私鑰可以通過所申請的部分私鑰授權(quán)碼廣播吊銷，可以阻斷密鑰泄露后帶來的進一步安全問題。

1 基礎(chǔ)知識

1.1 安全性假設(shè)

定義1 雙線性對[13]（bilinear pairing，BP）

若G1為q 階加法循環(huán)群，G2為q 階乘法循環(huán)群，映射e：G1×G1→G2稱為雙線性對映射則滿足以下3 條性質(zhì)：

1） 雙線性性：e（aP，bQ）ab，其中P，Q∈G1， a，b∈Zq；

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

3） 可計算性：任給P，Q∈G1，e（P，Q）是可以被計算的。

定義2 逆計算性Diffie-Hellman 問題（inverse computational diffie-hellman problem，Inv-CDH）

1.2 改進后的無證書數(shù)字簽名定義

由于在傳統(tǒng)無證書簽名方案中， 用戶公鑰與用戶身份缺乏認證關(guān)系, 使得該簽名方案容易遭受惡意攻擊。 文獻[14]提出基于雙重的無證書短簽名方案，實現(xiàn)了用戶身份與秘密值的綁定，避免了惡意用戶的公鑰替換攻擊，但該方案所提出的雙重的設(shè)置較為復(fù)雜，在實際應(yīng)用中部署較為繁瑣。 本文提出了基于密鑰捆綁的無證書簽名方案，該方案由七個算法組成，其定義如圖1 所示。

圖1 改進的無證書簽名定義Fig.1 Improved certificate-free signature definition

2 基于密鑰捆綁的無證書簽名方案構(gòu)造

方案由7 個算法組成，具體描述如下：

1） 系統(tǒng)建立：給定安全參數(shù)k，選擇階都為素數(shù)q＞2k的加法循環(huán)群G1和乘法循環(huán)群G2，設(shè)P 是G1的生成元，選擇雙線性對e：G1×G1→G2，選擇安全抗碰撞哈希函數(shù)：H1：｛0，1｝*→Zq*，H2：｛0，1｝*→Zq*。KGC 任選一個隨機數(shù)s∈Zq*作為系統(tǒng)主密鑰，秘密保存s，計算ypub=sP∈G1作為系統(tǒng)公鑰，公布系統(tǒng)參數(shù)：params=｛k，G1，G2，e，q，P，ypub，H1，H2｝。

2） 秘密值建立：簽名用戶user 隨機選擇秘密值x∈Zq*，計算并公開用戶部分公鑰y=xP∈G1。

3） 部分私鑰提?。汉灻脩魎ser 身份為ID∈（0，1）*，KGC 隨機選擇v，w∈Zq*，計算V＝vP，W＝wP，Q＝H1（ID，ypub，y，V，W），計算私鑰d=s-1（w+vQ） ，其中V，W 作為用戶user 申請部分私鑰的授權(quán)識別碼，可用于廣播吊銷泄露的部分私鑰，最后KGC 通過安全信道發(fā)送（d，V，W）給用戶。 部分私鑰合理性可以通過等式e（dP，ypub）=e（W+QV，P）驗證。

4） 私鑰建立：簽名用戶user 的私鑰為（x，d）。

5） 公鑰建立（密鑰捆綁）：簽名用戶user 計算：U＝xypub，并將用戶公鑰（y，U，V，W）公開，其中參數(shù)U 用于對KGC 和用戶進行密鑰捆綁，防止公鑰替換，任何人可以用e（U，P）＝e（ypub，y）來驗證有效性。

6） 簽名：簽名用戶user 對消息m∈（0，1）*簽名,得到簽名S 的步驟如下：

①計算h=H2（m，ypub，y，U，V，W）；

7） 簽名驗證：簽名驗證者驗證簽名σ=（m，S），步驟如下：

①計算Q=H1（ID，ypub，y，V，W），這個可以預(yù)計算后一直使用；

②計算h=H2（m，ypub，y，U，V，W）；

③當(dāng)e（S，U＋hypub）=e（W+QV，P）成立，則簽名驗證成功，否則簽名驗證失敗。

方案的正確性證明如下

3 安全性證明

在無證書簽名方案中，其安全模型所討論的敵手[15]主要分為以下兩類：

1） 第一類敵手A（模擬不誠實的用戶）：不知道系統(tǒng)主密鑰和用戶部分私鑰，但可以替換用戶公鑰。

2） 第二類敵手A2（模擬惡意但被動的KGC）：掌握了系統(tǒng)主密鑰和用戶部分私鑰，但不能替換用戶公鑰。

關(guān)于兩類敵手的安全游戲模型的形式化描述詳見文獻[16]，限于篇幅，本文不再贅述。 由于本方案在用戶公鑰建立時進行了密鑰捆綁，用戶與用戶公鑰之間存在關(guān)聯(lián)且可公開驗證，可以避免了第一類敵手的公鑰替換攻擊。 因此本文針對掌握系統(tǒng)主密鑰和部分私鑰的第二類敵手攻擊，給出隨機預(yù)言機下的安全性證明。

定理 在隨機預(yù)言機模型下，針對第二類敵手A2，在適應(yīng)性選擇消息攻擊下本文所提出的無證書簽名方案是存在性不可偽造的。

引理 假設(shè)A2在概率多項式時間t 內(nèi)以不可忽略的概率ε 攻破了本文方案， 記qx，qH1，qH2，qE，qpk，qS分別為敵手A2做秘密值詢問，H1詢問，H2詢問，部分私鑰解析詢問，公鑰詢問以及簽名詢問的次數(shù)；記tx，tH1，tH2，tE，tpk，tS分別為敵手A2做秘密值詢問，H1詢問，H2詢問、部分私鑰解析詢問，公鑰詢問以及簽名詢問的一次所需的時間，則存在概率多項式時間算法C，在時間t′內(nèi)以不可忽略的優(yōu)勢ε′解決Inv-CDH 問題。 其中

記列表Lx，LH1，LH2，LE，Lpk，LS為A2的秘密值詢問，H1詢問，H2詢問，部分私鑰解析詢問，公鑰詢問以及簽名詢問的跟蹤記錄。 A2詢問過程如下：

1） 秘密值詢問：當(dāng)A2對IDi進行秘密值詢問時，查找由數(shù)組（IDi，xIDi，yIDi）構(gòu)成的列表Lx是否存在IDi的記錄，若存在則將查找的值返回給A2，否則：①若IDi≠ID*，則C 隨機選取xIDi∈Zq*，計算yIDi=xIDiP∈G1，并將值xIDi發(fā)送給A2，且將數(shù)組（IDi，xIDi，yIDi）記錄到Lx中；②若IDi＝ID*，則令aP∈G1為用戶部分公鑰yIDi，并將“⊥”返回給A2，同時將數(shù)組（IDi，⊥，yIDi）記錄到Lx中，其中“⊥”表示為空。

2） H1詢問：當(dāng)A2對IDi進行H1詢問時，查找由數(shù)組（IDi，vIDi，wIDi，VIDi，WIDi，QIDi）構(gòu)成的列表LH1是否存在IDi的記錄，若存在則向A2返回對應(yīng)的值，否則：C 隨機選取vIDi，wIDi∈Zq*，計算VIDi＝vIDiP，WIDi＝wIDiP，選取QIDi∈Zq*作為H1（IDi，ypub，yIDi，VIDi，WIDi）的值，將值返回給A2，同時將數(shù)組（IDi，vIDi，wIDi，VIDi，WIDi，QIDi）記錄到LH1中。

3） 部分私鑰詢問：當(dāng)A2對IDi進行部分私鑰詢問時，C 檢查由數(shù)組（IDi，QIDi，vIDi，wIDi，dIDi）構(gòu)成的列表LE中是否存在IDi的記錄，若存在則將值返回給A2，否則：C 查找出LH1中IDi的記錄，計算dIDi=s-1（wIDi＋vIDiQIDi）， 并將dIDi發(fā)送給A2，同時將（IDi，QIDi，vIDi，wIDi，dIDi）記錄到LE中。

4） 公鑰詢問：當(dāng)A2對IDi進行公鑰詢問時，C 檢查由數(shù)組（IDi，yIDi，UIDi，VIDi，WIDi）構(gòu)成的列表Lpk中是否存在IDi的記錄，若存在則將值返回值A(chǔ)2，否則：C 查找出IDi在Lx以及LH1中IDi的記錄，若IDi≠ID*，則計算UIDi=xIDiypub，否則計算UIDi=xIDiypub=yIDis，將（yIDi，UIDi，VIDi，WIDi）返回給A2，并將（IDi，yIDi，UIDi，VIDi，WIDi）記錄到Lpk中。

5） H2詢問：當(dāng)A2對（IDi，mj）進行H2詢問時，查找由數(shù)組（IDi，mj，hj）構(gòu)成的列表LH2是否存在（IDi，mj）的記錄，若存在則向A2返回對應(yīng)的值，否則C 查找列表Lpk中IDi的記錄，若IDi≠ID*，隨機選取hj∈Zq*作為H2（mj，ypub，yIDi，UIDi，VIDi，WIDi）的值，并將hj返回給A2，同時將（IDi，mj，hj）記錄到列表LH2中，否則，將給定的實例中的b∈Zq*作為H2（mj，ypub，yIDi，UIDi，VIDi，WIDi）的值，并將b 返回給A2，同時將數(shù)組（IDi，mj，b）記錄到LH2中。

最后，A2停止詢問，輸出一個有效簽名σ。若簽名σ=（m*，S*）是挑戰(zhàn)身份ID*的，則C 通過查詢所維護的列表Lx，LH1，LH2，LE，Lpk，LS，提取與ID*的相關(guān)記錄數(shù)組，其中：yID*=aP，h=b 為關(guān)于m*的H2詢問值。

以下為解決Inv-CDH 困難問題的優(yōu)勢：

1） A2對哈希函數(shù)H1，H2詢問的應(yīng)答在Zq*中是均勻分布的。

C 解決Inv-CDH 困難問題的優(yōu)勢的下界估計為

而C 所需的多項式時間上界估計為

綜上所述，存在概率多項式時間算法，在時間內(nèi)以不可忽略的優(yōu)勢解決Inv-CDH 問題，這與Inv-CDH問題困難性矛盾。因此在隨機預(yù)言機模型下，針對第二類敵手，在適應(yīng)性選擇消息攻擊下本文所提出的無證書簽名方案是存在性不可偽造的。

4 效率分析

4.1 性能比較

表1 為本文方案性能比較分析，其中，M 代表倍乘運算，E 代表指數(shù)運算，P 代表雙線性對運算。

由表1 可知，在簽名階段本方案僅使用了1 次的倍乘運算，而文獻[4]方案使用了1 次雙線對運算和3次倍乘運算，文獻[6]方案使用了3 次倍乘運算，文獻[7]方案使用了1 次倍乘運算，文獻[11]方案使用了3 次指數(shù)運算和1 次倍乘運算。 本方案在簽名階段的計算量與文獻[7]方案相近，較低于文獻[4，6，11]方案；在簽名驗證階段本方案使用了1 次雙線對運算和1 次倍乘運算。文獻[4]方案使用了4 次雙線對運算和1 次指數(shù)運算，文獻[6]方案使用了2 次雙線對運算和1 次倍乘運算，文獻[7]方案使用了1 次雙線對運算和2 次指數(shù)運算以及1 次倍乘運算，文獻[11]方案使用了3 次雙線對運算，通過對比可知，在此階段本文方案計算量較低于文獻[4，6，7，11]方案。 綜上，本方案計算復(fù)雜度較低，在性能效率方面略優(yōu)于其他方案。

4.2 運行效率比較

在64 位windows7 操作系統(tǒng)、Intel（R） Core（TM） i3-4150 CPU @ 3.50 GHz 的CPU 和DDR3 1 600 MHz 16 G 的內(nèi)存以及華碩B85M-V5 PLUS 主板的運行環(huán)境下， 結(jié)合斯坦福大學(xué)開發(fā)的PBC （Pairing-Based Cryptography）庫，實現(xiàn)本文方案和文獻[4，6，7，10]方案，并比較各個方案在經(jīng)過100 次運行后的平均耗時，其實驗結(jié)果如表2 所示。 由表2 可知，本文方案在簽名階段的平均耗時為0.011 s，在驗證階段平均耗時為0.030 s，方案的平均總耗時為0.098 s。 在方案的平均總耗時上，本文方案與文獻[4]方案相比，減少了約50.5%，與文獻[6]方案相比，減少了約28.5%，與文獻[7]方案相比，減少了約10.1%,與文獻[11]方案相比，減少了約45.6%，由此可知，本文提出的簽名方案具有較高的運行效率。

表1 方案效率分析與比較Tab.1 Analysis and comparison of scheme efficiency

表2 方案運行100 次平均耗時比較Tab.2 The average time-consuming comparison of scheme running 100 times s

5 結(jié)束語

本文提出了一種基于雙線對的無證書簽名方案，并在隨機預(yù)言機的模型下，基于Inv-CDH 困難問題給出了方案的安全性證明。與傳統(tǒng)的無證書簽名方案對比，本文方案實現(xiàn)了公鑰與持有者之間的捆綁認知，防止了公鑰替換攻擊。 通過對比分析可知，本方案具有較高的計算效率。