第1章 混沌密码简介
为便于本书的讨论，本章简单介绍混沌密码的基本原理。密码学本身分为对立统一的两个基本组成部分：密码设计学（密码编码学）和密码分析学[1，2]。简而言之，密码设计学研究如何设计符合具体实际应用要求的安全快速加密算法，而密码分析学研究在何种条件下可以获得给定密文对应的密钥信息。1.1节介绍密码设计学和混沌密码设计框架。1.2节主要介绍密码分析学与混沌密码分析的不同之处。
1.1 混沌密码设计
加密算法也称为密码(cipher)或密码系统(cryptosystem)。但是，密码系统可能还含有其他提供信息安全服务的密码原语(cryptographic primitive)[2]。称加密对象为明文(plaintext)，称加密结果为密文(ciphertext)，将它们分别用 P 和 C 来表示。图1.1所示的加密过程可用等式
C = EKe(P)
来表示，其中，Ke 是加密密钥；E( )是加密函数。
图1.1加解密一般模型
类似地，解密过程可表示为
P = DKd(C)
其中，Kd 是解密密钥；D( )是解密函数。当 Ke = Kd 时，该密码被称为私钥密码(private-key cipher)或对称密码(symmetric-key cipher)。私钥密码的加解密密钥必须经专门的保密途径由发送者发送给接收者。当时，该密码被称为公钥密码(public-key cipher)或非对称密码(asymmetric-key cipher)。公钥密码的加密密钥 Ke 是公开的，而只有解密密钥 Kd 需要保密，因此不需要额外的秘密途径传输密钥。
直接或间接使用混沌系统设计的密码称为混沌密码。混沌理论与相对论、量子力学一起被誉为20世纪物理学的三大发现。半个多世纪以来，混沌理论及其应用得到了极大的发展。1960年，菲尔兹奖得主 Smale 在巴西访问时发现了马蹄映射，进而奠定了严格的混沌数学理论基础[3]。1963年，美国气象学家 Lorenz(洛伦茨)研究天气预报时发现了第一个耗散混沌系统——Lorenz 系统，成为后人研究混沌理论的出发点和基石[4]。数学分析和高等数学的教材中对无限序列只提及三种情况：周期、发散和收敛。实际上还有第四种情况：混沌。1975年，马里兰大学数学系李天岩和 Yorke 发表了经典论文“Period three implies chaos”，首次在动力学研究中引入“混沌”概念，从而开创了离散混沌数学理论[5]。1976年，普林斯顿大学 May 分析了 Logistic 映射的混沌动力学，并将其应用到生物种群繁殖的数学建模[6]。1998年，Smale 提出了18个当时未解决的数学问题，其中第14个问题是 Lorenz 系统是否存在奇异吸引子[7]。由此，激发 Tucker 于2002年给出了一组使得 Lorenz 系统呈现混沌性质的参数[8]。
*著名的混沌特征是“蝴蝶效应”，即混沌系统输出的状态序列针对初始条件或控制参数的微小变化极其敏感。此外，混沌具有拓扑传递性与混合性、周期点的稠密性、随机性与遍历性、正李雅普诺夫指数、分数维和奇异吸引子等典型特征。这些特征与现代密码学中的混淆(confusion)和扩散(diffusion)等特征密切相关[9]。另外，混沌吸引子的拉伸折叠变换与香农在经典论文“Communication theory of secrecy systems”(保密系统的通信理论)中所提出的加密方法具有惊人的相似性[10]。数据加密标准(data encryption standard， DES)和高级加密标准(advanced encryption standard， AES)算法的加密结果对明文或密钥的变化非常敏感，从某种意义上讲它们可视为定义在有限域上的混沌系统（明文为初始状态，密钥为控制参数）。这种微妙的相似性吸引研究者尝试结合混沌理论和经典密码学设计全新的安全加密算法。
1989年，Matthews [11]提出了首*混沌加密函数：
(1.1)
在过去30年中，数千种混沌加密算法被提出[12–21]。混沌理论在数字混沌密码中的用途大体上可分为以下四类：
(1)利用混沌映射直接或间接地生成变换明文内像素位置的置换矩阵[22–29]。
(2)用作伪随机数生成器产生伪随机序列，进而控制一些基本加密运算的构成和组合[30–44]。混沌密码中*广泛流行的算法结构是置换、替换、置换与替换交替结合[16，45]。
(3)当明文的元素值被转换为混沌映射的初始条件和控制参数时，直接生成密文[46–49]。
(4)利用混沌系统构造公钥密码[50]，进而组建密钥协商协议[51]。
随着移动互联网、云计算、社交网络和大数据等信息技术的迅猛发展和多媒体数据撷取设备的普及，多媒体数据(图像、视频和音频等)以更快的频率在各种有线或无线网络上传输，如何保护这些多媒体数据在公开信道的传输和存储变得越来越重要[52–54]。例如，短视频功能使得小视频中的隐私信息泄露风险成为公众担心的问题。然而，这些多媒体数据和文本数据在各方面都存在巨大差异：多媒体数据存储空间较大、应用场景的实时性要求高、相邻元素之间存在强相关性、多媒体数据使用专有格式存储等，这些特征使得经典加密标准遇到严峻挑战。未压缩的多媒体数据的尺寸非常大，常规文本加密算法（如 DES 等）的加密效率不高，难以满足实时加密的要求。因此，设计特殊的多媒体加密算法是亟须解决且具有挑战性的课题。
在过去的十年中，多媒体加密算法的设计和安全分析得到了相关研究人员的高度关注，包括图像加密[55，56]、视频加密[57–61]和音频加密[62–66]。多媒体加密涉及加密和压缩之间的平衡：先加密再压缩，密文的随机性将大幅降低压缩效率。数字图像数据的传输和存储对高处理效率和安全性能都有要求，这自然导致加密和压缩的有机结合：加密压缩后的数据[67–69]，同时压缩和加密[20，58，70–72]，压缩加密后的数据[73，74]。因为图像数据是多媒体数据的一种典型形式，可帮助展现所提出的加密算法生成的实际效果，所以大多数混沌加密算法采用图像数据作为加密对象。
1.2 混沌密码分析
密码分析学依赖被密码学界广为接受的柯克霍夫原则(Kerckhoffs’s principle)：假设攻击者知道加密和解密算法的任何细节。这一假设后来被香农重新表述成香农公理“The enemy knows the algorithm”，这就意味着一个密码的安全性只能依赖解密密钥 Kd 本身。因此，密码分析者的主要任务就是从一组明文和相应密文中获取该解密密钥的信息，用来解密其他使用相同密钥加密的密文。如果一个密码被大范围、长时间使用，那么其结构很容易被攻击者获悉。换个角度说，如果在加密算法结构已知的前提条件下，攻击者都无法获取解密密钥，那么在加密算法结构未知的条件下更无从谈起。
从密码学的角度看，安全强度高的加密算法必须能有效抵抗各种常规攻击。对于大多数加密算法，应慎重检查下列四种场景下对应的攻击方法。
(1)唯密文攻击：攻击者通过传输渠道截获、从密文存储位置盗取等手段获得密文，但事先并不清楚这些密文对应的明文。因为通信信道一般是公开的，所以开展唯密文攻击的条件门槛是*低的。
(2)已知明文攻击：攻击者能通过暂时访问加密机器或者成功猜测到明文信息时，知晓所得密文所对应的明文。
(3)选择明文攻击：为了增强攻击效果（提高获得密钥信息的准确度、减少所需明文的数量或降低攻击所需的空间和时间复杂度），攻击者选择特别的明文，并设法让加密者将其加密后发送给接收者，以非法获取相应的密文。
(4)选择密文攻击：当攻击者能暂时拥有解密机器的使用权限时，可选择一些特别的密文进行解密，获得对应的明文。
由于传输通道是公开的，攻击者很容易从中截取信息，如图1.1所示。因此，在上述四种常规攻击模型中，相对于攻击者，唯密文攻击的条件门槛*低。已知明文攻击和选择明文攻击要求攻击者能暂时使用加密系统（如密钥被存储在系统中）或者能猜测出整个（或部分）明文信息。选择密文攻击要求攻击者能暂时使用解密系统。后三者攻击模型对应的具体场景看上去较难出现，但在很多实际应用中已经出现，特别是在可供攻击者任意“驰骋”的网络空间[1]。如图1.2所示，已知明文攻击和选择明文攻击都假设多个明文是用相同密钥加密的。如果该假设不成立，则该密码的密钥不能重复使用，也就是一次一密乱码本(one-time pad)。如下原因使得一次一密乱码本在现实应用中不可行：1.密码中使用的伪随机序列具有周期性，使得等价密钥不时重复；2.需要专门保密地记录密码的使用情况，这给密钥管理带来沉重的负担；3.一次一密所需辅助数据比明文数据还多，这些数据的生成和传输大大降低了加密效率。
图1.2 明文攻击示意图
在已知明文攻击或选择明文攻击的场景下，攻击者可以观察明文对的差异与相应的密文对之间的差异（图1.3），分析这些差异在加密过程中的变化规律。注意差分是相对给定运算而言的，如减法、除法和异或。进行差分运算可以消除一些加密运算，这使得相对于差分明文，所攻击的密码变得更简单，从而提升攻击性能。
图1.3差分攻击示意图与传统的文本加密算法一样，混沌加密算法需要通过相当长时间的密码分析验证后才能被大规模实际应用。众所周知，密码分析可以促进加密算法设计水平的不断提高。事实上，密码设计与密码分析是一对矛盾的统一体，它们相互推动彼此的发展和完善。*早的混沌密码分析工作是1989年针对文献[11]中混沌密码的安全分析[75]：迭代公式(1.1)生成的伪随机序列的周期非常短，特别是当计算精度较小时。
文献统计分析表明，与混沌密码设计的论文数量相比，只有极少数混沌加密算法在公开文献中被给出密码分析结果[35，36，38，40，48，76–81]。这主要归因于：1.密码分析工作本身比较复杂，论证任何一个算法的非安全性都需要严谨完整的论据作为支撑；2.不少研究人员对密码分析工作有偏见，将指出算法的安全缺陷等同于贬低加密算法设计者的贡献；3.相对于密码设计，密码分析是一个“被动”的工作，必须根据特定的算法选择相应的攻击方法。
从抽象角度看，密码分析就是一种数学建模，即在已知*少明文和密文信息的条件下以*小的时间复杂度求解获得*多密钥相关信息这一目标函数[58，66]。传统的密码分析技术往往并不能直接用来对某种图像加密算法和混沌加密算法进行密码分析[82]。混沌密码所用具体混沌系统的缺陷和性质可用来支撑针对密码特定的攻击方法：混沌同步（一致性）[83，84]；混沌遍历[85]；数字设备中的有限精度计算和量化过程使得混沌系统的动力学性质出现不同程度的退化[16，47，86–90]。
由于现有混沌密码的密码分析不足以及可供混沌密码设计者借鉴的资料缺乏，混沌加密算法的优点长期未被全面了解且它们固有的安全漏洞也未被充分发掘，这严重妨碍了混沌加密算法安全性能的进一步提高。对混沌加密算法的安全分析也给我们提供了全新的视野和出发点来探索加密算法中使用理论方法的特定性质。归纳已有的混沌密码分析工作、分析一些典型的混沌加密算法和发掘混沌加密算法固有安全缺陷，在此基础上总结设计混沌密码应遵循的基本设计原则，这是提高混沌密码安全水平的有力举措。此外，还有助于思考常见疑问“什么是混沌密码能有效解决而现代密码不能有效处理的特别任务”。
2.1 引言
要使多媒体数据变得混乱而无法辨认，*简单有效的方法是随机置换它的数据成分（如像素比特、像素、位平面、图像块、频域系数、树节点）。在图像加密中，秘密置换（也称为置乱）广泛用于改变各种元素的位置[23，24，91–9
展开
