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

中山大学硕上学位论文细胞自动机在密码学中的应用研究 细胞自动机在密码学中的应用研究 专业：计算机软件与理论 硕士生：郝立波 指导教师：陈炬桦副教授 摘要 细胞自动机具有演化规则简单、相互作用局部化和信息处理高度并行的特 点。将细胞自动机的动力学系统复杂特性应用于密码技术当中，具有非常重要的 研究价值。 本文在前人学者对细胞自动机在密码学中的应用研究基础之上，总结了细胞 自动机的多项式分析方法和矩阵分析方法及其在伪随机序列发生方法中的应用 研究，提出了一种具有t 型邻居结构的细胞自动机模型，并应用该模型构造伪 随机序列发生方法。实验表明具有t 型邻居的细胞自动机伪随机序列发生方法 可以产生较好的伪随机序列并满足统计测试要求。 本文通过对具有t 型邻居的细胞自动机的演化规则结构研究，提出了一种 具有两个初始状态的可逆细胞自动机，并从密码学的角度出发，研究可逆细胞自 动机在分组密码中的应用模型，构造了基于可逆细胞自动机的分组对称加密方 法，并分析了该加密方法的安全可行性，以实现安全高效的对称加密方法。研究 表明，该加密方法对明文扩散的要求达到了较好的雪崩效应，特别是加密初始状 态随机序列的引入，更增强了该密码系统的抗攻击能力。 细胞自动机在密码学中的应用是密码学研究中的新领域，尽管基于细胞自动 机的各种加密方法的安全性还有待进一步检验，目前基于细胞自动机的加密方法 还处于探索与发展阶段，但细胞自动机在密码学中的应用研究作为密码技术自主 化方面的新技术，正逐步成为研究的热点。 关键词：细胞自动机，伪随机序列，分组加密，可逆 中山大学硕十学位论文细胞自动机在密码学中的应用研究 r e s e a r c ha n d a p p l i c a t i o no fc e l l u l a r a u t o m a t ai nc r y p t o g r a p h y c o m p u t e rs o f t w a r ea n dt h e o r y n a m e h a ol i b o s u p e r v i s o r ：c h e nj u h u a a b s t r a c t c e l l u l a ra u t o m a t ah a v et h ep r o p e r t i e so fs i m p l ec o n s t r u c t i o nb ye v o l u t i o nr u l e s ， t h ei n t e r a c t i o no fl o c a li n f o r m a t i o na n dah i g h d e g r e eo f p a r a l l e lp r o c e s s i n g a r c h i t e c t u r e c e l l u l a ra u t o m a t ah a v ec o m p l e xd y n a m i c ss y s t e mc h a r a c t e r i s t i c s t h e a p p l i c a t i o no 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 yh a sav e r yi m p o r t a n tr e s e a r c hv a l u e t h i sp a p e rs u m m e du pt h ep r e v i o u ss c h o l a r so ft h ec e l l u l a ra u t o m a t ar e s e a r c h a n dt h ea p p l i c a t i o no fc 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 , a n dd e s c r i b e dt h ec e l l u l a r a u t o m a t aa n a l y s i sm e t h o ds u c ha sp o l y n o m i a lm e t h o da n dm a t r i xm e t h o da n dt h e m e t h o do fp s e u d o r a n d o ms e q u e n c eg e n e r a t o r si nt h es t u d y t h i sp a p e rp r e s e n t sa t - s h a p e ds t r u c t u r eo fc e l l u l a ra u t o m a t aa n da p p l i e si tt oc o n s t r u c tp s e u d o r a n d o m s e q u e n c eg e n e r a t o r s e x p e r i m e n t ss h o wt h a tt h ep s e u d o r a n d o ms e q u e n c eg e n e r a t o r b a s e do nt s h a p e dc e l l u l a ra u t o m a t ai sab e t t e rw a yt og e n e r a t ep s e u d o r a n d o m s e q u e n c ea n ds a t i s f yt h es t a t i s t i c a lt e s t s t h i sp a p e rp r e s e n t sar e v e r s i b l ec e l l u l a ra u t o m a t aa n das y m m e t r i ce n c r y p t i o n s y s t e mw i t hr e v e r s i b l ec e l l u l a ra u t o m a t a an e w k i n do fr e v e r s i b l ec e l l u l a ra u t o m a t a w h i c hn e e dt w oi n i t i a ls t a t e sa n dh a v i n gt - s h a p e ds t r u c t u r ew a sd e s i g n e d t h i sp a p e r p r o p o s e dan e we n c r y p t i o na l g o r i t h mb a s e do nac l a s so fr e v e r s i b l er u l e sc e l l u l a r a u t o m a t aa n da n a l y s i st h ef e a s i b i l i t ya n dt h es e c u r i t yo ft h i se n c r y p t i o nm e t h o di n o r d e rt oa c h i e v es a f ea n de f f i c i e n ts y m m e t r i ce n c r y p t i o ns y s t e m r e s e a r c hs h o wt h a t b l o c kc i p h e rb a s e do nr e v e r s i b l ec e l l u l a ra u t o m a t ac a nn o to n l ya c h i e v eab e t t e r a v a l a n c h ee f f e c t , b u ta l s ob e c a u s eo fu s er a n d o ms e q u e n c ei nt h eb e g i n n i n go f e n c r y p t i o n c a ni m p r o v et h es e c u r i t yo ft h ea p p l i c a t i o n so fc e l l u l a ra u t o m a t ai n c r y p t o g r a p h y t h ea p p l i c a t i o no fc e l l u l a ra u t o m a t ai n c r y p t o g r a p h y i san e wa r e ao f c r y p t o g r a p h yr e s e a r c h ，a n dv a r i o u sm e t h o d so fe n c r y p t i o nb a s e do nc e l l u l a ra u t o m a t a s t i l lr e q u i r ef u r t h e ri n v e s t i g a t i o n a l t h o u g he n c r y p t i o nm e t h o d sw i t hc e l l u l a ra u t o m a t a a r es t i l li nt h ee x p l o r a t i o na n dd e v e l o p m e n ts t a g e ，i ti sah o p e f u lt e c h n i q u eo f i n d e p e n d e n tc r y p t o g r a p h yr e s e a r c ha n dw i l lb e c o m eh o tp o i n to fr e s e a r c hg r a d u a l l y k e yw o r d s ：c e l l u l a ra u t o m a t a , p s e u d o r a n d o ms e q u e n c e ，b l o c kc i p h e r , r e v e r s i b l e 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 学位做作者签名= 卿三池 日期：众一矿年岁月i ；e l 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院 系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采 用复印、缩印或其他方法保存学位论文。 学位论文作者签名卿立迦 日期：反n 子年5 月 日衅耐 雌 僻 耐 懈 铡 名 辄 鹤 醐 蚵 m b 中山大学硕上学位论文细胞自动机在密码学中的应用研究 1 1 研究背景及意义 第1 章绪论 随着计算机的广泛应用及互联网技术的飞速发展，保障信息通信安全的重要 性不断增强。信息通信安全的首要保证就是要有一个安全可靠的加密系统。密码 技术作为保密通信和信息安全的核心，受到世界各国学者、专家的青睐。密码技 术的自主研发成为发展信息安全技术的基础和前提。每个国家都希望研究出符合 本国需求的、具有自主知识产权和高度保密性的加密系统。 随着密码学的发展，加密技术可以分为两类：对称加密系统和公钥加密系 统。前者的加密密钥与解密密钥相同或从一个很容易推出另一个，后者的加密密 钥与解密密钥不同或从一个难以推出另一个。按照加密方式，密码系统可以分为 流加密和分组加密两种方式。前者是将明文按位加密，后者是将明文分成定长的 块加密。 随着对细胞自动机研究的不断深化与改进，细胞自动机本身所固有的简单规 则性、单元之间作用局部互连性引起人们广泛关注。本文就细胞自动机在密码学 中的应用进行研究与探索，重点是研究细胞自动机伪随机序列发生方法，并利用 本文提出的可逆细胞自动机设计分组加密算法，并对其进行安全性分析。利用细 胞自动机理论研究密码学新技术，有助于建立自主密码体制，并对密码学的研究 提出了新的思路与研究方法。 1 2 细胞自动机研究现状 1 9 4 8 年，j y o nn e u m a n n 在研究“什么逻辑组织结构的自动机具有通用图 灵机那样的自我复制的特性的问题时，首次提出细胞自动机的概念船1 。他采用 二维细胞自动机结构，使用具有2 9 个状态的二维细胞自动机建立了一个具有自 我复制特性和通用计算能力的细胞自动机模型。1 9 6 8 年e f c o l d d 对其进行 了简化，建立了有8 个状态的细胞自动机模型，实现了细胞自动机的自我复制特 性和通用计算能力口】。此后，b u r k s 对细胞自动机进行了大量的总结与研究h 1 。 中山大学硕上学位论文细胞自动机在密码学中的应用研究 早期的细胞自动机研究主要集中于理论方面，之后一些物理学家与生物学家将此 理论应用到其研究领域嵋1 ，应用细胞自动机理论构造的复杂模型来模拟复杂的自 然现象。由于早期细胞自动机理论的复杂性，难以完成物理实现，一定程度上限 制了细胞自动机理论的应用阳1 。2 0 世纪8 0 年代初，s w o l f r a m 在细胞自动机理 论研究方面作了大量的工作，并提出了简化的细胞自动机模型。他提出简化细胞 自动机的状态空间和邻域半径方法，以此构造出演化规则简单，具有局部互连性 和信息处理高度并行性的细胞自动机模型口1 。1 9 8 5 年，s 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 ) 的文章，首次提出了将细胞自动机 理论引入到密码学当中，极大地推动了细胞自动机理论和应用研究的发展，并开 创了细胞自动机理论在密码学中的应用研究。 1 2 1 细胞自动机的理论研究 自s w o l f r a m 提出对细胞自动机简化后，对细胞自动机的理论研究发展为 对其状态转移结构的分析与研究。主要有基于状态转移多项式的研究方法和基于 状态转移矩阵的研究方法1 。1 9 8 3 年，s w o l f r a m 首先提出使用状态转移多项 式的研究方法来分析一维、线性、单一细胞自动机口1 。1 9 8 4 年，o l i v i e rm a r t i n 等人使用多项式方法对循环边界的单一细胞自动机的可逆性、状态可达性和状态 结构等统计特性进行了研究瞪1 。1 9 8 6 年，w e r n e rp r i e s 等人使用多项式方法对 线性、单一细胞自动机的状态转移群特性进行了分析n 叫。1 9 9 3 年，b k k a r 等人根据多项式方法，使用线性细胞自动机的生成函数写出了其任意t 次演化后 的状态转移的闭合式。从而可以直接计算出细胞自动机演化后的全局状态1 。但 多项式方法却不能对混合细胞自动机进行分析。 为了能够有效的分析混合细胞自动机，1 9 9 0 年a l o k ek d a s 等人将状态 转移矩阵引入到混合细胞自动机中，通过分析细胞自动机状态转移矩阵的最小多 项式来分析一维、加性、混合细胞自动机的状态转移特性n 2 1 。1 9 9 3 年s h i n i c h i t a d a k i 等人根据状态转移矩阵的特征多项式分析了规则9 0 循环边界条件的细胞 自动机状态转移特性n 引。同年，d ，r o yc h o w d h u r y 等人将一维、线性细胞自动 机的状态转移矩阵分析方法扩展n - - 维、线性细胞自动机上，并对垂直邻居受限 的二维、线性细胞自动机的群特性进行了分析n 引。1 9 9 8 年，p o hy o n gk o h 等人 中山大学硕上学位论文细胞自动机在密码学中的应用研究 使用细胞自动机状态转移矩阵特征多项式的方法研究了任意边界条件的9 0 1 5 0 混合细胞自动机，并求出了固定边界条件与零边界条件下细胞自动机的特征多项 式之间的关系n 5 1 。 1 2 2 细胞自动机的应用研究 细胞自动机在很多领域中都有广泛应用，其中包括细胞自动机自然模拟模型 在各种复杂系统中的应用研究，如1 9 9 7 年，n i c h o l a sj s a v i l l 和p a u l i e n h o g e w e g 提出了一个可用于研究简单细胞系统形态发生的三维混合细胞自动机 和偏微分方程模型n 引。他们运用该模型模拟了黏菌从单一的细胞到可爬行的成虫 的生长过程。2 0 0 0 年，r s a d a n a n d a 和s w o n g t h a n a v a s u 提出了基于细胞自 动机的二进制图像边缘检测模型n 7 1 ，实现了对二进制图像边缘的检测及图像的像 素级检测。在城市时空演化方面，2 0 0 1 年p a u lmt o r r e n s 等人提出了带有分叉 ( t v o p r o n g e d ) 方法的扩展细胞自动机模型，用以模拟城市发展演化等地理扩散 过程n 缸坞1 。此外还包括细胞自动机并行计算模型的研列州2 门及本文所研究的细胞 自动机在密码学中的应用。 细胞自动机在密码学中的应用包括应用细胞自动机产生伪随机序列、应用细 胞自动机构造对称加密方法和非对称加密方法。由于细胞自动机演化过程是一个 反复的在康托集上的映射过程，具有很好的动力学系统所特有的复杂特性幽1 。演 化结果会因初始状态的不同而不同，某一细胞状态的单独改变，会在演化过程中 产生雪崩式的扩散。1 9 8 5 年，s w o l f r a m ，首次提出了将细胞自动机理论引入 到密码学当中，提出将细胞自动机的初始状态作为密钥，使用细胞自动机演化结 果作为伪随机序列对明文按位加密1 。尽管这种方法的安全强度不够高，但s w o l f r a m 开创了细胞自动机在密码学中的应用研究，具有深远的指导意义。1 9 8 9 年，p d h o r t e n s i u s 提出了使用具有m 序列特性的细胞自动机产生伪随机序 列1 。1 9 9 1 年，p t s a l i d e s 等人提出了应用规则9 0 1 5 0 的混合细胞自动机生 成伪随机序列汹1 。1 9 9 4 年s n a n d i 提出了使用g f ( 2 ) 上的可编程细胞自动机和 存储单元来产生伪随机序列。1 9 9 6 年，z m i c h a l e w i c z t 等人提出了引入遗传算 法演化方式的细胞自动机伪随机序列发生方法泌3 。1 9 9 9 年，m i o d r a g m i h a l j e v i c 等人提出了在g f ( q ) 上使用线性可编程细胞自动机的前向迭代产生 中山大学硕士学位论文 细胞自动机在密码学中的应用研究 伪随机序列的方法啪3 。2 0 0 0 年，m a r c ot o m a s s i n i 扩展了z m i c h a l e w i c z t 的方 法，提出了了引入遗传算法演化方式的二维细胞自动机伪随机序列的发生方法 汹1 。2 0 0 2 年，张传武利用9 0 1 5 0 混合细胞自动机的状态转移同构特性，提出了 基于垂直邻居受限的二维细胞自动机伪随机序列的发生方法伽1 。2 0 0 4 年， s h e n g - u e ig u a n 等人提出了具有可控细胞的细胞自动机( c c a ) 伪随机序列的发生 方法口，实现了以一维细胞自动机结构产生二维细胞自动机复杂特性的伪随机序 列发生方法。 细胞自动机在应用于伪随机序列发生方法的同时，细胞自动机在分组加密方 面也得到了相应的发展与研究。1 9 9 4 年，s n a n d i 等人提出了可编程细胞自动 机和群细胞自动机的概念，并根据细胞自动机循环群特性提出了基于置换群基本 变换的分组加密技术口2 | 。1 9 9 6 年，0 l a f e 提出了基于细胞自动机变换的概念 和一种基于细胞自动机变换的加密方法船州3 4 l 。2 0 0 2 年，s u b h a y a ns e n 等人提出 基于细胞自动机的分组加密方法( c a c ) 口纠，该方法使用两个具有固定周期的细胞 自动机，采用以明文作为初始状态直接输出密文的加密方式。2 0 0 4 年，f e n gb a o 对s u b h a y a ns e n 提出的加密方法进行了成功的密码分析m 3 ，张文涛也对该方法 的一个变形进行了分析阳7 1 。2 0 0 6 年，p a l l a v ij o s h i 等人提出了一个具有自可逆 特性细胞自动机分组加密方法呻1 ，该方法使用线性和非线性细胞自动机构造一个 自可逆细胞自动机进行多轮加密。2 0 0 7 年，j a e c h u ls u n g 和d e u k j oh o n g 共同 对p a l l a v ij o s h i 提出的方法进行了密码分析，指出由于在构造过程中所自有的 配对性使得该方法不够安全1 。细胞自动机在分组加密方面的研究不断展开，细 胞自动机的研究方向由比较成熟的伪随机序列发生方法转向高维细胞自动机研 究和利用可逆的细胞自动机在分组加密中的研究m 1 。细胞自动机在密码学中的应 用是密码学研究中的新领域，基于细胞自动机的各种加密方法的安全性还有待进 一步检验，目前基于细胞自动机的加密方法还处于探索与发展阶段。 1 3 本文所作的工作 本文在前人学者在细胞自动机在密码学中的研究基础之上，总结了细胞自动 机的多项式分析方法和矩阵分析方法及伪随机序列发生方法的研究。本文利用细 胞自动机所具有的演化规则简单、相互作用局部性和信息处理高度并行性的特 中山大学硕上学位论文细胞自动机在密码学中的应用研究 点，提出一种需要两个初始状态的具有t 型邻居的细胞自动机，并应用该细胞自 动机构造伪随机序列发生方法。在此基础这上本文进一步提出了具有t 型邻居的 可逆特性的细胞自动机，并分析了该细胞自动机的可逆特性。结合细胞自动机的 可逆特性，本文设计了一个利用可逆细胞自动机进行对称加密的分组加密方法。 最后分析了该加密方法的安全可行性。 1 4 论文结构与章节安排 论文结构安排如下： 第一章介绍细胞自动机的发展与研究背景，总结了细胞自动机在密码学中的 研究进展与研究成果。 第二章介绍了细胞自动机的基础知识，细胞自动机的分类、特点及研究方法。 第三章对利用细胞自动机构造伪随机序列发生方法进行了研究。 第四章提出了一种具有可逆特性的细胞自动机，并利用该细胞自动机构造分 组加密方法。 第五章是对本文研究工作的总结与展望。 中山大学硕士学位论文细胞自动机在密码学中的应用研究 2 1 细胞自动机 第2 章细胞自动机 细胞自动机是一种特殊的有限状态机，具有时间、空间和状态的离散性。早 期的细胞自动机研究开始于j v o nn e u m a n n 。1 9 4 8 年，j v o nn e u m a n n 在研究 “什么逻辑组织结构的自动机具有通用图灵机那样的自我复制的特性 的问题 时，首次提出细胞自动机的概念乜1 。他采用二维细胞自动机结构，使用具有2 9 个状态的二维细胞自动机建立了一个具有自我复制特性和通用计算能力的细胞 自动机模型。1 9 6 8 年e f c o l d d 对其进行了简化，建立了有8 个状态的细胞 自动机模型，实现了细胞自动机的自我复制特性和通用计算功能口1 。由于早期细 胞自动机理论的复杂性，难以完成物理实现，一定程度上限制了细胞自动机理论 的应用。2 0 世纪8 0 年代初，s w o l f r a m 在细胞自动机理论研究方面作了大量的 工作，并提出了简化的细胞自动机模型。他提出简化细胞自动机的状态空间和邻 域半径方法，以此构造出演化规则简单，具有局部互连性和信息处理高度并行性 的细胞自动机模型口3 。 2 1 1 细胞自动机的定义 细胞自动机是一种时间、空间和状态都离散的特殊的有限状态机。一个细胞 自动机由一组细胞单元阵列组成，每一个细胞单元都处于状态空间中的某种状 态。各细胞下一时刻的状态由当前细胞状态和与之相邻的细胞状态根据相应的状 态转移函数来确定。 细胞自动机是一个四元组c a = ，z 。，f ，曰) ，其中： d 一1 如表示空间结构，如2 丌l 是d 维细胞单元构成的空间结构。m 是第i 维空间上的细胞元素位置集合。 z 。表示空间状态，是细胞自动机中细胞单元的状态集合。 中山大学硕士学位论文细胞自动机在密码学中的应用研究 f 表示邻域函数规则，r 为领域半径。 b 表示边界条件，它确定了细胞单元在领域半径之内的细胞单元在超出空间 结构时的处理方法。 上面定义的细胞自动机中最简单的细胞自动机是一维的、领域半径为1 的、 状态空间为布尔值的基本细胞自动机。这也是在密码学应用研究中最为广泛的细 胞自动机。图2 - 1 是一维细胞自动机的直观图。 图2 1 一维细胞自动机结构图 2 1 2 细胞自动机的基本元素 自s w o l f r a m 提出简化的细胞自动机以来，其概念、结构和应用研究不断 深化。以下详细介绍细胞自动机的基本元素。 1 细胞：细胞是细胞自动机的最基本的单元，分布离散的空间阵列上。 细胞用来存储当前时刻的细胞状态。基本细胞自动机中的每个细胞所存储的 状态只有0 和1 两种。 2 细胞空间：细胞自动机可以存在于不同维数的空间中，对于基本细 胞自动机的细胞空间是由初始时刻处于某种状态的细胞序列随时间的离散变 化而演化的细胞序列。所有可能演化的细胞序列构成了细胞自动机的细胞空 间。细胞空间的组成同时与细胞邻域和边界条件密切相关。 3 邻域：细胞自动机在演化的过程中，下一时刻的状态是当细胞状态 与邻域细胞状态根据邻域函数规则确定的。邻域细胞就是与给定的细胞相互 影响下一时间演化状态的细胞集合。在一维细胞自动机中，以邻域半径来确 定邻域细胞，邻域细胞在与当前细胞距离小于或等于邻域半径的范围内。对 于基本细胞自动机，邻域细胞即指当前细胞的右邻居细胞和右邻居细胞。 4 边界条件：理论的上细胞自动机中细胞单元的个数是无限的，但在 实际应用中为了便于实现，细胞单元的数目是有限的，这就需要考虑边界的 条件。在实际运算中常用的边界方法有三种类型：周期型、反射型和定值型。 周期型边界条件是指相对的细胞边界连接起来的细胞空间。在基本细胞自动 中山人学硕士学位论文细胞自动机在密码学中的应用研究 机中表现为细胞序列组成首尾相连的环。反射型边界条件是指边界外的邻居 细胞状态是以边界为轴的镜面反射，在基本细胞自动机中可设边界外的邻居 细胞状态为当前细胞的状态。定值型边界条件是将边界外的细胞状态设置为 状态空间中的某一个定值。考虑到细胞自动机的物理实现，特别是超大规模 集成电路( v l s i ) 的实现，一般会采用定值型的零边界条件。 5 规则：细胞单元的状态在下一时刻的状态由邻域函数规则函数f 及 当前细胞与邻域细胞确定，对于基本细胞自动机细胞单元在下一时刻的状态 可表示为： s y l = 厂( s l 。，s ；，s i 。) ( 2 1 ) 其中g 为第i 个细胞在t 时刻的状态。 对于基本细胞自动机邻域内细胞有3 个，则有2 3 个映射情况，有2 8 个映射 函数。为方便起见，将所有邻域状态情况厂( 鞋。，研，殴，) 的映射值 g “= 厂( 殴。，研，s l 。) 由高位到低位组成的二进制数称为基本细胞自动机的规则 号。例如1 5 0 号规则如图2 2 所示。 皿 上 固 圆 l + 回 圆 上 回 圈 上 固 圆 l 回 圆 l ， 团 圆 l + 团 圆 j r 回 固回回田回固固回= 1 5 0 图2 2 细胞自动机规则表示方法 2 2 细胞自动机的分类 细胞自动机的多样性主要由其邻域函数规则决定，由于细胞自动机的邻域函 中山人学硕士学位论文 细胞自动机在密码学中的应用研究 数规则与空间维数、邻域半径和状态空间等直接相关，所以细胞自动机在分类时 必须指明这些参数。目前主要研究的是基本细胞自动机的分类。一般根据其邻域 函数规则的静态特性与动态行为之间的关系来划分细胞自动机。 早期对细胞自动机的分类是s w o l f r a m 根据基本细胞自动机演化过程定性 的分为四种类型h ： 状态转移进入一个固定的单一状态，这种细胞自动机演化行为简单，大多数 的初始状态都会演化为单一的全局状态，如所有状态均为零； 状态转移进入简单的周期状态，这种细胞自动机最终演化为结构简单的重复 状态； 状态转移进入混沌状态模式，这种细胞自动机演化行为复杂，有随机性的特 点，但同时也包含三角或其它结构在其状态演化过程中； 状态转移进入更为复杂的状态，这种细胞自动机演化结构复杂，有随机性特 点，虽然它的一些局部结构简单，但整体的演化结果却非常复杂。 例如，规则1 6 0 属于第一种，规则2 3 6 属于第二种，规则1 8 属于第三种， 规则1 5 0 属于第四种。四种类型的演化过程如图2 3 所示： 图2 3 细胞自动机状态演化 中山大学硕士学位论文细胞自动机在密码学中的应用研究 以上四种状态是一种定性的分类方法，不能判定给定的细胞自动机属于哪一 类。从细胞单元的演化规则是否随其状态演化过程而变化可以分为确定的细胞自 动机和可编程的细胞自动机。而确定的细胞自动机可根据其规则组成结构可分为 单一细胞自动机和混合细胞自动机。 邻域函数规则不随其状态演化而变化的细胞自动机称为确定的细胞自动机。 所有细胞单元使用相同邻域函数规则的细胞自动机称为单一细胞自动机 ( u n i f o r mc e l l u l a ra u t o m a t a ) 1 2 o 由两种或两种以上的邻域函数规则组成的 细胞自动机称为混合细胞自动机( h y b r i dc e l l u l a ra u t o m a t a ) h 别。 混合细胞自动机不仅具有单一细胞自动机所具有的组成单元结构的简单规 则性、单元之间作用的局部互连性和信息处理的高度并行性等特点，而且由于其 组成规则的多样性而带来了细胞自动机的多样性。可以使用其各细胞单元的规则 号即邻域函数规则的组合来表示混合细胞自动机，如使用细胞自动机第0 个单元 为规则9 0 ，第1 个单元为规则1 5 0 ，第2 个单元为规则1 0 5 ，第3 个单元为规则 6 0 可称为具有4 个组成单元的确定的混合细胞自动机，各细胞单元的规则号即 邻域函数规则的组合( 9 0 ，1 5 0 ，1 0 5 ，6 0 ) 为该细胞自动机的规则向量。 邻域函数规则随其状态演化而变化的细胞自动机称为可编程的细胞自动机 ( p r o g r a m m a b i ec e l l u a ta u t o m a t a ) 3 2 o 可编程细胞自动机在确定性的细胞自 动机的基础上增加少量复杂性的同时可以获得结构可变的细胞自动机，具有比确 定性细胞自动机更多的、种类更复杂的特性和更灵活的选择。 细胞自动机中只有一部分可以使用代数的方法进行分析，根据细胞自动机所 确定的变换可将其分为线性细胞自动机和非线性细胞自动机，以及加性细胞自动 机和非加性细胞自动机。其中线性细胞自动机和加性细胞自动机之间的区别在于 它们是否包含同或运算。 所有细胞单元的邻域函数规则均由异或运算组成的细胞自动机称为线性细 胞自动机。线性细胞自动机具有全局状态线性可加的性质，即线性细胞自动机的 任意两个全局状态s 。和s 。均满足f ( s 。+ s 。) = f o ) + ， 。) 。在基本细胞自动机 中线性细胞自动机只能由规则0 、6 0 、9 0 、1 0 2 、1 5 0 、1 7 0 、2 0 4 、2 4 0 这八种线 性规则组成。 对于一个细胞自动机的邻域函数规则厂o ，如果存在另一个邻域函数五使它 中山人学硕士学位论文细胞自动机在密码学中的应用研究 们的领域状态映射互补，那么称它们为互补规则。如果一个细胞自动机中所有细 胞单元使用的规则均由线性规则及其补规则组成则称这种只由异或运算和同或 运算实现的细胞自动机为加性细胞自动机，否则为非加性细胞自动机。 2 3 细胞自动机的特点 细胞自动机的结构单元简单，不但适合大型计算机的模拟，也便于细胞自动 机的物理现实。细胞自动机中每一个细胞单元下一时刻的状态不是取决于细胞自 动机中所有细胞单元的状态，而是仅取决于其邻域范围内的细胞单元的状态。这 种相互作用局部性不但提高了细胞自动机在演化过程中的速度，而且随时间的演 化，作用的范围不断扩大，具有很好的混淆扩散效果。同时细胞自动机的相互作 用局部性也有利于实现并行计算。 2 4 细胞自动机的分析 以上定义的各种细胞自动机中，只有一部分可以使用代数的方法来分析。所 以目前主要是对线性和加性的细胞自动机进行分析。主要的分析方法有多项式分 析方法和矩阵分析方法。细胞自动机的分析是根据细胞自动机的邻域函数规则来 分析其全局状态转移特性。s w o l f r a m 首先提出使用代数方法来分析基本细胞 自动机h 1 ，之后o l i v i e rm a r t i n 等又提出了使用有限域上的多项式的方法对一 维、线性、单一细胞自动机进行分析悖1 。为了能够实现对混合细胞自动机的分析， d a s 等人引入了状态转移矩阵的分析方法n2 1 ，通过分析细胞自动机状态转移矩阵 的最小多项式来分析一维、加性、混合细胞自动机的状态转移特性。 2 4 1 细胞自动机的多项式分析 设具有n 个细胞单元的基本细胞自动机，在t 时刻的全局状态为 s = ( s ：，s k j _ 一。) ，其中s ； 0 ，1 】，i = o j , 。一1 。可以用公式( 2 2 ) 中的多项式 来表示细胞自动机的全局状态： 中山大学硕士学位论文细胞自动机在密码学中的应用研究 s “。s t 0 + s ：工1 + + s o 一石一2 荟s ；戈 ( 2 - 2 ) 其中石的系数s ；表示第i 个细胞单元的状态值。令细胞自动机的状态转移多 项式为t ( x ) 来表示细胞自动机的邻域函数规则： 丁 ) 一，x 。+ + 口。z 。+ + 口，石7 ；口r 石( 2 - 3 ) 对于邻域半径为1 的细胞自动机，t ( x ) = a _ i x 。1 + a o x o + 口1 x 1 。其中z o 表示 当前细胞，x 。1 表示前一细胞，z 1 表示后一细胞。在边界条件为循环边界条件情 况下，下一时刻的全局状态可以表示为： s 1 ) = t ( x ) s ( x ) m o d ( x 一1 ) ( 2 - 4 ) 该方法只适用于一维、线性、单一的细胞自动机。为了能够实现对一维、线 性、混合细胞自动机与对一维、加性、混合细胞自动机的分析。d a s 等人又提出 了引入状态转移矩阵的分析方法n 列。 2 4 2 细胞自动机的矩阵分析 在一维、线性、混合的细胞自动机中，由于每个细胞单元的邻域函数不同， 所以每个细胞单元的转移状态都要表示为其邻域内的映射。在领域半径为1 采用 零边界条件的情况下可以表示为： 5 1 = a o , o $ ：+ 口o 1 s ： s ：+ 1 _ 口l 。s ：+ 口- l s ：+ 口l t z s z t ( 2 - 5 ) s 爱1 = 口 r l ，一2 j 0 2 + 口 r l ，一l s 0 1 将公式( 2 - 5 ) 改写成矩阵的形式为： s 1 t ： 5 t + - l l a o ，o a 1 o 0 a o ，1 a l 。1 0 0 0 0 0 a - 1 ，一2a 一l ，一l s ： s ： ： 5 二，一l ( 2 6 ) 2 0 q 中山大学硕上学位论文 细胞自动机在密码学中的应用研究 公式( 2 - 6 ) 可以简写为： s “；t s 其中称丁= g 0 ，o 口1 0 o q o ，1 口1 1 o o 口1 2 0o oo ( 2 - 7 ) 为线性细胞自动机 的状态转移矩阵，s = g ：，s ：，s 0 。r 为细胞自动机在t 时刻的全局状态。初始 状态为s 。g ：，s 。o ，s o 一。) r 的线性细胞自动机在经过t 次演化后的状态 s ，g ：，s ：，s 名一。) r 可以表示为：s ；z s 。这表明细胞自动机的状态转移过程 可以由满足线性可加的线性运算来表示，初始状态为s 。g ：，s ? ，s 0 一。厂的一 维、线性、单一细胞自动机，在经过t 次演化之后其状态可以由 ( s o ，0 ，o ) r ，( 0 ，s ? ，o ) r ，( 0 ，0 ，s 0 ) r 与丁的模二加运算来表示，此时对于初 始状态为s 。g ：，s ? ，s o 一。) r 的细胞自动机的状态转移分析等同于对初始状态 为( 0 ，s ：) ，o 厂的状态转移分析，即： s 。：t s 。( ( 丁) 。，仃) 舻仃) 枷) r 嘲 ( 2 8 ) 由公式( 2 - 8 ) 可知通过分析细胞自动机的状态转移矩阵可以方便的分析其状 态转移的特性。 加性的细胞自动机分析与线性细胞自动机分析方法相似，由于加性的细胞自 动机其邻域函数规则由异或运算和同或运算组成，所以与一维、线性、混合细胞 自动机不同的是其邻域函数规则可以表示为：瓯t 一口“s 三1 + 口。s ；+ 口m s 0 。+ j l ，其 中h = 0 时邻域函数规则满足异或运算，h = l 时邻域函数规则满足同或运算。由线 性细胞自动机的状态转移方程( 2 - 5 ) 可知，零边界条件的加性细胞自动机状态转 移方程可以表示为： 中山大学硕上学位论文细胞自动机在密码学中的应用研究 s 1 = a o , o s ：+ 口o 1 s ：+ o j ：”= 口1 ，o s ：+ 口1 。l s ：+ a l , 2 s ：+ 1 s 爱l = a n _ l ， r 一2 s 二，一2 + 口 r 一1 一l s 二，一1 + 一l 将公式( 2 - 9 ) 写成矩阵的形式为： s 1 t ： s t + 一1 1 a o ，oa o ，1 000 a l ，o口1 ，ia l ，2 00 ： 00 a ，a 。， s ： s ： ： s 0 一l + h o h l ： h 一l ( 2 - 9 ) ( 2 1 0 ) 矩阵方程( 2 - 1 0 ) 可以简写公式( 2 - 11 ) ： s 1 = 嬲+ h ( 2 - 1 1 ) 其中称t 为加性细胞自动机的状态转移矩阵。已知初始状态为 s 。；( s o ，s o ，s o 。) r 的线性细胞自动机在经过t 次演化后的状态可以表示为： s ；丁s o 。同理可知通过分析加性细胞自动机的状态转移矩阵及h 来分析加性 细胞自动机的状态转移特性。 对于一个细胞自动机，如果其状态转移矩阵t 满足r ，一，那么其状态转移方 程对于任意t 都有s p = t v s 一s 的特性，称这样的细胞自动机为群细胞自动 机n 引，并称满足该条件的最小p 为该群细胞自动机的阶。 2 4 3 基于规则9 0 1 5 0 的混合细胞自动机的分析 将细胞自动机应用于密码学中，需要使用具有大周期的细胞自动机。通过细 胞自动机的矩阵分析方法可以得出，如果线性细胞自动机的特征多项式是本原多 项式，那么该细胞自动机就可以达到最大周期h 驯，即对于具有n 个细胞单元的线 性细胞自动机，其周期可以达到2 “一1 。在一维线性细胞自动机中，除规则9 0 1 5 0 细胞自动机以外的其它细胞自动机的特征多项式一般为可约的多项式，而规则 9 0 1 5 0 循环边界条件的细胞自动机的特征多项式为可约多项式n 4 。h 5 1 。又因为规 则9 0 1 5 0 零边界条件的细胞自动机具有特征多项式与最小多项式相等的特性， 中山大学硕上学位论文细胞自动机在密码学中的应用研究 所以对线性细胞自动机的研究一般集中于零边界条件的规则9 0 1 5 0 细胞自动 机。图2 - 4 表示了演化规则为9 0 1 5 0 细胞自动机状态演化图。 在一维线性的细胞自动机当中，邻域函数规则为9 0 的细胞自动机与邻域函 数规则为1 5 0 的细胞自动机可以逻辑表示为： 2 s l ，s l - ( 2 1 2 ) l s ；“一s l 。a s ；$ s l 。 两式采用模二加运算可以表示为： s ，1 = s 厶+ 口f s ；+ s l l ( 2 1 3 ) 其中a ；= 0 时表示规则9 0 ，a i 一1 时表示规则1 5 0 。 可以用一个n 维向量0 。，a l , - - a 一。) 来表示9 0 1 5 0 线性细胞自动机的规则组 成，并称之为9 0 1 5 0 线性细胞自动机的规则向量，如5 个细胞组成单元的规 则为( 1 5 0 ，1 5 0 ，9 0 ，9 0 ，1 5 0 ) 细胞自动机可以使用规则向量( 1 ，1 ，0 ，o ，1 ) 来表示，并 称之为( 1 ，1 ，0 ，0 ，1 ) 9 0 1 5 0 线性细胞自动机。 对于具有n 个细胞单元零边界条件的9 0 1 5 0 线性细胞自动机，其状态转移 矩阵方程可以表示为： s“；ts(2-14) 中山人学硕士学位论文 细胞自动机在密码学中的应用研究 其中r = 0 0 1 a 一l ，a 。e o ，u 为细胞自动机的状态 转移矩阵，因为细胞自动机的状态转移的周期性等于其状态转移矩阵的周期性， 所以通过分析细胞自动机的状态转移矩阵的最小多项式来分析细胞自动机状态 转移的特性。9 0 1 5 0 线性细胞自动机的状态转移矩阵的特征多项式为： p o + x 1 0 i f n - i ( x ) ：l 丁+ 觑i 。l j a 1 - x ，