CSA  >> Vol. 10 No. 1 (January 2020)

    基于拉丁方与时变符号混沌系统的流密码算法设计
    Design of a Stream Cipher Algorithm Based on Latin Square and Time-Varying Symbolic Chaotic System

  • 全文下载: PDF(1065KB) HTML   XML   PP.118-125   DOI: 10.12677/CSA.2020.101013  
  • 下载量: 85  浏览量: 128  

作者:  

唐文君,田传俊:深圳大学电子与信息工程学院,广东 深圳

关键词:
流密码算法广义符号动力系统拉丁方基本密码系统Stream Cipher Algorithm Generalized Symbolic System Latin Square Basic Cryptosystem

摘要:

本文研究了一类三维时变广义符号动力系统的混沌性,并对它的多种伪随机性能进行了分析。在此基础上,结合拉丁方构造的基本密码系统,设计了一种多元流密码算法。最后,对该算法在数字图像上的加密效果进行了仿真,并与模2加法流密码系统的仿真结果进行了对比。仿真结果分析表明新流密码算法具有良好的加密效果和较高的安全性。

This paper studies chaos of a class of three-dimensional time-varying generalized symbolic systems, and analyzes the pseudo-randomicity of its solutions. Then, combined with the basic cryptosystem designed by Latin square, a stream cipher algorithm was designed. Finally, the encryption effect of the algorithm on digital image is simulated and compared with the simulation results of the modulo 2 addition stream cipher system. Simulation shows that this algorithm has good encryption effects.

1. 引言

众所周知,密码学中的加密算法是解决信息安全问题的有效手段之一,流密码作为现代密码学的一个重要分支,已在许多领域得到广泛应用 [1] [2] [3]。一般而言,流密码算法直接将密钥流序列与明密文序列模2加法进行加解密。但是,最近的文献 [2] 明确指出流密码算法设计可分为两个部分:一是基本密码系统设计,二是密钥流序列的设计,其中,基本密码系统可利用一组任意阶拉丁方设计,推广了利用模2加法或2阶拉丁方所设计的基本密码系统。当前,利用高于2阶拉丁方来设计基本密码系统的研究还未充分发展。另外,参照现有不少文献 [4] [5] [6] 知,可直接利用混沌系统生成的伪随机序列作为密钥流序列,因而先讨论一类新的三维时变广义符号系统。

不妨设Z为全体整数集, t Z N t = { t , t + 1 , } 为单边整数集,I为有界实数集,

