（计算机软件与理论专业论文）基于细胞自动机的流密码设计.pdf

目录 基于细胞自动机的流密码设计 计算机软件与理论胡瑞桓 指导老师：陈炬桦副教授 摘要 在信息时代的今天，经过了几十年的高速发展，信息技术和网络技术得到了 广泛的应用，互联网走进了千千万万的家庭。由于人们的信息传递方式渐渐从传 统的邮递方式转变为依靠网络进行传递，越来越多的信息出现在互联网上。因此 信息安全问题引起了全人类的重视，信息的安全与保护问题显得越来越重要，在 这样一个背景下密码学的理论与技术成为计算机科学与技术中的一个重要研究 领域。流密码是现代密码学中的一个重要的研究分支，随着细胞自动机理论的提 出与发展，研究人员开始将细胞自动机应用于流密码以产生随机密钥。细胞自动 机具有组成单元结构的简单性、单元之间作用的局部性和信息处理的高度并行 性，使得其特别适用于密码学。 本文对细胞自动机的基本理论、细胞自动机的周期性、细胞自动机产生序列 的随机性以及利用细胞编程寻找最优细胞自动机进行了深入的研究。文章首先介 绍了细胞自动机的相关知识；然后引出了用来寻找最优细胞自动机的细胞编程思 想，结合某些细胞自动机具有较好的周期性以及产生的序列随机性相对其他细胞 自动机更好的特性，改进细胞编程以使其在特定种群中寻找最优细胞自动机，并 对该最优细胞自动机产生的输出序列的伪随机性进行了测试。为了适应在特定种 群中寻找最优细胞自动机，本文对细胞编程进行了如下改进：提出了新的种群编 码规则，并且也提出了基于这种编码规则的进化操作。最后，利用产生的几种能 产生高伪随机性序列的细胞自动机构造了三种流密码结构。 关键词：细胞自动机，细胞编程，流密码 i i i 目录 t h e d e s i g no fs t r e a mc i p h e rb a s e do nc e l l u l a r a u t o m a t a c o m p u t e rs o f t w a r ea n dt h e o r y h ur u i h u a n s u p e r v i s o r ：c h e nj u - h 氓a s s o c i a t e dp r o f e s s o r a b s t r a c t i nn o w a d a y s ，w h e ni n f o r m a t i o nt e c h n o l o g yi s d e v e l o p i n gf a s t ，a n dm o r ea n d m o r ei n f o r m a t i o ni st r a n s f e r r e di nn e t w o r k s ，s ot h ei n f o r m a t i o ns e c u r i t yi sm o r ea n d m o r ei m p o r t a n t ，w h i c hm a k e sc r y p t o l o g yt h e o r ya n dt e c h n o l o g yb e c o m et ob eav i t a l d o m a i no fr e s e a r c h s t r e a mc i p h e ri sa - i m p o r t a n tr e s e a r c hb r a n c ho fc r y p t o l o g y , a n d w i t hf a s td e v e l o p i n go fc e l l u l a ra u t o m a t at h e o r y , s t r e a mc i p h e rh a sm a d ef a s t d e v e l o p m e n tw i t ht h eh e l po fs o m em a t ht o o l s t h ep r o p e r t i e so fc e l l u l a ra u t o m a t a ， s u c ha se a s i l yb e i n gi m p l e m e n t e db yv l s i ，t h eh i g hp a r a l l e ls t r u c t u r ea n dc o m p l e x d y n a m i cp r o p e r t y , m a k ei tb et h o u g h ta sap r o m i s i n gc o r et e c h n o l o g yi nc r y p t o l o g y i nt h i sp a p e r , w eh a v er e s e a r c h e dt h ep e r i o d i c i t yo fc e l l u l a ra u t o m a t a , t h e r a n d o m i c i t yo fs e q u e n c ef r o mc e l l u l a ra u t o m a t aa n dh o wt of i n dt h eb e s tc e l l u l a r a u t o m a t ab yc e l l u l a rp r o g r a m m i n g f i r s t ，t h i sp a p e ri n t r o d u c e st h eb a s i ck n o w l e d g eo f c e l l u l a ra u t o m a t a s e c o n d ，t h i sp a p e ri n t r o d u c e ss i p p e r sc e l l u l a rp r o g r a m m i n gw h i c h w a su s e dt of i n dt h eb e s tc e l l u l a ra u t o m a t a t h i sp a p e rm a k e su s eo ft h ec e l l u l a r p r o g r a m m i n gt of i n dt h eb e s t9 0 1 5 0 1 0 5 1 6 5c e l l u l a ra u t o m a t a ，a n di nt h eb a s eo f t h e c e l l u l a rp r o g r a m m i n g ，t h i sp a p e ri m p r o v e st h ec e l l u l a rp r o g r a m m i n gt o a d a p tt h e p u r p o s e l a s t ，t h i sp a p e rm a k e su s eo fs o m es t r e a mc i p h e rm e t h o d sw h i c ha r eu s e di n l f s rt os t r u c ts t r e a mc i p h e r , a n dt e s t st h e mt ob ee n o u g hr o b u s tt og u a r a n t e et h e r a n d o m i c i t yw i t ht h ei n c r e a s e m e n to ft h ec o m p l e x i t y k e yw o r d s ：c e l l u l a ra u t o m a t a , c e l l u l a rp r o g r a m m i n g ，s t r e a mc i p h e l i v 目录 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：杰a 璐柱 日期：螂年f1 月7 7 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅， 有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方 法保存学位论文。 学位论文作者签名：胡粥垃 导师签名：他蚝冲牟 1 日期：沙眸，f 月f 7 日 中山大学硕士学位论文基于细胞自动机的流密码设计 1 1 密码学 第1 章绪论 密码学的研究与应用在人类历史长河中已有几千年，在这几千年中大致经历 了三个发展阶段：古代加密方法、古典密码、近代密码。 根据史书和石刻中的记载，各个古文明在实践的过程中都发明了他们自己的 密码系统，例如古埃及的象形文字替换，古希腊的隐写术、斯巴达人的s c y t a l e 加密工具等等。三千年前的古埃及，人们为了记载历朝历代法老们的丰功伟绩， 使用一些无意义的符号来替代平常使用的象形文字，通过有目的得对这些象形文 字的替代，从而对信息达到加密的目的，这就是密码学的起源。而在公元前4 0 0 多年的古希腊战争中，情报的发送者为了安全得传送军事情报，将奴隶的头发全 部剔掉，然后在奴隶的头上记录情报的内容，等到头发长齐就将该奴隶送到另一 个部落再次剃光头发，原来的情报就可以显露出来，从而在部落之间实现秘密通 信，这就是隐写术。公元五世纪，斯巴达人发明了一种加密方法，这是移位加密 的雏形，信息的发送者将一羊皮条缠满一木棍，然后自上而下书记录信息，写完 后把羊皮条解开，就只能看见一组记有无意义字母串的羊皮条，这样就可以达到 记录信件保密的目的。收件人只需要用一根同样直径的木棍，把这根羊皮条缠上， 就可获得信件的原始内容，当时斯巴达人称之为“天书 。在四大文明古国中的 中国、印度、巴比仑，同样也都流传这种类似的信息加密方法。所有这些“加密 方法，都有着一个共同的特征：利用一些非规则的无用符号来代替所有可读的信 息，从而达到加密的目的。这些加密方法和技巧，虽然看起来非常原始和简单， 但它们却奠定了古典密码技术的基础。在而后的将近二十个世纪中，其他所有的 加密方法都是通过对这些加密方法进行变形或者是组合而成。 随着所加密信息日益增加，范围日益扩大，密码信息的传递、交互都对信息 保密的质量提出了越来越高的要求。在日常的应用中，一些有规则的加密方法和 简单的加密原理逐步被人们发现，这些方法是今天所称为的古典密码。 古典密码是近代密码体制的雏形，它的加密一般通过采用手工或机械变换的 方式进行文字置换，比古代加密方法更为复杂。典型的古典密码有：移位密码、 第1 章绪论 代换密码、仿射密码、维吉尼亚密码、希尔密码与置换密码。在1 9 1 7 年，m a j o r j o s e p hm a u b o r g n e 和a t & t 公司的g i l b e r tv e m a m 发明了一种安全性很理想的加密 方案，叫做一次一密乱码本。实质上，一次一密乱码本不过是一个足够大的无法 预测的真随机密钥字母集，这个密钥字母集按顺序被记录在纸上，从而组成一个 乱码本。它的最初应用是在电传打字机，发送者按照顺序使用乱码本中的每一密 钥字符加密对应的一个明文字符，加密算法是让明文字符和密码本中的对应密钥 进行模2 5 6 j j l l 法，一次一密乱码本中的密钥仅使用一次。当发送者对所发送的消 息加密后，立即销毁密码本中使用过的密钥文本。接收者有一个一模一样的乱码 本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息 后也立即销毁乱码本中使用过的密钥文本。 一次一密乱码本在理论上是一个完全保密体制，也就是说，无论密码分析者 拥有多么大的计算能力，他都不可以通过可以利用的信息对密文进行解密。但是 它在使用上具有很大的局限性，第一，它要求有一个长度不小于明文长度的完全 随机密钥，用这样的密钥来加密明文，而且密钥中的一个字符只能使用一次，不 准重复使用。第二，信息的收发双方必须使用一个完全相同的密码本，这使得密 码本的传送相当困难。 一次一密乱码本的出现，使得许多密码学家都试图寻找一个类似的完善保 密体制，但一直没有成功。到了二十世纪五十年代，一部分密码研究者放弃了“寻 找一个完善保密体制 的企图，他们开始充分利用自己所占有的计算资源，尝试 设计一个好的加密方法，使加密和解密都十分方便。但是，对所有的密码分析员 来说，即使他们能窃取到一部分明密文对，甚至能获得唯一解的信息，不过， 由于他们不具备相应的计算资源、不了解该加密算法的特性或者无法获得有关解 密的密钥，从而使他们无法在规定的时间内、在所具备的计算资源内解密密文。 这种有别于“完善保密体制 的方法，通常被称为“计算保密体制”。 根据这种设计思想，密码学家逐步发明了对称密码体制( 私钥密码体制) 和非 对称密码体制( 公钥密码体制) 这两种密码体制。所谓对称密码体制就是指收发双 方在加密或者解密时都采用相同的密钥，而非对称密码体制指收发双方采用不同 的密钥，比如发方采用收方的公钥进行加密，而收方利用自己的私钥进行解密。 对称密码体制又可分为分组加密体制和流密码体制。分组加密体制中较典型 2 中山大学硕士学位论文 基于细胞自动机的流密码设计 的有d e s 、i d e a 、f e a l 、a e s 等加密方法。 同时，也提出了很多的流密码算法，比如：基于编码学理论和方法上提出的 序列加密算法，前馈或后馈移位寄存器的加密算法，以及利用噪声隐蔽技术的伪 随机数加密算法等等【1 1 。 1 2 细胞自动机 1 2 1 细胞自动机的起源 细胞自动机的概念最早是由j v o nn e u m a n n 提出的，1 9 4 8 年，j v o nn e u m a n n 在研究具有怎样的逻辑组织结构的自动机具有通用图灵机那样的自我复制特性 的问题时，j v o nn e u m a n n 设计了一种二维细胞自动机结构以建立一个具有自我 复制特性和通用计算能力的细胞自动机模型，这种细胞自动机中每个细胞具有2 9 个可能状态【2 】。后来c o d d 对这种细胞自动机模型进行了简化，将2 9 状态细胞自动 机简化成8 状态细胞自动机细胞自动机以建立一个具有自我复制特性和通用计算 能力的细胞自动机模型【3 】。但是，由于这种细胞自动机模型过于复杂，以至于其 物理实现难以完成【4 】。j v o nn e u m a n n 逝世后，许多人继承了他的研究，最后由 a w b u r k s 改进了j y o nn e u m a n n 模型，并且对这种具有自我复制特性和通用计算 能力的细胞自动机模型进行了物理实现。早期的细胞自动机由于较为复杂，研究 主要停留在理论方面【5 】，在应用上受到了其本身复杂性的限制，仅仅用来模拟诸 如物理、化学、生物、经济等自然过程模型以及用来建立并行计算模型的算法模 型以及研究模式识别和复杂性理论等方面【6 】。 2 0 世纪8 0 年代初，s w o l f r a m 提出一种简化了的细胞自动机，他对细胞自动 机的状态空间和邻域半径进行了简化并将其应用于密码学，从而开创了细胞自动 机研究的新纪元。这种细胞自动机具有以下优点：组成单元结构简单规则性、单 元之间作用的局部互连性和信息处理的高度并行性。并且他提出了具有两个状 态、邻域半径为一的基本细胞自动机 7 1 。简化后的细胞自动机非常适合于v l s i 实现，有利于信息并行处理，而且能够通过简单的模型模拟复杂的现象。 s w o l f r a m 对细胞自动机的简化极大的推动了细胞自动机在理论研究和实际应用 上的发展。 第1 章绪论 1 2 2 细胞自动机的优点 随着集成电路的发展，电子电路的集成度越来越高，在对功能的复杂性和性 能的卓越性要求方面也越来越高，这便对硬件系统的设计提出了越来越高的要 求。在对系统设计进行简化的同时，一方面需要尽可能得提高系统的集成度，从 而将实现特定功能的部件数降为最小，甚至使用一块集成芯片实现一个子系统或 系统，这便是片上系统s o c ( s y s t e mo ns h i p ) 的思想，只需针对某一功能的片上 系统进行精心设计，从而简化整个系统设计的复杂性【8 】。另一方面一个系统的实 现均需要按照规范的体系结构，以使系统的设计更加简洁。 细胞自动机具有组成单元结构的简单性、单元之间作用的局部性和信息处理 的高度并行性，这使得其尤其适合于v l s i 实现，而由于密码算法对外界的不可 访问性【9 】要求使得在硬件上实现加密算法成为最佳的实现方式。同时，细胞自动 机单元并行结构可以带来信息处理的并行性【l 叫1 1 ，从而极大提高了实现系统的 性能。这使得细胞自动机在几乎不增加系统复杂度的条件下比线性反馈移位寄存 器l f s r 具有更高的处理速度和更好的性能。p h t s a l i d e s 等人比较了两个6 阶内置 逻辑块观察器系统，它们分别由线性反馈移位寄存器和细胞自动机所实现，细胞 自动机实现的速率为5 5 m 而线性反馈移位积存器实现的速率只有3 3 m ( 工艺为2 微米n c m o s ) 1 2 】。细胞自动机所具有的优势和系统的规模成正比，这是因为线 性反馈移位寄存器的速率与其长度成反比【1 3 1 。所以，对于系统的v l s i 实现，细 胞自动机是一种比较理想的方法【1 4 1 6 j 。 1 2 3 细胞自动机的研究现状 在细胞自动机的概念提出之初，对其的研究主要集中在细胞自动机的可逆 性。1 9 6 2 年，e f m o o r e 证明了一个g a r d e no fe d e n 定理【1 7 】：若在细胞自动机的 状态映射中存在多对一映射时，那么便存在不具有向前的状态的伊甸园( g a r d e n o f e d e n ) ，并且细胞自动机不可逆。1 9 6 3 年，j m y h i l l 证明了【1 8 】：“若有限细胞 自动机的全局状态映射为单射那么其必然是满射。在1 9 7 2 年，d r i c h a r d s o n 证 明了：“若细胞自动机的所有状态映射都为单射，那么其必然可逆，并且可逆细 4 中山大学硕士学位论文基于细胞自动机的流密码设计 胞自动机的逆仍然是可逆细胞自动机”【1 9 1 。1 9 7 4 年，s a m o r o s o 等人证明了存 在一种利用一维细胞自动机的邻域函数规则确定其可逆性的算法【2 0 1 ，随后j k a r i 证明了不能由邻域函数确定二维细胞自动机的可逆性 2 1 - , - 2 2 】。后来学者们逐渐转 向对某一类细胞自动机的可逆性进行研究，1 9 8 8 年，p a l a s hs a r k a r - 等人设计了一 种构造9 0 1 5 0 可逆细胞自动机的算法。 在二十世纪八十年代初期s w o l f r a m 提出简化了的细胞自动机后，对细胞自 动机的研究转移到对状态转移函数的研究。由于只有加性细胞自动机才具有可分 析的代数结构【2 ”，因此研究人员开始对加性细胞自动机的状态转移结构使用多 项式方法和矩阵方法进行研究。z 2 空间上的细胞自动机是一种广泛用于研究和应 用的一类细胞自动机，这不仅是因为它的简单性最适合v l s i 实现，而且z 2 空间 上的细胞自动机具有最大的并行度【2 4 1 。 1 9 8 3 年，s w o l f r a m 率先提出了对一维、线性、单一基本细胞自动机使用多 项式方法进行分析2 5 1 。19 8 4 年，o l i v i e rm a r t i n 等人使用有限域上的多项式方澄 研究了循环边界条件单一基本细胞自动机的可逆性、状态可达性和状态结构等统 计特性【2 6 】。1 9 8 6 年，w e m e rp r i e s 等人使用有限域上的多项式方法分析了线性孽。l 单一、基本细胞自动机的状态转移群特性【2 3 】。1 9 8 6 年，p g u a n 等使用循环矩阵对 循环边界条件的线性、单一细胞自动机进行了分析，并得到其可逆的条件2 7 1 。 1 9 9 3 年，b k k a r 等人在有限域上的多项式方法上，利用线性细胞自动机的生成 函数写出了经过任意t 次迭代后的状态转移闭合式，从而可以根据状态转移闭合 式直接计算细胞自动机t 次迭代后的全局状态 2 8 】。 虽然可以通过有限域上的多项式方法对一维、线性、单一细胞自动机进行有 效分析，但是对于更为广泛的混合细胞自动机分析，有限域上的多项式方法却无 能为力。为了分析一维、加性、混合细胞自动机，1 9 9 0 年a l o k ek d a s 等人提出 使用状态转移矩阵对一维、线性混合细胞自动机进行分析，从而利用细胞自动机 状态转移矩阵的特征多项式来间接得分析一维、加性、混合细胞自动机的状态转 移特性，这便是细胞自动机的矩阵分析方法【2 9 1 。 1 9 8 9 年，n p i t s i a n i s 等人利用细胞自动机的矩阵分析方法对规贝, t j l 5 0 的零边界 基本细胞自动机的群特性进行了分析【3 0 1 。1 9 9 2 年，a l o k ek d a s 等人提出了向量 空间理论方法来分析线性、单一基本细胞自动机的群特性和可达性等统计特性 5 第l 章绪论 【3 1 1 。1 9 9 2 年，a l o k ek d a s 等人提出了使用特征矩阵和特征多项式对周期边界条 件线性细胞自动机的状态转移特性进行分析【3 2 1 。1 9 9 3 年，j o h ng s t e v e n s 等人使 用细胞自动机状态转移矩阵的特征多项式方法研究了零边界条件的线性细胞自 动机的瞬时和周期状态转移特性【3 3 1 。1 9 9 3 年，s h i n i c h it a d a k i 等根据状态转移矩 阵的特征多项式对规则9 0 循环边界条件细胞自动机的状态转移特性进行了分析 【3 4 1 。1 9 9 3 年，d r o yc h o w d h u r y 等将一维、线性细胞自动机的状态转移矩阵分析 方法应用于二维、线性细胞自动机的分析，并分析了垂直邻居受限的二维、线性 细胞自动机的群特性【3 5 1 。1 9 9 8 年，p o hy o n gk o h 等使用细胞自动机状态转移矩 阵的特征多项式方法对任意边界条件的9 0 1 5 0 混合细胞自动机进行了研究，并归 纳出了固定边界条件与零边界条件下细胞自动机的特性多项式之间的关系【3 6 1 。 1 2 4 细胞自动机应用研究 细胞自动机在应用上的研究主要集中在以下几个方面：细胞自动机并行计算 模型、细胞自动机自然世界模拟模型、细胞自动机社会模拟模型、细胞自动机在 内建自测试中的应用，以及细胞自动机在密码学中的应用等，本文的研究主要集 中于细胞自动机在密码学中的应用。其中，细胞自动机在密码学中的应用包括细 胞自动机伪随机数生成法、细胞自动机分组加密方法、细胞自动机h a s h 函数法 和细胞自动机公钥加密法等。 由于细胞自动机局部的变化能带来复杂的全局变化，所以非常适合于用来产 生伪随机序列。1 9 8 5 年的美洲密码学年会上，s w o l f r a m 首次提出了将细胞自动 机的初始状态和状态变换规则作为密钥种子，使用细胞自动机演化产生的伪随机 序列作为流密码的密钥流【3 7 1 ，从而开创了细胞自动机在密码学应用的新篇章， 但是这种方法不能保证产生伪随机序列能够达到最大周期。1 9 8 9 年，p e t e r d h o r t e n s i u s 提出利用具有m 序列特性的细胞自动机迭代产生伪随机序列【3 8 j ； 1 9 9 4 年，s n a n d i 提出利用可编程细胞自动机和存储单元来进行流密码加密和分 组加密【3 9 1 ；1 9 9 7 年，d o l o r e sd el ag 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 方法进行了扩展，他们 加入了存储单元以避免细胞自动机过早的进入状态循环，但是这种方法同样无法 6 中山大学硕士学位论文基于细胞自动机的流密码设计 保证伪随机序列能达到最大周蝌删。19 9 8 年，m i o d r a gm i h a l j c v i c 等提出使用g f ( q ) 上的线性可变成细胞自动机产生伪随机序列的方法【4 2 1 。 除了细胞自动机可以在伪随机数发生器方面获得应用，同时也可以应用于对 称加密。1 9 9 4 年，根据细胞自动机的循环群特性，s n a n d i 等人提出了一种基于 细胞自动机的分组加密技术【4 3 】。1 9 9 5 年，b s r i s u c h i n 等人提出用非线性细胞自动 机构造f e i s t e l 型密码中的非线性函数，并将另一个线性细胞自动机每一时间步的 输出作为分组数据的加密密钥 4 4 1 。1 9 9 6 年，l a f c ，o 首次提出一种细胞自动机变 换的概念，并提出了利用细胞自动机变换进行加密【4 5 1 。2 0 0 2 年，c h a n gn z h a n g 等实现了s n a n d i 等人提出的基于置换群基本变换的分组加密技术】。 对于h a s h 函数的研究。2 0 0 0 年，p r a b i rd a s g u p t a 等人提出了一种h a s h 函数 的方法，这种方法使用具有一个吸引子的二前向状态的细胞自动机【4 7 1 。由于复 杂系统的多项式方程求逆的困难性，p g u a n 在1 9 8 7 年提出了一种基于混合细胞自 动机的公钥加密技术【4 引。1 9 9 4 年，z h a n g , c n 提出了一种基于扩展可编程细胞自 动机的密钥交换算测4 9 1 。在2 0 0 0 年，d k b h a t t a c h a r r y y a 提出了一种基于细胞自 动机的密钥交换认证方法【5 0 】。 1 3 本文所做工作 1 提出了利用细胞编程寻找最优9 0 1 5 0 1 0 5 1 6 5 混合细胞自动机的方法。 由于9 0 1 5 0 1 0 5 1 6 5 混合细胞自动机产生序列的随机性能比一般细胞自动机产 生序列的随机性能要好，可以在m s i p p e r 提出的细胞编程基础上进行扩展以寻找 最优的9 0 1 5 0 1 0 5 1 6 5 混合细胞自动机，主要包括设定种群编码规则，并在这个 种群编码规则上，给出了特定的进化操作。实验结果表明：用这种方法发现的伪 随机数发生器产生的随机数具有良好的统计性能，通过了f i p s l 2 0 1 随机统计测 试。 2 将应用于非线性反馈寄存器的几种流密码构造应用于细胞自动机，并对 这几种构造产生的结果进行了统计分析。通过几种基本的统计分析，我们认为利 用这些架构产生的流密码具有一定的密码强度。 7 第l 章绪论 1 4 论文的结构 本论文的组织结构和内容如下： 第1 章，概括介绍细胞自动机的研究背景、国内外的研究状况，并对本文所 做的工作作及整个论文的结构进行了说明。 第2 章，对细胞自动机基本理论、基本概念进行了介绍，并且讨论了细胞自 动机的多种分类以及细胞自动机的特点。 第3 章，首先引出了广泛用于检验随机性的f i p s l 4 0 - 1 统计性随机测试，然后 介绍了m s i p p e r 的细胞编程，由于9 0 1 5 0 1 0 5 1 6 5 混合细胞自动机产生序列的随 机性能比一般细胞自动机产生序列的性能能要好，我们将细胞编程搜寻的范围缩 小到9 0 1 5 0 1 0 5 1 6 5 混合细胞自动机，并且对m s i p p e r 的细胞编程算法框架进行 了适当改进，其中包括改进种群编码规则，并在这个种群编码规则上，给出了专 门的进化操作。实验结果表明，该算法找到的最优9 0 1 5 0 1 0 5 1 6 5 混合细胞自动 机可以通过随机性统计测试。 第4 章，介绍了流密码的基本概念，由于单一细胞自动机产生的密钥流容易 被己知明文攻击所攻破，本文将几种用于线性反馈寄存器的流密码结构应用于细 胞自动机，并且对它们进行了实验研究，结果表明这几种流密码架构在增加密钥 流复杂性的同时并没有影响密钥流的随机性能。 第5 章，对论文所做的工作进行了总结，明确需要进一步研究的内容，同时 对自动机的应用前景进行了展望。 中山大学硕士学位论文基于细胞自动机的流密码设计 第2 章细胞自动机理论 细胞自动机( c e l l u l a r a u t o m a t a ) ，也常被译为元胞自动机、点格自动机， 它是一种在时间上和空间上都离散的动态系统。细胞自动机中每个细胞都分布在 规则网格中，每个细胞处于状态空间中的一种离散状态之中，各细胞下一时刻的 状态由该细胞当前时刻的状态和邻域内其他细胞的当前状态所决定。 2 1 细胞自动机 2 1 1 细胞自动机定义 细胞自动机是y o nn e u m a n n 和u l a m 在研究生物系统中的自组织与自复制现。 象时提出的一种空间和时间上离散的一类数学方法模型。细胞自动机把空间离散 为一些规则的点格，每个点格( 常称为细胞) 状态被定义为一个变量；所有细胞 的状态按离散的时间步并行演化，每个细胞状态在某个时间步的取值由该细胞和 其邻域细胞前一时间步状态值所决定。 细胞自动机在数学上可以看成一个四元组( 钆，z 。，f ，b ) ，其中舭表示细胞 自动机的d 维空间，z 。则代表空间状态，即细胞空间中每个细胞的可能状态集合， f r 表示状态转移函数，其中r 为邻域半径；b 表示边界条件，它设定了当邻域范 围超出了边界条件时的处理方法。如图2 一l 所示的二状态半径为一的一维细胞自 动机： io00l0o1 0o l o l l 0 1 10ool o0 1 l 00 l ol lol 图2 - 1 一维二状态细胞自动机 细胞自动机有三个显著性特性：大规模同步并行性、区域之间的相互作用性 和细胞结构的简单性。同步并行性是指在细胞空间中的各个细胞在时间步上的演 9 第2 章细胞自动机理论 化是同步并行的，它尤其适合于s i m d 型计算机系统；细胞作用的局域性使得细 胞自动机适合用于区域分裂算法。细胞的演化规则一般都比较简单，但其简单的 演化规则能表达复杂的行为，其复杂行为引起物理学家、化学家和生物学家的广 泛兴趣【5 1 】。 细胞自动机广泛应用于计算机科学、物理学、数学、生物等多种研究领域， 比如在计算机科学中，细胞自动机的演化常常用来模拟并行计算模型，细胞可以 看成并行计算机，另外细胞自动机还可应用于计算机图形学以及图象识别、图象 处理的研究中；在物理学中，细胞自动机可以看成离散、多维的动力学系统，广 泛应用于电场、磁场的模拟，以及热扩散、热传导、机械波传递的模拟；在数学 中，细胞自动机可以看成一描述连续现象的偏微分方程的对立体，是一个时空离 散的数学模型；在生物学中，细胞自动机可以用来描述病毒的感染、扩散过程。 2 1 2 细胞自动机的构成 ( 1 ) 细胞 细胞又常常称为元胞或单元，是细胞自动机的基本组成单位。细胞自动机由 许许多多分布在离散一维、二维或多维欧几里德空间的晶格点上的细胞所组成。 例如若使用细胞自动机来模拟网格计算，那么可以将整个网格抽象为一细胞自动 机，而每一个网格节点就可以看成一个细胞来进行分析；若在图象处理的研究中 使用细胞自动机进行模拟，那么可以将整个图象可以视为细胞自动机，图像编码 中的每一比特就可以看成一个细胞。在本文中，主要研究细胞自动机在密码学中 的应用，采用二进制编码，所以每个细胞可能的状态只有0 和1 两种。 ( 2 ) 细胞空间 细胞单元所分布的空间就是细胞空间，细胞空间的几何划分在理论上可以是 任意维数的欧几里德空间规则划分，常为一维、二维或三维，但由于复杂度的原 因，目前细胞自动机在密码学中的研究主要集中在一维和二维细胞自动机上。对 于一维细胞自动机，细胞空间的划分只有也只可能有一种，那就是一条向两边无 限延伸的直线；而对于二维细胞自动机，细胞空间可能为多种模型，最为常见的 二维细胞自动机的细胞空间通常有四方、三角或六边形这三种主要的空间模型。 如图2 - 2 、2 - 3 、2 - 4 所示： l o 中山大学硕士学位论文基于细胞自动机的流密码设计 图2 - 2 四方形网格图2 - 3 三角形网格 图2 - 4六边形网格 这三种细胞空间在性能上各有优缺点。三角网格的主要优点是拥有相对较少 的邻居数目，这使得其演化规则较为简单，其缺点是在计算机环境中表达与显示 不方便，需要转换为四方网格；四方网格的优点是直观而且简单，特别适合于模 拟大规模集群计算机系统，其缺点是模拟各向同性的现象时有所不足；六边形网 格的优点是能够较好地模拟各向同性的现象，表达的模型能更加自然而且真实， 但是它的缺点是较多的邻居数目，使得对其进行表达较为困难和复杂【5 。 ( 3 ) 邻域 邻域，即某一细胞的邻域，是指与该细胞相互影响的细胞集合，细胞的下一 时刻状态要由邻域中其他细胞的状态和其自身状态所决定。在细胞阵列中，邻域 通常是在物理位置上与指定细胞相邻或相近的细胞。在描述细胞自动机时，通常 以邻域半径来描述邻域范围，与中心细胞距离小于或等于邻域半径的细胞均在该 中心细胞邻域范围之内。在一维细胞自动机中，所有细胞单元等间距的分布在一 条直线上，邻域结构也比较简单，通常时中心细胞两边若干等数目的细胞；而对 于二维细胞自动机，其邻域定义较为复杂，但通常有以下几种形式，如图2 5 所 第2 章细胞自动机理论 示，其中黑色的为中心细胞，周围灰色的细胞为中一t l , 细胞的邻居，它们在一定的 转移函数下共同决定下一时刻中心细胞的状态。 a 1 r - 厂l 、一 ， y y i r o l ln e u m a n n 型邻居 一 l ，l 、 ，一 y 一 1，y ， 、 。i 鼍 二工工 一yy， if m o o r e 型邻居 1， r- 、 tj i 一 1，y c o l e 型邻居 ，y 4厂、 1，j ， 。l 。、 1rj m a g o l u s 型邻居s m i t h 型邻居 图2 5 二维细胞自动机模型 ( 4 ) 边界条件 细胞自动机在理论上的定义通常是在各维向上无限延伸，并且细胞单元的个 数也是无限的，这常常用于对细胞自动机在理论上的研究和推理。但是在实际应 1 2 中山大学硕士学位论文基于细胞自动机的流密码设计 用过程中，通常无法模拟无限的细胞空间，因此细胞单元的数目被指定为有限的， 细胞空间的范围也被限定在一个边界之内，采用较多的边界方法为以下三种类 型：周期型、反射型和定值型。 周期型是指边界细胞的边界邻居取该方向另一头的边界细胞。在一维细胞 空间，细胞自动机模型被连成了一个环。而二维空间中，细胞自动机模型被连成 了一个拓扑圆环面。如下图2 - 6 所示： 图2 6 周期边界条件模型 反射型是指边界细胞的边界处邻居的状态使用本身当前时刻状态所代替，就 像边界处邻居的细胞状态是通过以边界为轴的镜面反射过来一样。如在邻域半径 为一的一维细胞自动机当中，其反射型邻域如下图2 - 7 所示： 图2 - 7 反射型边界条件模型 定值型是指所有边界细胞的边界邻居取某一固定常量。如图2 - 8 所示： 图2 - 8 定值边界条件模型 2 2 基本细胞自动机表示 通常，我们将领域半径为l 的一维细胞自动机称为基本细胞自动机。为了精 确、有效得表达基本细胞自动机的局部转移函数，s t e p h e nw o l f r a m 给出了一种使 用规则号表示局部转移函数的方法。 第2 章细胞自动机理论 计算规则号6 的方法是：假设基本细胞自动机规则的状态映射是 f 7 = f ( 11 1 ) ， f s = f ( 11 0 ) ，f s = f ( 1 0 1 ) ，f 4 = f ( 1 0 0 ) ，f a = f ( 0 11 ) ，f 2 = f f o l o ) ，f l = f ( 0 0 1 ) ，f o = f ( o o o ) ，那么6 7 = ，2 称为该细胞自动机的规则号。如 f 7 f 6 f 5f 4f 3f 2f if o1 0 0 1 0 1 1 0 1 撕，对 i = 0 应规则号为1 5 0 ，其逻辑函数表达式为s 什1 i - - s i 1 + s t i + s t i + 1 , 其中+ 表示模2 加法( 即 异或) ，图2 - 9 为规则1 5 0 的邻域状态映射关系，其中黑色代表值为l 的细胞，白 色代表值为0 的细胞： 十 i 圜 1r 露圈 1r 曩_ 图2 - 9 规则1 5 0 的邻域状态映射关系 2 3 细胞自动机分类 圜 1 r 细胞自动机自j v o nn e u m a n n 和s t a n i s l a wu l a m 提出并由s w o l f r a m 改进简化 以来，其概念、结构和应用都发生了较大的变化，下面介绍细胞自动机的分类。 细胞自动机有多种，按照细胞单元的组成结构是否随其状态迭代而变化可分 为确定型细胞自动机和可编程细胞自动机，而确定型细胞自动机又可分为两种， 根据其组成结构分别为单一细胞自动机和混合细胞自动机。 确定性细胞自动机：状态转移函数规则不随其状态变化而变化的细胞自动机 为确定性细胞自动机【l o l 。 单一细胞自动机：所有细胞单元的状态转移函数规则都相同的细胞自动机为 单一细胞自动机或规则细胞自动机( u n i f o r mc e l l u l a ra u t o m a t a ) 【l o 】。单一细胞 自动机具有组成单元结构的简单规则性、单元之间作用的局部互连性和信息处理 的高度并行性等细胞自动机特点。 1 4 t 中山大学硕士学位论文基于细胞自动机的流密码设计 混合细胞自动机：各细胞状态转移函数规不一定相同的细胞自动机为混合细 胞自动机( h y b r i dc e l l u l a ra u t o m a t a ) 1 0 】。混合细胞自动机不仅具有单一细胞自 动机所拥有的各种特点，而且由于其组成规则顺序的多样性而使得细胞自动机具 有多样性。在实际应用中采用的细胞自动机多为混合细胞自动机，本文所使用的 细胞自动机均为确定性、混合细胞自动机，并使用其各细胞单元的规则号即邻域 函数规则的组成的向量来表示该细胞自动机，例如若使用( 1 3 0 ，1 0 5 ，3 4 ，1 5 0 ，6 0 ) 细 胞自动机表示一个5 单元混合确定型细胞自动机，其中第0 个单元为规, 贝t j l 3 0 、第1 个单元为规贝j j l 0 5 、第2 个单元为规贝j 3 4 、第3 个单元为规贝j j l 5 0 、第4 个单元为规 则6 0 ，并称其各细胞单元的规则号即邻域函数规则组合( 1 3 0 ，9 0 ，2 0 4 ，1 5 0 ，6 0 ) 为该 细胞自动机的规则向量。 可编程细胞自动机：状态转移函数规则随状态变化而变化的细胞自动机为可 编程细胞自动机( p r o g r a m m a b l ec e l l u l a ra u t o m a t a ) r i o 】。 可编程细胞自动机在确定性细胞自动机的基础上增加了一些复杂性的同时 获得了转移规则可变的细胞自动机，具有比确定性细胞自动机更多的种类、更复 杂的特性和更灵活的选择。 2 4 小结 细胞自动机能通过局部状态的演化实现整个系统的全局演化，其具有大规模 同步并行性、区域之间的相互作用性和细胞结构的简单性，并表现出复杂的全局 特征。细胞自动机的这些特点为细胞自动机的在密码学中的应用提供了良好的条 件，使它尤其适合于在加密技术中应用。 1 5 第3 章基于细胞编程的伪随机密钥流发生器 第3 章基于细胞编程的伪随机密钥流发生器 设计流密码的一个重要目标就是设计随机性能好的伪随机密钥流产生器，使 得密钥流发生器输出的密钥序列具有类似“掷般子 一样的完全随机特性，但在 实际中密钥序列不可能是完全随机的，只可能是伪随机的。 3 1 伪随机序列的检验 3 1 1g o l o m b 随机性假设 假定s 。，s 。，s 。是0 - 1 序列，用 s 。) 表示这一序列，若存在一整数t 使得， 对于任意的i ，s i + t - - - - s 。成立，则称 s 。 是周期性序列，满足上述关系的最小的t 叫做 s 。) 的周期。若序列( s 。) 除最开始若干项后的其余部分是周期序列，则此序 列称为准周期序列。在序列 s 。) 的一个周期中，若s , - 1 s 。= s 州= = s i - , s 饥则 称( s s ，s 。小。) 为序列的一个长为i 的游程。0 游程称为沟，1 游程称为块。 若序列 s 。) 为一个周期为n 的周期序列。s 的自相关函数c ( t ) 为一个自变量取整 数的函数且定义如下畸引： v l c ( f ) = l n x ( 2 s t - 1 ) ( 2 s i - 1 ) ，o t n 一1 ( 3 1 ) i = 0 为了度量周期为t 的0 - 1 伪随机序列的随机性，g o l o m b 对序列的随机性提 出下述三条假设，即g o l o m b 随机性假设瞄剁： ( 1 ) 若t 是奇数，则o 一1 序列 s 。 一个周期内0 的个数比1 的个数多1 或 少1 ；若t 是偶数，则0 的个数与l 的个数相等。 ( 2 ) 在序列的一个周期内，长为1 的游程数至少占游程总数的1 2 ，长为2 的游程数至少占游程总数的1 4 ，长为3 的游程数至少占游程总数的1 8 ， 且在等长的游程中，o 、1 游程各占一半。 ( 3 ) 序列的自相关函数是双值的。即对某个整数k ，有 c = 爹1 w) ：h j “(