基于混沌的无线传感器网络分组加密算法

葛仕杰，汪烈军，李永明

(1.新疆大学 软件学院，新疆 乌鲁木齐 830046；2.新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046)

0 引 言

随着无线通信技术的发展和国家对万物互联的倡导，WSN现已广泛应用于环境监测、医疗监测、军事监测、智能电网、智能交通、智能家居等多个领域，保证通信安全[1]显得尤其重要。根据TinySec(Security for TinyOS)、SPINS等安全协议的推荐，目前WSN中广泛使用的算法为RC5算法。RC5-w/r/b算法是专利算法，商业推广成本较高，并且32 bit分组的RC5算法已经被证实存在安全隐患。RC6算法的出现是为了解决RC5算法存在扩散不足的缺陷，但由于算法中模乘运算占用过多的计算空间，导致计算能耗过高而不适用于大多数WSN。近年来，许多学者提出了轻量级分组密码[2]设计方案来替换RC5算法。田四梅设计了新的混沌S核[3]提升了算法的安全性，但也占用了较多的存储空间。邓昀等[4]通过对RC6算法增加对称层的方式降低了硬件资源消耗，使用双密钥机制达到了算法轻量化的目的。L.Yi等设计了基于Feistel网络结构[5]的混沌S核加密算法和混沌分组加密算法，通过实验验证了Feistel结构的加密算法具有更高的执行效率。Yuling Luo等[6]针对许连杰提出的CWSN算法进行改进，在加密函数中使用两个一维混沌映射参与加解密来提高混淆和扩散特性。王亚华等[7]借助云服务器的强大计算能力，将子密钥同步转移到云服务器上，从而设计出了更为安全的一次一密动态子密钥加密方案，但是节点频繁的接收密钥，导致传输过程能耗较高，且信道安全性和稳定性难以保证。Masoumeh.Sharafi对BCC算法[8]的改进提升了算法性能，通过减少BCC算法中的置换调用次数，增加算法轮数的方法，提升了算法的内存利用率，大大降低了算法能耗。卢政桥[9]通过logistic混沌随机序列对WEP通信协议进行改进，得到安全的加密算法，这种加密方式没有考虑整型后的混沌序列存在短周期的问题。LongTeng Yi等通过正弦混沌映射、baker映射、复合混沌映射[10]、线性同余生成器生成S核来增加扩散，增强加密算法的安全性，过多混沌映射引入使得算法计算能耗增加。结合上述算法的特点，设计出基于RC6算法的轻量级分组加密算法，算法使用RC6的加密框架，用两个一维混沌映射替代了RC6算法的模乘运算，这样一来既提升了算法加解密速度，又达到降低计算能耗的目的，本文还对加、解密函数进行了改进，引入两个一维混沌参与加、解密函数，使得算法更好抵抗明文攻击，具有更高的安全级别。

1 一种适用于WSN的算法设计方案

RC6算法最小明文分组是128 bit，针对WSN的数据包特征分组较大会引入过多冗余字节，32 bit的明文分组的加密算法被认为最适合用于WSN软件加密。为使RC6-32/20/16算法更好用于WSN，将RC6中4个32 bit的寄存器改为4个8 bit的寄存器，Feistel网络结构下的8 bit的数据单元，非常适合WSN中字长为8 bit的节点运算，这样单次加密的明文分组大小就是32 bit。本文提出的方法使用了CBC(分组连接)模式[11]，初始向量也为32 bit。在加解密算法中取消了复杂的模乘运算，代替为Cubic混沌映射参与加解密，使用RC6中的循环位移函数，解决了RC5中循环位移不依赖寄存器中所有位的不足。Feistel网络结构最大的优势就是加解密算法可逆，能够将F函数进行复杂的设计，文献[2]中详细对比分析了当前18种轻量级分组加密算法，讲述了置换网络与Feistel网络的应用特点。本文主要用两个一维混沌Logistic、Cubic和线性同余生成器生成主函数，整个算法中只涉及模加、模减、循环位移等简单的运算。

