基于正交拉丁方的混沌图像加密算法设计
Design of Chaotic Image Encryption Algorithm Based on Orthogonal Latin Square

作者: 林泽森 , 田传俊 :深圳大学电子与信息工程学院,广东 深圳;

关键词: 流密码算法图像加密正交拉丁方基本密码系统混沌系统Stream Cipher Algorithm Image Encryption Orthogonal Latin Square Basic Cryptosystem Chaotic System

摘要:
本文构造了一个8阶正交拉丁方组及其所决定的可逆变换的代数式,给出了基于该正交拉丁方组的基本密码系统的设计方法。在此基础上,结合Henon混沌系统设计了一种多元流密码算法,推广了二元加法流密码的设计方法,并对新流密码算法在数字图像上的加密效果进行了直方图、相关性、密钥敏感度及信息熵等分析,结果表明该加密算法具有良好的加密效果。

Abstract: This paper constructs an 8th-order orthogonal Latin square group and the algebraic formula of the reversible transformation determined by it, and gives the design method of the basic cryptographic system based on the orthogonal Latin square group. On this basis, a multiary stream cipher algorithm is designed in combination with the Henon chaotic system, the design method of  binary additive stream cipher is promoted, and the encryption effect of the new stream cipher algorithm on digital images is carried out by histogram, correlation, etc. Simulations show that the encryption algorithm has a good encryption effect.

1. 引言

流密码算法作为一类重要的密码体制是当前密码学的热门研究问题之一,也是信息安全领域的基础内容之一,在数字信息加密领域得到广泛应用 [1] [2] [3]。自1949年Shannon提出完善保密系统模型以来 [2],已有不少学者对其相关的理论模型和实际应用进行了研究 [3] [4]。当前,普遍认为完善保密系统模型是流密码算法的理论基础,其中,常见的二元流密码算法是基于模2加法运算来进行设计的,它所使用的基本运算过于简单,这会影响整个算法的加密效果和安全性。最近的文献 [3] 推广了现有的完善保密系统模型,将流密码系统设计分为基本密码系统设计和应用密码系统设计,其中的一个关键是将常见的二元加法密码系统中的模2加法基本系统推广为一般的拉丁方基本系统。这样,与以前的基本系统设计相比,该模型最大的特点在于所能设计的基本系统的种类更加丰富、设计技巧更加灵活,并且能够有效地提高算法的复杂度。当前,已有文献 [4] 专门研究了4阶正交拉丁方组基本系统的设计方法,但尚未有文献对利用更高阶的正交拉丁方组设计基本密码系统的方法进行讨论。因此,本文将研究利用8阶正交拉丁方组设计基本密码系统的方法,并结合Henon混沌系统研究一种新的混沌流密码系统的设计与实现问题。

1997年,Fridrich首次将混沌系统应用到数字图像加密中 [5]。此后,因混沌系统具有初值敏感性和类随机性等特点,故在信息加密领域中得到广泛应用。由于一维混沌系统具有初始可控参数少,生成的序列随机性较差等缺点,因此,现在常用更高维的混沌系统来设计安全性更高的密码算法 [6]。本文将先利用8阶正交拉丁方组设计一个基本系统,之后再结合二维Henon混沌系统所设计的密钥序列空间来完成整个流密码算法的设计。

2. Henon系统

考虑到混沌系统所具有的初值敏感性和伪随机性等特点,本文将具体利用Henon混沌系统进行密钥序列空间的设计,简要介绍如下。

Henon映射是一类二维非线性混沌系统,其映射方程 [7] 如下:

