（计算机应用技术专业论文）元胞自动机原理及其在密码学的应用研究.pdf

博上论文元胞自动原理及其在密码学的应用研究 摘要 随着信息化的迅速发展，信息安全的重要性与r 俱增，成为科技领域面临的严峻挑 战。密码学是信息安全的核心，鉴于其敏感性和特殊性，各国都在积极探索具有自主知 识产权的密码技术以保障国家和社会利益。元胞自动机固有的组成单元的简单性、单元 之间作用的局部性、信息处理的高度并行性以及全局的复杂性等特点，使其在密码学领 域中有着独特的优势，被认为是密码学自主化的重要核心技术之一。 本文在综述国内外元胞自动机密码技术的基础上，对可逆和不可逆两类元胞自动机 构造对称密码的方法进行了深入的研究，取得的主要研究成果和创新之处包括： ( 1 ) 提出了元胞自动机的交叉复合和随机复合思想，在对复合元胞自动机系统的 迭代特性进行初步分析的基础上，利用不可逆元胞自动机的反向迭代加密技术，构建了 两个基于复合元胞自动机的分组密码系统。仿真结果表明，复合元胞自动机密码系统很 好地解决了单一元胞自动机密码系统中存在的误差单向扩散的问题，并且能够以较小的 规则半径获得大密钥空间，减少了规则表的存储空间和迭代计算中的计算量。 ( 2 ) 提出了元胞自动机的耦合系数概念，构造了一个新的耦合元胞自动机模型， 并分析了耦合系数对耦合元胞自动机时空演化的影响。针对已有的单耦合元胞自动机加 密系统中存在的不足，设计了一个基于多耦合元胞自动机的加密算法。该算法将多个元 胞进行耦合，增强了两个元胞自动机之间的作用，扩大了相互影响的范围，使得误差扩 散更为快速。另外，从并行处理的角度出发，设计了一个耦合元胞自动机的并行加密模 型，其优点在于大大提高了加密解密速度，具有更好的实时性和普适性。 ( 3 ) 针对可逆元胞自动机数量稀少、寻找困难的问题，给出了一种可逆元胞自动 机的构造方法，并利用可逆元胞自动机无信息损失和高度并行处理的特性设计密码。另 外，通过引入规则表的名参数，对原本庞大的规则空间进行了划分，证明满足五= o 5 的 一类规则适合用于加密，有效地避免了弱规则对加密算法性能的影响。理论分析和计算 机仿真结果表明，这种基于可逆元胞自动机的加密算法比基于不可逆元胞自动机的加密 算法具有更快的加密速度和更大的密钥空间，并且不存在数据膨胀问题，适合处理信息 量大和实时性要求高的图片、视频和音频。 ( 4 ) 针对图像具有数据量大、冗余度高、相邻像素间相关性强等特点，提出了一 种基于二维可逆元胞自动机的多幅图像加密算法。该算法能够直接以二维的方式处理图 像，不需要进行二维转换到一维的预处理，提高了信息处理的效率和速度。在加密过程 中，由于采用了一种链式循环迭代的模式，使得每一幅图像的明文统计信息被完全隐藏 到其它所有密文图像中，明文图像和密文图像之间具有极其复杂的依赖关系。仿真实验 表明，与同类算法相比，本文算法的优点在于不需要对强相关的图像序列进行去相关预 摘要博士论文 处理，并且多幅解密图像的灰度值和顺序也不会发生变化。 关键词：元胞自动机，信息安全，密码学，分组密码，图像加密，反向迭代，规则表 i l a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , i n f o r m a t i o ns e c u r i t yh a sb e c 0 m e i n c r e a s i n 西yi i n p o r t 锄t ，a n db r o u g h th u g ec h a l l e n g e st o s c i e n t i f i cf i e l d a st h ek e r n e lo f m f o r m a t i o ns 锨l r i 劬c r y p t o g r a p h yi sf e a t u r e db yi t ss e n s i t i v i t ya n dp a r t i c u l a r i t y i n e w o t t h i s ，e a c l lc ( m n t 哆h a sb e e nl o o k i n gf o rs e l f - d e p e n d e n tt e c h n i q u e so ft h ec r y p t o g r a p h y t o g i l a 伽t e em e i rb e n e f i t s a n dg a i n s a m o n gv a r i o u st e c h n i q u e s ， c e l l u l a r咖a t o n1 s c o n s i d e 耐舔t h em o s ti m p o r t a n to n e t h i si sb e c a u s ec e l l u l a ra u t o m a t o np o s s e s al o to f i 1 1 l l 删tc _ h a r 积舐s t i c s ，s u c h 弱s i m p l er e g u l a rs t r u c t u r e ，l o c a l i n t e r a c t i o n ，m a s s l v ep a r a l l e l i - s i l l a n dc o m p l e xb e h a v i o rw h i c hm a k ei tag o o dc a n d i d a t et od e s i g nc r y p t o s y s t 锄 b a s e do n ar e v i e wo ft h ec 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 aa th o m ea n da b r o a d ，t h i s p a p e rd i s c u s s e sh e w t od e s i g ns y m m e t r i cc i p h e r su s i n gr e v e r s i b l ea n di 仃e v e r s i b l ec e l l u l a r a u t o m a t a t h em a i nc o n t r i b u t e so f t h i sp a p e ra l e 嬲f o l l o w s ： ( 1 ) t h ec o n c e p to f c r o s sc o m p o s i t i o nc e l l u l a ra u t o m a t aa n dr a n d o mc o m p o s i t i o n c e l l u l a r a u t o m a t ai sp r o p o s e d a f t e ra n a l y z i n gs o m eb a s i cp r o p e r t i e so ft h ec o m p o s i t es y s t e l i l ，姗 b l o c kc i p h e r sa r ec o n s t r u c t e db a s e do nc o m p o s i t i o nc e l l u l a ra u t o m a t ab ym e a n so f 1 n v e r s e i t e r a t i o n t h en e we n c r y p t i o ns y s t e m se f f e c t i v e l ys o l v e t h ep r o b l e mo fo n e 。w a ye 玎o r d i 肺s i o ni nas i n g l ec e l l u l a ra u t o m a t o ns y s t e ma n da c q u i r el a r g ek e ys p a c ew i t h s i n 毗lr u l e r a d i u s ( 2 ) b yp r o p o s i n gac o u p l i n gp a r a m e t e r , w ed e s i g nan e w m o d e lo fc o u p l i n ge e l l u l 缸 a u t o m a t aa n da n a l y z et h et i m e - s p a c ee v o l u t i o no fc o u p l i n gc e l l u l a ra u t o m a t a a st h e r e a r e s o m ed i s a d v a n t a g e so ft h ec i p h e l b a s e do ns i m p l ec o u p l i n gc e l l u l a ra u t o m a t a , w e 胂唧a n e w 锄c r y p t i o na l g o r i t h mb a s e do nm u l t i - c o u p l i n gc e l l u l a ra u t o m a t a t h e m e t h o do fc o u p l m g m a n vc e l l sc a l le n h a n c et h ei n t e r a c t i o nb e t w e e nt w oc e l l u l a ra u t o m a t a , a n dm a k e 龇锄r d i f 觚eq u i c k l y m o r e o v e r , w ep r o v i d eap a r a l l e le n c r y p t i o nm o d e lb a s e do nc o u p l e d c e l l u l a r a u t o m a t 巩w i l i c hn o to n l yi m p r o v e st h es p e e do fe n c r y p t i o na n dd e c r y p t i o n ，b u ta l s oh a s m u c h h i g h e rr e a l t i m ep e r f o r m a n c e a n dm o r es u i t a b i l i t y ( 3 ) c o n s i d e r i n gt h a tt h e r e 批f e wo n e - d i m e n s i o n a lr e v e r s i b l ec e l l u l a ra u t o m a t a a n dt l l 粥 i sn 0e 仃e c t i v ep c e d u r ef o rf i n d i n gh i g h - d i m e n s i o n a lr e v e r s i b l ec e l l u l a ra u t o m a t a , a m e t h o d o fc o n s 仃u 砸n gr e v e r s i b l ec e l l u l a ra u t o m a t a i sp r o p o s e d t h er e v e r s i b l ec e l l u l a ra u t o m a t a 躺 f c a t u r e db yt h e i rn oi n f o r m a t i o nl o s sa n dp a r a l l e li n f o r m a t i o np r o c e s s i n g , s 0 i ti ss m t a b i et o f u st 0d e s i 班c i p h e r i n s t e a do fu s i n gt h ew h o l er u l es p a c e 勰t h ek e y s p a c e ，t h ei 删a 1 9 0 n t 胁 i n t 川u c e sap a r 锄曲e r 九t op a r t i t i o nt h er u l es p a c ea n dp r o v e st h a tr u l e sw i t h l = 0 5 锄e i i i a b s t r a c t 博士论文 b e c o m i n gt oe n e r y p t c o m p a r e dw i t ht h eg e n e r a li r r e v e r s i b l et o g g l ec e l l u l a ra u t o m a t a c r y p t o s y s t e m ，t h ep r o p o s e dm e t h o dg r e a t l yi m p r o v e st h es p e e do fe n c r y p t i o na n dh a sl a r g e k e ys p a c e f u r t h e r m o r e ，t h e r ei s1 1 0d a t ai n f l a t i o ni no u rm e t h o d ，w h i c hm a k e si ts u i t a b l ef o r m u l t i m e d i ae n c r y p t i o ns u c ha si m a g e ，v i d e o ，s p e e c h ( 4 ) a c c o r d i n gt os o m ei n t r i n s i cf e a t u r e so fi m a g es u c ha sb u l kd a t ac a p a c i t y , h i g hd a t a r e d u n d a n c ya n ds t r o n gc o r r e l a t i o na m o n gp i x e l s ，am u l t i p l e - i m a g ee n e r y p t i o nb a s e do i l t w o - d i m e n s i o n a lr e v e r s i b l ec e l l u l a ra u t o m a t ai sp r e s e n t e d t h ea l g o r i t h mp e r m i t si m a g e st o b em a n a g e di nat w o d i m e n s i o n a lw a y , r a t h e rt h a nt r e a t i n gt h e ma sao n e - d i m e n s i o n a ld a t a s t r e a m ，w h i c hg r e a t l yi m p r o v e st h ee f f i c i e n c ya n dv e l o c i t yo ft h ea l g o r i t h m a sa c i r c u l a r - c h a i ni t e r a t i n gm o d ei sa d o p t e dd u r i n gt h ee n c r y p t i o n ，t h es t a t i s t i c a li n f o r m a t i o nf o r e a c hp l a i ni m a g ei sd i s s i p a t e dn o to n l yi n t ot h el o n g - r a n go fi t so w nc i p h e ri m a g e ，b u ta l s o i n t ot h eo t h e rc i p h e ri m a g e si nt h eg r o u p t h i sm a k e st h er e l a t i o n s h i pb e t w e e nt h ep l a i n i m a g e sa n dc i p h e ri m a g e sa sc o m p l e xa sp o s s i b l e s i m u l a t i o nr e s u l t ss h o wt h a tt h em a i n a d v a n t a g e so ft h ep r o p o s e da l g o r i t h mc o m p a r e dw i t ho t h e ra l g o r i t h m sa r ea sf o l l o w s ：f i r s t l y , t h e r ei sn on e e dt od e c o r r e l a t et h es t r o n g l yc o r r e l a t e di m a g e s s e c o n d l y , t h ep i x e lv a l u e sa n d o r d e ro fm ei m a g e sd o n tc h a n g e k e yw o r d ：c e l l u l a ra u t o m a t a , 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 , b l o c kc i p h e r , i m a g e e n c r y p t i o n ，i n v e r s ei t e r a t i o n , r u l et a b l e i v 博十论文元胞自动机原理及其在密码学的应用研究 图目录 图2 2 3 1 二维元胞空间的划分1 1 图2 2 3 2 通过扩展边界元胞获得的四种边界条件1 2 图2 2 4 1 一维元胞自动机的邻域1 3 图2 2 4 2 二维元胞自动机的三种邻域模型1 3 图2 2 4 3c o l e 型邻域和s m i t h 型邻域14 图2 3 2 1 规则3 0 初等元胞自动机的时空演化图1 6 图2 4 1 四类元胞自动机的时空演化图1 8 图3 2 1 1 有限元胞自动机的前向迭代轨道2 2 图3 2 2 1 交叉复合元胞自动机系统的前向迭代轨道( f i = 3 0 ，f 2 = 8 6 ) 2 3 图3 2 2 2 随机复合元胞自动机系统的前向迭代轨道( f l = 3 0 ，砣= 8 6 ) 2 4 图3 3 1 1 不可逆元胞自动机的构形转移图2 5 图3 3 1 2 构造构形c t r ) 的前驱c ( r 1 ) 2 6 图3 3 2 1 选择明文攻击恢复密钥。2 7 图3 5 4 1 明文敏感性统计分析3 2 图3 5 4 2 密钥敏感性统计分析3 3 图4 2 2 1 耦合元胞自动机系统的时空演化图3 6 图4 3 2 1 多耦合触发元胞自动机数据加密模型3 9 图4 3 2 2 多耦合触发元胞自动机数据解密模型3 9 图4 4 1 2 寄存器块的内部结构4 2 图4 4 2 1 耦合触发元胞自动机并行解密模型4 4 图4 4 4 1 迭代加密和并行加密运行时间对比4 8 图4 4 4 2 迭代解密和并行解密运行时间对比4 8 图5 2 1 1 一阶和二阶元胞自动机的演化示意图5 1 图5 2 1 2 二阶可逆元胞自动机的时空演化图5 2 图5 2 2 1 初等元胞自动机规则统计图5 4 图5 3 1 算法示意图5 5 图5 3 22 - t c a 结构5 6 图5 5 3 1a 参数对算法性能的影响6 0 图5 5 4 1 加密时间比较6 l 图6 2 1 1 不同半径的v o n n e u m a n n 型邻域和m o o r e 型邻域6 5 图6 2 2 2 可逆元胞自动机的构形转移图6 5 i x 图目录博士论文 图6 2 3 1 规则表的一维数组存储形式6 6 图6 2 4 12 dr c a 的前向迭代和反向迭代6 7 图6 3 12 dr c a 信息处理单元。6 8 图6 3 2 基于2 dr c a 的多幅图像加密模型6 9 图6 4 1 多幅图像加密解密的实验结果7 1 图6 5 2 1 1 密码系统的明文敏感性测试( 尸= 2 ，r = 1 ) 7 3 图6 5 2 2 1 密码系统的规则密钥敏感性测试( p 2 ，r = 1 ) 7 4 图6 5 2 2 2 密码系统的迭代数密钥敏感性测试( p = 2 ，r = 1 ) 7 5 x 博士论文 元胞自动机原理及其在密码学的应用研究 表目录 表2 3 1 1 元胞自动机的规则表1 5 表3 5 1 1 交叉复合t c a 密码系统的加密过程2 8 表3 5 1 2 交叉复合t c a 密码系统的解密过程2 9 表3 5 1 3 随机复合t c a 密码系统的加密过程2 9 表3 5 1 4 随机复合t c a 密码系统的解密过程2 9 表3 5 2 1 相同半径下的密钥空间比较3 0 表3 5 3 1 单一t c a 密码系统的误差扩散过程3 0 表3 5 3 2 交叉复合t c a 密码系统的误差扩散过程3 1 表3 5 3 3 随机复合t c a 密码系统的误差扩散过程3l 表4 3 1 1 单个明文误差的扩散一3 7 表4 3 1 2 规则3 0 和9 0 的真值表3 8 表4 3 3 1 1 多耦合触发元胞自动机中a 的加密过程4 0 表4 3 3 1 2 多耦合触发元胞自动机中b 的加密过程4 0 表4 3 3 1 3 多耦合触发元胞自动机中a 的解密过程4 0 表4 3 3 1 4 多耦合触发元胞自动机中b 的解密过程4 l 表4 3 3 2 1 单个明文误差的扩散4 1 表4 4 3 1 信息符号编码4 5 表4 3 3 2 元胞自动机a l 的并行加密过程4 6 表4 3 3 3 元胞自动机a 2 的并行加密过程4 6 表4 3 3 4 元胞自动机a 1 的并行解密过程4 7 表4 3 3 5 元胞自动机a 2 的并行解密过程4 7 表4 4 4 1 串行加密和并行加密运行时间对比表4 7 表4 4 4 2 迭代解密和并行解密运行时间对比表4 8 表5 3 1 12 - t c a 规则真值表5 6 表5 4 1 信息符号编码5 7 表5 4 22 t c a 加密过程5 8 表5 4 32 - t c a 解密过程5 8 表5 5 1 1 相同半径下的密钥空间比较5 9 表5 。5 2 1 单个明文误差的传播5 9 表5 5 2 2 密钥误差的传播6 0 表6 2 3 1 邻域为m o o r e 类型的2 一dr c a 的规则表6 6 表目录 博士论文 表6 5 2 1 1 密码系统的明文敏感性测试( 尸= 4 ，r = 2 ) 7 4 表6 5 2 2 1 密码系统的规则密钥敏感性测试( p - - 4 ，r - - 2 ) 7 5 表6 6 1 两个密码系统的复杂性比较7 6 x i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 砰 年j 胡垆 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 湖7 年x 月垆 博士论文元胞自动机原理及其在密码学的应用研究 1 绪论 1 1 研究背景与课题意义 2 0 世纪9 0 年代，以互联网为代表的信息化浪潮席卷全球，波及到政治、经济、文 化和军事等各个领域，对人们的生产、生活、工作和思维方式产生了深远的影响，对经 济发展和社会进步起到了积极的推动作用。信息逐步成为社会经济变革的重要战略资 源，信息化程度已成为衡量一个国家综合实力的重要标志。然而，由于信息和网络具有 开放性、无主管性，不设防性、缺少法律约束性等特点，使得在整个信息化进程中，信 息安全问题变得尤为突出。如何依托信息化提升综合国力，同时确保国家的信息安全， 已成为各国政府关心的热点问题。 1 1 1 信息安全的重要性 目前，全球网民数量已经突破1 0 亿大关，美国、日本、法国等发达国家的互联网 普及率都超过了5 0 。网络已经成为现代社会“无处不有、无所不用的工具，社会和 经济的发展对网络的依赖程度也越来越大，可以说整个人类社会的正常运转已经与网络 密不可分。然而，人们在享受网络带来的各种好处的同时，网络信息的安全问题也日渐 突出、形势只益严峻。一方面，计算机病毒层出不穷，垃圾邮件泛滥成灾。据统计，全 球恶意程序已经超过1 ，1 0 0 万个，以当前的增长速度，到2 0 1 5 年将会有2 3 3 亿恶意程 序，每小时会有2 6 ，5 9 8 个新病毒需要处理。全球垃圾邮件也再次呈增多趋势，目前日均 流量已达7 1 0 亿件，用户收到的电子邮件中近9 5 是垃圾邮件，造成了大量的传输、存 储和运算资源的浪费。另一方面，网络诈骗事件屡见不鲜，计算机犯罪日趋猖獗。2 0 0 7 年，美国网络诈骗投诉总计2 0 7 万起，诈骗得手金额累计2 3 9 亿美元，受害者多达5 7 万人。其中，银行等金融机构成为网络诈骗的“重灾区，仅英国网上银行诈骗损失就 达到7 6 5 0 万美元，而我国每隔三分钟就会发生一起网络诈骗案。在国际刑法界列举的 现代社会新型犯罪排行榜上，计算机犯罪名列榜首，每笔犯罪的平均金额为4 5 0 0 0 美元， 每年造成的经济损失高达5 0 亿美元【1 3 】。 针对严峻的信息安全形势，各国政府提高了对信息安全问题的重视程度，相继采取 了一系列的方法和措施，以确保信息系统的正常运转。美国接连颁发了多个重要信息安 全法规和总统令，包括改组信息安全管理机构，出台网络安全国家战略等。为防止 “网络9 1 l ”事件的发生，美国还建立首支网络黑客部队，严防网络恐怖袭击，并于2 0 0 7 年正式成立网军司令部。俄罗斯闻风而动，在制定了俄罗斯联邦信息安全学说这一 国家战略之后，又启动了 2 0 1 0 年俄罗斯信息化发展纲要，计划将信息网络安全纳入 国家安全战略，并采取逐步完善网络信息安全立法、建立网络信息安全保障体系等措施 1 绪论博士论文 维护国家的信息安全。日本政府也在加强预防和积极应对，不仅对信息通信网络安全 可靠标准进行了大幅度修改，而且公布了电子政务实施过程中的信息安全行动方案， 强调“信息安全保障是日本综合安全保障体系的核心”，采取多种措施以维护国家信息 安全。我国自上世纪9 0 年代初开始重视信息安全，颁布了“中华人民共和国计算机信 息系统安全保护条例 ，这是我国第一个计算机安全方面的法律，较全面地从法规角度 阐述了关于计算机信息系统安全相关的概念、内涵、管理、监督、责任。随后，又成立 了网络与信息安全协调小组，加强了信息安全保障体系的建设，制订了 2 0 0 6 - - - 2 0 2 0 年国家信息化发展战略，将信息安全和政治安全、经济安全、文化安全放在同等重要 的位置。可见，信息安全在未来的很长一段时间内，都将在各国政治上处于前所未有的 高度【4 】。 1 1 2 信息安全的特殊性 信息安全是一项特殊的系统工程，其研究更强调自主性和创新性。当前我国信息产 业正处于起步阶段，信息化技术严重依赖国外，从硬件到软件都不同程度地受制于人， 一旦出现特殊情况，后果就不堪设想。例如，微软黑屏事件，m s n 切断古巴朝鲜等五 国服务事件，以及美国限制联想p c 事件，都让我们清醒地认识到：只有民族的才是自 主的，只有自主的才是安全的。 我国政府明确规定严格禁止直接使用国外的密码算法和安全产品，这主要有两个原 因：一是国外禁止出口密码算法和产品，所谓出口的安全的密码算法国外都有破译手段， 二是国外的算法和产品中可能存在“后门 ，关键时刻危害我国安全【5 】。事实上，美国已 制订了耗资十多亿美元的计划，研究如何将病毒固化潜伏在出口的集成电脑中，一旦需 要，激活病毒，使对方电子信息系统全部失效。因此，我们一定要未雨绸缪，严防后患， 把基点放在自主创新上，把知识产权作为国家发展的重要战略内容之一，确保在国家基 础信息系统、重要信息系统的关键设备、信息安全产品使用自主知识产权的国产化产品。 只有这样，才能立足于信息安全的制高点，摆脱牵制，提升我国整个信息安全的核心竞 争力。 1 1 3 信息安全的概念 信息安全是一个广泛和抽象的概念。传统的信息安全是指信息系统的正常运行，防 止信息系统中信息丢失、泄露以及未授权访问、修改或者删除。根据国际标准化组织 ( i s o ) 和美国国家信息基础设施( n i i ) 的定义，信息安全主要包含信息的完整性、可 用性、保密性和可控性这四个方面【6 1 。 ( 1 ) 完整性( i n t e g r i t y ) ：完整性是指信息在存储或传输的过程中保持未经授权不能 改变的特性，即对抗主动攻击，保证数据的一致性，防止数据被非法用户修改和破坏。 ( 2 ) 可用性( a v a i l a b i l i t y ) ：可用性是指信息被授权者访问并按需求使用的特性，即 2 博上论文元胞自动机原理及其在密码学的应用研究 保证合法用户对信息和资源的使用不会被不合理地拒绝。 ( 3 ) 保密性( c o n f i d e n t i a l i t y ) ：保密性是指信息不被泄露给未经授权的特性，即对抗 被动攻击，以保证机密信息不会泄露给非法用户。 ( 4 ) 可控性( c o n t r o l l a b i l i t y ) ：可控性是指对信息的传播及内容具有控制能力的特性。 授权机构可以随时控制信息的机密性，能够对信息实施安全监控。 从学科的角度来看，信息安全是一个新兴的综合性交叉学科领域，它要综合利用数 学、物理、通信和计算机诸多学科的长期知识积累和最新发展成果，进行自主创新研究， 加强顶层设计，提出系统的、完整的、协同的解决方案。与其他学科相比，信息安全的 研究更强调自主性和创新性，自主可以避免“后门”，体现国家主权，而创新可以抵抗 各种攻击，适应技术发展的需求 7 1 。 1 1 4 信息安全的核心 密码学是信息安全的核心和关键技术，它不仅可以保证信息的机密性，而且可以保 证信息的完整性、确定性以及抗抵赖性【s l 。密码学主要由密码编码学和密码分析学两部 分组成，其中密码编码学的主要任务是研究对信息进行编码以实现信息隐藏，而密码分 析学主要是研究通过密文获取对应的明文。密码编码学与密码分析学既相互对立又相互 依存，正是由于这种对立统一关系，才推动了密码学自身的快速发展【9 】。 当前密码研究主要有两大趋势：基于数学计算的传统密码技术以及基于非数学计算 的密码技术。基于数学计算的传统密码技术属传统密码学，包括公钥密码、分组密码、 序列密码、认证码、数字签名、h a s h 函数、身份识别、密钥管理、p k i 技术、v p n 技 术等。基于数学计算的传统密码技术至今为止是信息机密性、完整性和不可否认性保障 的主要机制与核心内容，仍然在发展研究中。基非于数学计算的密码技术包括信息隐藏、 量子密码、基于生物特征的识别理论和技术等内容。总体来看，基于非数学计算的密码 技术当前还没有广泛应用，正处于探索尝试阶段。密码技术特别是加密技术是信息安全 技术中的核心技术，国家关键基础设施中不可能引进或采用别人的加密技术，只能自主 开发【1 0 1 。 在探索自主密码技术的过程中，元胞自动机固有的组成单元的简单性、单元之间作 用的局部性、信息处理的高度并行性以及全局的复杂性等特点【l l 】，使其在密码学领域中 有着独特的优势，被认为是密码学自主化的重要核心技术之一。 1 2 元胞自动机研究的历史与现状 1 2 1 元胞自动机的诞生 元胞自动机( c e l l u l a ra u t o m a t a ，简称c a ) 的概念最早是由数学家s t a n i s l a wu l a m 和j o h ny o nn e u m a n n 在2 0 世纪5 0 年代提出来的。它的诞生可以说是两种思想的结合， 3 1 绪论博士论文 其中“元胞 的思想来源于u l a m ，而“自动机 的思想来源于v o nn e u m a n n 。早在2 0 世纪4 0 年代，v o nn e u m a n n 就对人造机器能否自我复制的问题产生了浓厚的兴趣，并 试图构造一个具有自我复制特性和通用计算能力的简单机器。但由于当时人造机器部件 昂贵以及计算技术的限制，他不得不寻求一种数学抽象来完成自己的设想。在u l a m 的 建议下，v o nn e u m a n n 开始从元胞的视角考虑这个问题，他引入元胞以代替“机器部件 ， 构造了第一个能自我复制的元胞自动机模型。该元胞自动机是由分布在二维网格上的数 千个元胞组成，其中每个元胞有2 9 种可能的状态，局部演化规则依赖于每个元胞的状 态和4 个最近邻元胞( 即东南西北4 个相邻元胞) 的状态。尽管这个模型复杂到当时的 计算机无法模拟的程度，却在理论上证明了通用计算和自我复制的可能性。 在v o nn e u m a n n 逝世之后，a r t h u rb u r k s 编辑和扩展他的许多研究成果，并出版了 自我复制自动机理论和元胞自动机论文集这两本书【1 2 , 1 3 】。遵循相同的思路，1 9 6 8 年，c o d d t l 4 】利用8 种状态的二维元胞自动机实现了自我复制的特性，从而简化了v o n n e u m a n n 原先那种极其复杂的模型。后来，l a n g t o n 经过研究发现，v o nn e u m a n n 元胞 自动机所具备的计算通用性，在现存的自复制过程和已知的生命体中根本用不到，针对 于此，他舍弃了计算通用的特性，提出了一个简化模型：自我复制环，l a n g t o n 的自我 复制环【1 5 】是能够自我复制元胞自动机中最著名的一个。 1 2 2 元胞自动机发展的三个重要阶段 自v o nn e u m a n n 的开创性工作之后，元胞自动机经历了三个重要的发展阶段：第一， j o h nc o n w a y 编制的生命游戏引起了研究者对元胞自动机的广泛关注；第二，s t e p h e n w o l f r a m 对初等元胞自动机的分类奠定了元胞自动机理论的基石；第三，l a n g t o n 基于 对元胞自动机的深入研究提出了“人工生命的概念，直接促进和导致了复杂性科学的 出现。 ( 1 ) c o n w a y 时期的普及阶段。2 0 世纪7 0 年代，微型计算机的发展为元胞自动机 的模拟提供了基本条件。英国数学家j o h nc o n w a y 试图简化v o nn e u m a n n 的通用计算模 型，编制了一个名为“生命游戏”的计算机程序，并由m a r t i ng a r d n e r 刊登在( s c i e n t i f i c a m e r i c a n ) ) 杂志的“数学游戏”专栏1 6 1 7 】。这个生命游戏是一个具有两个状态( 生或死) 的二维元胞自动机，它的演化遵循以下规则：一个状态为“生”的元胞周围如果有2 个 或3 个元胞为“生时，则该元胞继续为“生”，否则为“死 ；一个状态为“死”的元 胞周围如果有3 个元胞为“生 ，则该元胞变为“生。尽管这个规则很简单，却能呈现 出变幻莫测的延伸、变形和停止等复杂的图案。c o n w a y 利用直观的游戏使人们充分认 识到简单的单元和简单的规则也能产生复杂现象和具备模拟复杂系统的能力，从而吸引 了一大批专家学者投入到生命游戏和元胞自动机的研究工作中来【1 3 _ 2 l 】。随后的研究也证 明了这种元胞自动机具有通用计算的能力，它与图灵机等价【翻。可以说，生命游戏的问 4 博上论文元胞自动机原理及其在密码学的应用研究 世开辟了元胞自动机研究的新篇章，并使元胞自动机的概念逐渐普及到其它相关领域。 ( 2 ) w o l f r a m 时期的理论阶段。2 0 世纪8 0 年代初，美国物理学家s t e p h e nw o l f r a m 对一维元胞自动机，尤其是初等元胞自动机的深入分析【2 3 - 2 6 ，使元胞自动机理论和应用 研究有了突破性的进展。他借用统计力学的概念和方法，并在大量计算机实验的基础上， 将所有元胞自动机的动力学行为归纳为四类，详细介绍可见本文2 4 章节。虽然这种分 类不是严格的数学分类，却是非常有意义的发现，对于元胞自动机的研究具有很大的指 导意义。它反映出这种分类方法可能具有某种普适性，很可能有许多物理系统或生命系 统可以按这样的分类方法来研刭2 7 1 。除此之外，w o l f r a m 首次将计算理论和形式语言方 法用于研究元胞自动机，得到了一系列有意义的结果，如证明了从所有可能的构型出发， 迭代有限步后总可以得到正规语言【2 8 1 ，这方面的综述可参考文献 2 9 3 0 】。2 0 0 2 年， w o l f r a m 花了十年心血撰写的一种新科学【3 l 】出版发行，该书在发行之后的一个星期 里，初版五万册就全部销售一空，并且高居网上书店“亚马逊”排行榜的榜首。w o l f r a m 在书中探讨了自然界中复杂性的起源问题，他认为“传统科学”未能建立起解释宇宙复 杂性的理论，靠数学方程做不到这一点，所以他要发动一场新的“科学革命”，革命的内 容就是要用简单的电脑程序取代数学方程，而这种简单的电脑程序就是元胞自动机。尽 管专家学者们对这本书的评价褒贬不一，但不可否认，w o l f r a m 的工作为元胞自动机理 论研究，以及后来的人工生命和近来兴起的复杂性科学研究作出了卓越的贡献。 ( 3 ) l a n g t o n 时期的衍生阶段。2 0 世纪9 0 年代，l a n g t o n 给元胞自动机的动力学 行为分类赋予了新的意义。他引进了一个参数兄以衡量元胞自动机的活动性，通过一系 列测试发现，随着参数名的变化，元胞自动机的行为从稳定态( 类型i ) 变化到周期态 ( 类型i i ) ，进而通过复杂态( 类型) 达到混沌态( 类型i i i ) 。这一现象使l a n g t o n 想 到了物理学中的相变，于是他把元胞自动机中