混沌现象在第一次被发现和定义后，人们陆续发现许多混沌现象，在诸多混沌现象中，离散性混沌映射已经被证实在加密中优于较多混沌方程，WSN加密中常用的离散混沌映射有Logistics映射、Cubic映射、Tent映射、Henon映射等。由于高维混沌[12]较为复杂多用于图像加密[13]，并不适用于资源有限、计算能力较弱的WSN中，因此在本文所提算法使用的是两个一维混沌，两个一维混沌参与算法的加解密及主密钥的生成，cubic混沌映射参与子密钥的生成。

1.1 Logistic混沌方程介绍

一维Logistic映射在WSN中应用最多，如式(1)所示

xn+1=μxn(1-xn) 0≤μ≤4

(1)

式中：μ是参数，当μ∈(3.57,4] 时，Logistic出现混沌现象，由于混沌映射存在浮点运算，而节点不能处理浮点运算，因此需要对Logistic映射进行整型化，整型化过程在文献[12]中有详细的推导过程，就不再赘述。整型化后如式(2)所示

(2)

根据封闭式原理，整型后的公式只要初始值不取0，则迭代结果zk∈[1,2a-1]，a=2L-1， (L为计算机字长)，当取L=32，整型后的最小周期为14 448。式(2)中只涉及简单的模加、模减和循环位移运算，能够在节点上完成。

1.2 Cubic混沌方程及其整型化过程

一维Cubic混沌映射如式(3)所示

(3)

a，b是参数，图1关于a的映射图像，可以看出随着参数a的增大，输出区间越来越小，图2是关于b的映射图像，当参数b=2.3时图像出现混沌状态。通过图1可以得到当a=4时，xk∈[-1,1]， 为了获得较好的随机状态，取a=4，b=3， 得到公式

(4)

图1 Cubic混沌映射关于a的图

图2 Cubic混沌映射关于b的图

为了避免节点处理浮点运算，需要将式(4)进行整型化处理，令yk=c(xk+1)， 可以得到

(5)

将式(5)带入式(4)，可以得到

(6)

(7)

式(7)中消除了迭代后存在零解的情况，根据封闭式原理，当初始值在区间 [0,2c-1] 上任意取值，都不会在迭代后出现零值，且迭代后的值yk∈[0,2c-1]， 经过整型化后Cubic混沌映射可以用于WSN网络中资源受限的节点处理数据。

2 算法设计

2.1 加密算法

加密算法采用CBC分组模式加密，将输入的32 bit明文序列先与上一次密文进行异或操作(首次输入明文序列时，与32 bit的初始向量异或)，整个密文序列中每个单独加密的分组都与前一组的密文有着更强的关联性，以此消除明文、密文序列间的统计性规律，增强算法的混淆和扩散特性。在每组加密的过程中，将32 bit明文序列从低到高位依次存放在A、B、C、D这4个寄存器中，加密算法都是以8 bit的数据为单位进行处理，整个算法里只涉及加法、移位、异或等简单的节点CPU运算指令，保证算法在安全性的基础上，具备加密速度快、能耗低的优势。

本文所提加密算法采用RC6的加密体系结构，如图3所示，⊕表示按位异或运算，‘+’代表模2w加运算，a<>b表示a向左或向右移动b位，f密函数，S为子密钥，每轮加密用到2个子密钥，加上开头和结尾用到的4个子密钥，一共需要用到2r+4个子密钥(r表示加密轮数)，该算法加密轮数定为7轮(第三节会进行详细说明)。

图3 算法加密结构

加密过程的描述：

