基于四叉树的空域图像选择加密算法

2022-10-28

图像加密算法中目前使用比较广泛的有基于四叉树编码的图像加密算法。该加密算法主要对图像进行四叉树置乱加密，具有安全性较高、保持数据编码格式和数据压缩率不变等优点。但它没有充分利用图像特性，因此，其加密数据最较大，增加了计算复杂度。为此，我们在该加密算法的基础上，从减少加密数据量和提高安全性两方面入手，提出了一种新的图像选择加密算法——基于四叉树的空城图像选择加密算法。

一、四叉树置乱加密算法

1、四叉树编码

四叉树编码是最有效的图像压缩编码方法之一，广泛应用于GIS中。其基本思想是将2n×2n像素组成的图像构成的二维平面按4个象限进行递归分割，直到子象限的数值单调，从而得到一棵四分叉的倒向树，该树最高为力级。对如图1(a)所示的图像，可用四叉树编码法得到如图1(b)所示的四叉树。四叉树按存储方式的不同，分为线性四叉树和非线性四叉树2种。一个含m=2n×2n个像素的图像，其四叉树编码的时间复杂度为o(4m/3)，编码速度很快。由于四叉树编码具有算法简单、运算速度快、压缩率大等优点，因此广泛应用于图像编码中。

基于四叉树的空城图像选择加密算法

2、置乱加密算法

我们提出了2种四叉树置乱加密算法：（1）将同属1个父节点的4个子节点置乱，而保持节点阆父子关系不变；（2）将同一高度的节点（包括叶子节点和内部节点）进行置乱。2种置乱
算法的密钥空问分别为：

基于四叉树的空城图像选择加密算法

其中，H表示四叉树的高度；KHtree表示高度为日的四叉树置乱后获得的置乱空间；Nh表示h高度上内部节点的个数；Mh表示h高度上叶子节点个数；Ho表示本高度以上（不包含本高
度）的任何高度上都没有叶子节点。

通过分析可以看出，第（2）种置乱方法的密钥宅间更大、加密效果更好且图像恢复难度更大。

二、基于四叉树的空城图像选择加密算法描述

本文根据图像选择加密的基本思想，在第（2）种置乱方法的基础上提出一种新的图像加密算法。该算法主要过程如下：

（1）取出图像的1个位平面，将其捌分为若干16×16的块。

（2）将每个16×16的块划分为4个8×8的子块，并对其位置置乱。如图2所示。

基于四叉树的空城图像选择加密算法

（3）对每个8×8的子块进行四叉树编码。如果64个值相等，则称其为均匀的。

1）若不均匀，则将8×8子块内部同一高度的节点进行置乱，如图3所示。

基于四叉树的空城图像选择加密算法

2）若均匀，则加密其值。

三、基于四叉树的空城图像选择加密算法的实验结果

原始图像为大小为160×160的图像Lena，置乱和加密采用混沌Logistic映射，即xn+1=4×xn×(1-xn)。初始密钥为0.34，加密了MSB和第6级位平面，实验结果如图4所示。

基于四叉树的空城图像选择加密算法

四、基于四叉树的空城图像选择加密算法分析

1、加密数据量

通过加密算法描述可知，本文加密算法的加密过程主要包括以下3个部分：

（1）对4个8×8矩阵块的位置置乱。

（2）对非均匀8×8矩阵块的内部置乱。

（3）对均匀8×8矩阵的加密。

通过仿真实验得到图像MSB中均匀和非均匀8×8矩阵块的比倒，如表1所示。

基于四叉树的空城图像选择加密算法

在位置置乱过程中，因为对每个8×8矩阵都要进行处理，所以加密数据量为原MSB的1/64≈1%。由表1可以看出，一般图像的非均匀8×8像素都在50%以下，因此，内部置乱过程涉及的数据量最多约为50%，加密过程的数据量最多约为50%÷64≈1%。整个文件加密过程的数据量最多约为1%+50%+1%=52%，例如Lena.bmp的加密数据量只有1%+34%+ 66%÷64≈36%。

2、安全性分析

加密算法的安全性主要依赖密钥的安全性，而密钥的安全性与密钥空间大小、密文对密钥的敏感度有很大关系。

（1）密钥空间

内部置乱过程在整个加密过程中占有很大比例。本文内部置乱采用“同一高度的节点一进行置乱”。由式（2）可知，8×8矩阵形成的四叉树高度为3，可得最少的密钥空间为24H=243，最多的密钥空间为64！。在位置置乱过程中，16×16矩阵的密钥空间为4！。

由上述分析可知，当每个高度都只有一个内部节点时，内部置乱过程会出现密钥空间过少的问题。虽然这种情况出现的概率很小，但仍对算法安全性构成威胁。在最极端的情况下，即8×8的像素矩阵中63个点都同值时，密钥空间大小虽然可达243，但实际明文空间只有64种情况。此时只要穷举明文就能达到攻击放果。为了进一步提高安全性，本文提出一种对针对置乱算法的改进算法，其步骤如下：

1）对待加密图像文件通过密钥生成一个8×8伪随机矩阵A。

2）对待内部置乱的8×8矩阵口计算：

其中，N1是值为1的点的个数；No是值为0的点的个数。若Drff大于阙值T（如T=44)，则置标志位S=1，转第（3）步，若小于T，则置S=0，转第（4）步。

3）对矩阵A和矩阵B进行异或操作得到矩阵B’，转第（4）步。

4）对矩阵B或B’进行内部置乱操作。

上述改进算法对只有少数像素值不同的8×8矩阵和一个伪随机矩阵进行异或操作，增加该矩阵四叉树结构中内部节点的个数，从而提高密钥空间和明文空问。由式（1）可知，增加一个内部节点，置乱空间大约能提高29倍。因为对每个8×8矩阵都要添加一个标志位S来表明该矩阵是否进行过异或运算，所以会多占1/64×m bit，其中，m指图像像素个数。

（2）密文对密钥的敏感性

虽然内部置乱过程完成对多数数据文件加密，但由表1可以看出，大部分像素属于均匀8×8块，因此，对均匀8×8矩阵的加密同样具有重要作用。本实验采混沌Logistic映射，因为混沌映射具有初值敏感性，所以即使初值只有很小的改变，迭代多次后产生的伪随机序列仍会出现巨大变化。因此，即使攻击者获得了部分明文及相应密文，也无法恢复密钥流。

小知识之四叉树

四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。这种数据结构是由_拉斐尔·芬科尔(Raphael Finkel) 与_J. L. Bentley_在1974年发展出来。类似的数据分区方法也称为_Q-tree。