賀濤

（四川水利職業(yè)技術(shù)學(xué)院 信息工程系，四川 成都 611321）

混合型公鑰密碼算法在無線傳感器網(wǎng)絡(luò)加密中的應(yīng)用設(shè)計(jì)

賀濤

（四川水利職業(yè)技術(shù)學(xué)院 信息工程系，四川 成都 611321）

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

無線傳感器網(wǎng)絡(luò)；混合型多變量公鑰密碼算法；TinyOS；加密算法

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

1 混合型多變量公鑰密碼系統(tǒng)

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

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

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

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

2 混合型多變量公鑰密碼算法方案設(shè)計(jì)

2.1 建立算法模型

1）建立中心映射結(jié)構(gòu)：

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

2）構(gòu)建公鑰映射：

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

2.2 建立算法方案

根據(jù)構(gòu)建的公鑰映射建立混合型多變量公鑰密碼算法簽名過程如下：

2.3 方案實(shí)現(xiàn)設(shè)計(jì)

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

S2：Fg+b→Fg+b，其結(jié)構(gòu)和S1一樣，僅有的差別就是其系數(shù)和偏移量數(shù)目，需存儲(chǔ)的元素?cái)?shù)目總計(jì)（g+b）2+（g+b）=（g+b）（g+b+1）。

依據(jù)公式（3）可知，中心映射W需存儲(chǔ)g個(gè)多項(xiàng)式系數(shù) Ait′，Bij，Cik，Djk，Ekk′，Gi，Hj，Lk，M，總計(jì) g（r2+ rg+rb+gb+b2+r+g+b+1）。

因此，私鑰需存儲(chǔ)的元素?cái)?shù)目總計(jì)為：r2+r+g2+（g+b）（g+b+1）+g（r2+rg+rb+gb+b2+r+g+b+1）。

針對公鑰，需存儲(chǔ)公鑰映射的系數(shù)，若具有n個(gè)變量，則需存儲(chǔ)的元素?cái)?shù)目總計(jì)為（n+1）（n+2）*g/2。

公鑰和私鑰的存儲(chǔ)空間不單單決定于變量數(shù)目，而且還跟域的結(jié)構(gòu)有關(guān)，相異的域及其實(shí)現(xiàn)方法的差異將導(dǎo)致其占用不同的內(nèi)存空間。實(shí)現(xiàn)方式可分為以運(yùn)算換時(shí)間及以空間換時(shí)間兩種方式，其中以運(yùn)算換時(shí)間的方式占用的內(nèi)存少但是需要大大提高運(yùn)算次數(shù)，相反以空間換時(shí)間提高了運(yùn)算速度但是大大提升了內(nèi)存占用率，因此，在無線傳感器網(wǎng)絡(luò)上使用時(shí)應(yīng)均衡考慮空間及速度這兩個(gè)方面。

3）功能模塊設(shè)計(jì) 功能模塊包含有限域模塊、矩陣模塊、高斯模塊、公鑰和私鑰產(chǎn)生模塊以及簽名和其驗(yàn)證模塊，其具體功能如圖1所示。

圖1 功能模塊設(shè)計(jì)

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)的主要目標(biāo)是將混合型多變量公鑰密碼算法應(yīng)用到無線傳感器網(wǎng)絡(luò)中，同時(shí)在不同平臺(tái)上依據(jù)各參數(shù)取值得到加密時(shí)間，并進(jìn)行對比分析，首先采用TinyOS[12]自帶的TOSSIM（TinyOS simulator）仿真工具來驗(yàn)證算法的正確性，然后在實(shí)際環(huán)境中把該算法加載到無線傳感器節(jié)點(diǎn)中構(gòu)成傳感器網(wǎng)絡(luò)進(jìn)行運(yùn)行測試。

3.1 TOSSIM仿真實(shí)驗(yàn)與分析

3.1.1 實(shí)現(xiàn)過程

以Windows為實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)模擬，因?yàn)門inyOS是運(yùn)行于Linux操作系統(tǒng)，所以選擇一個(gè)相當(dāng)適用GNU工具集在Windows上實(shí)行嵌入式系統(tǒng)開發(fā)的Cygwin[13-15]作為一個(gè)類Unix的模擬環(huán)境，其工作界面見圖2所示。

圖2 Cygwin工作界面

選取相對較小的參數(shù)以驗(yàn)證算法的邏輯正確性，因此選取參數(shù)為r=7，g=7，b=7，有限域選取GF（28），包含的不能約多項(xiàng)式為x8+x6+x3+x2+1。該算法的實(shí)現(xiàn)方案是以模塊化的TinyOS操作系統(tǒng)構(gòu)建起來的，因此這個(gè)系統(tǒng)中的應(yīng)用設(shè)計(jì)應(yīng)該要以模塊化為基礎(chǔ)，其程序結(jié)構(gòu)圖見圖3所示。

