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

硕士论文基于有限自动机理论的公铜加密算法研究 摘要 密码技术是信息安全豹核心技术。魏今在计算机网络环境下信息的枧密性、安全 性、完整性、可用性等特性，都需要采用密码技术来解决。密码体制大体分为对称密 码( 又称为单钥或私钥密码) 体制和非对称密码( 又称为双钥或公钥密码) 体制两种，其 中后者在信息安全中据负着密钥协商、数字签名、消惑认证等重要角色，已成为最核 心的密码体制。 本文讨论的是基于有限自动机理论的公钥加密体制。这种加密体制是我国数学家 陶仁骥和陈世华首先提出的。该体制的工作原理是利用有限自动机的可逆性来完成加 密、解密以及数字签名等功能。本文蓄先余绍了自动机的基础知识以及自动机热密的 原理。接着介绍了自动机密码体制的发展过程中的几个重要的算法，并对部分算法进 行了改进和完善。最后，首先证明了可以将算法f a p k c 4 中的自动机扩展成自由存贮 自动机，然后结合扩箴后的f a p k c 4 算法，利用多个自动机的复合，设计了一个新的加 密算法，并对该算法进行了模拟实现及安全性分拆。该算法同时可以用傲加密和签名， 并且具有原来的有限自动机公钥体制的加、解密速度快等优点。同时由于该算法对自 动机的状态分量进行了扩展，增加了构造自动机的复杂度，也就提高了算法的安余性， 增加了破译的难度。 关键词：有限自动机公钥加密体制可逆饿加密解密数字签名 颈谂义蕊于霄般自动机理论的套铜加密算法研究 a b s t r a c t e n c r y p f i n gt e c h n o l o g yi st h ec o r e t h es e c u r i t i e so ft h ei n f o r m a t i o n n o w a d a y s ：i nt h ec o m p u t e rn e t w o r ke n v i r o n m e n t ，a l lt h ec o n f i d e n t i 8 l i t y ， s e c a r i t y ，i n t e g r a l i t y ，u s a b i l i t ya n dn o n r e p u d i a t i o no ft h ei n f o r m a t i o n m u s t b er e s o l v e db ye n c r y p t i n gt e c h n o l o g y o nt h ew h o l et h ec r y p t o g r a p h yh a st w o p a r t s ：s w 鞴e t r i ce r ，；p t o s y s t e m ( o n e - k e yo rp r i v a t ek e yc r y p t o s y s t e m ) ， a s y m e t r icc r y p t o s y s t e m ( t w o k e yo rp u b li ck e yc r y p t o s y s t e m ) ，a n dt h el a t t e r t a k e sm a r ei m p o r t a n tr o l ei nn e g o t i a t i n gk e y ，d i g i t a ls i g n a t u r ea n dm e s s a g e v a l i d a t i o n ；e t ci nt h es e c u r i t i e so ft h ei n f o r m a t i o n ，s oi t i st h em o s t i m p o r t a n to r y p t o s y 8 t e 辩。 i nt h i sp a p e rw ed i s c u s so n ep u b l i ck e ye r y p t o s y s t e mw h i c hb a s e do i lt h e t h e o r yo ft h ef i n i t ea u t o m a t o n 。t h i sc r y p t o s y s t e mw a sp r o p o s e db yt a or e n j i a n dc h e ns h i h u a , a n dw o r k sb yu s i n gt h ei 靛v e r t i b i l i t yt h e o r yo ff i n i t ea u t o m a t a t oc o m p l e t et h ee n c r y p t i n g ，d e c r y p t i n ga n ds i g n a t u r ef u n c t i o n 。i nt h ep a p e r w ef i r s ti n t r o d u c et h ek n o w l e d g eo ft h ef i n i t ea u t o m a t o na n dt h et h e o r yo f t h ec r y p t o s y s t e mb a s e do af i n i t ea u t o n a t o n 。t h e nw ed i s c u s ss o m ei m p o r t a n t a l g o r i t h m sp r o p o s e di nt h ed e v e l o p m e n to f t h i sc r y p t o s y s t e m ，a l s od os o m ew o r k t oi m p ：r o v eo ns o m eo n e s 。a tl a s tw ef i r s tp r o v et h a ti ti sv i a b 】et oe x t e n d t h ea u t o 瀚t ai nf a p k c 4a l g o r i t h mt ot h ef r e e - m e m o r ya u t o m a t a b a s e d0 nt h e n e we x t e n d e df 矗p k c 4 。a n dw i t hc o m p o u n d i n gm u l t i p l ea u t o m a t a , w ec o n s t r u c t8 n e wa l g o r i t h ma n di m p l e m e n ti t t h i sa l g o r i t h mc a nb eu s e dt oe n c r y p ta n d i m p l e m e n td i g i t a ls i g n a t u r e s 。a n ds t i l lr e t a i n sm e r i t so fe a r l yf a p k c ss u c h a 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 li ck e ye t c 。b e c a u s et h en e wa l g o r i t h m e x t e n d st h es t a t ec o m p o n e n to ft h ea u t o m a t a ，w h ic hm a k e sc o n s t r u c t i n ga u t o m a t a m o r ec o m p l e x ，t h es e c u r i t yw i l lb ei m p r o v e da n di t sh a r d e rt ob r e a ki n t o t h i sc r y p t o s y s t e m ， k e y w o r d s ：f i n i t ea u t o m a t a ，p u b l i ck e yc r y p t o s y s t e m , i n v e r t i b i l i t y ， e n c r y p t i o n ，d e c r y p t i o n ，d i g i t a ls i g n a t u r e 珏 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：登蜀i 羔。年月，7 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 2 受3i 量 文。年6 月l ? 日 硕十论文 摹于有限自动机理论的公钥加密算法研究 第一章绪论 1 1 密码学的发展 密码学是- n 古老而又年轻的科学，它用于保护军事和外交通信可追溯到几千年 前。在当今的信息时代，电子计算机和通信网络的广泛应用，一方面为人们的生活和 工作带来了极大的方便，但另一方面也带来了许多有待解决的问题，其中信息的安全 性就是一个突出的方面。譬如大量的敏感信息如病历、法庭记录、资金转移、私人财 产等常常通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性 是人们迫切需要的。因此，现代密码学的应用已不再局限于政治、军事，外交，其商 用价值和社会价值也已得到了充分肯定。 密码学的发展过程其实是一个编码与破译的不断斗争实践的过程，具体的说，其 发展历史可以大致分为三个阶段【，1 ： 第一个阶段为从古代到1 9 4 9 年。这一时期可看作是科学密码学的萌芽时期，这 段时期的密码技术还不能称为真正的科学，因为密码学家常常足凭直觉和信念来进行 密码设计和分析，而不是严格的推理证明。 第二个阶段为从1 9 4 9 年到1 9 7 5 年。这一阶段是密码学的初始期。s h a n n o n 发表 的“保密系统的信息理论”一文奠定了私钥密码系统的理论基础，从此密码学成为一 门科学。但是这段时期密码学理论的研究工作进展不大，公开的密码学文献很少，基 本上可以说是密码学作为科学，刚刚形成。 第三个阶段为1 9 7 6 年至今，是密码学的发展期。1 9 7 6 年d i f f i e 和h e l l m a n 的“密 码学的新方向”一文导致了密码学上的一场革命。他们证明了在发送端和接收端无密 钥传输的保密通讯是可能的，从而加速了密码学的发展，开创了公钥密码学的新纪元。 目前，当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨 出巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他先 进设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数学家、 计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学的发 展。 1 2 密码学的基本概念 密码学是研究系统安全和保密通信的一门科学，并随着先进科学技术的应用，其 渐渐成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、 计算机科学等有着广泛而密切的联系。根据作用和功能的不同，密码学可以分为两个 颂士论文 基于有限自动机理论的公钥加密算法研究 大的分支，即密码编码学和密码分析学。密码编码学的主要目的是寻求保证消息保密 性或认证性的方法，密码分析学的主要目的是研究加密消息的破译或消息的伪造。正 是这两个对立分支的互相斗争，大大的促进了密码学的不断发展。 采用密码技术可以隐藏和保护需要保密的消息，使非法用户不能提取信息。这些 未被保护的消息称作明文，隐藏后的消息称为密文或密报。显然，将明文转换成密文 的过程就是加密，而其反过程就是解密。对明文加密时采用的一组规则称为加密算法， 同样解密时采用的规则称为解密算法。在加密和解密的过程中都有一组密钥进行控 制，这个密钥分别称为加密密钥和解密密钥。 根据密钥的不同，可以将密码体制分成对称密码体制和非对称密码体制。对称密 码体制使用的加密密钥和解密密钥是一样，所以也被称为单密钥体制或者常规体制。 非对称密码体制，通常采用两个或两个以上的密钥，且加密密钥和解密密钥是分开的、 不一样的，所以又称为公钥加密体制。 所以，一个密码通信系统可以用图1 - 1 表示： 发送者 接收者 明文m 卜j 叫密文m j i1 r 一 il 密文m 卜一翌妯 加密算法e l 解密算法d 2 加密密钥k i解密密钥k 2 图1 - 1 一个密码通信系统结构图 如图中所示，一个密码系统包括如下几个部分：明文空间p ，密文空间q ；密钥 空间k i ，k 2 ，在私钥体制下k 1 = k 2 = k ，此时密钥k 需要安全的密钥通道传送给对 方；加密算法e 1 ：p - - q 。解密算法d 2 ：q 专p 。其变换过程为： e l ( p ) - - q ，d 2 ( q ) 专p 。对于给定的明文消息用e p 和密钥k l k 1 ，加密过程将明 文m 变换成密文m 。：m _ f ( m ，k 1 ) = e l ( m ) m p ，m 。q ，k l k 1 。接收者利用密 钥将密文转换成明文：m = g ( m ，k 2 ) = d 2 ( m ) m p ，m q ，k 2 k 2 。 在消息的传输和处理系统中，除了既定的接收者之外，还有一些发未被授权的用 户，他们利用各种非法的手段来窃取和修改加密的消息。虽然他们不知道系统的密钥， 但是通过分析可能从截获的密文中推断出原来的明文，这一过程称为密码分析。密码 分析者主要利用穷举法和分析法对密文进行攻击，穷举法是对截获的密文依次使用各 种可能的密钥解密，直到得到有意义的明文；或者在密钥不变的情况下，对所有可能 的明文进行加密直到得到与截获的密文一致的结果为止。理论上说，只要有足够的时 2 硕士论文基于有限自动机理论的公钥加密算法研究 间和空间，穷举法可以破译所有的算法，但是由于实际的时间和空间的限制使得这种 方法变得不可行了。例如，我们用穷举法花三年的时间可以破译一个机密文件，但是 如果该机密文件的保密期只有一年的话，那么这样穷举就没有意义了。 分析法又分为确定性分析法和统计分析法。确定性分析法是利用一个或几个已知 量用数学关系式表示出所求未知量( 如密钥等) 。统计分析法是利用明文的已知统计规 律进行破译的方法，密码分析者对截获的密文进行统计分析，得出其间的统计舰律， 并与明文的统计规律进行对比，从中提取明文和密文之间的对应或变换信息。我们可 以看出要对付密码分析，从确定性分析的角度看必须使得系统达到实际上的不可破 性，即从要截获的密文，在公钥体制中已知公钥，要确定私钥或任意明文在计算上是 不可行的；从统计分析的角度看必须减少明文的多余度，使得找到明文一密文对的概 率大大减少。同样系统保密性要不依赖于对加密体制或算法的保密，而依赖于密钥。 因此为了保护信息的安全，抵抗密码分析一个保密系统应当满足以下要求： 1 系统即使理论上不可破，也应当是实际上可不可破的。也就是说，从截 获的密文或某些已知明文密文对，要确定密钥或任意明文在计算上 是不可行的。 2 系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。 3 加密和解密算法适用于所有密钥空间中的元素。 4 系统既易于实现由便于应用p l 。 另外，要对付非法入侵者的主动攻击，防止消息的篡改、删除和伪造的一种有效 的方法就是使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息 的真伪，实现这种功能的密码系统称为认证系统。 1 3 公钥密码学理论和发展 1 9 7 6 年d i f f i e 和h e l l m a n 在“密码学的新方向”一文中提出了公钥密码体制的 新概念，从而开创了现代密码学的新领域。公钥密码学体制( p u b l i ck e y c r y p t o s y s t e m ，记为p k c ) 可以在不需要通信双方约定共同的密钥的情况下来加、解 密，这就使得发送信息的用户可以安全的只让合法的接收者接收到所需的信息，而其 他非法用户则被屏蔽。由于这种密码体制满足了在计算机网络环境下的通信双方的需 求，所以这一领域虽然只有短短的几十年的时间，但投入的研究人员之多，他们来自 学科之广，发表论文之多，发展迅速之快，是其他任何- f l 学科所不能比的。所以， 在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 ) 体制，后来关于这一领域的研究如雨后春笋，不仅提出了一系列 公钥密码体制，还由此引出了很多应用与新的概念，例如，公钥密码体制用于数字签 3 硕士论文 基于有限自动机理论的公钥加密算法研究 名，概率加密体制，自动机加密体制，门限方案等等。同时也有一些公钥密码体制被 先后破译，这就形成了较为系统得公钥密码学。 公钥加密算法用一个密钥对信息进行加密，而用另一个不同但是相关的密钥对 加密后的信息进行解密，所以，该体制中加密密钥和解密密钥是分开的，并将加密密 钥公开，解密密钥保密，每个用户都拥有两个密钥即加密密钥和解密密钥，并且所有 的公开钥都被记录在类似电话号码薄的密钥本中。所以这种密码体制的安全性是从己 知的公开钥、加密算法与在信道中截获的密文不能求出明文或密钥。所以其的特性有： 仅仅知道加密算法和加密密钥而要确定解密密钥，在计算上是不可行的，且两个相关 密钥中任何一个都可以用作加密而让另一个用作解密。 下图是一般公钥密码体制的示意图( 卜2 ) ，其中巨西表示加密算法，表示解 密算法，必须满足如下三个条件： ( 1 ) 是的逆变换，即v m m ( 明文空间) ，有 ( 力= ( ( 埘) ) = m ( 2 ) 在已知用户b 的公开钥和秘密钥的条件下，d 肺和e 厶均是多项式 时间的确定性算法。 ( 3 ) 对 v m m ，找到算法d 。使d 。( 层肛屉伽) ) = m 是困难的，就是说 在现有的资源和算法下，寻找d 。是不现实的。 图1 - 2 公钥密码体制示意图 图中墨。表示用户占的公开密钥，置。表示用户曰的秘密密钥，其整个通信过程 是：任一用户彳，想与用户曰通信，首先爿用占的公开密钥墨。对欲传送的明文m 加 密得到密文c ，当用户口接收到a 发送来的密文m 后，口用自己的密钥x 。对密文c 进 行解密得到明文m 。 如果一个函数，对它的定义域上的任意x 都易于计算f ( x ) ，而对于厂的值域 中几乎所有的y ，当，已知时在“多项式时间”内计算f _ 1 ( 力是不可行的，这样的， 就是单向函数。如果当给定某些辅助信息时则易于计算单向函数厂的逆厂一，这样就 称，是一个陷门单向函数。容易看出，设计公钥密码体制主要就是寻找限门单向函数， 通常选择n p 问题或n p c 问题作为构造公钥密码体制的数学基础。 4 颂十论文基于育限自动机理论的公钥加密算法研究 1 4 数字签名简介 在秘密通信过程中，如何才能使接收方确信他所收到的信息确实是发送法所发 送的? 如何确定这个信息没有被窜改? 解决这个问题的方法称为数字签名。数字签名 的工作原理是，发送法在发送信息前，先用自己的密钥队明文进行加密，然后在用对 方的空开钥加密，从而得到密文。当接收方接收到信息后，先用自己的密钥解密，再 用发送方的空开钥解密，从而得到明文，因为有了发送法用自己的密钥加密的存在， 所以接收方可以确信这个信息确实是发送方所发。 在公钥密码体制中，如果加、解密算法e ，d 是可交换的互逆变换，即v m m ( 明 文空间) ，有d ( e ) ) = e ( d ( 聊) ) = m ，则可以利用此加密体制来实现数字签名，这样 的公钥加密体制称为可用于数字签名的公钥加密体制。 假设用户a 欲发送一个签了名明文m 给用户b ，则操作过程是： ( 1 ) a 先用自己的密钥d a 对m 进行变换s = d a ( m ) ； ( 2 ) a 再利用用户b 的空开钥对s 进行变换，= e b ( d a ( m ) ) ，并将 发送给用户b 。 ( 3 ) 当b 收到一后，用他的密钥d b ，进行变换，得到： d b ( s ) = d b ( e b ( d a ( m ) ) = d a ( m ) 。 ( 4 ) b 再用用户a 的公开钥e a 进行变换：e a ( d a ( m ) ) = m 。 这样用户b 就得到了签了名的明文m 。由于除了a 之外，任何人都无法由i n 得到s ，所以这样b 就可以确信他收到了来自a 的信息，而且a 也无法否认他发送过 明文m 1 1 。 1 5 论题的引入及论文的结构 随着密码学研究的深入，科学家们又不断地提出各种新的加密算法和新的密码 体制。加密算法多种多样，例如：背包问题，整数分解问题，离散对数，丢番图方程， 二次背包问题等等，新的密码体制也各有所长，如：概率加密系统，椭圆曲线密码系 统，热流密码系统，混沌密码系统，量子密码系统等。 在1 9 8 5 年，我国学者陶仁骥和陈世华利用有限自动机可逆性理论提出了有限自 动机公钥密码体制( f a p k c ) ，并在此后陆续提出了该体制的一系列算法，该体制在国 际上有着一定的影响，国际上称为陶陈体制。这是提出的第一个属于序列密码范畴的 公钥密码体制。由于只涉及到逻辑运算，该体制实现起来比较简单，运算速度也比较 快。该体制的理论基础是有限自动机的可逆性，利用这一特性我们可以先用已知的自 动机对明文进行加密，然后再利用相应的逆自动机解密，从而恢复明文。再提出了这 5 硕士论文 基于有限自动机理论的公钥加密算法研究 里密码体制后，陶仁骥和陈世华两位科学家又相继提出了多个自动机加密算法即 f a p k c 加密系列，同时这些算法还使用于数字签名。 因为自动机密码体制是基于自动机的可逆性这个理论基础的，所以本文的组织 结构是这样安排的： ( i ) 第二章简单介绍自动机的理论基础，以及自动机理论与密码学结合的原 理，和自动机加密的理论基础和实现过程。 ( 2 ) 第三章介绍f a p k c o 和f a p k c i 算法。 ( 3 ) 第四一六章分别介绍f a p k c 2 ，f a p k c 3 和f a p k c 4 算法，并且对部分算法进 行改进。 ( 4 ) 第七章介绍在f a p k c 4 的基础上提出的一个新的算法。 ( 5 ) 最后对本文做一个扼要的总结，并且展望该研究领域的发展方向。 6 硕士论文摹于有限自动机理论的公钥加密算法研究 第二章有限自动机理论 2 1 有限自动机的基本概念 自动机理论( a u t o m a t at h e o r y ) 主要研究离散数字系统的功能、结构及其关系随 着微电子技术和信息科学的发展，自动机理论向信息技术的各个应用领域渗透，为它 们提供理论模型、设计技术和运行算法自动机理论的研究领域主要包括：有限自动机 理论、无限自动机理论、概率自动机理论、复自动机理论( 如细胞自动机和图自动机 等) 以及抽象自动机理论等。 有限自动机( f i n i t ea u t o m a t a ) 理论是自动机理论的一个的分支从本质上讲有 限自动机是从一些具体的动态离散数字系统中抽象出来的数学模型，一般情况下，一 个有限自动机肘可以表示成一个五元组m = ，其中x ，】，和s 是三个 非空有限集，分别称为m 的输入字母表，输出字母表和状态字母表；万是迪卡儿积 集s x x 到s 的单值映射，称为吖的下一状态函数，a 是s x x 到y 的单值映射，称 为肘的输出函数【i j 。若在肘的初始状态s ( o ) 下输入序列x ( o ) ，膏( 1 ) ，产生的输出 序列) ，( o ) ，y ( d ，则有； y ( f ) = 2 ( s ( o ，工( 功 j ( f + 1 ) = 8 ( s ( o ，工( f ) ) ，扫o ，l ，2 ， 另外，对于集合a ，用彳”表示a 上所有有限长序列的集合( 包括空序列。) ，彳。表 示a 上所有无限长序列的集合。按下面的方法可以将万和名扩充到s x “和 ( s x ”u x 。) ) 上： 万g ，占) = s , 8 ( s ，c ) = 万p o ，口) 工) 五g ，s ) = 岛五g ，肛) = 五g ，x ) 2 ( 8 ( s ，x ) ，) 其中s s ，z x ，口e x ”，e l r ”u x ”) 。 如果是y x “1 到y 的单值映射，而有限自动机m = x ，l s ，8 ，五 由下式定 义： y ( i ) - - 【y o i l ，y ( f k ) ，x f i ) ，工( f 1 ) ，工( f 一 ) ) f = o ，1 ，2 ， 则肘称为个( 向，七) 阶存贮有限自动机，记作 如x ，y 矿x s , 艿，五 ，即： s = y t ，y - l y ，善一 ，善q z 7 n；儿“；“ 仃川u 料 心 y - k + i y i 厂( j ，一后，y - 1 ，x - h ，工一i ，工) 工“ t l x = f ( y - k , y - l ，h ，x - 1 ，功 y - k ，y - i y t x _ t x 此时如果k = o ，则 如称为一个而阶存贮有限自动机。但如果肘由下式决定： y ( i ) = 妒o 一七) ，y o 1 ) ，x ( i - k 一矗) ，x ( i 一七) ) ，f = 七，k + 1 ，矗，k 0 ，贝u 肘为拟( ，k ) 阶存贮有限自动机，其中： s = 斟 y o ，y k - l y ，t ，x i x y l ：y k - i ( _ ，o ，y k - 1 ，善 ，童一l ，x ) x - h + i x - 1 工 8 蜘；肛b；- 旷u 硕士论文基于有限自动机理论的公钥加密算法研究 = ( ，y t 十x - h ，x - i ，工) y o ，几4 l x _ h ，x _ l x 如果8 ( s ，x ) 和五( s ，都不依赖x ，则称m 为自治的，显然，当m 是自治有限自动机 时，输入已不起作用，故可将m 记作： 4 1 。 2 2 有限自动机的叠加和可逆性 设m x ，l s ，艿，五 是一个有限自动机。 若对于任何状态s 和，无穷输入序列口和口，都有t ( s ，口) = 五( ，) 推出口= 口， 则称膨是可逆的。 若对于任何状态j 和，j 长t + i 输入序列口= ( x o ，而，) 和口= ( x o ，而，x r ) ， 都有旯( s ，口) = 五( ，) 推出x o = x o ，则称m 是延迟f 步可逆的，显然肘延迟f 步可 逆的充分必要条件是对于任何长f + 1 的输入序列口= ( x o ，毛，) ，其都由五( s 口) 惟一决定 设m 。= 为一有限自动机。若对于j s ，s 。，m 的无穷输入序 列口= ( x o ，而，) ，都有刀o ，五( j ，口) ) = ( t ，x - l ，x o ，五，) ，则称m 是肼的延迟f 步 逆，称肘是膨是原逆，称( s t , s ) 是一延迟f 步匹配对。 若对任何状态j ，无穷输入序列口和，都有旯( s ，口) = 五o ，) 推出口= ，则称 m 是弱可逆的。 若对于任何状态j ，长f + l 输入序列口= ( x o ，墨) 和= ( ，x t ，) ，都有 五( 凡口) = 五( s ，) 推出x o = x o ，则称m 是延迟f 步弱可逆的，显然m 延迟f 步可逆的 充分必要条件是对于任何长f + 1 的输入序列口= ( x o ，x 1 ，x r ) ，其都由j ，五0 ，口) 惟 一决定 设m - 为一有限自动机。若对于s s ，都存在s 使m 的无 穷输入序列口= ( x o ，而，一) ，都有刀0 ，五( 以口) ) = ( x - f ，码，一，”) ，则称肘是肘的 延迟r 步弱逆，称m 是m 是弱原逆【”。 任意两个有限自动机m 置，r ，s ，巧，丑 f = 1 , 2 ，满足条件l j ：= x 2 ，以 c ( m 。，m 2 ) 表示m 。和肼2 的叠加，即有限自动机 ，其中有 9 1，j；h；h 硕士论丈 基于有限自动机理论的公钥加密算法研究 占( ，z ) = 五( 砷= 五0 2 ， ( q ，膏) ) ，毛s ，j 2 是，x e x 设，g 分别是形“到v 和u 7 v p “到u 的单值映射。则肘，、肘。分别是t 阶输 入存贮有限自动机和( p ，) 阶存贮有限自动机。则m ，和m 。的组合有限自动机 c r ，肼。) 是由下式定义的( p + ，) 阶存贮有限自动机： “( f ) = g ( 0 ( f l l ，”( f 一，工厂( w ( f l ，w ( f f 强，( w ( f p ) w ( f p f ) ) ) i = 1 , 2 如果想进一步的了解有限自动机和有限自动机可逆性理论，请参考文献 1 儿4 。 2 3 线性有限自动机的构造 文献 4 中还给出了利用巧和心- 1 变换构造线性有限自动机的方法，下面首先介 绍一下这两个变换。 2 3 1 r o 。1 变换 设q = k 班7 驴l 川晰+ 。，满足条件：。 b b l o k 1 的行线性无关，口。m = 。，则 可对q 进行行的初等变换，但不改变它的前坍廿行，即q 可以左乘以矩阵，形 砭= 巨一。 呓( ) 砭 使得结果矩阵q = p g i - - 4 独】川。r + 1 ) 中m m = m t ，f = l ，k - i ， m h = 历肚+ 肼) i ，其中e 为研n 级单位矩阵，p h 为m h 级非奇异矩阵。 用记号g i 吐止g k 表示按规则r - 1 a 将g 。i 左乘以p k 变换到q 。 2 3 2 r s 。1 变换 厶。焉。山椰删件：吲尚删 b m x - l m l ) = 0 ，则可以将q + l 的最末一排矩阵( 即最后拼( i + i x ) 行) 右移所+ ，位， 硕十论文 基于有限自动机理论的公钥加密算法研究 补入0 ，结果为g i = 【厶】( 晰+ ，+ l ，m n = 脚t ，f = l ，k + 1 。 用记号g 。坐一g 。表示按规则巧1 将q 。变换到q 。 对q = 【爿扯】川。，+ 1 ) 和g - 【彳耻b 聃】州m 。，+ 1 ) 我们定义 k ：j m 如h i 彳驰2 o _ ，= _ f ，而一l ，爿* 有定义且不为o1当m m o 彳c七，=三： 4c七，=三2二。 这里约定，当( 或砬) 无定义时，钆( 或4 - 。) 无定义。 以c ( 七) 表示条件：= o , i = l ，| i ，= 呵，一l ；= 1 - i ，i = l ，七；当q 不 扛1 ，k ；a ( k 1 非奇异。 以c 。 ) 表示条件：颤= o , i = l ，k + l ，= 吖，一1 ；碗= l 一f = l ，k ， 咄椰= l k 当e 不完全定义且以o 时，厶和磙在， j r + 2 - i ， 在其他处都有定义，i = l ，k ，当q 不完全定义且咄。坤o 时，以+ 。m 和壤+ ，m 在 2 3 3 构造线性自动机 下面我们给出一个具体的构造有限自动机的例子： 设肘 g f ( q ) f ( r ，1 阶存贮线性有限自动机，定义如下： y ( 力= a f f ( i 一_ ，) + 只膏( f d j 。1一 i ：0 。12 一 其中a 力g f ( q ) j 2 m 级矩阵，b 为舒( g ) 上埘x ，矩阵，m ， o 。 基于以上的变换规则，我们可以得到一个构造延迟f 步弱可逆( ，) 阶存贮线性有 限自动机的方法( ，f ) ： ( 1 ) 求出一个所p + ，+ 1 ) 伽+ ，) ( 不完全定义) 矩阵q + l ，g f “满足条件c ( f + 1 ) ， 硕士论文基于有限自动机理论的公钥加密算法研究 蠢：。， 的列线性无关， 芝 的行线性无关，且当，：。时，4 。：一e 。 蓐- ，巧1 陋蓐石口 ( 2 ) 作一个变换序列g r + l _ 寸g f 专寸g 2 专g ：；g l ，其中 巧一r l s , 1 j 一。取彳j - - - - a i i i , q = _ ，= o ，r ，则由( 1 ) 式定义r ) 阶 存贮线性有限自动机延迟f 步弱可逆。 ( 3 ) 任何延迟f 步弱可逆( ，) 阶存贮线性有限自动机m 皆可由( 1 ) ( 2 ) 的步骤得 到。 同理，我们可以构造一个f 步弱逆的( ，r ) 阶存贮线性有限自动，步骤如下： ( 1 ) 求出一个m x ( f + r + 1 ) ( m + f ) 矩阵g f + l ，g f + i 满足条件c o + 1 ) ， 置州) & f + 1 ) 0 ( f + 1 ) 的 列线性无关，且当f = o 时，4 m = - e 。 蓐t 石陋石- 巧1 m ( 2 ) 作一个变换序列g f + i 寸专g f 专_ g 2 _ q 专g i ，其中 丑= 一眨 - i 取4 = a i j i , e 吨= o ，舳式定义嘶 ，) 阶 存贮线性有限自动机延迟r 步弱逆。 ( 3 ) 任何延迟f 步弱逆( ，) 阶存贮线性有限自动机m 皆可由( 1 ) ( 2 ) 的步骤得到 4 i 。 2 4f a p k c 简介 1 9 8 5 年，陶仁骥和陈世华利用有限自动机可逆性理论提出了有限自动机公钥密码 体制( f a p k c ) 。同时也提出了一个具体的有限自动机公钥密码体制f a p k c o ，在1 9 8 6 年，陶仁骥和陈世华又又提出了f a p k c 的另外两种变形f a p k c i 和f a p k c 2 ，随后又相 继提出了f a p k c 3 和f a p k c 4 ，构成了一个有限自动机加密的算法系列。这几个算法共 同点是公钥中都有一个组合自动机c ( 肘。， “) ，但是每个算法又有不同点，主要体现 在其中的两个有限自动机m 和眠上： 1 2 硕士论文 基于有限自动机理论的公钥加密算法研究 f a p k c o ：m l 是延迟0 步弱可逆的，阶输入存储非线性有限自动机，m 。是延迟f 步 弱可逆的( f ，r ) 阶存储线性有限自动机。 f a p k c l ：m l 是延迟o 步弱可逆的，阶输入存储非线性有限自动机，m 。是延迟r 步 弱逆的，阶输入存储线性有限自动机。 f a p k c 2 ：m l 是延迟f 步弱可逆r 阶输入存储非线性有限自动机， 厶是延迟f 步 弱逆的r 阶输入存储线性有限自动机。 f a p k c 3 ：m 是延迟f 步弱可逆的啊阶输入存储有限自动机， 厶是延迟f 步弱可 逆的阮，) 阶存储有限自动机。 f a p k c 4 ：m i 是延迟f 步弱可逆的啊阶输入存储有限自动机，膨。是延迟f 步弱 可逆的( ，知) 阶存储有限自动机。 下面，我们以f a p k c 3 为例来介绍一下有限自动机公钥加密体制的基本算法： 1 生成密钥 1 ) 构造一个( ，k 。) 阶存贮有限自动机m 。= 和一个 ( + f o ，) 阶存贮有限自动机m 。- ，使得： 对于任意的知= 7 氐，任意的x 0 , 工l ，x ，记 儿咒= ( s o ，x o x l ) ，则有厶( j f o ，y y “) = x o x i ，其中 j 钿= 1 e s o ； 对于任意的”= 7 & ，令 = t 。s o ，对于任意的朋乃y ，记 x o x i = ( s o ”，y o y l ”) ，则有五( ，x o x ! ) = y - r e 儿i y o y i 。 2 ) 构造一个啊阶输入存贮有限自动机m l x ，x ，墨，4 ，丑 ，和一个 ( 1 ，啊) 阶输入存贮有限自动机m l x ，z ，墨，4 ， 。 ，使得： 对于任意的= 7 s o ，任意的x o ，而，x ，记 x o 而= ( ，工。而) ，则有 ( j ，x r t 工 “) = x o x i ，其中 j q 。= s l ； 对任意的岛。= 7 墨，任意的，而，x ，记 x o x i = ( 毛，x o 工l ) 贝q 有 ( ，x n x “) = x o 。x t ，其中 = r s 3 ) 由峨和肘。组合而成的有限自动机为m = c ( m ，帆) = 。 4 ) 记f = m a x ( v o ，f i ，i l o ) ，任选只i ，) ，+ ，y ，任意的 s o - r ，= r s o ，及任意的 s l f ，= 7 墨，记： j - f 叶l ，x - i ，= 厶( s o f ，) 0 1 ，y - i 一) ，$ o , s - - 氏( s o - f ，y 十 ，y l ，) k ，x i ，= ( s l - - f , $ j f 叶n j 工1 ，) ，j l j t - - - - 4 ( s l - f ，x 1 - t i ，- 】- l j 。) 1 3 硕士论文基于有限自动机理论的公钥加密算法研究 令s 删r = r ，甜- - - - 2 任选 = r s ，记： x k ，t 妇- ( x 1 ，x - k , - i ，】1 x ，工一 d ，x - i ，) ，令 j 删l 一= 1 x j 州。一= ： 5 ) 得到公钥：c ( m l ， 如) ，j “，v ，s 。，“+ f 1 得到密钥：，m l 。5 ，s a u t l , , d ，s “o ，f 0 ，f i 加密和解密过程：用户首先将欲发送的明文x o x i x n ，扩展f 0 + f 1 位得到： x o x l x 。x q + ，用公钥中的c ( m i ，m o ) 和s 。计算密文 儿几。+ 。= 五0 。，而x n + 。) 。当接收方收到密文后，利用密钥中的 如。和 s o t 。o 。d 以及公钥中的y 吨，j ，d 计算得到 。而x n + f t t = 厶。( 【h ，x l ，j ，“- l ，y 】，虼+ h + n ) ，然后再利用m 1 和j “g d 计算得到明文x o x l x 。= ( f h ，x 吨，x n l ，】，x n x q 。) 。 签名和验证过程：把信息儿y i 虬扩展+ f i 位得到：y o y l n + f o + ，用密钥中 的眠，m i ，岛，毛，计算得到签名： x o x l x n + f + = ( s ，f ，厶( s o , , y o y l y n + r + r t ) ) ，验证时用公钥中的c ( m l ，m o ) ， 毒，j 村r ，找出j = 2 ，验证五( 晶y + 1 只+ 如+ n ) 是否等于儿j ，l 儿 以上就是自动机公钥加密算法的原理和运算过程，不过不同的算法构造的自动 机有所不同，最后产生的的公开钥和密钥也有所差别。需要注意的是在具体实现时， 可以选取有限自动机m 。为线性的。而选取非线性有限自动机时，应考虑到安全性与 实用性的权衡折衷，以便使密钥长度适中，计算速度较快。 2 5 小结 本章主要介绍了自动机的基础知识，包括基本概念，可逆性，以及自动机的叠加 和构造，最后简单介绍了几个f a p k c 算法及自动机加密解密，数字签名和验证的原理 和运算过程。这一部分是本课题的基础，我们只有对这些知识有较深刻的了解并掌握 它们，才能在本领域取得有价值的研究成果。 1 4 硕士论文 基于有限自动机理论的公钥加密算法研究 1 9 8 5 年，陶仁骥和陈世华利用有限自动机可逆性理论提出了有限自动机公钥密 码体制( f a p k c ) 。同时也提出了一个具体的有限自动机公钥密码体制f a p k c o ，具体细 节请参考文献 9 。1 9 8 6 年，陶仁骥和陈世华又提出了f a p k c o 的两个变形，f a p k c i 和f a p k c 2 。其中f a p k c i 体制与f a p k c o 体制大致相同，所以本章就主要介绍f a p k c o 体制，简单介绍一下f a p k c l 体制，在最后会对两者作一个简单的比较，关于f a p k c i 体制的详细信息请参考文献 1 2 。 3 if a p k c o 密码体制 f a p