2.2 混沌和代数群运算结合的分组加密算法

在混沌密码的设计中，将混沌与传统密码中的运算或变换进行结合是近年来兴起的一种新的趋势。以混沌为补充，弥补传统加密变换中的不足，从而增强算法的安全性，正得到混沌密码和传统密码领域内的学者越来越多的认可。

本节我们介绍一种新的基于混沌和代数群论的分组加密方法，该算法很好地体现了混沌与传统加密变换相结合的思想[89]。从目前的研究情况看，不少基于混沌的软件加密技术都是使用混沌映射来产生伪随机序列。然而，当混沌系统用有限精度的计算机来实现的时候，数字化的混沌系统表现出了许多明显的不同的行为。它们的数字动力学行为也远不如连续混沌系统的动力学行为。例如，非常短的周期；依赖于特定的数字精度等。假设采用定点运算，并且有限精度为L位（设为二进制数），则混沌系统的性能将由于以下两个原因而降低：（1）整个系统中，只有2L有限个离散值来表示混沌轨道。因此，混沌序列的周期将小于等于2L；（2）计算机的量化误差使得混沌轨道的性能也远不如理论值。文献[89]中提出的将加密与代数群运算结合的方式，能在很大程度上避免混沌在有限精度下的退化问题，其设计思想值得借鉴。

2.2.1 分段线性映射

一维分段线性混沌映射具有良好的随机统计特性，其定义如下：

式中，p是控制参数，且p∈(0,1/2)。该混沌映射在区间[0,1]上具有如下性质：

① Lyapunov指数大于零，系统是混沌的，输出信号满足遍历各态性、混和性和确定性；

② 具有一致的不变分布密度函数 f(x)=1；

③ 输出轨道的近似自相关函数τ(n)=δ(n)。

2.2.2 基于混沌和代数群运算的分组加密算法

① 密钥

加密算法要求信息的发送者和接收者知道4 个密钥参数p1,p2,x0,K，并且要求0＜ p1,p2＜1/2,p1≠ p2，K是一个8 × 8=64比特的二进制密钥串。然后定义如下两个具有相同初值(x0)的离散分段线性映射来产生拟混沌轨道：

式中，x1(0)=x2(0)=x0，并且i=0,1,2,…。

② 噪声向量

首先，分别用离散混沌映射F(p1,x1(0))和F(p2,x2(0))产生两个拟混沌序列（当然，为了更好的性能可以让映射先行迭代 N0 次）∶ x1(1),x1(2),…,x1(i),…，x2(1),x2(2),…,x2(i),…。

然后，定义噪声向量U j(j=0,1,2,…)：U j =[u 64 j,u 64 j+1,,u 64 j+63]。对任意ui有：

③ 混淆与扩散

对于 j=0,1,…，设Vj =(vj0,vj1,…,vj7)=(U j+2⊕K)＜＜＜3，这里，⊕表示按位异或，＜＜＜ 3表示循环左移3位，vji(i=0,1,…,7)是一个8位的二进制位串，即vji ={0,1}8。

首先，构造一个双射函数,映射关系如表2.6所示。

即针对每一个v ji构造一个1～8的排列wji。g∶v ji →wji的映射构造算法如下：

a）由混沌映射F(p1,x1(i))产生一个新的混沌状态x1(i+1)。

b）通过模8加1操作，抽取x1(i+1)的前8个不同的数字位得到1～8的一个排列。如果这次操作失败[即状态x1(i+1)中的数字位通过模8加1操作不能得到1～8的一个排列]或者得到的排列前面已经出现过，则转a）继续，直到得到256个不同的1～8的排列为止。对应的伪代码如下算法所示：

算法：

然后，构造一个置换/代换映射 f ji(·)：

设有一个64位的二进制位串M =(M 1,M 2,M 3,M 4,M 5,M 6,M 7,M 8)，f ji(·)的定义如下：

式中Mk(k=1,2,…,8)是一个8位的二进制位串。rj()i · 表示Mk与vji在代数群中的模28+1乘运算，即

