1.3 混沌密码学的发展

1.3.1 混沌与密码学的关系

对于隐蔽明文消息中的冗余度，Shannon提出了两种基本的技术：混乱和扩散[17]。这也成为了密码学中指导密码设计的两个基本原则。混乱用于掩盖明文和密文之间的关系，使密钥和密文之间的统计关系变得尽可能复杂，从而导致攻击者无法从密文推理得到密钥。扩散则是将明文冗余度分散到密文中使之分散开来，以便隐藏明文的统计结构，实现方式是使得明文的每一位影响密文中多位的值。

混沌变换所具有的混合、对参数和初值的敏感性等基本特性和密码学的天然关系。混沌的伪随机特性和对系统参数的敏感性对应于传统加密系统的混乱特性[18]；混沌的轨道混合特性（与轨道发散和初值敏感性直接相联系）对应于传统加密系统的扩散特性。传统的密码算法敏感性依赖于密钥，而混沌映射依赖于初始条件和映射中的参数；传统的加密算法通过加密轮次来达到扰乱和扩散，混沌映射则通过迭代，将初始域扩散到整个相空间。混沌具有的优异混合特性保证了混沌加密器的扩散和混乱作用可以和传统加密算法一样好。另外，很多混沌系统与密码学中常用的Feistel网络结构是非常相似的，例如标准映射、Henon映射，等等[19]。

混沌和密码学之间具有的天然的联系和结构上的一些相似，启示着人们把混沌应用于密码学领域。但是混沌毕竟不等于密码学，它们之间最重要的区别在于：密码学系统工作在有限离散集上，而混沌却工作在无限的连续实数集上。此外，传统密码学已经建立了一套分析系统安全性和性能的理论，密钥空间的设计方法和实现技术也比较成熟，从而能保证系统的安全性；而目前混沌加密系统还缺少这样一个评估算法安全性和性能的标准。混沌理论与传统密码算法的相似点与不同之处如表1.1所示。

通过类比研究混沌理论与密码学，可以彼此借鉴各自的研究成果，促进共同的发展。一方面，混沌动力学中的一些物理量，可能成为密码安全性的一种标度，比如，在混沌动力学中，Lyapunov指数能有效地表示相空间内邻近轨道的平均指数发散率，可以尝试将Lyapunov指数的概念应用到加密系统中去有效地测度密码的发散程度；在混沌动力学中，Kolmogorov熵可以有效地表示信息在加密过程中信息量的损失速率，可以尝试应用Kolmogorov熵的概念来有效地标度迭代密码系统中迭代轮数的确定；一些具有良好密码特性的混沌变换还可以作为密码变换的候选者。另一方面，一些典型的密码分析工具也可以用于混沌理论的分析。由于密码学设计中十分强调引入非线性变换，因而可以肯定地说，混沌等非线性科学的研究成果将极大地促进密码学的发展。

1.3.2 混沌密码的起源与研究现状

1989年英国学者Robert A. J. Matthews首次明确提出“混沌密码”并得到广泛关注[20]。在混沌密码学发展的早期，日本学者Toshiki Habutsu于1991年发表的文章最具有代表性[21]，其中提出了混沌密码常采用的迭代加密模式，并开启了混沌密码的研究热潮。现就文献[21]中的混沌加密算法做一简要介绍，读者可以从中体会基于混沌的加密方式的特点。

文献[21]中选用了帐篷映射作为加密算法的混沌的方程，其表达式如式（1.22）所示。

帐篷映射对应的逆映射为：

显然，映射F是2对1的映射，而映射F -1是1对2的映射。因此，F n是2n对1的映射，而F -n是一个1对2n的映射。由于X =F(F-1(X))，因此X =Fn(F-n(X))。

选择混沌方程的参数α 作为密钥，加密算法如下：

步骤1，将明文转换为区间(0, 1)之间的浮点数。为描述方便，令明文转换后的浮点数位p，即0＜p＜1。将p作为混沌映射的初始值。

