無雙線性映射的無證書簽密方案

高改梅， 彭新光， 秦澤峰

(1. 太原理工大學 信息與計算機學院， 山西 太原 030024；2. 太原科技大學 計算機科學與技術學院， 山西 太原 030024；3. 山西青年職業(yè)學院 計算機系， 山西 太原 030032)

0 引 言

無證書公鑰密碼體制[1](CL-PKC, Certificateless Public Key Cryptography)解決了傳統(tǒng)公鑰密碼體制[2]的復雜證書管理問題和基于身份密碼體制[3]的密鑰托管問題， 提高了密碼系統(tǒng)的運行效率. CL-PKC中用戶的私鑰由自己和密鑰生成中心(KGC， Key Generation Center)共同生成. 因此， 用戶私鑰不由KGC完全掌控， 減少了對第三方KGC的依賴.

簽密[4](SC， Signcryption)在一個邏輯步驟內同時對信息進行簽名和加密， 與傳統(tǒng)的“簽名”+“加密”方式相比， SC降低了計算量和通信開銷. 文獻[5-6]把簽密引入身份認證和數(shù)據(jù)訪問控制中， 以提高信息安全運行機制的效率. 2008 年， Barbos等人[7]首次將簽密機制引入CL-PKC中， 提出基于雙線性映射理論的無證書簽密機制(CLSC, Certificateless Signcryption)， 但未進行安全性證明. 由于雙線性對運算的計算成本是點乘運算計算成本的20倍[8]， 所以基于雙線性對的CLSC計算開銷較高. Liu等人[9]提出了無雙線性對運算的CLSC(LX-CLSC)， 并在隨機預言模型中， 基于計算Diffie-Hellman假設和離散對數(shù)困難問題證明了該方案的機密性和認證性， 同時進行了效率分析. 2013年， Zhou等人[10]發(fā)現(xiàn)LX-CLSC方案不滿足機密性和不可偽造性， 安全證明中也存在缺陷， 提出改進的無雙線性對運算的CLSC(ZW-CLSC). 同時證明了所提方案的安全性， 并進行了效率分析. 2014年， Shi等人[11]又提出一種改進的無雙線性對運算的CLSC(SKGZ-CLSC)， 并對其進行了密碼學分析， 證明該機制是可證安全的. 2016年， Zhou等人[12]提出一種安全高效的CLSC(ZYZ-CLSC)， 并證明了方案的安全性， 通過性能分析指出其方案計算效率更優(yōu).

本文首先對ZW-CLSC方案進行正確性分析， 指出ZW-CLSC方案在解簽密階段根據(jù)已知信息無法恢復出明文消息. 同時構造具體的攻擊實例， 驗證ZW-CLSC方案無法抵抗其所聲稱的對類敵手的不可偽造性攻擊. 另外， 分析發(fā)現(xiàn)SKGZ-CLSC方案和ZYZ-CLSC方案的計算開銷較高. 因此， 本文設計了改進的無雙線性映射的無證書簽密方案GPQ-CLSC. 首先對ZW-CLSC方案進行安全性分析， 然后詳細闡述GPQ-CLSC方案， 并進行正確性分析， 接著在隨機預言模型中證明GPQ-CLSC方案的機密性和不可偽造性， 最后是效率分析.

1 基礎知識

1.1 相關困難性問題

定義1 計算Diffie-Hellman(CDH， Compute Diffie-Hellman)

定義2 離散對數(shù)(DL, Discrete Logarithm)

設G是橢圓曲線上階為q的循環(huán)群，P是G的生成元. 給定二元組(P,uP)， DL問題的目的是計算u.

1.2 CLSC安全模型

CLSC方案的攻擊敵手分為A1和A2兩類[13]：

A1類敵手是惡意用戶， 此類敵手不能掌控系統(tǒng)主密鑰， 但可隨意替換用戶公鑰.

A2類敵手是惡意KGC， 此類敵手可掌控系統(tǒng)主密鑰， 但不能隨意替換用戶公鑰.

安全的CLSC方案至少滿足IND-CLSC-CCA2攻擊(indistinguishability certificateless signcryption adaptive chosen ciphertext attacks)下的機密性和EUF-CLSC-CMA攻擊(existential unforgeability certificateless signcryption chosen message attack)下的不可偽造性， 詳細的安全模型和游戲定義見文獻[13].

