安全高效的無(wú)雙線性對(duì)的無(wú)證書(shū)簽名方案

胡冰潔，周彥偉，楊 波，張 晶

(1.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安710062；2.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100878；3.西安高新一中 初中部東區(qū)初級(jí)中學(xué)，陜西 西安710075)

2003年，Al-Riyaml等[1]提出了無(wú)證書(shū)公鑰密碼機(jī)制的新密碼學(xué)原理.在該機(jī)制中，用戶的私鑰由密鑰生成中心（Key Generation Center,KGC）和用戶共同生成.由于該機(jī)制可同時(shí)解決傳統(tǒng)公鑰密碼機(jī)制和基于身份密碼機(jī)制的固有問(wèn)題，即證書(shū)管理和密鑰托管，得到大量關(guān)注，并在知識(shí)產(chǎn)權(quán)保護(hù)、電子政務(wù)、網(wǎng)絡(luò)購(gòu)物等方面應(yīng)用廣泛.

2004年，文獻(xiàn)[2]提出無(wú)證書(shū)簽名方案，引起學(xué)者的廣泛關(guān)注，隨后大量的無(wú)證書(shū)簽名方案[3-15]相繼被提出.2006年，文獻(xiàn)[3]基于雙線性對(duì)運(yùn)算提出一個(gè)無(wú)證書(shū)簽名方案，但是該方案無(wú)法抵抗第一類敵手的公鑰替換攻擊.為對(duì)此安全缺陷進(jìn)行改進(jìn).2008年，文獻(xiàn)[4]提出一個(gè)改進(jìn)方案，在該方案中，用戶部分私鑰由短簽名方案生成，并直接和用戶選取的秘密值產(chǎn)生簽名的私鑰，雖然該方案在安全性方面優(yōu)于文獻(xiàn)[3]，但是在計(jì)算效率方面，該方案仍基于雙線性對(duì)運(yùn)算構(gòu)造，使得方案的計(jì)算效率和實(shí)用性較低.2010年，文獻(xiàn)[5]在不使用雙線性對(duì)運(yùn)算的前提下，設(shè)計(jì)了一個(gè)具有強(qiáng)安全性的無(wú)證書(shū)簽名方案，但是該方案使用了大量的指數(shù)運(yùn)算，在一定程度上降低了方案的計(jì)算效率.2012年，文獻(xiàn)[6]提出一個(gè)無(wú)雙線性對(duì)的無(wú)證書(shū)簽名方案，并在隨機(jī)預(yù)言機(jī)模型下基于橢圓曲線離散對(duì)數(shù)問(wèn)題對(duì)方案的不可偽造性進(jìn)行了證明.然而文獻(xiàn)[7]指出該方案存在安全缺陷，即無(wú)法抵抗第一類敵手的公鑰替換攻擊；并針對(duì)此安全缺陷提出了一個(gè)改進(jìn)方案，遺憾的是，該方案仍無(wú)法抵抗敵手的公鑰替換攻擊，使得該方案無(wú)法滿足實(shí)際應(yīng)用環(huán)境對(duì)簽名機(jī)制高安全性的要求.2014年，文獻(xiàn)[8]采用改變傳統(tǒng)無(wú)證書(shū)算法順序的方式對(duì)文獻(xiàn)[7]的方案進(jìn)行改進(jìn)，以KGC公告板形式公開(kāi)用戶公鑰，從而進(jìn)一步對(duì)KGC的行為進(jìn)行約束，然而該方案仍無(wú)法抵抗第一類敵手的公鑰替換攻擊.2016年，文獻(xiàn)[9]通過(guò)將簽名階段選取的隨機(jī)數(shù)與消息相關(guān)的哈希函數(shù)值進(jìn)行綁定的方法對(duì)文獻(xiàn)[8]的方案進(jìn)行改進(jìn)，提出9個(gè)相關(guān)的改進(jìn)方案，并在隨機(jī)預(yù)言機(jī)模型下基于橢圓曲線離散對(duì)數(shù)問(wèn)題對(duì)效率最優(yōu)方案的不可偽造性進(jìn)行證明，該方案依然存在安全缺陷，即無(wú)法抵抗第一類敵手的公鑰替換攻擊.2018年，文獻(xiàn)[10-14]分別提出了無(wú)證書(shū)簽名方案，文獻(xiàn)[10]的方案不能抵抗第一類敵手的公鑰替換攻擊；雖然文獻(xiàn)[11-12]所提出的方案是安全的，但是在簽名階段和驗(yàn)證階段均使用了大量的點(diǎn)乘運(yùn)算，在一定程度上影響了方案的計(jì)算效率和實(shí)用性；文獻(xiàn)[13-14]在方案的設(shè)計(jì)中使用了復(fù)雜的雙線性對(duì)運(yùn)算，并且無(wú)法抵抗第一類敵手的公鑰替換攻擊.2019年，文獻(xiàn)[15]基于物聯(lián)網(wǎng)的實(shí)際應(yīng)用環(huán)境提出了一個(gè)強(qiáng)不可偽造的無(wú)證書(shū)簽名方案，雖然該方案是安全的，但是其在簽名、驗(yàn)證階段均使用了雙線性對(duì)運(yùn)算，使得方案的計(jì)算效率較低.

