基于S盒的图像混沌置乱方法.doc

基于S盒的图像混沌置乱方法
摘 要 数字图像置乱技术,作为数字图像信息隐藏的预处理和后处理,其主要目的是将一幅有意义的图像变成一幅杂乱无章的图像,用以增加数字图像信息隐藏算法抵抗非法攻击的能力,从而增加安全性。本文以图像信息安全问题为背景,介绍了通常用于分组密码系统中的S盒的理论基础,提出了一种基于S盒的数字图像置乱方法,同时讨论了置乱算法的周期性。实验结果表明,算法具有很好的置乱效果。
关键词 信息安全 信息隐藏 S盒 数字图像置乱 周期性
中图法分类号: TN911.73 文献标识码: A Digital Image Scrambling Based on S-box
SUI Xin-guang, LUO Hui
(Key Laboratory,Southwest Institution of Electron&Telecom Techniques,Chengdu610041)
Abstract The main aim of digital image scrambling, which is used as the pre-processing or post-processing in
image information hiding, is to transform a meaningful image into a meaningless or disordered image in order to
enhance the power to resist invalid attack and in turn enhance the security. This paper introduces the academic
foundation of S-box that is usually applied to group cryptosystem with image information security as its
background, and then presents a method of digital image scrambling based on S-box and discusses the periodicity of
the arithmetic. The algorithm is proved to be efficient with experiments.
Keywords information security, information hiding, S-box, digital image scrambling, periodicity
1 引 言
随着计算机技术、通信技术、信息处理技术和智能化网络技术的飞速发展和广泛应用,数字化信息可以以各种形式在网络上迅速便捷地传输。然而由于网络的开放性特点,使得任何人都可以在网络上自由地获取他感兴趣的任何东西,这就使得信息的安全性倍受关注。在网络通信中,往日因存储量大和传输占用带宽大而让人们望而却步的数字图像也由于存储技术和网络通信技术的发展而在网络通信中占有越来越多的比率。数字图像有其固有的一些特殊性质,如2维的自相似性、相关性、大数据量等。随着计算机技术的发展,人们在图像信息安全方面做了许多有益的探索,并取得了一定成果,其中之一即图像信息隐藏技术。
作为信息安全领域的后起之秀,图像信息隐藏技术用于保密通信有自己的优势,因而近年来成为国内外研究的热点,特别是在图像隐藏、图像分存、数字水印等方面。数字图像置乱技术,作为数字图像信息隐藏的预处理和后处理,其主要目的是将一幅有意义的图像变成一幅杂乱无章的图像,使其所要表达的真实信息无法直观地得到。它可以增加数字图像信息隐藏算法
抵抗非法攻击的能力,以增加安全性。在数字图像置乱方面,已有许多比较有效的方法,如基于Arnold变换、幻方、Hilbert曲线、Conway游戏、Tangram算法、IFS模型、Gray码变
换、仿射模变换、多相滤波等方法[1~9]。本文从分组密码中S盒的高度非线性性和扩散性出发,提出了一种基于S盒新数字图像置乱方法,并通过实验验证了算法的有效性。
2 S盒
S盒是分组密码中的一个计算部件,是一个高度非线性的输入/输出真值表,其作用是使得明文和密钥产生充分的混淆和扩散。S盒的设计思想是这样的:将非线性度高、混淆和扩散性能好的密码函数作为分组密码的运算部件。考虑到这些密码函数的运算量很大,将其在各种
自变量下的函数值预先计算好并做成输入/输出真值表,在实际应用时只需要根据输入值来调用表中相应的函数值即可。例如,在DES(data encryption standard)加密算法中,可以用到多达8个S盒(表1所示为其中的S1)。
表1 S盒(S1)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
每个S盒都是4行和16列,6比特输入,4比特输出。由输入的首尾两比特确定S盒中的行,由输入的中间4比特确定S盒的列,其对应行和列处的值(4比特表示)即为输出值。实际上,每个S盒的每一行都是整数0~15的一个置换(即可逆变换)。在DES的加密算法中,S盒具有差分扩散功能,因而能抗差分攻击,同时由于它又是高度非线性的,每一个S盒的输出都不是它的输入的线性或仿射函数,因而能抵抗线性攻击。
3 S盒在数字图像置乱中的应用
数字图像置乱的目的是在2维的层次上,对数字图像的色彩、位置或者频率进行扰乱,使之成为一幅杂乱无章的图像,即使被非法攻击者截获,不知道恢复方法也无可奈何。此外,由于数字图像的大数据量以及庞大的明文空间,想要利用统计分析的方法将消耗巨大的工作量,在实现上是极其困难或者是得不偿失的。数字图像置乱有基于位置空间、色彩空间和频率空间的置乱变换,即改变像素的位置或色彩而置乱图像。但是要从置乱的图像恢复出原图像,必须保
证原始图像与变换图像之间的变换是可逆的或者是周期性的(即通过若干次变换就可以回复到初始状态)。而每个S盒的每一行都是整数0~15的一个置换,因而其变换是可逆的。
3.1 基于位置的置乱
由于S盒的每一行都是0~15(共16个数)的一个置换,8个S盒共有32个置换。把图像的每16行(列)分为一小组(利用一个置换来进行位置置乱),每32个小组构成一个大组,利用S盒的32个置换来对图像的一个大组(32个小组)进行行(列)置换,从而可以得到位置置乱的图像。图1是一个位置置乱的实例。

