ABSTRACT

This paper studies chaos of a class of two-dimensional time-varying generalized symbolic systems, gives a construction example of a special time-varying generalized symbolic chaotic system, and analyses the pseudo-randomicity of solutions of this system. At the same time, based on this system and m sequences, this paper designs a stream cipher algorithm and simulates its encryption effect in digital image. Simulation shows that the designed algorithm has good encryption effects.

Keywords:Two-Dimensional Discrete System, Generalized Symbolic System, Devaney Chaos, Stream Cipher Algorithm

基于二维时变符号混沌系统的流密码算法设计

田传俊^*，林敬，曾泉，黎杏玲

深圳大学信息工程学院，广东 深圳

收稿日期：2018年10月31日；录用日期：2018年11月12日；发布日期：2018年11月19日

摘 要

本文研究了一类二维时变广义符号动力系统的混沌性，给出了一种特殊混沌系统的构造实例，并对其混沌解序列进行了一些常见的伪随机性能分析。同时，结合m序列和该系统，设计了一种流密码算法，并对该算法在数字图像上的加密效果进行了仿真。仿真实验说明了所设计的序列密码算法具有良好的加密效果。

关键词 :二维离散系统，广义符号动力系统，Devaney混沌性，流密码算法

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

普遍认为，密码算法是信息安全领域的重要基础之一，其中，流密码算法是一种常见的密码算法。流密码算法研究的一个关键问题是密钥流序列产生器的设计，通常可用离散系统来产生。当前，混沌流密码算法是流密码算法研究的热点问题之一，其中的关键问题是如何利用离散混沌系统来产生算法中的密钥流序列。本文将先在理论上研究一类新的特殊时变广义符号混沌系统，之后再研究利用这类新系统来设计新的密钥流序列产生器的问题。由于广义符号系统比移位寄存器系统更加广泛，并且能在计算机上准确计算与实现，因此，它们在流密码算法中的应用研究是有理论和实际意义的。

作为特殊离散系统的时变广义符号混沌系统及其在构造伪随机序列方面的应用是一个研究较少的热点问题 [1] [2] [3] [4] [5] 。因此，本文将讨论如下一种新的二维时变广义符号系统的相关问题：

