基于身份的動態(tài)層簇式無線傳感網絡認證算法

袁 馳

（中國人民大學信息學院，北京 100872）

（?通信作者電子郵箱chiyuan@ruc.edu.cn）

0 引言

常規(guī)的密鑰管理算法中以公鑰密碼基礎最為常見［1-3］，這種密碼體制可分為三大類：基于公鑰證書的密碼體制、基于身份的密碼體制、無證書密碼體制［4-5］，其中基于身份的密碼體制無論是在安全性或是計算復雜度上相對優(yōu)勢都較為明顯［6］。文獻［7］指出，基于身份密碼體制（ID-Based Cryptosystem，IBC）是最適合無線傳感器網絡（Wireless Sensor Network，WSN）的公鑰體制。但是基于身份體制有一個致命的缺陷就是密鑰托管問題，因為私鑰生成中心掌握著所有用戶的私鑰，它可以非常容易冒充任何節(jié)點用戶，私鑰生成中心可以解密任何用戶密文，可以偽造用戶簽名，并且不易被發(fā)現。因此，如何設計出既能充分利用各節(jié)點的身份信息從而簡化密鑰管理開銷，又能避免私鑰生成中心帶來的密鑰托管問題的安全認證算法，就成了無線傳感器網絡信息安全需要研究的一個重要問題。近年來，學者們針對此問題提出了各種解決方案，但多數方案仍然依靠私鑰中心（PRivate Key Generator，PRKG）來生成用戶私鑰，因此并沒有從根本上解決密鑰托管問題。

針對此，提出的基于身份的分簇認證算法（Identity-based Dynamic Clustering authentication algorithm，IDC）算法，拋棄私鑰中心，引入一個可信第三方公鑰中心（Key Generating Center，KGC），直接產生用戶公鑰（與無證書密碼體制使用公鑰中心和用戶共同產生用戶私鑰完全不同），從根本上解決了密鑰托管問題，還可以動態(tài)生成全局偽秘密、能耗較低、性能穩(wěn)定并且安全性好，非常適合WSN環(huán)境。具體特點如下：

1）沒有密鑰托管問題。IDC 算法結合橢圓曲線離散對數困難問題、哈希函數、解簽密等知識，與傳統(tǒng)的基于身份認證算法中由私鑰生成中心生成所有用戶私鑰不同，它利用一個公鑰生成中心，采用逆向思維方法，生成申請者的公鑰及其對應的驗證參數，發(fā)送給申請者驗證，而用戶的私鑰既不由公鑰中心生成，也不用和公鑰中心聯合生成（區(qū)別于傳統(tǒng)無證書系統(tǒng)），而是由用戶自己秘密選定。

2）算法擁有較低的計算、存儲量但安全性較高。IDC 算法同時考慮到WSN 的特性，首先，采用分層結構，將各群體分為不同的簇群；采用分級結構，將系統(tǒng)分為簇首層（Cluster-Head Layer）和內部層（Intra-Cluster Layer）。由基站（Base Station，BS）為每一個簇首統(tǒng)一編發(fā)Id 號，由簇首層身份信息構成身份信息矩陣ID（Identity-matrix），內部層節(jié)點身份信息不參與身份矩陣構成。其次，在分層結構的基礎上，又有針對性地采用了分級處理，針對BS、簇首、普通節(jié)點能量的差異，采用兩種不同的公鑰生成算法：簇首層（頂層）公鑰申請過程基于身份矩陣運算，而內部層（下層）節(jié)點公鑰申請基于身份Id 與哈希函數數學運算得出。第三，身份Id 信息在算法中得到充分應用，與算法結合緊密：由Id 信息生成的范德蒙矩陣，大大節(jié)約了存儲空間，同時也減低了計算量；由Id 信息產生單向多項式的各系數，用以產生動態(tài)偽秘矩陣，無需再采用隨機數等方式生成多項式系統(tǒng)，也降低了計算量；動態(tài)偽秘矩陣也使得算法的安全性大大提高。

3）結合WSN 環(huán)境特點，節(jié)點間認證采用一次（解）簽密方案，降低了通信能耗。IDC 算法采用一次（解）簽密方案，在一次通信過程中同時實現加密和認證功能（一次通信是相對于一個節(jié)點的（解）簽密過程而言，不考慮節(jié)點認證成功后的反饋信息或不成功的返回信息），極大地節(jié)省了資源。

