Research And Application Of The Public Key Cryptosystem Based On Several Error-correcting Codes

Public key cryptosystem based on error-correct codes is mainly founded on the hard problem about decoding of linear codes. Unlike RSA or ECC, the public key cryptosystem, which not based on big prime decomposition or discrete logarithm, is generally acknowledged to have the ability resisting against quantum attack. However, excessive key storage of this scheme restricts its application. In this thesis, we focus on code structure, utilize some special matrix structure, such as Cyclic Matrix, Cauchy Matrix, Cyclic Symmetric Matrix, and adopt traditional crypto idea of systems like Mc Eliece and Niederreiter. Our aim is to design a new cryptosystem with high security and tiny key storage amount based on error-correct codes. Main contents of our thesis are as follows:At first, we construct a new primitive BCH codes with similar cyclic structure. To achieve it, we start with primitive BCH codes firstly by choosing primitive code sets randomly, and utilize symmetric group to make linear vector transform for these sets. We then choose the matrix generated randomly as distributed matrix and create keys for encryption and decryption. We introduce random error vector, it can strengthen whole system’s safety. As a result, the amount of public key decreases obviously and security of whole system gets improvement by building this BCH codes.Secondly, we propose a method to generate a Goppa codes with quasi-bivalence. Owing to binary Goppa codes is the fundamental element of classical Mc Eliece cryptosystem, the system’s security get strengthen while the amount of public key becomes large. This method based on Goppa codes is to construct a bivalent matrix with Cauchy Matrix ’s feature. Adopting this code not only can guarantee the security of classical Mc Eliece, but also enhance the efficiency of key storage.Thirdly, we compose a middle-density parity-check(MDPC) code with the ability of resisting against low-weight searching attack. Considering schemes with some special Boolean structure are easily to be attacked and lead to the risk of recovering public key from private key. We rethink it in a perspective of graph-based error correction code and utilize the special property of its check matrix to create this MDPC codes. In this process we combine definitions of block cyclic and cyclic symmetric structures, we also introduce cyclic randomly generated matrices to create public/private key pairs based on our MDPC codes and the constructing idea of Niederreiter cryptosystem. Then the result is remarkable decrease of public-key storage.In the last, we establish a CFS signature scheme based on p-Goppa codes. Combining the above cryptosystem based on Goppa codes with quasi-bivalence, we give transform algorithm by proving to support this scheme. What’s more, we associate RFID system with the cryptosystem of MDPC code and add initialization vector in RFID’s tags, to realize wireless encrypted secure transmission between tags and readers. This strategy can resist attacks of replay, eavesdropping and counterfeit.