Constructing Finite Automata with Invertibility bytransformation Method

Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.

Cryptanalysis on a finite automaton public key cryptosystem

An attack algorithm is proposed on a finite automaton public key cryptosystem.It is proved that this attack can break FAPKCO in polynomial time.The basic idea can be used in principle to attack other FAPKCs.Therefore,while designing an FAPKC,it must be taken into account whether it is secure or not under this kind of attack.

The generalization of public key cryptosystem FAPKC4

FAPKC4, a public key cryptosystem based on automata theory, is generalized so that component automata of compound automata in user’s public key would not be restricted to memory finite automata. The generalized FAPKCA can be used in encryption and implementing digital signatures as well.

FAPKC3: A New Finite Automaton PublicKey Cryptosystem

This paper deals with finite automaton public key cryptosystem and digital signatures. A new system FAPKC3 is proposed which can be used for encryption and implementing digital signatures as well. Some performances of a software implementation of FAPKC3 are presented and its security is discussed.

有限自动机理论的公钥加密算法的研究与改进

该文讨论的是基于有限自动机理论的公钥加密体制。该体制的工作原理是利用有限自动机的可逆性来完成加密、解密以及数字签名等功能。文中对该密码体制进行分析讨论并提出了构造可逆自动机的一种改进方法,提高了可逆自动机的复杂度,进一步增强了算法的安全性,同时也保持了密钥短,速度快等优点。

二元弱可逆有限自动机延迟步数的分解

本文考虑二元严格延迟τ步弱可逆有限自动机Ｍ的延迟步数的分解问题．首先证明如果Ｍ强连通且所有状态的延迟步数不小于τ－１，则Ｍ一定能分解为一个延迟０步弱可逆有限自动机和一个τ阶延迟元．然后证明如果Ｍ所有状态延迟步数均不小于ｍ，那么Ｍ可以分解为一个严格延迟τ－ｍ步弱可逆有限自动机和一个ｍ阶延迟元．最后考虑了Ｍ可分解为一个严格延迟τ－１步和一个严格延迟１步弱可逆有限自动机的条件．

非线性有限自动机的代数理论——兼谈FAPKC3公钥密码体制

引入半环描述输入存贮有限自动机及其复合运算,对非线性有限自动机的弱可逆性理论进行了代数化处理,提出相对基本分解并引出非线性核的概念等。作为应用,对FAPKC3公钥体制(文献[1])提出称之为“非线性核攻击”的攻击方法,由此提出该体制中私钥的非线性核必须符合的三条准则,并指出是否存在以及如何构造足够多的符合这些准则的密钥是有待研究的问题。