2 ZW-CLSC方案的安全性分析

本節(jié)對ZW-CLSC方案進行分析， 指出其不滿足正確性. 并構造具體的攻擊實例， 證明ZW-CLSC方案無法滿足其所聲稱的不可偽造性.

2.1 不滿足正確性

在解簽密階段， 用m‖s=H3(VB)⊕C恢復出m‖s， 無法從m‖s推斷出m的值， 因為m和s的長度不是固定值. 例如， 計算出H3(VB)并且得到m‖s=101001010010011011010001， 但是由于不知道m(xù)和s的消息空間大小， 無法確定m的值為m=101還是m=101001.

2.2 不可偽造性攻擊

設Alice和Bob分別是ZW-CLSC方案的發(fā)送方和接收方， Alice的公私鑰分別是PKA=(RA,XA)和SKA=(DA,xA). Bob的公私鑰分別是PKB=(RB,XB)和SKB=(DB,xB).

A1類敵手Eva掌握了Alice的公鑰PKA， Eva代替Alice與Bob進行消息交互， 過程如下：

1) 敵手Eva偽造公鑰

2) 敵手Eva偽造Alice的簽密文

② 計算VA=a(RB+XB+h1y)和U=H4(VA)P.

④ Eva發(fā)送簽密文δ*=(T,C*,U)給Bob.

3) Bob驗證簽密的合法性

Bob收到簽密文后， 根據(jù)解簽密算法驗證簽密的合法性. 若驗證成功， 則Eva成功偽造了Alice的合法簽密； 否則， Eva偽造失敗. 具體驗證過程如下：

① 計算VB=(xB+DB)T.

② 恢復消息m‖s*=H3(VB)⊕C*.

由此可知， Eva成功偽造Alice的簽密， 并通過了接收者Bob的驗證， 所以類敵手Eva具有偽造Alice合法簽密的能力.

3 本文GPQ-CLSC方案

3.1 方案描述

GPQ-CLSC方案包括五個算法， 詳細描述如下：

1) 系統(tǒng)建立(Setup)

KGC執(zhí)行如下操作完成系統(tǒng)建立， 并輸出系統(tǒng)參數(shù).

① 輸入安全參數(shù)k.

② 選擇階為大素數(shù)q的橢圓曲線循環(huán)群G，P是G的一個生成元.

⑤ 保密主密鑰z， 公開系統(tǒng)參數(shù)params=(G,q,P,y,H1,H2,H3).

2) 部分密鑰生成(PartialKeyGen)

用戶IDi和KGC交互完成部分密鑰生成， 描述如下：

①IDi發(fā)送身份標識給KGC.

③ KGC通過安全渠道將(di,Ri)發(fā)送給IDi. 其中di是用戶的部分私鑰，Ri是用戶的部分公鑰.

3) 用戶密鑰生成(KeyGen)

用戶IDi收到KGC發(fā)送的部分密鑰(di,Ri)后， 執(zhí)行如下操作， 完成密鑰的生成.

② 設置PKi=(Ri,Xi)為用戶公鑰， 設置SKi(di,xi)為用戶私鑰.

設本文的簽密發(fā)送者為Alice， 其身份標識是IDA， 那么她的公鑰為PKA(RA,XA)， 私鑰為SKA=(dA,xA). 簽密接收者為Bob， 其身份標識是IDB， 他的公鑰為PKB=(RB,XB)， 私鑰為SKB=(dB,xB).

4) 簽密(Sign)

當Alice要發(fā)送消息m給Bob時， Alice根據(jù)Bob的身份標識IDB和公鑰PKB， 并結合自己的私鑰SKA進行如下操作：

② 計算VA=β(XB+RB+h1y)和h1=H1(IDB,RB).

③ 計算

h=H2(m‖T‖IDA‖IDB‖XA‖XB).

④ 計算s=(xA+β)/(h+dA+xA).

⑤ 計算C=H3(VA)⊕(m‖s).

Alice將簽密文δ=(s,C,T)發(fā)送給Bob.

5) 解簽密(UnSign)