wj ()i · 表示把(rji(M1),rji(M2),…,rji(Mk),…,rji(M8))按照映射g中wji所对应的排列进行重新排序。例如v ji =(01100001)2, w ji =(4,6,1,3,5,8,7,2), M 3=(01100010)2，由于v ji⊙M3=(11111110)2=254，则

此处，。当i从0到7时，记

式中，,是vji在群中的逆元。

④ 加密/解密过程

将原始的明文P（二进制位流）按顺序分成(P1,P2,…,Pr)块。每块长为64比特。如果最后一块Pr不足64比特，则在后面补上0。

设C 0=U 0,P0=U 1。每一块64比特的明文Pj+1,(j=0,1,2,…,r-1)将按式（2.26）加密成64比特的密文Cj+1,(j=0,1,2,…,r-1)。

每一个64比特的密文C j将按式（2.27）解密成64比特的明文Pj

其加密/解密结构如图2.6所示。在整个加/解密过程中，⊕表示在群中的按位异或，⊙表示在群中的模28+1乘运算。 表示在群中的模264加运算。

2.2.3 安全性与性能分析

① 仿真结果

对于一个加密算法而言，安全性是首要的问题。下面将从理论和仿真实验方面来阐述本文提出的加密算法的安全性。在下面的分析与实验过程中，由于而，所以用28代替0。另外，在计算群的逆元时，采用扩展的Euclidean算法。

设x0=0.436567349535648，p1=0.485734534345379，p2=0.234579834895896，密钥K="cryption"，其对应的二进制为：

先让F(p1,x0),F(p 2,x0)迭代250次，接着按照算法1构造g∶v ji →w ji的映射（参见表2.7），最后计算U0,U1,U2,V0。

U0=0111000010101011000111100011000110100100110000110110100000100001

U1=0001000000011110100101011111011010010100110000010000111000100011

U2=0111110111000110000100011010111111001110010000100100111010011011

则明文P1="example1"（其ASCII码为“101,120,097,109,112,108,101,049”）按照式（2.27）、式（2.22）和式（2.24）加密后的密文C1的ASCII码是“139,186,020,164, 087,052,026,185”。注意，在C1中可能存在一些不可打印字符。

② 密钥空间

在下面的分析中，采用了IEEE 754 浮点数标准。根据算法对密钥序列ui的产生方法可以知道，式（2.19）和式（2.20）中参数p,1 p2对最后得到的密钥序列ui的性能影响非常大。因此需要仔细地选择参数p,1 p2。设， ，x0=0.x1x2…x15。因为0＜ p1,p2＜1/2,p1≠ p2，所以p1,p2的第1 位,∈{0,1,2,3,4}，又K的长度为64位，则算法的密钥空间约为

(5 ·1014)×(5 ·1014)×(1015)× 264=2.5 ×1044× 264 ≈2207.5

如果采取暴力攻击，此时密码分析者并不需要知道具体的p,1 p2和x0，但需要知道U j,K和映射g∶v ji →wji，每一个vji（8位）所对应的排列wji（8位）。此时的密钥空间约为8!·(8!-1)…(8!-255)· 264 · 264。对目前的计算能力来说，这个数字也是足够大的。

③ 扩散与混淆分析

在此加密算法中，混合使用了三种不同代数群中的运算：群中的按位异或运算，群中的模28+1乘运算，群中的模264加运算。由于三种运算的任何两种都不满足分配律和结合律（即三种运算互不相容），再加上wj()i · 的重排。所以算法获得了很好的扩散与混淆作用。下面来证明是可交换群。

由于28+1是一个素数，所以对模28+1乘法运算⊙构成交换群。其证明过程如下：

设m=28+1=257，则m是一个素数。

1）⊙运算是自封的

假设，即0＜a,b＜m。因为m是素数，所以(a,m)=(b,m)=1且(ab,m)=1。设m去除ab所得的商是q，余数是(ab)m，即：

ab=qm+ (ab)m,0≤(ab)m＜m

所以(ab,m)=((ab)m,m)，所以((ab)m,m)=1，所以。

（2）⊙运算是可交换的

设，则a⊙b=(ab)m =(ba)m =b⊙a。所以，⊙运算是可交换的。

