基于陷門哈希函數(shù)的無證書簽密方案

束 紅

（1.銅陵學(xué)院 數(shù)學(xué)與計算機學(xué)院，安徽 銅陵 244061；2.網(wǎng)絡(luò)與信息安全安徽省重點實驗室，安徽 蕪湖 241002）

數(shù)字簽密技術(shù)通過邏輯單操作完成對消息的加密和數(shù)字簽名，而其計算和通信成本比加密和簽名的疊加成本更有效，同時提供機密性、完整性、認證性和不可否認性［1］，在網(wǎng)絡(luò)安全傳輸和通信中起到重要的作用。

1 相關(guān)研究

1997 年，Zheng［2］（P17-21）首次提出了數(shù)字簽密的概念，有效改善了傳統(tǒng)的“先加密后簽名”算法計算效率低的不足［3］。 文獻［1］將數(shù)字簽密分為基于PKI 的簽密［2］（P17-21）、基于身份的簽密［4］及無證書簽密［3，5-8］三類。 其中，PKI 密碼體制具有證書的分發(fā)、存儲等管理問題， 基于身份的密碼體制存在密鑰托管的缺陷，因此，無證書密碼體制因其既無證書管理問題又無密鑰托管問題， 且計算效率高于傳統(tǒng)的公鑰密碼體制， 引起了廣大研究者的興趣。2008 年，Barbosa 等人［9］(P369-372)首次提出無證書簽密概念。 自此，學(xué)者們圍繞無證書簽密的研究逐漸深入，無證書簽密體制成為當(dāng)前密碼研究領(lǐng)域的熱點之一。無證書簽密方案根據(jù)其計算基礎(chǔ)的不同，可以分為基于雙線性對的無證書簽密方案［5，8］、基于指數(shù)運算的無證書簽密方案［3，7］和基于橢圓曲線密碼體制（ECC）的無證書簽密方案［6］。 由于雙線性對的運算時間大于乘法群上的指數(shù)的運算時間， 而指數(shù)的運算時間又大于ECC 群上的標量乘法運算時間［8］，因此，基于ECC 的簽密方案具有較高的計算效率。 陷門哈希函數(shù)的概念最早由Krawczyk 和Rabin 提出，用于構(gòu)造變色龍簽名［10］(P143-154)。 很多數(shù)字簽名方案都基于變色龍簽名思想［11］(P355-367)［12，13］。Chandrasekhar 等［14］(P610-618)基于陷門哈希函數(shù)提出聚合簽密方案，將多陷門哈希函數(shù)與可分解的乘法同態(tài)ElGamal 加密相結(jié)合，提出一種新的有效的聚合簽密方案，可以生成常量級的聚合簽密文本，從而為多對一的通信場景提供機密性和完整性及身份認證功能。本文基于ECC 及陷門哈希函數(shù)，提出一種無證書簽密方案。

2 預(yù)備知識

2.1 橢圓曲線離散對數(shù)問題

定義1 橢圓曲線離散對數(shù)問題ECDLP［15］假設(shè)E（Fl）是有限域Fl上的橢圓曲線，已知P 是E（Fl）的一個q 階生成元，當(dāng)Q∈E(Fl)且Q=aP，求整數(shù)a（0≤a≤q-1）。

2.2 CDH 問題

定義2 CDH 問題［16］令q 是群G 的 階，P 是G的生成元， 給定P，aP，bP∈G， 其中a，b∈Z*q且未知，計算abP∈G。

2.3 陷門哈希函數(shù)

陷 門哈希 函 數(shù)［10］（P143-154）擁有 哈 希/陷 門 密 鑰（HK，TK），其中，哈希密鑰HK 是公開的，陷門密鑰TK 是私有的。 陷門哈希函數(shù)使用一些特殊信息產(chǎn)生固定的哈希值，其抗碰撞性取決于用戶對陷門信息（TK）的了解狀態(tài)［11］（P355-367）。也就是說，僅知道HK時， 很難在消息空間找到兩個不同的消息s′和s，以及兩個不同的輔助參數(shù)u′和u［12］，使得THHK（s，u）=THHK（s′，u′）。 但是，當(dāng)TK 和HK 都已知時，根據(jù)s、s′和u， 很容易計算出u′， 滿足THHK（s，u）=THHK（s′，u′）。陷門哈希函數(shù)的這一性質(zhì)可用于構(gòu)造各種數(shù)字簽名方案［11］（P355-367）［12，13］。