需要指出的是，提出的IDC 算法，在解決了由私鑰中心帶來的密鑰托管問題的同時，引入了公鑰中心KGC，產生了一個新問題，就是合謀攻擊問題，即由若干節(jié)點合謀，對公鑰中心掌握的全局秘密D 進行破解的問題。對此，本文引入了身份Id 單向多項式，動態(tài)生成偽秘密矩陣D'，可以杜絕合謀攻擊，保證了算法的安全性。

1 相關工作

1.1 基于身份的認證體制

較為典型的基于身份認證算法有秦志光等［8］提到的密鑰隔離密碼系統(tǒng)（Key-insulated cryptography），將密鑰分成兩個部分，一部分由用戶自己控制，另一部分由一個物理安全的協(xié)助者保存。在需要使用密鑰時將兩部分的密鑰進行“拼接”從而得到一個完整的密鑰；但其沒能利用有效各節(jié)點的身份信息。陳淵等［9］提出一種基于身份但無線性對運算的加密算法，并在隨機預言機模型下證明了算法是適應性選擇密文安全的。兩種算法都采取一定方法避免了計算量較大的對運算操作，節(jié)省了開銷。但是兩種算法都借鑒無證書的思想，節(jié)點的私鑰由節(jié)點和私鑰生成中心（PRKG）共同生成，而非節(jié)點自己單獨生成，因此這兩種算法并沒有真正解決基于身份體制中的密鑰托管問題。危蓉等［10］提出了一種基于身份的WSN層簇式密鑰管理算法，較好地解決了WSN 密鑰管理問題，算法運用身份認證加密技術，對節(jié)點認證后進行分簇，并建立簇成員與簇頭之間共享簇密鑰，實現了系統(tǒng)構建、簽名、加密一體化，并通過分析對比，驗證了算法可以保證簇內完全連通并滿足無線傳感器網絡各項要求；但其采用橢圓曲線的Weil 雙線性對運算卻使得算法運算量增大。

郭江鴻等［11］提出了一個新的無線傳感器網絡密鑰協(xié)商算法，有效地解決了傳感器網絡密鑰協(xié)商方案中雙線對運算能耗較高且耗時較長的問題，但其算法描述系統(tǒng)公私鑰對是預先設定，在其廣播階段并沒有將系統(tǒng)私鑰x 廣播，而在節(jié)點間相互通信之初卻直接利用了系統(tǒng)私鑰x，其算法并未說明x 是何種方式秘密傳送至各節(jié)點，而系統(tǒng)私鑰x 如何有效分發(fā)正是此類算法一個關鍵環(huán)節(jié)，因此此算法雖然有一定創(chuàng)新但是回避了一個重要問題，僅是理論可行。郭萍等［12］將基于身份的RSA 機制與輕量級（Certificate Authority，CA）思想相結合，構建了一個基于身份及輕量級CA 混合模型的傳感器網絡密碼算法（簡稱LCA）。但這兩種算法的計算量與通信量均較大，仍然需要改進。

Yuan 等［13］提出一種（Authentication of Vandermonde Matrix，AVM）認證算法，利用矢量的正交空間內積與張量積特征，采用復雜度較低的矩陣相加（D+）方法來構建密鑰，保證了算法的前向安全性。另外，引入了隨機數與零知識證明算法，算法的不可逆性得以提高，使得攻擊節(jié)點不能篡改和替換消息，有效杜絕了中間人攻擊。

1.2 分簇管理

李英磊等［14］提出一種動態(tài)分簇的密鑰認證算法，對節(jié)點能量消耗和網絡安全性作出分析，給出了相關的解決辦法；Rohbanian 等［15］提出了層簇式WSN 進行密鑰管理，首先構建最短路徑，使用基于橢圓曲線的密碼方案進行會話密鑰分發(fā)；董發(fā)志等［16］提出一種“集中分簇，分布簇頭選舉”的算法，綜合考慮節(jié)點能量、距離等因素，達到了較好的能量和安全性的平衡；鄧紹江等［17］提出采用網絡分化思想提高系統(tǒng)通信效率，利用分組加密算法EBS-GL（Grouping and Layered key management strategy in WSN based on Exclusion Basis System），通過匯總消息比對方法及奇異點排除策略進行認證，增強了系統(tǒng)可恢復性；危蓉等［10］提出的算法也屬于分簇管理研究范疇。

