Research, Public Key Encryption Algorithm Based On Finite Automata Theory

Encrypting technology is the core of the securities of the information. Nowadays, in the computer network environment, all the confidentiality, security, integrality, usability and nonrepudiation of the information must be resolved by encrypting technology. On the whole the cryptography has two parts: symmetric cryptosystem (one-key or private key cryptosystem), asymmetric cryptosystem (two-key or public key cryptosystem) , and the latter takes more important role in negotiating key, digital signature and message validation, etc in the securities of the information, so it is the most important cryptosystem.In this paper we discuss one public key cryptosystem which based on the theory of the finite automaton. This cryptosystem was proposed by Tao Renji and Chen Shihua, and works by using the invertibility theory of finite automata to complete the encrypting, decrypting and signature function. In the paper we first introduce the knowledge of the finite automaton and the theory of the cryptosystem based on finite automaton. Then we discuss some important algorithms proposed in the development of this cryptosystem, also do some work to improve on some ones. At last we first prove that it is viable to extend the automata in FAPKC4 algorithm to the free-memory automata. Based on the new extended FAPKC4, and with compounding multiple automata, we construct a new algorithm and implement it. This algorithm can be used to encrypt and implement digital signatures, and still retains merits of early FAPKC's such as the fast speed, relatively short public key etc. Because the new algorithm extends the state component of the automata, which makes constructing automata more complex, the security will be improved and it's harder to break into this cryptosystem.