（3）⊙运算是可结合的

设。如果m|a-b，则(a)m =(b)m。由于ab-(a)m(b)m =a(b-(b)m)+(a-(a)m)(b)m是m的倍数。所以，m|ab-(a)m(b)m。因此，(ab)m =((a)m(b)m m。另一方面，，则c=(c)m。所以

（4）单位元e的属性

对所有的,由于1⊙g=(1× g)m =g=(g ×1)m =g⊙1，所以1是群中的单位元。

（5）逆元的唯一存在性

设，则(a,m)=1，所以存在整数c,d 使得1=ca+dm，所以(c,m)=1，((c)m,m)=1，，1=ca+dm=(ca+dm)m =(ca)m =((c)m · a)m =(c)m⊙a。因此(c)m=a-1，逆元的唯一存在性得证。

④ 加密与解密的唯一性

对于任何一个加密算法，其加密/解密的唯一性都是必需的。在此算法中涉及以下几种运算：群上的异或⊕、模加、模乘⊙和根据映射g∶vji→wji的重排置换。因此，算法的加密/解密的唯一性是由以下两点确定的：

（1）在群上的运算是可逆的，且其逆元是唯一的。

（2）映射g∶vji→wji是一个双射。

⑤ 统计测试

根据Shannon理论，一个好的加密算法应该具有良好的抗统计攻击能力。为了评估该算法性能，使用其加密如下两个文件：

（1）一个约3200字节的文本文件；

（2）一个128×128的灰度图像。

对比加密前后的明文和密文，以及对应的统计信息，如图2.7和图2.8所示。从对比测试的结果中，可以看出文本文件的密文的分布完全不同于明文，其在整个ASCII码表上的分布更加均匀。图像加密前面的直方图也同样形象地展示出密文的分布是均匀的。所以算法具有很好的抗统计攻击的能力。

更进一步，测试明文序列m1,m2,m3,…,mN和密文序列e1,e2,e3,…,eN之间的相关系数ρ，其计算公式如式（2.29）所示。

当N=800 × 8=6400和N=3200 × 8=25600时，明文序列和其相应的密文序列的相关系数计算结果如表2.8所示。实验数据全部落在μ-2σ,μ+2σ，即（-0.01254～0.01254）之间，μ和σ的定义如式（2.30）所示，它被认为是一个好的相关系数区间。

由于，这些数据都非常小，它表明明文序列和密文序列是相互独立的。

⑥ 密钥敏感性测试

任何一种密码系统都需要提供三种重要特性来防止密码分析，即

（1）对密钥敏感：对同一明文，密钥的微小变化将产生完全不同的密文。

（2）对明文敏感：对同一密钥，明文的微小变化将产生完全不同的密文。

（3）明文到密文的映射是随机的：一个好的密码系统，密文中不应该存在任何固定模式。

由于算法的密钥是由p1,p2,x0,K构成的，所以将从以下两方面来加以验证：

（1）保持p,1 p2和x0不变，改变K的最后一位得到，即

则P1="example1"加密后的密文的ASCII码为“063,228,053,068,041,184, 046, 031”，它完全不同于C1。

（2）保持p,1 p2和K不变，改变x0的最后一位得到。则

明文P1="example1"加密后的密文的ASCII码是“004,116,078, 084,185, 093 ,011,107”。

可以看出，当密钥x0只有10-15差异时，此时参与群中运算的元素及映射g(·)与原来的映射完全发生了变化（参见表2.7和表2.9）。同时，得到的密文也完全不同于C1。另外，由于本文算法在解密过程中需要v ji在群中的逆元，而不同元素的逆元也是不同的，所以本文的算法对解密密钥也是敏感的。

综述所述，文献[89]中的算法将分段线性混沌映射和群论中的变换结合在一起。所产生的密文依赖于明文、噪声向量、置换运算和代数群上的运算。它弥补了一些纯混沌密码算法的缺陷。大的密钥空间、三种群运算的扩散与混淆和排列置换运算保证了算法对统计攻击及其选择明文攻击等常用密码分析方法都有很好的抗攻击能力。