整个加密包含两个相似的Feistel结构，该结构的最大特点就是每轮只处理一半的数据，在第一轮加密时，轮函数f只作用于B和D，完成对数据A和C的处理，为了更好的掩盖明文信息，这里对B和D先跟子密钥完成异或操作，在最后一轮加密时，为了保证产生的密文信息扩散效果相同，添加了两个子密钥对A和C进行异或操作。在重复迭代过程中，轮函数f对异或后的数据B、D加密，加密产生的序列循环位移数是3个字节(这里w=8)，此时B产生的新序列的ASCII值对8取余作为C的循环位移量，同理D产生的新序列的ASCII值对8取余作为A的循环位移量，这两个位移量会根据输入明文信息的改变而不同，因此我们称为动态位移量，B产生的新序列与A完成异或操作后，再完成动态位移后再与轮密钥异或完成对A的单轮加密过程，其加密结果需要存放到D中。对C的加密过程与上述相同，完成单轮加密的序列需要存放在B中。B和D在第一轮中没有变化，只需要将对B异或后的序列存放在A中，将D异或后的序列存放在C中，这样在每轮加密时就能处理到各个存储器中的数据。

Feistel是一种对称的网络结构，f函数对于算法的加密效果的起到决定性作用，该网络结构无需要求f函数可逆，因此在设计函数时可以根据算法需求进行调整。图4是f函数的内部结构，P是16 bit的置换盒。

如图4所示，我们在设计f函数时，先将输入的8 bit数据扩展为16 bit的数据，为了使扩展后的数据信息与初始信息差异化更大，引入了一个16 bit的置换盒(P盒)，置换是加密中最常用也是最有效的扩散方式。扩展后的序列被分为左右两个部分，再引入f函数设计中最为关键的非线性函数，我们将整型后的两个混沌映射分别作用于其中的一部分，最后将产生的混沌序列异或，得到的还是8 bit的序列。经实验结果证明，对原序列扩展后引入混沌映射得结果，在混淆和扩散上远远好于混沌映射依次作用于8 bit的初始值。

图4 f函数内部结构

混沌映射的迭代轮数由输入的8 bit序列决定，由于在8 bit的处理器上，整型化后的Cubic映射周期最大值仅为26。为避免迭代次数超过Cubic映射最大迭代周期，本文取混沌迭代的最大轮数为13，经过多次实验证实，迭代13轮不会出现混沌现象衰退的情况，也能很好保证输入消息经过多次迭代，达到良好的扩散效果。通过输入序列对13进行取余计算，得到动态的迭代轮数，保证在每轮加密中混沌映射的迭代伦数都不一样，可以提升算法的安全性。

2.2 密钥扩展算法

在密钥扩展算法的设计中，我们先对主密钥序列的生成过程进行了改进，我们通过线性同余随机数生成器生成两个32 bit的初始序列，然后将这两个序列作为两个混沌映射的输入，经过混沌迭代产生两个随机的32 bit的序列，之后我们引入混沌级联的思想，将两个迭代后的序列异或，产生32 bit的主密钥序列，重复执行几次我们就获得了多个32 bit的序列，随机选取4个不同的序列组成加密所需的128 bit主密钥序列。

在8 bit处理器上，整型化后的Cubic映射周期最大值仅为26，文献[6,7]通过自相关性计算，证明了整型后logistic混沌映射、Cubic混沌映射存在的短周期问题，解决办法就是将产生的混沌序列进行复合，复合的操作即将两个混沌映射产生的序列进行异或操作，图5是复合混沌序列进行量化后的自相关性，可以看出量化后的复合序列具有良好的自相关性，说明混沌序列具有良好的随机性。

图5 复合序列的自相关性

为进一步扩大序列的周期，保证序列具有更好的随机性，在此基础上引入线性同余随机数生成器，本文使用参数最常用取值的公式，可以表示为

L(n+1)=(16807×L(n))mod(231-1)

(8)

加入线性随机数生成器后，根据延长周期复合定理可知，新的复合序列的周期是3个序列周期的最小公倍数，也就是线性同余序列的周期231-1， 新的复合序列的产生过程如图6所示。

图6 复合序列的生成过程

从图6复合序列产生的32 bit的随机序列中随机选取4个不同的序列Z1、Z2、Z3、Z4， 按照选取顺序从高位到低位组成128 bit的主密钥K，为方便表述将主密钥K用16个8 bitki划分，即K={k0,k1…k15}， 密钥扩展算法每轮产生两个子密钥，因为需要产生2r+4个子密钥，所以需要执行r+2轮，算法1是一轮子密钥算法的生成过程，P表示16 bit的置换，其存储的位置置换信息称为P盒。

