基于拉丁方的流密码算法设计与仿真

Design and Simulation of Stream Cipher Algorithm Based on Latin Square

摘要: 本文利用所构造的高阶拉丁方设计了一种新的基本密码系统，并结合常用的Logistic混沌系统提出了一种新的流密码算法。而且，将这种流密码算法应用于图像加密，并对加密效果进行了仿真。仿真结果表明该算法不仅密钥敏感性强、密钥空间大，而且加密后图像具备相邻像素相关性小，信息熵大等优点。

Abstract: This paper uses the constructed high-order Latin square to design a new basic cipher system, and combines the commonly used Logistic chaotic system to propose a new stream cipher algorithm. Moreover, applying this stream cipher algorithm to image encryption, the encryption effect is simulated. The simulation results show that the algorithm not only has strong key sensitivity and large key space, but also the encrypted image has the advantages of small correlation coefficient among neighbor pixels and large information entropy.

1. 引言

众所周知，加密算法是密码学的基础知识，是保护信息安全的一种基本方法，其中的流密码算法具有加解密速度快和安全性高等优点，因而在信息安全领域有着广泛应用。参照最近建立的完善保密系统一般模型，流密码算法的关键是基本密码系统和密钥流序列的设计。由文献 [1] [2] [3] [4] [5] 可知，当前常见的模2加法流密码算法的基本密码系统是由二元加法设计的，该运算过于简单，不利于设计出性能优良的流密码算法。最近，文献 [6] 利用了比模2加法更复杂的4阶拉丁方运算来设计基本密码系统，为流密码算法设计指明了一条新的设计路线。同时，文献 [7] [8] 也相继研究了16阶拉丁方构造基本密码系统的方法。由于拉丁方的数量会随着阶数的增加呈指数式增加，因此，文献 [6] [7] [8] 所能构造的拉丁方及其基本密码系统是十分有限的，还有许多问题值得进一步研究。当前，基于拉丁方设计基本密码系统的研究还未充分展开，它们在流密码算法设计中的应用还很狭窄。为了进一步推广二元加法流密码算法的设计方法，本文将给出一种任意有限阶拉丁方及其基本密码系统构造的新方法，并结合常见的Logistic离散混沌设计一种新的流密码算法。

2. 一些基本概念

参照现有密码学文献，流密码算法的基本步骤为：1) 设明文序列为 $m=m_0{m}_1{m}_2\cdots$ ；2) 利用密钥k和密钥流发生器产生一个密钥流序列 $z=k_0{k}_1{k}_2\cdots$ ；3) 利用加密变换E逐个加密明文得到密文 $c=c_0{c}_1{c}_2\cdots$，其中， $c_j=E\left(k_j,m_j\right)$，对任意 $j=0,1,2,\cdots$ ；4) 利用解密变换D将c依次解密恢复出明文序列 $m=D\left(k_0,c_0\right)D\left(k_1,c_1\right)D\left(k_2,c_2\right)\cdots$。

由文献 [6] 知，在常见的二元流密码算法中，加解密变换E和D都是模2加法。由于基本明文空间和密文空间 $Z_2=\left\{0,1\right\}$ 元素很少，因而所能设计的基本密钥变换和基本密码系统都很简单，且数量很少 [6]。为了改进这种常见的模2加法的基本加密方式，文献 [7] [8] 分别研究了单个16阶拉丁方构造基本密码系统的设计方法，但所构造的基本密码系统类型仍然有限。本文将研究新的高阶拉丁方及其相应的基本密码系统的设计方法。

定义2.1 设n阶方阵 $A={\left(a_{ij}\right)}_{n\times n}$， $n\in \left\{2,3,4,\cdots \right\}$ 满足 $a_{ij}\in \left\{0,1,\cdots ,n-1\right\}$。如果 $Z_n=\left\{0,1,2,\cdots ,n-1\right\}$ 上所有不同的数字在n阶方阵A的每行和每列中都出现，则称A为n阶拉丁方。

