混沌映射的水印算法设计与实现

摘要：为了保证水印的安全性，嵌入图像先生成实数值混沌序列，然后把实数值混沌序列转化为二进制序列，而利用该序列作为判断条件间接加密图像。加密水印的嵌入是按各个小波子块行扫描的顺序进行的，这加强了水印系统被破解的难度，也加强了水印的安全性和鲁棒性。

关键词：混沌；图像加密；水印嵌入；迭代算法

中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)21-30531-02

1 引言

到目前为止，还没有一个统一的、有足够数学定理支持的、普遍适用和完美的混沌理论，科学家们只能通过混沌系统所表现出的一些普遍现象总结归纳出其所谓的本质。哈肯[1]：“混沌性为来源于决定性方程的无规运动”；费根包姆：“确定系统的内在随机运动”；钱学森：“混沌是宏观无序、微观有序的现象”。综上所述，可以做出如下的理解：混沌是指确定的宏观的非线性系统在一定条件下所呈现的不确定的或不可预测的随机现象；是确定性与不确定性或规则性与非规则性或有序性与无序性融为一体的现象；其不可确定性或无序随机性不是来源于外部干扰，而是来源于内部的“非线叉耦合作用机制”。只有经过长期演化，结果才是不确定的，不可预知的。

混沌是确定论系统的随机行为的总称[2]，它的根源在于非线性的相互作用。混沌不是混乱，它不同于平衡态，是一种序，是貌似无序的序。自然界中最常见的运动形态，往往既不是完全确定的，也不是完全随机的，而是介于两者之间，这就是研究确定论系统中随机行为的重要意义所在。

2 混沌序列产生

在传统的迭代乘积密码系统[3]中，排列算法的主要任务就是对明文数据块中的元素进行重排（也称为“置乱”），使得密文块看起来是随机的。不过，这些排列算法通常是事先确定好的，而与密钥无关。这是一个明显的缺陷，使得某些迭代乘积密码系统特别容易受到差分密码分析的攻击，而基于密钥排列的安全性能会有较大改善。在基于密钥的排列算法中，以密钥作为排列的参数，参数能够唯一地确定排列的性质。

基于密钥的排列可以在频域或空间域进行。排列变换[4]可以是局部的，或是全局的。空间域的排列加密算法实现较为简单，因为不需要使用一般频域算法所必须的空域到频域的变换。算法是先生成实数值混沌序列，然后把实数值混沌序列转化为二进制序列，而利用该序列作为判断条件间接加密图像。利用混沌序列生成方式形成新的混沌映射，生成新的整数混沌序列。该序列仍然具有混沌特性，然后用生成的混沌序列直接加密图像，易实现、计算花费少，加密后图像可以完全正确的还原成原始图像。

2.1 混沌映射

利用函数映射，提出一个具有良好随机统计特性的一维非线性映射，由它生成的混沌序列为某一区域上的整数值混沌序列，具有随机性，并且对初值极其敏感。可定义如下：

xk+1=fa(xk)

混沌映射式(1)经过n次迭代后形成新混沌映射式(2)，同样具有上述混沌映射式(1)的混沌特性：

当给定初始值x0，参数a、m的值和迭代次数n的值就确定了，生成混沌序列为：{xk；k=0,1,2,3,L}。

该序列具有混沌特性，对初值条件X0极为敏感。a与n也作为初始条件，即把有序数组(x0,a,n)一起作为密钥，则攻击混沌系统式(2)成功的概率比只把x0作为密钥时攻击成功的概率更小。

下面的例子是混沌映射式(2)生成混沌序列的具体过程。

例如：要产生[1，371]之间的一个整数混沌序列，取参数m=371,a=205，表1为混沌序列产生过程。表的第一行为迭代次数n，第一列为xk，表中为对应某一xk，n的xk+1。

1) 加密算法设计

step 1 输入M，N，原始图像IR=(i,j,g(i,j))。

step 2 输入一维混沌映射式(2)的初始值x0，设置参数a，m的值和迭代次数n的值，用混沌映射(2)生成混沌序列：

x0,x1,x2,L,xm+n-1

step 3

for i=0 to m-1

Xi=xi mod n

for j=0 to n-1

if j+xi≥n

(i,j,g(i,j))(i,j+xi,g(i,j))