定義3 陷門哈希函數(shù)由四個概率多項式時間(PPT)算法組成［13］：

ParGen: 輸入安全參數(shù)k， 輸出系統(tǒng)公共參數(shù)param；

KeyGen: 輸入param， 輸出陷門/哈希密鑰對；

HashGen:輸入param，HK，消息s 以及輔助參數(shù)u，輸出哈希值THHK（s，u）；

TrapColGen:輸入param，，s，u 以及新消 息s′≠(s)，輸 出u′，使 得THHK（s，u）=THHK（s′，u′）。

3 基于陷門哈希函數(shù)的無證書簽密方案

3.1 方案構(gòu)造

3.1.1 初始化

密鑰生成中心(KGC)選擇兩個大素數(shù)p 和q，設(shè)E(Fp)是有限域Fp上的橢圓曲線y2=x3+ax+b mod p，其中，a，b∈Fp且4a3+27b2≠0。 G 是E(Fp)的一個循環(huán)子群，P 是G 的一個q 階生成元，W1：{0，1}*×G×G →，W2：{0，1}*×G →Z*q，W3：{0，1}*×G →，W4：{0，1}*×G→為安全無碰撞散列函數(shù)。

3.1.2 用戶密鑰生成

用戶IDi隨機選擇秘密值yi， 計算公開參數(shù)Yi=yiP，并將秘密值-公開參數(shù)對（yi，Yi）通過安全通道發(fā)送給KGC。

輸入用戶標識IDi和公開參數(shù)Yi，KGC 隨機選擇秘密值si， 計算Vi=siP 和βi=si+αW1（IDi，Yi，Vi），并將Vi和βi通過安全通道發(fā)送給用戶IDi。其中，βi為用戶IDi的部分私鑰。 用戶IDi通過驗證βp=Vi+KpW1（IDi，Yi，Vi）等式是否成立，驗證部分私鑰βi的正確性。

用戶IDi的公鑰和私鑰分 別 為：PKi=（Yi，Vi），SKi=（yi，βi）。

3.1.3 陷門哈希生成

這一部分由用戶IDi生成各自的陷門哈希值。輸入系統(tǒng)參數(shù)param， 用戶標識IDi和其哈希密鑰（公開密鑰）Yi，隨機選擇輔助參數(shù)r∈Z*q，計算陷門哈希值Ti=THYi（IDi，r）=W2（IDi，Yi）Yi-rP，將陷門哈希值Ti公開。

3.1.4 簽密

假設(shè)消息m 由發(fā)送者A 傳遞給接收者B，則簽密過程操作如下：

根據(jù)陷門碰撞（即THYA（IDA，r）=THR（C，r′）），計算新輔助參數(shù)r′=uW2（C，R）-yAW2（IDA，YA），令H=W4（IDA，TA，r′），計算K=u-（yA+βA）H mod q，則A簽密密文為σ=（R，K，C），將（σ，r′）發(fā)送給接收者B。

3.1.5 解簽密

接收者B 收到發(fā)送者A 傳遞的簽密文σ=（R，K，C），進行如下解簽密操作:

簽名驗證:計算hA=W1（IDA，YA，VA），H=W4（IDA，TA，r′））。 如果等式KP+（YA+VA+KphA）H=R 成立，則接受該簽名并輸出1，否則拒絕該簽名并輸出0。

解密密文:計算Q′=（yB+βB）R，解密明文m=C⊕W3（IDB，Q′）。

3.2 正確性

上文所提的簽密方案的正確性證明過程如下：

3.2.1 陷門哈希碰撞正確性

3.2.2 部分私鑰驗證正確性

3.2.3 簽名驗證正確性

3.2.4 密文加解密正確性

4 安全性分析

4.1 機密性

定理1 在隨機預(yù)言機模型中， 本文方案在適應(yīng)性選擇消息攻擊下具有機密性。

證明: 假設(shè)算法Z 是CDH 困難問題的解決方案，給定實例(P，aP，bP)，求解目標為abP。建立敵手C 和挑戰(zhàn)者Z 之間的游戲，令KP=aP，運行初始化算法，敵手C 進行如下詢問:

W1詢 問：當(dāng)C 以（IDi，Yi，Vi）詢 問 時，若 存 在（IDi，Yi，Vi，w1）∈Lw1，則Z 返回w1給C；否則，Z 選擇w1∈，且（*，*，*，w1）未出現(xiàn)在Lw1中，將（IDi，Yi，Vi，w1）保存在中Lw1， 并返回w1給C。