$\{\begin{array}{l}{x}_{m+1,n}=f\left(m,x_{m,n},y_{m,n},x_{m,n+1}\right)\\ y_{m+1,n}=g\left(m,y_{m,n},x_{m,n},y_{m,n+1}\right)\end{array}$ (1)

其中， $m,n\in N_0=\left\{0,1,2,\cdots \right\}$ ，I是实数集R的一个有界子集，k是一个正整数， $f:N_0\times I^3\to I$ 和 $g:N_0\times I^3\to I$ 是两个多元函数，并将 $\left(f,g\right)$ 称为系统(1)的系统函数或生成函数。

设 $Z=\left\{\cdots ,-1,0,1,\cdots \right\}$ 和 $N_t=\left\{t,t+1,\cdots \right\}$ ， $t\in Z$ 。记 $\Omega =\left\{\left(0,n\right)|n\in N_0\right\}$ ，则对任意定义在 $\Omega$ 上的序列 $\varphi =\left\{{\varphi }_{0,n}\right\}$ 和 $\phi =\left\{{\phi }_{0,n}\right\}$ ，一定存在二维离散时空序列 $\left(x,y\right)={\left\{\left(x_{m,n},y_{m,n}\right)\right\}}_{m,n=0}^{\infty }$ 满足(1)，且 $x_{m,n}={\varphi }_{m,n}$ 和 $y_{m,n}={\phi }_{m,n}$ ，对任意 $\left(m,n\right)\in \Omega$ 。称 $\left(x,y\right)$ 为系统(1)初值为 $\left(\varphi ,\phi \right)$ 的一个解。参照文献 [5] ，当 $I=Z_q=\left\{0,1,\cdots ,q-1\right\}$ 和 $q\in N_2$ 时，可将系统(1)称为(二维时变)(广义)符号动力系统。现有文献对时变符号系统研究很少，系统(1)的混沌性还没有文献研究过。

设 $x={\left\{\left(x_{m,n},y_{m,n}\right)\right\}}_{m,n=0}^{\infty }$ 是系统(1)的一个解，其中， $x_{0,n},y_{0,n}\in I$ ， $n\in N_0$ 。记

$x_m={\left\{\left(x_{m,n},y_{m,n}\right)\right\}}_{n=0}^{\infty }$ , $m\in N_0$ , (2)

对于任一有界子集 $I\subseteq R=\left(-\infty ,\infty \right)$ ，设

$I_2^{\infty }=\left\{{\left\{{\left(a_n,b_n\right)}^{\text{T}}\right\}}_{n=0}^{\infty }=\left(\begin{array}{ccccc}{a}_0& a_1& \cdots & a_n& \cdots \\ b_0& b_1& \cdots & b_n& \cdots \end{array}\right)|a_i,b_i\in I,i=0,1,\cdots \right\}$ . (3)

参照文献 [3] [5] ，可在 $I_2^{\infty }$ 上定义如下的一种常见形式的度量 $d:I_2^{\infty }\times I_2^{\infty }\to R^{+}=\left[0,\infty \right)$ ：

$d\left(x,y\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\frac{\left|x_{1,n}-y_{1,n}\right|+\left|x_{2,n}-y_{2,n}\right|}{2^n}}$ , (4)

对任意 $x={\left\{{\left(x_{1,n},x_{2,n}\right)}^{\text{T}}\right\}}_{n=0}^{\infty },y={\left\{{\left(y_{1,n},y_{2,n}\right)}^{\text{T}}\right\}}_{n=0}^{\infty }\in I_2^{\infty }$ ，其中，T表示转置，可省略不写。

对任意 $m=0,1,2,\cdots$ ，由式(2)，不难发现可将系统(1)等价地改写为无穷维离散系统：

$x_{m+1}={\left\{{\left(f\left(m,x_{m,n},y_{m,n},x_{m,n+1}\right),g\left(m,y_{m,n},x_{m,n},y_{m,n+1}\right)\right)}^{\text{T}}\right\}}_{n=0}^{\infty }=g_{m+1}\left(x_m\right)$ , (5)

其中， $g_1,g_2,\cdots$ 是由 $\left(f,g\right)$ 决定的 $I_2^{\infty }$ 上的一列映射。为了方便，对任意 $x\in I_2^{\infty }$ 和 $n\in N_1$ ，记

$G_n\left(x\right)=g_n\left(g_{n-1}\left(\cdots \left(g_1\left(x\right)\right)\cdots \right)\right)=g_n\circ \cdots \circ g_2\circ g_1\left(x\right)$ , $G_0\left(x\right)=x$ . (6)

下面介绍一列映射混沌性的相关概念，可参见文献 [2] [3] [4] [5] 。

定义1：对于度量空间 $\left(I_2^{\infty },d\right)$ 上的一列映射 $g_1,g_2,\cdots$ 和任意一点 $x_0\in X$ ，如果 $G={\left\{g_n\right\}}_{n=1}^{\infty }$ 的轨道 $O\left(x_0\right)={\left\{x_n\right\}}_{n=0}^{\infty }$ 是周期为p的周期序列，其中， $x_{n+1}=g_{n+1}\left(x_n\right)$ ， $n=0,1,2,\cdots$ ，则称 $x_0$ 为G或系统(5)周期为p的周期点。如果G的所有周期点组成的集合是X中的稠密子集，则称G或G所决定的系统(5)具有周期点的稠密性。

同时，如果任意两个非空开子集 $U,V\subseteq I_2^{\infty }$ ，存在整数 $n>0$ ，使得非空，则称G或系统(5)具有(拓扑)传递性。另外，如果存在 $\delta >0$ ，使得对任一 $x\in X$ 和x的邻域U，存在 $y\in U$ 和整数 $n>1$ ，使得 $d\left(G_n\left(x\right),G_n\left(y\right)\right)>\delta$ ，则称G或G决定的系统(5)具有初值敏感依赖性。

定义2：对于度量空间 $\left(I_2^{\infty },d\right)$ 上的一列映射，如果 $G={\left\{g_n\right\}}_{n=1}^{\infty }$ 或G决定的系统(5)具有传递性、周期点的稠密性和初值敏感依赖性，则称 $G={\left\{g_n\right\}}_{n=1}^{\infty }$ 或系统(5)是Devaney混沌的，也称与系统(5)等价的相应系统(1)在 $\left(I_2^{\infty },d\right)$ 上是Devaney混沌的。

2. 一类二维时变广义符号混沌系统

下面将通过例子来说明如何去构造具体的时变广义符号混沌系统。

设 $I=Z_q=\left\{0,1,\cdots ,q-1\right\}$ ，， $f:N_0\times I^3\to I$ 和 $g:N_0\times I^3\to I$ 定义如下：

$f\left(m,x_0,y_0,x_1\right)=a_{0,m}{x}_0+a_{1,m}{y}_0+a{x}_1\mathrm{mod}q=a_{0,m}{x}_0\oplus a_{1,m}{y}_0\oplus a{x}_1$ , (7)

$g\left(m,y_0,x_0,y_1\right)=b_{0,m}{y}_0\oplus b_{1,m}{x}_0\oplus b{y}_1$ , $x_0,x_1,y_0,y_1\in I$ 和 $m\in N_0$ , (8)

其中， ${\left\{a_{i,m}\right\}}_{m=0}^{\infty }$ 和 ${\left\{b_{i,m}\right\}}_{m=0}^{\infty }$ 是两个周期非负整数列，即存在整数 $p>0$ ，使得对任一和，有 $a_{i,m}=a_{i,m+p}$ 和 $b_{i,m}=b_{i,m+p}$ ，a和b是两个正整数，且a与q互素，以及b与q互素。

显然，利用式(7)和(8)所定义的函数f和g可以生成如下二维时变广义符号动力系统

$\{\begin{array}{l}{x}_{m+1,n}=f\left(m,x_{m,n},y_{m,n},x_{m,n+1}\right)=a_{0,m}{x}_{m,n}\oplus a_{1,m}{y}_{m,n}\oplus a{x}_{m,n+1}\\ y_{m+1,n}=g\left(m,y_{m,n},x_{m,n},y_{m,n+1}\right)=b_{0,m}{y}_{m,n}\oplus b_{1,m}{x}_{m,n}\oplus b{y}_{m,n+1}\end{array}$ (9)

其中， $x_{m,n},y_{m,n}\in Z_q$ ，对任意 $m,n\in N_0$ 。下面将系统(9)所等价的无穷维离散系统设为

$x_{m+1}=g_{m+1}\left(x_m\right)$ , $$ , $x_m={\left\{\left(x_{m,n},y_{m,n}\right)\right\}}_{n=0}^{\infty }$ , $m\in N_0$ , (10)

其中， $g_{m+1}:I_2^{\infty }\to I_2^{\infty }$ 是由f和g所导出的唯一映射，即对任意 $\alpha ={\left\{\left(u_n,v_n\right)\right\}}_{n=0}^{\infty }\in I_2^{\infty }$ ，有

$g_{m+1}\left(\alpha \right)={\left\{\left(a_{0,m}{u}_n\oplus a_{1,m}{v}_n\oplus a{u}_{n+1},b_{0,m}{v}_n\oplus b_{1,m}{u}_n\oplus b{v}_{n+1}\right)\right\}}_{n=0}^{\infty }$ . (11)

参照文献 [6] [7] ，并利用已知条件，容易证明如下的两个引理及其推论，其证明过程省略。

引理1：式(10)所定义的 $G={\left\{g_n\right\}}_{n=1}^{\infty }$ 是周期为p的一列映射，即 $G_m=G_{m+p}$ ， $m\in N_1$ 。

推论1：设是由式(10)所确定的一列映射，则对一切 $m,s,t\in N_1$ ，都有

$g_{s+mp-1}\circ g_{s+mp-2}\circ \cdots \circ g_s=g_{t+mp-1}\circ g_{t+mp-2}\circ \cdots \circ g_t$ . (12)

引理2：对任一、正整数m和 $r,v\in Z_q$ ，一定存在 $s\in Z_q$ ，使得 $r\oplus u^{m}s=v$ 。

定理1：时变广义符号系统(9)在度量空间 $\left(I_2^{\infty },d\right)$ 上是Devaney混沌的，其中， $I=Z_q$ 。

证明：由定义2，显然只需要证明系统(10)是 $\left(I_2^{\infty },d\right)$ 上的Devaney混沌系统就行了。

首先，将证明系统(10)在 $\left(I_2^{\infty },d\right)$ 上具有传递性。

对任意两个非空开子集 $U,V\subseteq I_2^{\infty }$ ，以及对任一 $\alpha ={\left\{\left(s_n,t_n\right)\right\}}_{n=0}^{\infty }\in U$ 和 $\beta ={\left\{\left(u_n,v_n\right)\right\}}_{n=0}^{\infty }\in V$ ，存在 $\theta >0$ ，使得 $B_{\theta }\left(\alpha \right)=\left\{x={\left\{\left(x_n,y_n\right)\right\}}_{n=0}^{\infty }\in I_2^{\infty }|d\left(x,\alpha \right)<\theta \right\}\subseteq U$ 和 $B_{\theta }\left(\beta \right)\subseteq V$ 。因此，根据式(4)所定义的度量d的性质可知，存在一个正整数M，使得

$\left\{x={\left\{\left(x_{1,n},y_{1,n}\right)\right\}}_{n=0}^{\infty }|x_{1,i}=s_i,y_{1,i}=t_i,i\in Z_M;x_{1,j},y_{1,j}\in I,j\notin Z_M\right\}\subseteq B_{\theta }\left(\alpha \right)$ ,

$$ . (13)

对任意一点 $x={\left\{\left(x_n,y_n\right)\right\}}_{n=0}^{\infty }\in I_2^{\infty }$ ，记

$G_1\left(x\right)={\left\{\left(a_{0,0}{x}_n\oplus a_{1,0}{y}_n\oplus a{x}_{n+1},b_{0,0}{y}_n\oplus b_{1,0}{x}_n\oplus b{y}_{n+1}\right)\right\}}_{n=0}^{\infty }={\left\{x_n^{\left(1\right)}\right\}}_{n=0}^{\infty }=x^{\left(1\right)}$ ,

其中， $x^{\left(1\right)}={\left\{x_n^{\left(1\right)}=\left(f_0\left(x_n,y_n\right)\oplus a{x}_{n+1},h_0\left(x_n,y_n\right)\oplus b{y}_{n+1}\right)\right\}}_{n=0}^{\infty }$ ，且函数 $f_0:I^2\to I$ 和 $h_0:I^2\to I$ 满足 $f_0\left(x_n,y_n\right)=a_{0,0}{x}_n\oplus a_{1,0}{y}_n$ 和 $h_0\left(x_n,y_n\right)=b_{0,0}{y}_n\oplus b_{1,0}{x}_n$ 。

一般地，利用递推法，对任意 $m=1,2,\cdots$ 和 $x={\left\{\left(x_n,y_n\right)\right\}}_{n=0}^{\infty }\in I_2^{\infty }$ ，都有

$G_m\left(x\right)=g_m\left(x^{\left(m-1\right)}\right)=g_m\left(\cdots \left(g_1\left(x\right)\cdots \right)\right)={\left\{x_n^{\left(m\right)}\right\}}_{n=0}^{\infty }=x^{\left(m\right)}$ , $x^{\left(0\right)}=x$ ,

其中，由式(6)定义，且

$x^{\left(m\right)}={\left\{x_n^{\left(m\right)}=\left(f_{m-1}\left(x_n,\cdots ,y_{n+m-1}\right)\oplus a^m{x}_{n+m},h_{m-1}\left(x_n,\cdots ,y_{n+m-1}\right)\oplus b^m{y}_{n+m}\right)\right\}}_{n=0}^{\infty }$ , (14)

和 $h_m:I^{2\left(m+1\right)}\to I$ 是按递推方式由G唯一决定的两列函数，对任意 $m,n\in N_0$ 。

由引理2可知，对任一整数 $$ 和 $c\in I$ ，都存在，使得

$f_{m-1}\left(x_n,\cdots ,y_{n+m-1}\right)\oplus a^{m}r=c$ , $h_{m-1}\left(x_n,\cdots ,y_{n+m-1}\right)\oplus b^{m}h=c$ . (15)

对于 $\alpha ={\left\{\left(s_n,t_n\right)\right\}}_{n=0}^{\infty }\in U$ 和 $\beta ={\left\{\left(u_n,v_n\right)\right\}}_{n=0}^{\infty }\in V$ ，由式(13)，(14)和(15)，可找到一点 $\eta ={\left\{\left(r_n,k_n\right)\right\}}_{n=0}^{\infty }\in I_2^{\infty }$ ，满足和 $k_n=t_n$ ，对，且依次可选取的 $r_M,r_{M+1},\cdots$ 和 $k_M,k_{M+1},\cdots$ ，使得如下等式成立：

$f_{M-1}\left(r_n,\cdots ,k_{n+M-1}\right)\oplus a^M{r}_{n+M}=u_n$ , $h_{M-1}\left(r_n,\cdots ,k_{n+M-1}\right)\oplus b^M{k}_{n+M}=v_n$ , $n=0,1,2,\cdots$ .

因此， $G_M\left(\eta \right)=\beta \in V$ 和 $\eta \in U$ 。这样，系统(10)在 $\left(I_2^{\infty },d\right)$ 上具有传递性。

其次，利用与上面传递性的相似证明方法，不仅可证明系统(10)具有周期点的稠密性，而且也能证明系统(10)具有初值敏感依赖性。由于证明过程是类似的，因此，省略它们的证明过程。这样，综合上面的证明过程可知，系统(10)在 $\left(I_2^{\infty },d\right)$ 上是Devaney混沌的。证毕。

例1：考虑如下时变离散时空系统

$x_{m+1,n}=a_{0,m}{x}_{m,n}\oplus a_{1,m}{y}_{m,n}\oplus x_{m,n+1}$ , $y_{m+1,n}=b_{0,m}{y}_{m,n}\oplus b_{1,m}{x}_{m,n}\oplus 3y_{m,n+1}$ , (16)

其中， $x_{0,n}\in I=\left\{0,1\right\}$ ， $q=2$ ，和 $a_{1,m}=\left(3m\right)\mathrm{mod}\left(2\right)$ ， $b_{0,m}=2+{\left(-1\right)}^{m+1}$ ， $b_{1,m}=\left(m+1\right)\mathrm{mod}\left(2\right)$ ，对任意 $m,n\in N_0$ ， $\oplus$ 和 $\mathrm{mod}\left(2\right)$ 表示模2加法运算。

由于系统(16)是时变广义符号系统，因此，现有的判断方法不能判断系统(16)是否具有Devaney混沌性。但是，由于 ${\left\{a_{i,n}\right\}}_{n=0}^{\infty }$ 和 ${\left\{b_{i,n}\right\}}_{n=0}^{\infty }$ 都是周期数列，对任一 $i=0,1$ ，且2与1、2和3都是互素的，因此，由定理1可知，系统(16)在 $\left(I_2^{\infty },d\right)$ 上是Devaney混沌的。

参见文献 [6] [7] [8] [9] [10] 的研究和分析方法，下面将对系统(16)的解序列伪随机性进行一些分析，并在此基础上，将构造一种流密码算法。

首先，系统(16)是Devaney混沌的，因而在理论上其解一般是混乱和几乎不相关的，因而下面就对解序列的混乱性和相关性进行数值计算，并与常用的Logistic系统的相应性质进行对比。仿真效果可参见图1，其中，(a)和(b)、以及(d)和(e)分别为本文符号系统解序列X和Y的混乱性和自相关函数，而(c)和(f)分别为Logistic系统解序列的混乱性和自相关函数。

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

由图1可以看出，系统(16)解具有很好的类随机性。由于广义符号系统解序列在三维空间中都很混乱，这比二维空间中的混乱性更加复杂和难以预测，因此，利用符号系统来设计密钥流序列所具有的安全性比Logistic系统就会更好一些。

其次，按照常见随机数检测方法 [10] ，再对解序列进行单比特、扑克和游程检验，参见表1。

从表1中数据可以看出，与Logistic系统的相应性能检测相比，本文符号系统大都会更容易通过上述3项随机性检测，因而它的解序列在单比特、连续多比特和游程总数的分布上都会接近均匀分布，因而其类随机性较为理想。

最后，参照现有混沌序列密码算法的设计方法，下面利用系统(16)的解序列来构造一种流密码系统：

1) 选择常见的一副数字灰度图像作为明文，利用Matlab语言可以将该图像表示为一个数字矩阵 $I={\left(m_{ij}\right)}_{256\times 256}$ ，其中，每个明文数值 $m_{ij}\in Z_{256}=\left\{0,1,\cdots ,255\right\}$ ；

2) 先选取某个JK触发器序列作为系统(16)的初始值，再利用系统(16)的某个解 $x={\left\{x_{m,n}\right\}}_{m,n=0}^{\infty }$ 计算出密钥流序列，其中，需要将二元解序列 ${\left\{x_{m,n}\right\}}_{m,n=0}^{\infty }$ 转化为在0~255中取值的密钥流序列；