算法1：密钥扩展算法

输入：128 bit主密钥K={k0,k1…k15}

输出：2个8 bit子密钥kr1、kr2

(1) for i=0 to 15 do

(2) {

(3) if i%2==0

(4)ki=Cubic(ki);

(5) else

(6)ki=ki⊕ki-1；

(7)ki=Cubic(ki);

(8)ki-1ki=P(ki-1ki);

(9) }

(10)K=K≪7;

(11)kr1=k0⊕k8;

(12)kr2=k4⊕k12;

算法1中主密钥由16个8 bitki组成，当i为偶数时执行混沌映射，当i为奇数时先ki与ki-1进行异或，异或的结果再次经过混沌映射，每两个ki计算完就用16 bit的P盒进行置换，置换操作执行8次后生成新的128 bit密钥序列，新的密钥序列循环位移7位，得到新的主密钥序列用于下一轮子密钥生成。循环位移位数遵循log2w规则，其中w表示序列长度，因此w=128 bit，计算结果为7，所以循环位移7位。轮密钥是选取每个Zi的高8位字节异或而得。

2.3 解密算法

如上所述Feistel结构是对称，因此解密算法就是加密算法逆过程，唯一的区别就是子密钥的使用顺序与加密相反。例如加密算法密钥参与顺序为Ki1，Ki2，Ki3，Ki4， 那么解密算法的密钥参与过程为Ki4，Ki3，Ki2，Ki1。 解密过程中的置换盒如下

3 实验结果

本文所提算法用C语言实现，本节通过详细对比实验数据验证了所提算法的安全性。

3.1 统计性测试

3.1.1 “0-1”平衡性测试

首先将密文转为二进制表示，如果加密效果良好，那么二进制密文中“0”、“1”应当是均等分布的，理论上各自占据的比例为0.5，为方便说明，n0表示二进制密文中“0”的个数，n1表示二进制密文中“1”的个数，n表示二进制密文中“0”、“1”的总数，那么式(9)中ε的值越趋近零，表示密文的“0-1”平衡性越好。本文对4个不同明文数据长度进行加密，加密后的密文序列进行平衡性分析

(9)

测试结果见表1，当密文数据越多时，ε的值越接近零。4个不同长度密文的“0”、“1”分布都几乎是均等的，这表明加密后的密文具有很强的“0-1”平衡性，通过概率统计对比明文和密文的“0”、“1”分布，很难获得有用的信息，因此可以抵抗统计攻击。

表1 “0-1”平衡性测试结果

3.1.2 字符平衡性测试

字符频率统计为了分析明文和密文中ASCII值 [0,255] 分布情况，根据统计结果分析出明文的关键信息，是协助破译密文有效手段，良好的加密算法，能够消除密文ASCII分布的波动，与明文ASCII没有有效的关联关系，达到难以通过统计的方式获取有效信息的效果，良好的加密方案产生的密文ASCII值平均比例为1/256，即0.0039。图7是10 029 327 bit明文各字符ASCII值的统计结果，可以看出明文ASCII取值非常不平均，部分的字符在明文中出现的次数过多，这极有可能分析出有效信息。图8是密文各字符ASCII值的统计结果，可以看出密文ASCII分布没有规律性，且各字符ASCII统计比例非常平均，统计概率在0.0039附近波动，具有非常好的字符平衡性，具备良好的抗概率统计攻击。

图7 明文字符ASCII值占比统计

图8 密文字符ASCII值占比统计

3.2 信息熵测试

信息熵用来衡量系统的混乱程度，系统的混乱程度越高熵值越大，这里将密文的序列值划分为8 bit字节为单位，那么在密文序列足够混乱的情况下信息熵为8，由于密文序列无法做到均匀分布，因此信息熵值越接近8，则验证密文混乱性越好，加密的安全性越高。信息熵的计算公式可以表示为式(10)，其中P(Si) 表示被测信息S中每个8 bit字符Si出现的频率，理想情况下字符分布是均等的，那么每个字符出现的概率为1/28，因此理想情况下式(10)的计算结果等于8，意味着计算所得结果越接近8，则加密算法的混乱效果越好

