向量运算加速的超混沌图像加密算法

葛 滨，陈 旭，陈 刚

(1.南通职业大学 电子信息工程学院，江苏 南通 226007；2.中国科学院半导体研究所，北京 100083)

近年来，如何保障数字图像在互联网上的安全存储和传输已经成为业界的研究热点[1-3]。与文本数据不同，图像数据具有二维结构、高冗余度和大数据量的特点，3DES和AES等加密算法已不再适用。虽然出现了Zigzag扫描[4]、Arnold变换[5]和幻方变换[6]等一些颇具特色的图像加密算法，但研究表明惟置乱算法仅能扰乱视觉信息，很难抵御现代密码分析技术[7]。对初值变化高度敏感的混沌系统能够产生大量优良的伪随机序列，天然符合密码设计所需的混淆和扩散规则[8-9]，因此随着混沌反控制技术的日趋成熟[10]，越来越多的研究人员正致力于使用混沌系统设计新型加密算法以彻底隐藏明文图像和密文图像之间的统计特性[11]。

相比普通混沌系统，超混沌系统结构更加复杂，具备在多个方向上拉伸折叠的能力，且两个以上正的李雅普诺夫指数使其在数字系统中能够保持更好的随机特性[12]。自文献[13]首次提出一种置乱-扩散结构的超混沌图像加密方案以来，先后出现了很多优秀的改进方案。文献[14]利用散列函数产生会话密钥提高了算法的明文敏感性，但是加密过程仅依赖异或运算，很难抵御选择明文等攻击。文献[15]引入遗传模拟退火的选择、交叉和变异操作改进算法的安全性，但其过于复杂的扩散过程导致加密速度较慢。文献[16]中引入密文分组链接加密使像素信息具有扩散能力，增强了算法安全性，但是其较慢的扩散过程导致运行效率不高。文献[17]将图像分块后利用多线程技术对加密流程进行加速，但是缺少了不同子块之间的扩散过程，因此难以抵御差分攻击。综上所述，超混沌系统虽然能够提高混沌图像加密算法的安全性，但现有方案中的扩散过程普遍将二维矩阵重构为一维序列后进行设计和优化，难以在安全性能和运行效率间找到平衡点，实用价值不高。基于此，针对图像二维结构特点，笔者提出一种基于向量运算的超混沌快速图像加密算法。

笔者引入向量运算，通过垂直方向和水平方向的并行分组链接加密，使任意位置像素信息能够在图像矩阵上快速扩散，提高算法的明文敏感性；使用研究最为广泛的超混沌陈(Hyper-Chen)系统产生原始超混沌序列，能够同时满足文中对安全性能和运行效率的需求；同时为适应上述扩散过程，设计了新的密钥矩阵生成方法和初始向量生成方法；此外，在会话密钥生成中引入时变的真随机数，进一步增强算法安全性。实验结果和分析表明，改进算法能很好地抵御穷举、选择明(密)文、差分分析等密码学攻击，且其扩散过程的时间复杂度仅为线性阶O(M+N)，在图像实时保密通信等场合具有较强的实用价值。

1 算法原理

设灰度明文图像P的尺寸为M×N，E表示加密运算，TC1，TC2，TC3，TC4表示扩散过程中产生的中间密文，则文中算法运行流程如图1所示。首先将填充真随机数明文图像的散列值分段量化产生系统初值等参数；然后在明文图像P上使用向量运算，经过两轮垂直方向扩散和两轮水平方向扩散后，产生几乎毫无关联的密文图像C。其中扩散过程所需的初始向量和密钥矩阵分别由低维混沌系统和超混沌系统产生。

1.1 混沌系统

1.1.1 超混沌系统

表1列举了目前图像加密算法中常用的混沌系统，相比而言，超混沌系统具有更多的初始数量，天然地具有更大的密钥空间。同时由表1可见，Hyper-Chen系统包含两个更大的正李雅普诺夫指数，具有更强的初值敏感性，不可预测性和抗退化能力[18-19]，且系统复杂度适中，因此文中算法设计中选用了该超混沌系统。

Hyper-Chen超混沌系统(简称系统(1))方程如下所示[20]：

(1)

其中，a，b，c，d，r为系统的控制参数。

由图2可见，当a=36，b=3，c=28，d=16和r=0.2时系统(1)表现出非常复杂的动力学特性，无法在异常稠密的相空间轨迹上对序列进行跟踪和预测，适用于产生文中扩散过程所需的密钥矩阵。

1.1.2 低维混沌系统

文中算法使用的Chebyshev映射(简称系统(2))产生的序列具有类噪声统计特性[21]，相比常用的Logistic映射，也不存在拟平凡密钥导致的退化问题。其方程如下：