由于基本密码系统取决于选取的拉丁方，因此需要研究拉丁方的构造方法。考虑到同一个整数都能利用十进制和二进制两种不同形式加以表示，为了便于表述，下面将十进制整数集 $Z_{2^t}^{}=\left\{0,1,\cdots ,2^t-1\right\}$ 和二进制数集 $Z_2^t=\left\{0\cdots 00,0\cdots 01,1\cdots 11\right\}$ 不加区别，且把它们对应相等的数也不加区别。

定理2.1 设 $n=2^t$。在 $Z_n=Z_2^t$ 上定义变换或函数：对任一 $m=m_1{m}_2{m}_3\cdots m_t\in Z_n$， $m_j\in Z_2$，对任一 $j=1,2,\cdots ,t$，定义 $f_0\left(m\right)=m_t{m}_{t-1}\cdots m_2{m}_1$， $f_1\left(m\right)=m_t{m}_{t-1}\cdots m_2{\bar{m}}_1$， $f_2\left(m\right)=m_t{m}_{t-1}\cdots {\bar{m}}_2{m}_1$， $\cdots$， $f_{n-1}\left(m\right)={\bar{m}}_t{\bar{m}}_{t-1}\cdots {\bar{m}}_2{\bar{m}}_1$。记

$A={\left(a_{ij}\right)}_{n\times n}=\left(\begin{array}{cccc}{f}_0\left(0\right)& f_0\left(1\right)& \cdots & f_0\left(n-1\right)\\ f_1\left(0\right)& f_1\left(1\right)& \cdots & f_1\left(n-1\right)\\ ⋮& ⋮& \ddots & ⋮\\ f_{n-1}\left(0\right)& f_{n-1}\left(1\right)& \cdots & f_{n-1}\left(n-1\right)\end{array}\right)$

则 $A={\left(a_{ij}\right)}_{n\times n}$ 是一个n阶拉丁方。

证明：当 $m=m_1{m}_2{m}_3\cdots m_t\in Z_n$ 依次取遍 $0,1,\cdots ,n-1$ 时，对于固定的 $j=0,1,\cdots ,n-1$，依次计算 $f_j\left(m\right)$ 会得到一个n维向量，它正好是向量 $\left(0,1,\cdots ,n-1\right)$ 的一个置换。因此，矩阵 $A={\left(a_{ij}\right)}_{n\times n}$ 中每一行的全部元素是由 $0,1,\cdots ,n-1$ 组成的。而且，由变换 $f_0,f_1,\cdots ,f_{n-1}$ 的定义，不难发现，当选定一个元素 $m=m_1{m}_2{m}_3\cdots m_t\in Z_n$ 时， $f_0\left(m\right),f_1\left(m\right),\cdots ,f_{n-1}\left(m\right)$ 都不相同，因此， $A={\left(a_{ij}\right)}_{n\times n}$ 中每一列的全部元素也是由 $0,1,\cdots ,n-1$ 组成的。于是，由定义2.1可知， $A={\left(a_{ij}\right)}_{n\times n}$ 是一个n阶拉丁方，证毕！

特别地，当t取8时，由定理2.1可得如下2⁸阶拉丁方

$L_{256\times 256}=\left[\begin{array}{cccccc}0& 128& 64& 192& \cdots & 255\\ 1& 129& 65& 193& \cdots & 254\\ 2& 130& 66& 194& \cdots & 253\\ 3& 131& 67& 195& \cdots & 252\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 255& 127& 191& 63& \cdots & 0\end{array}\right]=\left[\begin{array}{c}{T}_0\\ T_1\\ T_2\\ T_3\\ ⋮\\ T_{255}\end{array}\right]$

其中， $T_0:Z_{256}\leftrightarrow Z_{256}$ 表示可逆变换： $T_0\left(0\right)=0,T_0\left(1\right)=128,\cdots ,T_0\left(255\right)=255$ 等，其中，将 $Z_{256}$ 与 $Z_2^8$ 中相互对应的数不加以区别。因此，基于L设计的理论基本密码系统 $\left(M,C,T\right)$ 满足 $M=C=Z_2^8=Z_{256}$ 和 $T=\left\{T_0,T_1,\cdots ,T_{255}\right\}$。类似于文献 [6] 中的记号，下面将所设计的流密码系统的具体明文单元设为 $m_j\in M$，对任意 $j=0,1,2,\cdots$，等等。