安全性分析表明文獻(xiàn)[3,6-10]的方案存在安全缺陷，即不能抵抗第一類敵手的公鑰替換攻擊，未滿足實(shí)際應(yīng)用環(huán)境對(duì)簽名機(jī)制強(qiáng)安全性的要求.文獻(xiàn)[4,15]在構(gòu)造方案時(shí)使用了復(fù)雜的雙線性對(duì)運(yùn)算，使得方案的計(jì)算效率較低.另外，文獻(xiàn)[9]的方案不能抵抗敵手的公鑰替換攻擊，原因在于未考慮到在用戶密鑰生成算法中加強(qiáng)用戶公鑰元素間的聯(lián)系.

因此，為設(shè)計(jì)一個(gè)同時(shí)滿足強(qiáng)安全性和高計(jì)算效率的無(wú)證書(shū)簽名方案，本文采用不使用雙線性對(duì)運(yùn)算的思路，在用戶密鑰生成算法中，通過(guò)哈希函數(shù)加強(qiáng)用戶公鑰元素間聯(lián)系的方法，設(shè)計(jì)了一個(gè)安全高效的無(wú)證書(shū)簽名方案，并在隨機(jī)預(yù)言機(jī)模型下基于橢圓曲線離散對(duì)數(shù)問(wèn)題對(duì)方案的不可偽造性進(jìn)行證明，同時(shí)對(duì)方案的無(wú)密鑰托管性、不可否認(rèn)性以及前后向安全性進(jìn)行分析和說(shuō)明.經(jīng)安全分析可知，本文方案在安全性方面，相較于文獻(xiàn)[9]有較大的提升，即本文方案對(duì)兩類敵手可同時(shí)具有不可偽造性；經(jīng)效率分析可知，相比于文獻(xiàn)[4,15]，本文方案在簽名和驗(yàn)證階段均未使用雙線性對(duì)運(yùn)算.因此，與現(xiàn)有部分方案相比，本文方案滿足現(xiàn)實(shí)應(yīng)用環(huán)境下對(duì)簽名機(jī)制的強(qiáng)安全性和高計(jì)算效率的要求，更適合用于寬帶受限的網(wǎng)絡(luò)環(huán)境中.

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

1.2 無(wú)證書(shū)簽名方案及安全模型文獻(xiàn)[6]詳細(xì)的介紹了無(wú)證書(shū)簽名方案的基礎(chǔ)結(jié)構(gòu)，同時(shí)定義了無(wú)證書(shū)簽名方案的安全模型.在該模型中，攻擊者被劃分為兩類敵手：敵手A1（惡意的用戶，即第一類敵手）可替換用戶公鑰但不知道系統(tǒng)的主密鑰；敵手A2（惡意的KGC，即第二類敵手）知道系統(tǒng)的主密鑰但是不可替換用戶公鑰.