步骤2，反复迭代帐篷映射的逆映射[参见式（1.23）]n次，得：

并将C作为加密产生的密文。在每次进行逆变换时，在式（1.23）中任意选择其中一个方程作为变换的方程。根据加密算法可以很容易地推算出：一个明文可能会产生2n个密文并且只有其中的一个密文会被传送给接收方。

相应的解密算法如下：

采用同样的密钥 α，以密文 C作为式（1.24）的初始值，迭代帐篷映射 n次，即可恢复出明文，即

注意，在加密过程中进行每次帐篷映射的逆变换时，无论选择那个一个方程进行变化，对解密的结果都没有影响。整个加密和解密过程的示意图如图1.6所示。

上述算法非常具有吸引力的地方是整个加密和解密过程均只需要进行一个简单的混沌迭代，为密码算法的设计提供了一种新的思路。虽然，该算法后来被Eli Biham证明了存在安全问题[22]，但是基于混沌系统设计密码算法的思想却得到了学术界的认可，并随之开始了一轮混沌密码的研究。

1997年Baptista提出了一种利用混沌轨道的非线性特性，进行搜索加密的方法[23]。在该加密算法中，将混沌吸引子划分为若干个子空间（比如256 个），为每个子空间设置一个唯一标识符。加密时从当前的状态点出发，迭代混沌映射。当状态点进入代表明文字符的子空间时，将迭代次数作为对应的密文。同时为了提高密码系统的安全性，还引入了最少迭代次数和参数η。解密时，使用同样的混沌方程和初始值，仍然将混沌吸引子划分为同样的子空间并设置同样的标志符。读取一个密文，将混沌系统迭代密文所对应的次数，判断混沌轨道进入了哪个子空间，该子空间的标志符就是密文所对应的明文。该算法具有很鲜明的特点，同时也存在两个缺陷：密文的分布不均匀和加密速度较慢。随后，围绕此密码系统展开了一系列的改进和安全性分析，掀起了新一轮混沌研究的热潮。在文献[24]中，Wai-kit Wong提出引入离散均匀分布的伪随机整数rc来解决密文分布不均的问题，但这让加密速度变得更慢了。Kwok-wo Wong建议引入动态查找表来提高加密速度和增强安全性[25]。A. Palacios和H. Juarez建议使用多个耦合的混沌映射网络中发生的交替混沌来增强原始密码方案的安全性[26]。文献[27]中用已知明文攻击方法证明了M. S. Baptista的原始方案是不安全的。G. Alvarez等人对Baptista原方案及其改进方案进行了更多的安全性分析[28-30]。韦军等在文献[31, 32]中对Baptista类密码系统进行了较为彻底的分析并提出了相应的改进方案。

在最近的10年中，涌现出了数目众多的混沌密码学研究成果，其中还出现了几篇关于混沌密码的综述性文献。从总体上看，混沌密码主要有下面三个重要的设计思路：

1）使用混沌系统生成伪随机密钥流，该密钥流直接用于掩盖明文；这类加密方案要求人们深入研究利用混沌系统产生随机数的理论和离散化实现技术。

2）使用明文和/或密钥作为初始条件和/或控制参数，通过迭代/反向迭代多次的方法得到密文。第一种思路对应序列密码，而第二种思路则对应着分组密码。除了以上两种以外，最近几年还出现了一些新的设计思路，例如基于搜索机制的混沌密码方案；基于混沌系统的概率分组密码方案，等等。另外，还有不少的混沌密码方案专门为图像加密的目的而设计。

3）利用混沌来构造公开密钥密码，该项研究还处于初期阶段，混沌公钥加密的方案实用性还较差；但是对这类基于混沌的公开密钥密码系统的研究是一件很有意义的事情，对促进传统公开加密算法的改进大有益处。

① 混沌流密码