{ x n + 1 = 1 a x n 2 + y n y n + 1 = b x n (1)

其中, a , b 为控制参数,取 a = 1.4 , b = 0.3 , x 0 , y 0 ( 0 , 1 ) 时,整个系统处于混沌状态 [7]。为方便实际应用,还需用对混沌解序列进行某种变换,如取模运算等。

3. 基于正交拉丁方的流密码算法设计

3.1. 基本密码系统设计

在基本密码系统设计时需要利用拉丁方,介绍如下。

定义3.1若存在 n ( n 2 ) 阶方阵A,使得 Z n = { 0 , 1 , , n 1 } 上每个元素在A的每一行和每一列里仅出现一次,则称方阵A为n阶拉丁方。设 A = ( a i j ) n × n B = ( b i j ) n × n 都是n阶拉丁方,若 ( A , B ) 的n2个元素组成的集合等于 { ( i , j ) | i , j = 0 , 1 , , n 1 } ,则称A和B正交。特别地,当 k ( k 2 ) 个拉丁方 A 1 , A 2 , , A k 两两正交时,则称 A 1 , A 2 , , A k 为正交拉丁方组。

文献 [4] 对4阶正交拉丁方组所设计的基本密码系统进行了研究。本文将利用如下更高的8阶正交拉丁方组来设计基本密码系统:

L 1 = [ 7 0 1 2 3 4 5 6 6 1 0 3 2 5 4 7 5 2 3 0 1 6 7 4 4 3 2 1 0 7 6 5 3 4 5 6 7 0 1 2 2 5 4 7 6 1 0 3 1 6 7 4 5 2 3 0 0 7 6 5 4 3 2 1 ] = [ T 0 T 1 T 2 T 3 T 4 T 5 T 6 T 7 ] , L 2 = [ 7 0 1 2 3 4 5 6 3 4 5 6 7 0 1 2 6 1 0 3 2 5 4 7 2 5 4 7 6 1 0 3 1 6 7 4 5 2 3 0 5 2 3 0 1 6 7 4 0 7 6 5 4 3 2 1 4 3 2 1 0 7 6 5 ] = [ T 8 T 9 T 10 T 11 T 12 T 13 T 14 T 15 ] (2)

其中, L 1 , L 2 中的每一行可看成 M = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } 的一个可逆变换,比如 T 1 : Z 8 Z 8 表示如下可逆变换:

T 1 ( 0 ) = 6 , T 1 ( 1 ) = 1 , T 1 ( 2 ) = 0 , T 1 ( 3 ) = 3 , T 1 ( 4 ) = 2 , T 1 ( 5 ) = 5 , T 1 ( 6 ) = 4 , T 1 ( 7 ) = 7.

这样,利用上述两个8阶正交拉丁方可设计出理论基本密码系统 ( M , C , T ) ,其中

M = C = Z 8 = Z 2 3 , T = { T 0 , T 1 , T 2 , , T 15 } .

下面再考虑与 ( M , C , T ) 相应的实际基本密码系统 ( M , C , K , E , D ) 的设计问题。将 Z 8 Z 2 3 相互对应的十进制整数和3比特向量不加区别。对任意的 m = m 1 m 2 m 3 Z 8 c = c 1 c 2 c 3 Z 8

T 0 ( m ) = ( m + 7 ) mod 8

T 1 ( m ) = [ ( 3 × m 2 m 3 + 1 ) mod 4 + 4 × m 1 + 1 + 4 × m ¯ 3 ] mod 8

T 2 ( m ) = [ ( m 2 m 3 + 2 ) mod 4 + 4 × m 1 + 3 + 4 × m 3 ] mod 8

T 3 ( m ) = [ ( 3 × m 2 m 3 + 3 ) mod 4 + 4 × m 1 + 1 ] mod 8

T 4 ( m ) = ( m 2 m 3 + 4 × m ¯ 1 + 7 ) mod 8

T 5 ( m ) = [ ( 3 × m 2 m 3 + 1 ) mod 4 + 4 × m ¯ 1 + 1 + 4 × m ¯ 3 ] mod 8

T 6 ( m ) = [ ( m 2 m 3 + 2 ) mod 4 + 4 × m ¯ 1 + 3 + 4 × m 3 ] mod 8

T 7 ( m ) = [ ( 3 × m 2 m 3 + 3 ) mod 4 + 4 × m ¯ 1 + 1 ] mod 8

对应的逆变换的代数式如下:

T 0 1 ( c ) = ( c + 1 ) mod 8

T 1 ( c ) = ( 3 × c 2 c 3 + 1 ) mod 4 + 4 × c 1 , T 1 1 ( c ) = T 1 [ ( c + 3 + 4 × c 3 ) mod 8 ]

T 2 ( c ) = ( c 2 c 3 + 2 ) mod 4 + 4 × c 1 , T 2 1 ( c ) = T 2 [ ( c + 1 + 4 × c 3 ) mod 8 ]

T 3 ( c ) = ( 3 × c 2 c 3 + 3 ) mod 4 + 4 × c 1 , T 3 1 ( c ) = T 3 [ ( c + 7 ) mod 8 ]

T 4 ( c ) = ( c 2 c 3 + 4 × c ¯ 1 ) , T 4 1 ( c ) = T 4 [ ( c + 1 ) mod 8 ]

T 5 ( c ) = ( 3 × c 2 c 3 + 1 ) mod 4 + 4 × c ¯ 1 , T 5 1 ( c ) = T 5 [ ( c + 3 + 4 × c 3 ) mod 8 ]

T 6 ( c ) = ( c 2 c 3 + 2 ) mod 4 + 4 × c ¯ 1 , T 6 1 ( c ) = T 6 [ ( c + 1 + 4 × c 3 ) mod 8 ]

