適于ad hoc網絡安全通信的新簽密算法

張串絨，張玉清，李發根，肖鴻

（1. 中國科學院 研究生院，北京100049；2. 空軍工程大學 電訊工程學院，陜西 西安 710077；3. 電子科技大學 計算機科學與工程學院，四川 成都 611731）

1 引言

Ad hoc 網絡作為一種新型無線網絡，能夠在沒有事先建立基礎設施的環境下，由一組帶有無線通信裝置的移動節點組成多跳步、臨時性的自治通信系統。它以其組網迅速、適應性強、成本低廉等優點，可廣泛應用于工商、醫療、家庭、辦公環境和軍事等各個領域，具有廣闊的應用前景。但ad hoc網絡無中心、分布式管理、資源受限等特點，使其在信息的認證性、機密性、完整性、抗抵賴等安全性及其實現方面產生嚴重障礙。同時傳統網絡基于較充足網絡資源、固定連接、穩定拓撲、專門路由、命名和目錄等多種服務基礎上的相關安全措施，不再適于ad hoc 網絡，這就要求為ad hoc 網絡通信設計專門的安全技術和算法。

在ad hoc 網絡的安全通信中，大量信息的存儲和傳輸是同時需要機密性和可認證性保護的。密碼學傳統上是以“先簽名再加密”的方法來同時實現機密性和認證性這2種安全服務的，但這種簡單組合的方法，其計算和通信代價是加密和簽名的總和，效率較低，不適合ad hoc 網絡受限的環境。1997年，文獻[1]提出了一種新的密碼技術——簽密，它能在一個邏輯步內同時實現機密性和可認證性2項安全需求，效率遠遠高于“先簽名再加密”方法，已被公認為是同時實現機密性和可認證性的理想方法。目前，已有許多文獻研究將簽密技術用于ad hoc 網絡的密鑰管理、安全路由等安全協議的設計，其中文獻[2～6]研究了基于身份的簽密算法在ad hoc網絡安全協議中的應用。已有研究成果表明，基于身份簽密技術對提高 ad hoc 網絡通信的安全性及其實現效率具有重要作用。為了進一步提高ad hoc網絡通信的安全性和效率，本文研究新的基于身份的簽密算法，給出了一個可證明安全的短的基于身份的簽密算法，簡稱S-IDSC，與已有簽密算法相比，其計算和傳輸代價小，能更好地滿足ad hoc網絡無線通信帶寬受限、電池供電、收發設備內存小的特殊環境，高效實現 ad hoc 網絡密鑰管理、安全路由等通信過程中的安全需求。

2 相關基礎

2.1 基于身份簽密算法的組成

Malone-Lee在文獻[7]中首次提出了基于身份簽密思想，給出如下算法結構。

1) 系統建立(setup)：給定系統安全參數k，由密鑰生成中心PKG生成系統參數；

2) 密鑰提取(extract)：對消息發送者和接收者給出的身份信息 I DA和 I DB，由PKG生成與之相應的公私鑰對(dA,QA)和(dB, QB)，并通過秘密信道傳給相應用戶；

3) 簽密(signcrypt)：輸入 dA、 I DB和消息m，生成密文σ；

4) 解簽密(unsignc)：輸入 dB、 IDA和σ，輸出m或⊥，輸出⊥表明σ為無效簽密密文。

目前提出的基于身份簽密算法的還有文獻[8～11]等。這些基于身份簽密算法多是利用橢圓曲線上雙線性對來實現的，如 Weil對或改進的 Tate對。所謂雙線性對是一種變換，定義如下。

設 G1和 G2是2個q階的循環群，如果變換e滿足如下。

基于橢圓曲線上雙線性對的簽密算法，具有短的密鑰長度和低的通信帶寬要求。

2.2 基于身份簽密算法的安全性定義

文獻[8]定義了一種基于身份簽密算法的安全概念，具體如下。

定義 1 保密性：如果沒有任何多項式有界的敵手以一個不可忽略的優勢贏得以下游戲，則稱一個基于身份的簽密算法在適應性選擇密文攻擊下是不可區分的（IND-IBSC-CCA2）。

1) 初始化階段，挑戰者Γ輸入安全參數k，運行系統建立算法，并將系統參數 params發送給敵手Ω，保密系統私鑰s。