xn+1=cos(βarccosxn)，xn∈[-1，1] 。

(2)

当系统(2)的控制参数β≥2时进入混沌状态。文中算法中令β=4，此时系统(2)在迭代速度和安全性方面取得较好的平衡[21]，适用于快速产生扩散所需的初始向量。

1.2 会话密钥生成与分段量化

散列函数具有显著的雪崩效应，输入的微小变化将产生完全不同的输出结果，因此将明文图像散列值作为会话密钥能够改善加密算法的明文敏感性。笔者引入真随机数，不同时刻加密同一幅明文图像时将会使用完全不同的会话密钥，克服了会话密钥不慎泄露可能导致的安全问题。

1.2.1 会话密钥生成

真随机数通过应用程序编程接口(Application Programming Interface，API)从Random.org网站获取，其熵源是自然界真实的随机现象[22]。会话密钥的具体生成步骤如下：

(1)初始化一个长度为N的空序列S。

(2)调用API接口获取真随机数填充序列S，且接口参数中设置Si∈[0，255]，i=1，2，…，N。

(3)将序列S填充到矩阵P的最后一行生成P′，即P′ =[P；S]。

(4)令H=SHA-256(P′)。

(5)输出长度为64的十六进制序列H=h1h2…h63h64作为会话密钥。

1.2.2 分段量化

混沌系统的初始值一般为小数，且需要预迭代消除暂态效应带来的安全隐患，因此将会话密钥进行拆分后量化，产生系统式(1)的初始值{x1，x2，x3，x4}及其预迭代次数p1，系统式(2)的初始值x及其预迭代次数p2，具体步骤如下：

(1)利用式(3)对会话密钥的h1h2…h47h48部分进行归一化处理，产生值域范围在0～1之间的系统式(1)的初始值，其中T为十六进制转十进制运算：

(3)

(2)利用式(4)将会话密钥的h49h50部分的值域从0～255线性平移为20～275，产生系统式(1)的预迭代次数p1，此举避免过短的预迭代次数导致的潜在安全隐患：

p1=T(h49h50)+20 。

(4)

(3)利用式(5)对会话密钥的h51h52…h61h62部分进行归一化处理，产生值域范围在0～1之间的系统式(2)的初始值：

x=T(h51h52…h61h62)×2-48。

(5)

(4)最后利用式(6)将会话密钥的h63h64部分的值域进行变换，产生系统式(2)的预迭代次数p2：

p2=T(h63h64)+20 。

(6)

1.3 密钥矩阵生成

原始超混沌虽然具有较强的随机性，但是其值域范围在实数域上，无法直接用于图像加密，还需量化为0～255之间的整数，同时也能改善序列的统计特性[23]。文中在量化的基础上，引入重构步骤，以生成与图像矩阵尺寸相同的密钥矩阵，具体步骤如下：

(1)初始化行为MN/4，列为4的空矩阵B。

(2)系统式(1)预迭代p1次后，将每轮迭代产生的新状态值{x1，x2，x3，x4}按照式(7)对矩阵B进行填充；

(7)

(3)利用式(8)将实数矩阵B量化生成为整数矩阵B′：

(8)

(4)最后将矩阵B′重构为M×N的密钥矩阵K。

1.4 采用向量运算的快速扩散加密

向量化计算利用一条指令同时完成多个数据的操作，是图像处理算法中最常用的并行计算方式[24]。为兼顾算法的加密速度和加密强度，在图像矩阵上基于行向量和列向量实现并行的密文分组链接加密，通过垂直方向的两轮并行扩散和水平方向的两轮并行扩散，使任意像素信息能够高效扩散至密文图像所有位置。

1.4.1 初始向量生成

第一轮扩散中的初始向量需要从外部输入，使用系统式(2)快速产生规模相对庞大的初始向量。具体步骤如下：

(1)初始化一个空序列X。

(2)系统式(2)预迭代p2次后，将每次新产生的状态值x填充至序列X，直到长度为N。

(3)按照式(9)将实值序列X转换为0～255之间的整数序列，即为初始向量IV。

(9)

1.4.2 扩散加密流程

下面结合图3中像素的扩散过程示意图具体阐述向量快速扩散的原理，具体步骤如下：

(1)输入明文图像P，密钥矩阵K，初始向量IV。

(2)按照式(10)以行向量为计算单元，从第一行开始在垂直方向上完成并行分组链接加密，生成中间密文矩阵TC1，其中加密第一行像素所需的初始向量IV由外部输入；

(10)

其中，mod为逐元素的取模运算。⊕为逐元素的按位异或运算。如图3(a)所示，像素信息在垂直方向上完成了后向扩散。

