基于區(qū)塊鏈的無證書簽密方案

張?zhí)煜?王利朋,付俊俊,崔 馳,靳夢璐

(1.河南省鶴壁市廣播電視臺,河南 鶴壁 458030； 2.鄭州師范學(xué)院,河南 鄭州 450044； 3.北京大學(xué),北京 100871)

0 引 言

消息通信服務(wù)對簽密過程的基本安全要求是機密性和身份驗證，其中機密性通過加密來實現(xiàn)，身份驗證通過簽名來實現(xiàn)。傳統(tǒng)的“先簽名后加密”方案時間消耗較高。1997年，Zheng[1]首次提出了簽密概念，它將簽名和加密在同一個邏輯步驟中完成，與傳統(tǒng)方案相比，具有更少的計算量和較低的通信成本，實現(xiàn)了效率的提高，是一種較為理想的通信服務(wù)方式。傳統(tǒng)的公鑰密碼體制[2]是基于證書的密碼體制，用戶需要向受信任的證書頒發(fā)中心申請證書，證書將公鑰與用戶的身份綁定。由于對證書的管理成本過高，不利于大規(guī)模應(yīng)用。1984年Shamir[3]提出了基于身份的密碼體制，解決了證書管理問題?；谏矸莸墓€密碼體制直接使用用戶的身份信息(如ID或電話號碼)作為用戶的公鑰，而私鑰需要由可信第三方—密鑰生成中心(Key Generation Center, KGC)生成。由于KGC提供用戶的完整私鑰，攻擊者可攻擊KGC偽造用戶的合法私鑰對密文進行解密，因此存在KGC管理不到位的問題。2003年，Al-Riyami等人[4]提出無證書的公鑰密碼體制，在此密鑰系統(tǒng)中KGC只生成用戶的部分私鑰，需要用戶生成剩余私鑰并合成完整的私鑰。用戶的公鑰由用戶的身份信息和系統(tǒng)參數(shù)共同計算得出，這解決了基于身份的密碼體制所存在的KGC管理不足的問題。自此，基于無證書簽密方案的研究成為了簽密領(lǐng)域的研究熱門之一。Yu和Wu等人[5-6]提出了基于雙線性對的無證書簽密方案。但Selvi等人[7]方案中指出了Yu方案沒有實現(xiàn)不可否認性和機密性的證明，同樣Wu方案也沒有解決機密性的問題。Barreto等人[8]提出了在簽密和解密過程中不使用雙線性對，但在密鑰生成階段需使用雙線性對的簽密方案運算。俞惠芳和Li等人[9-10]基于雙線性對映射的方法提出了可證明安全性的無證書簽密方案，并在隨機預(yù)言機模型下證明了安全性。但由于雙線性對的運算開銷大，導(dǎo)致基于雙線性對的簽密方案存在計算量大的問題。針對上述的不足，不使用雙線性對的簽密方案[11-18]相繼被提出。朱輝和劉文浩等人[11-12]提出了無雙線性對的無證書簽密方案，并且在隨機預(yù)言機的模型下，基于離散對數(shù)(Discrete Logarithm, DL)問題和計算性Diffie-Hellman(CDH)難題證明了方案的機密性和不可否認性。無證書的簽密機制具有無密鑰托管的優(yōu)勢，國內(nèi)外的研究者分別提出了將無證書簽密機制與物聯(lián)網(wǎng)[17-21]、無線傳感器[22]等網(wǎng)絡(luò)環(huán)境相結(jié)合的簽密方案。

針對上述問題，本文提出一種基于離散對數(shù)(DL)問題與計算性Diffie-Hellman(CDH)難題的簽密方案，并對方案的機密性和不可偽造性等安全性進行證明。同時，通過性能分析將本方案與基于橢圓曲線簽密方案[18,23-24]的效率進行對比。利用區(qū)塊鏈的不可篡改與可溯源的特性對簽密驗證結(jié)果進行上鏈存儲以實現(xiàn)不可否認性。

1 相關(guān)工作

1.1 離散對數(shù)(DL)問題

1.2 計算性Diffie-Hellman(CDH)問題

1.3 哈希函數(shù)

哈希函數(shù)[25-26]是一種壓縮映射函數(shù)，可以將不同長度的消息映射成較短等長的消息串。具有如下性質(zhì)：

