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

Algebraic Theory of Nonlinear Finite Automata ——With Applications in Analyses of FAPKC3

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

A Semi -ring is introduced to describe input memory finite automata and their compositions; an algebraic treatment is given to the weak invertibility theory of nonlinear finite automata,relative basic decomposition and the concept of nonlinear kernel are introduced. As applications, a method called'nonlinear kernel attack 'is proposed to analysis of the public key cryptosystem FAPKC3([l]); to resist this attack,three criterions for the nonlinear kernel of a private key in this scheme are proposed ,and it is pointed out that, whether there exist enough (to make a key bank)keys fitting into these criterions and how to construct them is still a problem to be further investigated.