{ x m + 1 , n = f ( m , x m , n , y m , n , z m , n , x m , n + 1 ) y m + 1 , n = g ( m , y m , n , x m , n , z m , n , y m , n + 1 ) z m + 1 , n = h ( m , z m , n , x m , n , y m , n , z m , n + 1 ) (1)

其中, m , n N 0 f : N 0 × I 4 I g : N 0 × I 4 I h : N 0 × I 4 I 分别为三个多元函数,并称 ( f , g , h ) 为系统(1)的系统函数。对任意定义在 Ω = { ( 0 , n ) | n N 0 } 上的三个序列 ϕ = { ϕ 0 , n } φ = { φ 0 , n } γ = { γ 0 , n } ,存

在三维离散时空序列 x = { ( x m , n , y m , n , z m , n ) } m , n = 0 满足(1),且 x m , n = ϕ m , n y m , n = φ m , n z m , n = γ m , n ,对 ( m , n ) Ω

称序列x为系统(1)初值为 ( ϕ , φ , γ ) 的一个解。由文献 [4] 可知,当 I = Z q = { 0 , 1 , , q 1 } q N 2 时,可将系统(1)称为三维时变广义符号动力系统。在不混淆时,下面也将列向量写为行向量的形式。

对任一有界实数集I,记

I 3 = { { ( a n , b n , c n ) T } n = 0 = ( a 0 a 1 a n b 0 b 1 b n c 0 c 1 c n ) | a i , b i , c i I , i = 0 , 1 , } (2)

则在 I 3 上可定义如下度量,

d 1 ( x 1 , x 2 ) = n = 0 | x 1 , n x 2 , n | + | y 1 , n y 2 , n | + | z 1 , n z 2 , n | 2 n (3)

对任意 x i = { ( x i , n , y i , n , z i , n ) } n = 0 I 3 i = 1 , 2 。易知 ( I 3 , d 1 ) 是度量空间。

x = { ( x m , n , y m , n , z m , n ) } m , n = 0 是系统(1)的一个解, x 0 , n , y 0 , n , z 0 , n I n N 0 ,且

x m = { ( x m , n , y m , n , z m , n ) } n = 0 m N 0 , (4)

Δ 1 m , n = f ( m , x m , n , y m , n , z m , n , x m , n + 1 ) Δ 2 m , n = g ( m , y m , n , x m , n , z m , n , y m , n + 1 ) ,则系统(1)等价于式(5)中给出的无穷维离散系统:

x m + 1 = { ( Δ 1 m , n , Δ 2 m , n , Δ 3 m , n ) } n = 0 = F m + 1 ( x m ) m N 0 (5)

其中, F 1 , F 2 , I 3 上由 ( f , g , h ) 决定的一列映射。称系统(5)或映射列 F = { F m } m = 1 是由系统(1)或系统函数 ( f , g , h ) 所导出的。

2. 新混沌系统的构造和伪随机性分析

I = Z q = { 0 , 1 , , q 1 } ,对任意 a , b Z q ,记 a b = ( a + b ) mod q ,则 f : N 0 × I 4 I g : N 0 × I 4 I h : N 0 × I 4 I 定义如下

f ( m , x 0 , y 0 , z 0 , x 1 ) = a 0 , m x 0 a 1 , m y 0 a 2 , m z 0 a x 1 g ( m , y 0 , x 0 , z 0 , y 1 ) = b 0 , m y 0 b 1 , m x 0 b 2 , m z 0 b y 1 h ( m , z 0 , x 0 , y 0 , z 1 ) = c 0 , m z 0 c 1 , m x 0 c 2 , m y 0 c z 1 (6)

其中, { b i , m } m = 0 { c i , m } m = 0 为周期整数数列,即存在正整数p,使得 a i , m = a i , m + p b i , m = b i , m + p c i , m = c i , m + p ,对一切 i = 0 , 1 , 2 m N 0 成立, a , b , c 是三个与q互素的正整数。

不难发现,由式(6)定义的映射 ( f , g , h ) 可产生三维时变广义符号系统如下

{ x m + 1 , n = f ( m , x m , n , y m , n , z m , n , x m , n + 1 ) = a 0 , m x m , n a 1 , m y m , n a 2 , m z m , n a x m , n + 1 y m + 1 , n = g ( m , y m , n , x m , n , z m , n , y m , n + 1 ) = b 0 , m y m , n b 1 , m x m , n b 2 , m z m , n b y m , n + 1 z m + 1 , n = h ( m , z m , n , x m , n , y m , n , z m , n + 1 ) = c 0 , m z m , n c 1 , m x m , n c 2 , m y m , n c z m , n + 1 (7)

其中, x m , n , y m , n , z m , n Z q m , n N 0 。由于系统(7)是系统(1)的特定情形,故根据系统(1)和系统(5)的关系,系统(7)等价于如下系统(8)

x m + 1 = F m + 1 ( x m ) , x 0 I 3 , m N 0 (8)

上式中, x m = { ( x m , n , y m , n , z m , n ) } n = 0 I 3 F m + 1 : I 3 I 3 是由 ( f , g , h ) 所导出的映射,且对任意 α = { ( u n , v n , w n ) } n = 0 I 3 ,记 u ˜ m , n = a 0 , m u n a 1 , m v n a 2 , m w n v ˜ m , n = b 0 , m v n b 1 , m u n b 2 , m w n w ˜ m , n = c 0 , m w n c 1 , m u n a 2 , m v n ,则有

F m + 1 ( α ) = { ( u ˜ m , n a u n + 1 , v ˜ m , n b v n + 1 , w ˜ m , n c w n + 1 ) } n = 0 (9)

参照文献 [4] [5] [6] [7],易得如下引理及推论。

引理1:对式(8)中的映射列 F = { F n } n = 1 ,存在正整数周期p,使得 F m = F m + p m N 1

推论1:设 F = { F n } n = 1 是式(8)的系统映射,则对一切 m , s , t N 1 ,都有

F s + m p 1 F s + m p 2 F s = F t + m p 1 F t + m p 2 F t

记式(8)定义的映射列 F = { F n } n = 1 所确定的复合映射为:

G m = F m F m 1 F , m N 1 (10)

引理2:对 m N 1 a , b , r I = Z q ,存在 s I ,使 a r m s = b 成立。

定义1:若式(1)的系统函数 ( f , g , h ) 所确定的映射列 F = { F n } n = 1 或系统(5)在度量空间 ( I 3 , d 1 ) 上具有传递性、周期点的稠密性和初值敏感依赖性,则称 F = { F n } n = 1 或系统(5)是Devaney混沌的,也称与系统(5)相应等价的系统(1)在 ( I 3 , d 1 ) 上是Devaney混沌的。

定理1:在上述条件下,系统(7)在度量空间 ( I 3 , d 1 ) 上是Devaney混沌的。

证明:由定义1,只需证明系统(8)在 ( I 3 , d 1 ) 上是Devaney混沌的。

U , V I 3 U , V ,对 χ = { ( r n , s n , t n ) } n = 0 U β = { ( u n , v n , w n ) } n = 0 V ,存在 θ > 0 ,使得 B θ ( χ ) = { x = { ( x n , y n , z n ) } n = 0 | d ( x , χ ) < θ } U B θ ( β ) V 。根据 d 1 的定义知,存在 M N 1 ,满足

{ x = { ( x n , y n , z n ) } n = 0 | x i = r i , y i = s i , z i = t i , i Z M ; x j , y j , z j I , j Z M } B θ ( χ ) { y = { ( o n , p n , q n ) } n = 0 | o i = u i , p i = v i , q i = w i , i Z M ; o j , p j , q j I , j Z M } B θ ( β ) (11)

x = { ( x n , y n , z n ) } n = 0 I 3 ,记

G 1 ( x ) = { ( f 0 a x n + 1 , g 0 b y n + 1 , h 0 c z n + 1 ) } n = 0 = { ( x n ( 1 ) , y n ( 1 ) , z n ( 1 ) ) } n = 0 = x ( 1 ) ,

其中 f 0 , g 0 , h 0 分别满足: f 0 ( x n , y n , z n ) = a 0 , 0 x n a 1 , 0 y n a 2 , 0 z n

g 0 ( x n , y n , z n ) = b 0 , 0 y n b 1 , 0 x n b 2 , 0 z n h 0 ( x n , y n , z n ) = c 0 , 0 z n c 1 , 0 x n c 2 , 0 y n .

由递推法可知,对 m N 1 x = { ( x n , y n , z n ) } n = 0 I 3 ,有

G m ( x ) = F m ( x ( m 1 ) ) = F m ( ( F 1 ( x ) ) ) = { ( x n ( m ) , y n ( m ) , z n ( m ) ) } n = 0 = x ( m ) , x ( 0 ) = x ,

其中 G m 定义由式(10)给出,且有

x ( m ) = { ( f m 1 ( ρ n ) a m x n + m , g m 1 ( ρ n ) b m y n + m , h m 1 ( ρ n ) c m z n + m ) } n = 0 = { x n ( m ) } n = 0 (12)

上式中 m , n N 0 ρ n = ( x n , , x n + m 1 , y n , , y n + m 1 , z n , , z n + m 1 ) = { ( x n , y n , z n ) } n n + m 1 ,G决定了映射列 f m 1 : I 3 m I g m 1 : I 3 m I h m 1 : I 3 m I

根据引理2,对任意 m N 1 ξ I ,存在整数 r , s , t I ,满足:

f m 1 ( ρ n ) a m r = ξ , g m 1 ( ρ n ) b m s = ξ , h m 1 ( ρ n ) c m t = ξ (13)

已知 χ = { ( r n , s n , t n ) } n = 0 U β = { ( u n , v n , w n ) } n = 0 V ,由式(11)、(12)、(13)知,存在 η = { ( τ n , σ n , ς n ) } n = 0 I 3 ,使 τ n = r n σ n = s n ς n = t n ,其中 n Z M ,且 τ M , σ M , ς M , 依次满足:

f M 1 ( ζ n ) a M τ n + M = u n , g M 1 ( ζ n ) b M σ n + M = v n , h M 1 ( ζ n ) c M ς n + M = w n , n N 0

其中 ζ n = { ( τ n , σ n , ς n ) } n n + M 1 。故 G M ( η ) = F M F 1 ( η ) = β V ,且 η U 。由此可见系统(8)在 ( I 3 , d 1 ) 上是传递的。同理,可以类似方法证明系统(8)在 ( I 3 , d 1 ) 上具有周期点的稠密性和初值敏感依赖性,因而系统(8)在 ( I 3 , d 1 ) 上是Devaney混沌的。证毕。

例1:设 q = 16 和时变离散时空系统为

x m + 1 , n = a 0 , m x m , n a 2 , m z m , n x m , n + 1 y m + 1 , n = b 0 , m y m , n b 1 , m x m , n 3 y m , n + 1 z m + 1 , n = c 0 , m z m , n c 1 , m x m , n c 2 , m y m , n + 1 7 z m , n + 1 (14)

其中, x 0 , n I = { 0 , 1 } a 0 , m = 1 + ( 1 ) m mod 3 a 2 , m = 3 + 2 × ( 1 ) m b 0 , m = 1 + ( 1 ) ( m + 1 ) mod 3 b 1 , m = ( m + 1 ) mod 2 c 0 , m = 1 + ( 1 ) ( m + 2 ) mod 3 c 1 , m = ( 2 m ) mod 3 c 2 , m = 5 + 2 × ( 1 + ( 1 ) mod ( m , 3 ) ) ,对任意 m , n N 0

根据现有文献无法判断系统(14)是否具有Devaney混沌性。但由于系统(14)是(7)的特殊情形,根据定理1,系统(14)是 ( I 3 , d 1 ) 上的Devaney混沌系统。

现对系统(14)的混沌解序列进行混乱性和自相关性仿真,图1(A)~(C)分别显示了解序列 X , Y , Z 在三维空间上的混乱程度,图1(D)~(F)分别显示解序列 X , Y , Z 的自相关程度。通过图1,不难发现,系统(14)的解序列都具有复杂的混乱性和良好的自相关性。同时,使用NIST推出的SP800-22软件检测包来测试解序列的伪随机性,从表1可知,均通过检测。由此可得,新系统的解序列具有良好伪随机性,可将其用于密钥流序列和流密码算法的设计之中。

Table 1. NIST pseudo-random sequence detection results

表1. NIST伪随机序列检测结果

Figure 1. Confusion and correlation of solutions

图1. 解的混乱性和自相关性

3. 基于拉丁方的多元流密码算法

3.1. 算法描述

Z n = { 0 , 1 , , n 1 } 中的n个元素在n阶方阵L的每行每列中都出现,则称L为n阶拉丁方。显然,式(15)中的矩阵是一个16阶拉丁方。

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

文献 [2] 举例说明了利用4阶拉丁方构造基本密码系统的方法。目前还没有利用更高阶拉丁方来设计基本密码系统的相关研究。下面将利用式(15)中的16阶拉丁方L设计一个基本密码系统。将所有基本明文从小到大排列为一个行向量,并将拉丁方每一行作为其加密后的相应结果。例如,L的第一行所决定的置换 T 0 : M C 0 9 1 11 2 8 3 10 15 6

不难验证:对任意 m = m 1 m 2 m 3 m 4 Z 2 4 T 0 T 3 的代数计算公式为

T 0 ( m ) = ( 8 + ( m 3 m 4 + m 3 + m 4 + 1 mod 4 ) + 4 × m 2 + 8 × m 1 ) mod 16 T 3 ( m ) = ( 8 + m 4 m 3 + 4 × m 2 + 8 × m 1 ) mod 16

类似地, T 0 ~ T 15 均能以代数式表示,它们所决定的相应基本密码系统为 ( M = C = K = Z 2 4 , E , D ) ,并将相应的加解密具体步骤设计如下:

1) 设任一明文m为二元序列 m = m 1 m 2 m j Z 2 ,将该二元序列按每4比特进行分组,将分组后所得到的明文单位序列设为 m ˜ = m ˜ 1 m ˜ 2 ,其中 m ˜ 1 = m 1 m 2 m 3 m 4 Z 16 ,等等。必要时可对m的最后一个分组填充1而组成一个4比特分组。

2) 加密变换 E : c ˜ j = E ( k j , m ˜ j ) j = 1 , 2 , ,其中,取系统(14)的一个解序列作为16元密钥流序列 k = k 1 k 2 ,可得到密文单元序列 c ˜ = c ˜ 1 c ˜ 2