當Bob 收到Alice發(fā)送的簽密文后， 利用Alice 的身份標識IDA和公鑰PKA， 并結合自己的私鑰SKB執(zhí)行如下操作進行驗證.

① 計算VB=(xB+dB)T.

② 恢復消息m‖s=H3(VB)⊕C.

3.2 正確性分析

1) 部分密鑰的正確性

Alice和Bob可通過式(1)來驗證KGC為其生成的部分密鑰的正確性.

Ri+H1(IDi,Ri)y=riP+zPH1(IDi,Ri)=

(ri+zH1(IDi,Ri))P=diP.

(1)

2) 密文的正確性

在UnSign算法中， 密文的驗證可以通過式(2)和式(3)完成. 首先計算VB，

VB=(xB+dB)T=

(xB+rB+zH1(IDB,RB))βP=

β(XB+RB+yH1(IDB,RB))=VA.

(2)

根據(jù)VB和Alice發(fā)送的密文， Bob通過式(3)驗證密文的正確性.

m‖s=H3(VB)⊕C=

H3(VB)⊕H3(VA)⊕(m‖s)=

H3(VA)⊕H3(VA)⊕(m‖s)=m‖s.

(3)

3) 簽密的正確性

在UnSign解簽密算法中， 簽密的正確性可通過式(4)來驗證.

xAP+βP=XA+T.

(4)

4 安全性分析與比較

4.1 機密性分析

定理1A1類敵手的機密性.

證明假設算法F以三元組(P,aP,bP)為CDH問題的挑戰(zhàn)實例， 以Type-I敵手A1為挑戰(zhàn)者， F的目標是計算abP. 游戲開始后， F維護列表L1,L2,L3,LD,LSK,LPK,LS,LU分別跟蹤A1對預言機H1,H2,H3， 部分密鑰生成， 私鑰生成， 公鑰生成， 簽密和解簽密的詢問. 此外， F維護列表Lrec來記錄挑戰(zhàn)者身份信息. 各列表初始均為空.

1) 系統(tǒng)建立

F運行Setup算法， 并發(fā)送系統(tǒng)參數(shù)params給A1. F也可運行部分密鑰生成、 密鑰生成、 公鑰查詢、 公鑰替換、 簽密和解簽密等操作.

2) 詢問階段

A1可執(zhí)行多項式有界次的下列詢問.

公鑰生成詢問： 當收到A1的請求(ID,R.X)時， F進行下述操作：

如果(ID,R,X)在LPK中已經存在， 則F將(R,X)返回給A1.

公鑰替換詢問： 當收到A1的替換請求(ID,R′,X′)時， F將(R′,X′)替換現(xiàn)存的公鑰(R,X).

簽密詢問： 當收到A1提供的(IDA,IDB)和明文消息m時， F在列表L1中查詢(IDA,RA)， 并執(zhí)行下列操作：

如果c=0， F根據(jù)IDA和IDB從列表LSK和列表LPK中分別獲得(IDA,dA,xA)和(IDB,RB,XB)， 然后執(zhí)行Sign算法完成對明文消息m的簽密， 并將簽密文δ=(s,C,T)發(fā)送給A1.

如果c=1， F失敗并退出.

解簽密詢問： 當收到A1提供的(IDA,IDB)和密文δ=(s,C,T)時， F在列表L1中查詢(IDB,RB)， 并執(zhí)行下列操作：

如果c=0， F根據(jù)IDA和IDB從列表LPK和列表LSK中分別獲得(IDA,RA,XA)和(IDB,dB,xB)， 然后執(zhí)行UnSign算法完成解簽密驗證， 并將解簽密得到的消息m發(fā)送給A1.

3) 挑戰(zhàn)階段

4) 猜測階段

A1執(zhí)行多項式有界次詢問后輸出其猜測值c′∈{0,1}. 如果c′=c，A1使用V′=β(XB+RB+hy)進行H3詢問. 此時， CDH問題的備選答案已經存儲在列表L3中. F忽略A1的猜測值， 從列表L3中隨機選擇V′， 輸出(V′=(xB+rB)T*)/k=zβP作為CDH問題的解， 其中xB,rB,T*,V′都是未知量. 否則， F沒有解決CDH問題.

定理2 A2類敵手的機密性.

證明該定理的證明思路和方法與定理1類似， 重復部分不再贅述， 主要不同如下：