W2詢問：當(dāng)C 以（IDi，Yi）詢問時，若存在（IDi，Yi，w2）∈Lw2，則Z 返回w2給C；否則，Z 選擇w2∈，且（*，*，w2）未出現(xiàn)在Lw2中，將（IDi，Yi，w2）保存在Lw2中， 并返回w2給C。

W3詢問：當(dāng)C 以（IDi，Q）詢問時，若存在（IDi，Q，w3）∈Lw3， 則Z 返回w3給C； 否則，Z 選擇w3∈，且（*，*，w3）未出現(xiàn)在Lw3中，將（IDi，Q，w3）保存在中Lw3， 并返回w3給C。

W4詢問：當(dāng)C 以（IDi，Ti）詢問時，若存在（IDi，Ti，w4）∈Lw4， 則Z 返回w4給C； 否則，Z 選擇w4∈，且（*，*，w4）未出現(xiàn)在Lw4中，將（IDi，Ti，w4）保存在中Lw4， 并返回w4給C。

公鑰生成詢問:當(dāng)Z 接收到C 關(guān)于IDi的公鑰生成詢問時，執(zhí)行如下操作:若（IDi，Yi，Vi，di）∈LPK，則返回（Yi，Vi）給C。 否則，Z 選取隨機數(shù)di∈{0,1}，若di=0，則隨機選取yi，βi，w1∈Z*q，計算Yi=yiP，Vi=βiP-KPw1，且 滿 足（*，Yi，Vi，*）∈/ LPK，將（IDi，Yi，Vi，di）保存到LPK，并返回給C，同時將（IDi，yi，βi）保存到LSK。 若di=1，令Yi=y*P，Vi=v*P，且y*,v*∈，（*，Yi，Vi，*）∈/ LPK， 將（IDi，Yi，Vi，di）保存到LPK，并返回給C。

私鑰生成詢問: 當(dāng)Z 接收到C 關(guān)于IDi的私鑰生成詢問時，執(zhí)行如下操作：若（IDi，yi，βi）∈LSK，則返回（yi，βi）給C。 否則，Z 在LPK中查詢相應(yīng)的（IDi，Yi，Vi，di），若di=0，公鑰生成詢問中已將（IDi，yi，βi）保存到了LSK， 因此，Z 可直接將LSK中相應(yīng)的元組（yi，βi）傳給C。 若di=1， Z 終止模擬。

公鑰替換詢問:C選擇一個新的公鑰（IDi，，，di）替換原始公鑰（IDi，Yi，Vi，di）。

陷門哈希生成詢問:當(dāng)C 以（IDi，Yi）詢問時，若存在（IDi，Yi，ti）∈LT，則Z 返回ti給C;否則，Z 選擇r∈，計 算ti=W2（IDi，Yi）Yi-rP，將（IDi，Yi，ti）保 存在LT中， 并返回ti給C。

簽密詢問: 當(dāng)Z 接收到C 關(guān)于 （IDI，IDJ，m）的簽密詢問時，則Z 在LPK中查詢IDJ相應(yīng)的（IDI，YJ，VJ，dJ）執(zhí)行如下操作：若dJ=1，則Z 終止模擬。 否則，Z 分別對IDI，IDJ進行公、私鑰生成詢問，獲得相 應(yīng)元組（IDI，yI，βI）和（IDJ，YJ，VJ），生 成 密 文σ=（R，K，C）并返回給C。

解簽密詢問: 當(dāng)Z 接收到C 關(guān)于（IDI，IDJ，R，K，C）的解簽密詢問時， 若LPK中存在元組（IDJ，YJ，VJ，dJ），且dJ=0，則Z 分別對IDI，IDJ進行公、私鑰生成詢問，獲得相應(yīng)元組（IDJ，yJ，βJ）和（IDI，YI，VI），運行解簽密算法得到m 返回給C。 若LPK中存在元組（IDJ，YJ，VJ，dJ），且dJ=1，則Z 終止模擬。 若LPK中不存在元組（IDI，YI，VI），則Z 查詢（IDI，，，）∈Lw1， （IDI，，）∈Lw2， （IDI，QI，w3） ∈Lw3，（IDI，TI，w4）∈Lw4，計算m=C⊕w3，若等式KP+成立，則返回m 給C。 否則，輸出。

