The Research And Implemention Of Finite Automaton Public Key Cryptosystem

The Finite Automaton Public Key Cryptosystem (FAPKC) which is the first time-sequence public key cryptosystem was invented by two Chinese cryptographers Tao Renji and Chen shihua in 1985. Compared to some popular public key systems, FAPKC is easy to implement and has higher speed due to using logical operations. It caused lots of interests after being presented. So far, there have been more than 6 FAPKC algorithms and varieties proposed. With the development of the finite automaton invertibility theory, FAPKC will be analyzed and practiced more and more.The FAPKC is developed from the first algorithm FAPKCO to FAPKC3 and FAPKC4. The known attack methods are reduced echelon matrix attack, linear R_aR_b attack, stochastic search attack, etc. In this thesis we summarize the above algorithms and the corresponding cryptanalysis.This paper chiefly refers to the following works. Firstly, we analyse the stochastic search attack of FAPKC3, using reduced echelon matrix method, and proposing a searching algorithm RSS based on the equivalent linear RaRb transformation. We estimate the seaching success probability of RSS, which has higher probability and is more suitable for FAPKC3. Secondly, as the disadvantage of mostly-often used nonlinear operator AND in FAPKC, we design a new nonlinear operator based on Upper-Triangle Matrix Method proposed by Meskanen. We programs for the amending algorithms and presents the implementing results in this thesis.At last, some open questions and future work are disscussed.