混合型公鑰密碼算法在無線傳感器網絡加密中的應用設計

賀濤

（四川水利職業技術學院 信息工程系，四川 成都 611321）

混合型公鑰密碼算法在無線傳感器網絡加密中的應用設計

賀濤

（四川水利職業技術學院 信息工程系，四川 成都 611321）

針對混合型多變量公鑰密碼算法進行了方案設計，并采用TOSSIM工具對其進行了模擬仿真實驗，驗證了該算法程序的正確性。通過將該算法應用到到無線傳感器網絡中，并將其運用到不同的硬件平臺上，分析其在運算速度以及存儲方面的性能情況，同時還將其與其它加密算法進行了對比分析，最終說明該算法能夠很好的應用到無線傳感器網絡加密中。

無線傳感器網絡；混合型多變量公鑰密碼算法；TinyOS；加密算法

多變量公鑰密碼體制（MPKC）是以求解有限域上的非線性多變量方程組的數學問題為基礎的，這也是一個NP難題[1-4]。縱觀當前的實際研究情況，量子計算機在處理NP難題上并不具備什么優勢[5-6]，所以MPKC是具備抵擋量子計算機沖擊的潛在能力的，也將是能夠滿足于后量子密碼時代的公鑰密碼體系之一，同時通過與傳統公鑰密碼體制相對比可以發現多變量公鑰密碼算法具有運算量較低以及速率很快等優勢，并且非常符合無線傳感器網絡運算性能相對來說比較低的特征。盡管其公私鑰存儲占用空間相對比與其他算法來說較大，但仍能夠符合當前傳感器節點的條件。然而現如今，大多數的多變量公鑰密碼方案全是基于雙極型的，并且都有被攻破缺陷[7-11]，而基于混合型多變量公鑰密碼算法的設計研究還非常少，因此本文研究設計了混合型多變量公鑰密碼算法在無線傳感器網絡加密中的應用。

1 混合型多變量公鑰密碼系統

首先就是要構建一個混合型的多變量公鑰密碼中心映射H：kn+m→kl，即

其中，h1是 k[x1，x2，…，xn，y1，y2，…，ym]上的多項式，并且滿足特定條件：①若隨機給定一組數值，H將變成一個關于（y1，y2，…，ym）的線性方程組，通過該方程組能夠很簡便的求解出（y1，y2，…，ym）的值；②若隨機給定一組數值，H將變成一個關于（x1，x2，…，xn）的非線性方程組，通過該方程組也能夠很簡便的求解出（x1，x2，…，xn）的值。

當確定好合適的中心映射H之后，使用一組可逆仿射隱藏映射H，最終將得到其公鑰為：

式中，L1、L2以及 L3分別表示 kn→kn、km→km以及kl→kl的可逆映射。

2 混合型多變量公鑰密碼算法方案設計

2.1 建立算法模型

1）建立中心映射結構：

其中，F表示包含q個元素的有限域，r、g及b都是正數，r+g+b=n，wi∈F[y1，…，yr，…，z1，…，zg，…，t1，…，tb]，則中心映射W的完整結構如下：

2）構建公鑰映射：

分別構建兩個可逆仿射變換S1：Fr→Fr及S2：Fg+b→Fg+b與可逆線性變換S3：Fg→Fg，則構建公鑰映射：Fn→Fg如下：

2.2 建立算法方案

根據構建的公鑰映射建立混合型多變量公鑰密碼算法簽名過程如下：

2.3 方案實現設計

1）參數選取設計 參數選取條件r+g＞b，直接攻擊的復雜程度將隨著變量數目增加而急劇升高，然而如果變量的數目過于大時，針對無線傳感器節點的較少資源以及低功耗的性能來說是很難完成的。如果選取參數為r=20，g=24，b=10，那么其安全性能夠高達280。

S2：Fg+b→Fg+b，其結構和S1一樣，僅有的差別就是其系數和偏移量數目，需存儲的元素數目總計（g+b）2+（g+b）=（g+b）（g+b+1）。

依據公式（3）可知，中心映射W需存儲g個多項式系數 Ait′，Bij，Cik，Djk，Ekk′，Gi，Hj，Lk，M，總計 g（r2+ rg+rb+gb+b2+r+g+b+1）。

因此，私鑰需存儲的元素數目總計為：r2+r+g2+（g+b）（g+b+1）+g（r2+rg+rb+gb+b2+r+g+b+1）。

針對公鑰，需存儲公鑰映射的系數，若具有n個變量，則需存儲的元素數目總計為（n+1）（n+2）*g/2。

