一種基于密鑰捆綁的無(wú)證書(shū)簽名方案

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

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

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

1 基礎(chǔ)知識(shí)

1.1 安全性假設(shè)

定義1 雙線(xiàn)性對(duì)[13]（bilinear pairing，BP）

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

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

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

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

定義2 逆計(jì)算性Diffie-Hellman 問(wèn)題（inverse computational diffie-hellman problem，Inv-CDH）

1.2 改進(jìn)后的無(wú)證書(shū)數(shù)字簽名定義

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

圖1 改進(jìn)的無(wú)證書(shū)簽名定義Fig.1 Improved certificate-free signature definition

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

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

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

2） 秘密值建立：簽名用戶(hù)user 隨機(jī)選擇秘密值x∈Zq*，計(jì)算并公開(kāi)用戶(hù)部分公鑰y=xP∈G1。

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

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

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

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

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

7） 簽名驗(yàn)證：簽名驗(yàn)證者驗(yàn)證簽名σ=（m，S），步驟如下：

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

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

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

方案的正確性證明如下

3 安全性證明

在無(wú)證書(shū)簽名方案中，其安全模型所討論的敵手[15]主要分為以下兩類(lèi)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C 解決Inv-CDH 困難問(wèn)題的優(yōu)勢(shì)的下界估計(jì)為

而C 所需的多項(xiàng)式時(shí)間上界估計(jì)為

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

4 效率分析

4.1 性能比較

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

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

4.2 運(yùn)行效率比較

在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 主板的運(yùn)行環(huán)境下， 結(jié)合斯坦福大學(xué)開(kāi)發(fā)的PBC （Pairing-Based Cryptography）庫(kù)，實(shí)現(xiàn)本文方案和文獻(xiàn)[4，6，7，10]方案，并比較各個(gè)方案在經(jīng)過(guò)100 次運(yùn)行后的平均耗時(shí)，其實(shí)驗(yàn)結(jié)果如表2 所示。 由表2 可知，本文方案在簽名階段的平均耗時(shí)為0.011 s，在驗(yàn)證階段平均耗時(shí)為0.030 s，方案的平均總耗時(shí)為0.098 s。 在方案的平均總耗時(shí)上，本文方案與文獻(xiàn)[4]方案相比，減少了約50.5%，與文獻(xiàn)[6]方案相比，減少了約28.5%，與文獻(xiàn)[7]方案相比，減少了約10.1%,與文獻(xiàn)[11]方案相比，減少了約45.6%，由此可知，本文提出的簽名方案具有較高的運(yùn)行效率。

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

表2 方案運(yùn)行100 次平均耗時(shí)比較Tab.2 The average time-consuming comparison of scheme running 100 times s

5 結(jié)束語(yǔ)

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