2) 詢問階段（第一階段詢問），執行以下多項式有界次適應性詢問。

密鑰提取詢問：敵手Ω選擇一個身份 I DU，挑戰者Γ計算 dU=Extract(I DU)并將結果發給Ω。

簽密詢問：Ω選擇2個身份 I Di和 I Dj、一個明文m。Γ計算并將結果σ發送給Ω。

解簽密詢問：Ω選擇 2個身份 I Di和 I Dj、一個密文σ。Γ首先計算私鑰然后計算 U nsignc(σ,dj,I Di)，最后發送結果明文m或符號⊥給敵手Ω。

Ω能根據Γ對他簽密提交詢問的回答，調整他的詢問。

3) Ω輸出2個相同長度的明文 m0、m1和他希望挑戰的2個身份 I DA和 I DB。I DA和 I DB不能是在2) 中已經執行過密鑰提取詢問的身份。

5) 第二階段詢問：像 2)中那樣，Ω再次執行多項式有界次詢問。但是他不能對 I DA和 I DB執行私鑰提取詢問，也不能對密文σ執行解簽密詢問。

最后，Ω輸出一個值v′作為對v的猜測。如果v′=v，Ω贏得游戲。

定義 2 不可偽造性：如果不存在任何多項式有界的敵手以一個不可忽略的優勢贏得以下游戲，則稱一個基于身份的簽密方案在適應性選擇消息攻擊下是存在性不可偽造的(EUF-IBSC-CMA)。

1) 初始化階段：挑戰者Γ輸入安全參數k，運行系統建立算法，并將系統參數params發送給敵手Ω，并保密系統私鑰s。

2) 詢問階段：Ω類似保密性定義中那樣執行多項式有界次詢問。

3) 最后，Ω輸出一個新的三元組(σ*,I D ,I D ))，且這個三元組不是詢問階段簽密預

A B言機的輸出， I DA也不是詢問階段的密鑰提取預言機的輸出。如果 U nsignc( σ*,dB, I DA)的結果不是符號⊥，則A贏得游戲。

3 新的基于身份簽密算法S-IDSC

系統參數：給定安全參數k，PKG首先選取橢圓曲線上的2個q階的循環群 (G1,+)和 (G2,?)，G1的生成元為P，由 G1和 G2上Weil對或Tate對的變形得到雙線性變換記為PKG隨機選取自己的私鑰 δ ∈ Zq*，計算相應公鑰PKG再選取安全的對稱密碼算法(E,D)和3個散列函數其中l1是身份ID的比特長度，l2是 G1中元素的比特長度，n是明文比特長度。這樣，該算法的系統參數是

密鑰提取：給出用戶的身份 I DU，PKG計算相應的公鑰和私鑰 dU=δQU；本算法中發送者Alice和接收者Bob的身份公私鑰對分別記為(dA, QA)和(dB, QB)。

假定Alice要將消息m簽密發送給Bob，他們執行以下簽密和解簽密過程。

Alice簽密：

Alice發送密文σ=(t,r)給Bob，Bob收到密文σ后執行下面解簽密。

Bob解簽密：

算法的正確性證明：

關于算法要說明的是： dA和 dB本來是 G1上的點，在計算簽密中和解簽密中時需將它們轉換成 Zq*中的數。轉換的方法很多，比如，如果 G1是定義在有限域 Zq*上的橢圓曲線上的群，可以用 G1上點的橫坐標代表橢圓曲線上的點。關于這點文獻[12]有類似說明，可參考。

4 S-IDSC安全性及其效率分析

4.1 安全性分析和證明

假設S-IDSC中所使用的散列函數H1、H2、H3是隨機預言機。用符號 qi(i = 1 ,2,3)表示攻擊者詢問Hi的次數， qs和 qd分別表示攻擊者詢問簽密機和解簽密機的次數。

4.1.1 機密性

S-IDSC的機密性是基于雙線性對 Diffie-Hellman問題（BDH）的。所謂BDH問題是指：給定(P,a P,b P,c P ) ,計 算其中為未知，P是G1的生成元。