1) 敵手A2可以替換系統(tǒng)主秘鑰z.

2) 在公鑰生成詢問中， 設置R=zP而不是定理1中的R=rP， 將(ID,-,x,c)插入列表Lrec而不是(ID,r,x,c).

3) 在猜測階段， F輸出V′-(xB+kz)T*=zβP作為CDH問題的回答.

4.2 不可偽造性分析

定理3A1類敵手的不可偽造性.

證明假設算法F以二元組(P,uP)為DL問題的挑戰(zhàn)實例， 以Type-I敵手A1為挑戰(zhàn)者， F的目標是計算u. 游戲開始后， F維護列表L1,L2,L3,LD,LSK,LPK,LS,LU分別跟蹤A1對預言機H1,H2,H3， 部分密鑰生成， 私鑰生成， 公鑰生成， 簽密和解簽密的詢問. 此外， F維護列表Lrec來記錄挑戰(zhàn)者身份信息. 各列表初始均為空.

1) 系統(tǒng)建立

F運行Setup算法， 并發(fā)送系統(tǒng)參數(shù)params=(G,q,P,y,H1,H2,H3)給敵手A1. F設定y=up， 其他設置與定理1對A1的設置相同.

2) 查詢階段

與定理1相同， 敵手A1可執(zhí)行多項式有界次的詢問.

3) 偽造階段

A1以IDA為發(fā)送者，IDB為接收者， 經過多項式有界次詢問后， 輸出消息m的一個偽造密文δ*=(s*,c*,T*).

T*=βP=(s1(h+dA+xA)-xA)P=

(s2(h′+dA+xA)-xA)P.

所以有

s1(h+dA+xA)=s2(h′+dA+xA).

對A1敵手來說， 下面等式成立

s1(h+rA+uk+xA)=s2(h′+rA+uk+xA),

其中，k=h1=H1(IDA,RA)， 在此等式中只有u是未知變量， 所以u可以被計算出.

定理4A2類敵手的不可偽造性.

證明該定理的證明思路和方法與定理3類似， 重復部分不再贅述， 主要不同如下：

1) 在系統(tǒng)建立階段， F為敵手A2設置y=zp， 其他設置與定理2對A2的設置相同. 敵手A2可以任意替換用戶公鑰.

2) 在偽造階段， F根據(jù)分裂引理生成兩個合法簽名信息后， 敵手A2驗證等式s1(h+rA+zk+xA)=s2(h′+rA+zk+xA)， 其中，k=h1=H1(IDA,RA). 在此等式中只有rA是未知量， 所以rA可以被計算出. 而在公鑰生成詢問中， F設置了R=rAP=uP， 所以u也可以被計算出.

4.3 性能分析

表 1 CLSC同類方案效率對比Tab.1 CLSC similar scheme efficiency comparison

方案的安全屬性主要關注機密性和不可偽造性. 表 2 是GPQ-CLSC方案與其他幾個同類方案的安全屬性對比， 其中“√”表示具有該安全屬性， “×”表示不具有該安全屬性.

表 2 CLSC同類方案安全屬性對比Tab.2 CLSC similar scheme security attribute comparison

5 結 論

簽密作為數(shù)據(jù)信息安全保護的方法， 消息的保密性由加密來完成， 認證性由簽名來實現(xiàn)， 在一個邏輯步驟內同時完成簽名和加密， 具有較低的計算開銷和通信開銷. 本文對ZW-CLSC方案進行分析， 發(fā)現(xiàn)ZW-CLSC方案不滿足正確性. 同時， 構造具體的攻擊實例證明ZW-CLSC方案對A1類敵手不滿足不可偽造性. 在借鑒ZW-CLSC優(yōu)點的基礎上， 提出GPQ-CLSC方案. 在隨機預言模型中基于CDH假設和DL假設證明了GPQ-CLSC方案滿足機密性和不可偽造性. 性能分析表明， GPQ-CLSC在保證安全性的前提下， 計算開銷有所降低. 無雙線性對運算的CLSC方案， 減少了橢圓曲線對運算的開銷， 將更適用于無線傳感器網絡、 移動醫(yī)療數(shù)字網絡、 無線體域網等終端資源有限的應用場景中.