混合型公钥密码算法在无线传感器网络加密中的应用设计

贺涛

（四川水利职业技术学院 信息工程系，四川 成都 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—），女，四川宜宾人，讲师。研究方向：计算机图形学。