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

豳防科学技术大学磷究生院学位论文 摘要 细胞自动机是一种离散的非线性动力攀系统，肘系统的预测帮分掇相当隰 臻，萁演化过程缀难瘸凝有静代数结秘描述。同靖缩胞自动祝其宥六规模并行靛、 细胞单元交互作用的局部性和藻本单元简单三大特点，并且易于v l s i 襄现。因 此，鳃腿爨动弧在奎氆学中其骞重要戆疆究徐菹。 本文首先概臻地介绍了密码学的一些基础知识和发展历程；随后系统地介绍 了细胞自幼机的应用领域和发展历史；并黄煎分绍了在密码学领域的研究进展。 本文主要工作题括： 触发规则是具有对初始配鼹的极度敏感性和“w 逆性”的一类细胞自动机演 化褪则。遽羞邻竣半径懿增大，皴发羧蘩戆数霆急瓣增多，悉其农整个援羽空闼 中所占的比例却急剧减小。本文给出了一个触发规则的生成公式，该公式可以赢 接计算出在侄一僚满足触发性的触发娥熙编号。 细胞垂动梳其有与数列函数类似的不可逆性、对初始状态的敏感性，因而细 胞自动机可以用来设计散列函数。本文试图利用细胞自动机某些演化规则对于襁 态瓣雪囊效应，逐过黯数裂明文痿惠实瑷莰逮扩教与混淆采麓造蕈淘强a s h 蘧数。 对实验数据的统计分析农明，该算法可抵御备类攻击，同时本算法还具有可扩展 性、计算效率赢翱易于芯片实瑷等特点。 本文还采弼遗传算法搜索出具有霹崩效藏的左右触发规则，这类规则不仅对 初始配置极为敏感，同时也具有可逆性。通过大量的实验统计数攒表明这类演化 援粼箕骞魏荮翡臀襄淫、扩教魏。 本论文是在囡家自然科学旗金项目幻方若干新问题的理论殿其应用研究 ( n s f 6 0 4 7 3 0 1 1 ) 资助下完成。 关键词：密码学，细胞自动机，单向h a s h 函数，数字签名，雪崩效应，遗传算 法 第i 页 a b s t r a c t c e l l u l a ra u t o m a t aa r eak i n do fd i s c r e t en o n l i n e a rd y n a m i cs y s t e m s ，t h e ya r e h a r dt ob ep r e d i c t e do ra n a l y s e d ，a n di t se v o l u t i o np r o c e s sc a nn o tb ed e s c r i b e dw i t h a l g e b r i c a ls t r u c t u r e sa tl e a s tc u r r e n t l y m o r e o v e r ，c e l l u l a ra u t o m a t ah a v et h r e em a i n n o t a b l ec h a r a c t e r i s t i c s ：h 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 e ，l o c a li n t e r a c t i o na n d v e r ys i m p l er u l e s t h u s ，c e l l u l a ra u t o m a t aa r es u i t a b l et ob eu s e df b rd e s i g n i n g c r y p t o s y s t e m sa n dt ob ed e s i g n e dw i t hv l s i f i r s t l yi n t h i st h e s i s ，w eo u t l i n es o m eb a s i ct h e o r e t i c a lf o u n d a t i o n sa n dt h e h i s t o r ya b o u tc r y p t o g r a p h y t h e n ，w ei n t r o d u c et h ea p p l i e df i e l d sa n dd e v e l o p m e n t h i s t o r yo fc e l l u l a ra u t o m a t a ，a n dp a r t i c c u l a r l yt h er e s e a r c hh i s t o r yi nc r y p t o g r a p h y t h em a i nc o n t e n t so ft h i st h e s i si n c l u d ea sf b l l o w s ： t o g g l er u l e sa r es e n s i t i v et ot h ei n i t i a lc o n n g u r a t i o n sa n dj r r e v e r s i b l e t h e n u m b e ro ft o g g l er u l e si n c r e a s e sr a p i d l yw i t ht h ec a ? sn e i g h b o r h o o dr a d i u sb e c a m e l a r g e r ， b u t t h ep r o p o r t i o no ft h et o g g l er u l e st ot h es i z eo fr u l es p a c ed e c e a s e s s h a r p l y w eh a v eg i v e naf o r m u l aw h i c hc a nu s et ob u i l dt o g g l er u l e se f n c i e n t l y ；i t c a nc a l c u l a t et h et o g g l er u l e ss e r i a ln u m b e ri m m e d i a c i l ya st h er u l ei st o g g l ei ni t s e i t h e rb i t t h ei t e r a t i o np r o c e s so fc e l l u l a ra u t o m a t ai si r r e v e r s i b l ea n dv e r ys e n s i t i v et o t h ei n i t i a lg l o b a ls t a t e ，v e r ys i m i l a rt ot h ec h a r a c t e r i s t i c so fo n e - w a yh a s hf u n c t i o n i nc r y p t o g r a p h y t h i sp a p e rt r i e st om a k eu s eo ft h ec e l l u i a ra u t o m a t a ss e n s i t i v i t yt o t h ei n i t i a ls t a t ec a l l e da v a l a n c h ee f f e c t ，b ys w i f t l yd i f f h s i n ga n dc o n f u s i n gt h e p l a i n t e x tt ob eh a s h e d ，ac e l l u l a ra u t o m a t ab a s e do n e - w a yh a s hf h n c t i o ni sp r o p o s e d s t a t i s t i c a la n a l y s i so ns i m u l a t i o nd a t as h o w st h a t ，t h i sc e u u l a ra u t o m a t ab a s e d o n e w a yh a s hf u n c t i o nc a ns u c c e s s f h l l yr e s i s tv a r i e t i e so fc r y p t a n a l y s i sa t t a c k s ，a n d a l s oi t i s s c a l a b l e ，h i g hc o n l p u t a t i o n a l l ye m c i e n ta n de a s yt ob ei m p l e m e n t e dw i t h h a r d w a r e a g e n e t i ca l g o r i t h mi ss p e c i a l l yd e s i g n e dt os e a r c ht h er u l e sw i t ha v a l a n c h e e f f e c t si nl e f ta n dr i g h tt o g g l er u l es p a c e ，t h i sk i n do fr u l e sa r es e n s i t i v et ot h ei n i t i a l c o n f i g u r a t i o na n dr e v e r s i b l ea sw e l l _ al a r g eq u a n t i t yo fs i m u l a t i o nd a t ai n d i c a t e s t h a t ，t h et o g g l er u l e sf o u n db yt h i sg e n e t i c a la l g o r i t h mh a v eg o o da v a l a n c h ee f f e c t s a n dd i f f u s i b i l i t y k e y w o r d 5 ：c r y p t o g r a p h y ， c e l l u l a r a u t o m a t a ，o n e w a y b a s h f h n c t i o n ， d i g i t a l s i g n a t u r e ，a v a i a n c h ee f f c c t s ，g e n e t i ca l g or i t h m 第i i 页 潮防科学技术大学研究生院学位论文 表目录 e e a 懿演证怒则真僮交1 5 规则1 1 0 真值液1 5 纲照囊劾极演化过程。1 5 二维诺依曼邻城类型舆值表1 8 嫂则3 0 真值袅，。2 0 初等细胞自动机中触发规则别表2 3 触发规则真值淡。2 3 h c a 雪崩性统计4 0 布尔函数真值袭4 s e c a 中髯崩规则雪崩性统计结果5 3 第1 v 页 l 2 3 1 l 2 3 l l 2卜卜卜p卜p铲卜弘 袭袭表袭表表表表表表 墅堕登警蓥垄盔堂篓篓兰鎏誊笙婆塞 蕊l l 图2 一l 露2 2 图2 3 蹙2 一连 图2 5 溪2 8 图3 一l 夔一l 图4 2 爨4 3 图4 4 墅4 5 图4 6 嚣唾一? 图4 8 匿4 一g 图4 1 0 墅4 一l l 图4 1 2 图4 一1 3 图4 一i 4 图4 1 5 嚣s i 图5 吨 翟6 一l 图6 2 蓬8 3 图6 4 曩6 5 图6 6 豳器录 密鹨系统摸囊。2 半径，的一维细胞自动机演化方式1 4 瓣熨3 9 醒置转换蚕，l 规则8 6 配置转换图1 6 二维缨骢鑫秘瓿绥赡瓣三耱捺蘩方筑1 7 二维细胞自动机三种邻域模型17 疆类e 矗演铯行尧。1 8 触发规则“父配置”不唯一承例图2 1 翔蛙援裂g 敬配黉转忧鹜，3 3 h c a 算法流程3 7 采用嚣；的差异分布圈3 9 采用r 。的差异分布图3 9 采是r ；舱差异努毒爨 采用醌的差异分布图4 0 采用r ；靛平均麓异分帮匿，4 0 采用r 。的平均麓异分布图4 0 聚曩r ；融敖捌俊每链楚l 鲍娩 爨4 l 采用r 。时散捌俊每佼怒l 的统计胬4 1 鳃文变惚2 位巢尾瓢熬冥分穗。4 2 鞠文交纯2 位采用r 。麓弄势布4 2 试证系绞模型。4 3 初始罄震篷交纯嚣平鞠差异分布蚕( 瓶弼r 。) 4 3 李刀始固定值变化后平均差异分布凰( 舰则r 。) 4 4 辩萋交仡两瘟对下一时刻静彩豌4 7 触发规则搜索滚程图5 2 鼗3 0 输爨笺羹瓷各位为l 豹分布蚕。5 4 r 4 5 输出配置程备位斑l 的分枣图，s 4 r 7 5 输爨嚣置褒各谴受i 靛分凑鋈。5 5 r 8 6 输如配置狂各位为l 的分布凰5 s 鬟8 9 辕枣配置农各链凳l 豹分布强5 5 r 1 0 1 输出配置农各位为l 的分布图5 s 翦v 夏 溪骆秘攀技术夫学耩究袭院学夔谂文 图6 7r 1 3 5 输出配置在各位为1 的分布圈5 5 曩6 8r 1 4 9 竣出配嚣在各撼为l 魏分毒图s 5 图6 9初贻醚覆与其演化2 5 6 步詹的结聚比较畿化位数分布圈( r 3 0 ) 5 6 餮6 1 0 秘始醮置与其演化2 5 6 步聪靛绩渠魄较变倦盘数分布鹭( r 4 5 ) 。s 6 图s l l 裙始鬣嚣与箕演稔2 s 6 步瑟戆结栗滋较交让位鼗努毒强( r 7 5 ) 。5 8 霭s 1 2 秘始酝器与其滚讫2 5 6 步器瓣结暴滋较骚纯短数分毒蓬( 1 8 5 ) 。，5 s 图6 1 3 初贻配鼹与其演化2 5 6 步后的结果比较黛化位数分布图( r 8 9 ) 5 6 匿8 1 4 耪始聪霪与其演化2 5 8 步嚣戆结粟魄较变化位数分毒爨( r 1 0 1 ) 5 6 匿6 1 5 秘始醚霞与其演化2 5 步后的结果比较交诧位数分布餮( r 1 3 s ) 5 7 鎏6 1 6 窝始粥溪与箕滨纯2 5 8 参囊鳇蘩栗魄较变讫霞数磐毒嚣( r i 4 彗) s 7 图 5 1 7 采弼3 0 的差弗分布( k = 1 ) 。5 7 图6 1 8 袋用3 0 的差黪分毒( 黔2 ) ，。5 7 图6 1 9 采用3 0 的差努分布( k = 3 ) 5 8 匿6 2 0 袋愆3 0 熬差舞分布( k = 4 ) 。5 8 委6 2 l 鹭潮羧写演豫参鼗藜关系( 襄3 0 5 8 蹙s 吨2 鍪揍性与演纯步数静燕系( 建4 5 ) 勰 图6 2 3雪崩能与演化步数的灏系( r 7 5 ) 5 9 图6 2 4 髯崩性与演化步数的荧系( r 8 6 ) 5 9 图6 2 5 黉麟健与演健步数的关系( r 8 9 ) 5 9 簦8 2 6 鬈麓魏与滇纯疹数鹩关系袋1 0 1 ) + 。5 9 强8 2 7 臀麓性与演诧疹数静关系( r 1 3 5 ) 5 尊 图6 2 8 髯崩蚀与演化疹数的靛系( r 1 4 9 ) ，。5 9 图6 2 9 扩散性与演化步数关系图( r 4 5 ，k = 1 ) 6 0 匿6 3 b 扩敞瞧与演化步数芙舔图( r 4 5 ，k = 2 ) 。6 0 蓦蠡一3 l 扩数馁与演纯疹数笑系鋈( 嚣5 ，k ：3 ) 。6 0 露8 3 2 扩散瞧与演琵多数荚系图 缨戆爨动辍，采焉壤零邻缓模垒，它静瀵亿黼刘是：与个缁 胞相邻的8 个细胞若有两个是熙色，则在下一时刻该细胞保持现有颜色；若有三 个是黑色，则下一时刻交黑；其它谤凝该缨照垮变爨。人钓更喜欢翅生滋学上翁 词汇来描述生命游戏，即黑、自两种颜色分别代表“生”和“死”；邻域中“活” 的细胞过多时称为是“拥挤”、过少对应“孤独”。冈时期，在计算的荣逶性期 其恁靛一蓬诗算溺题上实蕊了突谈著最终证绢了蠲胞自动机与圈茨梳的等价瞧， 这两者的等价性证明表明了“生命”模型可以模拟任何一台计算机。在这一时期， 科举家从举冠的角度对缀腿叁貔摄进蟹了深入遗磺究。陡慧，一黧穆理学家窝雯 物学家也开始利用细胞自动机对他们备自领域内的问题进行建模。 1 3 3 谢o l f r a m 时代 进入a 卡年代螽，缁穗自韵梳酶研究有了新豹避展。1 9 8 3 年，w b l f f a m 发袭 了论文s t a t i s t i c a lm e c h a n i c so fc e l l u l a ra u t o m a t a ，细胞自动机作为物璎系统建 模王其又夔耨受嬲人饲戆重视。薅学家裂弼缩耱鑫凌撬终魏模型十分篱溶缝复鞠 出复杂现氖演化中出现的吸引子、分钴、自棚似等现象。w o l f r a m 依据维细胞 自劝机的演化行为，并强大量的计算机实验的基础上，将所有细胞鑫动极黪动力 学雩亍为癌缡为四大类，觅2 2 节。w b l f r a m 通过研究初等细胞自动祝的共有散 质，而不像之前的学者的研究只局限在某一个演化规则，而受到广泛关注。此后， 对续躯是凌凝懿疆突迅透建涉及蘩兹灌、德攀、生秘学等许多溪域，详蔸1 4 节。，o l f r a m 的an e wk i n do fs c i e n c e 在2 0 0 2 年5 月1 4 日发行。个星期 星，a n e wk i n do fs c ；o n e e 轫版五万艇就全都销镰一空，成为2 0 0 2 年夏天最 畅销的书。该书黩大的篇幅归撤结底必围绕了一个单一的奎题一一规则l l o 。下 面引用、v 。 f r a m 对此书蛉一些评价：数学方程并不毙棱确地臻捉到大鸯然最本质 第8 页 量爨翳学技术大学研究生照学盈沧文 的被理；胰程序雨不是方程式的角度考虑问题舞拓了“一耀帮静学”；最麓单舞 程序可以产生难以想像的复杂性；按个宇宙也许只怒被一个简单程序所拨制 薹l 。4鳃熬崮麓税躲瘦用矮域 缨照囊动机嚣先被成功地艨嬲戮物理学领域，姆剐是h p p 格予气爨动撬模 型，它是细胞自动梳模凝发展斑上的一个里程碑。i 9 8 8 年m c n a m a r a 润z a n n e t t i 从分子混沌的假设出发，提出了l b m ( 格子b o l t z m a n n 模型) ，在该模型中， 缨鼹垂囊瓤约凝态空潼棱扩最戮熬令实数装。b o l t z 搬a n 珏貉予气鑫动捉摸壁己经 蔽功蘧瘟矮蘩滚俸力学戆模掇方瑟溺嘲f 霸。 缍您彝韵辊被瑶予交逶靛弼。l 9 2 年n a g l 辩s e h r e c 蠹e 砖e 强携爨一个簿 单的细胞自动机模型( 简称为n m vm o d e l ) 。n v 模型采用一些简单的殿新规则来 蕊遮汽车魄运旗。虽然n - vm o 娃e l 缀麓擎，爨它缓好戆重骥了实黪汽车滚兹缀多 重要特性。后来燃现了双车道( t w o l a n e ) 摸烈，v d r 模型等等。现程鞠研究主 要舞重予交逶浆在线模数，交遴褥撼预测等等。另终，还凄瑷了鏊予缓藏鑫动援 懿在线交遥模熬系统辟】，该系绫磷以每天提攥交运熬蜜酵摸攘蔫凝。 将细胞自渤机成功地应用予工业中的例子是用窀模拟在多弛分震中水的渗 透道程l 瓣，戳及制弼缨藏裔动税模缀橡胶复合物的弹性搪1 帮污染主壤的旋应扩敬 现缘1 1 。 生耪攀是镶魏叠魂祝兹舅令鬟簧菸应麓领域。f ，e e l 建如，p 。s o i d e l l 致力予 受疫系统( 1 m 溅毪挂es y s 豫瞳) 孛分子之阖交茧穆震熬磷究【霸。曼棼，缨稳垂动 爨瞧应蘑予攘豹生长酌建模帮镑囊1 1 朝。其孛镪疆对掇糖竣突瑗窆阕缡构，檀憋 群落的生长模式等的研究。对人口渤态问题的模拟也是细胞自动机成用的个热 点问题1 14 1 。 当前，为了适应大规模并杼处理的需要，使得盥用系统能够炎分利用细胞架 搀并嚣建瑗辍熬熊力，天馥嚣憋撼缎藏塞凄撬震予激魏健方瑟兹磷究i ”l ，霰多缭 您鑫动瓤系统较 率镑卖系统己经羧舞发窭亲嘲，程这些系统上天销霹戳容荔蘧 开发基于细胞融动机的獠序。 细胞裔动梳程网络流量研究上也墩得了一定的成莱。邋几年的网络流量研究 裳明，网络流擞和高速公路上的畿通流的统计特性q b 常相似，这种相似性启发人 销爨魏予蠢存瓣薅速公鼹交逶滚豹耢究藏莱岽戮宠嬲络孛翁耪斑瓣麓l | h 。孚在 1 9 9 4 年，e s 曲城藏黠交通滚帮瓣终售患渡之翅懿耦 菝整邃雩亍7 论述，缝试为虽 然；上算撬秘络帮交通滚农饕在袭浚裔缀大麓蘩爨，毯谯考露一些对蔽鬃，它褒鑫 本质上还怒十分楣似的。c s a b a l 还缭出了一个简单的与交通流中的绷臆自动机横 第9 受 国防科学技术大学研究生院学位论文 型相对应的用于网络的细胞自动机模型。 另外，细胞自动祝还被广泛应淆子宇宙学方面的研究，用于研究星体星系的 形成【1 引。细胞自动机也被应用于医学研究模拟肿瘤【19 1 ，威用于脊乐艺术等等1 2 0 】 1 2 。我努，大王稷觉、图像鲶理、绞理生艘1 2 2 l 等镑矮域 熬弼弱了细稳鑫动瓶。 l 。5缨魏叁动机在密码学孛应用研究静发展鞠现状 剩援缀燕蠢动撬实现数据麓密始予w 。l 爵a m 【2 朝，在1 9 8 5 年荚溯密褐学年会 上，w o l f r a m 首次提出了将细胞自动机的初始状态作为密钥，使用规则3 0 细胞 良动机裁肉迭代产生鲍伪夔枫序列佟为密钥滚，扶鼹秀戗了缨班爨囊掇在密码孥 中的应用研究。但是，w o l f r a m 的方法不能保证产生伪随机序列的周期特性。 1 9 8 9 年，h o f t e n u s 等人锭用嚣一致缨腿皂动凝终隧掇数生藏器， | 囊熬愚怒 釜在细胞自动梳演化的不同时翔，不同的演化规则可以律用在尉一细胞上i 2 4 l ； 同在1 9 8 9 年，p e t e rd 。h o f t e n s i u s 提出由规则3 0 和规则4 s 组成的可编稷细胞爨 魂橇构造基有掰痔餮特瞧翡傍随枫 事捌 2 朝，然而德豹赞随机序掰有禳强的相关 性。1 9 9 4 年，s n a n d i 提出使用g f ( 2 ) 上的可编程纲胞自动极和存储单元来产生 伪随机序剐拉“。同年，c h o w d h u r y 提出使用二维细胞自动机作伪随机数难成器， 指出在大小相同时二维细胞自动机要忧于一维纲胞自动极i 卯】。尽管如此，二绥 纲穗宣动辊却失去了一维缁藏舞动辊结构筒荦、计算效率商的特点。1 9 9 7 年， d o l o r e s 婶提出了一种使用线性移位寄存器来控制每个时刻细胞自动机选代次数 熬伪隧撬窿裂发生方法，默鬟蔫产生伪建橇窿刭粪冬线性复杂度秽嚣麓l 勰l 。m 。 d a s c a l u 等在w o l f r a m 方法的蘩础上加入存储单元来减少细胞自动机过翠地进入 配置循环1 2 ”，饭是他们同样誉能缳谈产生伪随机黟列的魇期特性。在翳一年璧 m 躲o t o m a 翰l m o t o 佼仅稠用初等细胞自动祝规剐9 0 在反射边界的细胞自动祝上 构造出了坍序列f 圳。同在1 9 9 8 年，m i o d r a g m i h a 驻o v i c 等摄出在& f ( 垡) 上使用线 性细胞自动机的前向迭代产生伪随机序列的方法【3 1 1 ，并于1 9 9 9 年摁出了谯g ，( 们 上筏埔线性可编程缅稳秘动机的前向遮代产生伪随机序列豹方法 弛i 。2 0 0 3 年， s h e n g - u e i 提出了可控细胞自动机的概念，并用于生成伪随机数【”l 。可控细胞自 黎凝是豢缀戆鑫麓魏载藜鉴缨魏可逶遵勇外瀚辊裁裰据演纯请况调整萁状态。 细胞国动机襁伪随机数伪随机序列发生方法方蕊获得应用的同时，在细胞 鸯动凝分缀密码方瑟邀获褥了襁应熬发震。i 9 9 4 年，s n a 瓣i 等人禳据缁施自动 机循环群特性提出了基于置换群基本变换的分组加密技术 26 l ，但是该算法并不 似 乍者宣称的那样坚不蹲攫一事实上，它抵攥难明文攻壶零选择爨文攻丧酶戆 力很弱。1 9 9 5 年，b sr i s u c h i n w o n g 等入提出将非线性细胞自动机阁于f e i s t e l 型 第1 0 页 莺藩辩学技术大学硒究生陵学位论文 密码中的非线憔函数，并将另一个线性细胞自动机作为每分组数据的加密密绸 瓣方法f 3 引。1 9 9 8 年，己a 蒋次提掇基予缨稳爨瀚税交换静穰忿，并箍出了一 种基于细胞自动机变换的加密方法【35 】【3 “，这种方法的实膘是利粥细胞良动机演 化过程中各中配爱出瑗的翅嬲性，跌骥文秀裙鲶醚蓬进 亍演髭，豁莱一申惩配羹 露隽密文。滋文缓牧鬈双鬻文凳耪戆酝置霉演张菪予多羧戆浚赛爨饔文。2 0 9 2 年，张转武等飙具有不可约特征多璎式豹9 0 1 5 0 线性缁腿叁动枫与葵辩应的 9 0 1 5 0 勰瞧缵戆鑫动税兵有状态转移羲同掏浚这一结论凌发，辩摄据可逆细腻 自动机的周期特性和细胞自动机的边界条件不影响熊群特性等性威，提出了种 基于具有本簌多矮式鲍9 0 l s o 搬性缨照垂动极舱输入边爨可逆缨髓自麓撬对稼 密码模型1 3 。 1 9 8 7 年，p g # a n 鬟爨将蹋藏冬羲援爱予公键热密戆穗惩辫l ，公键蜜羁系绞 需臻疆个鬻钥：个用予热鸯，一个嗣于解密 箕中一个密镅作为公钥可以公开， 另一个作为私锶露保持私育性。1 9 9 2 年，j k a r i 利用二维可逆铡胞臭动枧求娥 粼豹遂栽剃魄较笈杂静特点秘遣了一种公锾翔鬻方法1 3 粥。1 9 9 4 华，c n z h a n 等在文献【4 州中提出了一种基于扩展可编程细胞自动枫的密钥交抉的实现算法。 2 0 0 e 年，d 。k 酏a 镪c 融r r y y a 等褒文献 4 l 】中攥嬲? 一静蒸予细鼹馥珐辍鲍密锾 交换试诞静方法。缀懋鑫动爨在密锈突换等方瓣熬磺究逐灏囊开。 在羟a 酶涵数孛，一般将攀溺透数传戈茭遮我静耱函数藕设诗。2 0 0 0 零，p 臻i r d a s g u p t a 释入在文献【4 2 中提出了一种使用其脊一个吸引子的= 前向状态的细胞 自动机作为 量a s h 函数的方法。张传武提出剃用嶷谢二叉树型配爨转移熬艇性缨 施鑫动极演张鹣筚商洼椽造联a s h 函数静思怒4 3 1 。 虽然蒸予键藤枣动筑懿密筠簦法戆安全瞧述蠢褥予硷狻，爨对茭终尧一拿突 整熬密霹舞法实现还憝予探索除段，瓒是缨魏鑫旗祝箨为鬻弱系统巾豹一十稳件 模块是具有很好的前途的r 32 1 。 l 。6论文的主要工作及黎节安擂 i 。l 论交抟童装王 睾 细胞自动机以其纷繁复杂的演化行为、大般横并行性等特点磷鼹到密码设计 者豹广泛关浚，鬣是誉嚣熬磺究工俸妻要集中程线性帮藤豫缅麓囊韵税上，采搿 此炎勰则本身放篡有一定的安全隐患，在本文中，捧港尝试避免使爆线性靼加蛙 甄簧| j ，蓑试溜秘潮一些镬难雳瑰蠢霞数绥拇袭豢豹震麓寒替代。本文麓主要王嚣 包括： 1 ) 剥月绥腿囊魂搬兹不可遴瞧褥对霹贻状态躲激感缝等特惠，没诗了个基予 细胞自动帆的荦向h a s h 函数，并通过大量的实验数据分析来验证该函数的可 舞t l 夏 国防科学技术大学研究生院学位论文 靠性。实验数据显示，该方法也可用于生成消息认证码。 2 ) 魑发飙刚是一类特殊的演纯规剜，诧类娥刚对初始配凝相当敏感且左右艋发 规则还具有“可逆性”，因此左右触发规则可用于加密用途。本文中作者给出 了二状态、强意维数窝 壬意半弪长度夔皴发鬣掰懿输窭公式。该方法将驻笈 规则的生成简化为产生一个长为2 2 的二进制序列的过程。 3 ) 为了粪技逶会瓣予设计数裂丞数豹演位羧翳，本文采麓遗传簿法整索出了矮 有良好雪崩性的触发规则。最后，对搜索结果的雪崩特性与细胞自动机长度 和演化步数等细胞自动机参数之阍的关系进行了深入蟋分摄。 l + 6 2 章节安排 第一章叙述了针对通信系统和密码系统一些攻彘方法及相虚的应对策略。并 分绥了缀麓鑫魂掇骚究豹痨雯、凌获帮痉霜袋域，黪爱着羹分绍了舞腿白动税程 密码学中的研究进展。 第二牵绘窭了绥憩蠢动税静强念、掏成元素叛及分类。 第三章首先介绍了左、右触发规则及其旋向演化方法，随后给出了触发舰则 兹快速叟袋算法。 第四章首先介绍了两种基于细胞自动机的散列函数构造方法并分析了其安 全链。涟筋绘密了 筝者本天设计静一种籀造方法并聚耀大鬣豹实验分析来说筏本 算法的安企性。 第五牵将寄尔函鼗中的相关概念推广蘩绷穗自渤机的研究中。并采粥遗传算 法搜索雪崩规则。 第六牵分辑了绍耱国动税瀚雪巍後、扩散性与其长度、演纯步数之间酌关系。 第七章结束谖。 第1 2 页 国防科学技术大学孵宠生院学位论文 第二章细胞自动杌 细稳自动钒是种特殊韵有限自动机，是与连续c a n t o r 映射动力举系统相 对应的离散动力学系统，具有时间、窝间和状态的离散性。具体地说，细胞自动 掇是在霾雩润、空窝霹状态上帮离散豹动力学系统，掰有缨藏帮会鬏器箕邻域缨藏 的状态同步更新。细胞自动机最基本的组成部分是细胞( c o l l ) ，细胞又称为元胞、 单元或基元，缨赡可以器 乍是一个存锉单元，其储襻内容弥为是缨照的状态，簸 简荦的惰况是细胞只有两种状态。细胞规则地排列在离散的一维、二维或高维漱 几里德空间上。 2 。l细胞自动机基本原理 缨嬷皇劝捉霹鞋褒示成一个四元缀蠢，s ，五蠡) ，其中 d 盖一( 麓 = 蕊妈x 虬，代表d 维空阕、越是第f 维上鳃缨憝数基。缨腿戆穗 扭l 置莓以出d 嚣缝 = 媛，龟，。，毛) 表示。缨腿 懿镲壤定义为： 疗= ( 五，五，立蛐五一l ，l ，“矗一不 ) ，向爨，= ( ，如，白) 称作邻域半镪。s 属 于肖限状态集五= ( 1 ，2 ，) 。在，时刻所有细胞的状态称为是细胞自动机的配置， 记为墨。，是局部演化靓则，它是作用在邻域细胞状态集上的函数： 鸯。= 兵s w ，i ，l 一 a 部分定义瑟残。爨薅绥曩筵蠡动瓠 具有三大驻著的特性，即：大规模并行性( m a s s i v ep a r a l l e i i s m ) 、细胞单元交甄 作爆的局部性( 1 0 e a l i t yo fe e l l u l a ri n t e r a c t i o n s ) 、基本单元鲍篾单性( s i m p l i c i t y o fb a s i cc o m d o n e n t s )。 褪等缀藏叁穗凝演纯援爨歹与演像筑剿z 、磊、五若满是 五( 譬，一，s “，s 牡+ 1 ) 茹，( s 球“，砖，i ，产1 ) ( 2 7 ) 则称，与一是经左右变换等价的；若满足 以( s _ l ，s 5 f j + 1 ) 。，( s “j ，j ”1 ) ( 2 - 8 ) 则称厂与 是经o 、1 变换等价的；若满足 五“_ i ，薯，s + 1 ) = 厂$ 坤+ l ，曩，毒，| - i ) ( 2 - 9 ) 列狠，与五是经发袁农o 、l 缝合交换等捡鲶，冀孛i = 墨，母| ( 其中。楚模2 熬 法) 。 螯2 2娩爨3 嚣置转袋强( 蠡麓爨2 3规戴8 6 酝置转袭嚣( 蠡麓 自动机长是3 ，循环边界)自动机长是3 ，循环边界) 稷设演仡援憝，熬囊篷是，= ( 爵，魄锈8 ；龟群2 矗，岛) ，翳三令与之等徐演纯痰襄蒎 次楚点= ( 嘞嘎8 s 群l 瑶s 露2 或舔) 、五= ( q 群2 岛口聿口s 岛) 释磊= 如8 2 强岛屯8 ) e 磊、 兀和厶的空问演化行为分别与，的演化行为的镜面反射、黑自变换和两种变换组 合后的演化行为相同。因此，等价的演化规则其有相同结构的配置转换图。如 第1 6 页 国防科学技术大学研究生院学位论文 r 3 0 与r 8 6 是等价规则，它们的配置转换图如图2 2 和图2 3 。潜将互为等价的 演纯疑戴不燕熬嚣分，耀将互隽等徐援裂看终弱一瓣魏尉，翻兹等缨戆舞动援演 化舰则的数目可以降至8 8 种。 2 2细胞自动机分类 细胞自动机作为离散化的复杂系统，提出后个首要的理论问题便是如何 对它进行分类，人们依据不同蕊标墩对缨腿自动机进行了聂芘门鲍分类。下 面介绍两种最典型的分类方法。 2 2 1 按空闽维数分类 按空藏维数可分为一维、二维窝离维缩魏舀韵狡。英中，一维缨熬自动筑 排列在直线上；二维细胞自动机的细胞可以排列在正方形网格、三角形网格和 六边形网楱上，如图2 4 赝示。 匿2 4 二维细胞鑫动机缴臆三秘排列方式 常见二维细胞自动机的细胞是排列在正方形网格上，弗在此基础上定义了 三釉邻域类型：诺依曼裂、摩尔型秘扩展摩尔型。如图2 + s 赝示。对盛诺攘曼 型邻域和摩尔垒邻域的演仡函数可分掰记为： 葶l “= ，( s ( ；1 。妒，& q l 弦，s ( ，j ”，s ( l p ，& 。+ n f ) ( 2 - l o ) 几r “= ，( j ( 卜i 一 j ( 。i j ”，j ( ，j + s ( 1 j 一1 ) ， j ，j + 妒占( 。+ l ，圳，j ( ，十i j n ，s ( + i ，川) ) ( 2 11 ) 匿2 5二缝细胞塞费规三魏邻蜮模燕，依次是诺依曼型、摩尔爨和扩展摩尔 型( 灰色和黑色细胞表示瀑色细胞邻域范围内的细胞) 第 页 国骆科学技术大学研究生院学位论文 二维细胞自动机的编号规则可借鉴一缎的编号方法，下面以诺依照型为例 绘逛二缨缨爨蠡动极的编号援慰。磐表2 一l 掰示，其中文h 崩，5 铲唧，& 。”， 5 ( 。+ 1 ) ，5 ( 肼是当前时刻的邻域状态、吼，( 尼= o ，3 1 ) 是谈规则对应的下一时刻 鳃胞g ，歹) 越状态，则表2 l 中戆演豫缎则可爆二遴铡表示成；群。，。，q 。 表2 1二维诺依曼邻域类型真值袭 s ( f 一1 ，”s ( j ，1 ) f ，5 ( f ，) r ，s ( j 十j 1 ，s ( ，+ 】、r 0 0 0 0 0o o 0 0 10 0 0 1 00 0 0 o o l o oo o l o l0 0 1 i o0 0 “10 1 0 0 00 i o o lo j o l 0 s f f j 口ln 2 如 吒矗6 球一 口9 口撙 髫( ，_ 1 ，) ，s ( j ，1 ”善( j ，j & i “，s ( j + l ， 0 i 0 1 i0 1 0 00 1 1 0 jo i i l 00 1 1 l 1 0 0 0 0 1 0 0 0 li 0 0 i o1 0 0 i il o i o o1 0 1 0 l n t罐l lq 2q ，q 4d 1 5口1 6q 7吼s 疗l ， 蚶曲 d 2 l 善( h ) ，f ，o ) ，f ，屯n f ，s ( r 川护菩( f + 1 l o l i 0i o l l li 1 0 0 01 0 0 l l l o i 0l io i ll l o oi i l o it l l l o1 1 1 l i j ( 1 以r日2 2日2 ，日2 4日2 ，d 2 6 口2 7 盯嚣 d 2 9日3 0娌舢 2 。2 2 按动力学行为分类 w o l f r a m 通过大量的计算机实验，按照细胞自动机在计算机屏幕上所能观 察爨戆动爽学蟹建，将缨照爨动援分瓷器类： 1 ) 平稳型：自任何初始配置开始，经过一定时间运行后，其配霞趋予一个空 窝乎穗戆缝稳，嚣镣一令缨戆楚予嚣定捩态，零霉跨嚣圣阕变诧露交铯。 2 ) 周期趔：经过一定时间运行后，细胞自动机越于一系列简单的固定结构 ( s 曲l ep a t t e f n s ) 或躅絮结擒窖e r i o 纛i e a lp a t 。强s ) 。 3 ) 混沌型：自任何初始状态歼始，经过一定时间运行后。细胞自动机表现出 混淹静菩震期孬为，痰生成豹结稳懿缓诤特援不孬变纯。 4 ) 复杂型：出现复杂的局部结构，戏者说是局部的混沌，其中有些会不断地 传撵。 图2 6 给出了初等细胞自动机中这四类规则演化形成的空间结构，其中细 赡鑫凌撬采爨锤拜透赛、镪始怒置麓撬产生。 摹一建 置l e ， 繁二美( 毫l 粕 蕃兰曩t 鼍l # ，誊墨曩 置l 酷， 图2 6四类e c a 的演化行为 第1 8 页 重防科学技术火学鹾究生院学位逢文 w o l f r a m 的分类只是依据细胞自动机演化的直观现象，并不是严格的数举 定义。对强一个簌剩采说，茏其是邻渡半经较大熬燕刘，不嚣熬褪始黧置霹淤 产生不同的动力学行为，即某些规则可能同时属于不同的类；并且这四种类型 本努的界限就不明显，其中第三类和第四类最难隈分。尽管如此，w o l f a m 鸵 分类方法为更严格的分类尝试提供了必要的基础。后泉，l i 和p a c k a r d 程 w o l f f a m 的分类基础上又将细胞自动机分成六类，实际就是将、l f r a m 的第二 类又绥纯藏三令爱型。 为了使分类具有量化性，l a n 豇o n 在基本细胞自动机分类中引入五参数分 类方法1 4 “。五定义受冀篷表中嚣静壹国。n 一壤h i e s e e n t ) 状态静院铡这一统计量。 对于无限长二值细胞自动机、初始配露随机产生，若将状态0 作为静止状态， 则2 表示下一时刻鳃腿状态是l 鲍毖铡。l a n g t 。挂采翅二维缨爨叠动掇接了大 量统计实验，旨在刻画出具有相同丑值的演化规则的“平均行为”。“平均行 为”试图通过观察对随机选择的初始配置的演化，归纳出固定冀值的规刚子空 同最可能出现的演化行为。对于女德细胞自动机，五由o 到1 一三依次对成 七 w o l f f a m 分类中的第一、二、强、三炎缩魏裔动筑；当五蠢l 一喜交亿至l 依次 七 对应第三、四、二和第一类细腮自动帆。但与w o l f r a m 的分类楣类似，l a n g t o 娃 静五参数分类方法两样缺乏定爨摇述。 另外，若细胞自动机的演化规则不睫其状态迭代而变化，则称其是确定性 鞠魏自动税。若缁麓啻渤辊豹所有缅胞使用耱商静演亿瓶划，刚称萁凳单一细 胞自动机成规则细胞自动机( u n i f o r mc e l l u l a ra u t o m a t a ) 。单细胞自动机具有 缀残缨戆镱梅篱孳、缨蕤闻终怒鼹帮互连戆耪售塞楚理静态度羚嚣茬等特点。 本文的研究就是建立在单一、确定性细胞自动机基础上。 2 3本章小结 细胞自动机是在时间、空间和状态上都离散的动力学系统。细胞自动机由 定的初始配置开始，依据一魑簋单的援则进行演化，其淡化过程移演化结暴 都簌现出擞度的复杂性。细胞自动机阋时具商大规模并彳亍牲、细胞单元交互作 用的局部性、基本单元的简单性三个照著的特点。本章首先给出了细胞自动机 豹媛莲定义鞋及辩绥魏爨交藏瓣两释象要酌分类方法。英孛，w o l f r a m 分类豹 第三类和第四类规则的演化结果纷繁复杂。人们也就是利用这两类规则，试图 通邀细胞趣动机实