3) 解密变换 D : m ˜ j = D ( k j , c ˜ j ) j = 1 , 2 , ,可得到明文16元序列 m ˜ = m ˜ 1 m ˜ 2 。然后将每个明文单元 m ˜ j 表示为4比特明文就得到解密后的原始二元明文序列 m = m 1 m 2

3.2. 实验结果及分析

将上述密码算法用于数字图像加解密,并将它与模2加法流密码系统进行的比较效果可参见图2

Figure 2. Encryption and decryption effect and gray level histogram

图2. 加解密效果及灰度直方图

图2可见,两种算法都能对原始图像进行有效的加解密,密文图像的灰度直方图都接近均匀分布,能抵抗统计分析。对明文图像和两种密文图像的相邻像素相关性做仿真计算,可见表2

Table 2. Correlation of each direction between adjacent pixels of original and encrypted graphs

表2. 原图与加密图相邻像素之间各方向的相关性

从表中可以看出,两种密文图像相邻像素相关系数都接近0,几乎不存在相关性。进一步,根据图像X信息熵的定义式(16)和最大熵原理知,由于本文所选取的Lena图像的灰度取值范围是[0,255],故图中各像素值等概率出现时最大信息熵达到8。

H ( X ) = i = 1 256 P ( x i ) log 2 P ( x i ) (16)