3. 一种新的流密码算法设计

3.1. 算法描述

参照文献 [6]，保密系统定义为从明文集M到密文集C的一组可逆变换T，可将每次加密的最小明文单元称为基本明文。基本密钥、基本密文和基本加解变换可类似定义。当 $M,T,C$ 都是基本单元时，称 $\left(M,T,C\right)$ 为理论基本(密码)系统。 $T^{-1}$ 为理论密钥(变换)集T的逆变换集。应用密码系统可类似定义。为了方便实际使用，有必要将T和 $T^{-1}$ 转化为集合K和加密变换E与解密变换D来实现。上面已设计出一个理论基本系统 $\left(M,T,C\right)$，因而还需要设计与它对应的实际基本(密码)系统 $\left(M,C,K,E,D\right)$。

1) 实际基本密码系统的设计 $\left(M,C,K,E,D\right)$

先将 $T=\left\{T_0,T_1,T_2,\cdots ,T_{255}\right\}$ 中每个变换的计算公式表示为：对任意 $m=m_0{m}_1{m}_2\cdots m_7\in Z_2^8$，

$T_0\left(m\right)=m_7{m}_6\cdots m_1{m}_0$， $T_1\left(m\right)=m_7{m}_6\cdots m_1{\bar{m}}_0$，

$T_2\left(m\right)=m_7{m}_6\cdots {\bar{m}}_1{m}_0$， $\cdots$， $T_{255}(m)={\bar{m}}_7{\bar{m}}_6\cdots {\bar{m}}_1{\bar{m}}_0$，

其中， $m_i\in Z_2$， ${\bar{m}}_i=1-m_i$， $i=0,1,\cdots ,7$。这样，实际基本密钥空间 $K=Z_{256}$ 满足 $k\leftrightarrow T_k$，对任意 $k\in K=Z_2^8$。因此，基本加密函数E的计算公式为 $c=E\left(k,m\right)=T_k\left(m\right)$。

为了方便实际应用，可将基本加密函数E和解密函数D的具体计算公式设计如下：

a) 基本加密函数E：对任一8比特基本明文 $m=m_0{m}_1\cdots m_7\in Z_2^8$ 和8比特密钥 $k=k_0{k}_1{k}_2\cdots k_7\in Z_2^8$，其中 $m_0,m_1,\cdots ,m_7,k_0,k_1,\cdots ,k_7\in Z_2$，将加密变换 $c=E\left(k,m\right)$ 统一设计为

$c=\left(m_7\oplus k_0\right)\left(m_6\oplus k_1\right)\left(m_5\oplus k_2\right)\left(m_4\oplus k_3\right)\left(m_3\oplus k_4\right)\left(m_2\oplus k_5\right)\left(m_1\oplus k_6\right)\left(m_0\oplus k_7\right)$，

其中， $\oplus$ 表示异或运算，多个相连的圆括号表示将多个比特组成一个多比特序列。

b) 基本解密函数D：对任一8比特密文 $c=c_0{c}_1{c}_2\cdots c_7\in Z_2^8$ 和8比特密钥 $k=k_0{k}_1{k}_2\cdots k_7\in Z_2^8$，其中 $c_0,c_1,\cdots ,c_7,k_0,k_1,\cdots ,k_7\in Z_2$，可将解密变换 $m=D\left(k,c\right)$ 设计为

$m=\left(c_7\oplus k_7\right)\left(c_6\oplus k_6\right)\left(c_5\oplus k_5\right)\left(c_4\oplus k_4\right)\left(c_3\oplus k_3\right)\left(c_2\oplus k_2\right)\left(c_1\oplus k_1\right)\left(c_0\oplus k_0\right)$。

至此就完成了实际基本密码系统 $\left(M,C,K,E,D\right)$ 的设计。