3) 加密变换： $c_{ij}=x_{ij}\oplus m_{ij}$ ，其中， $c_{ij}$ 表示密文数值， $\oplus$ 表示逐比特异或运算；

4) 解密变换： $m_{ij}=x_{ij}\oplus c_{ij}$ 。

将由上述方法所构造的流密码算法与基于Logistic系统所构造的流密码算法进行效果对比，它们的Matlab仿真效果可参见图2。

表1. 三种常见随机数检测结果

图2. 加解密效果图

直观上，由图2可以看出，两种算法都能对原图像进行优良和正确的置乱加解密。下面继续再对图2中原图和两种算法加密效果图的3种方向的相邻像素值之间的相关性进行仿真计算，可见表2。

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

从表2中，可以看到原图在三个方向上相邻像素之间具有很高的相关性，在各个方向的相关系数都接近1。而经过加密后，Logistic加密图和本文符号系统加密图在各个方向的相关系数则都接近0，说明加密效果良好。而且，还可以看出，利用本文符号系统加密比利用Logistic系统加密后在多数方向上的相关性更小，加密效果会更好。

3. 小结

本文研究了二维时变广义符号系统的混沌性，并对该系统所产生的序列进行了多种常见的伪随机性能分析，结果说明系统解序列的伪随机性能优良。在此基础上，构造了一种新的序列密码算法，仿真实验说明了该算法在数字图像加密中具有良好的效果。本文对今后混沌序列密码算法的研究具有一定的参考价值和实际意义。

文章引用

田传俊,林 敬,曾 泉,黎杏玲. 基于二维时变符号混沌系统的流密码算法设计
Design of a Stream Cipher Algorithm Based on Time-Varying Symbolic Chaotic Dynamical Systems[J]. 计算机科学与应用, 2018, 08(11): 1713-1719. https://doi.org/10.12677/CSA.2018.811189

参考文献