通过仿真计算,可得到原始图像信息熵为7.4442,新流密码系统加密图像信息熵为7.9974,模2加法流密码系统加密图像信息熵为7.9969,两种密文图的熵都比明文图的熵更接近最大理想值。综上所述,拉丁方基本密码系统在实际加密中的加密效果与传统模2加法流密码系统加密效果相差无几,且基于拉丁方基本密码系统计算复杂度更高,因而对相应流密码算法的攻击难度更大。这说明利用高阶拉丁方设计的流密码算法具有实用价值。

4. 小结

本文研究了一类新时变广义符号混沌系统,基于该系统和高阶拉丁方构造了一种与传统模2加法不同的多比特流密码算法,通过对数字图像加解密效果的分析与对比,说明了本文提出的算法具有可行性和较高的安全性。

文章引用:
唐文君, 田传俊. 基于拉丁方与时变符号混沌系统的流密码算法设计[J]. 计算机科学与应用, 2020, 10(1): 118-125. https://doi.org/10.12677/CSA.2020.101013

参考文献

[1] 张斌, 徐超, 冯登国. 流密码的设计与分析:回顾、现状与展望[J]. 密码学报, 2016, 3(6): 527-545.
[2] 田传俊. 密钥非均匀分布的完善保密通信系统[J]. 通信学报, 2018, 39(11): 1-9.
[3] 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
[4] 田传俊, 陈关荣. 广义符号动力系统的混沌性[J]. 应用数学学报, 2008, 31(3): 440-446.
[5] 田传俊, 林敬, 黎杏玲. 基于二维时变符号混沌系统的流密码算法设计[J]. 计算机科学与应用, 2018, 8(11): 1713-1719.
[6] 田传俊, 黎杏玲, 林敬. 基于时变双边混沌符号系统的流密码算法设计[J]. 计算机科学与应用, 2018, 8(10): 1582-1588.
[7] Tian, C. (2017) Chaos in the Sense of Devaney for Two-Dimensional Time-Varying Generalized Symbolic Dynamical Systems. International Journal of Bifurcation and Chaos, 27, Article ID: 1750060.
https://doi.org/10.1142/s0218127417500602