流密码的安全性主要依赖于密钥序列k = k1, k2, …。因此流密码系统设计的关键是如何设计出具有良好特性的随机密钥序列。前面曾介绍混沌是确定性非线性系统产生的类似随机性的现象，它产生于确定性系统却又难于预测。混沌系统对初值和系统参数极端敏感，相同的混沌系统在具有微小差别的初始条件下，将会发生完全不同的长期行为，混沌系统长期行为不可预测。然而，只要系统参数和初始条件给定，混沌现象本身是可以重复再生的。利用混沌系统，可以产生数量众多、非相关、类似噪声、又可以再生的混沌序列。因此将混沌理论用于流密码的设计中是可行的。

将混沌应用于流密码的设计主要有两种方式：一种是以混沌为基础设计伪随机数发生器（PRNG），另一种是利用混沌逆系统设计流密码。

近年来，有许多研究集中在使用混沌系统构造伪随机数发生器和对其性能进行分析[33-38]。对于连续混沌系统而言，很多混沌伪随机序列已经被证明具有优良的统计特性。当前两类主要的生成混沌伪随机数的方法是：1）抽取混沌轨道的部分或全部二进制比特[33, 34]；2）将混沌系统的定义区间划分为m个不相交的子区域，给每个区域标记一个唯一的数字0～m-1，通过判断混沌轨道进入哪个区域来生成伪随机数[35, 36]。在大部分基于混沌伪随机数发生器的流密码中，使用的只是单个混沌系统。迄今为止，已经有很多不同的混沌系统被采用，如Logistic映射[33, 38]，Chebyshev映射[39]，分段线性混沌映射[34,36,40-43]，分段非线性混沌映射[35]，等等。为了增强安全性，可以考虑使用多个混沌系统或者使用较为复杂的混沌系统。

