图像加密算法之分形Hilbert曲线混合Gray码加密

基于Hilbert曲线与Gray码，我们提出两种针对任意矩形彩色图像的加密算法，其一是对图像像素点的空域置乱，其二是对像素点的24位R、G、B分量的空域置乱，解密过程即加密过程的逆。

一、Hilbert曲线

1、二维Hilbert曲线

经典的二维Hilbert曲线的描述如下：首先将正方形四等分，求出各个小正方形的中心，并将它们连接，其次，将各个小正方形再细分为4个相同的小正方形；并连接各个小正方形的中心；……；按照这种分法不断细分下去，并按一定规则一一连接，就可以得到如图1的Hilbert曲线。

2、 三维Hilbert曲线

一阶三维Hilbert曲线构造方法：将一立方体等分成8个小立方体，把8个小立方体的中心按一定的次序连接成一条曲线，即连成图2的三维单元。以三维单元为基础来构造高阶三维Hilbert曲线，因为它是整个曲线形状的基础，所以又称它为基元。

n阶三维Hilbert曲线构造方法：将一立方体等分成8个小立方体，每个小立方体用n-1阶三维Hilbert曲线代替，然后按基元一样的次序连接这8条n-1阶三维Hilbert曲线。为使曲线更精美，对8条n-1阶三维Hilbert曲线作适当的旋转使连接的首尾平行于一轴线，如图3。

3、Hilbert曲线图像置乱

传统意义上利用Hilbert曲线实现图像置乱的思想：对图像像素点按Hilbert曲线的规则遍历，将其存入一维序列中，再重新排列生成置乱图像。实践证明，这种置乱算法应用性不强，如10×10大小的图像则不能按此规则置乱。

两种比较典型的算法，一种（算法1）是对非正方形图像分成四块满足Hilbert遍历规则的正方形块，分别是左上角，左下角，右上角，右下角，使得图像的每一部分至少
被置乱一次n1，这种算法比较繁琐，增加了算法的时间复杂度。另一种（算法2）是对前者的改进，将像素点的R、G、B三色分量排列成一维序列，对于M×N的数字图像，直接把3×M×N个图像数据排列到一维数组pl[]中，假如2n-1<3×M×N<2n，则可对pl[]补上(2n-3×MxN)个值为-1的数据，选择一条n阶Hilbert曲线进行置乱处理，再把值为-1的数据去掉，余下的就是置乱后的图像数据。该加密算法类似于对图像像素进行填充，增加了原图变换的工作量，如图4。

二、Gray变换

1、Gray码

定义1对于任意一个非负整数u，其二进制码记为纠=(uup-1up-217...u0u1)2，令：

i=1，2，…，p-1，则得到一个二进制表示的整数gu=(gpgp-1--g1go)2，变换式(l)称为Gray变换，gu称为的u的Gray码，其中运算“0”为模2加法。

2、Gray码图像置乱

（1）基于位置：对于MxN阶数字图像，按一定顺序对像素点进行编号，利用(N进制)Gray码变换置乱图像。

（2）基于色彩：保持像素点的位置不动，改变像素点的灰度(RGB)值。此时应先把像素点的R、G、B分量值用8位二进制码表示，再利用二进制Gray码变换。

如图5，置乱图1(64x64)是基于位置的变换，置乱图2是基于色彩的变换。

值得注意的是：对于基于位置的Gray变换，选取N进制和N进制的位数比较重要，如图像大小为3 x4-12，则像素点不能实现位置置乱的一一映射。而基于色彩的Gray变换，加密效果十分差，且周期很短，在实际中不具有应用性。

三、矩形分割算法

将任意一个矩形图像的长、宽（如果是长方体则是长、宽、高）通过矩形分割算法，对这两（三）个数分裂相同的次数，使长、宽（长、宽、高）分别分成2n（n=1，2…）段，即可将一个矩形（或者长方体）分成2nx2n（或者2nx2nx2n）块，将这些分裂出来的矩形块（或长方体块）作为一个单元，这些单元满足n阶二维(或三)Hilbert曲线遍历规则。

分割算法的详细步骤如下：

对任意整数m1，m2，做式(2)运算：

假定被分裂的数为l，通过一次分裂出来的两个数为l(0)l(1)，则分裂规则为：

对m1，m2同时分裂M= Min(Mm1，Mm2)次，即可将两个数分别分裂成2M等分。如图6通过两次分裂分成4x4=16小块。

四、图像加密新算法

1、二维Hilbert曲线混合Gray码空域重组矩形图像像素点

（1）图像分块

将图像的宽、高按矩形分割算法将图像分成2nx2n小块，将小块利用n阶Hilbert曲线遍历，达到对小块的置乱。由于矩形分割算法的特点，任意矩形图像分出来的块，最多只有一行块和一列块（或者只有一行块，或者只有一列块，或者没有）内的像素点的个数不是2n(n∈N)，如图6为第一列块和第三行块内的像素点的个数不为2n(n∈N)。

（2）对小块内像素点的处理

①若小块内的像素点的个数为2n(n∈N)，则可以选择n位二进制位对小块的像素点进行Gray码位置置乱，假定图像块大小为2x4，对小块内像素点进行编号(0，1，…，7)，从而用3位二进制Gray码变换重新排序像素点。

②若小块内的像素点的个数不是2n(n∈N)，比如3x3，则利用Gray色彩置乱顺序遍历小块内的像素点。

实验证明，小块内像素点的Gray码变换主要是降低像素点之间的相关性，单从视觉上来说，即使不对小块Gray变换，图像的置乱效果也是很不错的，如图7。

2、三维Hilbert曲线混合Gray码空域重组矩肜图像24位

（1）将像素点对应的R、G、B分量值转换为8位二进制数，把图像分成24个位平面，将像素点的24个位存入三维序列P3[k，i，j]中，其中i，j对应像素点的坐标，0≤k<24，如图8。

（2）将width，height，24这三个数按分割算法进行分裂，将长方体划分为2nx2nx2n个小长方体块，对应胛阶三维Hilbert曲线遍历规则。

（3）对小长方体块内二进制位数据的处理，与上节中的对小块处理类似，只不过从平面延伸到了空间，规则为：

①若小长方体块内的元素个数为2n(n∈N)，则选择Gray码位置置乱。

②若长方体块内的元素个数不是2n(n∈N)，则不做变换，因为小块内存储的元素是二进制位，如图9。

五、加密算法分析

（1）创新性

利用三维Hilbert曲线对彩色图像的24位空域置乱，通过图9可以发现，对彩色图像24位的空域置乱可以达到非常好的置乱效果，大大降低了像素之间的相关性。

（2）加密算法执行效率

算法在.net 2005环境下编译运行，机器配置为AMD 64Processor 2800+，内存1GB。对238×170图像（图4的原图）分别用4种算法变换一次所需要的时间如表1。

通过表1发现，基于二维Hilbert变换的新算法较这2种算法执行效率都要高，而基于三维的Hilbert变换则要慢很多，这与三维空间中的数据量有关，但是其置乱效果是非常好的。

（3）安全性

由图4、图5、图7、图9可以看出，基于像素点的空间位置置乱可能会给解密者留有一个信息：如果原图像是灰度图，则加密后的图像一定是灰度图。然而基于24位的空域置乱加密后则不再是灰度图，置乱图接近混沌状态，大大提高了加密的可靠性。