(3)将初始向量IV更新为第一轮扩散后的最后一行像素TC1[M，：]，重复步骤(2)的扩散过程，生成中间密文矩阵TC2，如图3(b)所示，像素信息已经扩散至该列的所有位置。

(4)按照式(11)将初始向量IV转置并更新为第二轮扩散后的最后一列像素TC2[：，N]，从第一列开始在水平方向上完成并行分组链接加密，生成中间密文矩阵TC3，扩散结果如图3(c)所示。

(11)

(5)将初始向量IV更新为第三轮扩散后的最后一列像素TC3[：，N]，重复步骤(4)的扩散过程，生成中间密文矩阵TC4，结果如图3(d)所示。至此，任意位置像素信息已扩散至密文图像上的所有位置。

(a)第一轮扩散 (b)第二轮扩散 (c)第三轮扩散 (d)第四轮扩散

(6)输出密文矩阵TC4，即为密文图像C。

1.4.3 解密流程

完整实用的密码算法必须配套解密流程，因为灰度图像中像素的值域为[0，255]，上述加密流程中的模运算和异或运算都存在有效的逆运算从而恢复出明文图像[25]。具体的解密步骤如下：

(1)输入密文图像C，密钥矩阵K，初始向量IV。

(2)根据式(12)的规则，从最后一列开始到第一列结束，以列向量为单位，完成水平方向上的第一轮解密，从加密流程反推易知，第一轮解密中所需的初始向量为TD1[：，N]。

(12)

(3)重复步骤(2)的解密流程，完成水平方向上的第二轮解密，其中所需的初始向量为TD2[：，N]。

(4)根据式(13)的规则，从最后一行开始到第一行结束，以行向量为单位，完成垂直方向上的第三轮解密，第三轮解密中所需的初始向量为TD3[M，：]。

(13)

(5)重复步骤(4)的解密流程，完成垂直方向上的第四轮解密，其中所需的初始向量为IV。

(6)输出矩阵TD4即为最终的解密图像D。

2 实验仿真与性能分析

基于Windows 7系统上的Matlab R2016a平台对8位标准灰度图进行实验，包含尺寸为256×256的Lena图像，512×512的Cameraman图像，1 024×1 024的Baboon图像和2 048×2 048的Timg图像。硬件资源主要包括：固态硬盘，Intel Core i5-6500 CPU，8 GB内存。采用定步长0.001和4阶龙格库塔算法求解超混沌系统。

2.1 抗统计攻击性能分析

直方图能够直观地反映像素的分布特性，图4是Cameraman和Baboon加密前后的统计直方图。实验结果表明，加密后灰度值近似等概率出现，分析人员无法依靠简单的频次攻击恢复明文图像。

(a)Cameraman明文

为了更好地评估加密后图像的抗统计分析性能，使用美国国家标准与技术研究院的SP 800-22随机数测试标准进行实验[26]。通过频率检测、游程检测和线性复杂度等15个测试方法，能够全面检验密文图像的统计特性。将上述两幅密文图像转化成比特序列进行检验，结果如表2所示，密文图像的随机特性非常显著，能够很好地抵御统计分析攻击。

表2 密文图像NIST随机性测试结果

2.2 信息熵分析

香农定理指出，当信息无序程度增加时，其熵值会随之增加，且当信息中每个元素的出现概率相等时，其熵值达到最大值。设一幅图像有L种灰度值gi(i=1，2，…，L)，且出现的概率分别为p(gi)，则图像的信息熵定义可表示为

(14)

如表3所示，文中算法的实验结果已经非常接近8位(共256种灰度值)随机灰度图像的理想信息熵值8，且相比现有方法更接近理想值，因此具有更好的加密效果。

表3 信息熵测试结果

2.3 抗相关攻击性能分析

通过扩散加密破坏相邻像素间的强相关性可以有效地隐藏明文图像和密文图像间的关联，利用式(15)进行对比实验，定量分析加密前后图像的相关性：

(15)

其中，ai和bi表示两个相同位置的灰度值。从3个不同方向随机选取3 000组相邻像素进行对比实验，加密前后的γ值如表4的第2～5列所示，通过扩散过程，密文图像中相邻像素已基本不相关。表4也列出了与文献[15-17]的对比结果。实验表明，文中算法对相关性攻击的抗性更强。

表4 图像相邻像素相关系数测试结果

2.4 抗差分攻击分析

明文像素的微小改变应当通过加密在密文图像上均匀扩散，正是这种密文对明文变化的异常敏感性使算法能够抵抗差分攻击。如式(16)所示，像素改变率(Number of Pixels Change Rate，NPCR)[3]和统一平均变化强度(Unified Average Changing Intensity，UACI)[3]可以定量描述密文图像随明文图像变化的程度。