不可偽造性的具體定義詳見(jiàn)文獻(xiàn)[6].

1.3 分叉引理在方案的安全性證明中，若挑戰(zhàn)者C利用敵手A的一次成功偽造無(wú)法解決困難問(wèn)題，則考慮使用分叉引理，以得到A的另一個(gè)成功偽造.分叉引理的實(shí)質(zhì)為A輸出關(guān)于消息m的兩個(gè)有效簽名的概率至少等于A在隨機(jī)預(yù)言機(jī)H所維持的詢問(wèn)-應(yīng)答列表中找到一個(gè)分叉的概率.

2 無(wú)證書(shū)簽名方案

3 安全性證明

參考文獻(xiàn)[9]，我們?cè)陔S機(jī)預(yù)言機(jī)模型下基于橢圓曲線離散對(duì)數(shù)問(wèn)題對(duì)方案的安全性和不可偽造性進(jìn)行證明.

4 現(xiàn)有無(wú)證書(shū)簽名方案的安全性分析

經(jīng)安全性分析得知，文獻(xiàn)[6-9]的方案不能抵抗敵手的公鑰替換攻擊原因在于：未考慮到在用戶密鑰生成算法中加強(qiáng)用戶公鑰元素間的聯(lián)系，或在簽名階段未將選取的隨機(jī)數(shù)與消息進(jìn)行關(guān)聯(lián).以文獻(xiàn)[9]的方案（方案1）為例，在此章節(jié)證明使用本文方案可解決其安全缺陷，使其達(dá)到其所聲稱的安全性，即滿足不可偽造性.

文獻(xiàn)[9]詳細(xì)介紹了其方案的各個(gè)算法，此處不再進(jìn)行贅述.

文獻(xiàn)[9]在生成用戶密鑰時(shí)未受到用戶的約束，使得敵手A1可進(jìn)行公鑰替換攻擊.而本文方案在設(shè)計(jì)用戶密鑰生成算法時(shí)通過(guò)哈希函數(shù)加強(qiáng)用戶各公鑰元素間的關(guān)聯(lián)程度.使用本文方案，敵手A1無(wú)法對(duì)文獻(xiàn)[9]的簽名過(guò)程進(jìn)行偽造，解決了其方案的安全缺陷.

5 性能及效率分析

本節(jié)對(duì)方案的性能（無(wú)密鑰托管性、不可否認(rèn)性、前后向安全性）以及效率進(jìn)行分析和說(shuō)明.

5.1 性能分析（1）無(wú)密鑰托管性 在本文方案中，由于用戶的私鑰Ski=(xi,di) 是由KGC生成的部分私鑰di和用戶選取的秘密值xi共同組成，所以，如果KGC想要掌握用戶的完整私鑰Ski=(xi,di) 以偽造簽名和解密密文，必須獲得xi，但xi是用戶隨機(jī)選取的，所以KGC無(wú)法獲得.另外，如果KGC想通過(guò)其掌握的部分公鑰信息Xi求解xi， 因?yàn)閄i=xi·P，則意味著KGC要求解橢圓曲線離散對(duì)數(shù)困難問(wèn)題.

因此，本文方案具有無(wú)密鑰托管性.

（2）不可否認(rèn)性 由安全性證明可知，本文所提方案對(duì)具有不同能力的兩種敵手而言，同時(shí)滿足不可偽造性.接收方將信息簽名 σ=(T,S)，消息mi和發(fā)送者身份Di的公鑰對(duì)Pki=(Xi,Ri)送給驗(yàn)證者，驗(yàn)證者在不需要獲得發(fā)送者和其的私鑰信息的前提下，僅需要進(jìn)行簡(jiǎn)單的計(jì)算即可確定發(fā)送者的身份.通過(guò)這種方法，可有效避免發(fā)送者的否認(rèn)行為.驗(yàn)證者所做計(jì)算如下：