1)正向計算簡單性：給定哈希函數(shù)h和消息m,計算h(m)是簡單的。

2)逆向計算困難性：對于給定的消息y，計算h(m)=y中的m是困難的。

3)防碰撞性：對于不同的消息m1、m2，使h(m1)=h(m2)在計算上是不可行的。

1.4 區(qū)塊鏈

2008年，中本聰在一本關(guān)于比特幣的白皮書[27]中第一次提出了區(qū)塊鏈這一概念。2009年第一塊序號為0的創(chuàng)世區(qū)塊誕生。自此，基于區(qū)塊鏈的數(shù)字貨幣相繼出現(xiàn)[28]。目前已經(jīng)從以比特幣為代表的數(shù)字貨幣的區(qū)塊鏈1.0時代，經(jīng)過以以太坊為代表的智能合約區(qū)塊鏈2.0時代，進入到在社會治理領(lǐng)域的去中心化信任區(qū)塊鏈3.0時代。

區(qū)塊鏈是一種通過P2P網(wǎng)絡(luò)節(jié)點構(gòu)建的分布式賬本，能夠在沒有可信第三方的協(xié)助下對數(shù)據(jù)或資源進行溯源。區(qū)塊鏈本質(zhì)上是一個去中心化數(shù)據(jù)庫，具有匿名性、公開透明、可追溯性和不可篡改等特性?；谶@些特性，區(qū)塊鏈從最初的數(shù)字貨幣擴展到各行各業(yè)中，被廣泛應(yīng)用于如金融、醫(yī)療和物流信息[29-33]等多個場景。

2 本文方案

2.1 方案框架

本文利用區(qū)塊鏈技術(shù)，基于離散對數(shù)難題，提出一種簽密方案。

如圖1所示，在本方案的簽密模型中，主要包括5個流程。

1)系統(tǒng)初始化。給定一個安全參數(shù)χ，KGC計算生成系統(tǒng)公開參數(shù)params和系統(tǒng)主私鑰s。

圖1 簽密模型圖

2)用戶密鑰生成。用戶根據(jù)身份信息ID生成部分私鑰，通過安全通道發(fā)送給KGC，KGC接收到用戶發(fā)送的部分私鑰并生成另一部分私鑰信息，并通過安全通道發(fā)送給用戶，用戶合成個人公私鑰信息。

3)消息加密。發(fā)送者根據(jù)個人公私鑰與接收者的公鑰信息對消息M進行簽名加密形成密文信息c，并將密文信息發(fā)送給接收者。

4)消息解密。接收者接收到密文消息c，根據(jù)接收者的私鑰信息與發(fā)送者的公鑰信息對密文進行解密并驗證。

5)消息上鏈。接收者將接收到的密文信息c和驗證結(jié)果上傳至區(qū)塊鏈。

2.2 方案步驟

1)系統(tǒng)初始化。

KGC運行此算法生成系統(tǒng)密鑰和系統(tǒng)公共參數(shù)，由下列5步組成：

①選取系統(tǒng)安全參數(shù)χ作為輸入，KGC選取大素數(shù)P形成循環(huán)群G，g為循環(huán)群G的生成元。

④選取一個已存在的對稱加解密算法k,Ek,Dk，其中k為對稱密鑰。

⑤公布系統(tǒng)公共參數(shù)params=〈P,G,g,Ppub,Ek,Dk,H0,H1,H2,H3〉，保存系統(tǒng)主密鑰s。

2)用戶注冊。

KGC和用戶合作完成此算法，合成用戶的公鑰與私鑰，由下面4步組成：

③用戶ID接收到KGC發(fā)送的u、D，計算等式gu=D·gH0(ID,XD)·Ppub·gH0(ID,Ppub)。如果等式成立，則用戶計算部分私鑰y=u-H0(ID,Ppub)。用戶通過SK=x+y合成私鑰。如果等式不成立，用戶拒絕接收u、D，并通知KGC重新發(fā)送。

④用戶計算PK=X·D作為自己的公鑰并廣播PK。

3)消息加密。

此算法由發(fā)送者Sen完成，接收者Rec的身份信息為IDRec。流程由下面5步組成：

②計算K=[PKRec·Ppub·gH0(IDRec,PKRec)]r和α=H1(IDRec,R,K)。

③計算k=H2(α,R)，用密文k對消息M進行加密Z=Ek(M||IDSen)。