易见，本基本密码系统是利用定理2.1中的高阶拉丁方设计的，不过，类似于上述方法，若将定理2.1中拉丁方的阶数t加以改变，则可得到不同的拉丁方，进而可设计出不同的基本密码系统。本文不再考虑了。

2) 应用密码系统中密钥流序列的设计

上面已设计出实际基本密码系统 $\left(M,C,K,E,D\right)$，还需要设计应用密钥序列空间才能构成一个完整的流密码算法。下面再来讨论应用系统中密钥序列空间的设计问题，将利用现有的Logistic混沌系统作为一个密钥流发生器来对密钥流序列空间进行设计。该混沌系统表达式如下：

$x_{n+1}=\mu x_n\left(1-x_n\right)$

其中 $x_n\in \left[0,1\right]$，对任意的 $n=0,1,2,\cdots$，且 $\mu \in \left[0,4\right]$。当 $\mu \in \left[3.571448,4\right]$ 时，系统会处于混沌状态。

综合上述基本密码系统和Logistic混沌系统，下面将给出一种新的流密码算法设计步骤：

1) 选择一幅数字灰度图像作为明文，在Matlab软件中，该明文可表示成一个矩阵 $I={\left(m_{ij}\right)}_{m\times n}$，其中， $m_{ij}\in Z_{256}$，对任意 $i,j=0,1,\cdots ,255$ ；

2) 将矩阵I按照从左到右，从上到下的顺序转化为明文序列 $m={\tilde{m}}_1{\tilde{m}}_2{\tilde{m}}_3\cdots$，其中 ${\tilde{m}}_i\in Z_{256}$ ；

3) 设 ${\mu }_1,x_0,{\mu }_2,y_0,{\mu }_3$， ${\mu }_1,{\mu }_2,{\mu }_3\in \left[3.571448,4\right]$， $x_0,y_0\in \left[0,1\right]$ 为算法的5个密钥，其中 ${\mu }_1$， ${\mu }_2$， ${\mu }_3$ 为Logistic混沌3个不同的控制参数， $x_0$ 和 $y_0$ 为2个初值。将 $x_0$ 和 $y_0$ 分别代入 ${\mu }_1$ 和 ${\mu }_2$ 所决定的Logistic混沌系统，重复迭代500次可使得解序列较为混乱，并记 $w_0=\left(x_{501}+y_{501}\right)/2$ ；

4) 将 $w_0$ 作为初值带入 ${\mu }_3$ 所决定的Logistic混沌系统，进行多次迭代，并舍去前500个数值，令 $k_0=round\left(w_{501}\right),k_1=round\left(w_{502}\right),\cdot \cdot \cdot$，可得密钥流序列 $z=k_0{k}_1\cdots$， $k_j\in Z_2$，将密钥流序列按每8比特进行分组，将分组后的序列记为 $\tilde{z}={\tilde{k}}_0{\tilde{k}}_1\cdots$，其中 ${\tilde{k}}_0=k_0{k}_1{k}_2{k}_3{k}_4{k}_5{k}_6{k}_7\in Z_{256}$ 等；

5) 加密变换：按照加密变换 $E:{\tilde{c}}_j=E\left({\tilde{k}}_j,{\tilde{m}}_j\right),j=1,2,\cdots$，依次对明文单元 ${\tilde{m}}_j$ 加密，可得密文单元序列 $c={\tilde{c}}_1{\tilde{c}}_2\cdots$，若有必要，可将c变换为2元密文序列；

6) 解密变换：按照解密变换 $D:{\tilde{m}}_j=D\left({\tilde{k}}_j,{\tilde{c}}_j\right),j=1,2,\cdots$，依次对密文单元 ${\tilde{c}}_j$ 解密，可得明文单元序列 $m={\tilde{m}}_1{\tilde{m}}_2\cdots$。然后可将m还原为原数字图像矩阵 $I={\left(m_{ij}\right)}_{m\times n}$。

3.2. 实验结果与分析

将上述密码算法运用于数字图像加解密，取密钥 $x_0=0.\text{5}78$， $y_0=0.189$， ${\mu }_1=3.723$， ${\mu }_2=3.912$， ${\mu }_3=4.000$，与文献 [9] 中常用密码算法进行对比，Matlab仿真的加解密效果图及灰度直方图如下：

