（计算机应用技术专业论文）基于自动机理论的公钥密码学研究.pdf

南柬理工大学硕士论宠 蕊于自幼机理论的公钥密码学研究 攮簧 随嚣计爨机网络技术的发展，人们对瓤终传蝓数攒的安众性要求越来越聪。传 统的如滚体制使月同一个密镧进行烟、解寮，要求强健簸密文的圈辩选要将鬻钥抟 输绘接收者，这就增加了传瓣数据的不安全性。显然不太适台嘲络上秘密通僖的鼗 要。而公钥加密体制县有加、解密密钥分开，用公钥加密、私钥解密的特点，可以 解决传统加密体制所西弼的闯题。 有隰童渤耩公锱密弼怒我藿学者提岛鹩一释基子有限爨动梳可递澧豹公开密 镄密码。本文讨论基予膏限翻动撬理论鹣公锯糯密体制，蓄先奔缁t 强骜琶蠢靛脊 限彝动机加密冀法，并对已谢的鼹萋申算法避穹亍了改进。然后将复会加密理论瓤露鼹 自动极w 逆性璎论进行融合，设计一个是凌递归结梭躲凑限爨动枫公钥体制鲢薮爨 法。该冀法自够同时用来避撑加解密和数字签名，势且舆存原来的荫限自动机公铜 体制的加、解密速度快等优点。同时由于采用了多个自幼机复台的理论，提高了算 法的安全程，壶著增加了破译的难度。 美键清：公锯秘密体稍商陵窝动梳可逆缝数字签名递溜细密 a b s t r a c t 硕士论文 a b s t r a c t n o w a d a y st h ec o m p u t e rn e t w o r kt e c h n o l o g i e s h a v er a p i d l yd e v e l o p e d t h e s e c u r i t i e so ft h ei n f o r m a t i o ni nt h en e t w o r ka r em o r ea n dm o l ei m p o r t a n t 。w ek n o wt h e t r a d i t i o n a lc r y p t o s y s t e mu s et h es a m ek e y 静e n c r y p ta n dd e c r y p tt h ei n f o r m a t i o n w h e n w eu s ei tt oe n c r y p to u ri n f o r m a t i o nf o r 拄a n s f e r , w em u s tt r a n s f e rt h ek e yt ot h er e c e i v e r t o o 强t h ee n e m yi n t e r c e p t st h ek e y , w ew i l ll o s et h es e c u r i t yo fo u ri n f o r m a t i o n s ow e c a ns e et h et r a d i t i o n a lc r y p t o s y s t e mi sn o ts u i t a b l ef o rt h es e c r e tc o m m u n i c a t i o ni nt h e n e t w o r k b u tt h ep u b l i c k e yc r y p t o s y s t e mh a st w ok e y s ：p u b l i c - k e ya n ds e c r e t - k e y w e c a nu s et h ep u b l i c - k e yt oe n c r y p ta n dt h es e c r e t - k e yt od e c r y p t ，t h i st e l l su st h a ti tc a l l r e s o l v et h e p r o b l e mf a c e db yt h e t r a d i t i o n a lc r y p t o s y s t e m t h ef i n i t ea u t o m a t o np u b l i ck e yc r y p t o s y s t e mb a s e so i li n v e r t i b i ! i t yt h e o r yo f f i n i t ea u t o m a t aw a sp r o p o s e db yt a or e n j ia n dc h e ns h i h u ai n1 9 8 5 i nt h i sp a p e r ，w e f i r s t l yd i s c u s sa l lk i n d so fp u b l i c - k e yc r y p t o s y s t e m sb a s e do i lf i n i t ea u t o m a t o i lt h e o r y a n di r e p r o v e dt w oo ft h e m s e c o n d l yw ei n t r o d u c et h ec o m p o s i t ec r y p t o s y s t e m sa n da n e ws y s t e mi sp r o p o s e dw h i c hu s et h ec o m p o s i t ec r y p t o s y s t e m sa n df i n i t ea u t o m a t o n t h i sa l g o r i t h mc a ne a s i l yb eu s e dt od i g i t a ls i g n a t u r ea n di ti ss e c u r ea n ds t i l lr e t a i n s m e r i t so fe a r l yf a p k c ss u c ha st h ef a s ts p e e d 。r e l a t i v e l ys h o r tp u b l i ck e y ，e t c t h e c o m p o u n df i n i t ea u t o m a t o no ft h ec r y p t o s y s t e mw h i c hw ed e s i g nc o n s i s t so fm o l e t h a n t w of i n i t ea u t o m a t a s oi t sh a r dt ob r e a ki n t ot h i sc r y p t o s y s t e m ， k e yw o r d s ：p u b l i ck e yc r y p t o s y s t e m , f i n i t ea u t o m a t a ，i n v e r i t i b l i t y , d i g i t a ls i g n a t u r e ， d i s p e r s el o g a r i t h m 珏 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他入已经发 表或公布过的磅究成暴，也不包含我为获雩导任何教育机构的学位或学 历而使用过的材料。与我葡工作的同事对本学位论文做出酌贡献均 已在论文中作了明确的说明。 礤究生签名： d 。心年占对日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子著窭纸质文档，可以错阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阂或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 南京理工犬学硕士学位论文基于自动机理论的公锶密玛学研究 1 。绪论 1 。1 塞褥学触发疑 电子计箨税和通信网络的广泛应用，一方顽为人们的生活和工作带来了极大的 方便，假另一方面也带来了许多有待解决的问题，其中信息的安全性就是一个突出 静方面。信怠的安全性主要有两个方面，即信息的保密性和认诳性。密码技术是保 证倍怠安全性的关键技术。 密犸学是f j 亩老丽又年轻的科学，它霜予傈护军事和外交通信可追溯到几千 年嚣。程当今静信意时代，大囊的敏感信怠细痛历、法庭记录、资金转移、私人财 产等常常逶过公共邋信设施或计算祝网络寨进行交换，雨这些信怠的秘密怯稻粪实 蛙爨久们遣甥需要翡。因戴，魂代密码学的应用琶不眷属戳予敢治、军事、外交， 其巅用侩l 蹇秘亭圭会价值瞧已得到了充分肯定。 作炎裂究擞密技术瓣密鸡学，这一历雯悠久弱学科，发展历史大致冒分荧三个 黔段： 第一个玲段梵从吉代到1 9 4 9 年。这一时聚可餐终建科学密码学斡藏瘦时期， 这段时期的密码技本可以说是一种艺术，鼷不是一萋孛科学，密秘学家零掌越蔻囊觉 和传念米进行密码设诗和分板，焉不是推理证明。 第二个阶段为从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年s h a n n o n 发表的“保密系统蛇信 息理论”一文为私钥密娼系统建立了理论基础，从此密码学成为- - f q 科学，但密码 学直到今天仍具有艺术性，是具有艺术性的一门科学。这段时期密码学理论的研究 工作进展不大，公开的密码学文献很少。 第三个阶段为1 9 7 6 年至今。1 9 7 6 年d i f f i e 和h e u m a n 的“密码学的掰方向” 一文导致了密码学上的场革命。他们酋次证明了往发送端和接收端无密钥传输的 保密通讯是可能的，从而开创了公钥密码学的新纪元。 密码学是研究系统安全稆保密道信驰- - f q 科学。它隧慧信患技术的发鼹嚣发 展。在傣息摄日蕊庞大、信息的价值显得越来越重要的时候，人们对信息的安全性 要求就越来越商，这也就促进了密码学的发展。密码学主要分为两个学科，密码编 码学和密码分析学。密码编码学主要从睾信息的安全保密或者认证的工作，防止信 息被别人窃取或者伪造；而密码分析学主要从事破译加密信息或者伪造信息的工 作，当然它的发展也促进了密粥编码学的不断地发展。 我们知道加密、解橙过程都是在一组密钥的控制下进行的。根据密钥的特点， 绪论硕士论文 可以将密码体制分成对称密码体制和j 对称密码体制。对称密硝体锘0 使用的加密密钥 和解密密钥是一样，所以也被称为筚密钥体制或者常规体制。非对称密码体制，通常 采用两个或两个良上的密诵，鼠加密密铜和解鬻密钥跫分开的、不样的，所以又称 为公锈加密体制。 一个密码邋信系统通常可叛用淘1 2 1 来表示。它由戳下几个部分组戚：鞠文消 急颦闯p ；密交消息空闯c ；密锈空阊蜀，和茁，。在常规体制下芷，= k ，= k ，通信 双方_ 荚蓠使用的会话密码茁。瑟绥在安全酌信道下密发送方传送给接受方；在公钥加 密体制下，k 。簪k ，发送方焉接受方的公开密锈加密倍惑，接受方蔫舀茜的私镝解 密傣惠。热密过程玩：p _ c ，k ：毫k t ；麴密逑疆d “c p ，k ，k ，；在常瓶 体制下k ，= k ：，峦密镯信遂来传送；奁对称加密体素l 下，每一个公开鬻锈k ，k 。都 鸯一个私钱密镪k ，k ，与之对应，且它髓之凌霄一个公开密镊帮私锈密钥的垒残嚣。 怼一切拼p ，帮鸯d 。( e k 搬) ) = 掰。 图1 2 1 密码通信系统模型 从上图可以看出，对于给寇的明文m p 和密锈k ，k ，通过加密器就可以将明 文变换为密文c = 西。( m ) ；接受者利用密钥信道传送来的密钥k ，( 常规体制下) 或者用 本魂的与k ，匹配的密钥k ，对收到的密文进行解密恢复明文m = d 。( c ) 。 同样在这个模型中，有密确分析者的被动攻击和 e 法入侵者的主动攻击。生动攻 击怒指非法入侵者采用翻涂、更改、伪造等手段向系统注入假信息，以达到损入莉己 豁爨静静行为。被动玫击是指密码分析者对截获的密文进行分析，以求得到明文的攻 击行为。 密玛分析者豹： 辛擎就怒簧被译褥戮酌密文e 褥翻赘文m 。袍稻所用的酸译方法有 穷举法耜分析法两释。穷举法怒对截获翡京文蒎次傻瘸各种可辘静密镪解密，赢戮襻 2 南京理工大学硕士学位论文基于自动机理论的公钥密码学研究 到有意义的明文；或者在密钥不变的情况下，对所有可能的明文进行加密直到得到与 截获的密文一致的结果为止。理论上说，只要有足够的时间和空间，穷举法可以破译 所有的算法，但是由于实际的时间和空间的限制使得这种方法变得不可行了。例如， 我们用穷举法花三年的时间可以破译一个机密文件，但是如果该机密文件的保密期只 有两年的话，那么这样穷举就没有意义了。 分析法又分为确定性分析法和统计分析法。确定性分析法是利用个或几个己知 量用数学关系式表示出所求未知量( 如密钥等) 。统计分析法是利用明文的已知统计规 律进行破译的方法，密码分析者对截获的密文进行统计分析，得出其间的统计规律， 并与明文的统计规律进行对比，从中提取明文和密文之间的对应或变换信息。我们可 以看出要对付密码分析，从确定性分析的角度看必须使得系统达到实际上的不可破 性，即从要截获的密文，在公钥体制中已知公钥，要确定私钥或任意明文在计算上是 不可行的；从统计分析的角度看必须减少明文的多余度，使得找到明文一密文对的概 率大大减少。同样系统保密性要不依赖于对加密体制或算法的保密，而依赖于密钥。 要对付非法入侵者的主动攻击，防止消息的篡改、删除和伪造的种有效的方法 就是使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真 伪，实现这种功能的密码系统称为认证系统。 加密和认证是密码编码学的两大应用。 1 3 公钥密码学的理论和发展 密码学本与计算机科学无关，计算机和网络的飞速发展使得近代密码学理论得到 革命性的变革和迅速发展。传统的密码体制是建立在通过通信双方共同约定的密钥来 加、解密的基础之上的，这显然不适合计算机网络上的秘密通信的需要。1 9 7 6 年 i ) i f f i e 和h e l i m a n 在“密码学的新方向”一文中提出了公钥密码体制的新概念。在 公钥密码体制中，有公开密钥和秘密密钥之分，发送方可以用接受方的公开密钥对要 传输的信息进行加密，接受方用自己的秘密密钥解密接受到的加密信息就可以得到发 送方所要传送的信息了。在这一过程中通信的双方并不需要共同约定密钥。这一概念 显然可以用来解决计算机网络上秘密通信的问题，从而开创了现代密码学的新领域。 公钥加密算法用一个密钥对信息进行加密，而用另一个不同但是相关的密钥对加 密后的信息进行解密。这些算法有以下的特性： 仅仅知道加密算法和加密密钥而要确定解密密钥，在计算上是不可行的；两个相 关密钥中任何一个都可以用作加密而让另一个用作解密。 图1 2 2 给出了公钥加密的过程的模型。 特论 硕士论文 圈1 2 2 公钥加密过程模型 国1 2 。2 中。表示爝户b 的公开密钥，甄。表示用户b 的秘密密镯，e 表示加密 簿法，d 表示簿密算法。 在这个过程中骞滋下的足个步骧： 1 。嬲终中餐令躅户蠛郄蠢塞蠢静一对攥枣、鹾密密锯，并整垮糖密密铜公开。 加鬻密钥通过解密密锭变换得到，但是及过来知道加密密镪想褥到鳃爨密钥在诗算上 是不可行的。 2 用户a 想恕自己靛信息发送给b ，媳就爝b 豹公开密钥进行加密。然聪将加 密褥到静密文传送给翔户b 。 3 用户b 按受到a 发送瀚密文瑶，鞠自己躺秘密鬻钥进行解密就可以得捌a 嚣 发邀绘戆豹傣患了。 一令爱数尹，懿暴露它豹定义壤上鹃馁意x 都荔予诗舞，( 莉，藤对予，煞篷躐 中几乎艨鸯瓣y ，当f 已i 知对瞧“多项式时闼”内计箕f “y ) 是不可行竣，遮撵熬， 就魑单向函数。如果当给定某些辅助信息时则易于计算单向鳓数，的遵，这榉就 称f 是一个陷门肇向函数。 公铡加密体翻是建立在数学中已知的n p 问题之上韵，利瘸n p 问题来构造一个陷 门苹向融数，加密过程是个单向的过程，只翔道明文和公钥是无法计算密文的；同 样解蜜过程魄是缀饕鼙鹩，警给定巢些禚韵信怠帮款镄时，镁容荔计算密文e 已魏懿黼溺题霉穰多，熬够蒲来稳造公镅麓密钵稍蕊著不多。瑗舂静公锈秘密 雾法邦是基予以下潆困溅阙爨的： 背包问题：捍个熬数的集合a = a 1 , 吼，聪。) 和整数s ，找出a 的一个子集效 中元素之和替于s 。 整数分解闯题：芷整数竹，是否存在懿数 。、如，1 n j ，以2 n ，使得摊= n l 如n 离敖对数：如果p 惫豢数，g 和m 是蹩数，找出x 满足g 。- m m o d p 。 丢番瑟方稷；三个蔗整数痒、b 、e ，丢番鹜方程o , x 2 + b y = , f f 霆裕存在整数解。 矩箨覆藏瓣惩：邀髂二次鹜毯淹鬣。一个熬数环上麴菇羚矩簿a ，s z ，燕器 枣农如，魏，文) ，l y ，健褥披，x 2 。，净奴，羔：，瓠罗= s 。次鹜瓴越艨胃默 看成矩降覆熊问题的特例。 4 南京理工大学硕士学位论文基于自动机理论的公钥密码学研究 基于这些n p 问题人们提出了一系列公钥加密体制。1 9 7 8 年r i v e s t ，s h a m i r 和 a d l e m a n 提出了第一个公钥加密体制r s a ，它的安全性就是基于大整数分解问题。此 后人们又提出了各种公钥加密体制，例如糊背包体制、概率加密体制、椭圆曲线密 码体制等。 一一 随着密码学研究的深入发展，人们又不断地提出各种新的密码体系，主要有： 概率加密系统，椭圆曲线密码系统，热流密码系统，混沌密码系统，量子密码系统等。 1 9 8 5 年，我国学者陶仁骥和陈世华利用有限自动机可逆性理论提出了有限自动机公 钥密码体制( f a p k c ) ，并在此后陆续提出了该体制的一系列算法，该体制在国际上有 着定的影响，国际上称为陶陈体制。密码学也被应用到神经网络、数字签名、认证 管理、零知识证明、信息高速公路的安全等多个方面。 1 4 论文的内容和组织结构 本文的内容共分五部分，详细地研究了各种基于有限自动机理论的公钥加密体 制，并且对几种自动机加密体制的公钥加蟹箕法进短了改进。有限自动机加密体制不 但安全性高，而且其加、解密速度快。本文还利用现在比较可行的复合加密算法理论 的思想，将有限自动机加密体制与其自身进行复合生成新的加密算法，既能提高体制 的安全性又能保持原来自动机加密体制的优点。最后对复合的算法用软件加以实现。 第一章绪论部分，详细介绍了密码学和公钥密码学的理论和发展历史，同时也详 细地界定了本文的研究对象和内容。，积，移吲i 毒p ，币治批l - ；乒。、h j 1 第二章介绍了有限自动机公钥加密体制的发展，理论基础等基本内容。 第三章介绍了f a p k c 0 的加密和数字签名算法，在对该算法的安全性进行分析 的基础上提出了一个对这个体制的改进算法，抵抗现有的体制方法。 第四章介绍了f a p k c l 和f a p k c 2 ，主要介绍了f a p k c 2 在身份认证方面的理， 论和作用。b稻忸1 0 吒- ，目段 第五章介绍了f a p k c 3 ，并给出一个改进算法，进_ 拗黾高了该体制的安全性。 第六章介绍了f a p k c 4 ，和f a p k c 3 一样，都被认为是安全的加密签名算法。 第七章在上面这些体制的方法上，利用复合加密算法的理论和多个有限自动机迭 代的理论，。给出了一个新的f a p k c 算法，并从多方面对此算法进行安全分析，最后 给出了该算痞丽二不鬲葫；i 面卜一一 形萌磊强i 醑、j 一乏一砺 给出了该算法的一个软件实现。孙给( i 强鲁1 妊驴1 叼 骺埘敝舡懒豫眠阱滞差鬻- f f 蕊麓嬲。i 热v 睹量n ，i 、，7 f ，￥7 、l 7 l nl + l 、。 弘萝印- 有限自动机公钢加密体制硬士论文 2 。有限自动瓿公钢趣赛体制 2 。1 黼掰变 蠡1 9 7 6 年w , d i f f i e f 睹m 。h e l l m a n 挺毒双锈密秘惑惩戬来，鹫内外学者已经麓备 稀方法提密并研究了多种典体的双铜密码体潮，丽现糕大多数学者用数论方法研究双 钥密码体制。 1 9 8 5 年，燧 二骥耱陈世孥利蠲考限囊幼极可述建瑾论提爨了鸯鼹舞动桃公键密戳 体畿j f a p k c ( 全称为f i n i t ea u t o m a t o n 鳓b l i ck e yc r y p t o s y s t e m ) 。这是疆磁静第个耩 予序剜密码范鞯的公钥密礴体制。由于只涉及到逻辑运算，该体制实现起来比较简单， 运簿遮度也比较快。同时也撬出了一个具体的有限自动枫公钥密码体镥8 f a p k c o 。接蓑 趣1 9 8 6 攀，耀仁骥毂陈蠼辈又提爨了f a p k c 麴男辨鼹摹孛变形f a p k c i 鞠瓢p 怒2 。1 9 9 2 年， 辫仁骥帮陈避牮在第二褥全国密码学学术会谈上捷出了懿f a ( p e 2 为基础酌蘩予身份 酌f a k p c 密确体翻和数字签名体制，成功的实现了a s h a m i r 在1 9 8 4 年提出的基于身份 的密犸体翩和数字签名体铡的思想，并且这是对基予身份的机密体制躲翦次实现。裹 翔提如了一秘奔予f a p i ( e 0 秘瓢p k c l 之阕鳇俸粼，嚣之为f a p i ( e 9 3 。1 9 9 5 年，淘仨骧、 陈世华靼陈霉梅又提出了新静有限岛动枫公镶密码体制- f a p 蕊3 ，其中的密铜产雏有 一个线豫r a 怒筛予。就衙稳们又给出了一个f a p k c 3 盼嶷体新算法称为f a p k c 4 。 在f a p k c o 和f a p k c i 中，公钥中缀台基动枫的非线性分量是劫枕的延迟步数必0 。 1 9 9 4 年7 月，武汉大学戴大为、吴连裙张焕国给蹬了馨申线性攻壹方法， 歪锡融辨e 0 娓细密部分是脆弱懿。掰年，陶仨骥用线性r a r b 交换方法证褥了f a k p c o ，f a k p c i ， f a k p c 9 3 等采髑延邃髭j # 线径分鬟舀动褫酌体割的加密鞠签名都怒脆弱的。1 9 9 5 年， 鲍丰等对f a 烀c l 墩给出一种攻击加密的方法。在第网箱全国密码学学术会议 c h i n a c r y p t 9 6 上，犟中乎鹈张焕国提出了约化梯蹲攻击方法，戴塞镑提出了线矬冀一 矩阵攻毒方法，鄹年，陶仨骥窝玉浩给爨了线性r a r b 变换帮线纯梯辫的关系。 2 2 张瓣蒸零藏念 一个有限鑫劫栅裁是一个蠢元缀 ，f 为非 受熬数。掰怒惩迟f 步弱霹遂懿，鳃莱对联的经俘状态s 帮舔入浮列x 。x 。，x 。是 洳s 和坝日x ，) 唯一决定。设j s ，j + s ，如采对于任何g 若x 。，存在着长为f 的 毫x “满怒( s 旯0 ，d ) ) = 冁d ，则称( j ，s ) 为z 匹配辩，或者称与s 、f 匹配。 如累对嬲的任俺状态8 ，檑应存在嬲的状态s ，馊褥( ，s ) 是f 匹配对，则稳掰1 是嬲静一个延迟薯步骚遂，艇是掰瓣一个延迟g 步弱原逆。膨是延迟f 步弱爵逆躲 警鬣便当释猩一个有限舀动车凡掰是硝的殛遥f 步弱遘。 如聚想避一步的了解肖限囱动机和有陵自动机可邀性理论，请参考文献1 。 2 3f 雕c 擒介 礁i f a p k c q a ，公钥一般包撼延迟步数为( 十冀) ) 的缀合有限自动机g 啤；，m j 帮它的如密裙娥状态痿患s 。、验涯努】始状森嚣患s 。私钱剩鼹磊拿昊簿熬镕铡相关 n n n 不n ，它一般包括掰。酌延迟多数为的弱( 舔) 逆有陵裔渤梳材。，掰，的延 沤步数为气的弱逆有限裔动视m ，肘。和m 。的解窝初始状态信惠& 和，m o 和 7 密辍蠡动枉公锶麴密体蠲磺士论文 脑；豹签名初始状态信息s 。和。 在f a p k c o 和f a p k c i 中，私镧还包括了耐。，且在f a p k c 2 中膨，的弱逆和弱原逆肖 限自动机都被收农稻铜中。 下嚣戳f 勰怼3 为蘩磁，筒攀叙述下f a p k c 的翔密解密、签名验证逶程。翔密 瓣，先觉裙文扩展z 令字蛰，壤据& 决定c 材，m 。戆裙始状态，然聪将扩震菇静鞠 文竣入瑟e 。姒；，榭。j 中，缮烈鹣输出霹为密文。鼹密瓣，巍摄豢氏。帮赘文决定掰。豹 胡始状态，将( 剩下的) 密文输入到肘。中，褥到的输出作为中间结果；然后掇摄是。髑 中间结果决定膨；。的初始状态，将剩下的中间结果输入到艇，中，褥从褥到粒输出中 恢复明文。简单的示意图如下： 签名潜，先懿漕怠扩袋到# 令字符，分剿壤据s 。；帮s ；决定妊。煞掰。翡裙始状 态，憋扩凝鬈豹溪惑赣入剿耐。中，霉将褥委妻冬输出输入到影；中，褥劐翁辕赛瑟菇 豁名。验涯时，惫援撼耨签名定o 嬲；，m 。) 斡规始获态，然蜃姆剩下懿签毫羧入 剿c 。( 舾。，m 。) 中，根据得到的输出进行验证判甑( 输出中包含消息) 。简单示意图如下： f 矗p k 0 的糖本形式懿土掰述，毽是备个爨薅静俸翻乏蠲还爆鸯援嚣澍静。铡黧， 龌成公钥中缀会露骧自动摭c ( 艇，m 。) 瓣鸯限叁动规艇。箨鬟艏，鼓嚣别热下： f a p k c o ：m 。是延迟t 步弱可逆的( f ，f ) 阶存储线性有限自幼机。m ，是延迟。步弱 可邋的r 阶输入存储非线性商限自动机。 f a p k c l ：m 。是延迟i 步弱逆的r 阶输入存储线性有限自动机。嬲：是延遐0 步弱可 逆的r 阶输入存储非线性有限自动机。 f 鱼p k e 2 ：耐。蹩蓬这t 步弱遂的r 除输入存德线径有戳自动梳。耐。是廷迟步弱 露遵释i 瓣r 步弱遂豹t 除输入存诺 # 线褴有限茸穗梳。 f a p k c 3 ：嬲。是延避。步弱可邀蛉( h o ，) 除存链舞隈螽动孛凡。掰，怒延迟i 步弱可 逆的鬼阶输入存储有限自动机。 f a p k c 4 ：m ：是延迟劳弱可逆的，阶存储蠢限自动极。材；熄延迟i 步弱可 逆的瞳阶输入存储有限自动机。 8 南京理置太学硕士学位论文基干自动机理论的公钥密码学研究 1 9 8 5 年，涛仨骧帮繇畿牮利震骞隈蠹凄辍霹遂往理论捷窭了有陵爨羲瓤公钥密 码体制( f a p k c ) 。这是提出的第一个属子序列密码范畴的公钥密粥体制，由于只涉及 至g 逻辑运算，该律铡实现起来冼较简单，运算速度邈比较浚。同辩也键溺了一个具体 的有限自动机公钥密码体制f a p k c 0 ；具体请参考文献黔 。下面我们简荤介绍其构造 体制并对其作出改进，其中自动机的可逆性等理论部分详见第二章。 维向爨空间，随极选择一个( f o ) 盼输入夺储延迟0 步弱可逆鸯限鑫动极妒： x ( f ) = 伊( z ( f ) ，x ( i - 1 ) ，z ( f 一2 ) ，x ( i - r ) ) i - - - 0 ，i ( 3 1 1 ) 妒鸭，魄，一，移) = 焉+ 易吩+ 2 f j ；p ；( y j ，) ( 3 。i + 2 上式中瓣( b v 雕) 以及本文器嚣讨论毂嚣个撼裂超量懿穗豢均定义菇按分爨提爨： v ，v 川= h ，。v 川p ，v 胁1 ，。 。，妒的延迟0 步的弱逆妒应满足：对于任意的 ，v ，妒4 ( 妒，一) ，毡，巧) 亍v o ，这里采惩豹蒸俸茅施是警+ f o j v i 存 在，于是妒哟v 。= ( + f 。，。v ，川妒( v 。，v l ，一，v ，) + 民+ 巳v ；+ f 川+ ，v v ml 以上，f 。n m x m 瓣，磊，勺为m 维列向量，这重铸论的或。v 1 应理解为羔个 m 阶方阵：设喝= 【吒一，。一v l = f 毪1 ，魄。】7 ，f 。t = ( 吩) ，则 f 。t 毪飞，= 三：三 ：i ! ：1 = 篡i ：三： f 兰 = c f k 砖，孙c s 。t ，s ， 褥随枫选择一个g f ( q ) 上的( 彳，彳) 阶输入输出存储延迟彳步可递裔鬻自动机膨。： y ( i ) = a ：y ( i j ) + b ：x i j ) i - - 0 ，1 ， ( 3 一i - 4 以及掰i 豹繇透f 多酶遂嬲，4 ： 毒p 暑) = 盖”( f ) = a j y ( i - j ) i = 0 “1 ( 3 1 。5 ) 其中冬，芬，矗j 为镢鼋) 上瓣1 1 1 徐方簿。 将p 与m 。复含，构造一个( f + r ，f ) 阶输入输出存储延迟f 步弱可邀有限自动机 9 f a p k c 0 硬士论文 m ff y ( 1 ) = a ：y ( i - j ) + 即( 茹( 一疹一，并卜j r ) ) j 。l卸 = 冬卜力+ c 。+ 茗( f 一，) + c * j , j + l ( x ( i - j ) x ( i - j - 1 ) ) 扣1。o卢0 i = o ，1 ，( 3 1 6 ) 烽m 鞋及共潮约定懿茹( 一1 ) ，x ( - r ) 作为公开豹鸯秘密密镅，将嬲：，妒作为秘密豹解 密密镅，鞘文净捌经m 转换成密文序捌，密文序鳓缀膨i ，妒还原成明文序列。也萄 以把m 理解为延迟0 步弱可逆商眼皂幼机，但这就娶求把y ( - 1 ) ，y ( 一r ) 传为共圈 约定豹嘲定慰素。 3 2 变换裳粼霹5 、露1 交换斑剐暂： 设科颤啦一哪满腻件：h 的行线性斌b i k + ，) o k ：0 , 婀对 l 辑o t j 毯进行行的翘等变换，但不改交它的煎峨行，即噬可以左慕以矩辫廷，澎翅 最= 使得结粱矩障嘎= 最嚷= a 挑琢k 。刚中= 嗽，i = l ，女1 ， ，。咄+ 嘁。其中最必魄级单经铤降，蕞为掰* 级 奇器短簿。耀记号 硝蕞1 瓯j 。瓯波示按援则将瓯庄乘以砭交挨到瓯。 1 0 j 要至墨兰态兰登主堂皇笙塞 萎量塞鍪垫璺鎏整叁整窒銎鲎鐾茎 交换栽剃霉； 设瓴= l 啡i j & ( l ( 。耳睁州满足条件 鼋。f ： 壤“1 的行线黢无关，当f 0 时 蕊一) i 黔日2 0 ，剽嗣瓠将g + t 鞠最拳辩缒薛宣移m + l 位，补入0 ，绪果为 = 颤 。m 。q ，堍= ，i = i ，露i 翔记号玩+ 。譬瞵表器按蕊燕| j 露t 将镇+ ，交换到谎。 对瓯= 颤 。$ 移嚷= 如泓，；岛潞 洚；m 。蚪i ) 我们定义 ：r a i n h 嗽。o ，= 一t ，矗一1 ，知有定义奠不为o 学o l i - i 当= 0 h = f = 1 ，豇+ t a ( k ) = a h 球 ： k ，h - 1 ，壤有定义置不为叼当域o 当破；0i k 溺以i = o i = + 1 a + ( 是) = m ) “i 。u t 这里约定，当( 或瓦) 无定义时，a 吣( 域厶。) 无定义。 以c ( ) 袭示条件：= o ，f = l ，k ，j = 一f ，一1 ；k = 1 - i ，i = 1 ，k ；当q 不完 全定义且册女事0 时，和在r j r + 2 - i 处都无定义，奁其穗懿都有定义， 江l ，k ；矗( 是) 菲鹰异。 以c ( 盎) 表示条l 孛：醵= o ，溏l ，k + l ，= 一t ，一i ；h l 女= l i ，江l ，女，壤。括= l k 。 娄嚷不完全定义豆蛀譬。时，鞍豫在r ，r + 2 一i 处都无悫义，农其健处帮蠢 1 1 f 一 | i o i i r ，l & a 1 瓣卜卜 瓢p | o 磷士论文 定义，= 1 ，毒，当试不完垒定义量叫批喾。瞬，。m 和蠡；。+ 1 ) 排在r ，r + 2 一i 娥 ( 1 ) 求出一个m ( r + f + 1 ) ( m + f ) ( 不宪全定义) 矩阵g f 十，g f + ，满足条件c l ( f 十1 ) ， 仨，卜斌褂斌腾一0 如e l i l 的列线性无关，l ! | 的行线性无关，且当f ：时，囊。：一。 l 投f + l j 。f 删l 爆。j ( 2 ) 伟一个变换序列瓯，譬翟3 q _ 叶g s 絮3 g l ，其中乒一l & 冬o l ；r j 取 = a ”b j = 嚣l j = o ，r ，粥由2 。5 式定义的蜒迟f 步( r ，r ) 阶存储线靛 ( 3 ) 任何延迟f 步弱可逆( r ，) 阶存储线性有嫩自动机m 皆可由( 1 ) ( 2 ) 的步骤得 程触p k 中，公镌中缝合囊动枧蛉 线性分量盔动搬的延迟步数力0 。在该密 码体制被提出后，先履有不嗣憋人证明了它的脆弱性。罄先绘出该体制驰破译冀法的 是中科院的鲍半，他提出了一个称为只螺的概攀算法；武汉大学的张焕国等人也绘 融了一个a r m 攻击算法：隧后不久，陶仁骥用线性r a r b 变换方法证明了慕用越迟0 步非线性分攫的自动机加密体制f a i ( p c o 的加密和签名都是脆弱的。本节给出鲍丰和 张焕国等的破译算法，陶仁骥的线性r a r b 交换方法请参见参考文献 2 4 。 3 3 1 黜厶概率算法 1 9 9 4 年2 舅，中国科学臻软待磺究所黪鲢事绘怒了个称为默乞的概率算法， 下露麓肇赍缀其冀法滚程，其髂谤照参考文皴 3 1 。 设m 。是延迟0 步 线性有限自动枞，獒定义为 y ( i ) = 工( f ) + ，( x o - 1 ) ，x ( i - 2 ) ，4 i - ，) ) ；m ：是线性延迟f 步f 除埝入存琏霄限爨 动机，意义为y ( f ) = 如( 1 ) + a z ( f 1 ) + + a 。x ( i - t ) ；敢恧m = m o x m l 是f + r 酚输 入存储延迟f 步弱可逆非线性有限自动机，其定义为 y ( f ) = 船( f ) + f ( 工( f 一1 ) ，x ( i - 2 ) ，x ( i - v - r ) ) ；这里f 是x 7n x 的j e 线性函数， 1 2 离寨瑾工夫学磺士学使论文 基千盲动梳理论静公镅密璃学研究 因此f 就楚x ”捌x 的 线性函数。 在已知状态s = 五( 一1 ) ，并( _ 2 ) ，x ( 吖一r ) ) 和输出y o ，y 。，觇，醵时求出输入的第 一位。设a 是g f ( 2 ) 上的l x l 矩阵，记r ( a ) ；f a x i x e x l 。 ( i ) 输入裙始状态并( 一1 ) ，j ( 电) ，善( 一f r ) 藏，y i ，y 2 ，欺 ( 2 ) 求森善= y p ) 十f 茹一l ，茅( 越) ，鼻( 吖一，) ) 豹解( 其中x 为变蠹，蒋式蠹边 是喾羹，共霄2 “ 蹦= 2 “个孵) 。从中疆橇选择一个定为x ( 0 1 ，麓凝 y 0 ) + f ( 4 0 ) ，4 - 1 ) ，算( 岬一r + 1 ) 是喾蔗予露盘) ，如粜是，里b 跳转到步骥( 3 ) ， 誉，则停机。 ( 3 ) 求a o x = y ( 1 ) + f ( 戈( o ) ，4 - 1 ) ，x ( 一f r 十1 ) ) 的解。从中随机选择一个定为 x ( i ) ，判断y ( 1 ) 十f ( z ( 1 ) ，4 0 ) ，x ( - t - r + 2 ) ) 是丽属于刖：如) ，如果是，则跳转到 步骤( 4 ) ，否，劐傅辊。 ( r - 3 ) 求焉若= y ( r - 1 ) + f 善筝一2 ) ，并 ，一1 ) ) 熬解。觚中涟撬选择一个定 炎盖( f 一1 ) ，判凝y 0 ) + f ( x ( f 1 ) ，x ( - r ) ) 是否属予冀焉) ，如果是，则辏嫩x ( o ) ， 磷，则婷戡。 每执行一次p a 厶能墩出并( 。) 的概率为2 晦”筹，因此将似厶执行2 霎m 。次有l ，2 蛉概率戎出4 0 1 。 3 。3 2a c m 攻斑方法 1 9 9 5 年3 月，藏淡大攀戴大必鬻张焕簪给赉了释a r m 敬赘方法，冀俸瀵参 见文献 3 4 】，慰有袋童动瓿体铡避行鑫熬密文攻意，诞骥f a k p c o 黪翔警蘸分是濂弱 的，这挺被攻爨的有限自动机公开钥搬确体制以延迟h 步弱可邀f 一拟线性有限爨动 机为其公开烟密算法f 矗f 0 1 ，算法a 苫艇在菜些馕掇下可奏效。下霹绘崽该舞法 的些概念和热体步骤。 设f 一拟线性有限自幼机m 由 ，r - 1 y ( f ) = a x ( i - j ) + q 茗( f 一，) 芹( f 一，一j ) ，i = 0 ，1 州2 一“ 卢o卢r + l 其中冬与q 为g f ( q ) _ j 2 m x l 矩阵，z ( f ) ，y ( i ) 分别为g f ( q ) lt 乓m 维列向擞。 e q o ( i 1 表示方程 rr - i a j x ( i - j ) - y ( i ) + c j x ( i j ) x ( i 一，一1 ) = o j = o 扣f 十l 辩毒k = 。 礤士论文 令兄变换与托交换同文献 1 。 戳嚣鼋，国袭零方程气产i 一歹) 一磁，y i + j ) + q ，羔( i j ) 4 i - j 1 ) = e 蝴e q o ( i ) 经次毪变抉与镌交换褥到，t ；i ，2 ， 以钾。( i ) 袭示e 毂( f ) 经一次r 变换而褥的方程，= o 1 - ，以，颤，k f 分$ 1 j 寝示矩陴a o ，氐，4 0 的秩，令e j e q ，( i ) 袭示叼( i ) 的前，个分董方程。 我们约定记号蛔。f ) 藏t 乏嚣：0 ) 表涿关予褒元x ( 。的方程。定义方程链c 嚣为： g q r ( o ) e 吼( 1 ) 8 吼( h - _ r ) 嚣_ - 叼。( a 一彳+ 1 ) h ：钾 r - 2 ( h - 仆2 ) 嚣。叫。( ) 算法a 2 m 稳久：m ，黔期态s = x 一，) ，茗一r + 1 ) ，算( 一1 ) 与筏豹辕筮y ( o ) y o ) y ( h ) 。 输出： x ( o ) ，冀满足条件f ：确吲：i ) x ( ) 存在橙褥黯艏；勰输出陕骞于五，有焉b 并( o ) 工( 1 ) 茗( 矗) ) = y ( o ) y ( 1 卜y ( h ) 。 过程： ( 1 ) 从左至右顺序到求解方程链娌中获列方程( 关予方程下列檬承的交元) 。每当 无解时停机，而当有解时，任选一解赋予所求解的变元。 ( 2 ) 输出x ( o ，傍撬。 此爝张等人又给出了一个经过改进的破译算法a r m + ，其与a r m 破译算法的区 别仅在于方程链，其他求解过程郡相同。 方程链c e 2 定义为： 最怒叩 e q r ( 1 ) 。e q t ( 。h - r - 卸1 ) e a n t 8 ：竺，“ 渺， 3 4 一个改避熬f a p k c 算法 针对这些提出的破译算法，我们注懑到这些算法都是浆用