1、 1 混沌加密学概述 摘要 混沌加密学近来成为了许多研究人 员究人员研究的话题。本文将以一种更接 近加密学和混沌理论的精髓的角度对混沌 加密学进行讨论。尽管本文提出了更多的 问题而不是提供答案，不过我希望它对今 后相关的研究仍会有启发意义。 引言 在过去的十年里，研究混沌系统的行为是极大的兴趣。混沌系统的特征包括对初始条件的敏感依赖性、随机行为的相似性和有连续的宽带功率谱。 混沌在数字通信系统的几个功能模块中具有潜在的应用：压缩、加密和调制。混沌振荡自同步 1的可能性激发了一系列对混沌密码学应用的研究工作。 仅仅在本论文提到所有相关的混沌和密码学的论文就将导致极长的列表；因此，我们建议读者参考
2、一些最近的文献2。 尽管在混沌密码学领域内已经有大量的论文发表，混沌密码学的研究对 传统密码学仍起到相当大的影响。这是因为两点原因： 首先， 几乎所有的混沌加密算法都使用在实数集体上定义的动态系统，因此很难做出实际的实现和电路的实现。 第二， 在加密技术发展的时期阶段，几乎所有提出的混沌加密方法都没对安全性和加密性能作出分析。此外，大多数提出的方法加密算法性能较弱且加密速度较慢。 密码学是 公认最好的有效防御被动和主动攻击的数据保密方法 3。文献 4给出了当前传统加密算法设计的发展概述。该论文的主要结论可以归纳为以下几句话： 2 “ 显而易见，一个很好地了解当前密码分析学的人可以毫不费力地 设
3、计出安全但是效率不高的加密算法： 对于一个分组密码，设计一个基于非线性操作（避免线性旋转）和简单混合要素（传递局部变化）的圆形函数是足够的；在轮之间加入密钥的复杂形式即轮密钥（和在开始和结束的密码）。如果轮数是32，甚至更好是 64，那么破解这种缓慢的密码将会非常困难。（ 当然也有可能通过遵循这种“秘诀”来产生弱密码，但这将需要一些加密技能！ ） 。” 很可惜，许多研究混沌密码学的学者并不遵循上述的秘诀而是急于发表新的加密算法，尽管没有任何加密技术且该算法不强、低速。例如，在采用的算法中 5，信 息中的每个字符都作为整数用于逻辑方程的迭代。而这将导致密码薄弱和缓慢。事实上，这个数可以是像 65
4、536一样大，而且总是比 250大。而在传统的加密密码中，加密变换进行的次数通常小于 32。 另一方面，算法也很弱，容易被已知明文攻击破解。 该文献的作者认为混沌加密学的研究应从那些通常较弱和较慢的算法设计转换，因此为了更好地理解混沌和密码学之间可能存在的关系，不与传统的算法相比较。 混沌理论的许多基本概念如混合 、保测变换和灵敏度在加密领域已有长时间的应用。在混沌提出前的 15年前， Shannon在他的著作中写道 7： “ 良好的混合转换通常是由两个简单的非交换操作的重复乘积形成的。例如，一系列的操作可以将面团搅拌成面团。先把面团揉成一块薄的板，然后再折叠，然后卷起来，然后再折叠等 在良好
5、的转换中 函数是复杂的，涉及到许多敏感的变量 。任何一个变量的微小变化都会改变输出量。 ” 混沌与密码学之间的深层关系仍未建立。这两个科学领域之间的重要区别在于使用密码学的系统是在有限集合上工作的，而应用混沌的系统只在连续域内有意义。 这篇小论文的主要目的是讨论混沌与密码学之间的可能联系，进一步指出未来研究的一些方向。 前 言 我们假设读者熟悉 混沌理论。为了突出本文的原创性，我们简要介绍三种最常见的加密对象（也称为基元）：分组加密算法（私钥算法） ，伪随机数发生器（附加的流密码）和加密散列函数。这些原语的完整描述和它们的属性可以在文献 4找到。 在密钥的作用下，分组密码将较短的字符串（通常是
6、 64或 128位）变换为长度相同的字符串。分组加密算法通常用 x 1n =E（ xn ， z）， n=0， ， k-1的映射形式来描3 述，其中明文 x0 ，密码 xk 和密钥 z定义 在有限字母集 。分组密码的优点是它们形成了一个可以用于加密的灵活工具：它们可以用来构造其他基元。 伪随机数发生器是一种确定性的方法，通常用映射来描述，生成一个小的“随机”数称为种子，更大一组看起来杂乱的数字称为伪随机数。 考虑到定义的发生器和由发生器生成的随机数字序列，伪随机数发生器加密是安全的。当不知道发生器的种子时，计算未来和之前的数字序列将会很难。单向函数 H对任意长度原图信息 M作处理，然后返回一个固
7、定长度的值 h， h=H（ M） ，例如对给定的 M很容易计算出 h，给定 h却很难计算出 M，而且很难找出两个不同的输入得出重复相同的输出。请注意，以上的定义是非正式的，并在没有用 word一词定义时一定程度上没有用。 这可能 与加密对象何时安全的问题有联系。我们应该强调可能保护（基于一些合理的假设）的基元比目前最快的使用算法慢几个数量级。 图 1总结了混沌映射和加密算法的异同点 。混沌映射和加密算法（或更一般地定义在有限集合上的映射）有一些类似的属性 ：对初始条件和参数变化的敏感 性， 随机性的行为和带有较长周期的不稳定的周期轨道。加密算法的加密轮数会导致算法加密扩 散和混乱效果。混沌映射
8、的迭代扩展了整个相位空间中的初始区域。混沌映射的参数可以代表加密算法的密钥。混沌和密码学之间的一个重要区别是，加密4 转换是在有限集合上定义的，而混沌只在实数集上有意义。此外，在时间上加密算法的加密安全性和性能的概念在混沌理论中没有对应。 我们现在用简单的例子来说明混沌系统和定义在有限集合上的映射之间的相似性和区别。以一个混沌映射为例，我们考虑转换映射 x（ t+1） =ax（ t） （ mod1） （ 1） 相空间 x=0,1为间隔且 a1为整数。换句话说，（ 1）是一个符号的转换。由此产生的 动态反映在单位时间间隔中 a的数字性质。当正的 Lyapunov指数 a1时该映射是混沌的。各种各
9、样的函数和 /或离散时间系统已被提出应用于密码学：在所有的相位空间中，对应的映射是一个有限集合，所有的参数都是整数。最简单的例子是转换映射（ 1）的离散相位空间： p(t+1)=ap(t) (mod N) (2) 其中 a1 ， N 和 p 都 是 整 数 ， 且p0,1， .， N-1。如果 N是互质的映射（ 2）是可逆的；注意转换映射对所有 a的取值不是可逆的。所有有限相空间 的动力系统最终都是周期性的。因此，引入函数的周期 P N 描述映射 F的最小周期， F NP 是恒定的、 PN 是系统大小 N的函数的最小值。一般来说，这些函数是在带有限集合相空间的离散动力系统的最复杂对象之中提出的
10、。为了对此说明，举一个例子，映射（ 2）中 a=2。 PN 有两个极值，最小值的取值是 log logN+1，当 N=2k-1， N-1最大，N取极值， 2是乘法集 U（ N）的输入值。然而主要的问题仍然是 PN 一般的取值。答案是未知的且和一类数论问题有关，围绕阿廷猜想（详细见 8和参考文献）。计算一些量的通常取值可采用遍历理论。这个例子说明了有限相空间动力系统遍历理论发展的难点。另一方面，映射（ 1）的遍历理论要简单得多。 系统（ 2）的 Lyapunov指数（ LE）接近 0，因为每一个轨道最终都是周期性的并且自动往复。因此，在此核心的问题是估计典型轨道的 LE避免时间超过自身周期。周期
11、轨道的分析关键取决于排序。两种排序，都和 Lebesgue措施对应，在文献中被认为是：根据系统大小 N排序，和根据最小周期 PN 然后同一周期的字典排序。在映射（ 2）的条件下， 5 a=2，两种不同的排序导致两种相反的答案：根据系统大小排序产生信息的对数 可压缩性和零有限时间的 LE（ 或缺乏随机性 ） 9，而根据最小周期排序导致正的有限时间 LE值和随机性 8。 选择混沌映射 混沌动力系统似乎是加密算法的不二之选。事实上，因为 分组加密算法可以改写为离散动力系统， x 1n =F（ xn ），初始条件 x0 是要加密的明文，最终状态 xk是密码 。然后要使映射具有混沌的性质意味着“在密码字
12、位数多上扩展明文密码的影响”。 为了确保 加密算法中 动态系统 的轨道结构复杂，我们假设系统除了是混乱的，应该也是混合的（更准确地 K-mixing）。此外，为了保证系统的参数可以被用作加密密钥，我们假设系统具有混沌鲁棒性，即系统有一大组参数是混沌的。 我们现在解释 K-mixing和混沌鲁 棒性对加密的影响。 指导设计实用算法的两个一般原则是扩散和混乱。 扩散指在密码字位数多上扩展明文密码的影响以便隐藏明文的统计结构。 这一想法的延伸是指扩展一个关键数字在许多数字密文的影响。混乱是指使用变换复杂的密文对明文的统计依赖性。混沌映射的混合性质与加密变换（算法）中的扩散性质有着密切的关系。该系统具
13、有混合性（或简单地说是混合），如果对任何两个可测集合 A1和 A2，我们描述 lim n (F N A1 A2)= (A1) (A2)10。换句话说，任何一组非零测量的 初始条件最终会随系统的发展扩散到整个相空间。如果我们认为可能的（合理的）明文作为在映射（转换）相空间的初始区域，那么它是混合性 （或在其他方面，对初始条件的敏感性） 即扩展一个关键数字在许多数字密文的影响。 混合系统也有以下几个有用的特性10：如果 0 是任意测量值（对应 0 是归一和绝对连续的）， n = 0 （ F n A） ,那么 n (A) (A)。因此我们可以说带有混合属性的动力系统，任何非平衡态分布趋于平衡。换句话
14、说，当迭代次数趋于指导设计实用 算法的两个一般原则是扩散和混乱。扩散指在密码字位数多上扩展明文密码的影响以便隐藏明文的统计结构。这一想法的延伸是指扩展一个关键数字在许多数字密文的影响。混乱是指使用变换复杂的密文对明文的统计依赖性。 6 无穷大时，密文的统计（通过不变测度计算）并不取决于明文的统计（对应于映射相空间的初始区域）。 一个好的加密算法也会扩展单一数字密钥的影响。加密算法的密钥是加密算法的参数。因此，我们应该考虑到包含参数和变量的变换反映方式敏感，即“任何一个很小的变化（变量，参数）很大改变输出”。换句话说，如果我们想使用混沌映射作为加密算法，一种 “混合属性”也应该在映射的参数空间中
15、保持。这意味着我们认为只有在参数（密钥）小扰动的情况下，该混沌映射是持久的。 当小 C1 扰动产生拓扑等价系统时，动力系统在结构上是稳定的。换句话说，一个结构稳定或强大的系统会在小扰动的作用下维持其定性性质。鲁棒性或结构稳定的混沌吸引子最终可以确保在密钥空间的扩散特性。基于非鲁棒性系统的算法可能存在密钥较弱。然而，大多数的混沌吸引子的结构不稳定 11。因此，在选择混沌映射时需要谨慎小心。众所周知，在光滑系统中不可能发生鲁棒性混沌， 而分段光滑的映射可能发生结构稳定的混乱 12。 应该考虑具有一大套鲁棒性的混沌参数（密钥）的系统。一个 密码系统 的 熵 用密钥空间的大小 来衡量并且用 log2
16、K来近似，其中 K是密钥的数量。因此，动力系统的更大一套参数空间意味着它的离散化版本有更大的 K。 从信息论的角度看 混沌理论作为非线性动力系统理论的一个分支，给我们带来了一些令人惊讶的事实：低维动力系统有复杂和不可预测的行为能力。确定性系统中混沌的起源是什么？ 为简单起见，我们考虑在这里定义的离散时间 动力系统的函数 F： x X，X RN 。点集 x， F（ x）， F 2 （ x）， 被称为初始条件 x的轨道（或轨道）。我们假设有一个混沌吸引子。如果它的运动是不可预测的，吸引子会不正式地被称作混沌的：吸引子的两个附近区域有吸引子中不同、无关的行为。 确定性系统的演化通过矢量场 F和初始条
17、件 x完全确定。然而，要完全详述初始条件无限量的信息和要求具有无限精度的测量系统，都是棘手的。测量系统有限精度的影响是什么？测量初始（和未来）状态和把状态空间划分为有限个区域、观察在这个宏观世界中的演化是等价的。 任何一组覆盖状态空间、有限数目的不相交区域被称为系统的一个分区。分区状态空间的过程将符号从分区中分配给每个区域，由此产生的宏观动力学被称为符号动力学。 7 如果系统是混沌的，那么属于同一区域的不同初始状态在一段时间后会产生不同的观察结果。从我们测量系统的角度来看，相同的宏观初始状态演变不同。决定论损失的发生和分区区域之间的转换只能通过概率预定。状态空间的划分将确定性混沌系统转换为一个
18、可以从信息论的角 度来分析的遍历信息源。 Kolmogorov-Sinai熵 （用 hKS 命名）是用迭代 F的信息创造的渐近率测度。正 熵 的系统通常被认为是混乱的。混沌运动轨迹的不可预测性是由附近点指数分离引起的。不可预测性意味着不确定性：因此，人们应该期待动力系统的 熵 与它的正指数有联系。这种深层的数学结果（称为 Pesin定理 13）只有用Sinai-Ruelle-Bowen定则严格证明。 从任何测量装置的角度来看，如果动力系统产生不可预测的序列，则称为混沌动力学。它在分区空间的运动是 随机的和运动轨迹是符合序列，而动态系统在连续状态空间中（显微镜）的运动是确定的。在系统过去粗粒度轨迹知识的基础上，我们可以只从概率的角度预测它未来的宏观状态。通过划分状态空间把一个确定性系统转换为一个信息源与 Shannon定理 14的确定性系统不能产生信息并不冲突。事实上，混沌系统不产生信息。也就是说，它的演变是完全由它的初始状态决定的。一个混沌系统仅仅把关于其初始状态的信息转换为相对测量系统是可见的形式。
