（计算机软件与理论专业论文）基于元胞自动机的公钥密码体制研究.pdf

硕士论文基于元胞自动机的公钥密码体制研究 摘要 随着i n t e r a e t 的发展，信息安全问题越来越受到人们的重视。加密算法是信息安 全领域的一项关键技术，因而许多专家、学者都在积极地研究更加安全、可靠的加密 算法。 本文在研究元胞自动机的理论和分析现有加密算法的基础上，提出了一种基于元 胞自动机的公钥加密算法。该算法把四个一维可逆元胞自动机作为私钥，而把由这四 个一维可逆元胞自动机通过运算构造出的一个m o o r e 型二维元胞自动机作为公钥。 本文通过理论分析，证实了该算法的正确性和可行性算法的仿真实验表明，该算法 能够较好地完成公钥加密体制中的加密、解密过程，是一个较有发展前途的公钥加密 算法，具有实用价值。在该算法的基础上，采用耦合元胞自动机的理论，本文又提出 了一种基于耦合元胞自动机理论的公钥加密的算法，这种算法可以极大地增加密钥空 问，有效地抵御蛮力攻击 最后，通过分析本文提出的基于元胞自动机的公钥加密算法的特点，本文指出了 该算法应该通过硬件方式来实现，适合在网络环境中来使用。 关键词：信息安全，密码学，元胞自动机，公钥加密 硕士论文基于元胞自动机的公钥密码体制研究 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t ，i n f o r m a t i o ns e c u r i t yh a sb e c a m em o r e a n dm o r ei m p o r t a n t e n c r y p t i o na l g o r i t h m sa r eo n eo ft h em o s tc r i t i c a l t e c h n o l o g i e so fi n f o r m a t i o ns e c u r i t y m a n ye x p e r t sa n ds c h o l a r sa r et r y i n g t h e i rb e s tt os t u d ys a f e ra n dm o r eu s e f u le n c r y p t i o na l g o r i t h m s o nt h eb a s eo fs t u d y i n gt h et h e o r i e so fc e l l u l a ra u t o m a t aa n da n a l y s i n g o t h e re n c r y p t i o na l g o r i t h m s ，t h i sp a p e rp u t sf o r w a r dan e wp u b l i c k e y a l g o r i t h m ，w i t c hu s et h et h e o r i e so fc e l l u l a ra u t o m a t a t h i sa l g o r i t h mu s e s f o u ro n e d i m e n s i o nr e v e r s i b l ec e l l u l a ra u t o m a t a st ob u i l dam o o r e n e i g h b o r h o o dt w o - d i m e n s i o nc e l l u l a ra u t o m a t a t h et w o - d i m e n s i o nc e l l u l a r a u t o m a t ai sap u b l i c - k e ya n dt h ef o u ro n e - d i m e n s i o nr e v e r s i b l e c e l l u l a r a u t o m a t a sb e c o m eas e c r e t - k e y t h i sp a p e r p r o v e st h a t t h i sa l g o r i t h mi s c o r r e c ta n df e a s i b l eb yt h ew a yo fa n a l y s i n gt h et h e o r y t h es i m u l a t i o n p r o g r a m m eo ft h ea l g o r i t h ms h o w st h a tt h ea l g o r i t h mc a nf i n i s ht h ep r o c e s s o fe n c r y p t i o na n dd e c r y p t i o ni nt h ep u b l i c k e yf r a m e w o r k i ta l s os h o w st h a t t h i s a l g o r i t h mi s ap r o m i s i n gp u b l i c - k e y e n c r y p t i o na l g o r i t h ma n dt h e a l g o r i t h mm a yb ev e r yu s e f u l o nt h eb a s eo ft h i sa l g o r i t h m ，t h i sp a p e rp u t s f o r w a r da n o t h e rp u b l i c - k e ya l g o r i t h mb a s e do nc o u p l i n gc e l l u l a ra u t o m a t a t h i sa l g o r i t h mc a ni n c r e a s ek e y - s p a c ea n dg e tb e t t e rr e s u l t a tl a s t 。a f t e ra n a l y s i n gt h ep r o p e r t i e so ft h ea l g o r i t h m , t h i sp a p e r p o i n t so u tt h a tt h ea l g o r i t h mh a st ob ei m p l e m e n t e db yh a t d w a r ea n di tn e e d s t ob eu s e di nt h ei n t e r n e tc i r c u m s t a n c e k e y w o r d s ：i n f o r m a t i o ns e c u r i t y ，c r y p t o g r a p h y ，c e l l u l a ra u t o m a t a ， p u b l i c k e ye n c r y p t i o n 硕士论文基于元胞自动机的公钥密码体制研究 图目录 图2 1 3 1 一维元胞自动机及其邻居7 图2 1 3 2 二维元胞自动机及其邻居7 图2 1 4 1 采用循环边界的一维元胞自动机8 图2 1 4 2 采用映射边界的一维元胞自动机8 图2 2 4 3 采用固定边界的一维元胞自动机8 图2 2 2 18 5 号元胞自动机的d eb r u i j n 表示法1 0 图2 4 1 1 生命游戏演化图( w i n l i f t 软件产生) 1 4 图2 4 3 1 格子气自动机规则1 5 图3 1 1 可逆元胞自动机的演化图1 8 图3 1 2 11 7 0 号和2 4 0 号c a 作用后的结果2 0 图3 2 1 1 公钥加密解密示意图2 2 图3 3 1 14 状态、i 2 半径元胞自动机示意图2 5 图3 3 1 24 状态、l 2 半径c a 状态转换图1 2 6 图3 3 1 34 状态、i 2 半径c a 状态转换图2 2 6 图3 3 2 1 运算前的初始配置2 7 图3 3 2 2 经过c a l 纵向、c a 2 横向运算后的结果2 7 图3 4 1 1 九重循环设定m o o r e 型二维元胞自动机初始状态3 0 图3 4 1 2 一维元胞各个方向计算示意图3 0 图3 4 1 3 使用不同方向的一维c a 计算时，需要计算的元胞的位置3 l 图3 4 1 4 一个二维元胞自动机的初始状态3 2 图3 4 1 5 通过南边变换一维元胞自动机计算后的结果3 2 图3 4 1 6 通过西边变换一维元胞自动机计算后的结果3 3 图3 4 1 7 通过北边变换一维元胞自动机计算后的结果3 3 图3 4 1 8 通过东边变换一维元胞自动机计算后的结果3 3 图3 4 2 1 使用二维元胞自动机加密的过程3 4 图3 4 2 2 使用一维元胞自动机第一次解密的过程3 5 图3 4 2 3 基于元胞自动机的公钥加密算法用二维c a 加密示意框图3 6 图3 4 2 4 基于元胞自动机的公钥加密算法用一维c a 解密示意框图3 6 图3 4 3 1 根据一维c a 构建二维元胞自动机的伪代码3 7 图3 4 3 2 用二维元胞自动机进行加密的伪代码3 8 图3 4 3 3 用一维元胞自动机进行一次解密的伪代码3 8 图3 4 4 1 元胞自动机加密解密时序电路示意图3 9 图3 5 1 1 仿真实验使用公钥加密4 0 图3 5 1 2 仿真实验使用一维私钥进行第一轮解密4 2 图3 5 1 3 仿真实验使用一维私钥进行第二轮解密4 3 图3 5 1 4 仿真实验使用一维私钥进行第三轮解密4 3 图3 5 1 5 仿真实验使用一维私钥进行第四轮解密4 4 图3 5 2 1c a 公钥加密算法加密图片效果图( 放大) 4 5 图3 6 1 1 耦合元胞自动机计算示意图4 5 v 硕士论文基于元胞自动机的公钥密码体制研究 图3 6 2 1 元胞自动机耦合加密系统加密过程示意图4 6 图3 6 2 2 元胞自动机耦合加密系统解密过程示意图4 6 图4 1 1 穷举法搜索初等元胞自动机的可逆规则4 9 图5 2 1 元胞自动机公钥加密在网络环境中的使用5 2 表目录 表2 2 1 18 5 号元胞自动机的w o l f r a m 表示法9 表2 3 1 1 各类一维元胞自动机( k 、r ) 所占比例1 l 表3 1 2 15 l 号和2 0 4 号c a 的规则转换表2 0 表3 3 1 1 一个4 状态、1 2 半径的一维可逆元胞自动机的状态转换表2 5 表3 4 1 1 选定的四个一维可逆元胞自动机3 2 表3 5 1 1 仿真实验用到的二维元胞自动机的所有规则4 l v i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：围起2 扣e 年6 月压日 学位论文使用授权声明 南京理i 大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：图垦 硝6 年月z o 日 硕士论文 基于元胞自动机的公钥密码体制研究 1 1 研究背景及意义 1 绪论 密码学的发展有悠久的历史，最早可以追溯到古代埃及人简单而有限地使用密码 学。第一次世界大战之前，密码学重要的进展很少出现在公开文献中，但该领域却和 其它专业学科一样向前发展着。1 9 1 8 年，美国加州的e d w a r dh h e b e m 申请了第一 个转轮机专利，这种装置在差不多在5 0 年里一直被指定为美军的主要密码设备【l 】。 随着当今i n t e m e t 的快速发展，信息安全任务越来越紧迫，而信息安全的首要保 证是有一个高效、可靠的加密系统，这个系统的核心是一个或多个能够快速运算而在 多项式时间内无法攻破的算法世界各国的不少专家、学者都在做这方面的工作，他 们尝试使用各种方法来构造加密算法，以便研究出符合本国国情，具有自己知识产权 和高度保密性的加密系统。 随着密码学的发展，加密算法主要有两大类：秘密密钥算法和公开密钥算法。简 单来说，密码密钥算法加密和解密使用的是相同的密钥，此时密钥的保密工作是一项 非常重要的工作；而公开密钥算法的加密密钥和解密密钥是不同的，并且从加密密钥 几乎无法的到解密密钥。 本文主要是运用元胞自动机的思想来研究其在公钥密码体制的应用。元胞自动机 从产生至今，研究取得了不少进步，在各个领域的应用也初见端倪。元胞自动机在密 码学中的应用较多，主要有对称加密和随机数产生等。但是，它在公钥密码体制方面 的研究相对滞后，这也与公钥密码体制的特点有关。在这里，我们尝试根据公钥密码 体制的特点，结合元胞自动机的思想，设计出一个具有一定实用意义的公钥加密算法。 1 2 国内外研究现状 在计算机出现前，密码学由基于字符的密码算法构成。不同的密码算法是字符之 间相互代替或者相互换位，好的密码算法是结合这两种方法，每次进行多次运算。计 算机密码算法有多种，最常用的有以下三种【l 】： d e s ( d a t ae n c r y p t i o ns t a n d a r d ，数据加密标准) 是最通用的计算机加密算法。 d e s 是美国和国际标准，它是对称算法，加密和解密的密钥是相同的。 r s a ( 根据它的发明者命名，r i v e s t ，s h a m i r 和a d l e m a n ) 是最流行的公开 密钥算法，它能用作加密和数字签名。 d s a ( d i g i t a ls i g n a t u r e a l g o r i t h m ，数字签名算法) 是另一种公开密钥算法， 它不能用作加密，只用作数字签名 硕士论文基于元胞自动机的公钥密码体制研究 本文主要基于元胞自动机的理论提出一个具有实用价值的公钥加密算法。元胞自 动机在密码学方面应用的研究时间相对较长，取得的成果也相对比较丰富。 元胞自动机在密码学方面的应用主要集中在两个方面：产生伪随机数和对称加 密。w o l f r a m 最早使用了3 0 号元胞自动机进行生成伪随机数的研究f 2 】。f r a n c i s z e k s c r c d y n s k i t m 和m a c r ot o m m a s s i n i 4 都进行过用元胞自动机产生伪随机数并进行对称 加密方面的研究。国内方面，张传武等人研究使用可编程元胞自动机产生伪随机序列 嘲；赵学龙使用触发元胞自动机结合耦合的方法研究过对称加密嘲。但是，元胞自动 机在公钥加密方面的尝试相对就少得多。g u a n 、g u t o w i t z 在这方面有过研究川嘲。 g u a n 使用了混合元胞自动机，依赖了它们的特殊性质，采用前向迭代的方式来 加密，而使用另一个元胞自动机前向迭代的方式来解密。作为加密密钥的元胞自动机 需要很好地选择，而且用来加密的元胞自动机的半径不能太大。 i 3 本文所做的工作 在分析先前学者研究工作的基础上，在元胞自动机公钥加密方面，本文的主要工 作成果和创新点如下： 1 结合仿真实验，分析了一维、2 状态、邻居半径为1 、采用循环边界的元胞自 动机可逆的内在原因。这类元胞自动机总数不多，可以采用穷举的方法列举出它们中 的所有存在的可逆元胞自动机对本文对这几对可逆元胞自动机可逆原因一一作了分 析。 2 提出了一种基于元胞自动机的公钥加密算法。本文使用四个一维、4 状态、 1 2 半径、采用循环边界的可逆元胞自动机，按照本文的算法构造了一个m o o r e 型二 维元胞自动机。本文把这个m o o r e 型二维元胞自动机作为公钥，把构造这个m o o r e 型二维元胞自动机的四个一维可逆元胞自动机作为私钥。本文证明了这种算法的正确 性和可行性。 3 在上面公钥加密算法的基础上，采用耦合元胞自动机的理论，本文又提出了 基于耦合元胞自动机的公钥加密算法。通过耦合的方法，可以使本文构造的基于元胞 自动机的公钥加密算法大大地增加密钥空间，有效地抵御蛮力攻击 2 硕士论文基于元胞自动机的公钥密码体制研究 4 设计了穷举搜索算法来搜索一维可逆元胞自动机。本文构造了两个搜索一维 可逆元胞自动机的算法：一个是用来搜索初等元胞自动机中的可逆元胞自动机对的穷 举算法；另一个是用来搜索多状态，1 2 半径、一维可逆元胞自动机的穷举搜索算法， 该算法是基于m o r a 等人提出的一个算法的基础上的，可v a s t 有效地搜索这类元胞自 动机中的可逆元胞自动机对。 5 通过分析本文构造的基于元胞自动机的公钥加密算法的特点，本文指出了该 算法适宜通过硬件方式来实现，适合在通过网络环境使用。 1 4 本文结构及内容 本文的工作重点是基于元胞自动机提出一种构造公钥加密的算法，其它的工作都 是围绕该算法来进行的。本文的结构如下： 第一章是绪论部分，介绍了研究背景及意义，国内外的研究现状，本文所做的工 作，以及本文的结构及内容。 第二章介绍了元胞自动机的基本理论。主要介绍了元胞自动机的定义、表示、分 类以及应用。 第三章介绍了基于元胞自动机的公钥加密系统。首先介绍了可逆元胞自动机的一 些知识和元胞自动机公钥加密的思想；接着证明了本文构造的公钥加密算法的正确 性：然后通过各种方式设计了基于元胞自动机的公钥加密算法并通过程序进行实验仿 真：最后根据耦合元胞自动机的理论介绍了基于耦合元胞自动机的公钥加密系统。 第四章介绍了通过穷举法搜索特定类型的可逆元胞自动机。 第五章简要地介绍了本文构造的公钥加密算法的使用方法。 本文结论部分对本文所做的工作进行了总结，并从实用的角度出发，提出了今后 的工作方向。 3 硕士论文基于元胞自动机的公钥密码体制研究 2 元胞自动机的基本理论 元胞自动机( c e l l u l a ra u t o m a t a , 简称c a ) 是最近一个比较热门的研究课题， 它是物理、数学、计算机和生物等学科的交叉产物。在计算机领域中，元胞自动机在 人工智能、计算复杂性分析以及加密等多个领域中有着较大的用途。 早期元胞自动机的发展应归功于现代计算机之父j v o nn c u m a n n ，但其思想起 源于s t a n i s l a wu l a m 。1 9 4 8 年，j v o nn e u m a n n 在研究“什么逻辑组织结构的自动 机具有通用图灵机一样的自我复制特性”的问题时，在s t a n i s l a w u l a m 的建议下，j v o n n c u m a n n 采用具有2 9 个状态的二维细胞空间即自动机建立了一个具有自我复制特性 和通用计算能力的元胞自动机【9 】。 简单来说，元胞自动机是一种特殊的有限状态机，具有时间、空间和状态的离散 性。构成元胞自动机的基本单位是元胞( c e l l u l a r ) ，有规律的分布在元胞空间 ( s p a t i a ll a t t i c e ) 的格点上，且各自的状态随着时间按照一定的局部规则变化。 也就是说，元胞的状态只能从一个有限的状态集中取值，每个时刻元胞的状态仅与其 自身和邻居在上一时刻的状态有关，并且，所有的元胞在每个时刻均是同时更新的。 典型的元胞自动机具有以下的一些特征【l o 】： 一、离散性：元胞自动机中的每一个元胞在时间、空间和状态上都是离散分 布的，其边界在理论上可以是无限的： 二、厨质性：元胞自动机内的每个元胞的分布方式是相同的，并且它们的变 化都服从相同的一组状态规则； 三、局部性：元胞自动机中每个元胞的状态转换只和它的邻居有关； 四、并行性：元胞自动机中的每个元胞的状态更新都是同步进行的。 元胞自动机虽然起源于2 0 世纪4 0 年代，但直到2 0 世纪8 0 年代中期才由于 s w o l f r a m 的简化才得以重视。早期的元胞自动机研究主要集中于理论方面，并且 由于早期元胞自动机结构的复杂性而限制了其应用【l ”。2 0 世纪8 0 年初，s w o l f r a m 提出对元胞自动机进行简化，他建议简化元胞自动机的状态空间和领域半径，以获得 具有组成单元结构的简单规则性、单元之间作用的局部互连性和信息处理的高度并行 性等优点的元胞自动机，并提出了具有两个状态、领域半径为一的初等元胞自动机 ( e l e m e n t a r yc e l l u l a ra u t o n m t a ，简称e c a ) 。s w o l f r a m 对元胞自动机的简化极大 推动了元胞自动机理论及其应用研究【“j 。 通过世界各地学者的努力，元胞自动机的理论得到了很大的发展。有不少研究模 型是基于元胞自动机的理论被提出来的。这些模型针对了那些很难用先前的理论解决 的问题，比如城市的演化，肿瘤的生长，森林的变化等等；也有很多基于元胞自动机 4 硕士论文基于元胞自动机的公钥密码体制研究 的实用的算法已经被研究出来。在信息科学领域特别是加密方面，元胞自动机的发展 非常迅速，已经有了不少基于一维元胞自动机的加密算法和伪随机数序列生成算法的 实现，但是基于元胞自动机的非对称加密算法的发展相对滞后。从目前来看，单独的 元胞自动机完成的算法还不完全理想，更好的结果是与当前密码技术相结合。我们有 理由相信，元胞自动机在密码学中的应用研究具有光明的前景。当前，最前沿的研究 是基于二维元胞自动机的，与一维元胞自动机相比，它具有更大的复杂性。 2 1 元胞自动机的定义 元胞自动机自j r o l l n e u m m m 提出并由s w o l f f - a m 简化以来，其概念、结构和 应用都发生了较大的变化。元胞自动机有多种，从元胞自动机的组成结构来看可以分 为单一元胞自动机和混合元胞自动机。 2 1 i 数学定义 下面首先从数学的角度一般性地介绍一下元胞自动机，然后分别介绍一些特定元 胞自动机的概念。 定义1 ：元胞自动机是一个四元组，用数学公式表达就是：c a = ( a 0 ，z 。厶n ， b ) 【1 3 】，其中包括： ( 1 ) 空问结构k = n z - = i = ( i ”，i * o i i 。e z ，i * - z 1 - o 是由d 维细胞单元构成的空间结构，其中兀毛= 气z 为集合 z ，。的笛卡儿积( c a r t e s i a np r o d u c t ) ，z 札= o ，1 ，n t - i ) 为模n j 的整数集，i - - - - i o ”。i ，。 为细胞单元的空间地址索引值； ( 2 ) 状态空间五：元胞自动机中细胞单元i 的状态取值范围。一般为具有q 个元素的有限交换环乞= 0 ，1 ，q - 1 ) ，状态赋值函数确定了t 时刻元胞自动 机中第i 个细胞单元与状态空间乞之间的映射关系； ( 3 ) 领域函数规则正，、：称由元胞自动机的领域半径r = ，0 ，山) 确定的第i 个细胞单元的状态配置为元胞自动机的领域函数规则z 。； ( 4 ) 边界条件b ：边界条件确定了某个细胞单元i = f o ，f 。 领域半 径之内的领域单元在超出元胞自动机空间结构时的处理方法，它包括映射边界条件 ( m a p p e db o u n d a r y ) 、固定边界条件( f i x e db o u n d a r y ) 和循环边界条件( p e r i o d i c b o u n d a r y ) 。其中，固定边界是指在元胞自动机中，将细胞单元i = i o ，l d - 的邻域状态配置中超出元胞自动机空间z n o 2 k 。的细胞单元的状态看为元 5 硕士论文基于元胞自动机的公钥密码体制研究 胞自动机状态空间z 上的一个固定状态。 上面定义的元胞自动机中，最简单的是d = 1 ，q ：2 ，r = 1 的初等元胞自动机 ( e l e m e n t a r yc e l l u l a ra u t o m a t a ，简称e c a ) 定义2 ：称所有细胞单元使用相同领域函数规则的元胞自动机为单一元胞自 动机或规则元胞自动机( u n i f o r mc e l l u l a ra u t o m a t a ，简称u c a ) n 钔。 定义3 ：称由两种或两种以上的领域函数规则组成的元胞自动机为混合细胞 自动机( h y b r i dc e l l u l a ra u t o m a t a ，简称h c a ) 旧。 混合元胞自动机不仅具有单一元胞自动机所具有的组成单元结构的简单规则性、 单元之间作用的局部互连性和信息处理的高度并行性等特点，而且由于其组成规则的 多样性而带来了元胞自动机的多样性。实际应用的元胞自动机一般均为混合元胞自动 机【1 3 1 。如使用( 1 0 2 ，9 0 ，2 0 4 ，1 5 0 ，6 0 ) 元胞自动机表示第0 个单元为规则6 0 ，第 1 个单元为规则1 5 0 ，第4 个单元为规则1 0 2 的5 单元确定混合元胞自动机，并 称其各细胞单元的规则号即领域函数规则的组合( 1 0 2 ，9 0 ，2 0 4 ，1 5 0 ，6 0 ) 为该元胞自动 机的规则向量。 下面按各个知识点更为详细地介绍元胞自动机的概念。 2 1 2 元胞及状态 元胞又可称为单元或基元，是元胞自动机的最基本的组成部分。元胞分布在离散 的一维、二维或多维欧几里德空间的晶格点上【l 6 】。 状态可以是( 0 ，1 的二进制形式，或是 s 。s 。，s j 整数形式的离散集。严格 意义上，元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了 扩展。例如每个元胞可以拥有多个状态变量。目前研究最多的是以0 、1 为状态集的 元胞自动机，因为这种元胞自动机比较简单，只有两种状态，可以直接和计算机中的 表示数字0 、1 的两种状态对应起来这样，基于这种元胞自动机的理论可以很方便 的用计算机来模拟。当然，这种元胞自动机用硬件来实现也是非常方便的。 2 1 3 元胞邻居 元胞自动机中的元胞是分布在元胞空间上的。元胞所分布的空间网点集合 就组成了的元胞空间理论上，它可以是任意维数的欧几里德空间规则划分。目前研 究多集中在一维和二维元胞自动机上。对于一维元抱自动机，元胞空间的划分只有一 种；而高维的元胞自动机，元胞空间的划分则可能有多种形式，最为常见的是二维元 胞自动机。二维元胞空间通常可按三角、四方或六边形三种网格排列【阚，本文主要按 6 硕士论文 基于元胞自动机的公钥密码体制研究 照四方形式排列来研究二维元胞自动机。图2 1 3 1 表示了一维元胞自动机的邻居状 态；图2 1 3 2 表示了二维元胞自动机的邻居状态。 图2 1 3 1 一维元胞自动机及其邻居 s m i t h 型 l m o o r e 型 l v o nn e u m a n n 型 l 湖豳 jr翼c习 秀。箩i髓 圜 巴 建黛叠 翻。躲 纛黼* 圆圈豳 c o l e 型 2 1 4 边界条件 表示元胞囵 t c o l e 型 表示邻居 图2 1 3 2 二维元胞自动机及其邻居 在理论上，元胞空间通常是在各维方向上是无限延展的，这有利于在理论上的 推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此， 我们需要定义不同的边界条件归纳起来，边界条件主要有四种类型：周期型，反射 型、定值型和随机型【阍。 周期型是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个 首尾相接的”圈；对于二维空间，上下相接，左右相接，而形成一个拓扑圆环面。周 期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。本文 所做的一切仿真实验所采用的都是这种边界条件。图2 1 4 1 是一维元胞自动机采用 循环边界时的示意图： 7 硕士论文 基于元胞自动机的公钥密码体制研究 图2 1 4 1 采用循环边界的一维元胞自动机 反射型是指在边界外邻居的元胞状态是以边界为轴的镜面反射。图2 1 4 2 表示 的是在一维空间中，当r = l 时的边界情形： 图2 , 1 4 2 采用映射边界的一维元胞自动机 定值型是指所有边界外元胞均取某一固定常量，对于初等元胞自动机可以采用 0 ，l 中的一个值图2 2 4 3 表示的就是这种情况： 固定采用这种元胞 固定采用这种元臆 图2 2 4 3 采用固定边界的一维元胞自动机 随机型是指在边界处实时产生随机值。这样的话，可以更加客观、自然地模拟 实际现象。 2 1 5 转换规则 元胞自动机规则是元胞自动机动态演化时所遵从的函数，这些函数决定了元胞自 动机中每个元胞未来的演化状态。它是根据元胞及其邻居当前状态来确定下一时刻该 元胞状态的函数，也可以称为状态转移函数。我们将一个元胞的所有可能状态连同负 责该元胞的状态变换的规则一起称为一个变换函数。这个函数构造了一种简单的、离 散的时间空间的局部物理成分。通常，对于一个系统来说，元胞自动机的规则是确定 的，也就是给定初始条件元胞自动机始终会沿着相同的路径演化，得到相同的演化结 果。但是有时为了更好地模拟自然现象，元胞状态转换采用的规则会发生变化。这种 元胞自动机就是上文所说的混合元胞自动机。 8 ， 口， 硕士论文基于元胞自动机的公钥密码体制研究 2 2 元胞自动机的表示 除了通常使用的状态转移表和状态转移矩阵，元胞自动机的状态转换规则还可以 采用两种更加有效的表示方法：w o 墙a m 表示法和d eb r u i j n 表示法。这两种方法都 是针对一维二状态元胞自动机的；若元胞自动机的状态大于2 或者采用更高维度的元 胞自动机，那么状态转移表是最有效的表示方法了 2 2 1w o l f r a m 表示法 w o l f r a m 首先对一维元胞自动机其进行了系统的研究，对于元胞状态是2 、邻居 半径是1 的基本元胞自动机来说，元胞f 在，+ l 时刻的状态q 只是与f 时刻元胞f 的本 身状态及其邻居状态有关，因此基本元胞自动机的演化函数可以用一个三元组 - l ，如) 来表示，即s ，t “= ( s t ，s l ) 对每个元胞来说，共有2 3 = 8 种可能邻居 构型，即集合r = 石= ，( i i i ) ，工= ，( 1 1 0 ) ，石= 厂( 0 0 1 ) ，石= 厂( 0 0 0 ) ) 。这 样就可以用晶的值来表示三元组的结果，即用s o 而s 2 与瓯屯氏s 7 的值来表示元胞自动 机的规则，显然有2 s = 2 5 6 种规则，其中，是由第h 个邻居构型状态产生的t + l 时 7 。罗，：+ 2 刻的元胞状态值。集合r 这个组合的值排成一列，它们的和的和勺= 蒿 称为 初等元胞自动机的规则号【j 2 l 。比如8 5 号元胞自动机，表2 1 1 1 说明的是用w o l f r a m 数字表示法来表示时的情况： 表2 2 1 18 5 号元胞自动机的w o l f r a m 表示法 2 2 2d eb r u i j n 表示法 邻居状态取值 0 0 0l 0 0 1 0 0 1 0l o l lo 1 0 0l 1 0 1o 1 1 0l 1 1 10 d eb 州n 表示法是采用图形的方式表示初等元胞自动机的邻居三元组 ( 如，e t 。) 的状态转换情况。这种表示方法是这样的：对于局部的状态转移函数 9 硕士论文 基于元胞自动机的公钥密码体制研究 j = 8 ( s u t ) ，我们把麒设为一个状态a ，而把甜设为另一个状态b ，从状态a 到状态 b 有一个箭头，把s 的值标在这个箭头上。 比如8 5 号元胞自动机，用d eb r u i j n 图形表示法示意如图2 2 2 1 【1 7 l ： o 图2 2 2 i8 5 号元胞自动机的d e b m i j n 表示法 当然这张d eb m i j n 图仅仅形象地表示了8 种局部状态转换过程，是没有经过优 化过的。 2 3 元胞自动机的分类 元胞自动机构成方式繁杂，变种很多，行为复杂。故其分类难度也较大，自元胞 自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题 和核心理论。 元胞自动机的多样性主要由其领域函数规则决定，由于元胞自动机的领域函数规 则与空间维数、时间阶数、领域半径和状态空间等直接相关，所以元胞自动机在分类 时必须指明这些参数【1 3 1 。 目前主要研究的是初等元胞自动机的分类。一般根据其领域函数规则的静态特性 与动态行为之间关系来划分元胞自动机。在基于不同的出发点，元胞自动机可有多种 分类，其中，最具影响力的当属s w o l f r a m 做的基于动力学行为的元胞自动机分类， 而基于维数的元胞自动机分类也是最简单和最常用的划分。下面就来介绍这两种分 类。 2 3 1 动力学分类 在8 0 年代初，s w o l f r a r m 详细分析了一维元胞自动机的演化行为，并在大量 的计算机实验的基础上，将所有元胞自动机的动力学行为归纳为四大类。他根据基本 1 0 硕士论文 基于元胞自动机的公钙密码体制研究 元胞自动机状态配置的时域特性将其分为四种类型：状态转移进入一个固定的状态； 状态转移进入简单的周期状态；状态转移进入混沌状态模式；状态演化为更加复杂的 模式。这四种类型的详细描述如下【1 9 】： ( 1 ) 平稳型：自任何初始状态开始，经过一定时间运行后，元胞空间趋于一个空 间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。 ( 2 ) 周期型：经过一定时间运行后，元胞空间趋于一系列简单的固定结构( s t a b l e p a t e r n s ) 或周期结构( p e r l o d i c a lp a t t e r n s ) 。由于这些结构可看作是一种滤波器 ( f i l t e r ) ，故可应用到图像处理的研究中。 ( 3 ) 混沌型：自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混 沌的非周期行为，所生成的结构的统汁特征不再变止，通常表现为分形分维特征。 ( 4 ) 复杂型：出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传 播。 例如，规则1 6 0 属于l 类、规则1 8 4 属于2 类、规则1 8 和1 0 5 属于第3 类等。 但从研究元胞自动机的角度讲，最具研究价值的具有第四类行为的元胞自动机，因为 研究表明这类元胞自动机可以用作广义计算机( u n i v e r s a lc o m p u t e r ) 以仿真任意复 杂的计算过程。s w o l f r a r m 还近似地给出了上述四种一维元胞自动机中各类吸引子 或模式所占地比见表2 3 1 1 【嘲，可以看出，具有一定局部结构的复杂模式出现的概 率相对要小一些。而第三种混沌型则出现的概率最大，并且，其概率随着k 和r 的增 大而呈现增大的趋势。 表2 3 1 i 各类一维元胞自动机( k 、r ) 所占比例 注：k 代表状态数，r 代表邻居半径 分类不是严格的数学分类，但s w o l f r a m 将众多的元胞自动机的动力学行为归 纳为数量如此之少的四类，是非常有意义的发现，对于元胞自动机的研究具有很大的 指导意义。 硕士论文 基于元胞自动机的公钥密码体制研究 2 3 2 维数分类 理论上，元胞自动机可以是任意维数的。那么，按元胞空间的维数分类，元胞自 动机通常可以分为【2 0 】： ( 1 ) 一维元胞自动机：元胞按等间隔方式分布在一条向两侧无限延伸的直线上， 每个元胞具有有限个状态s ，se s = s l ，s 2 ，s k l ，定义邻居半径r ，元胞的左右 两侧共有2 r 个元胞作为其邻居集合n ，定义在离散时间维上的转换函数，：s 2 州一s 可以记为：g “= ，( ，砚，碍，殴。，殴，) ，群为第i 个元胞在t 时刻的状态。 对一维元胞自动机的系统研究最早，相对来讲，其状态、规则等较为简单，往往 其所有可能的规则可以一一列出，易于处理，研究也最为深入。目前，对于元胞自动 机的理论研究多集中在一维元胞自动机上。s w o l f r a m 对元胞自动机的动力学分类也 是基于对一维初等元胞自动机( e l e m e n t a r yc e l l u l a ra u t o m a t a ) 的分析研究得出的。 它的最大的一个特征在于容易实现元胞自动机动态演化的可视化：二维显示中，一维 显示其空间构形，即空间维；另外一维显示其发展演化过程，即时间维。 ( 2 ) 二维元胞自动机：元胞分布在二维欧几里德平面上规则划分的网格点上，通 常为方格划分。以j h c o n w a y 的生命游戏为代表，应用最为广泛。 由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法， 转换n - - 维空间上，所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维 元胞自动机模型。本文构造的公钥加密算法使用了m o o r e 型二维元胞自动机来作为公 钥。 ( 3 ) 三维元胞自动机：目前，b a y s 等人在这方面做了若干试验性工作，包括在 三维空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论。 ( 4 ) 高维元胞自动机；只是在理论上进行少量的探讨，实际的系统模型较少。l e e m e e k e r 在他的硕士论文中，进行了对四维元胞自动机的探索。 2 4 元胞自动机的应用 元胞自动机理论自从提出之后，在各个领域的应用都得到了很大的发展，其范围 涉及信息学、计算机科学、物理学、社会学、环境学等学科。在信息学中，元胞自动 机在伪随机序列生成和对称加密方面都有很大的发展。在计算机科学中，元胞自动机 用来研究并行运算，因为并发运算是元胞自动机内在的优势。在物理学中，元胞自动 机用于模拟一些具体的物理现象的动态变化过程。在社会学中，元胞自动机用于研究 经济危机的形成与爆发过程。在环境学中，有些学者使用元胞自动机构造了森林生长 的模型。 1 2 硕士论文基于元胞自动机的公钥密码体制研究 2 4 1 生命游戏 c o n w a y 的“生命游戏”是最广为人知的元胞自动机。生命游戏( g a m eo f l i f e ) 是二维的元胞自动机，由剑桥大学的数学家j o h nh o r t o nc o n w a y 于1 9 7 0 年所提出 的。他认为细胞不会无限制地生长，于是他定义细胞在过度孤单与拥挤时会死亡，这 样的构想使他提出比j o h n v o n n e 啪a 的设计更为简单的元胞自动机。它根据元胞 的局部空间构形来决定生死，只不过规则更为简单。在这个元胞自动机中，把平面分 割成很多方格子，每一格子代表一个细胞，每一个细胞有八个邻居，这些细胞有两种 状态：生或死，存活的细胞我们在方格内涂上特定单一的颜色，而死亡的细胞我们则 不涂色。下面介绍生命游戏的构成及规则【2 1 l ： ( 1 ) 元胞分布在规则划分的网格上； ( 2 ) 元胞具有0 、l 两种状态，0 代表死，1 代表生； ( 3 ) 元胞以相邻的8 个元胞为邻居，即m o o r e 邻居形式； ( 4 ) 一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态( 确切 讲是状态的和) 决定： 在当前时刻，如果一个元胞状态为生，且八个相邻元胞中有两个或三个的状 态为生，则在下一时刻该元胞继续保持为生，否则死。去： 在当前时刻，如果一个元胞状态为”死”，且八个相邻元胞中正好有三个为生， 则该元胞在下一时刻”复活，否则保持为死。 尽管它的规则看上去很简单，但生命游戏是具有产生动态图案和动态结构能力的 元胞自动机模型。它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞状态值 的分布有关，给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失， 而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行，的则保 持图案定向移动，形似阅兵阵，其中最为著名的是滑翔机”的图案【2 ”。图2 4 1 1 显示了生命游戏中的各种图案1 2 l 】 生命游戏模型已在多方面得到应用。他的演化规则近似地描述了生物群体的生存 繁殖规律：在生命密度过小( 相邻元胞数之2 ) 时，由于孤单、缺乏配种繁殖机会、缺 乏互助也会出现生命危机，元胞状态值由1 变为0 ：在生命密度过大( 相邻元胞数 3 ) 时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，元胞状态值由1 变为 0 ：只有处于个体适中( 相邻元胞数为2 或3 ) 位置的生物才能生存( 保持元胞的状态值 为1 ) 和繁衍后代( 元胞状态值由0 变为1 ) 。正由于它能够模拟生命