④計算h=H3(M||IDSen,R,α)和v=SKSen+rh。

⑤密文內(nèi)容c=〈R,Z,h,v〉，將密文信息發(fā)送給接收者Rec。

4)消息解密。

此算法由接收者Rec完成，只有授權(quán)過的接收者才能成功運行解密算法。接收者Rec接收到密文c=〈R,Z,h,v〉運行解密算法。由下面4步組成：

①計算K=RSKRec和α=H1(IDRec,R,K)。

②計算k=H2(α,R)，用密鑰k解密消息M||IDSen=Dk(Z)。

③計算h′=H3(M||IDSen,R,α)，驗證等式h′=h，如果成立，執(zhí)行下一步；否則拒絕消息M退出解密算法。

④使用發(fā)送者的公鑰信息，驗證等式gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh，若成立，接收消息M，反之，拒絕接收消息M。

5)消息上鏈。

此算法由接收者Rec完成，接收者正確解密出消息M后，將密文信息c=〈R,Z,h,v〉與等式gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh的驗證結(jié)果上傳到區(qū)塊鏈上。當(dāng)對密文信息或發(fā)送者身份信息存在爭議時，可以從區(qū)塊鏈上查看已上傳的數(shù)據(jù)信息。

3 安全性分析

3.1 正確性分析

定理1 用戶注冊時驗證部分私鑰信息等式gu=D·gH0(ID,XD)·Ppub·gH0(ID,Ppub)成立。

證明：

gu=g[d+H0(ID,XD)+s+H0(ID,Ppub)]

=gd·gH0(ID,XD)·Ppub·gH0(ID,Ppub)

=D·gH0(ID,XD)·Ppub·gH0(ID,Ppub)

原式得證，等式gu=D·gH0(ID,XD)·Ppub·gH0(ID,Ppub)成立，則用戶收到的部分私鑰信息正確。

定理2 接收者接收到密文消息后，計算公式K=RSKRec，等式RSKRec=[PKRec·Ppub·gH0(IDRec,PKRec)]r成立。

證明：

RSKRec=[PKRec·Ppub·gH0(IDRec,PKRec)]r

gr·(x+u-H0(IDRec,Ppub))=(X·D)r·gs·r·gH0(IDRec,PKRec)·r

gr·(x+d+H0(IDRec,XD)+s+H0(IDRec,Ppub)-H0(IDRec,Ppub))

=(gx·gd)r·gs·r·gH0(IDRec,PKRec)·r

gr·(x+d)+s·h+H0(IDRec,PKRec)·h=gr·(x+d)+s·h+H0(IDRec,PKRec)·h

原式得證，等式RSKRec=[PKRec·Ppub·gH0(IDRec,PKRec)]r成立，則接收者收到的密文消息正確。

定理3 接收者驗證發(fā)送者身份的等式gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh成立。

證明：

gv=gSKSen+r·h

=g(x+y)·gr·h

=g(x+d+H0(IDRec,XD)+s+H0(IDRec,Ppub)-H0(IDRec,Ppub))·Rh

=X·D·gH0(IDRec,XD)·Ppub·Rh

=PKSen·gH0(IDRec,PKSen)·Ppub·Rh

原式得證，等式gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh成立，則發(fā)送者的身份信息正確。

3.2 安全性分析

3.2.1 機密性

定理4A1類敵手的機密性。若敵手A1能以不可忽略的優(yōu)勢ε在多項式時間內(nèi)贏得相關(guān)游戲，敵手A1最多進行qSK次私鑰生成詢問以及qs次簽密詢問，則算法F能以不可忽略的優(yōu)勢Adv(F)≥ε·(1-qSK/2k)2/(e(qs+1))在多項式時間內(nèi)解決CDH問題。

H0詢問：當(dāng)算法F收到A1對H0的詢問,,時，若存在記錄∈L0，∈L0,∈L0則返回相應(yīng)的記錄給A1；若沒有相應(yīng)記錄，A1先對IDi進行公鑰生成詢問，而后返回表L0中相應(yīng)的h0給A1。

公鑰生成詢問：收到A1對IDi的公鑰生成詢問時，算法F進行如下操作。

1)若存在記錄∈LPK，返回PKi=XiDi給A1。

私鑰生成詢問：當(dāng)算法F收到A1對IDi的私鑰生成詢問時，進行如下操作。