公鑰和私鑰的存儲空間不單單決定于變量數目，而且還跟域的結構有關，相異的域及其實現方法的差異將導致其占用不同的內存空間。實現方式可分為以運算換時間及以空間換時間兩種方式，其中以運算換時間的方式占用的內存少但是需要大大提高運算次數，相反以空間換時間提高了運算速度但是大大提升了內存占用率，因此，在無線傳感器網絡上使用時應均衡考慮空間及速度這兩個方面。

3）功能模塊設計 功能模塊包含有限域模塊、矩陣模塊、高斯模塊、公鑰和私鑰產生模塊以及簽名和其驗證模塊，其具體功能如圖1所示。

圖1 功能模塊設計

3 實驗結果及分析

實驗的主要目標是將混合型多變量公鑰密碼算法應用到無線傳感器網絡中，同時在不同平臺上依據各參數取值得到加密時間，并進行對比分析，首先采用TinyOS[12]自帶的TOSSIM（TinyOS simulator）仿真工具來驗證算法的正確性，然后在實際環境中把該算法加載到無線傳感器節點中構成傳感器網絡進行運行測試。

3.1 TOSSIM仿真實驗與分析

3.1.1 實現過程

以Windows為實驗平臺實現模擬，因為TinyOS是運行于Linux操作系統，所以選擇一個相當適用GNU工具集在Windows上實行嵌入式系統開發的Cygwin[13-15]作為一個類Unix的模擬環境，其工作界面見圖2所示。

圖2 Cygwin工作界面

選取相對較小的參數以驗證算法的邏輯正確性，因此選取參數為r=7，g=7，b=7，有限域選取GF（28），包含的不能約多項式為x8+x6+x3+x2+1。該算法的實現方案是以模塊化的TinyOS操作系統構建起來的，因此這個系統中的應用設計應該要以模塊化為基礎，其程序結構圖見圖3所示。

圖3 算法程序結構圖

此算法程序包含系統自定義MainC、TestGSV、GSV、Matrix、Gaussian以及GF6個模塊部分，各個模塊之間應用接口進行通訊連接，其中箭頭出發點表示接口的應用者，與之對應的箭頭另外一點表示接口的提供者，比如TestGSV模塊運行過程中要調用GSV模塊，他們經過DigtSign_GSV接口進行通訊連接，然而此接口能夠完成簽名與驗證的功用，其具體說明見表1所示。

表1 各模塊具體信息

3.1.2 實驗結果及分析

仿真結果見圖4，第一部分表示需要加密長度是7的原始信息，和實驗設置的參數一樣；第二部分表示通過算法加密之后的信息，其長度是21，第三部分表示還原之后的信息。

圖4 仿真結果

根據圖4可知，初始信息和還原之后的信息沒有變化，即驗證了算法的正確性；全部的元素都是選自GF（28），且都在[0～255]范圍內，符合元素取自有限域的條件；初始信息與經過算法加密之后的信息長度與設置參數狀態一樣，再次驗證了算法的正確性。

3.2 無線傳感器網絡上的應用實驗

1）不同參數結果對比分析 選取各不相同的參數，其公私鑰長度對比見表2所示。

從表2中能夠得知，公私鑰的長度隨著變量數的持續增大二增大，同時其長度增大速率也越來越大。當安全級別增加至280時，公鑰長度及私鑰長度已經非常靠近37 k及32K了，這也就說明其存儲內存空間最少得達到32 k。

2）不同硬件平臺對比與分析 依照表2列舉的參數分別選擇不同變量數把混合型多變量公鑰密碼算法運用到MICAz節點以及TelosB節點中，并且運算其要求的內存空間大小以及其各自的執行時間，見表3所示。

表2 公私鑰長度對比

表3 不同硬件平臺存儲占用空間以及時間對比

根據表3的數據可知，兩種硬件平臺在內存空間方面上要求非常靠近，并且MICAz節點要求的內存空間相對來說較大。當變量數等于21時，MICAz節點中的程序已經不能再執行了，因為存儲空間要求3 350 Bytes的內存占用空間，同時調用函數也要求若干空間，這就將致使整體的內存要求大于4 k，從而引致其不可再在在該節點上執行。對于TelosB節點上變量數增加至36時才不能執行，其主要原因是TelosB能夠供給的內存空間具有10 k，在實際情況下如果運用以空間轉時間方式來節省內存，是能夠成功執行的，其安全級別也能夠高達260，但是這將在很大程度上縮減其加密的效率。圖5反映了隨著n值的增大，加密程序所需的平均時間的增加趨勢。

圖5 算法加密程序執行時間