挑戰(zhàn):C 輸出IDI和IDJ以及兩個等長消息m0，m1， Z 查詢LPK獲得（IDJ，YJ，VJ，dJ），若dJ=0，則終止模擬。否則，令R=bP，隨機選擇Q∈G，計算C=ms⊕W3（IDB，Q），s∈{0,1}， 隨機選擇K∈使之滿足KP+（YI+VI+KPhI）H=R， 將挑戰(zhàn)密文σ=（R，K，C）返回給C。

C 經(jīng)過詢問，輸出s′作為s 的猜測，當(dāng)s′=s 時，Z 輸出作為CDH 困難問題的解。

綜上， 該方案在自適應(yīng)消息攻擊下具有機密性。

證畢。

4.2 消息驗證性

由于在假設(shè)CDH 問題是困難的情況下， 沒有多項式對手能夠偽造有效的消息。 因此，接收者B想要檢測消息（IDi，m，Yi，Vi）的有效性和完整性，可以通過檢測等式KP+（Yi+Vi+KPhB）H=R 是否成立來判斷。 其中，hB=W1（IDB，YB，VB），H=W4（IDA，TA）。故本方案提供身份驗證功能。

4.3 密鑰托管

本方案的部分私鑰βi和部分公鑰Vi是由KGC 根據(jù)用戶標識IDi和公開參數(shù)Yi生成的，由于Yi= yiP，KGC 若想從已知的公開參數(shù)Yi計算出秘密值yi，需破解ECDLP 問題，故本方案可以有效避免密鑰托管問題。

4.4 前/后向安全性

在本方案中，公開參數(shù)、部分公鑰及加密參數(shù)的產(chǎn)生來源于隨機產(chǎn)生的參數(shù)，即使敵手獲得了密文傳輸過程中的相關(guān)參數(shù)，但由于隨機數(shù)具有一定的時間效力，敵手無法根據(jù)此次獲得的參數(shù)分析出以前的密文和相關(guān)參數(shù)，也無法分析出未來的密文和相關(guān)參數(shù)，因此，該方案具有前/后向安全性。

4.5 不可否認性

若消息發(fā)送者A 對自己簽密的消息試圖抵賴時，需要公開驗證其身份。 由于等式KP+（YA+VA+KPhA）H=R 中包含發(fā)送者A 的公鑰，消息發(fā)送者的身份可以通過任何第三方機構(gòu)驗證，因此，當(dāng)消息發(fā)送者確實簽密了某消息，其行為不可否認。

5 性能分析

性能分析分別從通信和計算代價兩方面考慮，其中通信效率以密文長度來衡量，計算效率以簽名階段和解簽密階段驗證算法的計算量來衡量。 令TSM為橢圓曲線中的標量乘法的時間開銷，TE為群上的指數(shù)運算的時間開銷，TBP為雙線性映射運算的時間開銷， 其中，1 次乘法群上的指數(shù)運算的時間TE大約相當(dāng)于10 次橢圓曲線點乘運算TSM，1 次512 位的雙線性對運算的時間大約相當(dāng)于10 倍的1 024 位指數(shù)運算［8］。 由于群上的加法運算和哈希運算的時間遠小于上述運算，所以不考慮這些運算的操作時間。 定義Lm為消息長度，LG為群G 中元素的長度，Lq為中元素的長度。

如表1 所示， 由于雙線性映射的時間開銷遠大于標量乘法和指數(shù)運算， 故采用雙線性映射的算法［5，8］計算開銷較大，計算效率較低。 本文所提出的方案在簽密階段和解簽密階段分別只使用了3次和4 次橢圓曲線上的標量乘法，故具有較高的計算效率。 在通信效率方面，本文所提出的方案基本接近文獻［3］但高于其他算法［5-8］，適用于網(wǎng)絡(luò)帶寬資源有限的網(wǎng)絡(luò)環(huán)境。

表1 相關(guān)方案性能比較

6 總結(jié)

本文利用ECC 和陷門哈希函數(shù)構(gòu)造了一種新的無雙線性對的無證書簽密方案。該方案提供具有無需密鑰托管、可認證性、前/后向安全、不可否認性等安全特性，相較于同類型無證書簽密方案，本方案具有較高的計算效率和存儲效率， 適合網(wǎng)絡(luò)通信環(huán)境中計算速度、 存儲容量及帶寬受限的安全應(yīng)用。