(10)

表2列出了不同密文长度情况下的信息熵，从结果可以得到密文长度越大，信息熵越接近于8，整体信息熵接近于理想值，密文信息复杂度很高，具备抵抗信息熵攻击的能力。

表2 密文信息熵测试结果

3.3 混淆和扩散测试

混淆指明文和密文的关系尽可能的复杂，扩散指明文序列中的一位尽可能多地影响密文中的位数。混淆和扩散在密码设计时主要以完全性、雪崩效应、严格雪崩效应为主要标准。加密算法的输入为nbit，输出为mbit，输入的样本空间大小为T，aij表示T中只改变输入的第ibit位，对应输出的第jbit位发生改变的个数，bij表示在样本空间中只改变第ibit位的输出与原输出之间的差分汉明重量为j的个数。 #X表示X中元素的个数，那么3个标准可以做以下定义。

完全性指加密算法输出结果的每一比特位与输入的所有比特位有关，数学定义为

(11)

雪崩效应指初始输入的任一比特位的变化应该造成加密输出平均一半的输出比特位发生变化，数学定义为

(12)

严格雪崩效应指输入的任一比特位的变化都应导致输出的每一比特位有一半的概率发生改变，数学定义为

(13)

表3是T=20 000时的测试结果，d1=1，d2=1，d3=1说明算法具有较好的非线性扩散特性，加密轮数越高，混淆和扩散效果越好，考虑到算法的安全性与性能的平衡，本文所提算法的加密轮数取7轮，一方面增强了算法安全性，另一方面兼顾算法的性能。表4是本文算法与其它算法的对比，算法执行7轮与其它算法相比都具备较好的混淆与扩散效果，雪崩效果仅次于MCS算法，严格雪崩效果仅次于RC6算法。验证了本文算法的混淆和扩散效果优于大部分传统经典算法，也说明本文所提算法有足够强的抗差分攻击能力。

表3 算法扩散和混乱性与加密轮数的关系

3.4 算法能耗仿真

本文使用TinyOS2操作系统自带的TOSSIM仿真工具对传感器节点进行仿真，实现了对RC5、RC6及本文所提算法节点能耗的数据收集工作。仿真实验设置的传感器节点数量为100，为尽可能准确获取算法的计算能耗，只收集CPU的能量消耗作为参考值，将100个传感器节点的CPU能耗平均值作为最终单个节点的能耗值。通过表5中节点能耗对比可以看出，RC5算法在计算能耗上有着绝对的优势，本文改进后的算法相较于RC6算法的计算能耗下降了23.9%。

表4 扩散和混乱性比较

表5 算法计算能耗对比

3.5 加密性能测试

受限于WSN节点的资源，算法执行速度与变量所占空间是衡量加密算法可行性的重要标准，表6表明本文所提算法的执行速度优于其它几种算法，所占空间仅高于单一混沌算法MCS和文献[6]所提算法，低于传统经典算法，提升执行速度可以大大降低传感器能耗，对于资源有限的WSN来说，牺牲一小部分空间换取更高的执行速度是值得的。因此，本文所提算法适用于WSN。

表6 执行速度与存储空间比较

4 结束语

本文对RC6算法进行改进，复合两个一维混沌映射的迭代序列，增强了序列的随机性，引入线性同余随机数生成器延长了序列的周期，随机选取4个复合序列组成128 bit主密钥，保证了算法的密钥空间足够大，可以抵抗穷举攻击。整型后的混沌映射参与加解密，替代了RC6算法的模乘运算，大大节省了计算能耗，也达到扩散和混淆效果。改进后的RC6算法可以处理32 bit的明文分组，由于继承了RC6算法的优势，加解密速度远高于RC5算法。经实验证实，该算法具备轻量级特点，安全性较高，性能优于多数传统算法，可以用于中小型WSN进行安全的数据传输。