盡管MICAz的內存空間相對來說比較小，但是相應的 MICAz節點在執行時間方面基本上是TelosB節點的1/4，比TelosB提高了很多，與此同時伴隨著變量數的不斷增多，相差的倍數也越來越大，所以相對于整體情況來看，MICAz節點和TelosB節點都具有自身的優勢，針對實時性條件相對較高的應用應選擇MICAz，反之針對安全性條件較高的應用應選擇TelosB節點。

3）不同加密算法的對比分析 TinyECC[14-15]是TinyOS操作系統中相對來說非常成熟的密碼庫，與TinyECC算法加密的對比見表4所示。

表4 不同加密算法對比

根據表4可知，該算法運行效率很高，再一次驗證了MPKC密碼算法的運算高效性，僅有的缺點就是私鑰長度，能夠通過外存來增加內存的方法來提升內存空間，通過該方法就能夠使得安全級別達到280，但是這將縮減加密算法的效率。

4 結束語

通過實驗驗證了算法的可行性和實用性，并從正確性、運行效率和存儲空間分析算法，把混合型多變量公鑰密碼算法應用在不同的硬件平臺上，包括MICAz以及TelosB，對比并分析了不同參數和不同平臺的差異。同時與其他加密算法進行對比分析，最終說明混合型多變量公鑰密碼算法能夠很好的應用在無線傳感器網絡加密中。

[1]司海飛，楊忠，王珺.無線傳感器網絡研究現狀與應用[J].機電工程期刊，2011，28（1）:15-16.

[2]杜曉明，陳巖.無線傳感器網絡研究現狀與應用[J].北京大學學報，2008，26（1）:41-43.

[3]朱紅松,孫利民.無線傳感器網絡技術發展現狀[J].中興通訊技術，2009，15（5）:1-30.

[4]胡健，劉婉，唐雄燕.無線傳感器網絡的應用現狀及國內應用前景[J].中國科技論文在線，2007.

[5]裴慶祺，沈玉龍，馬建峰.無線傳感器網絡安全技術綜述[J].通信學報,2007，28（8）:113-122.

[6]李晶，王福豹，段渭軍，等.無線傳感器網絡節點操作系統研究[J].計算機應用研究，2006，23（8）: 28-30.

[7]馬文龍，高寶成.一種動態無線傳感網絡操作系統-SOS[J].電腦知識與技術:學術交流，2009，3（12）: 1576-1577.

[8]李澤華.Hyper-O數字簽名算法與 UOV數字簽名算法在無線傳感器網絡上的實現[D].廣州：華南理工大學，2014.

[9]潘浩，董齊芬，張貴軍，等.無線傳感器網絡操作系統TinyOS[M].北京：清華大學出版社，2011.

[10]Buchmann J,Bulygin S,Ding J,et al.Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems[C]//Cryptology and Network Security.Springer Berlin Heidelberg,2010:140-155.

[11]陳歡.資源受限情況下 Rainbow的硬件優化設計[D].廣州：華南理工大學，2012.

[12]Levis P,Lee N,Welsh M,et al.TOSSIM:Accurate and scalable simulation of entire TinyOS applications[C]//Proceedings of the 1st international conference on Embedded networked sensor systems. ACM，2003:126-137.

[13]Racine J.The Cygwin tools:a GNU toolkit for Windows[J].Journal of Applied Econometrics,2000，15（3）:331-341.

[14]Liu，An，Peng Ning."TinyECC:A configu-rable library for elliptic curve cryptography in wire-less sensor networks."Information Processing in Sen-sor Networks[C]//IPSN'08.International Conference on. IEEE，2008.

[15]Xiong X,Wong D S,Deng X.TinyPairing:A Fast andLightweightPairing-BasedCryptographic Library for Wireless Sensor Networks[C]//Wireless Communications and Networking Conference（WCNC），2010 IEEE.IEEE，2010:1-6.

Applied design of mixed public-key cryptography algorithm in wireless sensor networks encryption

HE Tao
（Information Engineering Department，Sichuan Water Conservancy Vocational College，Chengdu 611321，China）

In view of mixed multivariable public key cryptography algorithm design，and simulation using TOSSIM tool for the simulation experiment，verified the accuracy of the algorithm program.Through this algorithm is applied to wireless sensor networks，and applied to the different hardware platforms，the analysis of its performance in speed and storage，will also be it with other encryption algorithm is analyzed，finally shows that the algorithm can well applied to the wireless sensor network encryption.

WSN；hybrid multivariate public key cryptography algorithm；tinyOS；encryption algorithm

TN915

：A

：1674-6236（2017）02-0154-05

2016-04-17稿件編號：201604174

國家自然科學基金資助項目（51175515）

賀 濤（1977—），女，四川宜賓人，講師。研究方向：計算機圖形學。