2 算法設計

2.1 基本思想

2.1.1 動態(tài)安全過程

由用戶密鑰生成過程可知，公鑰中心在生成兩個集合B1和B2后利用B2產生公鑰中心驗證參數Kij，將B1=｛bj0，bj1，…，bjn｝發(fā)送至申請簇首用于生成Kij，分析部分矩陣［D'ID］T如式（1）所示（為表示方便，用“(B1)i”表示第i個簇首申請者得到的公鑰中心返回集合）：

如果不引入偽秘密矩陣D'，由秘密矩陣D 直接參與簇首節(jié)點的申請過程驗證，由于秘密矩陣D 為對稱矩陣，易得(n*n)的D 有個獨立的矩陣項，而集合B1會多次以固定的系數（dij）計算出結果返回給相應節(jié)點，這必然會導致相應個數節(jié)點的合謀攻擊，從而使攻擊者得到全局秘密矩陣D。

2.1.2 合謀攻擊條件

設全局秘密矩陣 D 中元素 dij為未知數xij，且有i，j ∈{0，1，2，…，(n -1)}，則對于每一個簇首申請節(jié)點而言，均可以得到一個如式（3）的線性方程組：

這些線性方程組的每一行中的未知數xij均相同，因此可以分別取各線性方程組的相同行（以第1 行為例），組成新的線性方程組，進而可反推出全局秘密D的對應行元素，最終破解全局秘密矩陣D，如式（4）所示：

2.1.3 應對策略

本文引入偽秘密矩陣D'，矩陣元素由一個單向函數多項式計算得出，分析多項式易知，由霍納法則（Honer’s Rule）通過不斷地把x作為公因子從降次后的剩余多項式中提取出來：

過程如表1所示。

可以看出，在已知x，Idi和p的情況下，非常容易求得y；而反過來，在已知y，Idi和p 的情況下，想求得x，則至少需要n2(lb p)2次乘法，當n 及p 很大時，可知由y 求x 幾乎不可能。由分析可以看出，引入偽秘密矩陣D'有兩個好處：

一是各偽秘密矩陣D'能保證動態(tài)變化。對于不同的簇首申請者，公鑰中心都會根據不同的申請者驗證份額Vi=（Vx，Vy）中的Vx（p=Vx）生成相應的偽秘密矩陣D'，因此不同的D'中對應的元素d'ij也各不相同。

二是單向函數y=f(x)能保證算法的前向安全性。即便是攻擊者通過其他手段，得到了偽秘密矩陣D'中的元素d'ij，其想實現由d'ij推算出秘密矩陣D中的元素dij也幾乎不可能，從而杜絕了各不同的簇首申請者合謀攻擊。

表1 計算過程Tab.1 Calculation process

2.2 外部通信（簇首間）

2.2.1 系統(tǒng)初始化

定義網絡中無線傳感器簇數目為n，每個簇首賦予一個特定的數字作為其身份標識，即簇首節(jié)點集合為｛Id1，Id2，…，…，Idn｝，公鑰中心首先進行如下操作：

步驟1 選定素數q，由此確定循環(huán)群Gq，之后選取此循環(huán)群上的橢圓曲線E，G為基點，p為其階。

步驟2 選取公秘矩陣D 并秘密保存，D 必須滿足是（n×n）對稱矩陣。

步驟3 構造兩個哈希函數：

步驟4 構建簇首身份范德蒙矩陣ID。

步驟5 依據簇首節(jié)點集合產生一個單向函數多項式，如下：

根據不同的簇首節(jié)點產生不同的偽秘密矩陣元素。

步驟6 公鑰中心對簇首層廣播循環(huán)群Gq、橢圓曲線E、基點G、哈希函數H0和H1。

2.2.2 用戶密鑰生成

步驟1 由申請者選取橢圓曲線上某一點P（xi，yi）作為自己的私鑰，即Si=（xi，yi）；同時隨機選取數zi∈Ζ，計算得出用戶的驗證份額Vi=ziSi=(Vx，Vy)。