結論 1 對S-IDSC，如果存在一個 IND-IBSCCCA2攻擊者Ω能夠在t時間內，以ε的優勢贏得定義 1中的游戲，那么，就存在一個算法 C，能夠在時間內，以的優勢解決BDH問題，其中et表示計算一次雙線性對運算所需要的時間。

證明C接收了一個隨機的 BDH問題實例他的目標是計算出e(P,P )abc，其中算法 C將攻擊者Ω作為它的子程序利用。結論1的證明分模擬階段和分析階段2個階段進行。

1) 模擬階段

C需要維護 L1,L2, L3,Ls, Ld5張列表，用它們來記錄C對Ω詢問 H1,H2, H3,S igncrypt,Unsignc的回答，這些列表初始時是空的， L1,L2, L3分別用于跟蹤Ω對預言機 H1,H2, H3的詢問，Ls和 Ld分別用于模擬簽密預言機和模擬解簽密預言機。

H1詢問：C首先從 {1 ,2,…,q1}中選取2個隨機數 i,j。Ω對 H1進行多項式有限次詢問，對Ω的第i次詢問，回答 H1(I Di) = a P，對Ω的第j次詢問，回答 H1(I Dj)= b P。由于 a P,bP是 BDH問題實例中的值，因此， I Di和 I Dj的私鑰 di、 dj就分別是acP、bcP（C并不能計算出這些值），而BDH問題的值 e (P,P )abc可由算出。對第e≠i、j次的詢問，C從Z*q中隨機取一值be，計算，并將(I De, be)添加到 L1中，給出回答值 Qe。

H2詢問：C首先檢查列表 L2中是否存在(ωe, k2,e)。如果列表 L2含有該條目，C把條目中給出的回答 k2,e輸出給Ω；否則，C從 Z*q中隨機取一值 k2，將 (ωe,k2)添加到 L2中并輸出 k2。

H3詢問：C首先檢查列表 L3中是否存在。如果列表 L3含有該條目，C把條目中給出的回答 re輸出給Ω；否則，C從 Zq*中隨機取一個值r，將添加到 L3中并輸出值r。

密鑰提取詢問：當Ω詢問 E xtract(I DA)時，如果或j，那么C將失敗并終止模擬；否則，在列表 L1中查找對應的條目，C計算 I DA的私鑰并給Ω。

簽密詢問：任何時候Ω可以選擇消息m和 2個身份 I DA和 I DB，對進行簽密詢問（此前已經對 I DA和 I DB進行過密鑰提取查詢）。①如果，C可通過密鑰提取算法Extract(I DA)計算出 I DA的私鑰 dA，然后簡單地運行簽密運算 S igncrypt(m,dA, QB)即可。②如果或但，C按如下過程模擬 S igncrypt(m,dA, QB)：首先在 L1中找到(I DB, dB)，然后從 Z*q中隨機選取x′和s′，計算可以從上述 H2詢問獲得)，計算 r ′ ← H3(k1′,m)，并檢查 H3的條目中是否已經有三元組 ( k1′,m,r ′)，且如果是這樣，C重復以上過程，另選x′和s′，直到找到的三元組的前兩元在 H3的條目中沒出現過，并將此條目添加到 L3，再計算相應的最后將簽密密文給Ω，這個簽密密文在Ω看來是有效的。③如果 I DA和IDB就是 I Di和 I Dj，那么，C從 Zq*中隨機選取x*和s*，計算再任選，計算(可從對 H2的詢問獲得)，計算，類似②檢查 H 中是否已經有相應3的三元組如有，重復該過程，直到找到的三元組的前兩元在 H3的條目中沒出現過為止，并將此條目添加到L3，計算t*←E(s*m)，C最后

解簽密詢問：當攻擊者Ω觀察到關于 I Di和IDj的簽密密文時，它可能要 C解密σ*。這種情況下，C就告知他該密文無效。當簽密密文是關于 I DA和 I DB的，但不是 I Di和IDj時，Ω收到該解簽密詢問，首先計算(可從對 H2的詢問獲得)，計算檢查是否在L3中，如果不在，C拒絕解密該密文；否則，C解簽密恢復出m。

2) 分析階段

下面對上述模擬進行分析，計算C成功的概率。如果Ω在第一階段對 I Di和 I Dj執行密鑰提取詢問，C將失敗。而在 q1次密鑰提取詢問中，選擇(I D,I D )的方法有 c2種，因此，Ω選擇身份 I D和