图1 位置置乱实例
图1(b)是经过行和列置乱的图像,从图中可以看出,尽管图像已经变得比较乱,但是还可以看出图像的轮廓。这是由于S盒的每一行都是0~15的置换,从而图像的行(列)置乱都是在16×16的块内进行的,只是在这个区域内打乱了图像像素的位置,而块与块之间的位置关系并没有被打乱。而图1(c)是在行和列置乱的基础上又进行了区域置乱,打破了块与块之间的位置关系,从而达到了比较理想的置乱效果。
3.2 基于灰度的置乱
由于S盒的每一行都是0~15的一个置换,而0~15可以用二进制的4个比特表示,从而每一个
置换都可以看作4比特串到4比特串之间的一个置换。利用这种关系,可以对图像进行灰度置乱。由于灰度图像的每个像素用8个比特表示,可以对其高4位和低4位分别进行置换,从而达到置乱的效果。
具体作法是:把图像每16个像素分为一组,利用S盒的32个置换对这16个像素(16字节,共32个41224中国图象图形学报第9卷位比特串)分别进行置换。图2是一个变换实例。

图2 灰度置乱实例
3.3 基于位置和灰度的置乱
既对图像进行位置置乱(打乱行、列及区域的位置关系),又对图像进行灰度置乱(改变灰度值)。图3是一个变换实例。

图3 位置加灰度置乱实例
4 置乱算法的性能分析
4.1 算法的复杂性分析
由于算法采用S盒置乱,直接调用真值表,而没有涉及函数的具体计算,整个算法中只有少量的加法运算和逻辑运算。例如,在灰度置乱中,对每个像素,只涉及两次“移位”运算,一次“与”运算,调用两次真值表,一次“加”运算。对于一幅M×N的图像,总共需要M×N次“加”运算,M×N次“与”运算,2×M×N次“移位”运算,2×M×N次调用真值表。因而算法复杂性很低,计算速度非常快,置乱以及解置乱方便快捷。
4.2 置乱的效果分析
一幅图像的概貌可以通过其灰度直方图来描述。例如,如果一幅图像的灰度直方图比较展开,那么它看起来就比较清晰柔和;如果直方图对比度小,则看
起来不自然;如果直方图的动态范围较小,则看起来不清楚。因而可以通过直方图来分析置乱的效果。对于一幅类似白噪声的图像,其直方图充满整个区域,而且分布应该比较均匀。同时,对于类似白噪声的图像,任意截取其中的某个小区域,其直方图分布应该与整个图像的直方图分布相似,也就是直方图的分布具有自相似性。

图4 置乱直方图比较
图4就是对置乱前后图像的直方图的一个比较(由于位置置乱不改变图像的直方图,这里只对灰度置乱的直方图进行比较)。其中,图4(a)为图2(a)图像的直方图,图4(b)为经过灰度置乱后,即图2(b)的直方图,图4(c)是从图2(b)中任意截取的一块小区域,图4(d)是截取出来的小块图像的直方图。从图中可以看出,经过置乱后图像的直方图充满整个区域,而且分布比较均匀。用直方图的相似度来定量地描述置乱的效果。

设两图像灰度直方图分别为h1(k),h2(k),k=
0,1.…,G-1则定义直方图的相似度为
α= 1 -
∑
G-1
k=0
h1(k) -h2(k)
∑
G-1
k=0
h1(k) +h2(k)
(1)对于一幅纯噪声的图像,其直方图分布应该是均匀的,即h(i)=h(j), i,j∈{0,1,…,G-1}。这里原始图像与白噪声图像的直方图相似度α=0.19,置乱后的图像与白噪声图像的直方图相似度α=0.81,截取小图像与白噪声图像的直方图相似度α=0.69,而截取部分与整幅置乱图像的直方图相似1225第10期眭新光等:基于S盒的数字图像置乱技术度α=0.85。这说明经过置乱后图像类似于白噪声,置乱效果良好。
4.2 置乱的安全性分析
一个0~15的置换有16! =20 922 789 888 000种可能性,由于本算法使用了8个S盒共32个0~15的置换,因而32个置换共有(16!)32=1.8×10426种可能性。对于非法攻击者来说,即使知道了置乱的方法,但要从1.8×10426种可能的置换中分析出算法所采用的置换,其运算量是非常巨大的。如果采用穷搜索的方法,平均需要搜索约10426种置换,这在实现上也是很困难的。另外,从密码学的角度来讲,每个0~15的置换都是有限域GF(24)到GF(24)的一个置换,32个置换相当于一个GF(2128)到GF(2128)的置换。因此,本方法相当于一套分组很大(16个字节共128比特)的分组密码,使信源明文的统计特性被隐蔽得很深,以至于对其统计分析是极其困难的。因此,置乱后的图像是安全的。

