论文部分内容阅读
前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题。对延迟步数≥3的前馈逆结构的刻划则是一个长期的未解决问题,尤其是当希望给出输出函数的显表达式时,这种刻划更加困难。弱可逆有限自动机的分解是有限自动机可逆性理论中的另一个问题,由鲍丰在1993年首次提出,目前它并没有得到深入的研究。本文主要研究了这两个课题。 在第一章,我们介绍有限自动机可逆性理论产生的背景、核心概念、主要研究内容、以及它在公钥密码学上的应用-有限自动机公开钥密码体制(FAPKC)。 在第二章,我们研究了二元延迟3步前馈逆有限自动机的结构。对于输入输出字母表大小相等且为2的c阶半输入存贮有限自动机M=c(Ma,f),其中自治有限自动机Ma的状态为一回路。当C(Ma,f)延迟3步弱可逆时,可将其按长3极小输出权W3,M分为W3,M=1,2,4,8四种所有可能情形。我们给出了延迟3步弱可逆的C(Ma,f)在长3极小输出权W3,M=1,2,8三种情形下f的表达式和某些关系式,并证明了满足这些表达式和关系式的C(Ma,f)就是延迟3步弱可逆的。由于C(Ma,f)延迟3步弱可逆当且仅当它是延迟3步弱逆,因此这就给出了二元延迟3步前馈逆有限自动机结构的一种部分刻划,这是一个在刻划延迟步数≥3的前馈逆有限自动机的结构方面有科学意义的结果。 在第三章,我们利用有限自动机输出权研究了弱可逆有限自动机的分解,得到如下结果。(1)主要定理:假设M是一个n元延迟T步弱可逆有限自动机,则M可分解为一个延迟0步弱可逆有限自动机和一个T阶延迟元当且仅当|WT,SM|=1对M中任何状态s成立。应用这一定理我们证明了(2)存在一类不能进行这种分解的弱可逆有限自动机。(3)从(2)中构造出例子,否定回答了1993年的一个未解决问题。(4)给出了二元严格延迟T步强连通弱可逆有限自动机可分解为严格延迟T-1步弱可逆有限自动机和严格延迟1步弱可逆有限自动机的一种充分条件。(5)找到了一类可以通过合成的方法构造出的n元延迟T步,且所有状态的延迟步数都为T的弱可逆有限自动机。 在第四章,我们提出了一种基于有限自动机签名体制的同时签名方案。该方案满足同时签名的安全性要求,即正确性、不可伪造性、模糊性和公平性。 在第五章,我们列出了一些目前未解决的问题及将来进一步要做的工作。