圖3 算法程序結(jié)構(gòu)圖

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

表1 各模塊具體信息

3.1.2 實(shí)驗(yàn)結(jié)果及分析

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

圖4 仿真結(jié)果

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

3.2 無線傳感器網(wǎng)絡(luò)上的應(yīng)用實(shí)驗(yàn)

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

從表2中能夠得知，公私鑰的長度隨著變量數(shù)的持續(xù)增大二增大，同時(shí)其長度增大速率也越來越大。當(dāng)安全級別增加至280時(shí)，公鑰長度及私鑰長度已經(jīng)非?？拷?7 k及32K了，這也就說明其存儲(chǔ)內(nèi)存空間最少得達(dá)到32 k。

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

表2 公私鑰長度對比

表3 不同硬件平臺(tái)存儲(chǔ)占用空間以及時(shí)間對比

根據(jù)表3的數(shù)據(jù)可知，兩種硬件平臺(tái)在內(nèi)存空間方面上要求非?？拷?，并且MICAz節(jié)點(diǎn)要求的內(nèi)存空間相對來說較大。當(dāng)變量數(shù)等于21時(shí)，MICAz節(jié)點(diǎn)中的程序已經(jīng)不能再執(zhí)行了，因?yàn)榇鎯?chǔ)空間要求3 350 Bytes的內(nèi)存占用空間，同時(shí)調(diào)用函數(shù)也要求若干空間，這就將致使整體的內(nèi)存要求大于4 k，從而引致其不可再在在該節(jié)點(diǎn)上執(zhí)行。對于TelosB節(jié)點(diǎn)上變量數(shù)增加至36時(shí)才不能執(zhí)行，其主要原因是TelosB能夠供給的內(nèi)存空間具有10 k，在實(shí)際情況下如果運(yùn)用以空間轉(zhuǎn)時(shí)間方式來節(jié)省內(nèi)存，是能夠成功執(zhí)行的，其安全級別也能夠高達(dá)260，但是這將在很大程度上縮減其加密的效率。圖5反映了隨著n值的增大，加密程序所需的平均時(shí)間的增加趨勢。

圖5 算法加密程序執(zhí)行時(shí)間

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

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

表4 不同加密算法對比

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

4 結(jié)束語

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

[1]司海飛，楊忠，王珺.無線傳感器網(wǎng)絡(luò)研究現(xiàn)狀與應(yīng)用[J].機(jī)電工程期刊，2011，28（1）:15-16.

[2]杜曉明，陳巖.無線傳感器網(wǎng)絡(luò)研究現(xiàn)狀與應(yīng)用[J].北京大學(xué)學(xué)報(bào)，2008，26（1）:41-43.

[3]朱紅松,孫利民.無線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀[J].中興通訊技術(shù)，2009，15（5）:1-30.

[4]胡健，劉婉，唐雄燕.無線傳感器網(wǎng)絡(luò)的應(yīng)用現(xiàn)狀及國內(nèi)應(yīng)用前景[J].中國科技論文在線，2007.

[5]裴慶祺，沈玉龍，馬建峰.無線傳感器網(wǎng)絡(luò)安全技術(shù)綜述[J].通信學(xué)報(bào),2007，28（8）:113-122.

[6]李晶，王福豹，段渭軍，等.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)操作系統(tǒng)研究[J].計(jì)算機(jī)應(yīng)用研究，2006，23（8）: 28-30.

[7]馬文龍，高寶成.一種動(dòng)態(tài)無線傳感網(wǎng)絡(luò)操作系統(tǒng)-SOS[J].電腦知識(shí)與技術(shù):學(xué)術(shù)交流，2009，3（12）: 1576-1577.

[8]李澤華.Hyper-O數(shù)字簽名算法與 UOV數(shù)字簽名算法在無線傳感器網(wǎng)絡(luò)上的實(shí)現(xiàn)[D].廣州：華南理工大學(xué)，2014.

[9]潘浩，董齊芬，張貴軍，等.無線傳感器網(wǎng)絡(luò)操作系統(tǒng)TinyOS[M].北京：清華大學(xué)出版社，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的硬件優(yōu)化設(shè)計(jì)[D].廣州：華南理工大學(xué)，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稿件編號(hào)：201604174

國家自然科學(xué)基金資助項(xiàng)目（51175515）

賀 濤（1977—），女，四川宜賓人，講師。研究方向：計(jì)算機(jī)圖形學(xué)。