i j q1iIDj作為挑戰身份的概率大于。在第二階段詢問中，如果Ω對執行 H2詢問，C將失敗，同理，在對 H2的 q2次詢問中Ω不對執行 H2詢問的概率大于q1。在對簽2密機的一次詢問中，由于 C失敗的概率最多為那么，q 次簽密機詢問失敗的概率最多為s，則C成功的概率至少是1因此，C 解決 BDH 問題的優勢至少為。在C的計算時間方面，每次簽密和解簽密詢問都是最多需要1次雙線性對運算。

4.1.2 不可偽造性

S-IDSC的不可偽造性是基于橢圓曲線上離散對數困難問題（ECDL問題）的。ECDL問題是指：已知計算使得，其中P是 G1的生成元。

結論 2假設橢圓曲線上離散對數問題是困難的，那么在隨機預言機模型下，S-IDSC是適應性選擇消息攻擊下存在性不可偽造的。

如果一個敵手能偽造一個S-IDSC中的簽名，那么他就能偽造文獻[12]中橢圓曲線上的短簽名SECDSS1。文獻[1]指出在離散對數困難問題下，如果將散列函數視為隨機函數，那么，簽名標準算法DSS的變體 SDSS1是在適應性選擇消息攻擊下存在性不可偽造的；因此，在橢圓曲線離散對數問題困難假設和隨機預言機模型下，S-IDSC是在適應性選擇消息攻擊下存在性不可偽造的。

4.2 效率分析

S-IDSC與已有基于身份的簽密算法相比，效率明顯提高，這主要體現在計算量和通信量兩方面。首先，從基于身份簽密中涉及的主要運算：雙線性對運算（P）、標量乘(M)和指數運算(E)來考察，S-IDSC的簽密算法需要1個雙線性對運算和1個標量乘運算，不需要指數運算；其解簽密算法需要 1個雙線性對運算和2個標量乘運算，也不需要指數運算，因此，S-IDSC共需要2個雙線性對運算，3個標量乘運算，不需要指數運算。要特別說明的是，S-IDSC中的2個雙線性對運算都是可以預計算的。進一步，考察S-IDSC的傳輸量，在S-IDSC中，需要傳輸的信息是σ=(t,r)，傳輸量是用表1給出本文算法與目前已有的幾個重要基于身份簽密算法的效率比較。在表1中， x( + y )表示x次雙線性對運算，y次雙線性對預運算。

表1 S-IDSC與已有重要基于身份簽密算法的效率比較

5 S-IDSC在ad hoc網絡中應用說明

對ad hoc網絡來說，密鑰必須由網絡節點自己動態生成并分發。在密鑰分發或傳遞過程中常常需要安全秘密信道，以確保密鑰分發過程的機密性和認證性，不僅如此，ad hoc網絡無線鏈路、微型終端、電池供電等特殊網絡環境，要求所使用的安全方案必須是輕量級的，力求最小的計算和傳輸量以節省資源。S-IDSC計算和傳輸代價低，從而可縮短密鑰分發的時間、節省帶寬資源，能有效地實現ad hoc網絡的密鑰管理的安全要求。下面以文獻[13]中ad hoc網絡的基于身份的(,)tn門限密鑰管理中服務節點系統密鑰份額更新為例，說明S-IDSC在ad hoc網絡安全協議中的應用方法。基于 S-IDSC的ad hoc網絡(,)tn門限密鑰管理中服務節點系統密鑰份額更新協議過程如下。

1) 初始化：由離線的PKG選擇ad hoc網絡的的系統參數，包括S-IDSC中的系統參數。

2) 更新請求：為了提高網絡的可用性，假設整個ad hoc網絡被劃分成定長時段，在每個時段結束前，各服務節點必須要為自己請求下一時段的新系統密鑰份額。為此，請求節點廣播請求信息；收到該信息的鄰居服務節點，驗證請求節點的身份，驗證通過，該鄰居節點為請求節點生成部分新系統密鑰份額，并對該份額進行簽密運算，將所得到的簽密密文通過公開信道發送給請求節點。

