（计算机应用技术专业论文）细胞自动机在密码学中的应用研究.pdf

摘要 细胞自动机在密码学中的应用研究 学科名称：计算机应用技术 导师姓名：姚全珠 学生姓名：李秀娟 答辩日期： ( 签名： ( 签名： 摘要 随着电子商务、电子政务等网络服务的飞速发展，对信息安全防护技术提出更 高的要求。作为信息安全核心的密码技术的自主性研发是国家和社会信息化的基础 和前提，是信息化过程中国家利益和社会权益的根本保障。细胞自动机特有的适合 v l s i 实现的简单、规则、高度并行的物理结构和复杂的动力学特性非常适合在密 码学中应用，被认为是密码技术自主化方面最有希望的核心技术之一。 本文对细胞自动机的基本理论、细胞自动机在密码学中的应用进行了研究，重 点是二维冯一诺依曼型邻域结构细胞自动机的研究。并基于此结构的细胞自动机提 出最大周期细胞自动机的构造方法，在此基础上提出密钥流发生构造方法；通过在 细胞自动机中引入遗传算法，根据生物学中的竞争生存策略选择熵值大的变换规 则，提出利用细胞自动机构造伪随机序列的方法，晟后对细胞自动机在密码学中应 用安全性进行分析。研究表明，基于细胞自动机的密码技术不仅可以简化密码系统 的设计，而且可以提高密码系统的性能。细胞自动机技术极有可能成为自主密码体 制核心技术之一，从而使得研究细胞自动机在密码学中的应用具有非常重要的价 值。 关键词：细胞自动机密钥流伪随机序列周期随机特性 a b s t r a c t c e l l u l a ra u t o m a t aa p p l i e di nc r y p t o g r a p h y m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：l ix i u j u a n( s i g n a t u r e ： d i r e c t o r ：p r o f y a oq u a n z h u ( s i g n a t u r e ： a b s t r a c t 逝趁塑) w it ht h er a p i dd e v e l o p m e n to fn e t w o r ks e r v i c es u c ha s e - c o m m e r c ea n d e - g o v e r n m e n t ，t h ec r i t e r i ao fi n f o r m a t i o ns e c 。u r i t yh a sb e i n ga d v a n c e d t h e r e s e a r c ha n de x p o i to fc r y p t o g r a p h i ct e c h n i q u ea st h ek e r n e lt e c h n i q u em u s t b eb a s e do nc o u r t t r yi n d e p e n d e n t l y ，w h i c hisc r i t i c a la s s u r a n c eo fn a t i o n a l i n t e r e s t sa n di n d i v i d u a lr i g h ti ni n f o r m a t i o ns o e i e t y c e 】l u l a ra u t o m a t a ( c a ) i sr e g u l a r ，s i m p l ea n dh i g hp a r a l l e lp r o c e s s i n ga r c h i t e c t u r ew h i c hi s s u i t a b l e o fv l s ii m p l e m e n t a t i o na n d i t sc o m p l i c a t e dd y n a m i cp r o p e r t i e s ， w h i c hi sv i e w e da st h em o s tp o t e n t i a l t e c h n i q u ei nt h es e l f d e p e n d e n t t e c h n i q u e so ft h ec r y p t o g r a p h y id i s c u s st h et h e o r yo fe e l l u l a ra u t o m a t a ，a n dt h ew a y sh o wc e l l u l a r a u t o m a t aa p p l l e di nc r y p t o g r a p h y ic o n s t r u e tm a x i m a l c y c l e1 e n g t hc e l l u l a r a u t o m a t a i ns u c c e s s i o n ，p r e s e n t i n gak e ys t r e a mg e n e r a t i o nm e t h o db a s e d o ni t ：a n dp r e s e n t i n g g e n e r a t i n gm e t h o do fp s e u d o r a n d o mn u m b e r ss e q u e n c e ( p n s ) ，t h r o u g hi m p o r t i n gg e n e t i ca l g o r i t h m a tl a s tia n a l y z et h es e c u r i t y c h a r a c t e ro fc e l l u l a ra u t o m a t ai nc r y p t o g r a p h y t h ea p p i c a t i o n so fc ai ” c r y p t o g r a p h yc a nn o to n l ys i m p l i f yt h ed e s i g no fc i p h e rs y s t e m ，b u ta l s o h a st h ep e r f o r m a n c ea d v a n t a g e s t h e s em a k et h ec aa st h ep o t e n tc a n d i d a t e o ft h ek e r n e lt e c h n i q u e si nt h ei n d e p e n d e n tr e s e a r c ho ft h ec r y p t o g r a p h y k e y w o r d s ：c e l l u l a ra u t o m a t a ( c a ) ，d s e u d o r a n d o mn u m b e r ss e q u e n c e ( p n s ) ， k e ys t r e a m ，c y c l el e n g t h ，r a n d o m i c i t y 独创性申明 茧8 3 5 2 0 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学 位论文是我个人在导师指导下进行的研究工作及取得的成果。尽我所知， 除特别加以标注和致谢的地方外，论文中不包含其他人的研究成果。与我 一同工作的同志对本文所论述的工作的任何贡献均已在论文中作了明确 的说明并己致谢。 率论文及相关资料若有不实之处，由本人承担一切相关责任。 论文作者签名：茎查终少舜夕月2 目 保护知识产权申明 本人完全了解西安理工大学有关保护知识产权的规定，即：研究生在 校攻读学位期间所取得的所有研究成果的知识产权属西安理工大学所有。 本人保证：发表或使用与本论文相关的成果时署名单位仍然为西安理工大 学，无论何时何地，未经学校许可，决不转移或扩散与之相关的任何技术 或成果。学校有权保留本人所提交论文的原件或复印件，允许论文被查阅 或借阅；学校可以公布本论文的全部或部分内容，可以采用影印、缩印或 其他手段复制保存本论文。 ( 加密学位论文解密之前后，以上申明同样适用) 论文作者签名：二螽纽导师签名：g 留啦鲜月2 日 西安理工大学硕士学位论文 1 前沿 1 1 课题背景 随着计算机和网络技术的飞速发展，互联网给人们的工作和生活带 来极大的方便。电子商务、电子政务也通过互联网迅速的发展起来。信 息安全是所有网络服务，电子商务、电子政务发展的前提和保证。我国开 展电子商务、电子政务起步相对较魄，与国外先进国家相比，在信息安 全防护技术等诸多方面都还存在不小的差距。为了保证我们国家和社会 信息安全，我国政府明确规定严格禁止直接使用国外的密码算法和安全 产品，这是因为国外出口的密码算法国外都有破译手段，关键时刻可能危 害国家利益。因此，我国提出大力发展信息安全产业的战略决策。信息 安全的核心技术是密码体制，要保证信息的真正安全，密码技术必须建 立本国的自主密码体制基础之上。只有这样，才能从根本上保障信息化 社会中国家和个人的利益。细胞自动机具有组成单元结构的简单性、单 元之闻作用的局部性和信息处理的高度并行性，并表现出复杂的全局特 性等特点，被认为是密码技术自主化方面晟有希望的核心技术之一。本文 就细胞自动机在密码学中的应用进行研究和探索，重点是基于细胞自动 机构造序列密码，并对其安全性进行分析。细胞自动机的提出为我们研 究自主密码体制提供新的解决方案和思路。 ， 1 2 细胞自动机理论的提出 1 9 4 8 年，j y o nn e u m a n n 在研究“什么逻辑组织结构的自动机具有 通用图灵机那样的自我复制特性”的问题时，首次提出细胞自动机的概 念。他采用具有2 9 个状态取值的细胞自动机建立了一个具有自我复制 特性和通用计算能力的细胞自动机模型，后来c o d d 对其进行了简化，使 用具有8 个状态的二维细胞自动机建立了一个具有自我复制特性和通用 用具有8 个状态的二维细胞自动机建立了一个具有自我复制特性和通用 细胞自动机 计算能力的细胞自动机模型”1 。但是这个模型结构复杂，需要数量庞大的 细胞单元实现，在当时难以完成物理实现，而且限制了细胞自动机理论 的发展。j v o nn e u m a n n 逝世后，经过许多人的改进，最后由a w b u r k s 完成和扩展了j v o r ln e u m a n n 的研究，物理实现了具有自我复制特性和 通用计算能力的细胞自动机模型0 1 。 细胞自动机理论自提出以来，已经经历了半个多世纪，但是真正得 到发展并引起人们广泛关注却是从九十年代初才开始、细胞自动机是时 间、空间都离散化的分布式动力学系统，系统所表现出来的宏观动力学 行为是由分散的元素问的局域作用来决定的。它是由具有拓扑空间结构 的细胞阵列、细胞状态的演化规则这两部分组成。细胞自动机的主要功 能在于可由局部特性及简单的一致性法则模拟、处理总体上具有高度复 杂性的离散过程和现象。 1 3 细胞自动机的应用领域 细胞自动机是由分布在规则网格中的每一个细胞取有限的离散状 态，遵循确定的局部规则做出同步更新，即大量细胞通过简单的局部相 互作用而构成的动力系统。它不同于一般的动力学模型，细胞自动机不 是由严格的物理方程确定，而是通过构造一系列模型的规则来实现的， 这恰恰增强了其表达复杂关系的能力，因而在许多领域都有广泛的应用。 1 3 1 细胞自动机在生物系统中的应用 自然界中，许多生物系统都是复杂系统，如神经网络和思维过程， 生物群体的消长过程，物种的进化过程和免疫系统等等。近年来，越来 越多的科学工作者运用细胞自动机方法研究各类生物系统，并取得了令 人瞩目的成果。大脑是复杂系统结构的最好代表，它由数目巨大且相互 作用的神经元构成。为了了解和重构大脑的功能，科学工作者已进行了 许多有意义的尝试。日本现代通讯研究所目前正在进行一项“细胞自动 2 西安理工大学硕士学位论文 机仿脑计划”的研究，目标是应用细胞自动机组建一个由1 0 亿个神经元 组成的具有自治能力和创造性的人工脑“。这是目前规模最大、最全面的 仿脑计划，特别是其中包括人类心智等方面的内容。 n i c h o l a sj s a v i i i 和p a u l i e nh o g e w e g 提出了一个可用于研究简单 细胞系统形态发生的三维混杂细胞自动机和偏微分方程( p d e ) 模型“1 。 他们运用该模型模拟了黏菌从单一的细胞到可爬行的成虫的生长过程。 模型的模拟结果无论在数量上还是质量上都与实地观察的结果具有很好 的一致性。 1 3 2 细胞自动机在经济系统中的应用 细胞自动机所具有的组成单元的系统性、状态的确定性、随时间演化 的相互依赖性等基本特征与经济学的复杂行为极为相似。描述复杂性的 细胞自动机方法应用于经济学的研究之中，形成非线性经济学的有机组 成部分。 经济学系统的非加和性以及细胞自动机在动态复杂系统描述中的基 本特征为细胞自动机方法在非线性经济系统中的应用奠定了基础。用细 胞自动机来模拟宏观经济系统，可以得到产生宏观经济各类动态模式的 微观机制。对细胞自动机的研究，可以使我们了解自相似行为的一般原 理，促使经济学系统的研究更加精确化、科学化。非线性经济学研究中 应用细胞自动机方法，首先要建立模拟该经济系统运作的细胞自动机模 型。然后用计算机模拟出它的演化过程，画出其演化时空图，随之分析 细胞自动机模型的演化行为。行为分析可从两方面进行：一是研究在各 个初始模式下，各个格点的一系列取值的统计特性；二是研究整个集合 的统计特性。 目前，细胞自动机在经济学研究中应用的研究主要限于理论探讨，距 离实际应用还有一定的距离。主要原因是细胞自动机在经济学系统中的 应用，目前只限于一维和二维的形式，对于更高维的形式，现在还不具 细胞自动机 备数学解决方法，而许多经济系统的复杂行为更适合于在高维情况下得 到解决。 1 3 3 细胞自动机在环境系统中的应用 细胞自动机已广泛应用于各种复杂的环境乐坑嗣计究中，主要有土壤 侵蚀、火灾蔓延、疾病传播和森林动态等系统。由于土壤侵蚀可被看成 是一个仅仅涉及局部作用的系统，所以土壤侵蚀问题是细胞自动机方法 的一个潜在的应用领域。已有一些描述土壤侵蚀过程复杂性的微分方程 模型，但这些模型的求解非常困难，且必须在大量简化的基础之上进行 求解。细胞自动机在土壤侵蚀领域的应用已取得突破性的进展，美国加 州大学的s m i t h 将地貌侵蚀的h u y g h e n s 波阵面方法与细胞自动机方法进 行比较，该模型涉及更多的状态，包括高度、水深、植被密度、渗透物、 销蚀、沉积物转移和沉积等，二者在二维情况下具有较好的一致性“1 。 许多科技工作者还运用细胞自动机模拟了植被的生长过程。如 s a a d i a 和a a s s i n e 等利用细胞自动机方法研究了地中海气候环境中的植 被生长动力学问题，得到了关于植被动力学行为较好的分析结果“1 。 1 3 4 细胞自动机在工程系统中的应用 细胞自动机由于具有结构简单和适合于并行运算的特性，已被广泛 应用于工程系统研究领域，如交通、图像处理、机器学习和控制等领域。 细胞自动机在交通系统研究中的一个最重要的应用是基于细胞自动 机的交通模型的研究。许多该领域的专家都已建立基于细胞自动机的交 通模型图，最典型的有w o l f r a m 建立的1 8 4 细胞自动机模型”1 。这些模型 揭示了交通流的非线性变化规律，真实再现了交通流中的交通复杂现象 形成全过程。这些模型不仅在城市交通发展中扮演了重要的角色，而且 为行人流细胞自动机模型规则的建立设计提供了基本准则。 w o n g t h a n a v a s u 和s a d a n a n d a 运用细胞自动机方法对二进制图像边 4 西安理工大学硕士学位论文 缘进行检测，实现了图像的像素级检测。1 ，设计出的一个新的基于细胞自 动机的二进制图像边缘检测模型可以提供二进制图像的最优边缘图，在 一般情况下这种模型好于针对灰度级图像的比较边缘算子。 细胞自动机方法已被广泛应用于机器学习和控制领域。文献“”将细 胞自动机用作高性能并行乘法器、分类器和素数筛选器。文献“”将细胞 自动机用作模式分类器。文献“2 3 利用自动机研究并行进化算法，展示了。 一个可在并行计算枫上运行的细胞自动机算法的程序。s q i a n 等提出了 一种增强学习算法和一种随机细胞自动机控制器的结构“”，学习控制了 一级倒立摆和二级倒立摆，并将随机细胞自动机模型与常规控制器和人 工神经网络方法进行了比较，强调了随机细胞自动机方法的学习控制能 力。 1 4 细胞自动机在密码学中的研究现状 2 0 世纪8 0 年代，美国p r i s t o n 研究所的s t e p h e nw o l f r a m 在细胞 自动机理论研究方面作了大量的工作，他简化了细胞自动机的状态空间 和邻域半径，以获得具有组成单元结构的简单规则性、单元之间作用的 局部互连性和信息处理的高度并行性等优点。简化后的细胞自动机不仅 具有适合v l s i 层次的简单规则结构、信息并行处理的局部互连结构，而 且具有复杂的动力学特性：1 9 8 5 年，在美洲密码学年会上，s t e p h e n w o l f r a m 发表了名为“c r y p t o g r a p h yw i t hc e l l u l a ra u t o m a t a ”的文章， 首次提出将细胞自动机的初始状态作为密钥，使用细胞自动机的前向迭 代产生的伪随机序列作为密码，从而开创了细胞自动机在密码学中的应 用研究 j4 e 细胞自动机具有的组成单元的简单、规则性。单元之间作用的局部 互连性和系统高度并行性使其极适合于在密码学中应用，尤其是在序列 密码中。并且由于细胞自动机模块之间的级联性使其易于v l s i 的实现， 成为片上系统的最佳实现技术。而由于对密码算法的外界不可访闯性的 细胞自动机 要求使得片上系统成为最佳实现方式。同时，细胞自动机单元之间的局 部互连性不但可以带来信息处理的高度并行性，而且可弱化在v l s i 的 小尺度环境中由于导线的电阻和寄生电容带来的时延效应“”，从而极大 提高了系统的性能。这使得细胞自动机与线性反馈移位寄存器l f s r 相 比，在几乎不增加系统复杂度的条件下，便可获得更高的处理速度和更 好的性能。p h t s a l i d e s 等人比较了两个使用线性反馈移位寄存器和细胞 自动机实现的6 阶内置逻辑块观察器系统，其最高速率分别为3 3 m 和5 5 m ( 工艺为2 微米n - c m o s ) “”。对于更大的系统，细胞自动机具有更大 的优势，这是因为在v l s i 的小尺度下导线的延时与其长度的平方成正比。 所以，对于系统的v l s i 实现，细胞自动机是一种理想的方法。 1 9 8 9 年，p e t e rd h o r t e n s i u s 提出使用具有m 序列特性的细胞自 动机产生伪随机序列“”；1 9 9 4 年，s n a n d i 提出使用g f ( 2 ) 上的可编程细 胞自动机和存储单元来产生伪随机序列“：1 9 9 7 年，d o l o r e sd e l a ， g u i a - m a r t i n e z 等提出了一种使用线性移位寄存器来控制每个时刻细胞 自动机迭代次数的伪随机序列发生方法，以提高产生伪随机序列的线性 复杂度和周期“”；1 9 9 8 年，m d a s c a l u 等在w o l f r a m 方法基础上加入存 储单元来减少细胞自动机过早的进入状态循环“，但是它们同样不可避 免的不能保证产生伪随机序列的周期特性。1 9 9 8 年，m i o d r a gm i h a l j e v i c 等提出在g f ( q ) 上使用线性细胞自动机的前向迭代产生伪随机序列的方 法o ”，并于1 9 9 9 年提出了在g f ( q ) 上使用线性可编程细胞自动机的前向 迭代产生伪随机序列的方法o ”，但是对于一般实用的伪随机序列方法均 是在g f ( 2 ) 而非g f ( q ) 上实现的，这不仅是因为在g f ( 2 ) 上产生伪随机序 列最容易，而且使用硬件实现时g f ( 2 ) 具有最大的并行性。 细胞自动机在伪随机数伪随机序列发生方法方面获得应用的同时， 在细胞自动机对称密码方面也获得了相应的发展。1 9 9 5 年， b s r i s u c h i n w o n g 等人提出将非线性细胞自动机用于p e i s t e l 型密码中 的非线性函数，并将另一个线性细胞自动机作为每一分组数据的加密密 6 西安理工大学硕士学位论文 钥的方法啪1 。1 9 9 6 年，l a f e 首次提出基于细胞自动机变换的概念，并提 出了一种基于细胞自动机变换的加密方法“。2 0 0 2 年，c h a n gn z h a n g 等提出了s n a n d i 等人在文献1 8 中提出的基于置换群基本变换的分组加 密技术的一种实现方法1 。 国内在这一方面的研究工作开展得还不太多，仅有几家长期从事序 列密码的研究单位在这一方面有所关注或投入部分力量。对细胞自动机 的研究大多集中子以下几个方面：细胞自动机的周期性研究；细胞自 动机构造密码研究；对细胞自动机构造的密码进行复杂性分析等。 虽然基于细胞自动机的密码算法的安全性还有待于检验，同时其作 为一个完整的密码算法实现还处于探索阶段，但是细胞自动机作为密码 系统中的一个构件模块是具有很好的前途。本文对二维细胞自动机在密 码学中的应用作一定的研究和探索工作，利用二维细胞自动机提出构造 密钥流发生方法和随机序列发生方法，并分析相应的密码强度。 1 5 论文结构和章节安排 文章首先介绍了我国研究自主密码体制的必要性和重要性，细胞自动 机作为一种有希望的自主密码技术的核心技术之一，提出了解决问题的 新思路，从而指明了本课题研究的动机和出发点。并简单介绍了细胞自 动机的提出和在相关领域的研究状况。在下一章，论述细胞自动机的数 学定义和细胞自动机的性质和构成，主要研究维二值三邻域结构的基 本细胞自动机。本文主要是研究细胞自动机在序列密码中的应用，在第 三章主要介绍了序列密码的基本概念和相关定理。在第四章基于二维冯一 诺依曼邻域结构的细胞自动机提出构造最大周期的方法，并利用最大周 期细胞自动机研究密钥流发生方法。第五章，基于二维冯一诺依曼邻域结 构细胞自动机构造伪随机序列，在细胞自动机理论中引入生物学中的竞 争生存策略，在具体规则变换中引入遗传算法，从而保证伪随机序列良 好的随机统计特性。最后，对细胞自动机的硬件实现进行分析，与线性 7 细胞自动机 反馈移位寄存器l f s r 等其它方法相比，细胞自动机的最大优势在于其特 有的适合v l s i 实现的组成单元的简单规则性、单元之间的局部互连性和 信息处理的高度并行性等。因此，基于细胞自动机的密码技术不仅可以 简化密码系统的设计，而且可以提高密码系统的性能。 西安理工大擘硕士学位论文 2 细胞自动机 本章对细胞自动机的基本概念、 动机的性质等问题进行介绍和研究， 进行研究的基础。 2 1 细胞自动机的定义 构成和基本特性、以及基本细胞自 细胞自动机理论是后续章节中作者 细胞自动机( c e l l u l a ra u t o m a t a ，简称c a ) 是一种特殊的有限状态 机，在电子科学领域称为迭代阵列。细胞自动机是在时间和空间上都离 散的动力演化系统。细胞自动机由具有一定状态的细胞单元组成的均分 阵列构成，每细胞单元在离散时间上的状态由该点和其相邻的细胞在 上一时间的状态和局部演化规则麸同决定，所有细胞单元依据演化规则 同步更新。在任一时刻，诸小单元状态的总体构成细胞自动机的格局。 从初始格局到最后格局的演化过程为计算处理过程，最后格局被视为计 算结果。所以，细胞自动机的每一小单元实际上均为一有限自动机，细 胞自动机即为有限态自动机的动态阵列，细胞自动机格局的演化过程即 为并行计算过程。 ( 1 ) 细胞自动机的数学定义 细胞自动机的数学定义可用集合表示：一个d 一维细胞自动机( d - c a ) 是一个4 维空间( z 4 ，s ，n ，f ) ，其中z 表示c a 中每个节点的值所构成 的集合；s 表示一个有限集，其中每一个元素就是c a 的一个状态；n 表 示z 。的一个有限子集，n = n 。ln ，= ( x ，扎) ，j ( 1 ，1 1 ) ，n q 做c a 的邻居，用r 表示邻域半径：f 表示c a 的一个状态转移函数，它是 一个局部变换规则。对细胞空间内的细胞，独立施加局部交换规则，则 可得到全局的变化。称细胞自动机某个时刻的全局状态 x ，( 盛，薪，薪一。) 为系统的配置，并称决定全局配置之间的转换 9 细胞自动机 关系为全局函数，它由局部函数规则f 决定x ，( z ，z ? ，斌。) 2 x ，( ，并2 f ( ，薪一，蜊) ，) 。至此，就得到了一个细 胞自动机模型。 ( 2 ) 细胞自动机的拓扑学定义 同样以一维细胞自动机为例，设s 为k 个符号的有限集。z 为整数全 体的集，称z 到s 的映射的全体s 2 为构形空间。那么s 。就是用s 中的符 号组成的双侧无限的符号序列的全体，即一维细胞自动机的所有构形的 集合。称a = ( a 一：a oa h ) 为构形空间中的点。在s 2 中引进任意两点x 和y 之间的距离 d ( x ，y ) 2 占( ，弘) 2 刊 ( 2 一1 ) 其中当x i = y t 时6 ( x 。，y 。) = 0 ，当x 。y 。时6 ( x 。，y 。) = l 。然后在s 2 中 可以建立起开、闭、紧等概念。在s 2 中定义移位算子6 为6 ( x 。) = 轧。 i z 。若连续映射f ：s z - s 2 与6 可交换，即f6 = 6f 。或对任意的 x s 2 有f ( ( 6 ( x ) ) = 5 ( f ( x ) ) ，则称f 为细胞自动机。根据一维定义，很 容易将它扩展到一个任意维数空间，所要做的工作只是将s 2 记为s 。，s “” 记为s “”。等，同时对一些描述作相应的改变。 2 2 细胞自动机的构成 ( 1 ) 细胞 细胞是细胞自动机的基本元素之一，细胞分布在离散的一维、二 维、或者多维空间的阵列上。一个细胞单元实际上是一种存储类型， 用来存储状态。在本文中，主要研究细胞自动机在密码学中的应用，采 用二进制编码，所以实际每个细胞所存储的状态只有0 和1 两种。 ( 2 ) 细胞空间 1 ) 细胞空间的几何划分：细胞自动机可以存在于不同维数的空间中， 如一维细胞自动机是由初始时刻处于某种状态的细胞随时间步序的移 动生长发育而成的，在一维情况下其生成空间是一条无限伸展的离散 1 0 西安理工大学硕士擘住论文 网格组成的条带，细胞单元等间距地分布在一条直线上；二维细胞自 动机是由平面网格细胞阵列随时间步序的推移而不断演化、生长而成， 细胞在二维平面上以连续方形格子、等边三角型、六边形蜂房形式或 其它形式排列。三维细胞自动机是由细胞相互连接形成一个立体空间 结构。 2 ) 边界条件：理论上细胞自动机中细胞单元的个数是无限的，细胞空 间通常在各维向上是无限延展的，这有利于细胞自动机在理论上推理和 研究。但是在实际应用过程中，由于细胞单元的数目是有限的，需要考 虑边界条件。在实际运算中，常用的边界方法有三种类型：周期型、反 射型和定值型。有时，在应用中，为更加客观模拟系统，还可以采用随 机型，即在边界实时产生随机值。 周期型：是指相对边界连接起来的细胞空间。对于一维空间，细 胞空间表现为一个首尾相接的环。在二维空间上下连接，左右连接。形 成个拓扑圆环面。周期型边界条件与无限空间最为接近，因此在应用 研究时多采用此种方法。 反射型：指在边界处邻居的细胞状态是以边界为轴的镜面反射。 如在一维细胞自动机当中，当r = 1 时，其反射型邻域如图所示： f - 1o 0 lo 圈2 - i 反射型边界不惹圈 定值型：所有边界处细胞取某一固定常量，如o o ，l 等。 在实际的应用中，这几种类型可以相互结合。如在二维空间中， 上下边界可以采用反射型，左右边界可采用周期型等。 3 ) 邻域：邻域指与一个给定细胞相互影响的细胞集合。在细胞阵列中， 邻域通常是在物理位置上与指定细胞最近的细胞。在本课题中，以半径 来确定邻居，与中心细胞距离小于等于半径的细胞均在该细胞邻域范围 细胞自动机 内。一维细胞自动机中，所有细胞单元等问距的分布在直线上，邻域结 构也比较简单。目前对细胞自动机的研究主要停留在一维c a 上，但是 由于一维细胞自动机结构的限制，其变换规则也比较简单，在密码学中 的应用存在安全问题。二维细胞自动机的细胞阵列以及邻域结构都比一 维复杂，更适合于密码学中的应用，所以本文主要对二维细胞自动机做 相关的研究。 二维细胞自动机的邻域定义通常有三种类型： 冯一诺依曼( y o n n e u m a n n ) 型 一个细胞的上、下、左、右相邻四个细胞为该细胞的邻居。其结构 示意图如下： 圈2 - 2 冯一诺依曼型邻域结构 其中，以x 。表示中心细胞，其邻居细胞是上、下、左、右四个方 向上的x 。j ，x 。x + ，和x 。此时，邻居半径r 为1 。其邻居定义 为： n = ( v i = ( v t ，v i ，) llv 。，一v 。l + l v iy - v 。，l i ，( v 。，v 。，) z 2 lv ；。，v t ，表 示邻居细胞的行列坐标值，v 。，v 。表示中心细胞的行列坐标值。 摩尔( m o o r e ) 型 一个细胞的上、下、左、右、左上、右上、右下、左下相邻八个细 胞为该细胞的邻居。邻居半径r 同样为1 ，相当于图像处理中的八邻域、 八方向，结构示意图为： 西安理工大学硕士学位论文 图2 - 3 摩尔型邻域结构 其邻居定义如下： n 。，。= f v ：( v ，；，v ，) f v ix - v 。1 ，iv 。，一v 。j l ，( v ，v 。，) z 2 v v v 。v 。，意义同前。 将以上的邻居半径r 扩展为2 或者更大，即得到扩展的摩尔型邻居。 其数学定义可以表示为： n r 。o r e = v j = ( v 。，v 。，) 1 v ix - v 。l r ，lv ly - - v 。，i r ，( v 。v 。，) z 2 ) ( 3 ) 规则 根据细胞当前状态及其邻居状态确定下时刻该细胞状态的状态转 移函数称为局部变换规则。局部交换规则主要反映近距离内格点间或细 胞间的相互作用即局域作用。按照这种规则，细胞在某瞬时的状态取决 于该细胞和邻域细胞在前一时刻的取值。依照不同的邻域类型，规则数 是不相同的，而且随着邻域半径的扩大，变换规则成指数形式增长。若 每个细胞有k 种可能状态取值，且邻域范围内有n 个细胞单元，则有k “ 条规则。对k = 2 ，n = 5 的v o nn e u m a n n 邻域有2 3 2 种规则；对n = 8 的m o o r e 邻域约有2 2 “种规则，因此细胞自动机是由简单规则出发探索复杂系统多 样性的有力工具。 除规定演化规则以外，还要赋予细胞自动机一个初始构型。初始构 型好似种子，细胞自动机的状态演化就是根据规则不断地更新来描绘种 细胞自动机 子后代的变化情况。从信息论观点来说，初始构型相当信息输入，细胞 自动机相当一台并行信息处理的计算机。 2 3 细胞自动机的特性 根据细胞自动机的构成及其规则分析，细胞自动机具有以下几个特 点： ( 1 ) 高度离散性：细胞自动机是一种时间和空间都离散化的数学模型， 其时间轴、空间变量和描述组成系统的基本元素一细胞的状态变量都是 离散的。细胞单元具有有限的状态并且排列成一个有规则的阵列结构。 这一特性极大地简化了计算和处理过程，但在总体上仍然很好地表现出 复杂的物理过程。一般计算机离散数值方法来自于连续微分方程的离散 化，在计算过程中存在截断误差，而细胞自动机是直接从物理系统中建 立起来的离散模型，因而不同于一般计算机离散数值方法，在无数次的 迭代过程中没有误差积累，这一点是计算机常规计算方法完全无法做到 的。 ( 2 ) 状态演化的同步性：细胞自动机每一个细胞的状态以统一确定的 规则演化，在宏观上是同步的。微观上，在通用计算机上对整个细胞自 动机的细胞逐个进行模拟计算，可以发现，细胞自动机的计算具有空间 和时间上的一致性，在宏观上其状态演化是同步的。 ( 3 ) 相互作用的局部性：细胞自动机细胞的状态根据一个局域作用规 则而被更新，具体地讲，在t + 1 时刻的细胞状态根据t 时刻它自己的状 态和其邻域细胞的状态而改变。因此，细胞自动机的演化规则是局部的， 而其表现出来的动力学演化行为是全局的。 正是基于细胞自动机高度离散性，通过简单的局域相互作用而在宏 观上表现出的高度复杂性，使之非常适合于在密码学中的应用。 1 4 西安理工大学硕士学位论文 2 4 细胞自动机的分类 细胞自动机有多种，从其细胞单元的组成结构是否随其状态迭代而 变化可分为确定性细胞自动机和可编程细胞自动机，而确定性细胞自动 机根据其组成结构又可分为单一细胞自动机和混合细胞自动机。 定义2 4 1 ：称细胞自动机的邻域函数规则不随其状态迭代变化的细 胞自动机为确定性细胞自动机。 定义2 4 2 ：称所有细胞单元使用相同邻域函数规则的细胞自动机为 单一细胞自动机。单一细胞自动机具有组成单元结构的简单规则性、单 元之间作用的局部互连性和信息处理的高度并行性等特点。 定义2 4 3 ：称由两种或两种以上的邻域函数规则组成的细胞自动机 为混合细胞自动机。混合细胞自动机不仅具有单一细胞自动机所具有的 组成单元结构的简单规则性、单元之间作用的局部互连性和信息处理的 高度并行性等特点，而且由于其组成规则的多样性而带来了细胞自动机 的多样性，实际应用的细胞自动机一般均为混合细胞自动机。 定义2 4 4 ：称邻域函数规则随状态迭代而变化的细胞自动机为可编 程细胞自动机。可编程细胞自动机在确定性细胞自动机的基础上增加复 杂性的同时可以获得结构可变的细胞自动机，具有比确定性细胞自动机 更多的种类、更复杂的特性和更灵活的选择。 定义2 4 5 ：如果一个细胞自动机中所有细胞单元使用的规则均由 x o r ( 异或运算) 和n x o r ( 同或运算) 实现，这种细胞自动机被称为加性细胞 自动机，否则为非加性细胞自动机。 定义2 4 6 ：称任意两个全局状态s 。和s 。均满足线性可加性 f ( s 。+ s 。) = f ( s 。) + f ( s ) 的细胞自动机为线性细胞自动机，否则为非线性细 胞自动机。线性细胞自动机中所有细胞单元使用的邻域函数规则只由异 或运算x o r 组成。 细胞自动机 2 5 对基本细胞自动机的研究探索 一般将d = 1 ，z = f 0 ，i ，邻域半径r = l 的一维二值三邻域c a 称为基本 细胞自动机，也是研究复杂细胞自动机的基础。在基本细胞自动机中， 细胞单元i 在t + l 时刻的状态可表示为s 。”1 = f ( s 。，s 。，s 。) 。领域状 态 s 。，s 。，s 。+ 。) 有0 0 0 l l l 共8 种取值，当变换规则确定后，每种邻 域状态都对应一个确定的输出值，也就是中心细胞在下一时刻的状态值。 例如以下规则： ： l 输入 l l l1 1 0i 0 11 0 00 1 10 1 00 0 10 0 0 l 输出 0l00l100 将其输出值用一个十进制数表示，如以上的0 1 0 0 1 1 0 0 对应的十进制数为 1 6 3 ，即表示该c a 采用的规则号为1 6 3 。因此，对于一维二值三邻域c a ， 则有2 5 6 种规则。对于t 时刻序列1 0 1 1 1 1 i 0 1 0 1 0 1 1 1 0 0 0 1 0 ，如果采用上 面的1 6 3 规则，则在t + l 时刻，输出序列为1 0 i 0 0 0 i 0 1 0 1 0 1 0 1 0 0 0 1 。 s w o l f r a m 对这2 5 6 种演化规则一一进行了详细而深入的研究“”。通过反 复测试可以发现所有2 5 6 种细胞自动机可以分为三类：固定值、周期循 环、混沌。在此列出典型的几个规则加以分析。 2 2 4 规则：经过一定时间，细胞自动机最终达到全0 的稳定状态，再 不发生变化。2 0 8 规则；经过若干个时间周期后，细胞自动机又咀复到了 原来的状态，因而采用2 0 8 规则的细胞自动机是循环的。将两个相同状 态之间经历的最小时间步长称为细胞自动机的周期。而1 5 0 规则和1 5 1 规则经过足够长时间演化后，即不能达到稳定状态，也没有固定的周期， 处于一种混乱的、无序的状态，我们将此称为混沌状态。在密码学中， 固定的细胞自动机没有价值，在此，我所做的研究主要是基于循环细胞 自动机和混沌细胞自动机。虽然细胞自动机结构简单，但能够表现出高 度复杂的全局特性，正是基于简单的结构设计，才有利于v l s i 的实现。 在基本细胞自动机中，一般用邻域函数规则的组合即规则号来表示细 1 6 西安理工大学硕士学位论文 胞自动机，例如( 6 3 ，1 5 2 ，2 2 4 ，9 0 ) 则表示该细胞自动机第一个细胞单 元采用6 3 规则，第二个单元采用1 5 2 规则，第三、第四细胞单元分别采用 2 2 4 和9 0 规则。例如规则9 0 和1 5 0 可用逻辑式表示为s t t * i = s i i t + a 。s 。+ s m 。， 其中当a i _ o 时表示趣则9 0 ，当a l = l 时表示规则1 5 0 。所以可以使用一个 n 维向量( a o ，a i ，- 一，a 。) 来表示9 0 1 5 0 线性细胞自动机的规则组成，并 称之为9 0 1 5 0 细胞自动机的规则向量，如规则( 1 5 0 ，9 0 ，1 5 0 ，9 0 ，1 5 0 ) 细 胞自动机可以使用规则向量( 1 ，0 ，1 ，0 ，1 ) 来表示，并称之为( 1 ，0 ，1 ，0 ，1 ) 9 0 1 5 0 线性细胞自动机。 2 6 本章小结 本章主要介绍细胞自动机定义和基本知识。第一节介绍了细胞自动机 的相关定义：在第二节，对细胞自动机的构成进行了详细论述，主要介 绍了细胞自动机的邻域结构，在第三节描述了细胞自动机的特性，第四 节介绍了细胞自动机的分类及相关定义，最后是对一维二值三邻域基本 细胞自动机进行研究，为后面的研究内容奠定基础。 1 7 西安理工大学硕士学位论文 3 序列密码 细胞自动机在密码学中的应用始于以细胞自动机产生的伪随机序列 作为序列密码，其目前主要应用也主要集中在序列密码当中，所以在研 究基于细胞自动机的密钥流构造方法和伪随机序列之前，有必要对序列 密码的相关知识作以介绍。 3 1 序列密码简介 根据密码算法对明文信息的加密方式，可分为序列密码体制和分组密 码体制，序列密码是密码体制中的一种重要体制。序列密码主要原理是 通过有限状态机产生性能优良的随机序列作为序列密钥，使用该序列流 逐比特加密信息得到密文序列。 设明文流为：m = m m 。m 。 密钥流为：k = k 。k ：k 则加密算法为：c = c ，c 。c = 巳，( m 。) e k 。( i l l 。) e k ，( ；) 解密算法为：m = m 。r f i ：m = d k 。( c 。) d 。( c ：) d 。，( c ，) 一 在序列密码中，加密变换常采用二元加法运算，即 c t = i n iok i ，m 。= c 。ok i ， 图3 1 是一个二元加法序列密码系统的模型。其中k 。为密钥序列生 成器的初始密钥。为了密钥管理的方便，k 。一般较短，它的作用是控制 密钥序列生成器生成长的密钥流序列k = k l ，k 2 ，。 复的明文序列 序列密码 在以上系统中，如果非法接收者知道了k 。也就知道了m ，因此密码 系统的安全性取决于密钥流的性能。 序列密码由于运算速度快，密文传输中的错误不会在明文中产生扩 散，而且由于序列密码历史悠久，理论体系完善，仍然是目前国际密码 应用的主流。序列密码的另一个优点是无错误传播，一个传输错误只影 响一个符号，不会影响后继符号。但这也是一个缺点，因为对手篡改一 个符号比篡改一组符号容易，在实际系统中可以通过附加非线性检错码 来克服这个缺陷。 序列密码在实施过程中，利用少量的密钥通过复杂的密码运算产生 大量的伪随机位流，用以还原明文位流。在序列密码体制中，只要发送 端和接收端有相同的种子或实际密钥和内部状态，就能产生出相同的密 钥流。此时，发送端和接收端的密钥生成器是同步的。但是一旦密钥产 生器失步，解密就不可能实现，而必须提供重建同步的手段。 3 2 序列密码相关理论 3 2 1 相关定义 定义3 1 ：对序列s ”，如果存在正整数n ，使得 s 。+ 。= s 。，i = o ，1 ，2 ， 则称该序列s 为周期序列，满足的最小正整数n 称为s 。的周期。 定义3 2 ：如果组合函数z = f ( x ；，埯，) ( n ) 对输入变量中任意n 1 个变量都具有独立性，我们就称该函数具有m 阶相关免疫性。可以从 ( x 。，x ：，x 。) 中任意选取1 1 1 个变量( x ，x 。，x 。) ，这里 i i t i ： i 1 0 0 0 时一维c a 才是安全的。鉴于一维c a 的安全性问题， 目前都把目光转向二维c a 。这一章主要是基于x o r 和n x o r 运算的加性自 动机，利用二维冯一诺依曼邻域结构的细胞自动机，研究最大周期细胞自 动机的构造方法，并利用所构造的最大周期细胞自动机研究密钥流发生 方法。 4 1 基本细胞自动机的周期研究 c a 的重要特征是细胞单元的局部作用引起复杂的全局变化。以基本 细胞自动机为例，c a 在t 时刻的所有变换函