1)若存在記錄∈LSK，返回SKi=xi+yi給A1。

2)若無相應(yīng)記錄，在對IDi進行公鑰生成詢問后，再在表LSK中查找相應(yīng)的元組，并返回SKi=xi+yi給A1。

簽密詢問：當(dāng)算法F收到敵手A1對的簽密詢問時(A1對IDSen已經(jīng)進行了公鑰生成詢問)，則F在LPK中查詢對應(yīng)的元組，并進行如下操作。

1)若ηSen=1，則算法F終止模擬。

2)算法F在表LSK和表LPK中分別查找IDSen及IDRec對應(yīng)的元組和，運行算法簽密(params,IDSen,IDRec,SKSen,PKRec,m)，生成相應(yīng)的簽密文c=〈R,Z,h,v〉，返回c給A1。

解簽密詢問：當(dāng)算法F收到A1對元組的解簽密詢問時(A1對IDRec已經(jīng)進行了公鑰生成詢問)，在LPK中查詢對應(yīng)的元組，并進行如下操作。

1)若∈LPK，并且ηRec=0，算法F分別在表LSK與表LPK中查詢相對應(yīng)的元組和,運行解簽密算法(params,IDSen,IDRec,SKRec,PKSen,c)，返回消息M給A1，若輸入的密文c無效，則算法F終止模擬。

2)若∈LPK，并且ηRec=1，當(dāng)∈L0,∈L1時，計算M||IDSen=Dk(Z)，若gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh成立，則返回M給A1，否則終止模擬。

3)若表LPK中不存在元組(表示公鑰被替換)，當(dāng)∈L0，∈L1時，計算M||IDSen=Dk(Z)，若gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh成立，則返回M給A1，否則終止模擬。

挑戰(zhàn)：敵手A1輸出2個希望挑戰(zhàn)的身份(IDSen,IDRec)和2個等長的明文消息(M1,M2)。

收到A1的挑戰(zhàn)信息后，算法F對身份IDRec進行了公鑰生成詢問，獲取表LPK中對應(yīng)元組，并進行如下操作。

1)若ηRec=0，則算法終止模擬。

敵手A1經(jīng)過概率多項式時間次數(shù)的上述詢問后輸出對η的猜測，η′←{0,1}，如果η=η′，算法就輸出R(e1+e2)r-1=XDgsgh0作為CDH問題的有效解；如果η≠η′，算法F沒有解決CDH問題。

算法F為A1模擬了真實的攻擊環(huán)境，如果F在模擬過程中未終止，且敵手A1以不可忽略的優(yōu)勢攻破了本方案的機密性，則算法F輸出CDH問題的有效解。

令事件ξ1表示敵手A1對挑戰(zhàn)身份IDSen和IDRec沒有進行過私鑰生成詢問，Pr[ξ1]≥(1-qSK/2k)2；令事件ξ2表示在詢問階段算法F未終止，Pr[ξ2]≥(1-δ)qS，當(dāng)qS足夠大時，(1-δ)qS→e-1,Pr[ξ2]≥e-1；令ξ3事件表示在挑戰(zhàn)階段算法F未終止，Pr[ξ3]=δ；ξ1∩ξ2∩ξ3表示模擬過程中算法不終止，Pr[ξ1∩ξ2∩ξ3]≥(1-qSK/2k)2/(e(qS+1))。

綜上所述，如果算法F在模擬過程中未終止，且敵手A1以不可忽略的優(yōu)勢ε攻破了本方案的機密性，則算法F能以優(yōu)勢Adv(F)≥ε·(1-qSK/2k)2/(e(qS+1))輸出CDH問題的有效解。

證畢。

定理5A2類敵手的機密性。在隨機預(yù)言機模型中，若敵手A2能以不可忽略的優(yōu)勢ε在多項式時間內(nèi)贏得相關(guān)游戲，敵手A2最多進行qSK次私鑰生成詢問以及qs次簽密詢問，則算法F能以不可忽略的優(yōu)勢Adv(F)≥ε·(1-qSK/2k)2/(e(qs+1))在多項式時間內(nèi)解決CDH問題

本定理的證明思路同定理4，不再贅述。

3.2.2 不可偽造性

對簽名進行偽造的主要有2類人，一類是Rec本人，一類是除接收者Rec以外的攻擊者。