步驟2 申請者秘密保存隨機數zi（用于隨后通信過程中的簽密過程），把自己的驗證份額Vi連同身份信息Idi合并得［Vi‖Idi］一并發(fā)送至公鑰中心（隨機數zi不能發(fā)送給公鑰中心，以防止公鑰中心泄密，zi僅用于隨后簇首間通信）。

步驟3 公鑰中心收到信息后，利用單向函數多項式y(tǒng)=f(x)mod(p)和秘密矩陣D中元素dij，產生一個偽秘密矩陣D'中元素（為了保證每一個簇首節(jié)點對應不同偽秘密矩陣，需要取申請者的驗證參數參與到單向函數多項式的計算中，即有，如下：

從而得偽秘密矩陣D'。

步驟4 公鑰中心在身份范德蒙矩陣ID 中隨機選取一列，比如j列，與上步生成的偽秘密矩陣D'聯合，計算集合B1=并由此計算出用戶Idi的公鑰Pi=G ?Vi及公鑰中心的驗證參數Kij=

步驟5 公鑰中心發(fā)送用戶公鑰Pi，集合B1及驗證參數Kij至申請者。

步驟6 申請者收到公鑰中心返回的信息后計算Kji=并驗證是否等于上步計算的Kij：如果通過，則申請接受公鑰Pi，并秘密保存自己的私鑰Si，同時公鑰中心對外公布用戶公鑰Pi；否則，返回錯誤，申請失敗，輸出符號⊥。

至此，完成各簇首節(jié)點的公私鑰的配置。

2.2.3 簽密

身份為Idi的節(jié)點為了給身份Idj的簇首節(jié)點發(fā)送一個消息Msg，執(zhí)行以下步驟：

步驟1 Idi首先取公鑰申請階段秘密保存的隨機數zi，與橢圓曲線上的基點G 計算ziG=R（r1，r2）；之后取r1與簇首Idj的公鑰Pj計算得驗證參數（u，v）=r1×Pj；再用u對消息Msg加密得Ecr=Eu(Msg)。

步驟2 利用哈希函數計算參數M=H1(r1‖Ecr)，參數N=H0(k1M)G。

步驟3 計算參數O'=Si-H0(r1M)mod q，參數O=M +O'。

步驟4 Idi將秘密保存的隨機數zi與上述各參數，生成密文Ci=(Ecr，R：(r1，r2)，N，O，z)，發(fā)送至Idj。

2.2.4 解簽密

簇首節(jié)點Idj接收到密文Ci后，執(zhí)行以下步驟：

步驟1 首先提取節(jié)點Idi的R 的前半部分r1，與自己的公鑰Pj計算驗證參數U'=r1Pj=(u，v)。

步驟2 計算M=H1（r1‖Ecr），O'=O-M。

步驟3 用u對加密消息Msg解密得到Msg=Du(Ecr)。

步驟4 計算P'=N+O'G，并驗證（zi·P'）？=（Pi）：如果驗證二者相等，則簇首Idi與Idj的共同的通信密鑰即為u，同時接受明文Msg，之后將v 保存，作為簇內共享密鑰；否則驗證失敗，輸出符號⊥。

至此，完成簇首之間通信。

2.3 簇內通信

2.3.1 簇內密鑰對申請

在每個簇內通過上述簇首節(jié)點解簽密過程預置對稱共享密鑰v。簇首為Idi的簇內節(jié)點Idim需要申請自己的公私鑰對。按如下步驟：

步驟1 節(jié)點Idim選取隨機數rm，與簇共享密鑰v（由上述簇首層運算得出）相乘之后發(fā)送［rm‖v（Sm）‖Idim］至簇首Idi。

步驟2 簇首Idi選取隨機數rn，依次計算兩個參數P1=rnSm-H0(Idim)，P2=rn+H0(Idi)H0(P1Idim)。

步驟3 簇首Idi計算節(jié)點Idim的公鑰Pim=G·Sm，之后發(fā)送密文Ci=(P1，P2，H0(Idi))至簇內節(jié)點Idim。