3) 更新生成：請求節點解簽密密文，獲得鄰居服務節點為它生成的部分新系統密鑰份額，然后通過可驗證秘密共享中的方法驗證份額的正確性。在(,)tn門限密鑰管理中，當請求節點收到并解簽密了t個鄰居服務節點的簽密密文，得到t個正確的部分新系統密鑰份額后，請求節點利用Lagrange插值公式，將這t個部分新的系統密鑰份額進行合成，生成自己的新系統密鑰份額。

此過程中由于S-IDSC的應用，實現了系統私鑰共享分額信息在ad hoc網絡公開信道的高效安全傳輸。

6 結束語

簽密作為同時實現機密性和可認證性的重要密碼工具，對解決ad hoc網絡目前面臨的安全問題具有重要意義。本文給出了一種新的基于身份的簽密算法S-IDSC，并證明了其在隨機預言機模型下是可證明安全的；關于新簽密算法S-IDSC的效率，通過與已有基于身份簽密算法的比較，體現出新簽密算法的高效性。尤其是其低的計算和傳輸需求，能很好滿足ad hoc網絡通信實現安全性的要求。通過對新簽密算法在ad hoc網絡密鑰管理安全協議中應用的簡述，說明了這種基于身份的新簽密算法在ad hoc網絡通信安全協議中的使用方法。在此特別指出，研究適合于ad hoc網絡安全通信的簽密算法，并將研究成果用于 ad hoc 網絡安全協議是必須加強的一個重要方向，這不僅是密碼學應用研究的需要，也是ad hoc 網絡廣泛應用的迫切需要。

[1] ZHENG Y L. Digital signcryption or how to achieve cost (signature &encryption) ＜＜ cost (signature) + cost (encryption)[A]. Cryptology-CRYPTO’97, LNCS1294[C]. Berlin, New York, Tokyo, 1997.165-179.

[2] LI F G, HU Y P, ZHANG C R. An identity-based signcryption scheme for multi-domain ad hoc networks[A]. ACNS 2007, LNCS 4521[C].2007. 373-384.

[3] KIM H, SONG J, YOON H. A practical approach of ID-based cryptosystem in ad hoc networks[A]. Wireless Communications and Mobile Computing[C]. 2007. 909-917.

[4] DENG H, AGRAWAL D P. TIDS∶ threshold and identity-based security scheme for wireless ad hoc networks[J]. Ad Hoc Networks, 2004,2 (3)∶ 291-307.

[5] LI J F, WEI D W, KOU H Z. Identity-based and threshold key management in mobile ad hoc networks[A]. International Conference on Wireless Communications, Networking and Mobile Computing 2006.(WiCOM 2006)[C]. 2006.1-4.

[6] KAMAT P, BALIGA A, Trappe W. An identity-based security framework for VANETs[A]. VANET’06[C]. Los Angeles, California, USA.2006. 94-95.

[7] MALONE-LEE J. Identity based signcryption[EB/OL]. http∶//eprint.iacr.org/2002/098/.

[8] LIBERT B, QUISQUATER J. A new identity based signcryption schemes from pairings[A]. 2003 IEEE Information Theory Workshop[C]. Paris, France, 2003. 155-158.

[9] CHOW S S M, YIU S M, HUI L C K. Efficient forward and provably secure ID-based signcryption scheme with public verifiability and public ciphertext authenticity[A]. Information Security and Cryptology-ICISC 2003, LNCS 2971[C]. Berlin, Springer-Verlag, 2004,352-369.

[10] CHEN L, MALONE-LEE J. Improved identity-based signcryption[A].Public Key Cryptography-PKC 2005, LNCS 3386[C]. Berlin,Springer-Verlag, 2005.362-379.

[11] BARRETO P S L M B, LIBERT N. Efficient and provably secure identity-based signatures and signcryption from bilinear maps[A].Advances in Cryptology-ASIACRYPT 2005, LNCS 3788[C]. Berlin,Springer-Verlag, 2005. 515-532.

[12] ZHENG Y, IMAI H. How to construct effcient signcryption schemes on elliptic curves[J]. Information Processing Letters, 1998, 68∶227-233.

[13] LI G S, HAN W B. A new scheme for key manegement in ad hoc networks[A]. ICN2005, LNCS 3421[C]. 2005. 242-249.