由表1可知，文獻(xiàn)[9-10,13-14]存在安全缺陷，其中文獻(xiàn)[14]完全是不安全，文獻(xiàn)[9-10,13]無(wú)法抵抗第一類敵手的公鑰替換攻擊，并且文獻(xiàn)[13-14]在驗(yàn)證階段均使用了復(fù)雜的雙線性對(duì)運(yùn)算，導(dǎo)致其計(jì)算效率較低；雖然文獻(xiàn)[11-12,15]對(duì)第一類敵手和第二類敵手而言均具有不可偽造性，但是其在計(jì)算效率方面仍有待提高.具體來(lái)說(shuō)，文獻(xiàn)[11-12]在簽名和驗(yàn)證階段均使用了多個(gè)點(diǎn)乘運(yùn)算，文獻(xiàn)[15]在簽名階段使用了大量的指數(shù)運(yùn)算，在驗(yàn)證階段使用了多個(gè)雙線性對(duì)運(yùn)算.而本文方案在構(gòu)造過(guò)程中采用了不使用雙線性對(duì)運(yùn)算的思路，對(duì)兩類敵手可同時(shí)滿足不可偽造性，并且在簽名階段中僅使用了3個(gè)點(diǎn)乘運(yùn)算，在驗(yàn)證階段中僅使用了4個(gè)點(diǎn)乘運(yùn)算.因此，與現(xiàn)有部分方案相比，本文方案具有更強(qiáng)的安全性和更高的計(jì)算效率.

表1 效率分析表Tab.1 The tableof efficiency analysis

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

本文分析現(xiàn)有的無(wú)證書(shū)簽名方案，發(fā)現(xiàn)部分方案存在以下情況：部分方案在構(gòu)造方案時(shí)采用了雙線性對(duì)運(yùn)算[13-15]，由于雙線性對(duì)運(yùn)算的計(jì)算量開(kāi)銷較大，導(dǎo)致方案的計(jì)算效率和實(shí)用性低下；部分不采用雙線性對(duì)運(yùn)算構(gòu)造的方案[11-12]在簽名、驗(yàn)證過(guò)程中大量使用點(diǎn)乘運(yùn)算，在一定程度上，使得方案的計(jì)算效率和實(shí)用性降低；另外，部分方案[9]存在安全缺陷，即無(wú)法抵抗第一類敵手的公鑰替換攻擊，經(jīng)安全性分析得知，造成此安全缺陷的原因?yàn)樵诿荑€生成過(guò)程中忽略公鑰各元素間的聯(lián)系或在簽名階段中未將所選取的隨機(jī)數(shù)與消息進(jìn)行關(guān)聯(lián).針對(duì)此情況，本文設(shè)計(jì)了一個(gè)安全高效的無(wú)雙線性對(duì)的無(wú)證書(shū)簽名方案，并在隨機(jī)預(yù)言機(jī)模型下基于橢圓曲線離散對(duì)數(shù)問(wèn)題對(duì)方案的不可偽造性進(jìn)行證明，同時(shí)對(duì)方案的無(wú)密鑰托管性、不可否認(rèn)性以及前后向安全性進(jìn)行分析和說(shuō)明.經(jīng)安全分析可知，本文方案可解決現(xiàn)有部分方案的安全缺陷，使其達(dá)到其所聲稱的安全性，即滿足不可偽造性.另外，本文方案在計(jì)算效率方面均具有較大的提升，即滿足實(shí)際應(yīng)用環(huán)境對(duì)簽名機(jī)制強(qiáng)安全性、高計(jì)算效率的要求.在傳統(tǒng)密碼學(xué)基礎(chǔ)原語(yǔ)的研究中，往往會(huì)忽略了由于泄露與通信雙方相關(guān)的秘密狀態(tài)信息而對(duì)其安全性所造成的影響,如何在泄露的現(xiàn)實(shí)環(huán)境中依然保持無(wú)雙線性對(duì)的無(wú)證書(shū)簽名方案的高機(jī)密性值得進(jìn)一步研究[18].