步驟4 節(jié)點Idim計算P2Sm的值是否等于P1+H0(Idim)+rmH0(Idi)H0(P1)的值：如果相等，則申請者接受公鑰Pim，并秘密保存自己的私鑰Sm，同時簇首Idi對外公布簇內用戶公鑰P1；若不相等，則返回錯誤，申請失敗，輸出符號⊥。

至此，完成各內部節(jié)點的公私鑰的配置。

2.3.2 簇內解簽密

簇內各節(jié)點申請完密鑰對后，按上述簇首解簽密過程進行簽密與解簽密，在此不再重復描述。

3 性能分析

3.1 安全性證明

定理1可驗證性。在簇首層（Cluster-Head Layer）公鑰中心和簇首Idi按照上述用戶密鑰生成步驟進行公鑰申請，驗證若Kji=Kji，申請者接受分配公鑰的過程滿足算法正確性要求。

證明 首先將2個矩陣偽秘密矩陣D'和簇首身份信息矩陣ID）進行乘和轉置運算：

而在用戶密鑰生成步驟中，公鑰中心隨機選取的第j 列，與偽秘密矩陣D'聯合，計算集合B1=｛bj0，bj1，…，b（jn-1）｝和集合

由上述過程可以看出，2 個矩陣（偽秘密矩陣D'和簇首身份信息矩陣ID）運算后得到的新矩陣K 仍然是對稱矩陣，對于矩陣K 中的元素來說，均有Kij=Kji。因此公鑰中心公鑰分配過程滿足正確性要求。 證畢。

定理2不可否認性。上述簇間通信過程中的簇首間驗證參數Pi的再計算過程滿足算法正確性要求。

證明

因為O'=Si-H0(RiM)mod q，N=H0(RiM)G

所以P'=N+O'G=N +(Si-H0(RiM)mod q)G=H0(RiM)G +(Si-H0(RiM)mod q)G=Si?G

因為Pi=Vi?G，Vi=zi?Si

所以Pi=zi?Si?G=zi?P' 證畢。

3.2 抗攻擊性

IDC 算法中，申請者的私鑰由申請者自己秘密保存，公鑰中心生成的是申請者的公鑰，在通信過程中傳遞的驗證參數也是基于申請者的公鑰，即使某一節(jié)點被捕獲，并不會對算法的機密性產生影響。其次，由于偽秘密矩陣D'的引入，實現的全局秘密的動態(tài)生成，敵手難以對偽秘密矩陣D'進行破解，而由dij'到dij的單向性質更加鞏固了這種假設，說明算法的抗攻擊（合謀攻擊）性得到了保證。

初始化配置完成后，某一簇首申請者通過基于身份矩陣的方法申請自己的公鑰，在申請成功后擁有自己的私鑰si和由公鑰中心分配的公鑰Pi，之后通過和同級另一簇首相互簽密從而獲得共同的通信密鑰u，因此，IDC 算法采用矩陣D 作為公鑰中心的全局秘密，結合動態(tài)偽秘密矩陣D'實現申請者公鑰生成，要比傳統(tǒng)基于身份的認證系統(tǒng)中用簡單數字或哈希函數等作為全局秘密要更為安全。

注 簇內通信過程中簇首與普通節(jié)點的申請過程與解簽密過程相似，唯一不同點在于簇內普通節(jié)點申請過程不是基于身份矩陣，而是基于身份Id 與哈希函數的數學運算得出，這樣做是為了降低簇內節(jié)點的計算量和存儲量，但二者生成密鑰對的思路相同，只是形式有差別，故此安全分析僅選擇簇間就可說明問題，簇內不再假設。

3.3 模擬實驗

3.3.1 場景設置

本文仿真實驗環(huán)境搭建參考CMU 大學MONARCH 項目（CMU Monarch Projects Wireless and Mobility extension）［18］提出的multihop無線網線模擬實驗所用方法。分3個步驟：一是修改并新增protocol 代碼文件*.cc 和*.h；二是對packet 頭文件*.tcl 和*.h 進行修改，同時對參數文件ns_default.tcl 進行定義；三是對makefile文件進行修改。

利用方法中的Setdest 程序隨機生成規(guī)模為60 的WSN 場景，相關參數的設置具體有三塊：

第一塊是網絡性能方面，如表2所示。