(16)

其中，C1(i，j)=C2(i，j)表示相同位置两个灰度值的加密结果，若C1(i，j)=C2(i，j)，则D(i，j)=0；否则，D(i，j)=1。一幅灰度图像的NPCR和UACI理想期望分别约为99.609 4%和33.463 5%[3]。

从图像任意位置选择一个像素点，将其灰度值微调后，与原始明文图像进行对比实验，共计100组，计算结果如表5所示。相比现有方案，文中算法的结果更趋近于理想值。

表5 NPCR和UACI测试结果 %

Lena图像NPCR和UACI测试的变化曲线如图5所示，都在理想期望附近轻微波动。显然，利用差分攻击对文中算法进行破解不可行。

(a)NPCR变化曲线

2.5 密钥敏感性分析

密钥敏感性体现在两个方面：加密时具有微小差异的两个会话密钥使同一幅明文图像生成两幅完全不同的密文图像；解密时会话密钥的微小错误将导致解密图像依然不可辨认且与明文图像毫无关联。

本阶段会话密钥通过SHA-256算法计算填充真随机数的Cameraman明文图像生成：74b93cda996d3b83e616fbb567b14396bb37cae585fcd7ff614fcff8f2c8d3af。文中的会话密钥由7个部分组成，如表3第1列和第2列所示，分别对密钥的7个部分做微小(即每个部分的最低位进行比特翻转)改变后，通过NPCR和UACI进行对比实验，结果如表6的第3列和第4列所示，结果表明加密密钥的微小改变引起了雪崩效应，生成了具有显著差异的密文图像。

继续用上述具有微小差异的密钥对Cameraman的密文图像进行解密实验，对比结果如表6第5列和第6列所示。密钥的微小改变导致解密出的图像依旧杂乱无章且与明文图像毫无关联。

表6 密钥差异对加解密结果的影响 %

2.6 密钥空间分析

在计算机等数字系统中，通常以会话密钥占用的比特长度来描述密钥空间的大小。使用SHA-256算法对填充真随机数的明文图像进行计算生成长度为256 bit的散列值，而2.5节的实验结果表明其每一位的微小变化都能影响加密和解密的结果，因此密钥空间为256位，远大于100位的安全密钥长度[15]，足以抵抗暴力攻击。

2.7 时间复杂度分析

传统的扩散加密算法需要将图像矩阵转换为一维序列进行至少两轮串行扩散操作，需2MN次运算才能生成密文图像，时间复杂度为平方阶O(MN)，文中算法由两轮垂直并行扩散和两轮水平并行扩散操作组成，只需2M+2N次运算就可生成密文图像，时间复杂度为线性阶O(M+N)，具有明显优势。在相同仿真环境下对上述两种方案进行编程实现，实验结果如表7所示，文中算法通过向量运算加速后的运行效率有了至少4倍以上的提升，同时也明显优于现有方案，因此更加适用于对实时性要求较高的应用场合。

表7 图像加密时间 s

2.8 抗噪性能分析

密文在公开信道传输中有时会受到一些噪声的污染，图像数据相比文本数据，冗余度更高，所以算法应当具有一定的鲁棒性，使遭受轻微噪声污染后的密文图像依然能解密出部分有效信息。首先，在Baboon密文图像上添加均值为零，方差分别为0.000 3和0.000 5的高斯噪声后进行解密，结果如图6(a)和图6(b)所示，能够恢复出部分有效信息。然后，在Baboon密文图像上添加均值为零，方差分别为 0.003 和0.005的椒盐噪声后进行解密，结果如图6(c)和图6(d)所示，也能够恢复出部分有效信息。两阶段实验结果表明，文中算法产生的密文图像在公开信道传输中具有较好的抗噪声性能。

(a)方差0.000 3

3 结束语

笔者提出一种基于向量运算的超混沌快速图像加密算法。该方法通过量化和重构原始超混沌序列，产生统计特性优良且与明文图像尺寸相同的密钥矩阵，在此基础上以行向量和列向量为计算单元，在图像矩阵上实现了并行密文分组链接加密，完成像素信息在密文图像上的快速全局扩散，时间复杂度仅为线性阶O(M+N)。此外，文中会话密钥由散列函数计算填充真随机数的明文图像产生，具有不可预测性且更加易于存储和传输。实验结果表明，文中算法能够兼顾运行效率和安全性能，且将来通过改进和优化移植到GPU等并行计算平台能够进一步提高加速比，具有很高的实用价值，广泛适用于图像实时保密通信等场合。