T 7 ( c ) = ( 3 × c 2 c 3 + 3 ) mod 4 + 4 × c ¯ 1 , T 7 1 ( c ) = T 7 [ ( c + 7 ) mod 8 ]

其中, m 1 Z 2 , m 2 m 3 Z 4 , m ¯ 1 = 1 m 1 ,×表示实数乘法,类似地可将 T 8 , T 9 , , T 15 的变换式及其逆变换式全部写出。因此,式(2)中2个拉丁方的每一行所决定的变换及其逆变换都可以用代数式来表示。这样,可将实际基本密钥空间设计为 k = k 1 k 2 k 3 k 4 Z 16 ,并将加解密变换设计如下:

a) 基本加密变换E:对任意3比特明文 m = m 1 m 2 m 3 Z 8 和4比特密钥 k = k 1 k 2 k 3 k 4 Z 16 ,其中 m 1 , m 2 , m 3 , k 1 , k 2 , k 3 , k 4 Z 2 ,可利用如下统一代数式将加密变换 c = E ( m , k ) 设计为:

c = k ˜ 0 × T 0 ( m ) + k ˜ 1 × T 1 ( m ) + k ˜ 2 × T 2 ( m ) + k ˜ 3 × T 3 ( m ) + k ˜ 4 × T 4 ( m ) + k ˜ 5 × T 5 ( m ) + k ˜ 6 × T 6 ( m ) + k ˜ 7 × T 7 ( m ) + k ˜ 8 × T 8 ( m ) + k ˜ 9 × T 9 ( m ) + k ˜ 10 × T 10 ( m ) + k ˜ 11 × T 11 ( m ) + k ˜ 12 × T 12 ( m ) + k ˜ 13 × T 13 ( m ) + k ˜ 14 × T 14 ( m ) + k ˜ 15 × T 15 ( m )

其中, k ˜ 0 = k ¯ 1 k ¯ 2 k ¯ 3 k ¯ 4 k ˜ 1 = k ¯ 1 k ¯ 2 k ¯ 3 k 4 k ˜ 2 = k ¯ 1 k ¯ 2 k 3 k ¯ 4 k ˜ 3 = k ¯ 1 k ¯ 2 k 3 k 4 k ˜ 4 = k ¯ 1 k 2 k ¯ 3 k ¯ 4 k ˜ 5 = k ¯ 1 k 2 k ¯ 3 k 4 k ˜ 6 = k ¯ 1 k 2 k 3 k ¯ 4 k ˜ 7 = k ¯ 1 k 2 k 3 k 4 k ˜ 8 = k 1 k ¯ 2 k ¯ 3 k ¯ 4

k ˜ 9 = k 1 k ¯ 2 k ¯ 3 k 4 k ˜ 10 = k 1 k ¯ 2 k 3 k ¯ 4 k ˜ 11 = k 1 k ¯ 2 k 3 k 4 k ˜ 12 = k 1 k 2 k ¯ 3 k ¯ 4 k ˜ 13 = k 1 k 2 k ¯ 3 k 4 k ˜ 14 = k 1 k 2 k 3 k ¯ 4 k ˜ 15 = k 1 k 2 k 3 k 4

b) 基本解密变换D:对任意3比特密文 c = c 1 c 2 c 3 Z 8 和4比特密钥 k = k 1 k 2 k 3 k 4 Z 16 ,其中

c 1 , c 2 , c 3 , k 1 , k 2 , k 3 , k 4 Z 2 ,可利用如下统一代数式将解密变换 m = D ( c , k ) 设计为: m = i = 0 15 k ˜ i × T i 1 ( c )

3.2. 算法设计

参照文献 [3],可将流密码系统设计分为基本密码系统和应用密码系统设计。其中,应用密码系统设计的关键在于密钥序列空间的设计。下面就综合利用上述基本密码系统和Henon混沌系统来设计整个流密码算法,其设计步骤如下:

a) 选取大小为 M × N 的灰度图像P,并将其表示成数字矩阵 I = ( m i j ) M × N ,其中 m i j Z 256 , i { 0 , 1 , , M 1 } , j { 0 , 1 , , N 1 }

b) 将矩阵I中每个像素值读取的8比特序列 m = m ˜ 1 m ˜ 2 m ˜ 3 转换为2元序列,其中, m ˜ 1 = m 1 m 2 m 3 m 8 等。同时,对每个8比特进行逐3比特的分组,转换为8元序列,其中, m ¯ 1 = m 1 m 2 m 3 Z 8 , m ¯ 2 = m 4 m 5 m 6 Z 8 ,剩余2比特 m 7 m 8 不参与分组和加密,等等;