end

end

利用第二步生成的混沌序列将图像的每行像素右移(循环移动)变换到该行的另一位置，像素的灰度值不变。

step 4

for j-0 ton-1

Yj=xM+j mod m

if i+Yj≥m

(i,j,g(i,j)) (i+Yj-M,j,g(i,j))

else (i,j,g(i,j)) (i+Yj,j,g(i,j))

end

end

这一步利用第2步生成的混沌序列将图像的每列像素下移(循环移动)变换到该列的另一位置，像素的灰度值不变。

step 5 得到加密图像的各个像素的新的灰度值g'(i,j)，生成加密图像IE=(i,j,g'(i,j))。

step 6 终止算法。

2) 解密算法设计

step 1 输入 M，N以及加密图像IE。

step 2 这一步与加密过程第二步正好一样，输入一维混沌映射式的初始值x0，设置参数a、m的值和迭代次数n的值，用混沌映射式生成混沌序列：x0,x1,x2,L,xm+n-1。

step 3

For j = 0 to N-1

Yj = xM+j mod M

For i =0 to M-1

if iCYj ≤ M

(i,j,g(i,j))(i-Yj+M,j,g(i,j))

else (i,j,g(i,j))(I-Yj,j,g(i,j))

end

end

这一步是加密过程的第4步的逆过程，利用第2步生成的混沌序列将图像的每列像素上移(循环移动)变换到该列的另一位置，像素的灰度值不变。

step 4

For i = 0 to M-1

Xj = xM+j mod N

For j =0 to N-1

If jCXi ≤ N

(i,j,g(i,j))(i,j-Xi+N,g(i,j))

else (i,j,g(i,j)) (i,j-Xi,g(i,j))

end

end

这一步是加密过程的第三步的逆过程，利用第二步生成的混沌序列将图像的每行像素左移(循环移动)变换到该行的另一位置，像素的灰度值不变。

step 5 得到解密图像的各个像素的新的灰度值g''(i,j)=g(i,j),生成解密加密图像ID = (i,j,g''(i,j))=IR还原图像。

Step 6 终止算法。

3) 加密、解密结构图，如图1。

其中，对于加密解密过程的混沌系统是完全一样的。混沌系统式的初始值x0，参数a,m的值和迭代次数n的值对于加密解密处理过程完全一样，从而保证加密前的图像和解密后的图像完全一致，即完全还原。

3 算法分析

1) 破解变得复杂

初始值x0的选取有m个不同的值。如图像为256色，则m=256。参数a的选取也有m个不同的值。那么破解复杂度是单初始值、单参数混沌系统的m2倍。如果把混沌映射式迭代次系统式复杂度，数n也作为密钥，则破解系统的复杂度变得更高，这里可以适当选取迭代次数n的值。把数组(x0,a,n)一起作为密钥，就是为了加大破解难度。

2) 提高了算法的随机性，增强了鲁棒性

对于图像的每个像素，由混沌系统式(2)生成的混沌序列随机特性，通过变换可能在图像的任何位置，加密结果可能有（M*N）!。结果,如果采用穷举法攻击需要计算（M*N）! 次，其破解成功的概率几乎为0。例如：一张原始图像， IR大小为M*N个像素，M =256，N = 256，采用穷举法攻击需要计算（256*256）! 次，这几乎不可能攻击成功。

4 结论

本文采用嵌入图像先生成实数值混沌序列，然后把实数值混沌序列转化为二进制序列，而利用该序列作为判断条件间接加密图像。加密水印的嵌入是按各个小波子块行扫描的顺序进行的，这加强了水印系统被破解的难度，也加强了水印的安全性和鲁棒性。

参考文献：

[1] I J Cox, J Kilian, T Leighton, et al.Secure spread spectrum watermarking for mulitimedia[R].NEC Research Institute Technical Report.1995.

[2] Miller M L, Cox I J, dBloom J A. Informed embedding: Exploiting image and detector information during watermark insertion[C].IEEE International Conference on Image Processing, 2000.

[3] 黄继武,姚若河.基于块分类的自适应图象水印算法[J].中国图象图形学报,1999(4).

[4] 易开祥,石教英.一种自适应二维数字水印算法[C].北京:全国第二届信息隐学术研讨会论文集,2000:108-112.

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”