5 基于S盒变换的周期性
S盒的每一个置换都是0~15的置换,用矩阵可以表示成
(y0,y1,…,y15) = (x0,x1,…,x15)A(2)
其中,xi,yi∈{0,1,…,15}(i=0,1,…,15),xi≠xj,
yi≠yj(i≠j),而A=
a0,0a0,1…a0,15
a1,0a1,1…a1,15
… …
a15,0a15,1…a15,15,矩阵A的每一行(列)都只有一个元素等于1,而其余元素等于0,它可以由单位矩阵经过有限次交换行和交换列得到,因而存在逆矩阵,从而变换是可逆的。对于变换的周期性,有以下定理。
定理1 对于给定的N和矩阵A,变换
(y0,y1…,yn-1)=(x0,x1,…,xn-1)A(modN) (3)
其中,A=
a0,0a0,1…a0,N-1
a1,0a1,1…a1,N-1
… …
aN-1,0aN-1,1…aN-1,N-1,ai,j为整数,y0,y1,…,yn-1,x0,x1,…,xn-1∈{0,1,…,N-1}
有周期性的充分条件是 A 与N互素,此处 A 是A的行列式值[6]。
应用于S盒的置换有N=16,而 A =±1(交换行和列的位置不改变行列式的代数值,而只改变
其符号),因而 A 与N互素,变换存在周期性。对于置乱周期的具体求法,可以通过求得每一
个置换的周期,然后对32个置换的周期取最小公倍数,就可以得到这里置乱的周期。从实验的角度得到的每个置换的周期如下:
{14,33,36,33,14,36,12,12,16,14,44,12,14,10,
42,14,14,12,36,14,14,55,36,14,44,30,36,30,
26,44,44,14}。
从而可以得到置乱的周期为720 720。
6 结 论
数字图像置乱是近年来新兴起来的研究课题,人们在这一方面已做过许多有益的探索,取得了不少成果。但是,寻找一种安全而又简单的置乱方法,一直是数字图像置乱研究的内容。本方法与基于Gray码变换的置乱方法有相似之处。但是,从密码学的角度来讲,基于Gray码变换的置乱由于是GF(24)到GF(24)的一个置换,其分组太小,很难抵抗对明文的统计分析,而本方法的分组很大(16个字节共128比特),使信源明文的统计特性隐蔽得很深,以至于对其统计分析是极其困难的。从上述实验结果和性能分析的结果来看,基于S盒的置乱效果较好,实现方便。用作数字图像信息隐藏的预处理或后处理是非常有效的。
参考文献
1 邹建成,铁小匀.数字图像的二维Arnold变换及其周期性[J].
北方工业大学学报,2000,12(1):10~14.
2 Ding Wei, Yan Wei-qi, Qi Dong-xu. Digital image scrambling
technology based on gray code [ A ]. In: Proceedings of
International Conference on CAD/CG [C], Shanghai, P. R.
China, 1999.
3 李国富,邹建成,齐东旭.广义Gray码及其在数字图像置乱中的
应用[A].见:全国第二届信息隐藏学术研讨会论文集[C],北
京,2000:1~6.
4 Qi Dong-xu, Ding Wei, Li Hua-shan. Tangram algorithm:
image transformation for storing and transmitting visual secrets
[A]. In: Proceedings of the 9' st International Conference of
CAD/CG[C], Shenzhen, P.R.China, 1997,(1):135~139.
5 李国富.正交拉丁变换的周期性及其在数字图像置乱中的应用
[A].见:全国第三届信息隐藏学术研讨会论文集[C],西安:西
安电子科技大学出版社,2001:1~7.
1226中国图象图形学报第9卷6 齐东旭,邹建成,韩效宥.一类新的置乱变换及其在图像信息隐
蔽中的应用[J].中国科学(英文版),2000,30(5):440~448.
7 Creusere C D, Mitra S K. Efficient image scrambling using
polyphase filter banks [A]. In: Proceedings of International
Conference On Image Processing[C], Austin, Texas, USA,
1994:81~85.
8 Joo K S, Bose T. Image scrambling using 2-D periodically shift
variant filters[J]. Midwest Symposium on Circuits and Systems,
1995,1(8):478~481.
9 BAI Sen, CAO Chang-Xiu. A novel algorithm for scrambling
the details of digital image[A]. In: Proceedings of the World
Congress on Intelligent Control and Automation (WCICA),
Shanghai, P.R.China, 2002,2:1333~1336.