攻擊者想要偽造發(fā)送者Sen生成密文〈R′,Z′,h′,v′〉使Rec的驗證等式gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh成立。在此過程中攻擊者需從最初的簽密中解出后續(xù)所需要的一些參數(shù)k、r，求解這些參數(shù)一定會遇到求解離散對數(shù)問題，這是在多項式時間內(nèi)無法破解的。

在解密過程中，接收者Rec偽造簽名，此時接收者Rec知道的信息有M、R、Z、h、v。對于簽密過程中的等式v=SKSen+rh，由R=gr求解r是求解離散對數(shù)難題，攻擊者無法在有效時間內(nèi)通過計算求解。且該等式中含有2個未知變量SKSen和r，而SKSen是發(fā)送者Sen的個人私鑰，由發(fā)送者個人秘密保存，攻擊者也無法獲得，因此，攻擊者無法偽造簽名。

3.2.3 不可否認性

方案具有公開驗證性，接收者Rec通過計算等式gv=PKSen·gH0(IDSen,PKSen)·Ppub·Rh驗證發(fā)送者Sen的身份信息，并將結(jié)果上傳至區(qū)塊鏈。因區(qū)塊鏈具有公開性和不可偽造性的特性，因此，可以實現(xiàn)簽名的不可否認性。

3.2.4 匿名性

4 性能分析

本章將從計算復(fù)雜度分析與仿真實驗2個方面對簽密算法進行對比。

4.1 計算復(fù)雜度分析

本文定義以下符號來表示方案中所使用的運算，如表1所示。

表1 復(fù)雜度符號表示

相較于模乘、冪模等運算，模加與模減運算的時間消耗低，故在此省略不計。其中Tmul

表2 性能分析

4.2 仿真實驗

本文中的仿真實驗采用的操作系統(tǒng)為Windows 10、Intel CPU i7-9750H、My Eclipse2015 CI。將本文與方案[18,23-24]進行仿真實驗數(shù)據(jù)對比，統(tǒng)計初始化、注冊、簽密和解密4個步驟的耗時，時間單位為ms。文獻[18]中涉及的變量n取值為5。文獻[18,23-24]所需的橢圓曲線參數(shù)參考了JPBC庫中Type A類。本文方案所涉及的大數(shù)P取8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791。

圖2中的數(shù)據(jù)重復(fù)實驗50次取平均值。如圖2所示，在初始化階段，文獻[18,23-24]使用橢圓曲線的點乘運算，單次運算的時間消耗約為15 ms，而本文方案在初始化階段使用冪模運算，時間消耗低于2 ms。本文的注冊階段和簽密方案的時間耗時都在3 ms左右。文獻[18,24]在注冊階段的時間效率都比本方案低。在簽密階段，文獻[18,23-24]的時間效率較低。在解密階段，文獻[18]涉及聚合簽密個數(shù)n，本實驗過程中n取值為5。從圖2中可以看出，文獻[18]的單個運算效率和文獻[23-24]的運算效率都比本文的解密效率低。因此，本文方案在整個簽密流程中都有著較高的效率。

圖2 簽密算法執(zhí)行時間

本文采用EOS環(huán)境模擬本文方案中區(qū)塊鏈的運行情況，其設(shè)備的具體配置如表3所示。

表3 區(qū)塊鏈環(huán)境配置表

本文主要利用了區(qū)塊鏈的不可篡改性和可溯源性，將密文和接收者對發(fā)送者身份驗證的結(jié)果上鏈到區(qū)塊鏈中。實驗測試的區(qū)塊鏈運行平均耗時如圖3所示。

圖3 區(qū)塊鏈運行平均耗時

從圖3中可以看出，區(qū)塊鏈的插入或查看時間遠遠小于本文方案的簽密總耗時。因此，對簽密算法的時間開銷影響甚微。

5 結(jié)束語

本文利用區(qū)塊鏈技術(shù)提出了一種基于離散對數(shù)的無證書簽密方案。方案利用區(qū)塊鏈的不可篡改性和可追溯性實現(xiàn)了簽密的不可否認性，并基于離散對數(shù)難題確保了方案的安全性。同時，本文通過標準模型證明了方案具有機密性。性能分析表明本方案性能更優(yōu)。仿真實驗結(jié)果顯示本方案執(zhí)行效率較高，且數(shù)據(jù)上鏈耗時對簽密過程的總耗時影響較小可忽略不計。