图1(e)~(g)分别为原始图像、本算法加密图像、对比算法加密图像的像素分布直方图，从图中可看出，两种算法都能对原始图像进行有效的加解密，密文图像的灰度直方图都接近均匀分布，能抵抗统计分析。更进一步，根据式(3-1)再对两种算法加密图像的相邻像素间的相关性进行计算，结果如表1。

$r_{xy}=\frac{\mathrm{cov}\left(x,y\right)}{\sqrt{D\left(x\right)}\sqrt{D\left(y\right)}}$ (3-1)

(a) 原始图像 (b) 加密后的图像 (c) 解密后的图像 (d) 常用算法加密图像 (e) 原始图片直方图 (f) 本算法加密图像直方图 (g) 常用算法加密图像直方图

Figure 1. Algorithm simulation renderings

图1. 算法仿真效果图

Table 1. Correlation simulation data

表1. 相关性仿真数据

其中：

$\begin{array}{l}\mathrm{cov}\left(x,y\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(x_i-E\left(x\right)\right)}\left(y_i-E\left(y\right)\right),\\ D\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\left(x_i-E\left(x\right)\right)}^2},\\ E\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{x}_i}\end{array}$

从表1中可看出，两种算法加密后的图像，在各个方向上相邻像素间的关系几乎为零，这说明像素间基本没有相关性。其次从表1中可知，本算法加密后的图像除了在竖直方向上仅有微小的差异外，在水平和对角方向上都比常见的流密码算法具有更低的像素相关性，这说明新算法具有更好的置乱效果。

下面对密钥空间进行分析。本算法包括五个密钥 $x_0,y_0,{\mu }_{\text{1}},{\mu }_{\text{2}},{\mu }_{\text{3}}$，假设计算精度为10⁻¹⁶，则密钥空间约为 ${10}^{80}\approx 2^{256}$。一般认为密钥空间大于2¹²⁸便能抵抗穷举攻击，因而本密码算法具有较强的抗穷举攻击的能力。另外，再对密钥敏感性进行测试，密钥敏感性指的是当密钥发生细小变化时，系统加解密效果会发生显著变化。为了评估本文所提出的加密算法的密钥敏感度，假定 ${\mu }_{\text{1}},{\mu }_{\text{2}},{\mu }_{\text{3}}$ 为固定值，采用了差别极其微小的两组密钥 $\text{key}1=\left\{x_0:0.278,y_0:0.189\right\}$ 和 $\text{key2}=\left\{x_0:0.278\text{0000001},y_0:0.189\right\}$ 分别对图像进行加解密，测试结果如图2所示。分析图2知，即使对解密密钥进行微小的改动，也无法恢复出明文，这说明本文所设计的算法对密钥极度敏感。

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

Figure 2. Key sensitivity test

图2. 密钥敏感性测试

下面再进行信息熵分析。根据图像信息熵的定义式(3-2)和最大熵原理知，由于本文所选取的Lena图像的灰度取值范围是[0, 255]，故图像中各像素值等概率出现时最大信息熵达到8。其中熵的计算公式为

$H\left(X\right)=-{\displaystyle \underset{i=1}{\overset{256}{\sum }}P\left(x_i\right){\log }_{2}P\left(x_i\right)}$ (3-2)

根据本文所选取的数字图像计算，可得原始图像信息熵为7.3722，文献 [9] 中的算法加密后的信息熵为7.9856，本算法加密后的图像信息熵为7.9994。从结果可看出，本算法加密后的图像信息熵比常用密码算法加密后的图像信息熵更接近理想值，故新密码算法具有更好的性能。

4. 小结

本文提出了一种高阶拉丁方的构造方法，并研究了这种拉丁方构造基本密码的设计问题，以及结合常见的密钥流产生器提出了一种新的流密码算法。通过与常见流加密算法对比分析可知，该算法密钥空间大，且加密后的图片信息熵更接近理想信息熵，因此该算法具有更强的抗攻击能力，具有一定的实用参考价值。