文献[44,45]详细研究了利用混沌逆系统设计流密码的一般结构及其密码分析，从整体上看，密文被反馈回来经过处理以后再直接用于掩盖（采用模加操作）明文，既与上面介绍的基于混沌伪随机数发生器的序列密码有相似之处，又借鉴了分组密码的CBC工作模式。文献[40, 41, 46]提出了几种具体的基于混沌逆系统的序列密码方案，它们的结构可用一个统一的式子来表示：y(t)=u(t)+ fe(y(t-1),…, y (t-k)mod1，其中u(t),y(t)分别表示明文和密文，fe(·)是一个从反馈密文生成掩盖明文的伪随机密钥流的k元函数。

② 混沌分组密码

在分组密码算法中，混乱与扩散是其中两个重要的步骤。混乱可以通过一个复杂的替代（Substitution）算法来达到目的；而扩散可以通过重复使用对数据的某种置换（Permutation），并对置换结果再应用某个函数的方式来达到。这种由替代和置换层所构成的分组密码有时被称为替代-置换网络，或SP网络。Feistel密码网络结构是SP网络的一种特殊形式。在DES、IDEA、Rijndael等各种具体的分组密码中，都体现了Feistel网络的基本结构。前面已经提到过：混沌的轨道混合特性对应于传统加密系统的扩散特性，而混沌信号的伪随机特性和对系统参数的敏感性对应于传统加密系统的混乱特性。所以，只要算法设计正确合理，就完全可能实现将混沌理论用于分组密码中。

混沌应用于分组密码的设计主要有如下几种思路：基于逆向迭代混沌的分组密码、基于正向迭代混沌的分组密码、利用混沌设计S盒并设计传统迭代型的分组密码。

基于逆向迭代混沌的分组密码由T. Habutsu等人于1991年最早提出[21]，该算法的思路在本节前面已进行过介绍，此处不再讨论。

正向迭代混沌分组密码的基本工作流程为，通过正向迭代一个混沌映射来伪随机地置乱明文，然后利用某些替代算法改变明文的值，多次重复以上过程得到密文。这类分组密码主要是面向图像加密的方案，其中以文献[19]所提出的方案最具代表性。

S盒是分组密码的核心，是大多数传统分组密码中唯一的一个非线性部件，它的密码强度直接影响整个密码系统的安全性能。在传统密码学中，寻找性能优异的S盒是困难而费时的。利用混沌系统的伪随机和遍历特性等优良特征，借助离散化混沌变换可以设计出具有高强度的固定S盒和动态S盒[47-50]。文献[50]中提出了一种通过迭代混沌映射构造S盒的方法，利用此方法可以批量产生具有不错密码学特性的S盒，然后再通过逐个测试找到具有更高密码学性能的S盒。这种基于混沌的S盒产生方式为找寻具有优秀密码学特性的S盒提供了一种有效途径。以此为基础，文献[50]中还提出了一种基于混沌系统的采用动态S盒的分组加密算法，由于对各个分组在进行加密时所采用的S盒是动态变化的，因此该算法能更为有效地抵抗针对S盒的攻击。在设计混沌分组加密算法时，通常需要将混沌函数转换到有限状态空间，然后利用转换后的混沌变换进行加密和解密。加密和解密计算将在有限域上进行，不受精度约束，实现更快速。当前已提出了一些基于此思路设计的混沌加密算法[47, 48]。这些研究表明，利用混沌系统可以构建高强度的S盒和加密算法，从而为建造现代高强度的信息安全系统提供更丰富的素材。

③ 混沌公钥密码

与基于混沌理论的对称密码的研究比较起来，利用混沌来构造公开密钥密码的研究成果就显得太少了。就本文所知，一些比较有价值的文献有：文献[51]提出一种利用混沌吸引子来实现公钥加密的方案，但是实用性不好；L. Kocarev利用Chebyshev混沌映射的半群特性，在文献[52]中提出了一种构造公钥密码的方案，这是一篇具有创新性和实用性的文章。P. Bergamo等在文献[53]中对Kocarev公钥密码方案进行了安全性分析，指出其中存在着安全漏洞。不过2004年末L. Kocarev又提出了一种新的基于混沌的公开密钥密码的文章[54]。尽管对此混沌公开密钥密码方案的深入研究可能还会暴露出新的问题，但是基于混沌的公开密钥密码系统的设计是一种新的设计思路，对公钥密码算法的发展有很大的促进作用，值得进一步的深入研究。

④ 基于混沌的图像加密

图像是人类表达信息的重要手段之一。在很多地方需要对图像信息进行加密，比如军用卫星所拍摄的图片、军用设施图纸、医院中患者的病历图像等。当前，人们已经提出了不少的图像加密技术，如基于矩阵变换/像素置换的方法、基于伪随机序列的方法、基于现代密码体制的方法，等等。传统的通用加密算法有时并不是非常适合图像加密。混沌密码技术的出现，为数字图像加密技术的发展提供了新的思路。就基于混沌的图像加密而言，比较好的思路有基于Cat映射、Baker映射和标准映射的图像加密算法。整个加密过程通常包括像素位置置乱和像素灰度值扩散两个阶段，并通过不断地重复上述过程达到增强加密效果的目的[19, 55-61 ]。一些学者将二维混沌扩展到三维空间以增加算法的强度。在已有的混沌图像加密算法中，置乱和扩散两个阶段截然分开且控制参数固定不变，这容易给攻击者提供便利。为此，文献[62]提出了一种变控制参数的混沌图像加密算法，很好地弥补了这一安全漏洞。同时，为了提高这类混沌图像加密算法的效率，文献[63]中将置乱和扩散两个阶段合为一个阶段并通过首末位像素点位置的交换来减少整体重复迭代的次数，从而在保证图像加密安全的条件下极大地提高了算法的效率。

考虑到频域中每一点的变化都会对整个数据集产生影响。为此，文献[64]提出了一种在DCT域中对图像进行混沌加密的算法。针对图像的特点，将空域和频域变换与混沌映射相结合来进行图像加密是当前的一个研究热点。N. K. Pareek利用两个Logistic映射，在外部密钥的控制下，迭代产生混沌状态值，然后将这些混沌的状态值引入对像素值的变换中[65]。我国台湾地区的学者Jui-Cheng Yen和Jiun-In Guo提出了另外一类混沌图像加密方案[66-68]。其基本思路是：一个混沌系统被用来生成伪随机序列，该序列被用来控制像素的伪随机秘密置换或者替代。为了增强混沌序列的复杂性，提高图像加密的安全性。近年来，一些复杂混沌系统也被引入到了图像加密中。由于图像加密的信息量通常都较大，因此如何提高图像加密算法的效率是一个值得关注的问题。王毅在文献[69]中指出应该避开直接对整幅图像的像素点做置换操作，而改为选取图像子块为操作的对象，从而降低输入数据集的规模。他在文中引入了图像分块和索引表的概念，采用的是8×8的子块为处理单位。文献[70]提出了一种基于混沌的并行图像加密算法。还有一些算法将图像压缩和加密结合在一起[71,72]。即在加密的同时对图像进行压缩，这样不仅能减少运算量，而且还能减少图像的冗余度，增强算法的安全性。

⑤ 基于混沌的Hash函数

传统的Hash函数，比如MD5，SHA等，主要是通过多轮次的逻辑异或运算或者密码迭代来产生Hash值。对前一种方式，为了保证安全，迭代的轮次必须要足够多。而对于后一种方式，Hash函数的安全性和效率则主要依靠于所采用的基本密码算法。2005年，对Hash函数的碰撞性研究取得了突破性的进展，发现诸如MD5、SHA-1和RIPEMD等在抗碰撞性方面的一些以前不为人知的缺陷[73, 74]。这也使得Hash函数的研究得到了更多的重视，成为了密码学界当前的一个研究热点。

混沌作为一种新的构造Hash函数的方法也正得到越来越多学者的重视。混沌系统对初始状态和系统参数极度敏感；混沌系统的动力学行为极其复杂，不符合概率统计学原理，难以重构和预测；此外，混沌系统的迭代过程还具有单向性，混沌系统每次迭代都会产生完全不同的结果，而同一个混沌系统若系数和初值相同，将肯定产生完全相同的两个迭代序列。可见，混沌序列天然具有Hash函数所要求的单向性、初值敏感性等众多性质，完全可能基于混沌理论构造出优秀的Hash函数。下面对当前主要的一些混沌Hash函数进行简要介绍。

K. W. Wong在文献[75]中提出了一种将加密和Hash结合在一起的方法。虽然在此方案提出后不久，就被指出其中存在安全漏洞，但是这种将加密和Hash结合在一起的方式，是一种很有特色的思路，具有很好的推广价值。Xun Yi将混沌迭代变换与DM(Davies-May)方案结合在一起，提出用迭代75次帐篷映射代替块加密方式来产生Hash值[76]。此方案具有与DM方案相同的安全性，并且具有更高的效率。这种与现代密码结合的方式也值得深入研究。在借助混沌构造Hash函数时还有如下几种常用的思路：

① 通过更改混沌映射的参数或状态值来产生Hash值。在产生Hash值的过程中，通过输入的消息来更改混沌系统中的参数或状态值，从而使混沌系统的轨道发生变化，并从最终和/或中间的混沌状态值中抽取二进制位来产生Hash值。由于无论是直接改变混沌系统的状态值还是通过改变参数来改变状态值，都会对混沌轨道产生影响，且随着迭代的不断进行，这种改变会得到进一步强化，从而保证不同的消息有不同的Hash值。

② 将多个混沌映射组合在一起产生Hash值。在输入信息的过程中按照一定的策略在不同的混沌映射之间进行切换，混沌轨道的各段分别由不同的混沌映射所组成。Hash值从中间和/或最终的混沌值中抽取。

③ 利用混沌系统的状态产生Hash值。将消息作为初值一次性或分段放入混沌系统中，对混沌系统进行多次迭代，然后从最终的状态中抽取Hash值。这种情况常要求混沌系统的结构要具有可扩展性，且系统本身较为复杂其序列不易被预测。

尽管基于混沌的Hash函数构造还不够成熟，但是相信随着混沌理论研究的不断深入，与密码学结合的日益紧密，其安全性会得到不断的提高，应用前景广阔。