第二塊為各比較算法能耗量化設置，對算法AVM、EBSGL、LCA與IDC算法進行能耗和時耗比較。具體如表3所示。

第三塊為可變量固定場景設置。由于在AVM 算法、LCA算法中的參數N1、L1、N不是固定的長度，其選取數值不同會導致計算能耗差異，因此需要對其進行固定操作。文獻［1-2］中證明的RSA模數值最低安全保證長度值與閾值的最優(yōu)典型設置域，本文將實驗場景設置為6個，具體為：S1（N1，L1，N）：（256，64，1 024）；S2：（256，128，1 024）；S3：（512，64，1 024）；S4：（256，256，2 048）；S5：（1 024，256，2 048）；S6：（2 048，128，2 048）。通過編寫tcl 腳本定義出相應的通信過程，使用SET 命令對場景進行設置，包括網絡的模擬結構以及通信過程，之后通過tracefd文件記錄模擬過程的跟蹤數據。

表2 網絡性能參數設置Tab.2 Performance parameter settings of the network

表3 四種算法計算量對比Tab.3 Comparison of calculation amount of four algorithms

3.3.2 實驗對比

圖1和圖2給出了四種算法的能量消耗與時間消耗對比，總體看來，IDC算法在能量消耗與時間消耗方面均優(yōu)于其他三種算法?？梢钥闯?，在完成一輪最小粒度的通信過程中，IDC算法能量消耗達到了毫焦耳（mJ）級，時間消耗基本接近毫秒（ms）級，均遠優(yōu)于LCA、AVM、EBS-GL算法，充分說明IDC算法的優(yōu)勢。原因有：1）因為IDC算法在滿足上述安全需求的情況下，針對節(jié)點所處位置的不同及運算能力的差異，采用分層分級方法，在減少系統(tǒng)存儲量的情況下同時提升了算法的處理效率。2）因為IDC 算法采用的一次解簽密方案即實現了節(jié)點間的認證及公密生成，大幅降低了通信成本，通信資源開銷也因此變少。3）因為公鑰中心的核心秘密身份矩陣是由身份Id生成的范德蒙矩陣，矩陣的每一列元素都可以唯一生成，在節(jié)省存儲空間的同時也降低了算法計算復雜度。

其次，IDC 算法性能穩(wěn)定。由圖1 可以看出，從S1場景到S6場景（L1：64→128，N1：256→2 048）的變化過程中，IDC 算法在完成一次單精度乘法的耗時始終處于一個比較平穩(wěn)的水平，即能量消耗在1～10 mJ，跨度不大于1.3 mJ；時間消耗一直保持在0.002～0.006 s。而LCA 等算法在場景S3到S4的變化過程中，出現了比較大的波動。特別地，在S3場景下，新算法耗時0.003 s，而LCA 算法耗時接近0.1 s，新算法的效率要高出其將近30 倍，如圖2 所示。這就表明IDC 算法在傳送的信息比特位長度值變化幅度較大的情況下，具有較強的穩(wěn)定性。

圖1 四種算法的能耗對比Fig.1 Energy consumption of four algorithms

圖2 四種算法時耗對比Fig.2 Time consumption of four algorithms

4 結語

無線傳感器網絡是一種非常有應用前景的傳感器網絡。由于其自組織的網絡特點，設計出安全且低能耗的輕量級通信協(xié)議尤為重要。本文提出的基于身份的IDC認證算法，由公鑰中心生成申請者的公鑰，由用戶自己秘密選定私鑰，從而避免了基于身份認證算法的密鑰托管問題。同時，算法采用分層結構和分級處理，增強了簇間通信的安全性，降低了簇內節(jié)點的計算量和存儲量。通過實驗對比，新提出的IDC算法能夠保證網絡通信安全，并且具有低能耗和高穩(wěn)定特性，非常適合于WSN。由于目前國內外對研究對真實環(huán)境下的實際實驗測試工作研究還很薄弱，而本文所提到的實驗環(huán)境也僅是利用仿真軟件進行人為設定，證明了算法的理論可行性，但缺乏在實際環(huán)境下的演練測試，所以下一步工作的重點除了對算法本身的性能研究之外，將嘗試在真實環(huán)境測試所研究的算法。