c) 选定初始参数 x 0 = 0.000001 , y 0 = 0.000001 , a = 1.4 , b = 0.3 代入Henon混沌系统,迭代产生混沌序列并对1进行取模运算,然后通过取整变换为2元序列,再将2元序列变换为16元密钥流序列 z = k ˜ 1 k ˜ 2 ,其中, k ˜ 1 = k 1 k 2 k 3 k 4 ,等等;

d) 加密变换:依次对步骤(b)处理后所得到的8元序列进行加密。先对明文序列m中每个8比特 m ˜ j 中的分组如 m ¯ 1 m ¯ 2 进行加密 c ¯ i = E ( m ¯ i , k ˜ j ) , i = 1 , 2 ; j = 1 , 2 , ,可得到加密后的分组序列 c ¯ 1 c ¯ 2 ,转换成6比特后拼接上未作加密的2比特 m 7 m 8 ,从而得到8比特的密文分组 c ˜ j ,对矩阵I中的所有像素值加密完成后即可得到密文图像c

e) 解密变换:依次对经过步骤(d)加密处理的每个密文序列c进行解密。同样只对8比特密文分组 c ˜ j 决定的3比特序列 c ¯ 1 c ¯ 2 进行解密 m ¯ i = D ( c ¯ i , k ˜ j ) , i = 1 , 2 ; j = 1 , 2 , ,可得到解密后的序列 m ¯ 1 m ¯ 2 ,转换成6比特后拼接上未作加密的2比特 m 7 m 8 ,从而得到8比特的明文序列m,全部解密完成即可得到明文图像P

特别说明如下:将矩阵I中每个像素值转换成8比特的2元序列后,为避免逐3比特分组不完整的情况,只需对前6位比特进行加密。由于灰度图像的效果主要由每个像素值的高位决定,因此只对每个8比特像素的前6位进行加密并不影响图像的加解密效果。

3.3. 仿真结果及分析

本文选取了大小为256 × 256的灰度图像Lena,根据上述算法步骤进行加解密,绘制了加密前后的图像直方图,与文献 [8] 所提出的复合两种混沌系统(Kawakami混沌系统和Bao混沌系统)且基于模2加法设计基本密码系统的流密码算法进行比较,仿真结果见图1。为方便叙述,本文将把文献 [8] 所提出的算法作为对比算法与本算法进行加密效果比较。

(a) 原图 (b) 本算法加密图 (c) 对比算法加密图 (d) 解密图 (e) 原始图像直方图 (f) 本算法加密图像直方图 (g) 对比算法加密图像直方图

Figure 1. Simulation effect of algorithm

图1. 算法仿真效果图

图像的直方图反映的是图像像素值的分布情况,像素值的分布越均匀,抵抗统计攻击的能力就越强。可以发现,两种算法都能对原始图像进行有效地加解密,加密效果相当,应用两种算法加密得到的密文图像的灰度值都接近均匀分布,能够有效抵抗统计分析,使得攻击者无法得到任何有效信息。

3.3.1. 相关性分析

图像像素的相关性指的是图像中相邻像素之间的关联程度,像素的相关性高,攻击者便可通过相邻像素预测像素值,从而获取图像数据。可靠的加密算法应保证相邻像素之间的相关性足够弱。本文在明文图像及其密文图像中随机选取了3000对相邻像素对,从水平、垂直和对角方向上绘制像素分布图,分析它们各自在三个方向上的相关性,结果如图2所示。其中,图2(a)~(c)是明文图像在水平、垂直和对角方向上像素的分布,图2(d)~(f)是利用对比算法加密得到的密文图像在水平、垂直和对角方向上像素的分布,图2(g)~(i)是利用本文算法加密得到的密文图像在水平、垂直和对角方向上像素的分布。可以看到,明文图像在三个方向的线性相关性都比较高,采用两种算法加密之后,密文图像在三个方向上的像素分布均匀性都能显著提高,相邻像素点的相关性大幅减弱,很好地掩盖了明文图像的相关特征。

(a) (b) (c) (d) (e) (f) (g) (h) (i)

Figure 2. Neighboring Pixel distribution

图2. 相邻像素分布图

相邻像素之间的相关性还可通过相关系数来表示,系数值越小,说明该图像相邻像素之间的相关性越弱,随机性越强,反之系数值越大,说明相关性越强,随机性越弱。随机选取N对相邻的像素对,并记其灰度值为 ( x i , y i ) , i = 1 , 2 , , N ,相关系数的计算公式如下:

