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

基于S盒的图像混沌置乱方法摘要数字图像置乱技术,作为数字图像信息隐藏的预处理和后处理,其主要目的是将一幅有意义的图像变成一幅杂乱无章的图像,用以增加数字图像信息隐藏算法抵抗非法攻击的能力,从而增加安全性。本文以图像信息安全问题为背景,介绍了通常用于分组密码系统中的S盒的理论基础,提出了一种基于S盒的数字图像置乱方法,同时讨论了置乱算法的周期性。实验结果表明,算法具有很好的置乱效果。关键词信息安全信息隐藏S盒数字图像置乱周期性中图法分类号:TN911.73文献标识码:ADigitalImageScramblingBasedonS-boxSUIXin-guang,LUOHui(KeyLaboratory,SouthwestInstitutionofElectron&TelecomTechniques,Chengdu610041)AbstractThemainaimofdigitalimagescrambling,whichisusedasthepre-processingorpost-processinginimageinformationhiding,istotransformameaningfulimageintoameaninglessordisorderedimageinordertoenhancethepowertoresistinvalidattackandinturnenhancethesecurity.ThispaperintroducestheacademicfoundationofS-boxthatisusuallyappliedtogroupcryptosystemwithimageinformationsecurityasitsbackground,andthenpresentsamethodofdigitalimagescramblingbasedonS-boxanddiscussestheperiodicityofthearithmetic.Thealgorithmisprovedtobeefficientwithexperiments.Keywordsinformationsecurity,informationhiding,S-box,digitalimagescrambling,periodicity1引言随着计算机技术、通信技术、信息处理技术和智能化网络技术的飞速发展和广泛应用,数字化信息可以以各种形式在网络上迅速便捷地传输。然而由于网络的开放性特点,使得任何人都可以在网络上自由地获取他感兴趣的任何东西,这就使得信息的安全性倍受关注。在网络通信中,往日因存储量大和传输占用带宽大而让人们望而却步的数字图像也由于存储技术和网络通信技术的发展而在网络通信中占有越来越多的比率。数字图像有其固有的一些特殊性质,如2维的自相似性、相关性、大数据量等。随着计算机技术的发展,人们在图像信息安全方面做了许多有益的探索,并取得了一定成果,其中之一即图像信息隐藏技术。作为信息安全领域的后起之秀,图像信息隐藏技术用于保密通信有自己的优势,因而近年来成为国内外研究的热点,特别是在图像隐藏、图像分存、数字水印等方面。数字图像置乱技术,作为数字图像信息隐藏的预处理和后处理,其主要目的是将一幅有意义的图像变成一幅杂乱无章的图像,使其所要表达的真实信息无法直观地得到。它可以增加数字图像信息隐藏算法抵抗非法攻击的能力,以增加安全性。在数字图像置乱方面,已有许多比较有效的方法,如基于Arnold变换、幻方、Hilbert曲线、Conway游戏、Tangram算法、IFS模型、Gray码变换、仿射模变换、多相滤波等方法[1~9]。本文从分组密码中S盒的高度非线性性和扩散性出发,提出了一种基于S盒新数字图像置乱方法,并通过实验验证了算法的有效性。2S盒S盒是分组密码中的一个计算部件,是一个高度非线性的输入/输出真值表,其作用是使得明文和密钥产生充分的混淆和扩散。S盒的设计思想是这样的:将非线性度高、混淆和扩散性能好的密码函数作为分组密码的运算部件。考虑到这些密码函数的运算量很大,将其在各种自变量下的函数值预先计算好并做成输入/输出真值表,在实际应用时只需要根据输入值来调用表中相应的函数值即可。例如,在DES(dataencryptionstandard)加密算法中,可以用到多达8个S盒(表1所示为其中的S1)。表1S盒(S1)012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613每个S盒都是4行和16列,6比特输入,4比特输出。由输入的首尾两比特确定S盒中的行,由输入的中间4比特确定S盒的列,其对应行和列处的值(4比特表示)即为输出值。实际上,每个S盒的每一行都是整数0~15的一个置换(即可逆变换)。在DES的加密算法中,S盒具有差分扩散功能,因而能抗差分攻击,同时由于它又是高度非线性的,每一个S盒的输出都不是它的输入的线性或仿射函数,因而能抵抗线性攻击。3S盒在数字图像置乱中的应用数字图像置乱的目的是在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-1k=0h1(k)-h2(k)∑G-1k=0h1(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!=20922789888000种可能性,由于本算法使用了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,15a1,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-1a1,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