ρ x y = cov ( x , y ) D ( x ) D ( y ) (3)

其中:

{ E ( x ) = 1 N i = 1 N x i D ( x ) = 1 N i = 1 N ( x i E ( x ) ) 2 cov ( x , y ) = 1 N i = 1 N ( x i E ( x ) ) ( y i E ( y ) ) (4)

根据式(3)和(4)分别计算明文图像和密文图像在水平、垂直和对角方向的相关系数,结果见表1。从表中可以看出,明文图像在三个方向的相关系数均接近1,表明图像像素之间的相关性较强,经过加密之后,所有方向的相关系数均接近于0,有效降低了图像像素的相关性。两种算法尽管在某一方向上的相关系数有微小差异,但总体相差无几,均可以打乱图像像素之间的关联。

Table 1. Image correlation coefficient

表1. 图像相关系数

3.3.2. 密钥敏感度分析

更进一步,对密钥敏感度进行分析,密钥敏感度指的是当密钥发生细小变化时,系统的加解密效果会发生显著变化。为了评估本文所提出的加密算法的密钥敏感度,采用了差别极其微小的两组密钥 key 1 = { x 0 : 0.000001 , y 0 = 0.000001 } key 2 = { x 0 : 0.000001001 , y 0 = 0.000001001 } 分别对图像进行加解密,结果如图3所示。对于使用key1加密的密文图像,采用key2进行解密,根本无法得到原始图像,这说明本文所设计的算法对密钥极度敏感,具有较高的安全性。

(a) 原图 (b) key1加密图 (c) key1解密图 (d) key2解密图

Figure 3. Encrypt and decrypt images with different keys

图3. 不同密钥加解密图像

3.3.3. 信息熵分析

图像的信息熵反映了图像像素值的不确定性,熵值越高,不确定性就越高。一个可靠的图像加密算法应保证密文图像具有足够高的不确定性。信息熵的计算公式如下:

H ( m ) = i = 0 M 1 p ( m i ) log 2 p ( m i ) , i = 0 M 1 p ( m i ) = 1 (5)

其中, M = 256 表示256个灰度级, p ( m i ) 表示灰度值 m i 出现的概率,根据最大熵原理,理想的密文图像的最大信息熵为8。本文计算了图像加密前后的信息熵,并与使用对比算法 [8] 得到的密文图像的信息熵进行比较,结果如表2所示。可以看到,应用本算法对图像进行加密所得到的信息熵更接近理想值8,说明经过本算法加密的密文图像具有更好的不可预测性,优于对比算法。

Table 2. Image information entropy

表2. 图像信息熵

4. 小结

本文研究了基于8阶正交拉丁方组的基本密码系统的设计方法,同时结合Henon混沌系统设计了一种新的多元流密码算法,并将其应用到图像加密上。通过对仿真结果的分析可知,该算法具有较高的安全性和可行性,为后续研究更高阶正交拉丁方组及其基本密码系统设计打下了基础。

文章引用: 林泽森 , 田传俊 (2020) 基于正交拉丁方的混沌图像加密算法设计。 计算机科学与应用, 10, 1706-1713. doi: 10.12677/CSA.2020.1010181

参考文献

[1] 张斌, 徐超, 冯登国. 流密码的设计与分析: 回顾、现状与展望[J]. 密码学报, 2016, 3(6): 527-545.

[2] Shannon, C.E. (1949) Communication Theory of Secrecy System. Bell System Technical Journal, 28, 656-715.
https://doi.org/10.1002/j.1538-7305.1949.tb00928.x

[3] 田传俊. 密钥非均匀分布的完善保密通信系统[J]. 通信学报, 2018, 39(11): 1-9.

[4] 田传俊. 基于4阶正交拉丁方组实际基本密码系统设计[J]. 深圳大学学报(理工版), 2020, 37(3): 251-256.

[5] Fridrich, J. (1997) Image Encryption Based on Chaotic Maps. IEEE International Con-ference on Systems, Orlando, FL, 12-15 October 1997, 1105-1110.

[6] 朱和贵, 蒲宝明, 朱志良, 赵怡然, 宋禹佳. 二维Sine-Tent超混沌映射及其在图像加密中的应用[J]. 小型微型计算机系统, 2019, 40(7): 1510-1518.

[7] Hénon, M. (1976) A Two-Dimensional Mapping with a Strange Attractor. Communications in Math-ematical Physics, 50, 69-77.
https://doi.org/10.1007/BF01608556

[8] 缑新科, 吴贻峰. 基于复合混沌的数字图像加密算法[J]. 计算机与数字工程, 2018, 46(12): 2574-2579.

分享
Top